We will be doing two things this week:
1. Converting our existing interpreter from one that uses direct substitution to one that defers it. We will do this through the introduction of environments.
2. We will extend our grammar from WAE to FWAE, and in doing so introduce functions. These functions will be first-class values, and that has some interesting implementation implications.
Conversion Prep (30 - 45m)
Environments are a functional datastructure; by that, I mean we do not "set" or "mutate" the environment. Instead, we extend an existing environment by adding to it, and we do not ever need to remove from it, largely because we are using it in a recursive context that takes us down, not up, through our grammar.
We need two functions: first, one to create an empty environment, and a second to extend an environment.
(define (make-empty-env) ...)
(define (extend-env bnd env) ...)
The first function takes no arguments, and the second takes a binding structure and an environment.
But what is an environment? How about a data definition?
An environment is EITHER
– empty, OR
– a binding followed by an environment
What does that remind you of? You can, at this point, either:
1. Choose an existing Scheme datastructure to represent environments, or
2. Create an mtEnv structure and Env structure that lets you implement the above definition.
After you are done, we need one more function: lookup.
(define (lookup id env) ...)
This function takes an identifier and looks it up in the given environment. If you cannot find the identifier, you should throw an error.
(error 'lookup "No identifier found for ~a" <id>)
The error function takes a symbol (identifying the name of the error context—in this case, the lookup function), a format string (which we have seen briefly before), and then any values you want to substitute into the format string. I recommend passing the identifier that was not found.
Spot Check
Check in with myself or the TA before proceeding. Be prepared to discuss and defend your design for an environment.
Conversion (20m)
Once you have implemented the three functions
1. (make-empty-env)
2. (extend-env bind env)
3. (lookup id env)
you are ready to convert your interpreter. Save your work in a new file called
<uname>-envinterp.rkt
before proceeding.
1. Throw away subst.
2. interp should now take two parameters: an ast and an env. You might rename this to interp-with-env. Replace all recursive calls to interp with this new function name. (Right-click on the function name interp in the define statement and do it the easy way.)
3. You'll now need to handle the id? case in your interpreter. When you find an identifier in your interpretation, what should you do?
4. You'll need to modify the with? case in your interpreter. What should you do when you find a with structure? We used to substitute... now, what should we do instead?
5. You'll need to modify all calls to interp to take a second parameter. You only need to modify the env in the case of with; otherwise, we should probably leave it alone.
6. Write a new function called interp that takes a single argument, ast. It should just call interp-with-env and pass the ast as well as a fresh, empty environment. This is a one-line helper function.
Spot Check
Again, check in with myself or the TA before proceeding.
Note of the Moment (2m)
Remember, functions are:
1. A binding form, and
2. In implementation, just a data structure.
That said, as you are writing your deferred-substitution interpreter (or environment-passing interpreter), things will work or not work based on how you handle your environment. That isn't to say it's hard, or tricky, or anything else: but how you store values into the environment, look them up, and which environment you use is going to be critical.
Please, continue.
Implementing Functions
Functions appear in two places:
1. On the right-hand side of a binding (in a with), and
2. When applied.
We need to handle each of these separately.
Parsing Functions (10m)
When we parse our code, we need to create a fun-def structure for each function definition we see.
(struct fun-def (formal body))
The fun-def structure contains the formal parameter (an id) and the body (a FWAE). When you see a function application, you'll want to create a fun-app structure:
(struct fun-app (id actual))
Interpreting Functions (2h)
When we interpret a function binding, what do we need to do? For example, consider the following program:
(with (x 3)
(with (f (fun (y) (+ x y)))
(with (x 1)
(+ x (f 4)))))
We bind 3 to x. We then bind a function of one argument to the name f. We then bind x to 1. Finally, we evaluate the expression (+ x (f 4)). Here's my big question:
What value of x should we use when evaluating (f 4)?
Should we evaluate the body (+ x y) with x = 3 or with x = 1?
I think, when you see an fun-def structure while interpreting, you will need to rewrite it into a fun-bind structure.
(struct fun-bind (formal body env))
You'll probably have to do this as a special case of with. That is, your subst interpreter may need to actually ask "what is on the right-hand side of my with binding?", and then do the right thing.
Interpreting functions, in a nutshell
1. When interpreting the with, you'll need to see if you're binding a function. If you are, it will (initially) be a fun-def structure. You need to rewrite it as a fun-bind structure, and do the right thing with the environment at that point.
2. When interpreting, you'll encounter fun-app, but not fun-bind structures. Interpreting the function is a matter of interpreting the body with the correct substitutions being made into the correct environment. Remember, the function application is just a substitution... but in the correct environment.
Depending on how you implement your interpreter, you may find the above two instructions more or less accurate. (There are multiple ways to approach your implementation.)
Lab Book and Discussion
The previous section is 1.5hrs (or, perhaps, more) because you need to do a lot of discussion and thinking about how environments work when you encounter functions.
Discussion is key. Work with your partner—or, anyone else—to come up with a clear description of how you should handle the interpretation of first-class functions.
Notes are key. Your lab book should contain clear examples of code, what it should evaluate to, and how you will achieve that evaluation.
Tests are key. You need check-equal? statements (using the rackunit library... (require rackunit) is easier than what we've been doing) that capture your tests before you begin writing your interpreter. This means writing short sample programs and knowing how they should evaluate. Your previous tests should continue to run, and you should continue running them. Another 20-30 tests may appear as part of this work, and that is just fine.
Due Tuesday, N1
I expect you to turn your code in to the Sakai dropbox. Call it <uname>-envinterp.rkt. Please, name the file correctly.
A written document (4-6 pages) that clearly explains two things.
First, your document should explain what substitution is and how it works. Specifically, explain why your function subst works the way it does and why any other behavior would, in your view, be incorrect.
Second, your report should then explain the critical differences between a substitution-based interpreter and a deferred-substitution (or environment passing) interpreter. Specifically, why is this critical in the light of implementing first-class functions? Provide examples that would (for example) fail under substitution but work only because of environment passing.
You are submitting individual reports. I want to know what you understand.
Your report should be free of errors. Typographic errors and poor grammar are not acceptable.
Your report should be submitted to the Sakai dropbox. It should be called <username>-subst.odt. Note, Open Office is a preferred format—not Word.
Your report is due by class on Tuesday.
This should be written so someone with a knowledge of data structures can read your paper and make sense of it. (Assume they have some knowledge of Scheme as well.) Your paper can be structured around your code, and should explain clearly what your code does and why it does it. In other words, your report will demonstrate an understanding of the implementation and the rationale behind it.
Assigned
Tuesday, O25.
Due
Tuesday, N1.
Return By
Tuesday, N7.
