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 ~]$
If you want to
download a copy of the software to your own computer, you should probably get the latest version which is now called Racket.
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.
|
EXP |
using CONS |
Using LIST |
|
(1) |
(cons 1 null ) |
(list 1) |
1.1 |
(1 2 3) |
|
|
1.2 |
(( 1 )) |
|
|
1.3 |
((( 2 ))) |
|
|
1.4 |
(1 (2)) |
|
|
1.5 |
(1 . 2) |
|
|
1.6 |
(1 2 3 . 4) |
|
|
1.7 |
((1 . 2) (3 . 4)) |
|
|
(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
|
S |
expression to return
the atom x |
|
(x) |
(car s) |
2.1 |
((x)) |
|
2.2 |
(1 x 2 3) |
|
2.3 |
(1 (x) 2 3) |
|
2.4 |
(1 (2) ((3))(((x)))) |
|
2.5 |
x |
|
2.6 |
((1 x 2) 3) |
|
2.7 |
(1 . x) |
|
2.8 |
(1 2 . x) |
|
(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.
|