Lab 4 The Magic of Recursion

Purpose: The purpose of this lab is to practice designing and programming with self-referential data. We will also assign partners in this lab.

Textbook references: Chapter 9: Designing with Self-Referential Data Definitions

Partner Up!

Goals: Get a lab partner. Begin a beautiful friendship.

As you walk into the lab you should see a list on the board of partnerships. Please find your assigned partner and sit with them. This person is your partner for the next 2 weeks. Say hello! Ask them their favorite color! Tell them something wonderful that happened to you this week!

Exercise 1 Exchange contact information with your partner. You will need to get together a lot so you are going to need to be able to talk to each other. Please give them a method of communicating with you that you will check regularly (as in, don’t just give them your email if you never check your email).

Exercise 2 Arrange a time to start working on homework 4 with your partner. It’s due on Friday so you are going to have to do it soon. It would be a good idea to establish a time to work on future homeworks as well, if you can.

Exercise 3 Read the policy page to find out what to do if you are having problems with your partner. It is very important that you tell us if you are struggling to work with your partner. Otherwise we can’t help you resolve the problem.

Designing with Self-Referential Data

Consider the following self-referential data definition for natural numbers:

; A Nat is one of:

; - 0

; - (add1 Nat)

Note that this definition is different from one you may have seen in lecture. Your TAs will discuss the parallels at the start of the lab.

Exercise 4 Create a template for the data definition given above. If you are struggling with this please see the design recipe page on the course website.

Exercise 5 Design the function even-nat? which takes a Nat and returns true if the Nat is an even number. Yes, zero is even. You may not use even? or odd? to write this function.

Exercise 6 Design the function nat+ which takes two Nats and returns their sum. You may not use + to write this function.

Self-Referential Data in the World

James Braid is trying to perform hypnosis on one of his patients but he needs your help. He has asked you to develop a program which shows a set of concentric rings of various colors filling a screen. The program will start with a blank screen and each time the clock ticks it will add a new circle of a random color and size underneath the current set of circles. The program should stop when the outermost circle is the same size as the screen. Below is a video showing what we are looking for:

Recall that the steps we take to design world programs break with our usual convention of top down programming because the larger program is at the bottom instead of at the top. However, you should continue to design your individual functions using top down programming as much as possible.

Step 1: What stays the same?

Exercise 7 Define some constants to represent the things in the world that never change.

Step 2: What changes?

To help you out James has developed the following data definition for a RingSet:

(define-struct ring [color size others])

; A RingSet is one of:

; - "no rings"

;    and represents the starting state where nothing is on the screen

; - (make-ring Color Nat RingSet)

;    and represents an underlying circle of a given color and radius

Exercise 8 Complete the steps of the data design recipe for the given data definition.

Step 3: Which handlers do we need?

Exercise 9 Write the signature and purpose statements for the handler functions you will need. Recall that big-bang always requires a to-draw clause. Which other clauses will you need based on the program description? If you are having trouble take a look at the documentation, and if you are still confused, ask a tutor or TA for assistance.

Step 4: Design your handlers

Exercise 10 Design the function that draws the RingSet onto the screen. NOTE: You will need a helper function here, and the empty-image will come in handy.

Exercise 11 Design the function that updates the RingSet every time the clock ticks. To ensure that you don’t add circles that are too large for the screen, you’ll want to use min somewhere in this function. Since random produces a number and not a color, James has designed the following function which takes a natural number in the range [0,7) and produces a color:

; choose-color : Nat[0,7) -> Color

; Choose the color corresponding with the given number

(check-expect (choose-color 0) "red")

(check-expect (choose-color 1) "orange")

(check-expect (choose-color 2) "yellow")

(check-expect (choose-color 3) "green")

(check-expect (choose-color 4) "blue")

(check-expect (choose-color 5) "purple")

(check-expect (choose-color 6) "pink")

(define (choose-color n)

(cond [(= n 0) "red"]

[(= n 1) "orange"]

[(= n 2) "yellow"]

[(= n 3) "green"]

[(= n 4) "blue"]

[(= n 5) "purple"]

[(= n 6) "pink"]))

Exercise 12 Design the function that determines if the program should stop. Remember that the program ends when the outermost ring has a diameter that matches the width of the screen. How can we be sure that this will always occur?

Step 5: Put it all together!

Exercise 13 Design the function hypnosis which, given the initial RingSet, begins the animation of the hypnosis rings. Give it a try!

Before You Go...

If you had trouble finishing any of the exercises in the lab or homework, or just feel like you’re struggling with any of the class material, please feel free to come to office hours and talk to a TA or tutor for additional assistance.

NOTE: There is no lab next week because of the exam. The next lab will be on October 15th.

Stretch Goals

In this section we will update the program so that when the circles fill the screen, the program removes them one by one until there is nothing on the screen and then starts all over again adding the circles to the screen in random colors and sizes.

Exercise 14 Update your data definition to account for any new information you need to keep track of. Be sure to complete all the steps of the data design recipe.

Exercise 15 Update any functions that now take in a new data definition. Recall from Lab 3 Structured Data that functions which take in the same data as before can stay the same.