Programming Languages assignment VII

Assignment VII

Due date Friday April 27.


Scheme discussed in detail in Chapter 10 of Sethi's book. A Scheme interpreter
is presented in Chapter 13, along the same lines as what we discussed in class.
The long example on formal differentiation in Chapter 10 is illuminating. Make
sure you read it and understand how it works.

Do the following exercises in Scheme:

a) Write a function that computes the length of a list, counting its
components at the top level:

       (len '(1 2 4 6 8))  yields 5
       (len '( (one 1) (two 2)))  yields 2

b) Write a function that computes the number of atoms in a list:

       (len '( (one 1) ((two 2)))) yields 4

c) Suppose you have a list of pairs (an association list) in which symbols
are paired with an integer (a count). For example:

       ((Mark 15) (Angela 27) (Joe 12) (Curly 23))

Write a function that takes such a list, and a symbol. If the symbol is
already present in the list, return a list with the corresponding count
updated.
          (Update ' Joe '((Mark 15) (Angela 27) (Joe 12) (Curly 23)))
yields
          ((Mark 15) (Angela 27) (Joe 13) (Curly 23))

If the symbol is not present in the list, add the association (Symb 1) to
the list.

d) Using the function you wrote in part c) write a function that takes a
list with duplicate symbols, and produces an association list where each
symbol is associated with the number of times it appears in the original
list. So for example:

        (catalog '(a b c a  b b x y a x b))

yields   ((a 3) (b 4) (c 1) (x 2) (y 1))