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
In this tutorial I will be discussing environments in the specific context of Wraith Scheme, and much of what I say will apply to Wraith Scheme only. Other Scheme implementations may do things differently.
We have already discussed environments in the tutorial, "Environments and Scope". There is more to say. First , let's review the basics.
An environment is in essence a list of variable bindings -- key/value pairs in which the key is a variable and the value is its present binding in that particular environment. Sometimes Wraith Scheme actually implements an environment a little differently, using what is called a hash table instead of a list -- we will get to that later. The point is that an environment works like a list of variable bindings -- you can look up the value of a variable in it.
The reason for creating an environment and dealing with it in Scheme is that typically an environment contains precisely the list of variable bindings that are valid in some particular scope. In previous tutorials, we have already seen how Scheme can determine the scope of a variable binding from lexical analysis of program source code, and that typically, the scope of a variable binding is the body of a lambda expression where that variable is an argument. Environments would not be of much use in Scheme if they did not correspond so neatly to the scopes of variables in lambda expressions.
The idea here is that Scheme only has to do the lexical analysis of the text once: The first time Scheme sees a particular lambda expression, it makes up a list of all its argument variables, and associates that list with the lambda expression itself at the place where the lambda expression is stored in Scheme main memory. When the lambda expression is actually used in a procedure application, Scheme uses the list of variables to create an environment for the body of the lambda expression, without having to do the lexical analysis over again.
The process of discovering which variable binding to use for looking up its value by lexical analysis may involve examining the bodies and argument variable names of a whole lot of nested lambda expressions. In order not to have to perform that operation repeatedly as a program is running, Wraith Scheme maintains a list of environments -- you can think of it as a chain or a sequence of environments, one for each lambda expression involved in the nest. When a lambda application begins, Scheme attaches the environment for that lambda expression to the head of the list. If that lambda expression contains another lambda expression, a nested one, then Scheme will attach its environment in turn to the head of the environment list. When a procedure application using a lambda expression finishes, Scheme removes the first item from the environment list.
In this way, the sequence of lambda-expression environments in the list always corresponds to the nesting sequence of the lambda expressions involved. Scheme can find the appropriate binding for a variable simply by going through the environments in the chain one at a time, starting from the head of the list. Scheme does not have to redo the lexical analysis each time: All the information about variable scope is implicit in the structure of the environment list.
When no procedure application is executing -- that is, when Scheme is at top level -- you would expect that the environment list contains only one environment, the top-level environment. That is sort of how it works, but the top-level environment is itself somewhat structured; it has three separate pieces, each with its own environment. So when Wraith Scheme is at top level, there are actually three separate environments in its environment list. We will discuss this more in the tutorial "Evaluation and Eval".
The top-level environment contains a large number of variable bindings, and it take a long time to look things up in a long list of variable bindings. Therefore, Wraith Scheme uses a different mechanism for implementing the top-level environments that contain many bindings. It uses a hash table to hold the bindings.
A hash table works by using a hash function to convert the key of a key-value pair (in this case, the variable name of the binding) into an integer in the range from zero up to and not including N, for some N. One simple hash function for use with variable names might be to add up the ASCII numbers of the letters in the variable, divide by N, and take the remainder. Wraith Scheme uses a different hash function, but that one will do for an example.
The resulting number is used as the index to look up something in a hash vector containing N items. Each item is a list of variable bindings, and the idea is to keep all of the variable bindings whose variable has the same hash value in the same list. So the lookup procedure for a variable in a hash-table environment is to hash the variable name, get the corresponding element of the vector, which will be a list of bindings, and then look for the variable in that list. This mechanism is much faster than looking up the binding in one long list of bindings; it amounts to a way to divide the big long list into sublists systematically, so that you can easily find out which sublist to look in for any given binding. Incidentally, each entry in the hash vector is called a bucket. We might speak of "the bucket corresponding to hash value 42", for example.
The purpose of this tutorial has been to guide you to a better understanding of how Wraith Scheme handles variable-lookup by lexical scope when code is running. Remember that Wraith Scheme maintains a list of environments that correspond to the lexical scopes that are the bodies of any lambda applications that are running or are stacked on the procedure call stack, and that at the very end of this chain are the environments for top level. All Wraith Scheme has to do to find a variable binding is to go through the list of environments one at a time, starting from the front, looking for the variable in question.
-- Jay Reynolds Freeman (Jay_Reynolds_Freeman@mac.com)