26 Interpreting Functions
26.1 Adding Functions to the Language
Now that we have basic expressions and conditionals, let’s grow to have a complete programming languageby adding functions.
26.1.1 Defining Data Representations
Imagine we’re modeling a simple programming environment. The developer defines functions in a definitions window, and uses them in an interactions windowFor historic reasons, the interactions window is also called a REPL or “read-eval-print loop”. (which provides a prompt at which they can run expressions). For now, let’s assume all definitions go in the definitions window only (we’ll relax this soon: Functions Anywhere), and all stand-alone expressions in the interactions window only. Thus, running a program simply loads definitions. Our interpreter will correspond to the interactions window prompt and assume it has been supplied with a set of definitions.A set of definitions suggests no ordering, which means, presumably, any definition can refer to any other. That’s what we intend here, but when you are designing your own language, be sure to think about this.
fun double(x): x + x end fun quad(x): double(double(x)) end fun const5(_): 5 end
Exercise
When a function has multiple arguments, what simple but important criterion governs the names of those arguments?
data FunDefC: | fdC(name :: String, arg :: String, body :: ExprC) end
What is the body? Clearly, it has the form of an arithmetic expression, and sometimes it can even be represented using the existing ArithC language: for instance, the body of const5 can be represented as numC(5). But representing the body of double requires something more: not just addition (which we have), but also “x”. You are probably used to calling this a variable, but we will not use that term for now. Instead, we will call it an identifier.We’ve discussed this terminological difference in From Identifiers to Variables.
Do Now!
Anything else?
Finally, let’s look at the body of quad. It has yet another new construct: a function application. Be very careful to distinguish between a function definition, which describes what the function is, and an application, which uses it. The argument (or actual parameter) in the inner application of double is x; the argument in the outer application is double(x). Thus, the argument can be any complex expression.
data ExprC: |
| numC(n :: Number) |
| plusC(l :: ExprC, r :: ExprC) |
| multC(l :: ExprC, r :: ExprC) |
| trueC |
| falseC |
| ifC(c :: ExprC, t :: ExprC, e :: ExprC) |
| <idC-dt> |
end |
| idC(s :: String) |
| appC(f :: String, a :: ExprC) |
fdC("double", "x", plusC(idC("x"), idC("x")))
fdC("quad", "x", appC("double", appC("double", idC("x"))))
fdC("const5", "_", numC(5))
Exercise
Extend desugar with support for identifiers and applications.
26.1.2 Growing the Interpreter
fun interp(e :: ExprC, fds :: List<FunDefC>) -> Value: |
cases (ExprC) e: |
end |
end |
| numC(n) => numV(n) |
| plusC(l, r) => arith-binop(lam(x, y): x + y end, l, r, fds) |
| multC(l, r) => arith-binop(lam(x, y): x * y end, l, r, fds) |
| trueC => boolV(true) |
| falseC => boolV(false) |
| ifC(cnd, thn, els) => |
ic = interp(cnd, fds) |
if is-boolV(ic): |
if ic.b: |
interp(thn, fds) |
else: |
interp(els, fds) |
end |
else: |
raise('not a boolean') |
end |
Exercise
Modify arith-binop to pass along fds unchanged in recursive calls.
fun get-fundef(name :: String, fds :: List<FunDefC>) |
-> FunDefC: |
end |
26.1.3 Substitution
fun subst(w :: ExprC, at :: String, in :: ExprC) -> ExprC: |
end |
Do Now!
Suppose we want to substitute 3 for the identifier x in the bodies of the three example functions above. What should it produce?
In double, this should produce 3 + 3; in quad, it should produce double(double(3)); and in const5, it should produce 5 (i.e., no substitution happens because there are no instances of x in the body).A common mistake is to assume that the result of substituting, e.g., 3 for x in double is fun double(x): 3 + 3 end. This is incorrect. We only substitute at the point when we apply the function, at which point the function’s invocation is replaced by its body. The header enables us to find the function and ascertain the name of its parameter; but only its body participates in evaluation. Examine the use of substitution in the interpreter to see how returning a function definition would result in a type error.
These examples already tell us what to do in almost all the cases. Given a number, there’s nothing to substitute. If it’s an identifier, we have to to replace the identifier if it’s the one we’re trying to substitute, otherwise leave it alone. In the other cases, descend into the sub-expressions, performing substitution.
Before we turn this into code, there’s an important case to consider. Suppose the name we are substituting happens to be the name of a function. Then what should happen?
Do Now!
What, indeed, should happen?
There are many ways to approach this question. One is from a design perspective: function names live in their own “world”, distinct from ordinary program identifiers. Some languages (such as C and Common Lisp, in slightly different ways) take this perspective, and partition identifiers into different namespaces depending on how they are used. In other languages, there is no such distinction; indeed, we will examine such languages soon [Functions Anywhere].
For now, we will take a pragmatic viewpoint. If we evaluate a function name, it would result in a number or Boolean. However, these cannot name functions. Therefore, it makes no sense to substitute in that position, and we should leave the function name unmolested irrespective of its relationship to the variable being substituted. (Thus, a function could have a parameter named x as well as refer to another function called x, and these would be kept distinct.)
cases (ExprC) in: |
| numC(n) => in |
| plusC(l, r) => plusC(subst(w, at, l), subst(w, at, r)) |
| multC(l, r) => multC(subst(w, at, l), subst(w, at, r)) |
| trueC => trueC |
| falseC => falseC |
| ifC(cnd, thn, els) => |
ifC(subst(w, at, cnd), subst(w, at, thn), subst(w, at, els)) |
| appC(f, a) => appC(f, subst(w, at, a)) |
| idC(s) => |
if s == at: |
w |
else: |
in |
end |
end |
Exercise
Observe that, whereas in the numC case the interpreter returned numV(n), substitution returns in (i.e., the original expression, equivalent at that point to writing numC(n)). Why?
26.1.4 The Interpreter, Resumed
| appC(f, a) => |
fd = get-fundef(f, fds) |
subst(a, fd.arg, fd.body) |
Tempting, but wrong.
Do Now!
Do you see why?
| appC(f, a) => |
fd = get-fundef(f, fds) |
interp(subst(a, fd.arg, fd.body), fds) |
Okay, that leaves only one case: identifiers. What could possibly be complicated about them? They should be just about as simple as numbers! And yet we’ve put them off to the very end, suggesting something subtle or complex is afoot.
Do Now!
Work through some examples to understand what the interpreter should do in the identifier case.
fun double(x): x + y end
When we substitute 5 for x, this produces the expression 5 + y. So far so good, but what is left to substitute y? As a matter of fact, it should be clear from the very outset that this definition of double is erroneous. The identifier y is said to be free, an adjective that in this setting has negative connotations.
| idC(s) => raise("unbound identifier") |
And that’s it!
cases (List<FunDefC>) fds: |
| empty => raise("couldn't find function") |
| link(f, r) => |
if f.name == name: |
f |
else: |
get-fundef(name, r) |
end |
end |
26.1.5 Oh Wait, There’s More!
fun subst(w :: ExprC, at :: String, in :: ExprC) -> ExprC: ... end
Sticking to surface syntax for brevity, suppose we apply double
to 1 + 2. This would substitute 1 + 2 for each
x, resulting in the following
expression—
fun subst(w :: Value, at :: String, in :: ExprC) -> ExprC: ... end
Exercise
Modify your interpreter to substitute names with answers, not expressions.
We’ve actually stumbled on a profound distinction in programming
languages. The act of evaluating arguments before substituting them
in functions is called eager application, while that of
deferring evaluation is called lazy—
26.2 From Substitution to Environments
Though we have a working definition of functions, you may feel a slight unease about it. When the interpreter sees an identifier, you might have had a sense that it needs to “look it up”. Not only did it not look up anything, we defined its behavior to be an error! While absolutely correct, this is also a little surprising. More importantly, we write interpreters to understand and explain languages, and this implementation might strike you as not doing that, because it doesn’t match our intuition.
There’s another difficulty with using substitution, which is the
number of times we traverse the source program. It would be nice to
have to traverse only those parts of the program that are actually
evaluated, and then, only when necessary. But substitution traverses
everything—
Exercise
Does substitution have implications for the time complexity of evaluation?
There’s yet another problem with substitution, which is that it is
defined in terms of representations of the program source. Obviously,
our interpreter has and needs access to the source, to interpret it.
However, other implementations—
26.2.1 Introducing the Environment
The intuition that addresses the first concern is to have the
interpreter “look up” an identifier in some sort of directory. The
intuition that addresses the second concern is to defer the
substitution. Fortunately, these converge nicely in a way that also
addresses the third. The directory records the intent to
substitute, without actually rewriting the program source; by
recording the intent, rather than substituting immediately, we can
defer substitution; and the resulting data structure, which is called
an environment, avoids the need for source-to-source rewriting
and maps nicely to low-level machine representations. Each name
association in the environment is called a
binding.This does not mean our study of
substitution was useless; to the contrary, many tools that work over
programs—
Observe carefully that what we are changing is the
implementation strategy for the programming language, not
the language itself. Therefore, none of our datatypes for
representing programs should change, neither—
Let’s first define our environment data structure. An environment is a collection of names associated with...what?
Do Now!
A natural question to ask here might be what the environment maps names to. But a better, more fundamental, question is: How to determine the answer to the “natural” question?
Remember that our environment was created to defer substitutions. Therefore, the answer lies in substitution. We discussed earlier [Oh Wait, There’s More!] that we want substitution to map names to answers, corresponding to an eager function application strategy. Therefore, the environment should map names to answers.
data Binding: | bind(name :: String, value :: Value) end type Environment = List<Binding> mt-env = empty xtnd-env = link
26.2.2 Interpreting with Environments
Now we can tackle the interpreter. One case is easy, but we should revisit all the others:
fun interp(e :: ExprC, nv :: Environment, fds :: List<FunDefC>) -> Value: |
cases (ExprC) e: |
end |
end |
| numC(n) => numV(n) |
| plusC(l, r) => arith-binop(lam(x, y): x + y end, l, r, nv, fds) |
| multC(l, r) => arith-binop(lam(x, y): x * y end, l, r, nv, fds) |
| trueC => boolV(true) |
| falseC => boolV(false) |
| ifC(cnd, thn, els) => |
ic = interp(cnd, nv, fds) |
if is-boolV(ic): |
if ic.b: |
interp(thn, nv, fds) |
else: |
interp(els, nv, fds) |
end |
else: |
raise('not a boolean') |
end |
| idC(s) => lookup(s, nv) |
Do Now!
Implement lookup.
| appC(f, a) => |
fd = get-fundef(f, fds) |
arg-val = interp(a, nv, fds) |
interp(fd.body, <fof-env-interp-appC-rest-xtnd>, fds) |
xtnd-env(bind(fd.arg, arg-val), nv) |
fun lookup(s :: String, nv :: Environment) -> Value: |
cases (List) nv: |
| empty => raise("unbound identifier: " + s) |
| link(f, r) => |
if s == f.name: |
f.value |
else: |
lookup(s, r) |
end |
end |
end |
Observe that looking up a free identifier still produces an error, but
it has moved from the interpreter—
check: |
f1 = fdC("double", "x", plusC(idC("x"), idC("x"))) |
f2 = fdC("quad", "x", appC("double", appC("double", idC("x")))) |
f3 = fdC("const5", "_", numC(5)) |
f4 = fdC("f4", "x", s2p2d("(if x 1 0)")) |
funs = [list: f1, f2, f3, f4] |
fun i(e): interp(e, mt-env, funs) end |
|
i(plusC(numC(5), appC("quad", numC(3)))) is numV(17) |
i(multC(appC("const5", numC(3)), numC(4))) is numV(20) |
i(plusC(numC(10), appC("const5", numC(10)))) is numV(10 + 5) |
i(plusC(numC(10), appC("double", plusC(numC(1), numC(2))))) |
is numV(10 + 3 + 3) |
i(plusC(numC(10), appC("quad", plusC(numC(1), numC(2))))) |
is numV(10 + 3 + 3 + 3 + 3) |
Do Now!
Spot the bug.
26.2.3 Deferring Correctly
interp(appC("f1", numC(3)), mt-env, |
[list: fdC("f1", "x", appC("f2", numC(4))), |
fdC("f2", "y", plusC(idC("x"), idC("y")))]) |
raises "unbound identifier: x" |
fun f1(x): f2(4) end fun f2(y): x + y end f1(3)
In fact, so will our substitution-based interpreter!
Why does the substitution process result in an error? It’s because, when we replace the representation of x with the representation of 3 in the representation of f1, we do so in f1 only.This “the representation of” is getting a little annoying, isn’t it? Therefore, we’ll stop saying that, but do make sure you understand why we had to say it. It’s an important bit of pedantry. (Obviously: x is f1’s parameter; even if another function had a parameter named x, that’s a different x.) Thus, when we get to evaluating the body of f2, its x hasn’t been substituted, resulting in the error.
What went wrong when we switched to environments? Watch carefully: this is subtle. We can focus on applications, because only they affect the environment. When we substituted the formal for the value of the actual, we did so by extending the current environment. In terms of our example, we asked the interpreter to substitute not only f2’s substitution in f2’s body, but also the current ones (those for the caller, f1), and indeed all past ones as well. That is, the environment only grows; it never shrinks.
xtnd-env(bind(fd.arg, arg-val), mt-env) |
26.2.4 Scope
The broken environment interpreter above implements what is known as dynamic scope. This means the environment accumulates bindings as the program executes. As a result, whether an identifier is even bound depends on the history of program execution. We should regard this unambiguously as a flaw of programming language design. It adversely affects all tools that read and process programs: compilers, IDEs, and humans.
In contrast, substitution—
26.2.5 How Bad Is It?
To understand the binding structure of your program, you may need to look at the whole program. No matter how much you’ve decomposed your program into small, understandable fragments, it doesn’t matter if you have a free identifier anywhere.
Understanding the binding structure is not only a function of the size of the program but also of the complexity of its control flow. Imagine an interactive program with numerous callbacks; you’d have to track through every one of them, too, to know which binding governs an identifier.
if moon-visible(): f1(10) else: f2(10) end
Exercise
What happens on cloudy nights?
26.2.6 The Top-Level Scope
(define y 1) (define (f x) (+ x y))
(define y 1) (define (f x) (+ x y)) (define y 2)
(define y 1) (define f (let ((z y)) (lambda (x) (+ x y z)))) (define y 2)
26.2.7 Exposing the Environment
If we were building the implementation for others to use, it would be wise and a courtesy for the exported interpreter to take only an expression and list of function definitions, and invoke our defined interp with the empty environment. This both spares users an implementation detail, and avoids the use of an interpreter with an incorrect environment. In some contexts, however, it can be useful to expose the environment parameter. For instance, the environment can represent a set of pre-defined bindings: e.g., if the language wishes to provide pi automatically bound to 3.2 (in Indiana).
26.3 Functions Anywhere
Programming languages should be designed not by piling feature on top of feature, but by removing the weaknesses and restrictions that make additional features appear necessary.
One of the things we stayed coy about when introducing functions [Adding Functions to the Language] is exactly where functions go. We suggested we’re following the model of an idealized programming environment, with definitions and their uses kept separate. But, inspired by the Scheme design principle, let’s examine how necessary that is.
Why can’t functions definitions be expressions? In our current arithmetic-centric language we face the uncomfortable question “What value does a function definition represent?”, to which we don’t really have a good answer. But a real programming language obviously computes more than numbers and Booleans, so we no longer need to confront the question in this form; indeed, the answer to the above can just as well be, “A function value”. Let’s see how that might work out.
(+ 2 ([deffun f x (* x 3)] 4))
26.3.1 Functions as Expressions and Values
data ExprC: |
| numC(n :: Number) |
| plusC(l :: ExprC, r :: ExprC) |
| multC(l :: ExprC, r :: ExprC) |
| trueC |
| falseC |
| ifC(c :: ExprC, t :: ExprC, e :: ExprC) |
| idC(s :: String) |
end |
| fdC(name :: String, arg :: String, body :: ExprC) |
| appC(f :: ExprC%(is-fdC), a :: ExprC) |
fun interp(e :: ExprC, nv :: Environment): |
# removed return annotation of Value because fdC is not a Value! |
cases (ExprC) e: |
| numC(n) => numV(n) |
| plusC(l, r) => arith-binop(lam(x, y): x + y end, l, r, nv) |
| multC(l, r) => arith-binop(lam(x, y): x * y end, l, r, nv) |
| trueC => boolV(true) |
| falseC => boolV(false) |
| ifC(cnd, thn, els) => |
ic = interp(cnd, nv) |
if is-boolV(ic): |
if ic.b: |
interp(thn, nv) |
else: |
interp(els, nv) |
end |
else: |
raise('not a boolean') |
end |
| idC(s) => lookup(s, nv) |
Do Now!
Observe that we’ve left out the return annotation on interp. Why do you think this is? Run some examples to figure it out.
| fdC(_, _, _) => e |
| appC(f, a) => |
fun-val = interp(f, nv) |
arg-val = interp(a, nv) |
interp(fun-val.body, xtnd-env(bind(fun-val.arg, arg-val), mt-env)) |
check: f1 = fdC("double", "x", plusC(idC("x"), idC("x"))) f2 = fdC("quad", "x", appC(f1, appC(f1, idC("x")))) f3 = fdC("const5", "_", numC(5)) f4 = fdC("f4", "x", s2p2d("(if x 1 0)")) fun i(e): interp(e, mt-env) end i(plusC(numC(5), appC(f2, numC(3)))) is numV(17) i(multC(appC(f3, numC(3)), numC(4))) is numV(20) i(plusC(numC(10), appC(f3, numC(10)))) is numV(10 + 5) i(plusC(numC(10), appC(f1, plusC(numC(1), numC(2))))) is numV(10 + 3 + 3) i(plusC(numC(10), appC(f2, plusC(numC(1), numC(2))))) is numV(10 + 3 + 3 + 3 + 3) end
26.3.2 A Small Improvement
Do Now!
Is there any part of our interpreter definition that we never use?
| fdC(arg :: String, body :: ExprC) |
Do Now!
Do you see what else you need to change?
| fdC(_, _) => e |
26.3.3 Nesting Functions
inner-fun = fdC("x", plusC(idC("x"), idC("x"))) outer-fun = fdC("x", inner-fun)
fdC("x", fdC("x", plusC(idC("x"), idC("x"))))
fdC("x", plusC(idC("x"), idC("x")))
...
appC(fdC("x", fdC("y", plusC(idC("x"), idC("y")))), numC(4))
fdC("y", plusC(idC("x"), idC("y")))
26.3.4 Nested Functions and Substitution
appC(fdC("x", fdC("x", plusC(idC("x"), idC("x")))), numC(4))
fdC("x", plusC(idC("x"), idC("x")))
appC(fdC("x", fdC("y", plusC(idC("x"), idC("y")))), numC(4))
fdC("y", plusC(numC(4), idC("y")))
In other words, we’re again failing to faithfully capture what
substitution would have done. A function value needs to
remember the substitutions that have already been applied to
it. Because we’re representing substitutions using an environment, a
function value therefore needs to be bundled with an
environment. This resulting data structure is called a
closure.“Save the environment! Create a closure
today!”—
26.3.5 Updating Values
data Value: |
| numV(n :: Number) |
| boolV(b :: Boolean) |
| closV(f :: ExprC%(is-fdC), e :: Environment) |
end |
fun interp(e :: ExprC, nv :: Environment) -> Value: |
cases (ExprC) e: |
end |
end |
Do Now!
Write out these two cases.
| fdC(_, _) => closV(e, nv) |
| appC(f, a) => |
clos = interp(f, nv) |
arg-val = interp(a, nv) |
interp(clos.f.body, xtnd-env(bind(clos.f.arg, arg-val), clos.e)) |
Exercise
Observe that the argument to interp is clos.e rather than mt-env. Write a program that illustrates the difference.
This now computes the same answer we would have gotten through substitution.
Do Now!
If we now switch back to using substitution, will we encounter any problems?
Yes, we will. We’ve defined substitution to replace program text in other program text. Strictly speaking we can no longer do this, because Value terms cannot be contained inside ExprC ones. That is, substitution is predicated on the assumption that the type of answers is a form of syntax. It is actually possible to carry through a study of programming under this assumption, but we won’t take that path here.
26.3.6 Sugaring Over Anonymity
Now let’s get back to the idea of naming functions, which has evident value for program understanding. Observe that we do have a way of naming things: by passing them to functions, where they acquire a local name (that of the formal parameter). Anywhere within that function’s body, we can refer to that entity using the formal parameter name.
fun double(x): x + x end double(10)
double = lam(x): x + x end double(10)
(let ([double (lambda (x) (+ x x))]) (double 10))
fun something(): double = lam(x): x + x end double(10) end
(define (double x) (+ x x)) (define (quad x) (double (double x))) (quad 10)
(let ([double (lambda (x) (+ x x))]) (let ([quad (lambda (x) (double (double x)))]) (quad 10)))
(let ([quad (lambda (x) (double (double x)))]) (let ([double (lambda (x) (+ x x))]) (quad 10)))
26.4 Recursion and Non-Termination
Hopefully you can convince yourself that our pure expression
languages—
Do Now!
Construct a non-terminating program for that interpreter.
il = fdC("inf-loop", "x", appC("inf-loop", numC(0)))
interp(appC("inf-loop", numC(0)), [list: il])
Exercise
Precisely identify the generative recursion that enables this.
Do Now!
Why does this work? Why is this an infinite loop?
What’s happening here is actually somewhat subtle. The initial call to interp results in the interpreter finding a function and interpreting its body, which results in another call to interp: which finds the function and interprets its body, which results...and so on. If for some reason Pyret did not support recursion (which, historically, some languages did not!), then this would not work. Indeed, there is still something we are leaving to Pyret:
Do Now!
Does this program truly run for “ever” (meaning, as long as the computer is functioning properly), or does it run out of stack space?
Okay, that was easy. Now let’s consider our most recent interpreter. What can it do?
fun loop-forever(): loop-forever() end loop-forever()
loop-forever = lam(): loop-forever() end loop-forever()
(lam(loop-forever): loop-forever() end)(lam(): loop-forever() end)
Therefore, Pyret’s fun is clearly doing something more than just textual substitution: it is also “tying the loop” for recursive definitions through a hidden rec [Recursion and Cycles from Mutation].
Do Now!
Can we try anything else that might succeed?
little-omega = lam(x): x(x) end
omega = little-omega(little-omega)
Exercise
Why does this run forever? Consider using substitution to explain why.
(lam(x): x(x) end)(lam(x): x(x) end)
26.5 Functions and Predictability
We began [Adding Functions to the Language] with a language where at all application points, we knew exactly which function was going to be invoked (because we knew its name, and the name referred to one of a fixed global set). These are known as first-order functions. In contrast, we later moved to a language [Functions Anywhere] with first-class functions: those that had the same status as any other value in the language.
This transition gave us a great deal of new flexiblity. For instance, we saw [Sugaring Over Anonymity] that some seemingly necessary language features could instead be implemented just as syntactic sugar; indeed, with true first-class functions, we can define all of computation ([REF]). So what’s not to like?
The subtle problem is that whenever we increase our expressive power, we correspondingly weaken our predictive power. In particular, when confronted with a particular function application in a program, the question is, can we tell precisely which function is going to be invoked at this point? With first-order functions, yes; with higher-order functions, this is undecidable. Having this predictive power has many important consequences: a compiler can choose to inline (almost) every function application; a programming environment can give substantial help about which function is being called at that point; a security analyzer can definitively rule out known bad functions, thereby reducing the number of useless alerts it generates. Of course, with higher-order functions, all these operations are still sometimes possible; but they are not always possible, and how possible they are depends on the structure of the program and the cleverness of tools.
Exercise
With higher-order functions, why is determining the precise function at an application undecidable?
Exercise
Why does the above reference to inlining say “almost”?