This is a bunch of notes taken from the classes if you want to read through them again
Last active
December 2, 2020 14:43
-
-
Save DusterTheFirst/2f6ad4b0411eac38610acc045809c375 to your computer and use it in GitHub Desktop.
ECS Notes Orange
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| *.rkt |
| Designing Data | Designing Functions |
|---|---|
| Data Definition - what kind of data is allowed | Signature - what kind of data goes in and what kind of data comes out? |
| Interpretation - what does this data mean? | Purpose - what does this function do? |
| Examples (at least 2) | Testing - examples of how the function works (using check-expect) |
| Template (see Designing Templates) | Code - using the template |
- How many cases of data are there? If there is more than one option, you will need a conditional expression (this happens when you have union data)
- How can you tell the cases apart? This will determine the question you ask in each clause of your conditional expression. You can skip this step if you are not working with union data.
- What can you pull out of the data in each case? If it is structured data you must call the selectors here.
- Is the data you pilled out complex with its own data definition? If you are referencing another data definition that you made, you need to call the template for that data type on the selected data.
- What changes and what stays the same? Things that stay the same are constants and things that change are your WorldState (you may need to design your own data here).
- Which clauses do we need? Your options are:
to-draw,on-tick,on-mouse,on-keyandstop-when. - Design your main function (the one that calls
big-bang). This is the only function you cannot write tests for. Make a wishlist of the functions you need to design. - Design the functions on your wishlist. Be sure to follow all the steps of the function design recipe when you do so.
Jump to TL;DR (summary)
Jump to Table Of Contents
Code for this lesson on wescheme
Design a function message-to-employee which takes in the kind of data you defined above and produces a message about the employee’s paycheck. For example if the employee receives a paycheck every week you should produce “Here is your weekly paycheck!”. Is the template useful here? Why or why not?
Define what the data is
Paycheck can be weekly, biweekly, or monthly.
What does it represent?
Paycheck represents how often an employee is paid.
Now that we have it all in our head, we should put it down in a comment:
; A Paycheck is one of:
; - "weekly"
; - "biweekly"
; - "monthly"
; and represents how often an employee is paidOnce you have the idea, define some constants (if there are a finite amount).
(define PC-W "weekly")
(define PC-B "biweekly")
(define PC-M "monthly")Once you have the idea and the data, create a template:
(define (paycheck-template pc)
(cond [(string=? pc PC-W) ...]
[(string=? pc PC-B) ...]
[(string=? pc PC-M) ...]))The
...s are not valid scheme, they just tell us that we will come back to them later.
Now we can move onto creating a function to tell the employee about their paycheck. Always start by laying out the function you want.
Name: message-to-employee
Input: Paycheck
Output: String
Description: Message an employee about when their paycheck arrives.
Now that you have it in your head, put it in a comment.
; message-to-employee : Paycheck -> String
; Message an employee about when their paycheck arrivesOnce you have the layout of your function, ALWAYS write out (at least) 2 check-expect tests.
(check-expect
(message-to-employee PC-W)
"Here is your weekly paycheck!")
(check-expect
(message-to-employee PC-B)
"Here is your biweekly paycheck!")
(check-expect
(message-to-employee PC-M)
"Here is your monthly paycheck!")In this case, we create 3 tests since there are 3 variants of our type.
Now that we have it all layed out, we can create a function by pasting our template.
(define (message-to-employee pc)
(cond [(string=? pc PC-W) ...]
[(string=? pc PC-B) ...]
[(string=? pc PC-M) ...]))Now we need to change the ...s to something more useful.
In our case, the ...s would all become the same thing:
(define (message-to-employee pc)
(cond [(string=? pc PC-W) (string-append "Here is your " pc " paycheck!")]
[(string=? pc PC-B) (string-append "Here is your " pc " paycheck!")]
[(string=? pc PC-M) (string-append "Here is your " pc " paycheck!")]))Since they are all the same, we can simplify the function down to just one line.
(define (message-to-employee pc)
(string-append "Here is your " pc " paycheck!"))In the end, our template and custom type were not used since they were more or less extrenious, we did not need to create a custom type for this since there is one code path for every paycheck type
Design a function calculate-annual which takes in a Number, representing the amount an employee makes on a single paycheck, and the data describing how often they receive the paycheck. It produces a Number with an estimate of their annual wages. For example, if the employee gets their paycheck once per month you will need to multiply the input number by 12 since there are 12 months in a year. Is the template useful here? Why or why not?
As always, start your function definition with its signature
Name: calculate-annual
Input: Number and Paycheck
Output: Number
Description: Estimates how much an employee will earn by the end of the year
Now that you have it all out, put it in a comment:
; calculate-annual : Number Paycheck -> Number
; Estimates how much an employee will earn by the end of the yearCheck expect time!
(check-expect (calculate-annual 4 PC-M) 48)
(check-expect (calculate-annual 34 PC-W) (* 34 52))
(check-expect (calculate-annual 450 PC-B) (* 450 26))Now that we have the check-expects all out, its time to make the function:
(define (calculate-annual single-paycheck pc)
(cond [(string=? pc PC-W) (* single-paycheck 52)]
[(string=? pc PC-B) (* single-paycheck 26)]
[(string=? pc PC-M) (* single-paycheck 12)]In this case, the custom data type is useful since we are able to use the seperate paths to calculate the paycheck differently
Design data to represent the name of someone who has donated to a charity. Your data should account for the fact that the donor may wish to remain anonymous. Why can’t we use a String to represent the anonymous donor? What can we use instead? Don’t forget to follow all 4 steps of the design recipe for data.
The first thing we need to do when defining a data type is to define what it can be:
; A DonorName is one of:
; - String
; - false
; and represents the name of someone donating to charityNow that we have our data type all layed out for us, we should now create (at least) 2 examples of the data type.
(define DONORNAME1 "Paul")
(define DONORNAME2 false)Once we have some examples we can make a template:
(define (donor-template dn)
(cond [(string? dn) ...]
[(boolean? dn) ...]))Remember, the ...s are there for us to replace later when we copy this template
Design a function email-donor which takes in the type of data you defined above. If the donor is not anonymous it produces a message to send via email such as “Thank you, Bob!” if the donor’s name was Bob. If the donor was anonymous it produces false. What kind of data do you need to design in order to write the signature for this function?
As always, start your function definition with its signature:
Name: email-donor
Input: DonorName
Output: String or false (we could make another data type, but to save time I will not)
Description: To send a message to the given donor if they are not anonymous
Now that you know it, put it in a comment:
; email-donor : DonorName -> String or false
; To send a message to the given donor if they are not anonymousNow that we have the signature, we can write some check expects
(check-expect (email-donor DONORNAME1) "Thank you, Paul!")
(check-expect (email-donor DONORNAME2) false)And finally, we can write the function itself, copying the template and replacing the ...s
(define (email-donor dn)
(cond [(string? dn) (string-append "Thank you, " dn "!")]
[(boolean? dn) false]))- Unions are useful for if you need to hold 2 different data types in the same spot
- Unions can be one data type or the other, but never both
- Unions are invisible to scheme, so scheme cannot enforce the types for us
- Unions can be separated using the
type?functions, such asstring?ornumber? - Cond is very powerful for using unions. ie. the above function
- ALWAYS define at least 2 examples of the union if it has an infinite amount of possibilities see Lab 2 Problem 4
- If Possible define all variants of the union (only for non infinite ones) see Lab 2 Problem 2
Jump to TL;DR (summary)
Jump to Table Of Contents
Code for this lesson on wescheme
In our previous text editor, we only used the text as the world state, limiting us to not be able to move the cursor around the screen
Currently, we can only store data one at a time, it could be a union (Such as a String or a Number) but it could never store both at the same time.
To hold more than 1 data at a time, we can use structures
When creating a structure, you should figure out what data you want to store.
For our example, we will create a structure to store an address. In an address,
we want to store a house-number, city, street, and zipcode.
As with all definitions, we want to start out with a comment describing it:
; An Address is a (make-address Nat String String String Nat)Nat in this case is used to tell us that it is a natural number
In the code snippet, we specify the name, and then a function make-address to create
an address, now to define it in scheme to actually use, we can use the define-struct tool
(define-struct address [house st city state zip])Now, once we have define-struct, we can create one using the automatically created make-address
function.
(make-address false "hello" 2 -7 true)and that would return
(address false "hello" 2 -7 true)Notice that this does not match our comment, but scheme cant read our comment, so it doesn't know better.
To make sure that we match our address definition, we can make some samples and a more detailed description of the structure.
The more detailed description looks like:
; and represents someone's address
; - where house is the house number
; - st s the name of the street
; - city is the name of the city
; - state is the abbreviation for the state
; - and zip is the zip codeand would be placed after the structure definition.
Now that we have a good description, we can make some samples for reference
(define ADDRESS1 (make-address 50 "Rice St" "Wellesley" "MA" 02482))
(define ADDRESS2 (make-address 1 "a" "b" "c" 7))Now that we have the structure defined, we need a way to access the different members of it. Lucky for us, Scheme creates a bunch of helper functions for us:
(address-<field> address)where <field> is replaced by the name of the field defined above. ie.
(address-house ADDRESS1)would return 50, since it is the value we put in the structure when we made it or "constructed it"
We can put all of these helper methods together into a template for future use
(define (address-template a)
(... (address-house a)
(address-st a)
(address-city a)
(address-state a)
(address-zip a) ...))Remember, the ...s are there for us to replace later when we copy the template function.
Another helper function created for us is the address? function which lets us check if
a type is an address.
(address? ADDRESS1) ; true
(address? (make-address false false false false false)) ; also true
(address? 3) ; falseThe second example returned true because scheme does not know about our capitol A Address type and does not know that we want the fields to be specific types. Because of that, as long as we made a structure using the
make-addressfunction scheme will see it as a structure
Now that we have the address structure created, we can make a student structure that uses our address structure as one of the fields. To start making our student structure, which will hold a name, year of graduation, and an address we start with the comment to describe it:
; A Student is a (make-stdnt String Nat Address)We are going to name our structure
stdntto help show that the name of the structure can be whatever you want
Once we have the comment, we need to tell scheme about it, using the define-struct tool
(define-struct stdnt [name gradyr house])Remember the names can be anything we want, but we need to use the same ones defined here later in our project, NOT the data type
Once we have the structure defined for scheme, we now need to describe each field
; and represents a student
; - where name is the student's full name
; - grad-yr is the student's graduation year
; - and house is the address where the student livesNow, we define 2 sample students:
(define STUDENT1 (make-stdnt "Sheev" 4 ADDRESS1))
(define STUDENT2 (make-stdnt "Alice" 1234567789 ADDRESS2))As always, after setting up the struct and creating the samples, we should create a template for us to use later.
(define (student-template s)
(... (stdnt-name s)
(stdnt-grad-yr s)
(address-template (stdnt-house s)) ...))Notice how in this template, we also use the address-template. That is because the house member of the
studentstructure is anaddressstructure, so we need to use the tools from the address-template to get the data out of the address
What if we want to use our new fandangled structure in a function? Well, lets try it out! As always, we can start by making a function, say one that adds one to a student's year-of-graduation (holds them back)
As always, start by laying out the function you want.
Name: stay-back
Input: Student
Output: Student
Description: Adds 1 to a student's graduation year.
And now we can put that into a nice comment for us to read:
; stay-back : Student -> Student
; Adds 1 to a Student's graduation yearOnce we have the comment for the function, we can create (at least) 2 check-expect tests to verify that it is working how we expect.
(check-expect
(stay-back STUDENT1)
(make-stdnt "Sheev" 5 ADDRESS1))
(check-expect
(stay-back STUDENT2)
(make-stdnt "Alice" 123456790 ADDRESS2))Okay, that all looks great, now we have to define the function:
(define (stay-back s)
(+ 1 (stdnt-gradyr s)))This above code with not work, remember you cannot modify a structure. In order to make a change, you have to create a whole new one, created from the old one with the new value in place of the old.
Heres how you would do that:
(define (stay-back s)
(make-stdnt (stdnt-name s) (+ 1 (stdnt-gradyr s)) (stdnt-house s)))Notice that we have to re-create the structure with
make-stdntbut with the difference being that the gradyr is now one more than the given
As always, start by laying out the function you want.
I know it can get repetitive, but your later self with thank you
Name: update-zip-for-student
Input: Student and Nat
Output: Student
Description: Update a student's zip code to be a new, given a new zip code
And now as a nice concise comment
; update-zip-for-student : Student Nat -> Student
; Update a student's zip code to be a new, given a new zip codeNow that we have the function all layed out, we can start with some check-expects
(check-expect
(update-zip-for-student STUDENT1 12345)
(make-stdnt "Sheev" 4
(make-address 50 "Rice St" "Wellesley" "MA" 12345)))
(check-expect
(update-zip-for-student STUDENT2 98765)
(make-stdnt "Alice" 123456789
(make-address 1 "a" "b" "c" 98765)))Looks normal, and it is, all that changes is the zip code. This should be easy, right?
Well yes, but we have a lot of writing to do. We can define our function, copying the student template, but, we cant just update the zip by replacing the last parameter with a new zip code, cause it takes in a whole structure. We need to make another function that can update the zip in the structure for us.
Whenever you write a function, try to keep it limited to using only one data type at a time. In our case, we only use the student structure in this function, and we will make another
update-zipfunction to handle the address structure
(define (update-zip-for-student s new-zip)
(make-stdnt (stdnt-name s)
(stdnt-grad-yr s)
(update-zip (stdnt-house s) new-zip)))Now, its time to make the update-zip function. Ill go quick with this one, assuming you have gotten faster with them aswell.
; update-zip : Address Nat -> Address
; Update the zip code for this address to the given #Bam, theres our signature and description
(check-expect
(update-zip ADDRESS1 02020)
(make-address 50 "Rice St" "Wellesley" "MA" 02020))
(check-expect
(update-zip ADDRESS2 13579)
(make-address 1 "a" "b" "c" 13579))Whamo, we have some check expects
And then we can, very simply, just create the update-zip function
(define (update-zip a new-zip)
(make-address
(address-house a)
(address-st a)
(address-city a)
(address-state a)
new-zip))It may look like a lot of code, but if you break it down, all it does is create a new address, give it the house, st, city, and state of the old address, and just replace the zip with the new zip
Now that we have learned to use structures, we can put them to good use. We can use them in our text editor. Remember when we had our text editor, it could type and delete, but you could not move the cursor around. That was because our world state was a single string: The text that was in the editor. We had no way of storing the cursor position. Well, using these new hot structures that we have learned about, that is all about to change.
So. first thing you do with any data type, function, or struct is a simple, one line comment describing it.
In our case, we will make a structure called TextEditor or te for short with the text and cursor position
as members. We can write this out in a comment like so:
; A TextEditor is a (make-te String Nat)Now that we know about the text editor, we need to tell scheme about it. (remember, anything after a ; is
invisible to scheme and is only for us to read).
We can define the struct as such:
(define-struct te [text cursor])And now we can describe the types in the text editor further
; and represents a text editor
; - where text is the text you have typed
; - and cursor is the index of the cursorAll together they will look as such:
; A TextEditor is a (make-te String Nat)
(define-struct te [text cursor])
; and represents a text editor
; - where text is the text you have typed
; - and cursor is the index of the cursorNow that we have the struct created and layed out. We need to make 2 samples:
(define TE1 (make-te "hello" 1))
(define TE2 (make-te "ECS" 0))Although we don't have time to implement it into our text editor but we can make a simple
function that we may be able to use as the on key handler for our big-bang program. Since it
will handle key events, it take in our world state, in this case the TextEditor structure and the key event.
; insert-text : TextEditor KeyEvent -> TextEditor
; Insert text the user typed at the cursor's locationAn example check expect could exist as such:
(check-expect (insert-text TE1 "a")
(make-te "haello" 2))- Structures are a way to store more than one data piece in the same place
- Structures can be created like so:
(make-struct my-struct-name [field1-name field2-name ...])- When using structures, you can use the generated function
<name-of-structure>-<name-of-field>where<name-of-structure>is replaced with the name of your structure. (ex:address) and<name-of-field>is replaced with the name of the field that you want to read. (ex:st). So to access an address's st(reet), we can use the helper function(address-st a) - When using structures in a function, only access one data type at a time, make different functions for deeply nested data, such as the address inside of the student see: Changing the zip code
- ALL DATA IN SCHEME IS IMMUTABLE (unable to be mutated (changed))
- To be able to modify a structure, you have to create a whole new one with the new data see: Holding a student back
- Scheme is very lax and does not enforce the types you want in your structures, you have to be weary of that and enforce it yourself
Jump to TL;DR (summary)
Jump to Table Of Contents
Below is the code we have written for the text editor last week:
; A TextEditor is a (make-te String Nat)
(define-struct te [text cursor])
; and represents a text editor
; - where text is the text you have typed
; - and cursor is the index of the cursor
(define TE-EMPTY (make-te "" 0))
(define TE1 (make-te "hello" 1))
(define TE2 (make-te "ECS" 0))
; insert-text : TextEditor KeyEvent -> TextEditor
; Insert text the user typed at the cursor's location
(check-expect (insert-text TE1 "a")l
(make-te "haello" 2))
(check-expect (insert-text TE2 "right")
(make-te "ECS" 1))We had created a simple structure for the text editor which can hold both the text and the cursor position.
We have accidentally skipped a step between the TextEditor structure and the
insert-text function. We need to make a template.
We are now going to design the template.
See ECS Help Sheet's Designing Templates section.
(define (te-template te)
(... (te-text te)
(te-cursor te)
...))Since both of these are primitives or things that we have not defined ourselves,
we do not have to call or make any more templates, we can just use them directly.
See: ECS Help Sheet's
Designing Programssection for more information on designing a program
Lets make some constants. We know that the background will stay the same, so lets make that
(define BACKGROUND (rectangle 600 200 "solid" "light blue"))We also know that the font color, font size, and an image for the cursor will stay the same:
(define FONT-COLOR "black")
(define FONT-SIZE 20)
(define CURSOR-IMAGE (rectangle 2 50 "solid" "black"))Remember, we can always come back and define more constants, these are just the ones we can think of right now. And remember, putting things in constants will help a lot since you only have to change them in one spot, and not all over your program if you want to change their value
Now that we have some constants, we can move to step 2. We need to figure out what
clauses we need.
We will probably need to-draw so that we can draw the world, we want on-mouse so that we can
click and move the cursor around, and lastly we want on-key so we can capture the user's typing
and display it.
Finally, we are here!!1! We can design our main function. Lets call this microsoft-word
(this might violate tons of copyright, but we are too cool for copyright law). We also need to figure out what goes
in and what comes out. With most all main functions, they will take in the WorldState and return a WorldState.
And now, we can put it all together with a nice description as well
; microsoft-word : TextEditor -> TextEditor
; Starts up a text editor where you can move the cursor
(define (microsoft-word initial-editor)
(big-bang initial-editor
[to-draw draw-text-editor]
[on-mouse curse-of-the-cursor] ; Remember, these can be named whatever we want, as long as we know what they mean
[on-key insert-text]))Now that we have the main function and a wishlist of all the functions we want, we can make their function signatures so we know what we want later when we design them.
Lets define our draw-text-editor signature. Since it is the to-draw handler, it takes in the WorldState and
outputs the drawn Image. We can put it in a nice old comment with a description
; draw-text-editor : TextEditor -> Image
; Draws the text with the cursor at a certain positionNow that we have draw-text-editor, we can define the curse-of-the-cursor. This function will be in the clause on-mouse.
Because of that, it gives us some special things. As always, it will give us the WorldState and it will also give us the x
and y coordinate of the mouse and a MouseEvent defining what the mouse did, and it returns a new modified (or not) WorldState.
We can plop that into a handy comment for us.
; curse-of-the-cursor : TextEditor Number Number MouseEvent -> TextEditor
; Change the position of the cursor when you clickAnd we had already created the insert-text function last week:
; insert-text : TextEditor KeyEvent -> TextEditor
; Insert text the user typed at the cursor's locationNow that we have all of the signatures in our wish list, we can start writing the functions.
We can start with the draw-text-editor function. As always, we need to start with some check expects.
(check-expect
(draw-text-editor TE-EMPTY)
(overlay (beside CURSOR_IMAGE (text " " FONT-SIZE FONT-COLOR)) ; This will create the blank image with just a cursor
BACKGROUND))
(check-expect
(draw-text-editor TE1)
(overlay
(beside (text "h" FONT-SIZE FONT-COLOR)
CURSOR_IMAGE
(text "ello" FONT-SIZE FONT-COLOR)) ; Here we put the cursor between the `h` and `ello` since it is a cursor pos 1
BACKGROUND))Now we can go and define the draw-text-editor function body.
So, we want to have 2 states, either there is no text in the editor, or there is some text.
we can check for such using a cond.
(define (draw-text-editor editor)
(cond [...]
[...]))Now we need to somehow get the text out of the editor structure. We can do so by using our template. Lets paste it down here so we can use it.
(define (te-template te)
(... (te-text te)
(te-cursor te)
...))To access the text, we can use the te-text helper function from our template.
So we can paste it into the first cond. We need to check it to make sure that its length is > 0, meaning
it is not empty
(define (draw-text-editor editor)
(cond [(> (string-length (te-text editor)) 0)] ; new
[...]))Now we can define a simple template of what we will do. Remember, we want to write some text, the cursor, and then the rest of the text
(define (draw-text-editor editor)
(cond [(> (string-length (te-text editor)) 0)
(overlay (beside (text ... FONT-SIZE FONT-COLOR) ; new
CURSOR-IMAGE ; new
(text ... FONT-SIZE FONT-COLOR)) ; new
BACKGROUND)] ; new
[...]))Now, we need to figure out how to draw the text in front of the cursor. We can get a slice of
a string by using the substring function, and use the cursor position to chop it. We want to get the
substring of the te-text from 0 up until te-cursor
(define (draw-text-editor editor)
(cond [(> (string-length (te-text editor)) 0)
(overlay (beside (text (substring (te-text editor) 0 ; new
(te-cursor)) ; new
FONT-SIZE FONT-COLOR)
CURSOR-IMAGE
(text ...))
BACKGROUND)]
[...]))And now that we have the first text, we can do the second text very much the same, except this time, we
don't need to give substring an ending point, because in doing so, substring will just go until the end.
(define (draw-text-editor editor)
(cond [(> (string-length (te-text editor)) 0)
(overlay (beside (text (substring (te-text editor) 0
(te-cursor))
FONT-SIZE FONT-COLOR)
CURSOR-IMAGE
(text (substring (te-text editor) ; new
(te-cursor)) ; new
FONT-SIZE FONT-COLOR))
BACKGROUND)]
[...]))Now that we have the text having state, we can work on the section of the function when there is no text to draw. Since we will draw the same thing every time you have no text, we can extract it into a constant. We can copy it from our first check expect
(define BLANK-EDITOR-IMAGE
(overlay (beside CURSOR_IMAGE (text " " FONT-SIZE FONT-COLOR)) ; This will create the blank image with just a cursor
BACKGROUND))and then update our check expect from
(check-expect
(draw-text-editor TE-EMPTY)
(overlay (beside CURSOR_IMAGE (text " " FONT-SIZE FONT-COLOR)) ; This will create the blank image with just a cursor
BACKGROUND))to
(check-expect
(draw-text-editor TE-EMPTY)
BLANK-EDITOR-IMAGE) ; changedand we can add that into our new function
(define (draw-text-editor editor)
(cond [(> (string-length (te-text editor)) 0)
(overlay (beside (text (substring (te-text editor) 0
(te-cursor))
FONT-SIZE FONT-COLOR)
CURSOR-IMAGE
(text (substring (te-text editor)
(te-cursor))
FONT-SIZE FONT-COLOR))
BACKGROUND)]
[else BLANK-EDITOR-IMAGE])) ; new- USE YOUR ECS Help Sheet. It will walk you through it all.
- Make constants! they will help you keep duplicated code to a minimum, and will save you when you need to change them.
- Complex programs can be broken down into simpler parts and are a lot easier when you do so
- WRITE COMMENTS. Since we were unable to finish the text editor today, we will thank ourselves later when we have to come back to it, that we have left comments telling us about what we still need to do. (Your memory can only serve you so well)
Jump to TL;DR (summary)
Jump to Table Of Contents
Starting code for this lesson on wescheme
We left off writing a game where the user can make balloons which will fly upwards. Our game worked and was great, but there is a slight problem, we can only have 2 balloons at a time, and that sucks. We want all the balloons!!!
Currently our Balloon game type is as follows:
; A BalloonGame is one of:
; - false (no balloons)
; - Posn (balloon)
; - (make-twothings Posn Posn)
; and represents either a screen with no balloons, a screen with a balloon,
; or a screen with two balloonsAs we can see, there are the 3 variants, no balloons, one balloon and 2 balloons. If we wanted 3 balloons what could we do? One option would be to make a 4th variant and make it something like:
; - (make-threethings Posn Posn Posn)But that method has a problem. First off, we need to make another whole data type threethings
and making data types is so not lit. Another problem with this method is every single time
we want to add another balloon, we have to make another variant, and a whole new data type. UGH.
What if I told you that you lived in a simulation that there is a way to make a data definition that
can hole infinite amounts of data.
You saw this coming if you read the title, but what you might not have known is what in the gosh darn is this fandangled recursion thing? Well, I can hit you with what my friend Merriam Webster says:
recursion (noun)
re·cur·sion | ri-ˈkər-zhən
a computer programming technique involving the use of a procedure,
subroutine, function, or algorithm that calls itself one or more
times until a specified condition is met at which time the rest
of each repetition is processed from the last one called to the
first
Ok webster, that's cool and all, but like HUH? what do all those words mean. Procedures? Subroutines?
It looks like Mr. Webster is a bit too verbose for us, let be break it down.
Recursion is when some thing does itself multiple times. In terms of scheme and our programming knowledge, there are 2 places where we can use recursion. Functions and structures.
A data structure is recursive when one of the parts of it is the data structure itself. A way to visualize it is to think of russian nesting dolls (also called Matryoshka):
Click To Expand Images
Each doll has its outer shell with the paint and the nice artwork, but if you look inside of them, they have a whole new doll inside.
This outer doll can be thought of as the structure and the paint could be a property of it, much like the
positions in our twothings structure and the doll on the inside would be a whole new two things struct.
Lets try to change our BalloonGame into a recursive structure so that we can have infinite balloons and
it may help to see a concrete example.
Back to our BalloonGame structure:
; A BalloonGame is one of:
; - false (no balloons)
; - Posn (balloon)
; - (make-twothings Posn Posn)
; and represents either a screen with no balloons, a screen with a balloon,
; or a screen with two balloonsWe can join the single and double data structure variants into one recursive data variant.
; A BalloonGame is one of:
; - false (no balloons)
; - (make-twothings Posn BalloonGame)
; and represents either a screen with no balloons, or a screen with at least one balloonIn the above definition, we replaced the second Posn in the twothings struct with a Balloon,
but what does that entail exactly? Well, now chain our Balloon Gmes together.
We can start with the inside most BalloonGame, the false variant.
(define NO-BALLOONS false)Since the false variant of our data type has no BalloonGame inside of it, it is the end of
the recursion, the center most Matryoshka. But we can now put another doll around it:
(define ONE-BALLOON (make-twothings (make-posn 10 20) NO-BALLOONS))Now our ONE-BALLOON constant is a BalloonGame with one balloon. If we unravel it, or replace
the constants with their actual value so its a bit easier to picture, it will look as such:
(define ONE-BALLOON (make-twothings (make-posn 10 20) false))The false at the end signals that that is the end of our recursion. Now if we have 2 balloons, we can show that like so:
(define TWO-BALLOONS (make-twothings (make-posn 250 93) ONE-BALLOON))or unwrapped:
(define TWO-BALLOONS (make-twothings (make-posn 250 93) (make-twothings (make-posn 10 20) false)))Once again, we have that false at the end to signal that our recursion is done.
Recursion is a lot to wrap your head around, so this could take multiple reads through
(and definitely should), but here are a few more examples of the BalloonGame data structure
for you to gander at
(define NO-BALLOONS false)
(define ONE-BALLOON (make-twothings (make-posn 10 20) NO-BALLOONS))
(define TWO-BALLOONS (make-twothings (make-posn 250 93) ONE-BALLOON))
(define THREE-BALLOONS (make-twothings (make-posn 200 200) TWO-BALLOONS))
(define FOUR-BALLOONS (make-twothings (make-posn 350 26) THREE-BALLOONS))And them "unraveled"
(define NO-BALLOONS false)
(define ONE-BALLOON (make-twothings (make-posn 10 20)
false))
(define TWO-BALLOONS (make-twothings (make-posn 250 93)
(make-twothings (make-posn 10 20)
false)))
(define THREE-BALLOONS (make-twothings (make-posn 200 200)
(make-twothings (make-posn 250 93)
(make-twothings (make-posn 10 20)
false))))
(define FOUR-BALLOONS (make-twothings (make-posn 350 26)
(make-twothings (make-posn 200 200)
(make-twothings (make-posn 250 93)
(make-twothings (make-posn 10 20)
false)))))In the "unraveled" version — which by the way you should almost never type out by hand, always use the method shown above it, where you have each nested one get defined before it — it becomes a bit clearer to see the "nesting" of the structure inside of itself. It is worthy to note that all of them end in false. If there not a second, non recursive variant of our data type, we would never to be able to stop recursing, but since we have that second false variant, we are allowed to stop our data type with the false variant.
Since we have now updated the data definition and its samples (the NO-BALLOONS - FOUR-BALLOONS above) we can move to the final step of the data defining process, which is to make our template. In our case, we just need to update our template.
Currently we have this:
; BalloonGame -> ???
(define (balloon-game-template game)
(cond [(boolean? game) ...]
[(posn? game) (posn-template game)]
[(twothings? game)
(... (posn-template (twothings-thing1 game))
(posn-template (twothings-thing2 game)))]))And that template worked for our 3 variants, the no balloons (false), the one Posn, or the 2 Posns.
Since we no longer have 3 variants we have to change the template. We can begin by removing the one
posn template, since although we do use only 1 posn, we still use the twothings struct.
; BalloonGame -> ???
(define (balloon-game-template game)
(cond [(boolean? game) ...]
- [(posn? game) (posn-template game)]
[(twothings? game)
(... (posn-template (twothings-thing1 game))
(posn-template (twothings-thing2 game)))]))Now its all fine and dandy? Right? Well not yet... We also changed the data that is stored in the two things structure. Since we changed our definition, we also need to change the code that uses it, or the implementation.
In our new data definition for the two things variant, we changed from 2 Posns to a
Posn and another BalloonGame. In our above template, we call the posn-template on the
thing1 and the thing2 from twothings since they both used to be posns, Now the second
one is another BalloonGame so we have to call this same baloon-game-template on that
baloon game
; BalloonGame -> ???
(define (balloon-game-template game)
(cond [(boolean? game) ...]
[(twothings? game)
(... (posn-template (twothings-thing1 game))
- (posn-template (twothings-thing2 game)))]))
+ (balloon-game-template (twothings-thing2 game)))]))As you can see, we now have our template calling that same template. This is very similar to our recursive data structure in a lot of ways, I wonder what it would be called?
Recursive functions are very much the same as recursive data definitions. But instead of containing themselves, as recursive structures do, they call (or run) themselves.
We can see that in practice in our new and updated balloon-game-template:
; BalloonGame -> ???
(define (balloon-game-template game)
(cond [(boolean? game) ...]
[(twothings? game)
(... (posn-template (twothings-thing1 game))
(balloon-game-template (twothings-thing2 game)))]))Since the function calls itself, it needs a path to take that could not call itself or else it would be stuck calling itself which would call itself which would....
Just like how a recursive structure needs a second variant a recursive function needs a cond or if with one or more of the paths not calling itself.
This escape can be seen in our template with the boolean? cond case which will run when we get to the end of our "nested dolls".
# TODO: FUNCTION HANDLING THEM # TODO: REST
- Final Product
- Recursion is the method of nesting something inside of another of that same thing
- We can have recursive data structures (A structure that contains itself) (think of a russian nesting doll)
- We can have recursive functions (A function that calls itself)
- With all recursive things, you MUST have an 'escape'
- Recursive data structures must have a variant to signal that the recursion is finished (our false case above)
- Recursive functions must have a way to not call themselves again, so they must contain a cond/if with at least one branch not calling themselves
- If you do not have this escape from recursion
- Your data structure would be infinitely large since it would forever contain 1 more of itself which would contain 1 more of itself which ....
- You function would never be done running since it would forever call itself which would call itself which would call itself which would ....
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment