Programming with
Data Structures and Algorithms

Local definitions and quote

This lab will introduce you to two features of Scheme. The first, local will allow you to write code that is more concise, to more easily write faster code, and prepare you for future features of Scheme. The second, quote and s-expressions easily write faster code, and express your data more efficiently.

Local definitions

The local syntax in Scheme allows you to write definitions that have a local scope. This means that whatever you define will be bound the same way as if you used a top-level define statement while you are inside the expression, but will not be bound at all elsewhere.

Take a look at the section on local in How to Design Programs for the syntax. Notice that the definitions work the same way they used to, only now they are inside a local expression. You do not need to read the section titled "Semantics of local", though some of you may find it interesting.

Now do exercises 18.1.1 - 18.1.3. For 18.1.1 you do not need to actually circle anything, but make sure you know what would be circled in which color.

Local definitions can also be very useful when you call a very slow function, and need to use the output more than once. You could just call the function again for each time you need to use the output, but this could take a long time and greatly increase the runtime of your function. This is especially true when the time consuming function is a recursive call. Instead you can bind the output of the call using a local statement, and refer to the binding inside the body of the statement.

Try writing the max function that finds the maximum element of a list of numbers. First write it without using local. Notice that in the worst case, this implementation makes two recursive calls on the rest of the list. This runs in exponential time! Now try writing another version that only makes one recursive call (hint: use local). This version will run in linear time on the length of the list.

S-expressions and quote

What are s-expressions? Though the term sounds forboding, s-expressions simply take the Scheme syntax with which you're already familiar — parenthesized collections of expressions, numbers, and strings — and let you use them to express data. To do so, you will use quote. It is most straightforward to explain quote with examples:

    (quote (4 5 6.0 1/3))
    (quote ("hello" "world"))
    (quote (("My name is" "Jon")
            ("My name is" "Inigo Montoya")))

evaluate to:

    (list 4 5 6.0 1/3)
    (list "hello" "world")
    (list (list "My name is" "Jon")
          (list "My name is" "Inigo Montoya"))

Quote can also be written as shorthand: instead of writing (quote e), you may write 'e. This is how Scheme programmers prefer to write symbols, and, just as (list 4 5 6) is how we view some data which exists internall inside Scheme, we view symbols directly with quote:

    '(4 5 6)
    '(((name "Jon")
       (age 20))
      ((name "Inigo Montoya")
       (ago unknown)))

evaluate to:

    (list 4 5 6)
    (list (list (list 'name "Jon")
                (list 'age 20))
          (list (list 'name "Inigo Montoya")
                (list 'age 'unknown)))

It can even be used to represent things that look like Scheme code, which can be very convenient for writing programs that operate on other programs (type checkers, compilers, &c.) For example,

    '(define (talk who)
         [(equal? who "Inigo Montoya")
          "You killed my father. Prepare to die."]
         [(equal? who "Wesley")
          "As you wish."]))

evaluates to:

    (list 'define (list 'talk 'who)
          (list 'cond
                (list (list 'equal? 'who "Inigo Montoya")
                      "You killed my father. Prepare to die.")
                (list (list 'equal? 'who "Wesley")
                      "As you wish.")))

To formalize:

On atomic data (numbers, strings, and symbols), quote does nothing:
' "foo" "foo"
' 42 42
'apple 'apple
But on lists, quote operates like this:
'(a b c …) (list (quote a) (quote b) (quote c) …)

It cannot be used to write structs.

Try some of the above examples to get a feel for how quote is used.

Universe practice — lab 3.5 (Optional)

If you want, you can work on the following practice with World/Universe. This lab is optional.

This lab will introduce you to Universe, a teachpack for Scheme that allows you to write reactive, graphical programs, by walking you through the creation of a simple video game. If you missed Monday's lecture on reactive programming, Chapter 4 of How to Design Worlds will help you understand what's going on behind the scenes in this lab.

Before you begin, you'll need to add the teachpack. Choose Language -> Add Teachpack… from the DrScheme menu bar, select from the list, press Ok, and then click Run.

A flight simulator tracks the location and travel velocity of an airplane. Since our simulation will be two-dimensional, the location is just an x-y coordinate pair, and the travel velocity is a pair giving the horizontal and vertical components.

DrScheme provides a built-in structure for coordinates:

                  (define-struct posn (x y))

Do not type this into your definitions window -- it is built in!

  1. Develop a data definition for planes that contains an image of the plane, a location (posn) and a travel velocity. Create your own data definition for the travel velocity.

  2. Create an example of a plane with the name plane1. To give your plane an image, use the one supplied by the book: you can either save it to file and insert it into your program using the Special->Insert Image menu option, or just Copy it in your browser and Paste it using the File menu.

  3. Develop a function move-plane that consumes a plane and produces a plane. The new plane has the same image and velocity as the given plane, but the location coordinates are changed by the respective amounts indicated in the travel velocity.

  4. To start using universe, put the following two definitions at the top of your file:

    (define WIDTH 500)
    (define HEIGHT 200)

    Develop a function draw-plane that consumes a plane and produces a scene showing the plane image at its coordinates. To produce a scene, use the place-image function defined in the teachpack as follows, replacing [plane-image], [x-coord] and [y-coord] with expressions that get these values from your plane structure:

      (place-image [image] [x-coord] [y-coord] [previous-scene])
    Since the only image we want on our canvas is the plane, our [previous-scene] should be an empty canvas, which we can produce by calling (empty-scene WIDTH HEIGHT). Note that (0,0) is the top left corner of the canvas, and larger coordinates move down and to the right.

  5. Put the following lines of code at the bottom of your file:

      (big-bang plane1  ;; plane1 is the name we used in part 2
                (on-tick move-plane (/ 1 28))
                (on-draw draw-plane WIDTH HEIGHT))
    When you press Run, DrScheme will pop up a window containing your plane at its original location (make sure the location is within the WIDTH and HEIGHT boundaries defined by the constants above). Note that the plane's location refers to the location of the center of the image. You should see your plane move across the window.

    on-tick tells DrScheme to call move-plane every (/ 1 28) seconds, and on-draw tells DrScheme how to draw the result (where WIDTH and HEIGHT give the size of the image canvas in pixels). After each call to move-plane, DrScheme stores the resulting plane and uses it as the input to move-plane the next time it is called.

    You can stop the animation by closing the animation window. If you leave it open, you will eventually get an error from DrScheme when the plane's coordinates are too big. You can ignore this error.

Now we want the user to control the plane by pressing the arrow keys to increase or decrease the angle at which the plane is coming down.

  1. Develop a function change-plane-vel that consumes a plane and a string (the order of parameters is important) and produces a plane. The produced plane has the same image and location as the given plane, but possibly a new velocity. If the input string is "down", increase the vertical component by 0.5. If the input string is "up", decrease it by the same amount. On any other string, just produce the original plane unchanged (DrScheme may pass in other strings, so you do need the else case here).

    Add the following line as an additional argument to big-bang:

    (on-key change-plane-vel)
    Now when you press Run to start the animation, your plane should move in response to presses of the up and down arrow keys.

Our current animation lets the plane fly right through the ground. We want to (a) stop the animation when the plane touches the ground and (b) report either a crash or a safe landing depending on the rate of vertical descent at the time of landing.

  1. Write a function at-ground? that consumes a plane and produces a boolean indicating whether the bottom of the plane image is at the lower edge of the animation window. The built-in function image-height produces the height of an image in pixels. Remember that the plane's location refers to the location of the center of the image.

    Add the following line as an additional argument to big-bang to stop the animation when the plane lands:

    (stop-when at-ground?)

  1. Develop a function steep-slope? that consumes a plane and determines whether the plane's vertical velocity is more than three times its horizontal velocity.

  2. Edit your draw-plane function to put a large text message in the animation window when the plane touches the ground. The message should be different depending on whether the plane landed steeply or not (such as "CRASH!" versus "Safe landing"). You can produce an image of text using the following:

    (text [string] [font-size] [color])
    To specify font color, just use a string, like "red". The common colors are pre-defined. You can place this image in a scene using place-image, just like the plane image.

There are many more exciting ways to extend this program, like stopping the animation when the plane flies out of the window, or wrapping the plane around the left/right edges, or giving the user more controls. Feel free to experiment if you have time left in the lab. More information about working with key and mouse events is in the documentation for (just look up in the helpdesk).