Students discover the need for compound date - data structures - using 2-dimentionsal
animation. They learn the syntax for data blocks, constructors and dot-accessors, and
practice each by creating a "digital bakery".
Students identify real-world behaviors that require data structures
Students make use of a complex data structure: Cake
Students define variables bound to Cakes
Students will generalize their understanding of function constructors and accessors
Students write code that extracts each field from those Cakes
Students will write functions that access fields of a CakeType
Standards and Evidence Statements:
Standards with prefix BS are specific to Bootstrap; others are from the Common Core. Mouse over each standard to see its corresponding evidence statements. Our Standards Document shows which units cover each standard.
BS-DR.1: The student is able to translate a word problem into a Contract and Purpose Statement
given a word problem, identify the domain and range of a function
given a word problem, write a Purpose Statement (i.e. - rewrite the problem in their own words)
BS-DR.2: The student can derive test cases for a given contract and purpose statement
given a Contract and a Purpose Statement, write multiple examples or test cases
given multiple examples, identify patterns in order to label and name the variables
BS-DR.3: Given multiple test cases, the student can define a function
given examples and labeled variable(s), define the function
BS-DR.4: The student can solve word problems that involve data structures
write examples for a function that prodiuces a data structure
write functions that produce data structures
BS-DS.1: The student is able to read data blocks
given a data block, create instances of the data structure
given a data block, use dot-accessors to access fields of the data structure
BS-DS.2: The student is able to solve problems using data structures
identify problems that require use of a data structure
BS-IDE: The student is familiar with using a REPL, entering expressions properly, and interpreting error messages
enter and evaluate expressions on the computer
BS-M: The student models a problem in context and determines the data needed to describe the problem
identifying which quantities are fixed and which are variable
identifying the datatype of a given quantity, in context
BS-PL.1: The student is familiar with declaring values and applying built-in functions using the programming language
representing (numeric, string, boolean, image, etc) values in the programming language
BS-PL.3: The student is able to use the syntax of the programming language to define values and functions
defining and using functions
Length: 120 Minutes
Glossary:
calling: Using a function by giving it inputs
constructor: A function that creates instances of a data structure
contract: a statement of the name, domain, and range of a function
data structure: A datatype which packages several datatypes as fields
domain: the type of data that a function expects
dot-accessors: A way to extract the values of fields an instance
field: A part of a data structure that has a name and holds a single value of a specified datatype
instance: A specific, packaged value of a data structure that contains other values in its fields
name: how we refer to a function or value defined in a language (examples: +, *, star, circle)
purpose statement: a brief description of what a function does
range: the type of data that a function produces
variable: something that changes
Materials:
Pens/pencils for students, fresh whiteboard markers for teachers
Class poster (List of rules, language table, course calendar)
Language Table (see below)
Student Workbook folders with names on covers, and something to write with
Preparation:
Write Agenda on board
Display class posters, Language Table, Design Recipe
Students will deepen their understanding of function definitions and the Design Recipe
Evidence Statementes
Product Outcomes
Materials
Pens/pencils for students, fresh whiteboard markers for teachers
Class poster (List of rules, language table, course calendar)
Language Table (see below)
Student Workbook folders with names on covers, and something to write with
Preparation
Write Agenda on board
Display class posters, Language Table, Design Recipe
Review(Time 15 minutes)
ReviewIn the previous unit, you reviewed almost everything from Bootstrap:Algebra including Datatypes, Contracts, and the Design Recipe.
In this unit you will go above and beyond all that, and learn an entirely new construct that will be the basis for everything you’ll do in Bootstrap:Reactive.
Ask a few introductory review questions to test students’ understanding:
What are the three parts of a Contract?
What is the Pyret code to draw a solid, green triangle of size 22?
Why is it important to write at least 2 examples before defining a function?
To make sure the material from the previous unit is fresh in your mind, tackle the following activity:
Turn to Page 8 in your workbook. Write a function called double-radius,
which takes in a radius and a color. It produces an outlined circle of whatever color was passed in, with radius
twice as big as the input.
If walking through this example as a class, use a projector so kids can see the function being written on the computer.
Remember how to use the design recipe to work through word problems?
Step 1: Contract and Purpose Statement
What is the Name of this function? How do you know?
How many inputs does it have in its Domain?
What kind of data is the Domain?
What is the Range of this function?
What does this function do? Write a Purpose Statement describing what the function does in plain English.
Review the purpose of Contracts: once we know the Name, Domain, and Range of a function, it’s easy to write examples using those datatypes.
Step 2: Examples
Using only the Contract and Purpose Statement, see if you can answer the following questions:
Every example begins with the name of the function. Where could you find the name of the function?
Every example has to include sample inputs. Where could you find out how many inputs this function needs,
and what type(s) they are?
Every example has to include an expression for what the function should do when given an input. Where
could you look to find out what this function does?
Write two examples on your paper, then circle and label what is changing between them. When labeling,
think about what the changing things represent.
Don’t forget to include the lines examples: and end! Your examples should look similar to:
Each one of these answers can be found in the Contract or Purpose Statement. Suggestion: Write these steps on the board, and draw
arrows between them to highlight the process. The goal here is to get students into the habit of asking themselves these questions
each time they write examples, and then using their own work from the previous step to find the answers.
Step 3: Definition
Once you know what is changing between our two examples, you can define the function easily. The things that were circled and labeled in
the examples will be replaced with variables in the function definition.
Underneath your examples, copy everything that doesn’t change, and replace the changing things with the variable
names you used. (Don’t forget to add the fun and end keywords, as well as the single colon (:) after the function header!)
For more practice, turn to Page 9 in your workbook and complete the Design Recipe for the double-width function.
Check students understanding: Why do we use variables in place of specific values? Why is it important to have descriptive variable
names, as opposed to n or x?
Remind students about nested functions: A function whose range is a number can be used inside of a function requiring a number in its domain, as in
circle(2 * 25, "outline", "red").
Introducing Structures
Overview
Learning Objectives
Students will understand the limitations of atomic datatypes
Evidence Statementes
Product Outcomes
Students identify real-world behaviors that require data structures
Open the Package Delivery file on your computer and press ’Run’. What happens?
The drone tries to deliver a package directly to a house, but the box falls straight down, outside of the delivery zone. We want the package to fall diagonally, and land right in front of the house. Let’s take a look at the code to see why it falls into the road instead. There are a few new concepts in this file, but first, let’s focus on what you already know.
Look at the function defined here called next-position.
What is this function’s Domain? Its Range?
What does next-position do with its inputs?
This function takes in two numbers, representing the x- and y-coordinate of the box, but it only produces a new y-coordinate (after subtracting 5). If only the y-coordinate is changing, the box will always fall straight down. To reach the house, it will have to fall diagonally.
How should the box’s x-coordinate change if it moves diagonally to the right (toward the house)? How should its y-coordinate change?
Functions can return only one thing at a time, but we want to return a new x- and a y-coordinate in order to make the box fall diagonally. Thankfully, we have a way to combine multiple things within one container, called a Data Structure. For this project, we’ve created a structure for you to use called DeliveryState, which contains two Numbers. These represent an x and a y-coordinate.
Look at line 5, where we’ve defined DeliveryState. We’ll go through the new syntax for defining a data structure, because very soon you’ll be defining brand new structures of your own!
On the first line, we’ve written a comment that describes the stucture. We’re calling it DeliveryState, and it contains Numbers for the x- and y-coordinate.
You’re already familiar with built-in data types like Number, String, Image and Boolean. On the next line, the data keyword allows us to create brand new data types of our own! Here, we are making a data type called DeliveryState. We choose this name, because it represents the current state - or position - of the package being delivered. Pyret lets us write any name after data, but it’s good habit to choose a meaningful name and capitalize it.
The next line begins with the | symbol, sometimes called a "bar" or "pipe", followed by the name of the constructor function for this structure: delivery. This is similar to what you’ve seen before: to create an Image, we call the function that creates it: rectangle, triangle, square, etc. To create a DeliveryState, we can use the deliveryconstructor function with its inputs (x and y).
This data block tells us that we’re defining a new data type called DeliveryState, whose constructor function delivery takes in two Numbers: x and y. Once we’ve listed each input and its data type, we finish defining the structure with the end keyword, just like finishing an example block.
In the interactions area, practice making some DeliveryStates using the delivery() constructor function. Try making a DeliveryState that represents the box’s position if it’s on the road, another when it’s in the air, above the house, and one when it’s right in front of the house- a successful delivery!
Students will soon be writing creating new data structures. Cover this new syntax carefully, paying special attention to capitalization (the name of the structure is capitalized (DeliveryState), whereas its constructor function (delivery) is lowercase), double colons (::) before data types, and commas between inputs to the constructor function.
Now it’s up to us to get this box delivered sucessfully, and make sure it lands at the house.
Turn to Page 10 in your workbook, read the word problem, and fill in the Contract and Purpose Statement for the function next-position.
Point out that we’re now using a new data type in a contract: next-position consumes two Numbers, and produces a DeliveryState. Once we’ve defined a new data structure using the above data block, we can use it just like other datatypes.
Now for our two examples. Using, or callingnext-position with two numbers is easy, but what happens to those numbers? We can’t return both at the same time...unless we use a data structure! To do so we’ll need to use the constructor function to make a structure from the data we already have.
According to the definition for DeliveryState, what function makes a DeliveryState? What is its contract?
# delivery :: Number, Number -> DeliveryState
What two things are part of a DeliveryState? Do we have values for those things as part of our first example?
We don’t want our DeliveryState to contain the same x and y values we gave the next-position function. How will the values change? (Remember to show your work!)
Your first example should look something like:
Once your first example is complete, write one more example with different inputs for the x and y coordinates.
Remind students to show every step of their work in the example step of the design recipe: if the x-coordinate increases by 5 while the y-coordinate decreases by 5, they should show the addition and subtraction within the DeliveryState data structure, instead of just returning the new numbers.
Now that you have two examples, it’s time to define the function. You know the drill: circle and label everything that changes between your two examples, copy everything that stays the same, and replace the changing things with the variables you chose.
When you finish, your function definition should look like:
Now, instead of just changing and returning one number (a y-coordinate), we can return both the x and y-coordinates of the box within a Data Structure.
Open the Package Delivery code again and replace the original next-position function with the one in your workbook to make the box land within the dlivery zone, in front of the house! Don’t forget to change the given examples to match your new function definition.
Until now, a function could only return atomic values: single Numbers, Strings, Images, or Booleans. In Bootstrap:Reactive, our functions will still return one value, but that value can be a Data Structure, (or just "structure" for short) containing any number of values. This way we can return both the x- and y-coordinate of a package using a DeliveryState. Later on, we’ll create new structures to record detail about characters in a game, like their health, position, amount of armor, or inventory.
In Bootstrap:Algebra, students’ games were made by keeping track of just a few numbers: the x-positions of the danger and target, and y-position of the player. In Bootstrap:Reactive, students’ games will be much more complex, and will require many more values to move characters, test conditions, keep track of the score, etc. Data structures simplify code by organizing multiple values: You couldn’t represent every part of a player (position, health, inventory, etc.) with one number or string, but you can refer to all these things collectively with a data structure. This way, we can have one value (a data structure) containing multiple other values that can be accessed individually.
Cakes
Overview
Learning Objectives
Evidence Statementes
Product Outcomes
Students make use of a complex data structure: Cake
Students define variables bound to Cakes
Students will generalize their understanding of function constructors and accessors
Cakes Suppose you own a famous bakery. You bake things like cookies, pastries, and tarts, but you’re especially known for your world-famous cakes.
What type of thing is a cake? Is it a number? String? Image? Boolean? You couldn’t describe all of the important things
about a cake with any one of those data types. However, we could say that we care about a couple of details about each cake, each of which can be described with the types we already know.
For each of the following aspects of a cake, think about what datatype you might use to represent it:
The flavor of the cake. That could be "Chocolate", "Strawberry", "Red Velvet", or something else.
The number of layers
Whether or not the cake is an ice cream cake.
What datatype could we use to represent the entire cake?
Now that we know everything that is part of a cake, we can use a data structure to represent the cake itself. Let’s take a look at how this works.
On this page, we will define a data structure for cakes, which we call CakeType (since this is now a new data TYPE). At the top of this page we see a comment, stating what things are part of a CakeType. Below that is a line that says data CakeType:, which begins the definition of a new data structure, called CakeType. On the next line, we define the function that makes a CakeType (cake), and how exactly to make a CakeType—the names of each thing in a CakeType, and their data types. Each piece of information that makes up a cake (the flavor, etc) is called a field. A field has both a descriptive name (like flavor) and a datatype.
What name describes the first field in a CakeType? What data type can we use to represent it?
Refer students back to their language table, to see what Types are available.
There is a little bit of new syntax involved in defining structures. On the first line on Page 11, we write flavor :: String,, which tells Pyret that the first element of any CakeType will be its flavor, represented by a String. This line shows how to define one field in a data structure.
What name describes the second field in a CakeType? What data type can we use to represent it?
On the next line, write layers :: Number,, which tells Pyret that the second element of any CakeType will be its number of layers, represented by a Number.
What data structure should we use to represent whether or not the CakeType is an ice cream cake? Use this to define another field.
On your paper, you should have:
This is the code that defines the CakeType data structure. It tells the computer what a CakeType is and what goes into it. It also defines its constructor function, called cake. To make a CakeType, you must call the constructor function with three things: a flavor, which is a String, layers, a Number, and is-iceCream, which is a Boolean. Remember that order matters! For now, these are the only things that we’re going to keep track of in a CakeType, but you can imagine how you might extend it to include other information.
Stress the importance of being able to define your own datatypes
to students: no longer are they bound by the single values of numbers, strings, or booleans! Pyret allows you to define brand new Data Structures, containing
any combination of values.
Open the Bakery file and look at lines 3 - 8. Do they match what you have on your paper?
Now take a look farther down, at line 10: birthday-cake = cake("Vanilla", 4, false)
What is the name of this variable?
What is the flavor of birthday-cake?
How many layers does birthday-cake have?
Finally, is birthday-cake an ice cream cake, or not?
Below the data definition for CakeType there are four CakeTypes defined and assigned to the variables birthday-cake, chocolate-cake, strawberry-cake, and red-velvet-cake. Ask students questions about these CakeTypes to get them thinking about how they would define their own.
On line 14, define another CakeType, which you can name however you like (but choose something descriptive, like pb-cake, lemon-cake, etc.) To start,
how would you define this variable?
What function is used to make a Cake?
Which thing comes first in a Cake structure?
Now what do you expect to happen when you type the name of your new CakeType into the interactions area? Click ’Run’ and try it out.
pb-cake = cake("Peanut Butter", 2, true)
Have students walk you through the process of defining a new value and making a CakeType with whatever flavor, etc. they like.
Define two new values for some of your favorite cakes. You can give them whatever names you prefer. You can make any kind of CakeTypes that you want, as long as your structure has the right types in the right orders!
Repetition is key in this lesson. Have students identify each part of the CakeType for every CakeType they’ve defined.
What is the flavor of their first CakeType? Its number of layers? Ensure that students are using their inputs in the right order!
At this point, you’ve worked with two different Data Structures: JumperStates and CakeTypes, and you’ve created different examples, or instances, of these structures.
Instances are concrete uses of a datatype, just as 3 is a concrete Number (where Number is the type). Here, CakeType is the type, and cake("Chocolate", 8, false) is
a concrete cake with specific values for each field. In programming, we create instances much more often than we create new data structures.
For now, the important point is to recognize the difference between a structure definition (the data.... piece of code) and
specific instances of a data structure (like birthday-cake, or jumper(44, 75).
Students often struggle with the difference between the definition of a data structure and instances (items created from) a data structure. When students define CakeType, they haven’t
created any specific cakes. They have defined a type that they can use to define specific cakes. If they have a specific cake, they can ask questions of it such as "is this a chocolate
cake?" and produce an answer. If all they have is the CakeType definition, they can’t answer such questions. Some people like the analogy of a cookie cutter here – CakeType defines
a cookie cutter, but doesn’t produce any cookies. To get a cookie, you use the cake constructor to define a specific cake with specific values for the fields.
Based on these instances of CakeTypes you just wrote:
What is the name of the function that creates a CakeType?
What is the Domain of this function?
How many things are in the domain?
The three things in the domain of cake are, in fact, the three things that we have already listed on Page 11! With data structures, the order is very important: we always want the first string in cake to be the CakeType’s flavor, the first number to be its number of layers, etc.
CakeTypes are the first example of defining a new datatype that students will see, but Pyret allows you to define any number of new data structures to hold
any combination of values. The important points to remember about creating structures at this point is that whenever the constructor function is called (in this case, cake), it must take in the same
number and type of values as in the structure’s definition, and its inputs must be in the same order as the definition.
After clicking the "Run" button, in Pyret, type
birthday-cake into the interactions area and hit enter. What do you get back?
Does this make sense? What happens when you type just a number into the interactions area? We get that same number back! What about Strings? Images?
Booleans? If we don’t do anything to our input, or use any function on it, we get back exactly what we put in! Here, you put in a CakeType, let’s see what we get back. At first glance, it looks like a function call was the answer! But there’s a few things different about what appears in the output. First, it isn’t the same color as a normal function call, which is the first hint that something’s different. Second, we can click on it, and see that this value is storing three other values in its fields – the flavor, layers, and whether or not it’s ice cream. This compound value that’s printed is an instance of a CakeType. It’s a value in its own right, so when we type in birthday-cake it shows us this value (just like with numbers and strings).
Remind students that values will always evaluate to themselves. 4 evaluates to 4, the string "pizza" evaluates to "pizza", and birthday-cake evaluates
to cake("Vanilla", 4, false)
Dot-Accessors
Overview
Learning Objectives
Evidence Statementes
Product Outcomes
Students write code that extracts each field from those Cakes
Materials
Preparation
Dot-Accessors(Time 10 minutes)
Dot-AccessorsSuppose you want to get the flavor out of chocolate-cake. You don’t care about the message, color, or anything else - you just want to
know the flavor. Pyret has syntax for doing precisely that: .flavor.
If you type chocolate-cake.flavor into the interactions area, what should it evaluate to? Try it out!
What kind of thing did it return: A Number, String, Image, Boolean, or structure?
Practice taking the flavor out of every CakeType you have defined, using .flavor
Of course, there are ways to access any part of a CakeType, not just the flavor! What do you think you would get if you typed chocolate-cake.layers in the interactions area?
Try using the dot-accessors .layers and .is-iceCream on your CakeTypes! Do they do what you expect?
A way to prompt students to use these accessors is to ask: "How do you get the flavor out of a CakeType?" or "How do you get the layers out of a CakeType?"
Throughout the course you can set up a call and response system with students, where the question "How do you get the X out of a Y?" will prompt the name of the accessor.
The previous syntax is known as Dot-Accessors. They allow you to specify exactly what part of a structure you want. If we want to know if we can fit a certain CakeType through a doorway, we probably care only whether the number of layers is less than a certain amount. Likewise, if we want to know whether or not a character in our game has lost, we need to know only if her health is less than 0:
we might not care what her location is, or the color of her armor. Programmers use accessors a lot, because they often need to know only one piece of information from a complex data structure.
Our CakeType structure is defined using data CakeType: and the cake(...) lines, which tell the computer what things make up that structure, and what order and type each
thing is. In return, we get new functions to use. Until we write these lines, we don’t have
cake(...) (to make a Cake), .flavor (to get the flavor out of the Cake), .layers, or any other dot-accessors, because Pyret doesn’t know what a CakeType is- we haven’t defined it.
To see this for yourself, type a pound sign (#) before the line which begins with cake(...) and each of the fields. This comments out the definition, so that the computer ignores it. Hit run, and see what happens.
When the cake(...) lines are commented out, Pyret returns some errors, saying you’re trying to use cake before its definition. It doesn’t know what cake is or does, because we defined a CakeType structure with no constructor. Make sure students understand that the line beginning with
data and a line similar to cake(...) are needed in order to create and work with any structure.
Your Bakery
Overview
Learning Objectives
Students will write complex functions that consume, modify and produce structures
Evidence Statementes
Product Outcomes
Students will write functions that access fields of a CakeType
Materials
Preparation
Your Bakery(Time 30 minutes)
Your BakeryOf course, when programmers work with data structures, they don’t just define them and create instances. They also write functions that use and produce structures. Let’s get started writing some functions for CakeTypes.
Turn to Page 12 in your workbook. Write the contract and purpose statement for a function called taller-than, which consumes two CakeTypes, and produces true if the first CakeType is taller than the second.
What is the domain for this function?
What is the range of taller-than?
Which part(s) of the CakeTypes will you need to check to determine if one is taller than the other?
For your first example, try comparing birthday-cake and chocolate-cake. Do we care about what flavor either of these CakeTypes are? What about whether or not one of them is an ice cream cake? All we need to figure out which one is taller is their number of layers.
How do you get the number of layers out of birthday-cake? What about chocolate-cake? Write your first example to figure out if birthday-cake has a greater number of layers than chocolate-cake.
Write one more example for the function taller-than, this time using it to compare any two CakeTypes you defined earlier.
Next, circle and label what changes between the two examples. How many variables will this function need? Then write the definition, using your examples to help you.
After replacing the changing things with variables, your definition should look similar to:
Turn to Page 13 in your workbook. Your bakery needs to know if certain CakeTypes needs to be refrigerated. If the temperature is greater than 32 degrees AND the given CakeType is an ice cream cake, the function should return true.
Fill out the Contract and Purpose Statement for the function.
Write two examples for how one would use will-melt.
Circle and label what varies between those examples and label it with a variable name.
Define the function.
Give students plenty of time to practice using dot-accessors, extracting pieces of the Cake structures and writing expressions that compute with them.
Optional: In the Bakery file, extend the CakeType data structure to include one more field: a message, represented as a String. (Make sure you remember to change each CakeType instance below the data definition: if a CakeType now contains four fields, each instance will need to include all four fields!) Next, write a function called birthday-cake, which takes in a string representing someone’s name, and produces a 2-layer, chocolate CakeType with "Happy birthday [Name]!" as the message. Hint: You’ll want to use the string-append function to combine two strings into one. Here is its contract: # string-append :: String, String -> String
Since this function returns a CakeType, remind students that they’ll need to use the cake constructor function to produce a CakeType.
Closing
Overview
Learning Objectives
Evidence Statementes
Product Outcomes
Materials
Preparation
Closing(Time 5 minutes)
ClosingData Structures are a powerful tool for representing complex data in a computer program. Simple videogames, like Pong, might need to
keep track of only a few numbers at once, such as the position of the ball, position of each paddle, and the score. But if a game has many
different enemies, each with its own position and health, or multiple levels with their own background images, the game can get
very complicated very fast, and structures are a great way to manage and make sense of all the data. Programmers can do a LOT with data
structures, and in the upcoming lessons you’ll start creating your own structures to make a customized animation.
Have students volunteer what they learned in this lesson! For extra practice with the vocabulary involved with data structures, have students complete Page 14 in their workbooks.
Now that we know everything that is part of a cake, we can use a data structure to represent the cake itself. Let’s take a look at how this works.
