Lab 4 The Magic of Recursion

Purpose: The purpose of this lab is to give you some hands-on experience with processing structurally recursive data definitions as well as more practice creating world programs.

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

Code Review

Today we will code review a portion of assignment 3. Feel free to ask questions about the code as we go through it. This is an excellent opportunity to figure out what we were looking for.

Hypnosis

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, growing and shrinking. The user will provide to the program the size of the circle in the center, and each tick the program will add a new ring, of a random size and color. When the screen is full the rings will disappear one by one until only the inner circle remains. Then the process will start over again. The TAs will demonstrate the program at the beginning of class.

Step 1: What stays the same?

Exercise 1 Define constants to represent the things that are not changing in the world. This can include graphical constants (images you will need throughout the program) but can also include non-graphical constants.

Step 2: What changes?

The things that change in this game are the number of rings, and whether we are adding or removing rings. We can keep track of these two things in a structure:

(define-struct game [current up?])

; A CircleGame is a (make-game NestedRings Boolean)

; - where current is the current set of nested rings

; - and up? is #true if we are adding rings and #false if not

Now we need a data definition for NestedRings. Since we don’t know how many rings there will be we need to use a self-referential definition.

(define-struct nested [outer inner])

; A NestedRings is one of:

; - CircInfo

;   -> representing a single circle

; - (make-nested CircInfo NestedRings)

;    -> representing an outer ring and some inner rings/circles

What information do we need to remember about each circle? We need to know its radius since there will be circles of different radii in the program, and we need to know the color since that will change as well. Since we only have two things to keep track of we can use a structure.

Exercise 2 Design a data definition for a CircInfo which keeps track of a circle’s radius and color.

Exercise 3 Create templates for all the data definitions in your program. Remember that when a data definition references another data definition you will have to call another template.

Exercise 4 Create examples for all the data definitions in your program. You will have to do this "bottom up". That is, start by making examples of a CircInfo and work your way up to the more complex pieces of data.

Step 3: Which handlers do we need?

Exercise 5 Write down the signatures and purpose statements for the handler functions you need. This is your "wishlist" of functions that you will need to create.

Step 4: Design your handlers

Exercise 6 Design the handlers you decided on in the last step. Remember to follow all the steps of the function design recipe. These steps will help you ensure that your functions all work together the way you expect.

To help you create circles of a random color James has given you this helpful function which converts a number into one of seven different colors.

; choose-color : Nat -> 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"]

[else "pink"]))

Step 5: Put it all together!

Exercise 7 Design a function that uses big-bang to create your program, inserting the functions you defined above into the appropriate clauses.