Lab 5h Quoted Lists, Abstraction, Worlds

Purpose The purpose of this lab is to equip you with some conveniences in *SL programming, namely quote, unquote, and friends, and to give you some practice with abstraction. In addition, you get to design a simple list-based calculator.

Quote

Be sure to use BSL+ for this lab.

Quotation uses a new keyword, quote, to write down lists: '(1 2 3), which is translated into (list 1 2 3). That probably seems more complicated than just using list, but the key is that ’ is a shorthand for quote, so you should really write '(1 2 3). Here are some examples:

quote quotes an expression in parentheses by add list after the open parenthesis and quoting everything inside the parentheses. Quoting a number or a string results in the same number or string.

Quoted lists can be nested:

quote is especially useful when writing tests for functions that deal with lists.

Exercise 1 Design a function that takes a list of lists of numbers and returns a list of the sums of all the numbers in each sublist. Using ’ is encouraged.

Quasiquote and Unquote

> '(23 24 x 26 27)

in the interactions area. What result do you expect?

Here is the result of the experiment:

(list 23 24 'x 25 26)

The x did not become 25. Instead, it was quoted to create 'x, which is a new type of value called a Symbol. Symbols play a role similar to that of strings; they are a great way to represent symbolic information as data.

A symbol can look like any variable, with a ’ in front. Consider another example:

> '(1 (+ 1 1) 3)

You might expect this to construct (list 1 2 3). However, following the rules for quote, you discover that '(1 (+ 1 1) 3) is short for (list '1 '(+ 1 1) '3). The quoted numbers remain numbers and the inner list is expanded, and you get (list 1 (list '+ '1 '1) 3). Again, the quoted numbers are numbers, so the final result is

(list 1 (list '+ 1 1) 3)

This means that '+ is a symbol just like 'x; it has nothing to do with the function +.

But what if you actually wanted a list with the result of (+ 1 1) in it? For that, you would use quasiquote. quasiquote constructs lists like quote: `(1 2 3), the shorthand for which is `(1 2 3).

In most cases, quasiquote acts like quote:

The difference is that in quasiquote, you can also unquote to escape back to *SL.

The same example, using the , shorthand for unquote:

Abstraction Over Values

Sometimes when we solve problems, we find that the solution to one problem looks a lot like the solution to another one. Check out these functions and data definition: (from now on we will leave out the definition for lists, and use the [Listof X] notation).

; A [Listof Number] is one of:

; – empty

; – (cons Number [Listof Number])

; lon-add2 : [Listof Number] -> [Listof Number]

; Add two (2) to each element of the given list of numbers

(define (lon-add2 lon)

(cond [(empty? lon) empty]

[else (cons (+ (first lon) 2)

(lon-add2 (rest lon)))]))

; lon-add5 : [Listof Number] -> [Listof Number]

; Add five (5) to each element of the given list of numbers

(define (lon-add5 lon)

(cond [(empty? lon) empty]

[else (cons (+ (first lon) 5)

(lon-add5 (rest lon)))]))

Is it clear what each function does? You are hopefully asking "Why would you do that?!" since they are almost exactly the same.

Exercise 4 Design a function named lon-add-n that abstracts both of the functions above, taking an extra argument, which is the number to be added to each element.

Note: Use the following recipe for abstraction...

1. Are the function definitions similar? If they are based on the same template, the answer is probably yes. If not, reconsider abstracting over them. Mark the differences in pairs and connect the pairs via lines; we call these difference lines.

2. Create a function definition that looks just like one of the two. Give it a new distinct name. Add one parameter to the function header per "difference line". Also add those parameters to the recursive calls. Use the parameters where the different expressions used to be.

3. Can you re-define the original functions using the abstraction you created? Do so.

4. Do the re-definitions pass the test suites for the original functions? If not, you’re in trouble.

5. Develop a general signature for the abstraction and give a purpose statement.

Abstraction over Functions

You'll have to switch to ISL for this part! As you’ve seen in class, functions (as in many other nice programming languages) are considered data just like 5 or (list "hello"). We can name them with defines, return them from and pass them to other functions, and even store them in structures.

Suppose we implemented this function:

; lon-sub-n : [Listof Number] Number -> [Listof Number]

; subtract 'n' from each element of the given list of numbers

(define (lon-sub-n lon n) ...)

This looks like the function you just implemented, right? Substitute - for + and they are actually the same. Substitution... isn’t that just what "plugging-in" does?

Exercise 6 If you were to abstract these two functions into a single, more general one, what would be its signature? Be precise... you will need another arrow (->) in it.

Exercise 7 Write the function, name it lon-do-n, that abstracts both of the functions, taking an extra argument, which is the function to be applied to each element and the given number.

Interpreting a Simple Programming Language

The goal is to design an interactive program that illustrates how a turtle moves when given a series of commands. That is, the program consumes a list of commands, sets up the turtle facing right in the center of the canvas, and then executes one of these commands per clock tick. Its return value is the last position of the turtle.

Our design is available on-line. Please download the program, open it in DrRacket, and read the sections on constant definitions, data representations, main function, and wish list. As you can see the wish list consists of two functions: render-turtle and execute-one-command. We would like you to design these functions. Do not hesitate to add new wishes to the wish list. We recommend that you finish execute-one-command first so that main’s tests pass. Then work on rendering.

Challenge: Random Walks