Last week, we saw very small functions that operate on atomic data (booleans, numbers) as well as structured data (using the struct keyword). This week, we continue with structured data, and dive into lists.
The use of data structures is essential; mastering this material is essential.
① Read section 3 of HtDP 2e.
② Exercises like numbers 96–100 and 104–106 are particularly important. You should be able to answer questions like these with 100% confidence.
③ Read and practice up to section 4.2. We will be working exercises like 113 and onward in class.
Metadata
We begin work on this Tuesday, September 13th. At the minimum, I'd like to see code submitted to Sakai by Thursday, September 15th that includes everything up through "Create-O-Problem."
I might include problems like #1-5 of the "Processing Lists" problems on the take-home exam. By "might" I mean "if I do, they will be very similar and/or no more complex." However, I would like the list-processing questions to be done by Tuesday, Sept 20 at the latest.
I will provide feedback on this work by Tuesday, Sept 22nd.
FILE NAMING CONVENTION
If you would please name your file:
username-lab2.rkt
Replace username with your own username, and make sure the file ends with the extension .rkt.
Begin (10m)
We'll begin with a quiz focusing on structured data.
Evaluate (10m)
We will trade quizzes, grade them, and discuss points where you did not understand or successfully answer the question.
Note to Future Self: This process has been taking longer; roughly 15 minutes for the quiz, and 30+ for discussion. This seems to be a good learning process, though, and the students have said they think the format works for them.
Definitions (15m)
Write structure definitions for the following items. Also, write the name of each function that is produced by the definition as well as a contract for that function. (By writing the contract for, say, make-card, you are deciding what type of data the structure should hold.)
1. A card has two fields, suit and rank.
2. A student is known by a name and a snark-rank.
3. A domo has no fields.
4. A function has a name, parameters, and body. You may abbreviate parameters as params and function as fun.
5. The empty-node has no fields.
You should be able to do this without referencing online documentation. We will use structures extensively in the implementation of interpreters; it must be second nature to define, make, and interact with record-based structures in Scheme.
I assume you have practiced further while preparing for class; if you need more practice, see me.
Discuss (30m)
Questions you may want to consider:
1. Why do we need structures when we have things like lists?
2. Propose structure definitions that could represent:
• A function definition in Scheme; for example,
(define (square x) (* x x))
• A function application in Scheme; for example,
(square 42)
• An if statement.
Find a partner to discuss your definitions with; argue to consensus what you think is the clearest set of structure definitions you might use in an interpreter. Present this to your instructor or TA before proceeding.
Note to Future Self: This discussion pushed students ahead; not everyone saw the connection of "code as data" right away. That said, it is where we going—so this became a brief mini-lecture on code-as-data. Not sure if that was good or not.
Lab Book (10m)
Take time to write in your lab notebook those topics and/or questions that challenged you particularly. Make notes that you feel will help you better understand the material later, or, for that matter, follow up on it later for further study.
At this point, your thoughts should specifically be turning to the role that structures might play in representing parts of a language.
Structure Practice (30m)
Before we tackle lists, we'll get used to simply building and and manipulating structured data. Remember to follow the design recipe.
- Provide a datatype definition for a structure called a pit, representing points in time since midnight. A point in time consists of three numbers: hours, minutes, and seconds.
Now develop the function time-diff. It consumes two pits, t1 and t2, and returns the number of seconds from t1 to t2.
For example:(time-diff (make-pit 1 2 3) (make-pit 4 5 6))
should yield 10983. - Provide a structure definition and a data definition for a game-score. A game-score is characterized by two pieces of information: a symbol representing the name of the team and a number representing the points-scored by that team.
- Develop a function that consumes two game-scores from a particular game and returns the name of the team that won or
'tieif the scores were equal. - Develop a datatype definition for a position in two-dimensional space called a posn. A posn should have an x and a y coordinate.
- Provide a datatype definition for shapes. There are three kinds of shapes:
• A circle has a center (center isa posn?) and a radius (radius isa number?)
• A square has an upper-left corner (corner isa posn?) and a length (length isa number?)
• A rectangle has an upper-left corner (corner isa posn?), width (width isa number?), and height (height isa number?)
In each case, remember to provide a clear comment regarding the structure along with its definition.Develop the function area that consumes a shape and computes its area. - Develop the function in-shape? that consumes a shape and a posn, and returns true if that posn is within the shape, false otherwise.
Additional Practice (Optional)
If you need additional practice with structures, work problems 1–6 from this page under the section "user-defined datatypes."
Lab Book and Chat (20-30m)
Take time to write in your lab notebook those topics and/or questions that challenged you particularly.
Specifically, recap what you know about structures in Scheme. How are they similar to classes or other mechanisms you know for organizing data in other languages? What do you see as their strengths, weaknesses? (The last question is, of course, entirely contextual: for what tasks are they useful/well-suited, and how could using them "out of context" make them a poor choice for data abstraction?)
Make a point to discuss this entry with a colleague. Challenge each-other to think beyond the knee-jerk response of "WOW! Scheme is the PERFECT PROGRAMMING LANGUAGE!", but instead start thinking critically about the features of a language and how they might be used.
Create-O-Problem (30m)
Along with a partner, create a problem that requires the programmer to do the following:
1. Define a structure.
2. Write a function that checks one or more values within that structure.
3. Write a function that consumes a structure, makes a decision based on its contents, and (potentially) creates a new structure with a new value in one or more of the fields. (For example, imagine an "absolute value" function that consumed posn structures: it would have to return a new posn that had only positive values.)
It is assumed that the person solving your problem will follow the design recipe.
Reply to the Piazza note Create-O-Question (Sept 13) and post your question there.
