Students discover the need for data structures and they practice defining them, making examples, and writing functions that produce them.
Product Outcomes:
Students identify real-world behaviors that require data structures
Students make use of a complex data structure: Auto
Students define variables bound to autos
Students write code that extracts each field from those autos
Students define functions that produce an auto
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.
Length: 90 minutes
Glossary:
accessor functions: functions to extract values from a data structure
contract: a statement of the name, domain, and range of a function
data structure: A group of values that can be returned as a single datatype
domain: the type of data that a function expects
example: shows the use of a function on specific inputs and the computation the function should perform on those inputs
function definition: code that names a function, lists its variables, and states the expression to compute when the function is used
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
variable name: name of the information that can be different each time a function is used
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
Students will deepen their understanding of function definitions and the Design Recipe
Evidence Statements
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
Seating arrangements: ideally clusters of desks/tables
Review
(Time 20 minutes)
In the previous unit, you reviewed almost everything from Bootstrap 1 including Datatypes, Contracts, and the Design Recipe.
In this unit you will go above and beyond all that, and learn an entirely new datatype that will be the basis for everything you’ll do in
Bootstrap 2. To make sure the material is fresh in your mind, tackle the following activity:
Ask a few introductory review questions to test students’ understanding, such as:
What are the three parts of a Contract?
What is the racket code to draw a solid, green triangle of size 22?
Why is it important to write at least 2 examples before defining a function?
Turn to Page 7 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, whose radius
is 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?
What is the Domain of this function?
What is the Range of this function?
What does it 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 types 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.
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 two examples will be replaced with variables in the function definition. (You don’t always want to make a pink
circle whose radius is double 50. You want to be able to change the color and radius.)
Underneath your examples, copy everything that doesn’t change, and replace the changing things with the variable
names you used.
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?
Turn to Page 8 in your workbooks. Write a function called double-width,
which takes in a height and a color. The function produces a solid rectangle, which is whatever height and
color were passed in. Its width is twice the height.
Fill out the Contract for this function.
What is the function’s Name?
What is the function’s Domain?
What is the function’s Range?
Using the Contract you’ve written, write two Examples for the function.
What part of the Contract helps you fill in the left side of an Example?
What part of the Contract tells you what the function needs as input?
How can the Range of a function help you write the Example?
Looking at those two examples, circle the parts that are change-able, then label them with a good variable name.
Why is it helpful to choose a variable name before defining the function?
Now write the function definition, using the Examples you’ve written.
This is very similar to the previous problem, and is meant to get students very comfortable with using the design recipe before delving into more complex problems.
Remind students about nested functions: A function whose range is a number can be used inside of a function requiring a number in its domian, as in
(circle (* 2 25) "solid" "red").
Introducing Structs
Overview
Learning Objectives
Students will understand the limitations of atomic datatypes
Evidence Statements
Product Outcomes
Students identify real-world behaviors that require data structures
For each of the things below, figure out which datatype you would use to represent it in Racket.
Would you use a Number, String, Image, or Boolean for:
a color
a picture of a circle
your name
your age
whether or not something is correct
an x-coordinate
your friend’s favorite food
a picture of ninja cat
a set of coordinates
A set of coordinates requires two numbers: an x and a y. Unfortunately, functions can only return one piece of data at a time.
Can you use a String to return two numbers? Not if you want to add or subtract them! Why do you think you can’t use an Image or a Boolean to represent two numbers?
You can illustrate the importance of structures with an activity: Pass out bags of datatype cards, and instruct students to take out all of the cards from
the bags, and set them on the table in front of them. List each thing above that could be returned by a Racket function, and have students hold up a card
to show what datatype each would be.
Every function that you could possibly write or use in Racket can only give back one thing. That is, the range only has one thing in it.
You need a new type of data - something that can hold more than one thing at once. Racket actually has a tool to make such a thing, and
it’s called a Data Structure, or "struct" for short. A struct can hold any number of datatypes. It could have just two numbers,
to represent coordinates, or it could hold as many numbers as you want, as well as strings, images, booleans, or even other structs!
(We’ll talk about nested structures in a later lesson.)
Set aside the two number cards; one for the x and one for the y coordinates. Then pick up your plastic bag. Put the two number cards
inside the plastic bag, and then hold it up. "How many things am I holding? One!"
Now imagine that you’ve put the two numbers that you’re using to describe the x and y into a box. If you were to hold up the box, you’d
only be holding one thing! In the same way, complex structs can be defined in Racket to hold multiple things. Look at some more examples,
but remember that you might need a "struct" to group things together.
Which of the following things can represented using one piece of data (and which type is it?), and which ones need a
struct to contain multiple pieces of data?
the name and the age of a character
a flavor of soup, and whether it is hot or not
how many pets you have
a picture of a shape, with the number of sides and its color
a direction that a plane is traveling, and how fast it is going
In Bootstrap 1, students’ games were made by keeping track of only a few numbers: the x-positions of the danger and target, and y-position
of the payer. In Bootstrap 2, 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 many different values: You couldn’t represent every part of a player
(position, health, inventory, etc.) with one number or string, but you can represent all these things with a data structure.
Autos
Overview
Learning Objectives
Evidence Statements
Product Outcomes
Students make use of a complex data structure: Auto
Suppose you want to open up an autobody shop. You take people’s cars and trick them out, giving them paint jobs, turbo-charging them, etc.
What type of thing is an auto? Is it a number? String? Image? Boolean? You couldn’t describe all of the important things
about an automobile with any one of those things. However, we could say that we care about a couple of things in our shop that can be
described with these types.
For each of the following aspects of an automobile, think about what datatype you might use to represent it:
The model of the car. That could be "Prius", "H2", "XTerra", or something else.
How much horsepower the car has.
How large the rims are.
What color the car is.
The value, or price of the car.
What datatype could we use to represent the entire auto?
Let’s represent the different parts of a car like so:
model: String
horsepower: Number
rims: Number
color: String
value: Number
These are the only things that you’re going to keep track of in an auto, but you can imagine how you might extend it to include other things.
Copy the fields of an auto struct and their types onto the board.
Now that you know everything that is part of an auto, you can use a struct to represent the auto itself. (This is the very first time that
you’re going to use structs, and they’re going to play a HUGE part in your videogame.) Let’s take a look at how this works.
Open the Autobody Shop file and read the line that starts with
(define car1....)(define car1 (make-auto "M5" 480 28 "black" 50000))
What is the name of this auto?
What is the model of this auto?
What is the horsepower of car1?
What is the rim size of car1?
What is the color of car1?
Finally, what is the value of car1?
As you can see here, it’s really easy to make this auto struct! We have a bit of code which tells the computer which order everything goes
in...and we’ll talk about that shortly. For now, let’s practice defining some new autos.
The first line in this file tells the computer that an auto is a new data structure, and the names of its fields.
Below there are three autos defined and assigned to the variables car1, car2, and car3. Ask students
questions about these autos to get them thinking about how they would define their own.
Define another car, called new-car. To start
how would you define this variable?
What function is used to make an auto?
Which thing comes first in an auto struct?
Now what do you expect to happen when you type new-car into the interactions window? Click Run and try it out.
Have students walk you through the process of defining a variable called new-car and making an auto with whatever model, hp, rims, etc. they like.
If they struggle with making an auto, have them check their contracts page!
Define two new variables for each of your favorite cars. Call one [yourname]-car (nathan-car, sam-car, jill-car, etc),
or whatever name you prefer. You can make any kind of cars that you want, as long as your struct has the right types in the right orders!
Repetition is key in this lesson. Have students identify each part of the auto struct for every auto they’ve defined.
What is the model of their first auto? Its value? Ensure that students are using their inputs in the right order!
When you defined these new autos, you used a new function: make-auto.
What is the name of this function?
How about the domain?
How many things are in the domain?
The five things in the domain of make-auto are, in fact, the five
things that we have already listed! So in our workbook, on the Contracts page, we know to write:
Remember to have students copy the contract into their workbooks, and write the contracts yourself on the board.
With data structures, the order is very important: we always want the first string in make-auto to be the auto’s model, the first number
to be its horsepower, etc.
Underneath the contract, write what each part of make-auto’s domain represents.
We know the name and domain, but what’s the range? If I give make-auto a String representing the model of an auto, a number for the hp,
another number for the rim size, a string for the color, AND a number for the value, what should I get back? An Auto! But Racket doesn’t have a
datatype for an Auto. We’ll have to use a struct. Racket doesn’t have autos built into it, so later on you’ll learn about defining your own
structures to use in YOUR videogame.
Autos are the first example of defining a new datatype that students will see, but Racket allows you to define any number of new data structures to hold
any combination of values. The important points to remember about structures is that whenever make-[structure] is called, 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. Unit Three introduces
students to even more data structures, and in Unit Four they begin defining their own.
After clicking the "Run" button, in WeScheme, type car1 into the interactions window and hit enter. What do you get back?
Does this make sense? What happened when you typed just a number into the interactions window? We got 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 an auto, and got back that auto!
Remind students that values will always evaluate to themselves. 4 evaluates to 4, the string "pizza" evaluates to "pizza", and car1 evaluates
to (make-auto "M5" 480 28 "black" 50000)
You can see what your cars look like by using the function provided at the bottom of the screen. It’s called draw-auto, and it takes an auto as input and
gives you back an Image with your car in it.
In the interactions window, type (draw-auto car1) and see what happens. Use the function with the cars YOU defined!
Students will spend lots of time "drawing" their autos. Encourage them to define some new autos, and to alter the color, rim size, value, etc. to see their changes
reflected in the images. Don’t forget to remind them to click "Run" after making any changes!
Accessor Functions
Overview
Learning Objectives
Evidence Statements
Product Outcomes
Students write code that extracts each field from those autos
Materials
Preparation
Accessor Functions
(Time 10 minutes)
Suppose you want to get the model OUT of new-car. You don’t care about the rim size, or horsepower, or anything else- you just want to
know the model. Racket has a function for that, called auto-model. If you give auto-model an auto, it will return the model
of that auto.
If you type (auto-model new-car) into the interactions window, what should it evaluate to? Try it out!
What kind of thing did it return: A number, string, image, or struct?
Practice taking the model out of EVERY auto you have defined, using auto-model
In your workbook, flip back to your contract sheet. Think about what kind of thing you gave to the auto-model function,
and what kind of thing you got back.
What is the name of this function?
What is the domain of this function?
What about the range?
Write the contract for auto-model on your contract sheet.
; auto-model : auto -> String
Of course, there are functions to access any part of an auto, not just the model! What do you think the contract for auto-hp is?
Write it down in your workbook.
Write down the contracts for auto-rims, auto-color and auto-value. Then try them out on your autos! Do they do what you expect?
A way to prompt students to use these functions is to ask: "How do you get the horsepower out of an auto?" "How do you get the color out of an auto?"
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 function.
The previous functions are known as Accessor Functions. They allow you to specify what part of a struct you want, without
getting back the whole thing. If we want to know if we can afford a certain auto, we probably only care whether the value is less than
a certain amount. Likewise, if we want to know whether or not a character has died, we only need to know if his health is less than 0:
we might not care what his location is, or the color of his armor. Programmers use accessor functions a lot, in order to make large
pieces of data (like structures) more manageable.
Autobody Shop
Overview
Learning Objectives
Students will write complex functions that consume, modify and produce structures
Evidence Statements
Product Outcomes
Students define functions that produce an auto
Materials
Preparation
Autobody Shop
(Time 25 minutes)
Now you know all about how to work with automobiles in Racket!
What function makes an auto?
Which function draws that auto?
How do you get the value out of an auto?
How do you get the color out of an auto?
But you don’t just want to take an auto and give it right back. You’re running an autobody shop! You’ll take people’s cars and change
them, making them better in some way, and then return them to the customer. Let’s figure out how to do that.
Turn to Page 9 in your workbooks. Write a function called paint-job,
which changes the color of an automobile.
What is the domain for this function? We’ll need to get instructions about which auto we’re changing,
AND what color we’re making it.
What do you think our autobody shop is going to give back? What would be the range of
paint-job?
In your first example, use the original car1 and turn it purple. We know our customer will expect to get an auto back: you wouldn’t bring your car
into the shop and be OK with only getting a pair of rims back! But we won’t be returning the same auto- it will be almost identical, with only the color changed.
It might not be immediately obvious to students that when a function returns an auto, they must use the make-auto function to
produce it. By starting with a "fresh" auto, students are forced to think about every single field in order. Thinking about what exactly
makes up an auto and going back to the contract for make-auto gives them lots of practice with the auto struct and accessor
functions.
The moment you write make-auto, you know that you’ll need to give it five things: the model, hp, rims, color, and value of that auto.
We already know what model this car should be: the same as the given auto! But what if you didn’t know exactly what string to use.
How could you access JUST the model of car1 and use it in your make-auto function?
The horsepower also doesn’t change with a paint job. So how do you get the hp out of car1?
The rim size shouldn’t change with a paint job. How do you get the rims out of car1?
What about the color? In this example paint-job is taking in car1 and the string "purple".
So this auto’s color will just be "purple".
Don’t forget the last part of the auto struct- the value! The purpose statement for paint-job doesn’t say anything about the value
changing, so how do you get the original value out of car1?
Write one more example for the function paint-job, this time using it to paint car2 green.
Circle and label what changes between the two examples. How many variables will this function need?
Write the definition, using the examples to help you.
After replacing the changing things with variables, your definition should look similar to:
Students may be tempted to put color in quotes, because the color of the car must be a string. However, the domain of
paint-job tells us that the function will take in an auto and a string, so whatever color is input will already
have quotes around it. Values evaluate to themselves, so the string "color" cannot evaluate to anything other than "color".
If we want color to be a variable, or shortcut for "purple", "green", "blue", etc. it must be written WITHOUT quotation marks.
Turn to Page 10 in your workbooks. When you turbocharge an engine, you get
more power out of it. Your bodyshop offers a turbocharging job that adds 20 horsepower to any engine, but keeps everything
else the same.
Fill out the Contract and Purpose Statement for the function.
Write two Examples for how one would use turbocharge.
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 accessor functions, extracting pieces of the Auto structs and modifying them.
Closing
Overview
Learning Objectives
Evidence Statements
Product Outcomes
Materials
Preparation
Closing
(Time 5 minutes)
Structures are a powerful tool for representing complex data in a computer program. Simple videogames, like Pong, might only need to
keep track of a few numbers at once, like the position of the ball, position of each paddle and the score. But if a game has many
different enemies, each with their own position and health, or multiple levels with their own background image, the game can get
very complicated very fast, and structs 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 will create your own structs to make a customized videogame.
Have students volunteer what they learned in this lesson
Reward behaviors that you value: teamwork, note-taking, engagement, etc
Unit 2
Let’s represent the different parts of a car like so:
