CMPSC 220 - Allegheny College - Spring 2010
This semester, we'll be building our own computer and studying parallel programming with resources from concurrency.cc
We've seen how not to do bindings in a language — unless you're a fan of the programming language Perl — so now we're going to do it right. We'll be implementing lexical scope, and doing it by converting our interpreter from one that is simply naturally recursive to one that is an environment-passing interpreter.
We have to define a few things. First, lets define an empty environment.
(define empty-env '())
So, lets use a list to represent our environment.
Now, we need a procedure that follows the following contract:
;; CONTRACT
;; extend-env : env id val -> env
It should take an environment (a list), an id structure, and a value (implying a structure we have interpreted already), and return a new environment that has been extended with the symbol of the id associated with the value. I would recommend using a data structure called an env-pair to hold the symbol and value.
(define-struct env-pair (sym val))
This means your environment (a list) should just be a list of env-pairs.
Lastly, you'll need to look up values in the environment.
;; CONTRACT
;; lookup-in-env : env id -> value
You should take your environment (a list of env-pairs) and an id structure, and find the env-pair that contains the same symbol as the id structure. Your function should then return the value.
Note that this is a very simple recursive function that will follow the template that you became familiar with in our last assignment. You are given a list of structures (implying you need to look inside of them for information) and an identifier (that is also a structure), but other than that, it's just a simple list processing function.
When you are done with your interpreter that implements lexical scope, write tests that break for one and work for the other. That is, you should be able to write tests that interpret correctly using lexical scope, and when interpreted with dynamic scope, fail. This is much like what we did in class.
Each test should come with a short comment that explains why the test fails for one and passes for the other, indicating that you understand why this works.
Submit your code to Sakai. You are optionally encouraged to make an appointment to come in and discuss your solution. This is an opportunity to ask questions and make sure you're ready for the final.
This work is licensed under a CC BY-SA 3.0 License.