Problem 11 (200pts): dynamic scoping with mu

All of the Scheme procedures we've seen so far use lexical scoping: the parent of the new call frame is the environment in which the procedure was defined. Another type of scoping, which is not standard in Scheme but appears in other variants of Lisp, is called dynamic scoping: the parent of the new call frame is the environment in which the call expression was evaluated. With dynamic scoping, calling the same procedure with the same arguments from different parts of your code can create different behavior (due to different parent frames).

The mu special form (spec; invented for this project) evaluates to a dynamically scoped procedure.

scm> (define f (mu () (* a b)))
f
scm> (define g (lambda () (define a 4) (define b 5) (f)))
g
scm> (g)
20

Above, the procedure f does not have a or b as arguments; however, because f gets called within the procedure g, it has access to the a and b defined in g's frame.

Implement do_mu_form in scheme_forms.py to evaluate the mu special form. A mu expression evaluates to a MuProcedure. Most of the MuProcedure class (defined in scheme_classes.py) has been provided for you.

In addition to implementing do_mu_form, complete the MuProcedure case within the scheme_apply function so that when a mu procedure is called, its body is evaluated in the correct environment. When a MuProcedure is called, the parent of the new call frame is the environment in which that call expression was evaluated. As a result, a MuProcedure does not need to store an environment as an instance attribute.

Use Ok to unlock and test your code:

python ok -q 11 -u
python ok -q 11

At this point in the project, your Scheme interpreter should support the following features:

  • Creating procedures using lambda and mu expressions,
  • Defining named procedures using define expressions, and
  • Calling user-defined procedures.