, or make programs which run indefinitely.

As of now, we couldn’t, say, write the function map (see our functional programming primer, A Taste of Racket, for a definition). If we try, we get a nasty error:

```(with map (fun (f list)
(if (end? list)
end
(pair (f (first list)) (map f (rest list)))))
(map (fun (x) (+ 1 x)) (pair 7 (pair 6 (pair 5 end)))))```

It complains that “map” is not bound in the current environment, which is a shame, because map is a really great function to have around, and we can’t build it yet (well, that’s not quite true, but it wouldn’t be as straightforward as what we have above).

It turns out that even though we can’t quite do this kind of recursion with names, we can still achieve infinite loops in Chai! We challenge the reader to figure out how to do it, and see what our interactive interpreter does in response. As a hint, the shortest solution the author has found is a mere 33 characters long, including spaces and parentheses, and it only requires functions and applications.

## Some Further Issues to Address

We recall saying we would like the user to be able to redefine what “+” means via a with expression. However, upon trying to evaluate the following program which “adds” two functions, we get an error:

```(with + (fun (f g) (fun (arg) (+ (f arg) (g arg))))
((+ (fun (x) (+ x 1)) (fun (y) (* y  2))) 7))```

In order to fix this, we need to stop distinguishing between primitive operations and functions which are bound to symbols in our environment. In other words, we want to pre-populate the environment with bindings for primitive functions, which can be overwritten by the programmer. This will simplify our code significantly, since we can move even more of the logic outside of the interpreter and parser, and think of everything as a function application. This is something we have to look forward to in the future.

As long as we’re thinking of everything as a function application, why don’t we simplify Chai even further so that we only have functions and applications? No numbers, no primitives, no conditionals. What sort of language would we get? We’ll see just what happens with a little intermezzo next time. Of course, we will only do this temporarily to explore its theoretical properties, and then we’ll return to the civilized world.

Until then!

# Chai – Environments and Variables

As usual, we encourage the reader to follow along with our online interpreter for this version of Chai. In addition, the source code for this version of Chai is available on this blog’s Google Code page. So go ahead: experiment, discover, and play!

The Dr. Racket programming environment (not to scale, color, font, or positioning)

## Variables, Variables, Variables!

A land without variables would be quite ugly. Runtimes would be sluggish, superfluous arithmetic expressions would litter every corner, and the architects (we coders) would be quite melancholy. Want to reuse a value or function? Forget about it. Want to inspect a randomly generated number more than once? Yeah right. Want to have code that someone else can actually read? Dream on.

Luckily, we’re on an exodus to a better place. A land of loops, first-class functions, and all sorts of other neat language forms. Let’s begin by implementing variables and variable references.

## Substitution, Schmubstitution

The first naive approach to variable references would go something like this: whenever the programmer binds a variable, say “x” is bound to 7, the interpreter goes ahead and replaces every occurrence of the symbol “x” with the value 7. So a (pseudocode) program like

```bind x to 7
bind y to 8
x + y```

would first evaluate to

```bind y to 8
7 + y```

and then to

`7 + 8`

and finally result in 15. Of course, this is fine for simple arithmetic expressions, but what if we want to write a program like

```bind x to 1
print x
bind x to (x + 1)
print x
...```

This kind of thing happens all the time in (procedural) programs, specifically when we’re looping over a counting variable. With our current substitution method, this program would evaluate (with a grain of sense) to something counter-intuitive:

```print 1
bind x to (1 + 1)
print 1
...```

This is obviously not what the programmer has in mind. So what we really want with a variable is to capture the current value of a variable at the time it is referenced. In other words, we want to keep track of the scope of our variables. Plainly speaking, a variable’s scope is the part of the program where its values may be accessed. Usually, and for the remainder of this post, such “parts of programs” will be nested expressions. Note that we will go into more depth about scope in future posts, in particular the difference between dynamic scope and lexical scope, but for now the difference is moot, because our programs consist of but a single expression.

Of course there are ways to avoid conflicting substitutions, but they are more work than the solution we will arrive at anyway. So let’s skip banal direct substitution method and go straight to a more civilized discussion.

## Environments

Environments will be our alternative to substitution. An environment is simply a mapping from variable names to values which is updated as a program runs and new variable bindings are introduced. In other words, as our program evaluates it has a new piece of data floating around with it. Returning to our problematic program above, it might evaluate as follows:

```bind x to 1
print x
bind x to (x + 1)
print x```

In the first step, we add “x” to the environment and give it a value of one:

```[environment: x -> 1]
print x
bind x to (x+1)
print x```

When the print statement is reached, the interpreter looks up the appropriate value of $x$ in the environment, and uses that value. After the subsequent bind statement, the evaluation looks like

```[environment: x -> 2, x -> 1]
print x```

In the environment, we simply use the first binding of $x$ as our replacement value. The astute reader might ask: “Why bother keeping the first binding of $x$ around at all?” This is a reasonable question in the simple pseudocode language we have here, but once we implement our syntax form for Chai, we will find virtue in this peculiar decision. In general, the argument in favor of environments will become stronger and stronger as we add more features to Chai. So without further ado, let us design the syntax form for variable bindings and references.

## New Syntax: with and ref

Variable references are easy. We simply add a new language that consists of any valid identifier (here, a symbol as judged by Racket). Our EBNF syntax tree now includes the line:

```expr =...
| variable-reference```

where a variable reference is a string of characters which is recognized as an identifier by Racket. Note that for our purposes we don’t actually care about these kinds of details, and the Racket specification is fairly liberal with identifiers. This means we can use all of the nice descriptive variable names like “number->string”. The specification is more explicit when we implement the additional line of code in our AST:

`[ref (id symbol?)]`

For binding new variables, we will make variable scope explicit. In particular, we want the programmer to be responsible for telling the interpreter where variables are in scope. This extra burden on the programmer is not so bad. In most languages, the scope of a variable is determined by a set of rules, and here we just trade memorization for explicitness and ease of writing the interpreter. So now we introduce the “with” form, which binds a single variable and describes its scope. Its EBNF:

```expr =...
| (with variable-name expr expr)```

The first sub-expression corresponds to the value of the new variable, and the second sub-expression is the “body” of the with. In particular, the result of the “with” expression is the result of the body expression, after adding these new bindings. In our interpreter, the body will be the only place that references to this particular variable are granted. For example,

`(with x (+ 3 4) (* x x))`

evaluates to 49, but the following program, while well-formed, might sensibly raise an error upon evaluation:

`(with x 2 (with y 3 z))`

Since “z” is a free variable. Here the environment only contains “x” and “y”, and “z” is unbound. Another language designer (say, a designer of Mathematica) might reasonably wish to run programs with free variables evaluating trivially to themselves. Unfortunately, doing this right requires a lot of overhead which we are simply not equipped to handle