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

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 1 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 2 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 3 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 (or bigger). 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 4 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 5 Complete the steps of the data design recipe for the given data definition.

Step 3: Which handlers do we need?

Exercise 6 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: Main Function

Now that we’ve decided on our handler functions, we can put together our main function which will call big-bang.

Exercise 7 Design the main function hypnosis which, given an initial RingSet, runs the hypnosis program using big-bang.

Step 5: Design your handlers

Exercise 8 Design the function that draws the RingSet onto the screen. NOTE: You will need a helper function here to do the majority of the work. When writing this helper function, the empty-image will come in handy.

Exercise 9 Design the function that updates the RingSet every time the clock ticks. 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. You can use it with a random number (as in (choose-color (random 7))) to select a random 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 10 Design the function that determines if the program should stop. Remember that the program ends when the outermost ring has a diameter that is at least the width of the screen.

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.