6 Functional Abstraction

\(\newcommand{\la}{\lambda} \newcommand{\Ga}{\Gamma} \newcommand{\ra}{\rightarrow} \newcommand{\Ra}{\Rightarrow} \newcommand{\La}{\Leftarrow} \newcommand{\tl}{\triangleleft} \newcommand{\ir}[3]{\displaystyle\frac{#2}{#3}~{\textstyle #1}}\)

Abstraction is the process of finding similarities or common aspects, and forgetting unimportant differences. As humans, we do this all the time, as a means of coping with the world. It’s what lets us talk about "chairs" without having a specific chair in mind.

With Racket, we have been using abstraction already, each time we write a function. The "sum of squares" function abstracts away the differences between expressions such as (+ (* 3 3) (* 4 4)) and (+ (* 5 5) (* 2 2)). We instead focus on the similarity, the idea of squaring two different values and summing them, and capture that in the function body.

On a different level, we have seen many similarities between functions, and captured them in templates and design recipes. We can do more abstraction along these lines.

6.1 A first example

Consider the following two similar functions.

What sqr-all and increment-all have in common is their general structure. Where they differ is in the specific function applied to each element of the argument list (sqr for the first and add1 for the second) to create the corresponding element of the result list.

We could write one function map to do both these tasks if we could supply, as an argument to that function, the predicate to be used. Then we could just supply sqr as that argument in order to get the functionality of sqr-all, or we could supply add1 to do what increment-all does.

A function cannot be used as an argument in Beginning Student with List Abbreviations. However, it is permitted in Intermediate Student (ISL), the next language level, to which we now move. The feature was deliberately left out of the lower levels, because it doesn’t need to be used immediately. Omitting it lets DrRacket catch some common beginner errors and provide more meaningful error messages.

In Intermediate Student, here’s how we might write map, generalizing our two specific examples.

This definition contains the subexpression (f (first lst)). Here f is not the name of a predefined or user-defined function, as it has to be in BSL and BSL+. It is the name of a parameter. The rules for the "function part" of a function application have changed. We’ll be more precise about them soon.

We don’t actually have to write the definition of map, as it is a predefined function in ISL. Using it, we could give a concise definition of sqr-all.

(define (sqr-all lst) (map sqr lst))

Or we could simply replace all uses of sqr-all. For example, (sqr-all mylist) becomes (map sqr mylist). Choosing one approach or the other is a matter of style and readability.

map is an example of an abstract list function. We will soon see others. More generally, map is an example of a higher-order function, a function that consumes and/or produces functions.

What is the contract for map? First, we need to figure out how to write, in a contract, the type of an argument that is itself a function. What we can do is use the contract of that function as its type.

But this does not accurately reflect the relationships among the various Any types. For example, (map sqr (list "bad" "data")) is not a valid use of map, because sqr cannot be applied to a string. The contract should take this into account. To facilitate this, we introduce the idea of type variables, which can stand in for an unknown, arbitrary type the way an algebraic variable does for an unknown, arbitrary value. If we use the type variable X more than once in a contract, we mean that both those uses refer to the same type.

Let’s refine the contract of map using this idea. The bad example above tells us that the first argument function has to be applicable to a list element. So if the first argument function works when applied to type X, then everything in the second argument list must be of type X.

; map: (X -> Any) (Listof X) -> (Listof Any)  

But we can continue reasoning like this. Whatever appears in the result list is the result of applying the first argument function. So if the first argument function produces values of type Y, then the result list must contain values of type Y.

; map: (X -> Y) (Listof X) -> (Listof Y)

This is the most accurate contract for map, and it provides good guidance for the use of the function.

6.2 More functional abstraction

We saw this function in the previous chapter.

Here is a similar function.

Once again, what these two functions have in common is their general structure. Where they differ is in the specific predicate used to decide whether an item is removed from the answer or not. We can write one function to do both these tasks if we supply, as an argument to that function, the predicate to be used.

filter is also a predefined function in ISL. We can simplify the code a little.

Here is the contract for filter.

; filter: (X -> Boolean) (Listof X) -> (Listof X)

6.3 Functions are values

In BSL and BSL+, numbers are first-class values, but functions are not. In ISL, functions are first-class values. They can be arguments to function or produced by functions; they can be put into lists and structures. But functions are to be first-class values, we should be able to produce them while the program is being run.

As an analogy, consider the expression (* (+ 3 4) 5). Evaluating this expression produces the intermediate value 7, and the final value 35, neither of which appear in the expression, and neither of which have a name or identifier bound to them. We need a way of creating function values in a similar fashion.

The way to create function values is to use lambda.

(lambda (x) (* x x)) is the function which consumes a single argument and produces its square. It is behaviourally equivalent to the predefined function sqr. A lambda expression resembles a function definition, but the keyword define is replaced with lambda, and there is no function name (the function is anonymous). A definition is not an expression, and it can only appear at the top level of a program. A lambda expression can appear anywhere that an expression is expected. A lambda expression is a value.

lambda is not available in ISL. But it is available in the next language level, Intermediate Student with Lambda (ISL+), to which we now move. It seems strange to use a Greek letter for this language feature. The name comes from the lambda calculus, which was the first general model of computation. The lambda calculus was defined by the logician Alonzo Church in the 1930’s, and used by him to demonstrate the first uncomputable problem.

The lambda calculus has only lambda (function creation) and function application. It has nothing else – no numbers, Booleans, strings, conditionals, or structures. Yet it can express any computation that Racket can. Many functional programming languages (including Racket) can be viewed as the lambda calculus with features added to make it easier to express computation (without adding any theoretical power).

As a programming language construct, lambda was present in LISP in 1959, though its implementation was somewhat problematic (that was fixed when Scheme was defined in 1975). The feature has gradually been making its way into other languages. It was added to C++ in 2011, to Java in 2014, and even to Excel in 2021.

An immediate use of lambda is in creating function arguments for applications of map or filter. For example, (map (lambda (n) (* n n n)) mylist) produces a list of the cube of every number in mylist. (lambda (x) (not (equal? x 'apple))) is the function that produces false if it is applied to the symbol 'apple, and produces true otherwise. (filter (lambda (x) (not (equal? x 'apple))) mylist) is an expression that eats apples from mylist; it produces a list that has all values in mylist that are not 'apple.

6.4 Syntax and semantics of ISL+

We don’t have to make many changes to our earlier syntax and semantics to take into account these powerful new features. First, we introduce a grammar rule for lambda expressions.

Before, the first position in a function application had to be the name of a predefined or user-defined function.

We remove this rule and add a new one. The first position in an application is now an expression (computing the function to be applied).

When evaluating a function application, the expression in the first position must now be evaluated, just like the arguments. The rule for rewriting the application of a lambda value to arguments resembles the rule for application of a user-defined function.

((lambda (x1 ... xn) exp) v1 ... vn) => modexp

where modexp is exp with all occurrences of x1 replaced by v1, all occurrences of x2 replaced by v2, and so on.

We do not reduce expressions in the body of a lambda, just as we previously did not reduce expressions in the body of function definitions.

Before, there were two kinds of definitions:

Now, there is only one kind of definition, the first kind, which binds a name to a value. The second definition is rewritten to be like the first kind.

Here is the general rewrite rule.

(define (f x1 ... xn) body) \(\Rightarrow\) (define f (lambda (x1 ... xn) body))

We can now remove the rule for rewriting the application of a user-defined function. The rule we just added for application of a lambda expression suffices.

Here is a trace using the old rules:

(interest-earned 200)
\(\Rightarrow\) (* interest-rate 200)
\(\Rightarrow\) (* 3/100 200)
\(\Rightarrow\) 6

And a trace using the new rules:

(interest-earned 200)
\(\Rightarrow\) ((lambda (amount) (* interest-rate amount)) 200)
\(\Rightarrow\) (* interest-rate 200)
\(\Rightarrow\) (* 3/100 200)
\(\Rightarrow\) 6

Understanding traces like the second one is an important skill, but they can be less readable than traces like the first one. Sometimes we will use the name of a user-defined function as a synonym for its lambda value, just as we use empty instead of '() or true instead of #true.

lambda has uses far beyond what we have seen so far. Suppose during a computation, we want to specify some action to be performed one or more times in the future. Before knowing about lambda, we might build a data structure to hold a description of that action. To actually perform the action later on, we would need a helper function to consume that data structure and perform the action it described. Now, we can just describe the computation clearly using lambda, and simply apply the resulting function when needed in future. As a very simple example, consider the make-adder function, which consumes a number and produces a function that adds that number to its argument.

\(\Rightarrow\) (define make-adder (lambda (n) (lambda (x) (+ n x))))

(define p3 (make-adder 3))
\(\Rightarrow\) (define p3 ((lambda (n) (lambda (x) (+ n x))) 3))
\(\Rightarrow\) (define p3 (lambda (x) (+ 3 x)))

(p3 4)
\(\Rightarrow\) ((lambda (x) (+ 3 x)) 4)
\(\Rightarrow\) (+ 3 4)
\(\Rightarrow\) 7

What is the contract of make-adder?

; make-adder: number -> (number -> number)

For a more extended example of the practical use of lambda, let’s consider the general task of character translation in strings. Racket provides the function string->list to convert a string to a list of characters. This is the most effective way to work with strings, though typically structural recursion on these lists is not effective, and generative recursion needs to be used. In the example we are about to discuss, structural recursion works.

The function list->string converts a list of characters to a string. Racket’s notation for the character ‘a’ is #\a. The result of evaluating (string->list "test") is the list '(#\t #\e #\s #\t). This is unfortunately ugly, but the # notation is part of a more general way of specifying values in Racket, which we’ve already seen with #true and #false.

As an example of character translations in strings, we might want to convert every ’a’ in a string to a ’b’. The string "abracadabra" becomes "bbrbcbdbbrb". This doesn’t require functional abstraction. If you’d known about characters while working through the previous chapter, you could have written a function that does this particular character translation, and it would probably look a lot like this.

Our example translation can now be created with the expression
(list (is-char? #\a) (always #\b)).

The translate function will consume a list of translations and a string to be translated. For each character c in the string, it will create an result character by applying the action of the first translation on the list whose predicate is satisfied by c. If no predicate is satisfied by c, the result character is c. As an example of its use, suppose we have a string s, and we want a version of it where all letters are capitalized, and all numbers are “redacted” by replacing them with asterisks. char-alphabetic?, char-upcase, and char-numeric? are predefined functions we can make use of for the needed predicates and actions.

Here’s the implementation of the translate function, which uses two helper functions, each doing structural recursion on a list argument (one on a list of translations, the other on a list of characters).

Exercise 26: Write down the contract for trans-loc. \(\blacksquare\)

6.5 Local bindings and scope

Previously, we had two notions of scope, global and local.

A name bound by a top-level definition (as in the first line above) is in global scope, visible to code below. It can be shadowed by a use of the same name as a parameter, as in the second line. This introduces a new local scope for the the name, that is, the body of the function.

A use of lambda does something similar. But because lambda can occur anywhere an expression is expected, the situation is more complicated. Each use of lambda introduces a new local scope. Lambdas may be nested, and an inner lambda may reuse a parameter name that is used by an outer lambda.

(lambda (x) (lambda (x) (* x x)))

In this expression, the x in (* x x) refers to the parameter of the inner lambda. This expression creates a function that, when applied to an argument, ignores that argument and produces a function that squares its argument.

A use of lambda introduces new binding occurrences of the names of the parameters. The body of the lambda may contain bound occurrences of those names, referring to the binding occurrences of the parameters. Each binding occurrence may have several bound occurrences, but each bound occurrence corresponds to exactly one binding occurrence. The scope of a binding occurrence is the body of the lambda, except for places where the name is shadowed by a reuse.

We extend these ideas to top-level definitions (including old-style function definitions). To illustrate the usefulness of local scope, and to introduce Racket’s other constructs for local binding, we will discuss several implementations of a simple mathematical formula. Heron’s formula says that the area of a triangle with sides \(a, b, c\) is \(\sqrt{s(s-a)(s-b)(s-c)}\), where \(s=(a+b+c)/2\).
Our first implementation treats s as a function.

This is awkward, and the code is not very readable. If we compute s only once, and provide the result as an argument, that argument can be used several times without recomputation. The code gets a bit cleaner, also.

This helper function is only used once, and isn’t going to be used elsewhere. Now that we have lambda, we can use it to construct the helper function inside the body of t-area, and use it immediately.

This is closer to the mathematical definition. The only problems are the "visual noise" from using lambda, and the fact that the binding occurrence of s and the expression it is meant to be bound to are separated. Racket provides the let construct (in ISL and above) to make this use of lambda more readable.

As with cond, the convention is to use square brackets to improve readability. Here’s the general grammar rule for let expressions.

And here is the reduction rule, which simply translates a let expression into the corresponding immediate application of a lambda.

(let ([x1 e1] ... [xn en]) exp)
\(\Rightarrow\) ((lambda (x1 ... xn) exp) e1 ... en)

We discussed earlier how the substitution model did not really describe what happens when a Racket program is actually run; it only accurately predicted the effect. But in this case, it is closer to reality than in other cases. It should be no surprise to you that some predefined Racket functions, such as map, are implemented in Racket itself. A small number of core functions are implemented in machine language (which we will discuss in part 2 of FICS).

But this idea also extends to forms which use different syntax. Racket, like Scheme and LISP, allows syntactic extension. A programmer can define new syntax using Racket constructs. A small number of core forms are implemented using other methods, and then derived forms can be written by the programmer using a feature known as macros. lambda is a core form, but let is a derived form, and the macro which implements let causes the program to be rewritten as described above.

Because the substitution model is a rewriting model, this can be confusing. You should keep thinking of the substitution model as a mathematical model whose purpose is to predict what happens when a Racket program is run. But when a program is run in DrRacket, there is an initial phase called macro expansion in which the program is actually rewritten to use only core forms. This is followed by a computation phase where the program is run using techniques that are more efficient than a direct implementation of the substitution model would be.

The macro implementing let is like the code implementing map, in that if it were not predefined, the programmer could write it themselves. Macros are not available in the teaching languages, so it is a little premature to discuss them. Furthermore, the situation is even more complicated, because macros can produce other macros, so the rewriting and computation phases are repeated until all macros have been expanded. Macros are an important tool in full Racket, and play a major role in the implementation of the teaching languages (adding additional error reporting that is either more beginner-friendly or covers situations that are valid in full Racket but not in a teaching language). It is worth a slight detour to look briefly at them.

You should understand that most programming languages do not have a feature like macros, or if they do, it is not as sophisticated and powerful as in Racket. Most programming languages have a fixed syntax. If a language feature is not present, you do without, or lobby for its inclusion in the next release. But in Racket, you can often implement it yourself. Here is how the rewrite rule for let could be added to a Racket program using a macro.

I won’t explain this fully, but here is a brief overview. define-syntax-rule is a way of creating a macro that can be used in the case where there is a single rewriting rule. It specifies a pattern that a use of let is matched against, with pattern variables that are bound to parts of the let expression. Those pattern variables can be used in the "answer", which specifies where the matched parts appear in the rewritten expression. The ellipsis (...) is used to indicate repetition (it really is part of the code, not something missing). More sophisticated macro creation forms allow multiple rewriting rules (as needed for cond, which is a macro expanding to uses of the primitive form if) and ways of manipulating subexpressions.

If this has piqued your interest, you can read more the Macros section of the Racket Guide in the Racket documentation, or wait until later in this flânerie. To summarize this brief diversion, macros allow the programmer to create new syntax in a program. This makes Racket a laboratory for language design and implementation.

The let construct allows one to define several bindings, but none of the names bound can be used in any of the right-hand-side expressions. This makes defining local recursive functions difficult. The more general local construct allows an arbitrary number of local definitions whose scope is the body expression. It also uses the keyword define, just as with top-level definitions, for readability.

Here’s the grammar rule for local:

The complete description of the reduction rule for local is the most complicated semantic rule we will see.

(local [(define x1 e1) ...] body) \(\Rightarrow\) ???

The identifier x1 is replaced by a fresh identifier x1new everywhere in the local expression. This is repeated with the rest of the definitions. The rewritten definitions are lifted out to the top level. When no local definitions remain, the following rule applies.

(local [] body) \(\Rightarrow\) body

Here’s an example of rewriting a local expression using these rules.

We know how it goes after this.

6.6 Still more functional abstraction

Let’s try to generalize from the template for structural recursion on a list.

We replace the first ellipsis by a base value, and replace the rest of the ellipses by some expression which combines the value of (first lst) and the result of the recursive application on (rest lst).

This suggests passing the base value and a function implementing the combining expression as parameters to an abstract list function.

foldr is a predefined function in ISL+. The name is short for "fold right", because the function can be viewed as folding a list using the provided combine function, starting from the right-hand end of the list. A generic trace of foldr might look something like this:

(foldr f 0 (list 3 6 5)) \(\Rightarrow^*\)
(f 3 (foldr f 0 (list 6 5))) \(\Rightarrow^*\)
(f 3 (f 6 (foldr f 0 (list 5)))) \(\Rightarrow^*\)
(f 3 (f 6 (f 5 (foldr f 0 empty)))) \(\Rightarrow^*\)
(f 3 (f 6 (f 5 0))) \(\Rightarrow^*\) ...

A real trace would substitute for f first. Intuitively, (foldr f b (list x1 x2 ... xn)) computes (f x1 (f x2 (... (f xn b) ...))).

As another example, (foldr + 0 (list x1 x2 ... xn)) computes (+ x1 (+ x2 (... (+ xn 0) ...))). So we can sum up a list of numbers like this:

(define (sum-list lst) (foldr + 0 lst))

Exercise 27: Make use of type variables to write down the contract for foldr. \(\blacksquare\)

The function provided to foldr consumes two parameters: one is an element on the list which is an argument to foldr, and one is the result of reducing the rest of the list. Sometimes one of those arguments should be ignored, as in the case of using foldr to compute the length of a list.

(define (len lst) (foldr (lambda (x y) (add1 y)) 0 lst))

The function provided to foldr, (lambda (x y) (add1 y)), ignores its first argument. Its second argument represents the reduction of the rest of the list (in this case the length of the rest of the list, to which 1 must be added).

Since foldr is an abstraction of structural recursion on lists, we should be able to use it to carry out the same computation as sqr-all.

We need to define a function (lambda (x y) ...) where x is the first element of the list and y is the result of the recursive application on the rest of the list. sqr-all takes this element, squares it, and conses it onto the result of the recursive application. Thus the function we need is (lambda (x y) (cons (sqr x) y)).

Since we generalized sqr-all to map, this suggests that we might be able to use foldr
to define map.

Clearly empty is the base value, and the function provided to foldr is something involving cons and f. In particular, the function provided to foldr must apply f to its first argument, then cons the result onto its second argument (the reduced rest of the list).

Exercise 28: Implement filter using foldr. Make sure you have done exercise 27 before working with foldr. \(\blacksquare\)

Exercise 29:
What is (foldr cons empty mylist)?
What is (foldr cons mylist1 mylist2)? \(\blacksquare\)

foldr is universal for structural recursion on a single list parameter. Anything that can be done with the list template can be done using foldr, without explicit recursion. Does that mean that the list template is obsolete?

No. Experienced Racket programmers still use the list template, for reasons of readability and maintainability. Abstract list functions should be used judiciously, to replace relatively simple uses of recursion. In practice, map and filter are used more often. foldr is used mostly in relatively short, simple expressions, such as the one summing a list of numbers.

Exercise 30: Use the predefined abstract list functions map, filter, and foldr to implement unique-left and unique-right from Exercise 14 and 15, but without helper functions or explicit recursion. You can and should use lambda. If you did not do the earlier exercises, or did not use pure structural recursion, you will find this task easier if you go back and do them properly first. \(\blacksquare\)

Exercise 31: Use the same approach as in the previous exercise to implement cross, which consumes two lists of distinct values, and produces a list of two-element lists consisting of one value from the first list and one value from the second list. For example, (cross '(a b c) '(1 2)) should evaluate to
'((a 1) (a 2) (b 1) (b 2) (c 1) (c 2)).
The order here is important. \(\blacksquare\)

Exercise 32: In this exercise, you will make use of a new higher-order function. The shortest and clearest description of the unfoldr function is its code.

Your first task is to understand what unfoldr does. Note that unfoldr does not use structural recursion. Write a contract for the function. Try to create a sample application and trace it by hand, on paper, to see what it does.

Once you have a sense of what unfoldr can do, copy its code into DrRacket and use it to implement the following Racket functions without helper functions or explicit recursion.

6.7 Simplifying Racket

I said above that the lambda calculus was as powerful as any other programming language. In this section, which should be considered optional reading, we will gradually remove features from the set we have defined so far, until we are left with just the lambda calculus expressed in Racket syntax.

We start with an interesting simulation of structures, which demonstrates the power of lambda. Suppose we want to simulate the effect of the following statement.

(define-struct point (x y))

In the following definition, a point is actually a function that responds to symbolic "messages" given to it as arguments.

(define (my-make-point x y)

(lambda (msg)

(cond

[(symbol=? msg 'x) x]

[(symbol=? msg 'y) y])))

(define (my-point-x p) (p 'x))

(define (my-point-y p) (p 'y))

Exercise 33: Trace the following program and verify that the expressions evaluate to their expected results.

(define p1 (my-make-point 3 4))
(my-point-x p1) \(\Rightarrow\) 3
(my-point-y p1) \(\Rightarrow\) 4
\(\blacksquare\)

Exercise 34: There’s no obvious way to define the equivalent of the point? type predicate. Can you see a way of achieving this (by possibly complicating the simulation)? \(\blacksquare\)

The simulation above suggests that lambda can be used to simplify Racket by getting rid of structures. Obviously, this takes more code, and is not as expressive as structures are. But if we were just interested in what was possible to express, rather than the degree of expressivity, what other simplifications might we make?

Clearly, we can replace cond with nested if expressions. But we can go much further than this, and simulate if and Booleans using lambda. The constants #true and #false will be:

(lambda (x y) x)

(lambda (x y) y)

These are functions of two arguments, each of which ignores one argument and produces the other. This choice seems ill-motivated until we see what we can do to replace if. The idea is that the test expression in the if should evaluate to true or false, or more precisely our replacements for them. (For convenience in the exposition, we will continue to refer to things we have replaced or simulated, with the understanding that we mean the new constructs.)

We replace (if b c d), where b is the test expression, c is the expression to be evaluated if that is true, and d the expression to be evaluated if that is false, with:

((b (lambda (y) c)

(lambda (y) d))

0)

Note that this substitution (like most of what we are talking about in this section) has to be a textual replacement, like a macro would cause. if cannot be written as a function, because a function evaluates all of its arguments, but if evaluates exactly one of expressions c and d.

If b evaluates to one of the two argument-choosing functions, then that will be applied to the lambda-wrapped c and d (the point of the lambda-wrapping is so that c and d will not be evaluated before b is applied). So the right one of those will be selected, and then the wrapping will be taken off by applying what is selected to the dummy argument 0 (thus allowing the chosen expression to be evaluated).

Next, we get rid of lists. As we saw earlier, cons is a special kind of two-element structure. We use the idea of our simulation of structures above, but we simplify it by using the Boolean values instead of the two symbols.

We replace cons with:

(lambda (f r)

(lambda (b)

(if b f r)))

Then first and rest are:

(lambda (p) (p true))

(lambda (p) (p false))

This is really just a variation on the structure simulation that we started with.

We replace empty by (lambda (x) true). Once again, this seems ill-motivated, until we look at the definition of empty?.

(lambda (p)

(p (lambda (f r)

(lambda (x) false))))

Clearly (empty? empty) will yield true. What happens when empty? is applied to (cons y z)?

Looking at the definition of cons, we see that (cons y z) looks like (lambda (b) (if b y z)). But we also replaced if with a construct that applies b to lambda-wrapped y and z. So if b is (lambda (f r) (lambda (x) false)), then both of those are ignored in favour of a lambda-wrapped false, which is then applied to 0 to produce false. So our replacement for empty? works.

Continuing, we observe that strings and symbols can be replaced by lists of numbers. More interestingly, we can get rid of numbers entirely. Natural numbers can be replaced by lists of the same length. sub1 becomes rest, add1 becomes a use of cons (it doesn’t matter what the lists contain), zero? becomes empty?, and so on. If we have natural numbers, it is simple to construct integers, exact rational numbers, and other numeric forms.

Next, we get rid of named user-defined functions. For non-recursive functions, this is easy. We just replace each use of the name with the lambda expression it is bound to. Eliminating named recursive functions takes more thought. We can illustrate the problem by looking at a simple recursive function, such as the one below that computes the factorial of its natural-number argument.

(define (fact n)

(if (zero? n)

1

(* n (fact (sub1 n)))))

It’s not obvious how to write this using a lambda expression, because the name of the function is used in its own body expression.

(lambda (n)

(if (zero? n)

1

(* n (r (sub1 n)))))

But what is r? We don’t know what to put in at that point, so let’s make this into a function which consumes an appropriate r. We’ll call it pfact, for "proto-factorial" (meaning "early form of factorial"). Then we’ll try supplying a suitable argument to pfact... like pfact.

(define (pfact r)

(lambda (n)

(if (zero? n)

1

(* n (r (sub1 n))))))

(define fact (pfact pfact))

This doesn’t quite work. The problem is that what we want to substitute for r is fact. That means that we should define fact as (pfact fact). But of course we can’t write a definition like this.

However, the idea to use pfact as the argument is not a bad one. It’s just that the body of pfact does the wrong thing with r. Instead of applying pfact to (sub1 n), the code needs to apply (pfact pfact). So we change the application of r to be an application of (r r).

(define (pfact r)

(lambda (n)

(if (zero? n)

1

(* n ((r r) (sub1 n))))))

(define fact (pfact pfact))

And this works. Furthermore, because there is no explicit recursion, we can rewrite the first definition in the form (define pfact (lambda (r) ...)) and then get rid of the names pfact and fact entirely. This technique can be generalized to write one function, usually called the Y combinator, that consumes something written like the first version of pfact and produces a proper factorial function.

Of course, we have to add more parentheses to applications.
((lambda (x y z) e) p q r) becomes
((((lambda (x) (lambda (y) (lambda (z) e))) p) q) r).

What is left? Only variables, lambda, and function application. And yet, because we have shown how to simulate everything we eliminated, this has as much power as Racket.

This is the lambda calculus. It is usually written in a more condensed form, which has three grammar rules and one reduction rule.

\[\begin{array}{rcl} E &=& (\lambda V~.~E)\\ &|& (E~E)\\ &|& V~~ \mbox{(variables)} \end{array}\]

Here is the reduction rule: \[((\lambda V.F)~G) \rightarrow F[V\leftarrow G]\]

The notation on the right hand side means "substitute \(G\) for \(V\) everywhere in \(G\)", and this requires a careful recursive definition. But intuitively it should be clear.

We won’t be making further use of the lambda calculus here, but it plays a significant and surprising role in my flânerie Logic and Computation Intertwined (LACI).