Home > Technology > “Definitional interpreters” by J. Reynolds

“Definitional interpreters” by J. Reynolds

I’ve just completed reading of a famous paper of J. Reynolds “Definitional interpreters for high-order languages”. This paper is so good that I re-read it every two years. First, it has obvious historical value, since it introduced very important concepts for compiler writing and programming language semantics. Even nowdays it is a great tool for undestanding these concepts. It is focused, concise, simple and still very deep (like a half of SICP comressed 10 times). This combination of depth and conciseness is very thought provoking. Each time I read this paper I do two passes. First pass is to strengthen my understanding of overall ideas, and second is for reflections and deep digging. This time I decided to write down the results of second pass. Two years later I’ll do it again and then compare.

The paper is about operational semantics of programming languages. It shows how a meaning of programming language is given by providing an interpreter for this language implemented in another, better understood language, for example an instruction set of some abstract machine. A simple purely applicative high-order language is defined by providing a full operational semantics as a set of rules in spoken language (abstract machine implied). Then author sets a task of implementing an interpreter for that language in that language. Given semantics provides us with understanding of the tool we use and of the thing we make. The purpose of investigation is to get a deep understanding of a nature of high-order functions, and an order of evaluation. There is also a third very important point: a nature of recursion.

As a first step an author provides us with “direct” interpreter, which uses high-order techniques. Unfortunatelly, there is no explanation of how this interpreter is obtained, it is just given. The most striking feature of this  interpreter is that it is meta-cirular, which means that each feature in defined language is implemented directly by the same feature of implementation language. Evaluation of application expression is performed by application, and evaluation of lambda expression produces function. This simplicity is stiking because every reader knows very well that production compilers for programming languages are big and complex. An answer is simple: our interpreter is not conserned with problems of parsing, of code generation and of optimization. However, apparent simplicity is deceaving. Detailed explanations of operational semantics are encoded using high-level techniques, which makes them less explicit and less obvious. The main mystery is an implementation of recursion, which is not revealed since letrec is implemented via letrec.On the over hand, this simple interpreter is a good exercise (or a good example) of a program written in high-level language.

As a second step, this interpreter is defunctionalized, and all high-order functions are removed. Instead, a data structures are provided. This second interpreter is much closer to operational semantics given in the beginning. So, probably a better way to arrange a paper was to start from first-order interpreter and then moving to high-order interpreter. Someone who is familiar with lambda calculus will also note that replacement of high-order functions with data structures is a cheat, because all data structures are syntaxic sugar for lambda terms. Apparent difference is that high-order interpreter produces functions which already contain computations, which are just delayed until a parameter will be supplied. First order interpreter breaks this by adding encode function (which produces a record which is, in fact, a decode function), and by moving computation later just after function which interprets record. I think that this re-arrangement of computations is a most important part.

So, high-order programming style specifies computations which are delayed until all input is available. Delayed computations are two-way abstraction facility: it is opaque for a code which will supply an input, and a delayed computation doesn’t have an access to the code which invokes it, only to supplied parameter. Defunctionalization breaks this abstraction: instead of providing a delayed computation there is an environment captured and computation representation encoded, and the code which supplies an input is now responsible for interpreting that encoded computation. Defunctionalization makes data flow of interpreted program more apparent.

Similar trick with delaying happens with recursion. The most tricky part in explanation is to show that new(e) is the same as e. This happens because instead of packaging environment as function (delayed computation with everything ready except of variable name), an environment contains a syntaxic part of declaration expression, (a “thunk”). Environment now also interpreted by function get(), which unpacks the trunk and evaluates an expression by providing the same enironment which binds name to the trunk. This means that, for example, while evaluating a following expression:

letrec fractal = lambda(x).if x == 0 then 1 else fractal(x – 1)
in fractal(200)

each time when body of lambda encounters a “fractal” name then it first discovers a trunk, then creates a new closure based on it, and then passes a closure into eval function together with same environment, so making of closure from trunk will happen again and again in a loop. This is not very efficient, but simple and clear. More efficient interpreter will use assignment. So, by delaying an evaluation of recursive definition we don’t have to use cyclic records, but somehow recursion is implemented. If get() performs actual evaluation, then recursion in defined language depends on recursion get() -> eval() -> get() -> eval() in defining language. But get() performs simplest evaluation by returning a closure, and actual interpretation of that happens in eval(), so recursion depends on eval() calling itself in a loop. Unlike high-order functions, a recursion not an introduced feature, but meta-circular. After understanding this I immediatelly undestood that this result should be expected. Loops are evaluated by evaluation loop, that’s the only way.

A great thing about second interpreter is that it makes it clear that evaluation is a manipulation on environments, and nothing more. Anyway, programs are closed lambda terms, which are just combinators.

The most difficult part of the paper for me is an introduction of continuations. To understand it, one should first clearly understand a problem. Initially we don’t need an interpreter which allows us flexibly change order of evaluation. We want interpreter which performs some declared evaluation strategy on interpreted program independently on evaluation order of defining language. So all this talk about “serious functions” is not about some abstract functions, but about functions of our interpreter itself. In fact, that we want to do is to make programs which loop forever in case of call-by-value to do it, to loop forever. Yes, we want programs which we expect to not terminate to do it.

After this text was written, I’ve discovered “Definitional Interpreters Revisited” from the same author. Better late then never.

  1. No comments yet.
  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s

%d bloggers like this: