Assignment 2, Due April 16, 1996

On some of the questions you will have to make certain assumptions. Please state the assumptions you are making.

  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.

Maintainer of this page: Bjørn S. Fjeld Pettersen