CS61A Summer 2011 Homework 8
Topic: Assignment, state, environments
Reading: Abelson & Sussman, Section 3.1, 3.2
Also read “Object-Oriented Programming---Below-the-line view” (in course reader).
Abelson & Sussman, exercises 3.3, 3.4, 3.7, 3.8, 3.10, 3.11
Some of these require that you draw environment diagrams. You can upload a pdf of your diagrams or turn in hand drawing into the box. Please indicate clearly on your homework if you have done this.
Extra for experts:
The purpose of the environment model is to represent the scope of variables; when you see an x in a program, which variable x does it mean?
Another way to solve this problem would be to rename all the local variables so that there are never two variables with the same name. Write a procedure unique-rename that takes a (quoted) lambda expression as its argument, and returns an equivalent lambda expression with the variables renamed to be unique:
> (unique-rename ’(lambda (x) (lambda (y) (x (lambda (x) (y x))))))
(lambda (g1) (lambda (g2) (g1 (lambda (g3) (g2 g3)))))
Note that the original expression had two variables named x, and in the returned expression it’s clear from the names which is which. You’ll need a modified counter object to generate the unique names.
You may assume that there are no quote, let, or define expressions, so that every symbol is a variable reference, and variables are created only by lambda.
Describe how you’d use unique-rename to allow the evaluation of Scheme programs with only a single (global) frame.
Unix feature of the week: foreach, grep, find
Emacs feature of the week: C-t (transpose), M-c, M-u, M-l (change case)