Problem Set 8
This problem set requires very little actual programming. In order to do it, however, you will need to have a good understanding of Sections 4.1 and 4.2 of the textbook. If you have lost the habit of planning your work carefully before coming to lab, this would be a good week to change your working style--otherwise you are likely to waste a great deal of time in the lab.
The code for this problem set includes these files:
These tutorial exercises are meant to help you gain some understanding of the evaluator so that you are familiar with the code before you go to lab.
Scoping rules dictate how values for free variables are found. With lexical scoping (which is what you have seen so far), they are looked up in the environment in which the procedure was created. With dynamic scoping however, they are looked up in the caller's environment.
It may be easier to illustrate this using environment diagrams. With the rules you have seen so far, when a procedure is applied, you create a frame and then you hang this new frame off of the frame in which this procedure was created. If dynamic scoping rules are in play, then this new frame hangs off of the environment in which the procedure is being applied.
What do the following expressions evaluate to if lexical scoping were used? What if dynamic scoping were used? Draw environment diagrams to explain how your answers arise.
(let ((y 1))
(let (( f (lambda (y) (lambda (x) (+ x y))) ))
((f 20) 300)))
(let ((y 1))
(let (( f (lambda (x) (+ x y)) ))
(let ((y 20))
(f 300))))
Here is some helpful information for using the evalator:
;;; M-Eval input: (+ 3 4) ;;; M-Eval value: 7
shows an interaction with the meval evaluator. To evaluate an expression, you type the expression into the *scheme* buffer at the ;;; M-Eval input: prompt, and press ctrl-x ctrl-e.
(set! *unparser-list-depth-limit* 7) (set! *unparser-list-breadth-limit* 10)
at the end of the file evdata.scm. You may want to alter the values of these limits to vary how much list structure will be printed as output.
As usual, for all the lab exercises below, you should turn in listings of any procedures you define in your solutions, as well as sample evaluations demonstrating their correct behavior.
You may find it helpful to keep your code, including any modifications you make to the code we have provided, in a separate file. After you have loaded the problem set code, you can then evaluate select portions of code from your answer file to redefine a current definition.
Actually extend the primitives that are bound in the initial global environment with those from Tutorial Exercise 1. Start the evaluator by typing (init) and evaluate a few simple expressions and definitions. It's a good idea to make an intentional error and practice restarting the read-eval-print loop (both with and with-out wiping the environment clean). Turn in a listing of the procedures that were changed and an excerpt of this practice session.
(If for any reason you need other primitives defined, you now know how to include them in the evaluator.)
Let's look at how we can extend the evaluator to be able to handle the AND special form.
(a) One attempt is to type in a definition for AND at the evaluator prompt in the runtime environment of the simulation. However, this will not work. Show an example of why AND doesn't behave properly. What about AND makes it different from the other procedures you've written in this class?
The next two approaches involve modifications to the evaluator meval code.
(b) You've already seen how cond can be implemented as a derived if expression in the evaluator code. Implement AND as a derived expression.
(c) Instead of repackaging the components of AND as a derived expression of another expression that you already know how to evaluate, you can implement AND behavior by handling it directly as a special form (which is what you would have to do if there were no way for AND to be written as a derived expression). Show how to implement AND in this manner.
Let's have some more practice with derived expressions by extending the evaluator so that it can handle let.
(a) Do Exercises 4.6 in the book which asks you to extend the evaluator to handle let.
(b) Do Exercises 4.7 in the book which asks you to extend the evaluator to handle let*.
Consider the for special form: (for <var> <initial> <pred> <next> <body>)
Here's what happens when this expression is evaluated:
For example: (for x 1 (<= x 10) (+ 1 x) (write-line x)) would print the numbers from 1 to 10.
Why is for a special form? Add the for construct as a special form to the evaluator.
In the next exercise, you will be implementing dynamic scoping. You may want to put your definitions in a different file because you will want to use the evaluator that you have at this point (which has incorporated your answer from Lab Exercises 1-4) for Lab Exercise 6.
Modify the evaluator so that it follows dynamic scoping rules rather than lexical scoping rules.
Turn in a listing that shows that your modification correctly performs dynamic scoping instead of lexical scoping. If you've successfully augmented your system to handle let, then you can use the let expressions from Tutorial Exercise 4 to test whether dynamic scoping works.
This exercise explores the possibility of lexical and dynamic scoping co-existing in the same system. Recall that when a procedure is applied, a new environment is created and an expression is evaluated in this new environment. Scoping rules specified how environments are linked together so that this new environment is linked to either the environment in which the procedure was created (a lexical link) or the caller's environment in which the procedure was applied (a dynamic link). In this manner, scoping rules basically told you where to look for the value of a free variable. Imagine a hybrid environment structure where each environment had not one but two links - both a dynamic link dyn-env and a lexical link lex-env, and furthermore, the programmer had the ability to specify that a free variable should be looked up in a dynamically scoped manner instead of the usual lexically scoped way.
We must be able to do two things:
We do this by creating a special form called dynamic. If dynamic is provided with a variable name in addition to a variable value, then this indicates that a new dynamically scoped variable is being created and defined. If dynamic is provided with a variable name only, then this indicates that this variable is a dynamic one and should be looked up in a dynamically scoped manner (by looking in dynamically enclosing environments).
To support dynamic variable declarations and dynamic scoping as an option in addition to the usual lexical scoping rules, we expand the notion of an environment. Specifically, it contains:
Note that dynamic variables and lexical variables can live in the same frame, but in order for a dynamic variable to be accessed (when an expression is evaluated with respect to this environment) the variable must also be present in the list DYNAMICS (i.e. declared to be a dynamic variable).
(We will also require dynamic statements, like internal defines, to appear at the start of a procedure body. If the user does not adhere to this, then anything goes and you cannot guarantee what the outcome will be. In your implementation below though, you do not have to check for this, for simplicity, assume that dynamic statements are correctly placed, although in practice you would have to handle this.)
Here's an example:
(define (foo x y) (define z 100) (dynamic *w* 50) ;; definition (and declaration) (bar (+ x y z))) (define (bar b) (gorp (* 2 b))) (define (gorp c) (dynamic *w*) ;; declaration (+ c *w*)) (foo 1 2) => 256
These three procedures are defined in the global environment. Notice that in foo, *w* and a value are supplied to dynamic and so a dynamic binding is created and in gorp, this dynamic variable is then accessed.
Let's look at what happens when we evaluate (foo 1 2):
Your goal now is to implement this behavior in the evaluator. Use the evaluator that you ended up with before doing Lab Exercise 5.
To start you off, we've provided some code for you in lex-dyn.scm including a modified version of meval and mapply. You need to complete the definitions of several procedures in this file:
(a) Complete the definition of the syntax procedures: dynamic?, dynamic-declaration?, dynamic-definition?, dynamic-variable and dynamic-value.
(b) Study the new environment structure. Complete the definitions for the selectors: enclosing-environment, enclosing-dyn-env and dynamics-in-env, and also the definition for add-dynamic-in-env which adds a variable to the DYNAMICS list.
(c) When looking up a variable, we check if it's on the list of DYNAMICS. If it is, then we look it up in a dynamically scoped manner (we look it up in the current frame, if it's not there, we trace dyn-env links to the dynamically enclosing environment). If it is not on the list of DYNAMICS, we check the current frame for the variable and if it is not found in the current, we follow lex-env links to the lexically enclosing environment.
Complete the definition of lookup-dynamic-loop. (If you find a need to, you may modify the code for lookup-variable-value and lookup-lexical-loop and/or provide any extra helping procedures so long as the procedures are consistent with their specifications.)
Turn in a listing of all the procedures that have been modified or newly defined.
(d) Another operation that requires traversing the environment structure is set-variable-value!. Now that you have had experience with lookup, complete the definitions of set-variable-value!, set-lexical-variable-loop and set-dynamic-variable-loop so that you set! a variable in a manner that is similar to how you would lookup a variable.
Turn in a listing of all the procedures that have been modified or newly defined.
(e) Turn in a listing with well chosen examples as test cases that clearly show that your code and the resulting evaluator correctly handle both dynamic and lexical scoping.
(f) Now that you have understand how lexical scoping and dynamic scoping work, what situations might dynamic scoping be good for? What are some advantages? Are there any risks or disadvantages?
Turn in answers to the following questions along with your answers to the questions in the problem set:
This document was generated using the LaTeX2HTML translator Version 98.1p1 release (March 2nd, 1998)
Copyright © 1993, 1994, 1995, 1996, 1997, Nikos Drakos, Computer Based Learning Unit, University of Leeds.
The command line arguments were:
latex2html ps8-eval.
The translation was initiated by Tony Eng on 1998-11-09