Jones N.D.Partial evaluation and automatic program generation.1999

Interpreters, compilers, and running times 41

** L

L

M

M

C

The major problem with implementing languages interpretively is that the `natural' running time of the interpreted program must be multiplied by the basic cycle time used by the interpreter. This cost of one level of interpretation may well be an acceptable price to pay to have a powerful, expressive language (as was the case with Lisp since its beginnings). On the other hand, if one uses several layers of interpreters, each new level of interpretation multiplies the time by a signi - cant constant factor, so the total time may be excessive. Compilation is clearly preferable if there are too many interpreters, each interpreting the next.

3.1.7Program running times

We study the time di erence between executing a program directly on a machine and executing it with the aid of an interpreter. That is, we study the cost of interpretation.

For many programming languages one can predict the actual running time on the computer with reasonable precision. For example, the number of elementary operations (required to execute the program) is a good time estimate.

To make this more concrete, suppose that arithmetic expression exp contains c constants, v variables, and m additions or multiplications. A measure of the time to evaluate exp is c + v + m, since every constant, variable, or operator needs to be accessed once. By this measure, evaluation of x+2*y would take 5 time units.

In fact, c + v + m is roughly proportional to the time that would be taken by machine code instructions to evaluate the expression. Since we are mainly interested in the rate of growth of execution time, the di erence between, say, time 10n + 5 and 10n + 8 is immaterial, whereas the di erence between 10n and 11n will be considered signi cant.

Considering a whole program p rather than just an expression, we count one for each variable access, function call, pattern match, arithmetical operation, and logical operation performed.

De nition 3.1 For program p and inputs d1,. . . ,dn, let tp(d1,. . . ,dn) represent the

running time of p on d1,. . . ,dn.

2

42 Programming Languages and Interpreters

3.1.8Interpreter running times

Suppose we are given a programming language S. To de ne the e ect of S-program execution we write an interpreter for S using some existing implementation language, say L. The interpreter is thus an L-program. Its input consists of the S- program s (usually in the form of an abstract syntax tree), together with the input data for s. We now exemplify this using an interpreter (written in ML) for an extremely simple expression language.

Evaluating expressions in contexts

The value of the expression x + 2 y clearly depends on the current values of x and y. More generally, an expression e can only be evaluated if the current values of all variables in it are known. These values can be represented by a socalled environment, namely a function env : V ariable ! V alue. If, for example, env(x) = 5 and env(y) = 7 the value of x+2 y in environment env is 5+2 7 = 19.

An appropriate evaluation function for expressions with variables thus has type

eval : Expression Environment ! V alue env : Environment = V ariable ! V alue

One way to evaluate an expression is by substitution. For example, one could rst substitute for every variable the value bound to it in env, and then apply function neval of Section 2.3 to evaluate the resulting constant expression. An alternative is to do the substitution only when needed during evaluation, using env to the current value of variables. This approach is seen in the following ML program, where eval is de ned by recursion on the expression's syntax.

datatype exp =
Num of int	(* Constant	*)
| Var of string	(* Variable	*)
| Add of exp * exp	(* Addition	*)
| Mul of exp * exp	(* Multiplication *)
fun eval (Num n,	env) = n
| eval (Var v,	env) = env(v)

| eval (Add(e1, e2), env) = eval (e1, env) + eval (e2, env) | eval (Mul(e1, e2), env) = eval (e1, env) * eval (e2, env)

For example, if env = [x 7!5; y 7!7] then evaluation of x + 2 y proceeds as follows:

eval(Add (Var "x", Mul (Num 2, Var "y")), env)

=eval(Var "x", env) + eval(Mul (Num 2, Var "y"), env)

=env("x") + eval(Num 2, env) * eval(Var "y", env)

=5 + 2 * env("y")

=5 + 2 * 7

=19

The untyped lambda calculus: syntax and semantics 43

The running time of the interpreter

Now consider the running time of the interpreter eval. It exceeds the running time texp = c + v + m for direct evaluation because of the `interpretation overhead': the extra book-keeping time needed for eval to decompose exp into its subexpressions and to nd variable values in env.

The interpreter's running time with inputs p and d1; . . . ; dn is approximately tint(p; d1; . . . ; dn) = tp(d1; . . . ; dn)

where is a factor depending only on the program p being interpreted.

Interpretation overhead

Such overhead is typical for a wide range of interpreters. We shall see below that for eval above the factor is between 3 and 5, which thus is the overhead for the `interpretation loop' in eval. For realistic interpreters the interpretation overhead can be substantially larger (factors from 3 to 200 have been reported in the literature), depending on the language being implemented.

Detailed time analysis

In the interpreter eval, an access to a source program variable v is done by an application (env v). Suppose, a little optimistically, that such an application takes 1 time unit. Then a source program variable access involves a call, a match, an access to variable env, an access to variable v, and an application, totalling 5 time units.

Then the total time is 3 for constants (a call, a match, and an access to variable n), 5 for a source program variable (a call, a match, two variable accesses, and an application), and 5 for an addition or multiplication (call, match, two variable accesses, and either + or ) plus the time to evaluate the arguments. The total interpretation time thus is:

tint(exp) = 3c + 5v + 5m

Thus we can relate the maximum evaluation time for the interpreter to the `natural' evaluation time texp:

3 texp tint(exp) 5 texp

3.2The untyped lambda calculus: syntax and semantics

Lambda notation was developed in the 1930s by Alonzo Church [47,48] as a way to write expressions denoting functions and as a medium for studying an important question: what functions can be computed by mechanical devices? (His answer was: those that can be speci ed by lambda expressions.) Since then lambda calculus has been studied extensively within the eld of mathematical logic. It is widely

44 Programming Languages and Interpreters

used in computer science, and is the core of Lisp, Scheme, and most other functional programming languages, including ML, Miranda, and Haskell.

3.2.1Lambda notation for functions

A starting point is the observation that arithmetic expressions alone are not suitable for de ning functions. For example, it is not clear whether the expression n! denotes the factorial function itself (of type n! : N ! N) or its value given the current value of n (of type n! : N). Another problem: if y2 + x is regarded as

a function of two variables, should (y2 + x)(3; 4) have the value 13 = 32 + 4 or 19 = 42 + 3?

These problems are solved by using the notation x:exp to denote a function of one variable. The ` ' is the Greek letter `lambda', x is the formal parameter, and exp is the body of the function. An application ( x:exp)(5) of this function to the value 5, say, is evaluated by rst substituting 5 for all free occurrences of x in exp, then evaluating the resulting expression. A de nition of `free occurrence' appears in the next section.

A function of several variables can be de ned by writing (x1; . . . ; xn):exp. Using this notation we can de ne the two di erent interpretations of y2 + x by

( (y; x):y2 + x)(3; 4)	=	13
( (x; y):y2 + x)(3; 4)	=	19

The notation can be augmented by writing x : A:exp to give the type A of x. If exp has type B, then x : A:exp will have type A ! B. A function of several arguments can be written as

(x1 : A1; . . . ; xn : An) : exp

which has type A1 An ! B, provided exp has type B.

Note that according to these rules (x : A; y : B):exp : C has type (A B) ! C while the expression x : A: y : B:exp : C has type A ! (B ! C). The latter is a curried version of the former.

From now on we consider only the untyped lambda calculus, and therefore do not add types to the expressions. We now give some examples from Section 2.2.1 rewritten as lambda expressions:

square = x:x2

h = (m; n):m + n

k = (m; n):(m + n; m , n) twice = f: x:f(f(x))

add = n: x:x + n

The untyped pure lambda calculus, containing only variables, abstraction, and application, has been studied at length in mathematical logic by Church [48] and

The untyped lambda calculus: syntax and semantics 45

Barendregt [16]. We choose for our mini-language a dialect which is extended with data values (typically numbers or lists) and a conditional expression. Our treatment has di erent goals and thus is less formal than that of Church and Barendregt.

3.2.2Syntax of the lambda calculus

The abstract syntax of our variant of the untyped lambda calculus is de ned by the grammar below. For the sake of generality the set hConstanti of possible constant values and the set hOpi of operations on them have not been speci ed: various dialects will have their own data domains. In our examples, hConsti will be the natural numbers and hOpi the arithmetic operations.

hLami ::=	hConstanti	Constants
j	hVari	Variables
j	hLamihLami	Application
j	hVari.hLami	Abstraction
j if hLami then hLami else hLami		Conditional
j	hOpihLami. . . hLami	Base application

Examples

As in the earlier discussion we shall only parenthesize when necessary to remove ambiguity, and shall write, for example, f x for f(x) and f x y for (f(x))(y). Note that an operator such as + by itself is a lambda expression. Thus (5+6) should formally be written as (+ 5 6), but we shall use ordinary in x notation where it clari es the examples. In an expression --- x.--- the part x is understood to apply to the longest complete expression to the right of the `dot'.

x 5

+ 5 x (or 5 + x in ordinary notation)

x.x + 1 ( y.( x.x/y)6)2

if x=y then x+y else x-y

3.2.3Evaluating lambda expressions

Evaluating a lambda expression is simple: the expression is repeatedly rewritten by a series of reductions until the nal answer is reached, if ever. We write M)P to mean that lambda expression M can be reduced (or rewritten) to lambda expression

P.

An occurrence of variable x in a lambda expression is bound if it is inside a subexpression of form x.. . . . For instance, the occurrence of x is bound in x.x

46 Programming Languages and Interpreters

but not in y.x.

An occurrence of variable x in a lambda expression is free if it is not bound. For instance, the occurrence of x is free in y.x but not in x.x.

A variable x is free in a lambda expression if it has a free occurrence. For instance, x is free in y.x( x.x), but not in y. x.x.

We use a special notation for substitution. When N and M are lambda expressions, [N/x]M is the result of substituting N for all free occurrences of x in M.

3.2.4Lambda calculus reduction rules

-conversion: x.M ) y.[y/x]M

Renaming the bound variable x to y. Restriction: y must not be free in M.

-reduction: ( x.M)(N) ) [N/x]M

Function application. A function x.M is applied to argument N by substituting N for every free occurrence of x in M. Restriction: no free variable in N may become bound as a result of the substitution [N/x]M. This problem can be avoided by rst renaming bound variables in M.

-reduction: op a1. . . an ) b

whenever b is the result of applying op to constants a1,. . . ,an

Computation with data values. For example, (+ 5 6) can be reduced to 11. Restriction: the arguments a1,. . . ,an must be data constants.

reduction of conditional: if	true then M else N	)	M
if	false then M else N	)	N

reduction in context: ...M... ) ...N...

whenever M ) N

A subexpression of a lambda expression may be reduced without changing the rest of the expression.

repeated reduction: M1 ) M3

whenever M1 ) M2 and M2 ) M3

A computation consists of a series of the above reductions. For instance, a conditional (if B then M else N) may be reduced by rst reducing B to an atomic value b; then if b is true, the conditional reduces to M, else if b is false, the conditional reduces to N.

The untyped lambda calculus: syntax and semantics 47

Examples

	+ 5 6	) 11	by -reduction
(5 + 6) = 11		) true	by two -reductions
a.a + 5		) b.b + 5	by -conversion
( a.a + 5)6		) 6 + 5	by -reduction
( a.a + 5)6		) 11	by repeated reductions
( x.( y.x+y)6)7 ) ( x.x+6)7			by reduction in context
if true then 13	else 14	) 13	by conditional
if 5+6=11 then 13	else 14	) 13	by and conditional
( x.(( x.x+x)5)+x+( x.x*x)3)4		) 23	by repeated reductions

A redex is an expression which can be reduced by a -, -, or conditional reduction. A top-level redex is a redex not inside a lambda abstraction. Functional programming languages restrict the use of -, -, and conditional reductions to top-level redexes.

A lambda expression is in weak head normal form (or whnf) if it is a constant, such as 17, or a function x.M, or a free variable x, or an application x e1 . . .

en of a free variable x, where n 1. If a lambda expression is in whnf, it has no top-level redex.

All of the above expressions can be reduced to whnf. However, some lambda expressions cannot. For example, ( y.y y)( y.y y) can be -reduced, but it reduces to itself, which can again be -reduced, and so on inde nitely:

( y.y y)( y.y y)

) ( y.y y)( y.y y) ) ( y.y y)( y.y y)

) . . .

A restriction on substitution

In -conversion and -reduction, the substitution [N/x]M may only be done if no free variable in N becomes bound as a result of the substitution. A free variable that becomes bound is said to be captured.

For example, let y be a free variable of the argument N in:

( x.2+( y.x+y)5) (y+1)

|	{z		} |		{z }
	M				N

Blindly applying -reduction and substitution would yield the lambda expression 2+( y.(y+1)+y)5, in which the free variable y in N has become captured: bound by the lambda abstraction y. in M.

This is clearly wrong, since the y's of M and N have nothing to do with each other, and luckily the restriction on substitution prevents -reduction in this case. However, ( x.M)N can always be reduced if we rst rename M's bound variable y to z by an -conversion.

48 Programming Languages and Interpreters

Functional programming languages

In functional programming languages, considered as implementations of the lambda calculus, renaming is not needed. Such implementations do not allow free variables in the `program' (the top-most lambda expression), and they do not perform reductions inside lambda abstractions x.M. Because of these restrictions, the expressions considered in reduction rules have no free variables. In particular, there are no free variables in the argument N of an application ( x.M)N, and therefore no variables can be captured.

Also, because of the restrictions, every whnf at top-level is a constant or a function.

3.2.5Call-by-value and call-by-name

Even with this restriction, the reductions on a lambda expression may be done in many di erent orders. For example, we may -reduce a top-level application ( x.M)N right away, or we may require the argument N to be evaluated to a whnf before -reduction of the application. These alternatives are known as call-by-name reduction and call-by-value reduction, or normal order reduction and applicative order reduction.

The call-by-name reduction order does not impose further restrictions. Thus the application ( x.M)N can be reduced immediately by a -reduction.

The call-by-value reduction order further restricts the use of -reduction to toplevel redexes ( x.M)P where the argument P is a whnf (that is, a constant or a function). Thus with call-by-value, a (top-level) application ( x.M)N must be reduced by rst reducing the argument N to a whnf P; then ( x.M)P is reduced by a -reduction.

In principle, call-by-name is preferable to call-by-value because of the completeness property: namely, if M can be reduced to a constant c, then the call-by-name reduction order will reduce M to c.

In other words, if there is any way to reduce an expression to a constant, then call-by-name will do it. This does not hold for call-by-value, as shown by the example:

( x.1+2) (( y.y y)( y.y y))

Call-by-name reduces this expression to 3, since x does not occur in the body 1+2. However, call-by-value attempts to reduce the argument (( y.y y)( y.y y)) to a whnf, which is impossible as shown above.

An obvious question is: can di erent reduction sequences produce di erent nal unreducible answers (in the form of constant values)? The answer is `no' as a consequence of the Church{Rosser theorem [115].

The untyped lambda calculus: syntax and semantics 49

3.2.6Recursion in the lambda calculus

The pure lambda calculus has no explicit way of expressing recursion. An extension often seen is the so-called Y constant, with reduction rule

Fix-point reduction: Y M ) M(Y M)

Clearly this allows application of M as many times as desired by reductions:

Y M ) M(Y M) ) M(M(Y M)) ) M(M(M(Y M))) ) . . .

For example, let M be ( f. n.if n=0 then 1 else n*f(n-1)). Then de ne the factorial function by:

fac = Y M

Now 3!, say, can be computed as follows:

fac(3) = Y(M)(3) ) M(Y M)(3)

) ( n.if n=0 then 1 else n * (Y M)(n-1)) (3) ) 3*(Y M)(2)

) 3*M(Y M)(2)

) 3*( n.if n=0 then 1 else n * (Y M)(n-1))(2) ) 3*2*(Y M)(1)

) 3*2*M(Y M)(1)

) 3*2*( n.if n=0 then 1 else n * (Y M)(n-1))(1) ) 3*2*1*(Y M)(0)

) 3*2*1*M(Y M)(0)

) 3*2*1*( n.if n=0 then 1 else n * (Y M)(n-1))(0) ) 3*2*1*1

) . . . ) 6

This gives a syntactical view of recursion; the x-point constant Y explicates recursion by unfolding a formula as often as needed to obtain the desired result. This view resembles the interpretation of recursive type equations as seen in Section 2.3.

Surprisingly, the x-point constant is not really necessary. It can be expressed in the untyped lambda calculus by the following lambda expression, called the Y combinator:

Yn = h.( x.h(x x))( x.h(x x))

To see this, let M be any lambda expression. Then we have

Yn M = ( h.( x.h(x x))( x.h(x x)))M ) ( x.M(x x))( x.M(x x))

) M(( x.M(x x))( x.M(x x)))

Denoting the lambda expression ( x.M(x x))( x.M(x x)) by C, we observe that

50 Programming Languages and Interpreters

Yn M ) C and also C ) M C. Thus C behaves as Y M above, so the lambda expression called Yn faithfully simulates the Y constant.

A call-by-value version of the Y combinator

The expression called C is not in whnf, and -reducing it gives an application M C whose argument is C. Call-by-value reduction will attempt to reduce the argument C to a whnf rst, producing M(M C), then M(M(M C)), and so on. This process will not terminate. Thus Yn is useless with call-by-value reduction order.

However, the lambda expression Yv below encodes recursion under call-by-value:

Yv = h.( x.h( a.(x x)a))( x.h( a.(x x)a))

3.3Three mini-languages

We now present three simple languages and interpreters for them.

Section 3.3.1 presents an interpreter for the untyped call-by-value lambda calculus. A program is simply a lambda expression, and the computed value is an expression also. The lambda calculus is especially interesting because of its simplicity, its computational power, and its notable di erences from conventional languages. Further, it illustrates some fundamental concepts in a simple context:

Binding of variables to values.

Call-by-name and call-by-value argument evaluation.

First-order representation of functions by closures.

Section 3.3.2 presents the language of rst-order recursion equations. This is also a functional, expression-oriented language. Unlike the lambda calculus, the concepts of `program' and `computed value' are separated. The programming languages Lisp, Scheme, ML, and Miranda (among others) resemble a combination of the lambda calculus and recursion equations.

Section 3.3.3 presents the language of traditional imperative ow charts with assignments and jumps, and gives an interpreter for it. Moreover, a mathematical semantics for ow charts is given in Section 3.3.4.

Later in the book we present partial evaluators for each of the three minilanguages, showing a range of partial evaluation techniques necessary to handle the various features.

3.3.1An interpreter for the call-by-value lambda calculus

We now develop an interpreter for untyped call-by-value lambda expressions | an executable ML program, shown in Figure 3.1.