15. Language V6

So far, our source language has no capability to define top-level variables that persist from one expression evaluation to another. V6 addresses this omission.

For example, consider the following list of expression:

define i = 1
define ii = add1(i)
define iii = add1(ii)
define v = 5
define x = 10
define f = proc(x) if zero?(x) then 1 else *(x,.f(.g(x)))
.f(v)
define g = proc(x) sub1(x)
.f(v)
.f(iii)

Evaluated by V6, it produces this output:

i
ii
iii
v
x
f
no binding for g
g
120
6

15.1 A quick tour

Let us go over every line of the input with its corresponding output.

With V6, programs can have now two forms: a top-level "define" or a regular expression. Most lines in the above input exploit the "define" feature. Each "define" binds a value to a variable. For instance, the first line of our input binds integer value 1 to variable i. V6 acknowledges this binding creation by printing the name of the variable to the output. However, a "define" does not just create a new binding, it is does so in some permanent way. We see this permanence in action in the next two lines of the input. The second line creates a new binding for variable ii based on the value bound to i. Indeed variable ii is bound to the evaluation of the expression add1(i) yielding 2. The definition of iii parallels this structure. For each of those definitions, the name of the bound variable appears on the output.

Definitions are not just reserved for integer values. The sixth input line binds a function to variable f (again the name of the variable thus bound appears in the output). The next line then attempts to evaluates this function with the content of variable v. Unfortunately, the function stored in f calls function g which is not defined at this stage. The message "no binding for g" appearing on the output confirms this observation. The next input line does define function g which now allows us to call f without generating an error (at least some values of the parameter): Evaluation of f(v) and f(iii) outputs 120 and 6, respectively.

15.2 Syntax

Since a "program" can now have two forms: A top-level "define" or an expression, we need to have two grammar rules for the Program nonterminal. Below are their grammar rules:

<Program:Define> ::= DEFINE <SYMBOL> EQUALS <Exp>
<Program:Eval>   ::= <Exp>

The only new addition to our lexical section is the definition for a token named DEFINE.

15.3 Semantics

The "define" feature adds "top-level" bindings that persist until all the input is processed, that is, until the end-of-file is detected. It is legal to have multiple "define" of the same variable. The processing of each new such "define" replaces the old value with the new.

A top-level variable is one that has a binding in the initial ("top-level") environment. All we need to do to support the creation of such top-level definitions is to add bindings to the initial environment, the environment that the evaluation of all expressions in the source language extends.

The global env variable contains the initial environment for our languages. The Program module initializes this variable by calling the initEnv static method defined in the Env class.

Program
%%%
env = Env.initEnv()
%%%

Notice that this initial (top-level) environment starts out with an empty list of bindings.

Our strategy for making top-level definitions is to take advantage of the add method in the Env class. To add a new top-level definition, we create a Binding object and add it to the top-level Env object. Once added, these bindings will be known in any subsequent expression evaluation that uses the initial environment.

To support redefinition of variables, we look up the identifier in the top-level environment. If a binding to this identifier already exists in the top-level environment, we replace the binding’s value with the new value.

15.4 Recursion

Interestingly for top-level function definitions, "define" works similarly to letrec with respect to direct recursion support. Indeed every top-level function definition captures (in a closure) the initial environment, which gets modified every time another top-level definition is encountered. When we add a new binding to the top-level environment, the binding gets added to the local bindings instead of extending the top-level environment. In this way, all of the top-level closures can access this binding, as well as any others that may crop up later! Thus the following program works:

define even? = proc(x)
  if zero?(x) then 1 else .odd?(sub1(x))
define odd? = proc(x)
  if zero?(x) then 0 else .even?(sub1(x))
.even?(11)
.odd?(11)

The call to even? produces 0 (i.e., false) and the call to odd? produces 1(i.e., true).