11 Programs as Data Structures🔗

11.1 Computing over Programs🔗

Until now, we have only written interpreters, i.e., programs that consume our programs and produce a value in our language. However, we have no reason to be limited to just an interpreter. We can take this concept further and build other kinds of programs that manipulates programs.

In fact, in Lambda: First-class Functions to evaluate programs, we used:

• free? queried expressions to check if a variable is a free variable;

• alpha-reduce rewrote expressions to rename certain variables; and

• beta-reduce substituted variables with their values in an expression.

Crucially, all these functions operated on a program, but unlike our interpreter did not return a value. We will use similar ideas here and look at general style of writing such functions.

In general, these take the form of tree walking algorithms (equivalent to doing a depth-first search on a tree). This will be demonstrated by the following examples.

11.2 Queries on Programs🔗

Often, there are programming tools that compute some queries over a given program. As an example, consider a query that computes a list of the integer constants used through a given program. We will define it as a depth-first style tree traversal—except, the nodes in our tree will be the subexpressions. To do this, we need to write a pattern match with cases handling our entire language:

Whenever list-ints comes across an integer, it returns the integer as a list. For booleans and variables, it returns an empty list as these are not integers. All other cases just compose this result from the integer values correctly. For example, +, *, if, let, λ, etc. all themselves will not contain integer constants, but their subexpressions may. So these cases recursively call list-ints on the subexpressions and append all the results from subexpressions together.

We can craft any kind of query that may be useful to compute over programs. A common question often asked is how long is my program? We can write a size function that counts the number of terms in the program.

We are recursively calculating the size of each subexpression and adding 1 or 2 based on how many other keywords or identifiers were there in the term.

We can take any program and ask how long is the program:

Notice the last example carefully, we declared foo as 6, but we called foo as a function. Our size query ran perfectly fine! size works only with the given program’s syntax. It did not have access to the interpreter, thus does not care about the programs semantics. It did not check if a function is being applied or some other value.

11.3 Program Rewrites🔗

We can also write functions that run over programs and rewrites individual terms to be something else (just like alpha-reduce and beta-reduce). It turns out to be useful in a variety of scenarios:

11.3.1 Elaboration🔗

Until now, the recipe we used to design languages broadly fell in these 3 steps:

• Design a syntax for a language feature

• Give semantics to the language

• Implement semantics in the interpreter

We repeated this over and over again as we added new features to the language. Many times, however, new language features do not add any new expressive power to the language. In such cases it should be possible to rewrite a term to something we can already express in the language. Let us look at it with an example. We added let bindings first, followed by lambda functions. But, lambda functions allow us to represent let bindings easily:

or, more generally,

(let ((x e1)) e2)

is equivalent to

((λ (x) e2) e1)

We could simplify our interpreter by removing all the places we handle let and by just rewriting all let-bindings to be represented using lambdas. This means less code (and bugs) in the interpreter. Our interpreter then represents only a smaller version of the surface language, called the core language! The process of rewriting a surface syntax to a smaller core language is called elaboration. The elaborator usually is simpler than an interpreter and it usually needs to work only about the new feature. The original language need not be verified again. Tested certainly, but because we are not truly adding anything to the language except syntax all we need to worry about is the new definitions and whether they implement the new feature correctly. This strategy is used in Haskell, where the Haskell compiler (GHC) implements only a smaller core language and programs in the Haskell surface syntax are reduced to the core language.

We can do something similar for the let-binding example above:

Notice the change from the previous that computed some value over programs. Here our function works over an expression and produces an expression. In contrast, the interpreter works over the program and produces a value.

Here we are recursively calling elaborate-let on the subexpressions on all terms of the program. The real change is only in the let case, where it is rewritten to a function application to e1 with the function as a lambda with body as e2.

11.3.2 Optimization🔗

Most, if not all, modern compilers and interpreters perform some kind of optimization on programs they process. Such optimizations range from simple function inlining and elimination of constant calculations to sophisticated variable elimination and loop unrolling.

This simple example will take a Lambda program and perform optimizations on numerical calculations. We could write some rules that always hold true for integers:

x + 0 = x\\ 0 + x = 0\\ x - 0 = x\\ x - x = 0\\ 1 * x = x\\ x * 1 = x\\ 0 * x = 0\\ x * 0 = 0\\ x / x = 1\\ x / 1 = x\\

These rules are not exhaustive, but it gives you an idea of the kind of rules that can be used for optimization. Let’s define an optimization that replaces each expression on the left with the corresponding expression on the right. These are optimizations because the left-hand side has more computations than the equivalent expression on the right-hand side, which means computing the right hand side expressions will be faster.

All optimizations have to be semantics preserving, i.e., the behavior of a program should not change after optimizations are applied. While the examples of optimization we have here are fairly simple, in general it is non-trivial to design optimizations and prove that they preserve the program behavior for all programs in the language.

Again, our optimize routine is calling itself recursively on every subexpression. Notice all the optimizations we wrote are for the arithmetic operations +, -, *, and /, so our optimizations are only limited to these operations. We encode the optimization rules for all 4 arithmetic operations here. Each subexpression is optimized and then checked if they fit the pattern expected in the rules. For example, if 0 is added to any term, it results in the same term. However, if none of the optimization rules apply, we still have to return the term with the + operation so that the program meaning stays same. Similarly, for - and /, we check if both operands are same in which case we return 0 and 1 respectively. The key thing to note is optimize returns an optimized program not a value like the interpreter. As we are rewriting programs, we have to take care to ensure we produce a program.

We can run our optimizer to check if it behaves as expected:

11.4 Testing🔗

We can convert all the sample programs we ran to check our functions into test in a similar fashion as we did in earlier classes. However, another way to test your programs is to think about properties that these rewrites will have and check if such properties hold on a set of programs.

For example, for the rewrite discussed in elaborate-let, one of the key things is that the program with let and without let should agree on the result. Additionally, the elaborated program should not have any let terms remaining after the rewrite. We can capture these conditions as for all input programs e:

The first clause says that result of evaluation will be equal for both programs, and the second clause says the new program should not have any let bindings. We can define such a query as follows:

Then we can test with the properties by writing a few random terms:

If we miss a recursive call somewhere, our checker can spot that without manual inspection.

For optimizations also, we can come up with a property that both the input and output programs of the optimizer should agree on the results as the optimizer is semantics preserving. Additionally, the output of the optimizer should have same or fewer operations than before. Writing these as a property:

We are reusing the size function we saw earlier. Now we can throw a bunch of random programs at this checker to test our optimizer is correct: