Homework 5
Scheme I

out: 4/5, due: 4/15 (Mon) @11:59pm

This assignment tests your understanding of Scheme s-expressions, lists, and atoms. It also gives you a chance to get your Scheme environment together and practice evaluating simple Scheme expressions in the mzscheme read-evaluate-print listener.

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.

    linux1[1]$ more example.ss 
(define (double x) (+ x x))

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

linux1[2]$ 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)
linux1[3]$
If you want to download a copy of the software to your own computer, you can get it from Racket. Note, though, that there might be subtle differences across versions, so it would be best to download the same release as what is on the GL machines. This is version 5.1.3. To get that version, on the Racket web page, go to "Download", then at the bottom, click on "All Versions", then select the "[Download]" link for Version 5.1.3, and you should be set.

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.

 
EXP
using CONS
Using LIST
  (1) (cons 1 null ) (list 1)
1.1 (1 2)    
1.2 (1 (2))    
1.3 ((1) 2)    
1.4 ((1 2))    
1.5 ((1) (2))    
1.6 (((1)) (2))    
1.7 (((1) (2)))    
1.8 (1 . 2)    
1.9 (1 2 . 3)    

(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

 
s
expression to return the atom x
  (x) (car s)
2.1 (x 1 2)  
2.2 (1 x 2)  
2.3 ((x) 1 2)  
2.4 (1 (x) 2 3)  
2.5 ((1) (x) 2 3)  
2.6 ((1 x 2) 3)  
2.7 (1 x . 2)  
2.8 (1 . x)  
2.9 (1 2 . x)  
2.8 (1 . (x))  

(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))

What to hand in

Submit to project hw5 a pdf file named hw5.pdf with your answers to the problems. For problems 1 and 2, you can just use text input, but make sure it is clear which subproblem each answer is for. For problem 3, you can either use your favorite simple drawing tool, or write it out by hand and scan it in, then insert the picture into the file, before exporting as PDF.