Lab 4h Lists
Purpose The purpose of this lab is to give you some hands-on experience with list-processing functions and programs.
Notes
For those of you who programmed before, the lists you see here are so-called linked lists, equipped with basic functions (cons, first, rest, cons?, and empty?), which you could of course write in your favorite language. You also encounter empty, a special piece of data.
For everyone, when an interviewer asks in the future whether you know about linked data structures, the answer is yes, we encountered them in the third week of our first course. Conventional approaches to programming introduce such data structures at the end of the second semester or in the third one; you have a leg up here.
In this lab, start with either of the two world programs below, but do try to complete both of them!
Turtles All The Way Down
After a lecture on cosmology and the structure of the solar system, William James was accosted by a little old lady.
“Your theory that the sun is the centre of the solar system, and the earth is a ball which rotates around it has a very convincing ring to it, Mr. James, but it’s wrong. I’ve got a better theory,” said the little old lady.
“And what is that, madam?” Inquired James politely.
“That we live on a crust of earth which is on the back of a giant turtle,” she replied. Not wishing to demolish this absurd little theory by bringing to bear the masses of scientific evidence he had at his command, James decided to gently dissuade his opponent by making her see some of the inadequacies of her position.
“If your theory is correct, madam,” he asked, “what does this turtle stand on?”
“You’re a very clever man, Mr. James, and that’s a very good question,” replied the little old lady, “but I have an answer to it. And it is this: The first turtle stands on the back of a second, far larger, turtle, who stands directly under him.”
“But what does this second turtle stand on?” persisted James patiently. To this the little old lady crowed triumphantly. “It’s no use, Mr. James –– it’s turtles all the way down.”
—
J. R. Ross, Constraints on Variables in Syntax 1
To get you started we will provide a few constants
(define TURTLE-IMG )
(define TURTLE-HEIGHT (image-height TURTLE-IMG)) (define TURTLE-WIDTH (image-width TURTLE-IMG)) (define TURTLE-SCALE 0.8) ; TURTLE-SCALE represents the size of a turtle with relation to the one it is standing on (define BACKGROUND (empty-scene 600 900))
Exercise 1 Develop a recursive data definition for a stack of turtles.
Exercise 2 Design the function draw-turtles that draws a stack of turtles to the scene.
Hint: This may be one of the few times where overlay/align/offset is easier to use than place-image.
After a few clicks, you should have a stack that looks something like this:
Exercise 3 Design the function add-turtle which adds a turtle to a stack of turtles.
Switch roles.
Exercise 4 Design the function click-turtle for big-bang’s on-mouse which adds a turtle when the mouse is clicked.
Exercise 5 Pull all the pieces together and stick them in big bang.
Extensions
Exercise 6 Chelonian Collapse: Try enhancing your turtle pile so that each turtle falls onto the stack from above the top of the screen, and lands on top of the stack. Hint: You will need to change your representation of a world.
Exercise 7 Pile up: Try further enhancing your turtle world to support multiple piles of turtles. Design your new multiple-pile world so that it can handle arbitrarily many piles of turtles: it should contain a list of single-pile worlds. You’ll need to rethink how your mouse handler works, to choose which pile is the correct target for adding the new turtle...
Fun with Gravity
A scientific simulation firm needs to simulate the effects of gravity on an arbitrarily large number of falling balls. Your job is to create a BSL simulation where the scientists can spawn new falling balls by clicking the mouse. They will fall to the ground for a bit until they go off the screen. The app should be in a 500 x 500 window. Once the balls go off screen the scientists no longer care about them.
(require 2htdp/image) (require 2htdp/universe) ; Ball -> LoB (define (main b) (big-bang (cons b empty) ; <— the world state is a LoB [to-draw draw-lob] [on-tick go] [on-mouse new-ball])) ; LoB -> LoB ; move balls, apply gravity, and then filter out those that are off screen (define (go lob) (on-screen-balls (apply-gravity (move-all lob))))
As you can see, the scientists kind of followed the design recipe for world programs. But you know how scientists are. So they leave it to you to finish the job.
Switch roles.
Exercise 8 Develop a data definition for a Ball. A Ball should have a position in x and y and a velocity in x and y (pixels per clock tick).
Domain knowledge What is a velocity? What is a speed? If you don’t recall or if you have never heard, do not hesitate to ask the TA.
Exercise 9 Develop a data definition for a LoB (list of Balls).
Exercise 10 Develop templates for both data definitions. The template for LoB should refer to the template for Ball. Why?
Switch roles after each function you design so that you both get experience writing functions for lists.
Exercise 11 Design the function off-screen?, which determines whether a ball is off the screen.
Hint Use global constants for the size of the canvas rather than putting constant values directly into your code. We do this because you may need to use the canvas size values more than once.
Exercise 12 Design the function move-ball that consumes a Ball and creates a new one that has been moved according to its velocity. The new ball’s velocity is the same as the one used as input.
Domain knowledge If you do not recall what it means for an object to be located at (x,y) and to move by a velocity of (dx,dy), ask your TA.
Exercise 13 Design the function gravity that consumes a ball and creates a new one whose y velocity has been increased by gravitational acceleration.
Exercise 14 Design the function draw-lob that draws a list of balls on to an empty canvas.
Hint If you are using overlay instead of place-image then be sure to have a transparent background, by passing the "transparent" color into the empty-scene function. It can also be useful to first design the draw-ball function.
Exercise 15 Design the function on-screen-balls that filters out all that balls that are off of the screen from a list of balls.
Exercise 16 Design the function move-all that moves every ball in a list of balls according to its velocity.
Exercise 17 Design the function apply-gravity that applies the gravity function to every ball in a list of balls.
You can now comment out the on-mouse clause with #; to run the program.
Exercise 18 Design the function new-ball that adds a ball wherever the user clicks the mouse. The new ball will have a random velocity. You will give this function to on-mouse
Hint Use the function random.