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. [REF]
One of the things we stayed coy about when introducing functions (Adding Functions to the Language) is exactly where functions go. We may have suggested we’re following the model of an idealized DrRacket, 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, 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 ([define (f x) (* x 3)] 4))
Let’s first define the core language to include function definitions:
(define-type ExprC [numC (n : number)] [idC (s : symbol)] <app-type> [plusC (l : ExprC) (r : ExprC)] [multC (l : ExprC) (r : ExprC)] <fun-type>)
For now, we’ll simply copy function definitions into the expression language. We’re free to change this if necessary as we go along, but for now it at least allows us to reuse our existing test cases.
[fdC (name : symbol) (arg : symbol) (body : ExprC)]
We might consider more refined datatypes that split function definitions apart from other kinds of expressions. This amounts to trying to classify different kinds of expressions, which we will return to when we study types. [REF]
[appC (fun : ExprC) (arg : ExprC)]
With this definition of application, we no longer have to look up functions by name, so the interpreter can get rid of the list of function definitions. If we need it we can restore it later, but for now let’s just explore what happens with function definitions are written at the point of application: so-called immediate functions.
[fdC (n a b) expr]
What happens when you add this?
We’ve alluded periodically to the answers computed by the interpreter, but never bothered gracing these with their own type. It’s time to do so now.
(define-type Value [numV (n : number)] [funV (name : symbol) (arg : symbol) (body : ExprC)])
We’re using the suffix of V to stand for values, i.e., the result of evaluation. The pieces of a funV will be precisely those of a fdC: the latter is input, the former is output. By keeping them distinct we allow each one to evolve independently as needed.
Now we must rewrite the interpreter. Let’s start with its type:
(define (interp [expr : ExprC] [env : Env]) : Value (type-case ExprC expr <interp-body-hof>))
This change naturally forces corresponding type changes to the Binding datatype and to lookup.
Modify Binding and lookup, appropriately.
Clearly, numeric answers need to be wrapped in the appropriate numeric answer constructor. Identifier lookup is unchanged. We have to slightly modify addition and multiplication to deal with the fact that the interpreter returns Values, not numbers:
[plusC (l r) (num+ (interp l env) (interp r env))] [multC (l r) (num* (interp l env) (interp r env))]
(define (num+ [l : Value] [r : Value]) : Value (cond [(and (numV? l) (numV? r)) (numV (+ (numV-n l) (numV-n r)))] [else (error 'num+ "one argument was not a number")]))
There are two more cases to cover. One is function definitions. We’ve already agreed these will be their own kind of value:
[fdC (n a b) (funV n a b)]
That leaves one case, application. Though we no longer need to look up the function definition, we’ll leave the code structured as similarly as possible:
[appC (f a) (local ([define fd f]) (interp (fdC-body fd) (extend-env (bind (fdC-arg fd) (interp a env)) mt-env)))]
In place of the lookup, we reference f which is the function definition, sitting right there. Note that, because any expression can be in the function definition position, we really ought to harden the code to check that it is indeed a function.
What does is mean? That is, do we want to check that the function definition position is syntactically a function definition (fdC), or only that it evaluates to one (funV)? Is there a difference, i.e., can you write a program that satisfies one condition but not the other?
We can check that it syntactically is an fdC and, if it isn’t reject it as an error.
We can evaluate it, and check that the resulting value is a function (and signal an error otherwise).
[appC (f a) (local ([define fd (interp f env)]) (interp (funV-body fd) (extend-env (bind (funV-arg fd) (interp a env)) mt-env)))]
Modify the code to perform both versions of this check.
(test (interp (plusC (numC 10) (appC (fdC 'const5 '_ (numC 5)) (numC 10))) mt-env) (numV 15)) (test/exn (interp (appC (fdC 'f1 'x (appC (fdC 'f2 'y (plusC (idC 'x) (idC 'y))) (numC 4))) (numC 3)) mt-env) "name not found")
The body of a function definition is an arbitrary expression. A function definition is itself an expression. That means a function definition can contain a...function definition. For instance:
(fdC 'f1 'x (fdC 'f2 'x (plusC (idC 'x) (idC 'x))))
(funV 'f1 'x (fdC 'f2 'x (plusC (idC 'x) (idC 'x))))
(appC <nested-fdC> (numC 4))
(funV 'f2 'x (plusC (idC 'x) (idC 'x)))
(appC (fdC 'f1 'x (fdC 'f2 'y (plusC (idC 'x) (idC 'y)))) (numC 4))
(funV 'f2 'y (plusC (idC 'x) (idC 'y)))
(appC (appC (fdC 'f1 'x (fdC 'f2 'y (plusC (idC 'x) (idC 'y)))) (numC 4)) (numC 5))
((define (f1 x) ((define (f2 y) (+ x y)) 4)) 5)
((define (f2 y) (+ 5 y)) 4)
In other words, we’re again failing to faithfully capture what substitution would have done.On the other hand, observe that with substitution, as we’ve defined it, we would be replacing x with (numV 4), resulting in a function body of (plusC (numV 5) (idC ’y)), which does not type. 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 even very advanced programming constructs under this assumption, but we won’t take that path here. 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.
While we’re at it, observe that the appC case above uses funV-arg and funV-body, but not funV-name. Come to think of it, why did a function need a name? so that we could find it. But if we’re using the interpreter to find the function for us, then there’s nothing to find and fetch. Thus the name is merely descriptive, and might as well be a comment. In other words, a function no more needs a name than any other immediate constant: we don’t name every use of 3, for instance, so why should we name every use of a function? A function is inherently anonymous, and we should separate its definition from its naming.
(But, you might say, this argument only makes sense if functions are always written in-place. What if we want to put them somewhere else? Won’t they need names then? They will, and we’ll return to this (Sugaring Over Anonymity).)
We need to change our representation of values to record closures rather than raw function text:
(define-type Value [numV (n : number)] [closV (arg : symbol) (body : ExprC) (env : Env)])
While we’re at it, we might as well alter our syntax for defining functions to drop the useless name. This construct is historically called a lambda:
[lamC (arg : symbol) (body : ExprC)]
When encountering a function definition, the interpreter must now
remember to save the substitutions that have been applied so
far:“Save the environment! Create a closure today!”
[lamC (a b) (closV a b env)]
This saved set, not the empty environment, must be used when applying a function:
[appC (f a) (local ([define f-value (interp f env)]) (interp (closV-body f-value) (extend-env (bind (closV-arg f-value) (interp a env)) (closV-env f-value))))]
[appC (f a) (local ([define f-value (interp f env)]) (interp (closV-body f-value) (extend-env (bind (closV-arg f-value) (interp a env)) env)))]
What happens if we extend the dynamic environment instead?
In retrospect, it becomes even more clear why we interpreted the body of a function in the empty environment. When a function is defined at the top-level, it is not “closed over” any identifiers. Therefore, our previous function applications have been special cases of this form of application.
(lambda (f) (lambda (x) (f 10)))
(lambda (x) ((lambda (y) (+ x y)) 10))
(lambda (f1) (lambda (x1) (f1 10)))
(lambda (y1) (+ x y1))
(lambda (x1) ((lambda (y1) (+ x y1)) 10))
But one moment. What happens if we try the same example in our environment-based interpreter?
Try it out.
Observe that it works correctly: it reports an unbound identifier error. Environments automatically implement capture-free substitution!
In what way does using an environment avoid the capture problem of substitution?
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.
(define (double x) (+ x x)) (double 10)
(define double (lambda (x) (+ x x))) (double 10)
((lambda (double) (double 10)) (lambda (x) (+ x x)))
(let ([double (lambda (x) (+ x x))]) (double 10))
(define (double x) (+ x x)) (define (quadruple x) (double (double x))) (quadruple 10)
(let ([double (lambda (x) (+ x x))]) (let ([quadruple (lambda (x) (double (double x)))]) (quadruple 10)))
(let ([quadruple (lambda (x) (double (double x)))]) (let ([double (lambda (x) (+ x x))]) (quadruple 10)))
(define (loop-forever x) (loop-forever x)) (loop-forever 10)
(let ([loop-forever (lambda (x) (loop-forever x))]) (loop-forever 10))
((lambda (loop-forever) (loop-forever 10)) (lambda (x) (loop-forever x)))
This is another feature we get “for free” from the top-level. To eliminate this magical force, we need to understand recursion explicitly, which we will do soon [REF].