Environments and Eval

One of a series of tutorials about Scheme in general
and the Wraith Scheme interpreter in particular.

Copyright © 2011 Jay Reynolds Freeman, all rights reserved.
Personal Web Site: http://JayReynoldsFreeman.com
EMail: Jay_Reynolds_Freeman@mac.com.

In previous tutorials we have talked a great deal about the process of evaluation, and how to make it happen. We have also talked about the possibility of having Scheme convert data into running computer code, but we haven't shown a general way to do that. In this tutorial, we will learn how.

Scheme computer programs and other expressions all look like lists -- possibly deeply-nested lists, but lists no less. For example, here is a quoted list that represents the calculation of the hypotenuse of a right triangle whose sides are 3 and 4.

The problem is, how do we get Scheme to evaluate that list? What do we do to get Scheme to remove the quote, so to speak, to treat the list as an expression to be evaluated, and give us back the number 5 as the result?

You could always just type the unquoted list into Scheme at top-level, and it is certainly not cheating to do so, but typing things in at top level isn't the general solution we were looking for, either. We might not be at top level when we need to evaluate the list. We might have built the list up, piece by piece, using operations like "list" and "cons", inside a Scheme program. In that case, we would like to have some procedure that would evaluate the list for us, because Scheme programs have no way to type things at top level. (Actually, they do, but it takes a sneaky trick to pull it off, and it is slow and inefficient besides. We can do better. I will tell you what the trick is later.)

For a long time, most Lisp implementations have had a procedure that does exactly that. It has traditionally been called "eval", and the way you might use it in another Lisp implementation is like this. (It doesn't quite work that way in Scheme.)

There was a long-running debate in the Scheme community about whether Scheme should have an "eval" procedure, and how it should behave if it did. The essence of the debate had to do with what environment "eval" should use for looking up variable bindings. The big choices were

I wont go into the technical and philosophical details of the discussion, but there were many, and it took a long time to resolve the issue. At the time I started writing the ancestor of Wraith Scheme -- the original Pixie Scheme -- the debate was still going on. I wanted Pixie Scheme to have some kind of "eval", and I decided to put one in as an enhancement. I chose to call it something else, so that when and if the dust finally settled in the debate, I would be able also to put in whatever kind of "eval" the Scheme community settled on, without Pixie Scheme's' users having to rename things in their existing programs.

It was particularly easy to put in the kind of eval that used the environment in which it was called, so that is what I did. I named the procedure "e::cons-with-continuation", and it is still there in Wraith Scheme.

We haven't talked much about the continuation yet, and indeed the word has many meanings. In this case, though, the continuation is the stream of instructions which Scheme is going to execute. It is equivalent to a list of instructions. So if you were to cons something with the continuation, you would be putting it at the front of the list of instructions that Scheme was going to execute, so that it would be the very next expression that Scheme executed. Procedure "e::cons-with-continuation" does exactly that, so the its name is quite appropriate, even if it does take too long to type.

Eventually, the debate about "eval" was resolved. In essence, the choice was to use the top-level environment, but the Scheme community decided to put in an extra feature at the same time. So Scheme's "eval" is a little more complicated than the simple model described at the start of this tutorial. First I am going to show you how to use it, and what it does in the most common case. Then I will talk about the extra features.

The way you use Scheme's standard "eval" to evaluate things in the top-level environment is to give it the expression to be evaluated as its first argument and "(interaction-environment)" as a second environment. For example

The extra feature was a way to specify the environment that eval should use. The second argument to "eval" does that. The R5 report does not say what kind of object the second argument to "eval" should be, rather it states that the argument should be what is returned by one of three named functions, one of which is "interaction-environment". In Wraith Scheme, each of these three functions actually returns an environment list of the kind I described in the tutorial "More on Environments" -- you can evaluate "(interaction-environment)" yourself to see what it looks like. Other Scheme implementations may of course use some other kind of object to convey the same information.

As you can probably guess, procedure "interaction-environment" is supposed to return something that has to do with what we have been calling the "top level environment". It does, but to explain more fully, and to introduce the other two procedures that "eval" may rely on, I need to explain how the top-level environment is structured.

The Scheme top-level environment has three layers. At bottom -- at the very tail end of the environment list -- is a rather small environment which is intended to contain only the variable bindings of the essential reserved words of Scheme -- a few things like "if" and "lambda" and so on, that define the fundamentals of the language. In Wraith Scheme, I found it desirable to put a few other things there as well. I hope no one minds. If you would like to see what this list contains, evaluate

This environment is called the null environment.

The second layer, at the next-to-the-last position in the environment list, contains the variable bindings of all the other reserved words that are defined in the R5 report. The combination of the two bottom layers, that contains the variable bindings of all of the reserved words of the R5 report, is called the Scheme report environment.

The third layer contains the variable bindings of all of the names of the procedures and so on that you yourself have defined for Scheme, and in the case of Wraith Scheme, it contains variable bindings of the names of all of Wraith Scheme's enhancements. The combination of the first three layers is called the interaction environment; it is synonymous with what we have been calling the "top level environment".

You have already seen the procedure to obtain the interaction environment. It is "interaction-environment", and is called as "(interaction-environment)". The other two procedures return respectively the Scheme report environment and the null environment, and -- unsurprisingly, I hope -- they are respectively named "scheme-report-environment" and "null-environment". Yet there is one surprise: Each of those last two procedures takes an argument. Only one argument works in Wraith Scheme; it is the number 5. So in summary, the three procedures that return environments for "eval" to use must be called as

The "5" refers to the R5 report. I believe the intent is to allow implementers of Scheme to create single Scheme applications which can behave like the version of the language described in any of the numbered "Rn" reports -- whichever one the user wants to use. You can imagine a Scheme implementation in which "(eval my-expression (scheme-report-environment 6))" evaluated something in an R6 Scheme, whereas "(eval my-expression (scheme-report-environment 4))" evaluated it in R4 Scheme.

In any case, Wraith Scheme is not such an implementation, it is an R5 Scheme and nothing more. Yet in order to conform to the standard for "eval", you must call it with a return value from one of the given procedures as its second argument, and you must use "5" as the argument to "scheme-report-environment" and to "null-environment".

Oh, yes, I was going to tell you how any Scheme can have an "eval" function whether there is one built in or not. We haven't said anything about the procedures to read and write files from within Scheme programs in these tutorials, so I am not going to write the procedure out for you, but the idea is this. You write a procedure that takes the expression you want evaluated as an argument, and within that procedure you

and finally

That is very ugly and very unaesthetic, but it does work. Don't you just love it? By the way, you should probably also remember to delete the temporary file after you are done with it.

-- Jay Reynolds Freeman (Jay_Reynolds_Freeman@mac.com)

Wraith Face