1. Implement, document (i.e. provide specifications), and test the following functions in Scheme (Racket is also allowed). An association list is a list of bindings of names to values: ((name1 val1) , ((name2 val2) etc (name t value t)). This data structure can be used to implement a symbol table. An environment can be represented by a list of association lists (i.e. a list of symbol tables), where the first element in the list is nearest scope, the second the next surrounding scope, and the last the outermost scope.

a. Write recursive scheme function lookup that takes two parameters name and assoc_list,that returns the binding pair whose name equals the given name. If no such binding is found return the null list.

b.Write recursive function lookup-env that takes two parameters name and environment and returns the binding with the specified name in an environment (i.e. list of association lists) and null if no such binding is found.

Hint: Review the data structures of the implementation of the Metacircular Evaluator, presented in Week 6 Part 1 file.

2. Work out solutions in Scheme of the following SICP programming problems: 4.4, 4.9 of section 4.1.2 and 4.11 of section 4.1.3. Submit your solutions together with the data demonstrating that your code works properly.

You may directly adapt the code available at http://community.schemewiki.org/.