5 Adding Functions to the Language

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.

5.1 Defining Data Representations

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:

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 body—i.e., the identifiers with the same name as the formal parameter—with that value.Observe that we are being coy about a few issues: what kind of “value” [REF] and when to replace [REF]. To simplify this process of search-and-replace, we might as well use the same datatype to represent both. We’ve already chosen symbols to represent formal parameters, so:

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:

identifying which function to apply, and providing its argument.

5.2 Growing the Interpreter

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:

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.

5.3 Substitution

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:

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.

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?

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:

5.4 The Interpreter, Resumed

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

Tempting, but wrong.

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:

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.

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—here, a positive connotation) before the interpreter ever sees them. As a result, there is only one possible response given an identifier:

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))])]))

5.5 Oh Wait, There’s More!

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 expression—(+ (+ 1 2) (+ 1 2))—for interpretation. Is this necessarily what we want?

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

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—and has some variations. For now, we will actually prefer the eager semantics, because this is what most mainstream languages adopt. Later [REF], we will return to talking about the lazy application semantics and its implications.