Homework 4
Basic Scheme

out: 3/16, due: 3/30

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

Scheme 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 MzScheme v4.1.1 [3m], Copyright (c) 2004-2008 PLT Scheme Inc.
> (+ 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 (14 points)

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 your 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 symols) 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 (16 points)

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

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 x (cons 'a null))
> (define y (cons 'b x))
> (define z (list x y))
> (define w (cons (car z) z))

(4) Some Simple Scheme Functions (12 points each, total of 60)

Feel free to add addional functions if you think you need them, but you should not need too many.

• Write a Scheme function called countZeros that returns the number of zeros in a given simple list of numbers. The input will be a (possibly empty) list of integers. For example, (countZeros '(0 1 2)) should return the value 1.
• Write a Scheme function called findMinMax that takes a simple list of numbers and returns a list consisting of the smallest and largest values in the list. For example, (findMinMax '(0 1 2)) should return the list (0 2).
• Write a Scheme function called chopList that takes a list and removes the last element of the list. For example, (chopList '(0 1 2)) should return the list (0 1). Make sure that (chopList '()) returns the empty list.
• Write a Scheme function called unravel that takes a list with possible many nested sublists, and returns a list with all atoms at the top level. For example, (unravel '(1 (2 3) (a (b c)))) should return the list (1 2 3 a b c).
• Write a Scheme predicate eqStruc that tests for the structural equality of two input lists. Two lists are structurally equal if they have the same list structure, although their atoms may be different. For example, the lists '(1 2 3 ) and '(4 5 6) are structurally equal. The lists '(a (b c) d) and '(a b (c d)) are not structurally equal.

What to hand in

Hand in (1) your answers to problems 1, 2 and 3 on paper in class; (2) Submit a single file containing the definition of all of your Scheme functions named hw4.ss using the submit command on the gl system with course cs331 and project hw4. For your convenience, we have prepared a file called hw4stub.ss that has function templates for you to fill in.