Comp 210 Lab 2: Data Structures

Index: define-struct, Design recipe, Ping-pong example

First, congratulations you have graduated to DrScheme's "intermediate" language level! What we will be introducing isn't allowed in the beginner level. In DrScheme, select Configure Language Level from the Language Level menu. Choose Intermediate from the resulting menu. Click Execute.

`define-struct`

In class we made a data definition for a point (point = a list of two numbers). We then defined several helper functions so that we could just think in terms of points rather than lists of two numbers:

     (define (make-point x y)
        (cons x (cons y empty)))
     (define (point-x point)
        (first point))
     (define (point-y point)
        (first (rest point)))

Doing this sort of thing is very common and also very straightforward. In fact, it's a good thing to automate, so we do. Instead of the above, we can use

     (define-struct point (x y))

This defines functions like the above, and more. In fact, it defines

One constructor make-point.

A constructor constructs one of the indicated compound things, here a point, when given as many arguments as needed, here two.
Two selectors point-x and point-y.

A selector selects the relevant piece of information from the compound thing, e.g., the "x" component of a point.
One predicate point?.

A predicate answers the question whether or not its one argument is of the right form, here a point.

Q: What do each of the following return?

     (make-point 3 4)
     (point? (make-point 3 4))
     (point? (cons 3 (cons 4 empty)))

We originally represented a point as a two-element list. Well, that seems kind of strange:

To build a two-element list, we also need to use empty. Why should we use a representation that needs that "extra" thing?
Accessing the second element is more difficult than the first, i.e., compare (first (rest pair)) vs. (first pair), respectively.

define-struct makes a point not be represented as a list, but as a special thing, different from everything else. But what is the point? Well, all we care about is that it has two elements in it and that we can make them, look inside them, and test them. Do we care what they really are inside the computer?

Q: Would it matter if we had typed (define-struct point (y x)), instead?

Design Recipe for Compound Data

Let's remind ourselves of what the Design Recipe is. We'll need a couple new steps when dealing with structured, or compound, data like the above.

Formulate a data definition.
As above, for a point.
Write the function's contract and header.
Make some examples of what the function should do.
Make a template for the function body.
I.e., given the kind of data that this function takes as input, what do we know? We can use its selectors!
```
     ; distance-to-point : point -> number
     (define (distance-to-point point)
         ...(point-x point)...(point-y point)...)
     
```
Write the function body.
Test the function.

Ping-pong example

To do: Let's play ping-pong. In DrScheme, load the library teach/pingp-play-lib.ss. (In the Language menu, use Set Library To...") Now start the game with (go 'John) (use your name, although it doesn't matter), and click in the window it creates. Click near the paddles to move them.

Ok, now we are going to start writing this program. Don't be afraid -- we're going to go step-by-step, and give you lots of code to do all the drawing stuff. To load some support code into DrScheme, load the library pingp-lib.ss.

To do: Form pairs of students. Do the exercises in section 5.4. You won't finish all these exercises during lab, but hopefully you'll be interested enough to finish on your own. Warning: The online version is garbled in places, so here's an outline:

Allow straight-line movement:
1. Define the vec data structure (and constructor, selectors, and predicate) that has two components, x and y which are numbers. It models speed.
2. Write posn+ : posn vec -> posn. A posn is just like a point, and is already defined in the library.
3. Write vec* : number vec -> vec.
4. Write move : posn vec number -> posn.
5. Test with (tracer a-posn a-vec move time), where time is a number (amount of time). Use (stop) to close the "canvas", i.e., drawing window.
Allow straight-line movement, version 2:
1. Define the ball data structure (and associated functions) that has two components, posn and speed which are a posn and vec.
2. Define move : ball number -> ball.
3. Test with (trace-ball a-ball ball-posn move time).
Model bouncing off a wall:
1. Write east-bounce : ball -> ball, and corresponding functions west-bounce, north-bounce, and south-bounce.
2. Modify these similar functions to write the corresponding functions ew-bounce and ns-bounce.
3. Write ns-speed : ball -> number and the corresponding function ew-speed.
4. Write ns-direction : ball -> symbol and the corresponding function ew-direction. The former returns either 'NORTH or 'SOUTH; the latter, either 'EAST or 'WEST.
5. Write ns-time-to-wall : ball -> number and the corresponding function ew-time-to-wall.
You probably won't get this far in lab, but you should continue following the exercises in the lecture notes.