On this page:
Quote
Quasiquote and Unquote
Abstraction Over Values
Abstraction over Functions
Interpreting a Simple Programming Language
Challenge:   Random Walks

Lab 5h Quoted Lists, Abstraction, Worlds

home work!

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.

image

Quote

Be sure to use BSL+ for this lab.

In BSL, you created lists using cons and empty, for example

(cons 1 (cons 2 (cons 3 empty)))

The shorthand function list lets you write (list 1 2 3). This lab introduces an even more concise shorthand: quotation.

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:

> '(1 2 3)

(list 1 2 3)

> '("a" "b" "c")

(list "a" "b" "c")

> '()

empty

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:

> '(("a" 1)
    ("b" 2)
    ("d" 4))
(list (list "a" 1) (list "b" 2) (list "d" 4))

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

image

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.

image

Quasiquote and Unquote

Suppose your definitions area contains one constant definition:

(define x 25)

Imagine running this program and experimenting with

> '(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:

> `(1 2 3)

(list 1 2 3)

> `("a" "b" "c")

(list "a" "b" "c")

> `()

empty

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

> `(1 ,(+ 1 1)  3)

(list 1 2 3)

The same example, using the , shorthand for unquote:

> `(1 ,(+ 1 1) 3)

(list 1 2 3)

Exercise 2 Eliminate quote, quasiquote, and unquote from the following expression so they are written with list. Check your answers in the interactions window after you have finished.
  • `,(+ 1 2)

  • '("foo" (bar ()))

Switch roles.

Exercise 3 Do the same for the following:
  • `(list y 3)

  • `,'(+ 1 2)

  • `("a" ,(cons "b" `("d" "e"))  "c")

image

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.

Switch roles.

Exercise 5 Rewrite (recreate) both lon-add2 and lon-add5 using your more general function, and write a few tests for each to be sure they work as expected.

image

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.

Switch roles.

Exercise 8 Rewrite (or write) both lon-add-n and lon-sub-n using your more general function, and write a few tests for each to be sure they work as expected.

image

Interpreting a Simple Programming Language

Imagine a turtle (or a pointed triangle) that marches on the order of three different commands:
  • move causes the turtle to move forward by a fixed number of pixels;

  • turn left causes the turtle to turn left by 90 degrees on the spot;

  • turn right causes the turtle to turn right by 90 degrees on the spot.

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.

Clearly, commands and series of commands are the two key classes of data. Intuitively, we wish to use lists such as

'(turn-left move turn-right move)

to represent a series of commands. Otherwise the world-program design is relative straightforward, following the design recipe for interactive programs.

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

If you have time, implement a function that when given a natural number n generates a list of n random commands. Here is how to generate one random command:
; {0,1,2} -> ACommand
; generate a command based on the given natural number n
 
(check-expect (random-command 0) 'move)
(check-expect (symbol? (random-command (random 3))) true)
 
(define (random-command n)
  (cond
    [(= n 0) 'move]
    [(= n 1) 'turn-left]
    [(= n 2) 'turn-right]))