Let’s start turning this into a real programming language. We could add intermediate features such as conditionals, but to do almost anything interesting we’re going to need functions or their moral equivalent, so let’s get to it.
Add conditionals to your language. You can either add boolean datatypes or, if you want to do something quicker, add a conditional that treats 0 as false and everything else as true.
What are the important test cases you should write?
A set of definitions suggests no ordering, which means, presumably, any definition can refer to any other. That’s what I intend here, but when you are designing your own language, be sure to think about this.
(define (double x) (+ x x)) (define (quadruple x) (double (double x))) (define (const5 _) 5)
When a function has multiple arguments, what simple but important criterion governs the names of those arguments?
What are the parts of a function definition? It has a name (above, double, quadruple, and const5), which we’ll represent as a symbol (’double, etc.); its formal parameter or argument has a name (e.g., x), which too we can model as a symbol (’x); and it has a body. We’ll determine the body’s representation in stages, but let’s start to lay out a datatype for function definitions:
(define-type FunDefC [fdC (name : symbol) (arg : symbol) (body : ExprC)])
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.I promise we’ll return to this issue of nomenclature later [REF].
Finally, let’s look at the body of quadruple. 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. These are uses. 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.
Let’s commit all this to a crisp datatype. Clearly we’re extending what we had before (because we still want all of arithmetic). We’ll give a new name to our datatype to signify that it’s growing up:
Identifiers are closely related to formal parameters. When we apply a
function by giving it a value for its parameter, we are in effect
asking it to replace all instances of that formal parameter in the
[idC (s : symbol)]
Finally, applications. They have two parts: the function’s name, and its argument. We’ve already agreed that the argument can be any full-fledged expression (including identifiers and other applications). As for the function name, it again makes sense to use the same datatype as we did when giving the function its name in a function definition. Thus:
[appC (fun : symbol) (arg : ExprC)]
identifying which function to apply, and providing its argument.
(fdC ’double ’x (plusC (idC ’x) (idC ’x)))
(fdC ’quadruple ’x (appC ’double (appC ’double (idC ’x))))
(fdC ’const5 ’_ (numC 5))
Look out! Did you notice that we spoke of a set of function definitions, but chose a list representation? That means we’re using an ordered collection of data to represent an unordered entity. At the very least, then, when testing, we should use any and all permutations of definitions to ensure we haven’t subtly built in a dependence on the order.
Now we’re ready to tackle the interpreter proper. First, let’s remind ourselves of what it needs to consume. Previously, it consumed only an expression to evaluate. Now it also needs to take a list of function definitions:
(define (interp [e : ExprC] [fds : (listof FunDefC)]) : number <interp-body>)
Let’s revisit our old interpreter (A First Look at Interpretation). In the case of numbers, clearly we still return the number as the answer. In the addition and multiplication case, we still need to recur (because the sub-expressions might be complex), but which set of function definitions do we use? Because the act of evaluating an expression neither adds nor removes function definitions, the set of definitions remains the same, and should just be passed along unchanged in the recursive calls.
(type-case ExprC e [numC (n) n] <idC-interp-case> <appC-interp-case> [plusC (l r) (+ (interp l fds) (interp r fds))] [multC (l r) (* (interp l fds) (interp r fds))])
; get-fundef : symbol * (listof FunDefC) -> FunDefC
Substitution is the act of replacing a name (in this case, that of the formal parameter) in an expression (in this case, the body of the function) with another expression (in this case, the actual parameter). Let’s define its type:
; subst : ExprC * symbol * ExprC -> ExprC
It helps to also give its parameters informative names:
(define (subst [what : ExprC] [for : symbol] [in : ExprC]) : ExprC <subst-body>)
The first argument is what we want to replace the name with; the second is for what name we want to perform substitution; and the third is in which expression we want to do it.
Suppose we want to substitute 3 for the identifier x in the bodies of the three example functions above. What should it produce?
A common mistake is to assume that the result of substituting, e.g., 3 for x in double is (define (double x) (+ 3 3)). 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 remains for evaluation. Examine how substitution is used to notice the type error that would result from returning a function definition.
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 haven’t seen an example with a different identifier but you’ve guessed what should happen: it stays unchanged. 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?
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 [REF].
For now, we will take a pragmatic viewpoint. Because expressions evaluate to numbers, that means a function name could turn into a number. However, numbers cannot name functions, only symbols can. 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.)
Now we’ve made all our decisions, and we can provide the body code:
(type-case ExprC in [numC (n) in] [idC (s) (cond [(symbol=? s for) what] [else in])] [appC (f a) (appC f (subst what for a))] [plusC (l r) (plusC (subst what for l) (subst what for r))] [multC (l r) (multC (subst what for l) (subst what for r))])
Observe that, whereas in the numC case the interpreter returned n, substitution returns in (i.e., the original expression, equivalent at that point to writing (numC n). Why?
Phew! Now that we’ve completed the definition of substitution (or so we think), let’s complete the interpreter. Substitution was a heavyweight step, but it also does much of the work involved in applying a function. It is tempting to write
[appC (f a) (local ([define fd (get-fundef f fds)]) (subst a (fdC-arg fd) (fdC-body fd)))]
Tempting, but wrong.
Do you see why?
Reason from the types. What does the interpreter return? Numbers. What does substitution return? Oh, that’s right, expressions! For instance, when we substituted in the body of double, we got back the representation of (+ 5 5). This is not a valid answer for the interpreter. Instead, it must be reduced to an answer. That, of course, is precisely what the interpreter does:
[appC (f a) (local ([define fd (get-fundef f fds)]) (interp (subst a (fdC-arg fd) (fdC-body fd)) 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.
Work through some examples to understand what the interpreter should do in the identifier case.
(define (double x) (+ x y))
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.
In other words, the interpreter should never confront an identifier.
All identifiers ought to be parameters that have already been
substituted (known as bound identifiers—
[idC (_) (error 'interp "shouldn't get here")]
And that’s it!
Finally, to complete our interpreter, we should define get-fundef:
(define (get-fundef [n : symbol] [fds : (listof FunDefC)]) : FunDefC (cond [(empty? fds) (error 'get-fundef "reference to undefined function")] [(cons? fds) (cond [(equal? n (fdC-name (first fds))) (first fds)] [else (get-fundef n (rest fds))])]))
Earlier, we gave the following type to subst:
; subst : ExprC * symbol * ExprC -> ExprC
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
When you learned algebra in school, you may have been taught to do this differently: first reduce the argument to an answer (in this case, 3), then substitute the answer for the parameter. This notion of substitution might have the following type instead:
; subst : number * symbol * ExprC -> ExprC
In fact, we don’t even have substitution quite right! The version of substitution we have doesn’t scale past this language due to a subtle problem known as “name capture”. Fixing substitution is complex, subtle, and an exciting intellectual endeavor, but it’s not the direction I want to go in here. We’ll instead sidestep this problem in this book. If you’re interested, however, read about the lambda calculus, which provides the tools for defining substitution correctly.
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—