Assignment 2, Due April 16, 1996

1. The usual little scheme programs... Implement (without using the built-in functions):
   1. member (test whether an object is in a list)
   2. append (append two lists)
   3. reverse (reverse a list)
   4. sort (return a sorted version of a list)
   5. dot product of two vectors implemented as lists

   ---

2. Suppose that sets are implemented as lists, where each element of a set appears exactly once in its list. Define functions that implement the following operations:
   1. Test whether an element is a member of a set.
   2. Construct the union of two sets.
   3. Construct the intersection of two sets.
   4. Construct the difference of two sets; that is, the set of elements that are in the first set, but not in the second set.
   5. Test if a list is a legal set (i.e. no duplicates)
   Handle errors in an intelligent manner.

   ---

3. Supposes that sets are implemented as binary trees. Define functions as above. (You might also want to create some constructors, i.e. functions that create sets from other values).

   ---

4. Implement pairs (lists) as procedures. Write the functions cons, car, cdr, append.

   ---

5. Consider the following grammar:

   
   <M> ::= id | ( lambda id <M> ) | ( <M> <M> ) | (let (id <M>) <M>)

   
   where id is a Scheme symbol.

   1. Write a Scheme program that accepts an expression in the above language and produces a list of its free variables.
   2. Write a Scheme program that accepts a variable and an expression in the above language, and returns #t iff the variable occurs free in the expression.
   Free variables are defined as the corresponding Scheme expressions.