This assignment gives you a chance to get your Scheme environment together and write some simple Scheme functions. Unless otherwise specified (or suggested by the examples) you can assume that reasonable arguments are given to your functions. In other words, you need not add code to check the arguments provided. Obsessive compulsives are free to do so, of course.

Getting ready

We'll use the Racket Scheme system, which has been installed on the gl linux machines and is also available to download and install on your own computer. We recommend that you use the version installed on GL, which is the one that we will use to test your programs. You can invoke this on gl with the mzscheme command, as the following session shows.

[finin@linux1 ~]$ which mzscheme
/usr/local/bin/mzscheme
[finin@linux1 ~]$ more example.ss 
(define (double x) (+ x x))

(define (fact n) (if (< n 2) 1 (* n (fact (- n 1)))))

[finin@linux1 ~]$ mzscheme
Welcome to Racket v5.1.3.
> (+ 1 2)
3
> (load "example.ss")
> double
#<procedure:double>
> (double (+ 100 200))
600
> (define x 99)
> (fact x)
933262154439441526816992...852109168640000000000000000000000
> (exit)
[finin@linux1 ~]$

Your assignment

(1) Constructing s-expressions

One thing you have to master in learning Scheme or Lisp is how to construct s-expressions. In the following table, the first column lists some s-expressions we would like to construct. Complete the rest of the table by giving the simplest possible expression to build the s-expression.

The expression in the second column should only use the cons function and the one in the third should only use list. If it's not possible to construct an s-expression say so. You are not permitted to include a quoted list (like '(b c)) in giving you answer, including a quoted empty list -- use null for that. You are permitted, of course to use quoted atoms. Note that some of the expressions contain pairs with a cdr that is an atom. Such lists must be serialized (i.e., turned into a linear sequence of symbols) using the dotted-pair notation.

We've done the first row for you as an example. You should, of course, verify your work using the Scheme interpreter.

(2) De-constructing s-expressions

Another thing you have to master in learning Scheme and Lisp is how to access elements in an s-expression. In the following table, the first column lists some s-expressions containing a single instance of the atom X. Assume that the variable S is bound to the s-expression in the first column. The second column should be an expression that when evaluated returns the atom X. You are only allowed to use the functions car and cdr and a single instance of the variable s. We've done the first row for you as an example. You should, of course, verify your work using the Scheme interpreter. In doing so, you can assign s a value using the define function, e.g., do (define s '((x)) when checking your answer for 2.1

(3) Depicting s-expressions

It's important to understand how s-expressions are represented in Scheme, but luckily, it's so simple that it's very easy. S-expressions are either atoms or lists. This problem focuses on the representation of lists and assumes that atoms (e.g., numbers and symbols) are simple objects to which we can point. Lists are made up of cons cells, which are data structures that hold two pointers (the car and the cdr). Every cons cell represents a list and the car points to the first element of the list and the cdr points to the list containing the remaining elements. Suppose we type the following two expressions into our Lisp interpreter

> (define foo (cons 'b (cons 'c '())))
(b c)
> (define bar (cons 'a foo))
(a b c)

The standard way to depict the results is shown in the figure. It shows the variables foo and bar pointing to s-expressions that are their values. The depiction makes it obvious that the two lists "share structure".

Draw a similar diagram to show the result of the following dialog with the Scheme interpreter.

> (define a (list 1 2))
> (define b (cons 0 a))
> (define c (list 0 a))
> (define d (cons a a))
> (define e (list a a))

(4) chop and unchop

hw5> scheme
Welcome to Racket v5.1.3.
> (load "hw5.ss")
> (chop '(1 2 3))
(1 2)
> (chop '(1))
()
> (chop '())
cdr: expects argument of type <pair>; given ()

=== context ===
/Users/finin/Sites/331f11/hw/hw5/hw5.ss:7:0: chop
/Applications/Racket/collects/racket/private/misc.rkt:85:7

> (unchop '() 100)
(100)
> (unchop '(1 2 3) 'infinity)
(1 2 3 infinity)

Hints: There are several ways to define these functions, some being more efficient than others. For this assignment you need not produce the most efficient solution. Note that lists in Lisp and Scheme are traditional linked lists. One way to access the last element of a list is to traverse the list until you reach an element where the next (cdr) element is the empty list (null). Another way is to use the built in function reverse and take the first element of that. To "remove" an element from the end of a list, you can reverse it, take the cdr, and return the reverse of that. To add an element to the end of the list, you can reverse it, cons the new element onto the result, and then return the reverse of that.

(5) shift-left and shift-right

Write functions shift-left and shift-right that take a single argument that is assumed to be a list, possibly empty. Shift-left and returns a new list like its argument but with first element moved to the end of the list. Shift right returns a new list with the last element moved to the front. Here are some examples:

> (shift-left '(1 2 3))
(2 3 1)
> (shift-left '(1))
(1)
> (shift-left '())
()
> (shift-left (shift-left '(1 2 3)))
(3 1 2)
> (shift-right '(1 2 3))
(3 1 2)
> (shift-right '(1))
(1)
> (shift-right '())
()
> (shift-right (shift-right '(a b c)))
(b c a)

(6) zipper?, zip and unzip

Let's define a zipper as a proper list where each element is a list with exactly two elements which can be any expressions. Write a function zipper? that returns #t if its single argument is a zipper and #f if it is not. Write a function zip that takes two proper lists and creates a zipper out of them, pairing up elements from the first and second arguments. If the either of the two lists is shorter than the other, use null for the missing elements. Write a function unzip that reverses the process, taking a zipper and returning a list of two lists. Some examples should make this clear.

> (zipper? '((a 1)(b 2)))
#t
> (zipper? '((foo 100)(bar 2 3)))
#f
> (zipper? '((a 1) b (c 3)))
#f
> (zipper? '((a 1) . 2))
#f
> (zip '(a b c) '(1 2 3))
((a 1) (b 2) (c 3))
> (zip '(a b c) '(1))
((a 1) (b ()) (c ()))
> (zip '(a b) '(1 2 3))
((a 1) (b 2) (() 3))
> (zip '() '())
()
> (unzip '((a 1)(b 2)(c 3)))
((a b c) (1 2 3))
> (unzip '())
(() ())

Testing your Scheme code

You should create a single file named hw5.ss that contains the definitions of your functions for problems four, five and six. To help you get started, here is a file with stubs for the functions you have to write. Feel free to add additional functions if you think you need them (you should not, though).

You can test your scheme code using the unit test file hw5test.ss. You can run this from the command line on gl like this

mzscheme -f hw5test.ss

This will run various unit tests and print a report like the following.

[finin@linux1 hw5]$ mzscheme -f hw5test.ss

Running chop tests
5 success(es) 0 failure(s) 0 error(s) 5 test(s) run

Running shift tests
12 success(es) 0 failure(s) 0 error(s) 12 test(s) run

Running zip tests
17 success(es) 0 failure(s) 0 error(s) 17 test(s) run
[finin@linux1 hw5]$

What to hand in

Submit to project hw5 two files: (1) a pdf file named hw5.pdf with your answers to problems 1, 2 and 3 (2) a file named hw5.ss with the definition of all of your Scheme functions.