## Programming-Language Theory Explained for the Working Programmer: Principles of Programming Languages

Programming languages come in many sizes and flavors. Working programmers have been exposed to a few of them and might wonder: What is the essence of programming languages? In this article, we explore this question, but, unlike most presentations on the topic, we avoid mathematical notation and jargon. We start with a small program and remove one abstraction at a time, until we reach the core of what make programming languages work. The whole discussion is driven by executable code, making it approachable to all programmers.

Besides satisfying curiosity, this article introduces programming techniques that are generally applicable in everyday programming. And, for people starting in programming-language design and analysis, this article introduces a minimal programming language core from which to build.

### Starting Point§

Consider the following program:

Racket

```
(define (sum-up-to number)
(if (zero? number)
0
(+ number (sum-up-to (sub1 number)))))
(sum-up-to 5)
```

Ruby

```
def sum_up_to number
if number.zero?
0
else
number + sum_up_to(number - 1)
end
end
sum_up_to 5
```

Java

```
public class Main {
public static int sumUpTo(int number) {
if (number == 0) {
return 0;
} else {
return number + sumUpTo(number - 1);
}
}
public static void main(String[] args) {
System.out.println(sumUpTo(5));
}
}
```

This program defines a function that sums integers from zero up to a given number, then calls this function with `5`

, outputting `15`

. What are the essential features in programming languages that allow this program to be written? To address this question, we first have to consider what *is* an essential feature.

Suppose one wants to write an application that tracks information about bicycle trips. If one could find a programming language that comes with native constructs for distances, weather conditions and so on, then that would be a perfect fit. But programming languages generally do not have these features, so one has to use numbers, functions, lists, records, objects and other simpler features to *encode* the necessary functionality.

Bicycle-trip information is not an essential feature of programming languages, that is why they do not have it. But that is not a problem, because the key observation is that *any feature a language does not have, we can encode in terms of simpler features*. Most features included in most programming languages are non-essential—like bicycle-trip tracking would be—they exist solely for convenience. Not having a feature makes the language simpler, having it makes it more convenient. Our goal in this article is to explore this simplicity–convenience spectrum, removing one feature at a time, in the direction of simplicity. When we can no longer *encode features away* without breaking the program, what remain are the *essential features*—we will then have reached the essence of programming languages.

It is important to note that simplicity is not the same as easiness. As we advance, programs get simpler, because they use fewer features, but they also become more difficult to understand. Think of the difference between programs in Ruby and C that perform the same task: while C is a simpler language, programs in it tend to be more difficult to read.

### Numbers§

For convenience, here is the initial program again:

```
(define (sum-up-to number)
(if (zero? number)
0
(+ number (sum-up-to (sub1 number)))))
(sum-up-to 5) ;; => 15
```

The first features we remove via encoding are numbers and operations on them. There many different ways to rewrite the program above without numbers. For example, one could use strings to represent numbers, redefining the operations on them accordingly:

```
(define (zero? number)
(equal? "0" number))
(define (sub1 number)
___)
(define (+ operand-left operand-right)
___)
(define (sum-up-to number)
(if (zero? number)
"0"
(+ number (sum-up-to (sub1 number)))))
(sum-up-to "5")
```

Alternatively, we could encode numbers with strings not using their string representation, but the string length. In this encoding, the contents of the strings representing numbers would be irrelevant, only their length would be meaningful. For example, `0`

would become `""`

, `1`

would become `"☺"`

, `5`

would become `"☺☺☺☺☺"`

, and so on. The running example would look like the following in this encoding:

```
(define (zero? number)
(equal? "" number))
(define (sub1 number)
___)
(define (+ operand-left operand-right)
(string-append operand-left operand-right))
(define (sum-up-to number)
(if (zero? number)
""
(+ number (sum-up-to (sub1 number)))))
(sum-up-to "☺☺☺☺☺")
```

On a related idea, we could encode numbers as list lengths. Again, the contents of the lists would be irrelevant, only their length would be meaningful:

```
(define (zero? number)
(equal? '() number))
(define (sub1 number)
(if (zero? number)
'()
(rest number)))
(define (+ operand-left operand-right)
(append operand-left operand-right))
(define (sum-up-to number)
(if (zero? number)
'()
(+ number (sum-up-to (sub1 number)))))
(sum-up-to '(☺ ☺ ☺ ☺ ☺))
;; => '(☺ ☺ ☺ ☺ ☺ ☺ ☺ ☺ ☺ ☺ ☺ ☺ ☺ ☺ ☺)
```

Some encodings are more convenient than others. For example, it is more difficult to implement addition in the first encoding presented above than in the other two. The first encoding uses the string representation of numbers, so implementing addition in it amounts to recreating the addition algorithm taught in elementary school, including addition tables, carries and so on. But in the other two encodings, addition is just appending (either strings or lists), which is easy to implement.

We are not seeking easiness, though. So, from all the possible encodings, we choose one that is unnatural and inconvenient, but interesting: we encode numbers using *functions*. Each number is a function of two arguments: the first, another arbitrary function; and the second, an arbitrary argument. These functions representing numbers repeatedly apply the first argument to the second, and the amount of applications represents the number being encoded:

```
(define (zero function argument)
argument)
(define (one function argument)
(function argument))
(define (five function argument)
(function
(function
(function
(function
(function argument))))))
```

For `zero`

, the given function is not applied, the argument is returned unaltered. For `one`

, the given function is applied once. For `five`

, the given function is applied five times. And so on.

When we print these numbers to inspect them, this is what Racket outputs:

```
> five
#<procedure:five>
```

As the listing above illustrates, functions are opaque, so we introduce extra machinery. This is a non-essential feature of programming languages and is not part of our program, but it helps us read the program’s output:

```
(define (pretty-print number)
(number add1 0))
```

The function `pretty-print`

is not part of our main program, it only exists as a helper. That is why it is allowed to contain regular Racket numbers and operations on them—namely, `0`

and `add1`

. It receives as argument a number encoded in terms of functions and transforms it back into a regular number, so that we can read it:

```
> (pretty-print zero)
0
> (pretty-print one)
1
> (pretty-print five)
5
```

The way `pretty-print`

works reveals how this encoding of numbers using functions works. Numbers are functions, so `pretty-print`

*applies that function*. As arguments, numbers receive another function and an initial value. Then the number repeatedly applies that given function to the initial value; the amount of applications corresponds to the number we want to encode.

The function `pretty-print`

makes a careful choice of arguments with which it calls the number. The initial value is `0`

, and the function to be repeatedly applied is `add1`

. So, `(pretty-print five)`

evaluates as the following:

```
(add1
(add1
(add1
(add1
(add1 0))))) ;; => 5
```

Now that we have an encoding for numbers, we need to adapt out program to use it. For the main function, `sum-up-to`

, we just change the return from `0`

(the native Racket number) to `zero`

(our encoding as defined above):

```
(define (sum-up-to number)
(if (zero? number)
zero
(+ number (sum-up-to (sub1 number)))))
```

The next step is to modify the functions that work on the numbers so that they are aware of the encoding we introduced. There are three of them: `zero?`

, `sub1`

and `+`

.

To implement `zero?`

, we can use an idea similar to `pretty-print`

: call the number—which is a function—with carefully chosen arguments. For the initial value, we choose `#t`

, and for the function we choose one that always returns `#f`

:

```
(define (zero? number)
(define (always-false ignored-argument)
#f)
(number always-false #t))
```

Remember that these are the encoded numbers:

```
(define (zero function argument)
argument)
(define (one function argument)
(function argument))
(define (five function argument)
(function
(function
(function
(function
(function argument))))))
```

So, if `zero?`

is called with `zero`

, then the initial value `#t`

is returned unaltered. If `zero?`

is called with `one`

, then it becomes `(one always-false #t)`

, which then becomes `(always-false #t)`

, and evaluates to `#f`

. The same happens to any number that is not `zero`

:

```
> (zero? zero)
#t
> (zero? one)
#f
> (zero? five)
#f
```

To implement addition (`+`

), we can use the following observation: if the number `number-left`

means “do something to the argument `number-left`

times,” and the number `number-right`

means “do something to the argument `number-right`

times,” then the number `number-left + number-right`

means “do something to the argument `number-left + number-right`

times.” In particular, we can *do something* to the argument `number-right`

times and use the result as the initial value to *do something* to the argument `number-left`

times:

```
(define (+ number-left number-right)
(define (result function argument)
(number-left function (number-right function argument)))
result)
```

The following listing is an example of `+`

in use:

```
> (pretty-print (+ five five))
10
```

For the last operation on numbers, `sub1`

, we start by simplifying the problem by reducing its scope. In `sum-up-to`

, the function `sub1`

is only called with positive numbers. Also, our encoding using functions can only represent non-negative numbers. So, we define `(sub1 zero)`

to output `zero`

instead of `-1`

as it should according to mathematics.

With this restriction in place, we can define `sub1`

for positive integers using a *sliding window* over the number line. Starting with a pair `(zero, zero)`

, for each step, the right element goes to the left, and the new right element is the current plus one. Another way of interpreting this is that the right element is traversing the number line and the left element is one behind it. We take that step `number`

times and the predecessor of the given `number`

is the element on the left of the pair:

```
(struct pair (left right))
(define (sub1 number)
(define initial-pair (pair zero zero))
(define (slide-pair current-pair)
(define current-number (pair-right current-pair))
(pair current-number (+ current-number one)))
(define final-pair
(number slide-pair initial-pair))
(pair-left final-pair))
```

We can test `sub1`

and see the result using `pretty-print`

:

```
> (pretty-print (sub1 five))
4
```

At this point, we have all the numeric operations necessary for `sum-up-to`

encoded in terms of functions. This means that numbers are not an essential feature of programming languages. On the next section, we address the only other primitive data type used in our program: booleans.

### Booleans§

There is only one place in which we use a boolean in our program: the conditional (`if`

) in `sum-up-to`

’s body. Its condition depends on `zero?`

, which is the only function generating booleans. For convenience, the following lists their current definitions again:

```
(define (sum-up-to number)
(if (zero? number)
zero
(+ number (sum-up-to (sub1 number)))))
(define (zero? number)
(define (always-false ignored-argument)
#f)
(number always-false #t))
```

Are booleans an essential feature of programming languages, or can we *encode them away*? Programmers familiar with C know that the answer to this question is negative, because in C there are no booleans. They are encoded in terms of numbers: zero represents *false* and any other number represents *true*.

As was the case with numbers, different encodings are possible. For example, we could use the strings `"true"`

and `"false"`

; or an empty list could mean *false* and lists with at least one element could represent *true*. And, as before, some encodings are more convenient than others.

A particularly interesting choice would be to follow C’s example and use numbers to encode booleans. But, since in the previous section we *encoded numbers away* in terms of functions, we are consistent and use functions to encode booleans:

```
(define (true first second)
first)
(define (false first second)
second)
```

In our encoding, booleans are functions that receive two arguments. The value `true`

returns the first argument, and `false`

returns the second argument.

We can now adapt `zero?`

to use these values:

```
(define (zero? number)
(define (always-false ignored-argument)
false)
(number always-false true))
```

Because we changed the representation of booleans, we need to modify the conditional (`if`

) accordingly. It receives as arguments a condition, a value (`then`

) to return in case the condition is *true* and another value (`else`

) in case it is *false*. The condition is a boolean which we encoded as a function, and this function is already capable of choosing which value to return:

```
(define (if condition then else)
(condition then else))
```

We introduced a problem in `sum-up-to`

, though. Here is its current definition one more time:

```
(define (sum-up-to number)
(if (zero? number)
zero
(+ number (sum-up-to (sub1 number)))))
```

Before we encoded `if`

, this code was using Racket’s `if`

. And Racket’s `if`

only executes a branch if necessary. In particular, the part `(+ number (sum-up-to (sub1 number)))`

only ran if `(zero? number)`

was *false*. But now, because `if`

is a function call, by the time we check the condition to make a decision, this part already ran. And it contains a recursive call to `sum-up-to`

, which leads to an infinite sequence of recursive calls. This program does not terminate.

To solve this issue, we *wrap* the conditional branches in functions, so that they do not execute right away. We then use `if`

to choose the right function to call:

```
(define (sum-up-to number)
(define (then)
zero)
(define (else)
(+ number (sum-up-to (sub1 number))))
(define branch-to-take
(if (zero? number) then else))
(branch-to-take))
```

The key observation regarding the listing above is that `(define (then) ___)`

and `(define (else) ___)`

are defining two *functions* called `then`

and `else`

. These functions receive no arguments, that is why we define them with `(define (then) ___)`

and not `(define (then x y z) ___)`

. Similarly, the code `(branch-to-take)`

is calling the function `branch-to-take`

without any arguments.

Our work with booleans is complete. There are no longer any native Racket booleans in our program, they have been encoded into functions. Moreover, our program contains no primitive values (numbers, booleans, strings, and so on), and it continues to have the same meaning:

```
> (pretty-print (sum-up-to five))
15
```

So we can conclude that primitive values are not essential features to programming languages, which is a surprising result. Are compound data structures essential? On the next section we explore this question.

### Pairs§

The only instance of a data structure in our program is a *pair*, used in `sub1`

. There are three functions to interact with pairs: the function `(pair left right)`

, which creates a pair with the elements `left`

and `right`

; the function `(pair-left pair)`

, which receives a pair and returns the element on the left; and the function `(pair-right pair)`

, which receives a pair and returns the element on the right.

Encodings for pairs are not as natural as, for example, the encoding for numbers in terms of strings. But can it be done at all? In particular, can we use functions for that purpose, since we have used them for primitive data types in the previous sections? It turns out that we can. And the crucial insight is that inner functions (functions defined within other functions) can refer to arguments of the outer function. They *remember* those arguments even after the outer function has returned. The following listing illustrates this:

```
(define (store value)
(define (retriever)
value)
retriever)
(define stored-5 (store five))
(define stored-1 (store one))
(pretty-print (stored-5)) ;; => 5
(pretty-print (stored-1)) ;; => 1
```

In the code above, `store`

is a function which receives a `value`

and stores it for later. The way to retrieve the value is to apply the function returned by the call to `store`

. It works by defining and returning an inner function, `retriever`

, which has access to the outer `value`

and *remembers* it, even after `store`

itself has returned.

To implement a pair, we can use the idea from `store`

, but with two `value`

s as arguments to *remember*. The problem then becomes: when retrieving, which of the two values to return? This is not a decision we can make at the point of defining `retriever`

, because information about which of the two values to return is only known when retrieving.

The solution is to modify `retriever`

to receive an argument, a `selector`

function. Then `retriever`

calls `selector`

with both values in the pair and let it decide which one to return. With that, the `pair`

function is complete:

```
(define (pair left right)
(define (retriever selector)
(selector left right))
retriever)
```

We can now create pairs, but to retrieve the values from it we still have to define the selectors. They receive `left`

and `right`

and return the correct element in the pair:

```
(define (selector-left left right)
left)
(define (selector-right left right)
right)
```

With the selectors defined above, pairs are functional, as the listing below exemplifies:

```
(define number-pair (pair five one))
> (pretty-print (number-pair selector-left))
5
> (pretty-print (number-pair selector-right))
1
```

We are now one step away from defining the accessor functions `pair-left`

and `pair-right`

used by `sub1`

. We only need to wrap the usage pattern from the listing above:

```
(define (pair-left pair)
(define (selector-left left right)
left)
(pair selector-left))
(define (pair-right pair)
(define (selector-right left right)
right)
(pair selector-right))
```

The following is an example of these accessor functions in use:

```
> (pretty-print (pair-left number-pair))
5
> (pretty-print (pair-right number-pair))
1
```

More importantly, our program is working with this encoding for pairs in terms of functions:

```
> (pretty-print (sum-up-to five))
15
```

Before we move on to other programming-language features that we might question as either *essential* or *encodeable*, let us appreciate the importance of the result above. We used functions to encode pairs, but what about other data structures? They are not used `sum-up-to`

, but, if they were, could we *encode them away*? Or are there data structures which are *essential* features in programming languages?

One more time, the answer is that data structures in general are *encodeable* in terms of simpler features. And, once again, there are different encodings available. In particular, it is possible to encode all data structures in terms of pairs; and, ultimately, in terms functions, by the result of this section. The figure below illustrates examples of encodings:

In the figure above, lists (also known as arrays and vectors) are composed of pairs of pairs and a distinguished empty pair. This distinguished empty pair could be represented by, for example, *false*—anything outside the range of possible list elements (integers, in the example) would work.

A list containing pairs of elements could be interpreted as a record (also known as dictionary, hash and associative array). The left element of the pair is the key and the right element is the value.

Finally, with records it is possible to encode objects. Some fields are non-function values (for example, `name`

and `birthdate`

), and some are functions (for example, `age`

), which can be interpreted as methods. One special record field (`self`

) contains a reference to the whole record itself. This self-awareness is necessary so that methods (for example, `age`

) can refer to other object attributes (for example, `birthdate`

).

Objects can get more complicated, with features such as inheritance and polymorphism. Also, there exists many other data structures: tuples, trees and more. But, with varying degrees of difficulty, they are all encodeable in terms of pairs, the simplest way to couple data together. So, ultimately, this section shows that all data structures can be defined in terms of functions.

The next features we have to address are those in functions themselves, because they are the only kind of value left in our program. What aspects of functions are essential features of programming languages? What aspects can be *encoded away*? In the next section, we address the most powerful feature of functions: *recursion*.

### Recursion§

There is only one recursive function in our program: `sum-up-to`

. The following is its current definition, for convenience:

```
(define (sum-up-to number)
(define (then)
zero)
(define (else)
(+ number (sum-up-to (sub1 number))))
(define branch-to-take
(if (zero? number) then else))
(branch-to-take))
```

The particular point of recursion is the call to `sum-up-to`

in the `else`

branch. This works because, in Racket, when defining the function using `(define (sum-up-to number) ___)`

the binding for `sum-up-to`

is available in the body. Can we *encode this feature away*?

Surprisingly, the answer to this question is positive. And there are multiple possible encodings; the simplest is known as *tying the knot*. To *tie the knot* in our program, we start by introducing an auxiliary function `sum-up-to/rest`

which `sum-up-to`

calls in place of the recursive call:

```
(define (sum-up-to number)
(define (then)
zero)
(define (else)
(+ number (sum-up-to/rest (sub1 number))))
(define branch-to-take
(if (zero? number) then else))
(branch-to-take))
```

The name `sum-up-to/rest`

for this auxiliary function is appropriate because, as implemented, `sum-up-to`

is only performing one step of the computation; it delegates the rest of the computation to `sum-up-to/rest`

. The question then becomes: how do we implement `sum-up-to/rest`

?

A first idea would be to copy and paste the implementation for `sum-up-to`

:

```
(define (sum-up-to/rest number)
(define (then)
zero)
(define (else)
(+ number (sum-up-to/rest (sub1 number))))
(define branch-to-take
(if (zero? number) then else))
(branch-to-take))
```

But this idea is bad, because now `sum-up-to/rest`

is using recursion, the exact feature we are trying to *encode away*. Alternatively, we could reuse our previous idea and rewrite `sum-up-to/rest`

to delegate to another auxiliary function `sum-up-to/rest2`

. But this idea is also bad, because we would be just delaying the problem: how would we write `sum-up-to/rest2`

?

Because we do not know how to implement `sum-up-to/rest`

, we can leave it for later, defining just a placeholder:

```
(define (sum-up-to/rest number)
"TEMPORARY IMPLEMENTATION")
(define (sum-up-to number)
(define (then)
zero)
(define (else)
(+ number (sum-up-to/rest (sub1 number))))
(define branch-to-take
(if (zero? number) then else))
(branch-to-take))
```

Before we can use `sum-up-to`

, we have to provide an implementation for `sum-up-to/rest`

. But, once `sum-up-to`

has been defined, we can use it to implement `sum-up-to/rest`

. The resulting program is still non-recursive, because all variables are defined before they are used. We can use mutation (`set!`

) to *change* the placeholder definition of `sum-up-to/rest`

into `sum-up-to`

itself:

```
(define (sum-up-to/rest number)
"TEMPORARY IMPLEMENTATION")
(define (sum-up-to number)
(define (then)
zero)
(define (else)
(+ number (sum-up-to/rest (sub1 number))))
(define branch-to-take
(if (zero? number) then else))
(branch-to-take))
(set! sum-up-to/rest sum-up-to)
```

After the `set!`

operation, the name `sum-up-to/rest`

refers to the function `sum-up-to`

, instead of the placeholder implementation. So `sum-up-to`

can call itself via `sum-up-to/rest`

, restoring its original functionality. With this change, the program is no longer recursive, and it still outputs the same value:

```
> (pretty-print (sum-up-to five))
15
```

We have successfully encoded recursion, but the encoding relies on mutation of the program’s state (`set!`

). Can we then *encode mutation away*? Yes, but it would be a pervasive change to the program—the encoding would require modifications to *every* function definition and *every* function application. In addition to their existing arguments, functions would receive a record representing the current global state of the program. This record would map the variable names to their current value. Also, in addition to their existing return value, functions would return a possibly modified record representing a possibly modified state of the program. Then, every function application would be changed to thread this global state throughout the program. And, finally, every variable reference would need to access the record, selecting the corresponding field. The following extract illustrates this idea:

```
(define initial-state (empty-record))
(define (sum-up-to/rest number program-state)
(pair "TEMPORARY IMPLEMENTATION" program-state))
(define state-with-partial-sum-up-to/rest
(record-set initial-state
"sum-up-to/rest" sum-up-to/rest))
(define (sum-up-to number program-state)
___ (record-lookup program-state "sum-up-to/rest") ___)
(define state-with-complete-sum-up-to/rest
(record-set state-with-partial-sum-up-to/rest
"sum-up-to/rest" sum-up-to))
```

In the listing above, the placeholder implementation of `sum-up-to/rest`

and `sum-up-to`

were modified to receive an extra argument representing the `program-state`

. Also, they return pairs of their output value and a possibly modified `program-state`

. Then, when using `sum-up-to/rest`

in `sum-up-to`

, it is necessary to lookup its definition in the given `program-state`

. Finally, we have to manage the global `program-state`

, first creating it as an `empty-record`

, then adding `sum-up-to/rest`

as it is implemented and overwriting its value when `sum-up-to`

is available.

While feasible, this solution is not elegant. It affects even the functions that do not need to change the global state of the program, because they need to thread it appropriately.

So we backtrack and reconsider our encoding for recursion, avoiding mutation. This is `sum-up-to`

before we *tied the knot*:

```
(define (sum-up-to number)
(define (then)
zero)
(define (else)
(+ number (sum-up-to/rest (sub1 number))))
(define branch-to-take
(if (zero? number) then else))
```

It still depends on `sum-up-to/rest`

, which we do not know how to implement. But, this time, instead of coming up with a placeholder implementation for it, we change `sum-up-to`

so that it receives `sum-up-to/rest`

as an argument:

```
(define (sum-up-to sum-up-to/rest number)
(define (then)
zero)
(define (else)
(+ number (sum-up-to/rest (sub1 number))))
(define branch-to-take
(if (zero? number) then else))
```

Now it is the job of `sum-up-to`

’s callers to provide a suitable `sum-up-to/rest`

:

```
(pretty-print (sum-up-to ___ five))
```

What can we use to fill in the `___`

above? A good candidate is `sum-up-to`

itself:

```
(pretty-print (sum-up-to sum-up-to five))
```

This choice is similar to the one in the line `(set! sum-up-to/rest sum-up-to)`

when *tying the knot*. But this time there is a problem. We passed `sum-up-to`

as the `sum-up-to/rest`

argument when calling `sum-up-to`

itself. So, in `sum-up-to`

’s body, when `sum-up-to/rest`

is called, this is actually a call to `sum-up-to`

. And `sum-up-to`

requires a `sum-up-to/rest`

as its first argument:

Again, we can use the same idea as before to solve this issue. We can pass `sum-up-to/rest`

itself as the argument:

```
(define (sum-up-to sum-up-to/rest number)
(define (then)
zero)
(define (else)
(+ number
(sum-up-to/rest sum-up-to/rest (sub1 number))))
(define branch-to-take
(if (zero? number) then else))
(branch-to-take))
```

With this change, we successfully encoded recursion in terms of non-recursive functions:

```
> (pretty-print (sum-up-to sum-up-to five))
15
```

Unfortunately, we changed the interface to `sum-up-to`

in this process. Now callers need to be aware of the recursion encoding, and call the function with `(sum-up-to sum-up-to number)`

, which is inconvenient. We can make this better by introducing an auxiliary function `sum-up-to/partial`

:

```
(define (sum-up-to number)
(define (sum-up-to/partial sum-up-to/rest number)
(define (then)
zero)
(define (else)
(+ number
(sum-up-to/rest sum-up-to/rest (sub1 number))))
(define branch-to-take
(if (zero? number) then else))
(branch-to-take))
(sum-up-to/partial sum-up-to/partial number))
```

The algorithm for adding numbers is in `sum-up-to/partial`

, and `sum-up-to`

is only a façade to fix `sum-up-to/partial`

’s interface. This brings us back to the original:

```
> (pretty-print (sum-up-to five))
15
```

The result of this section is the most important in this article to this point. We encoded recursion in terms of non-recursive functions, using self-passing. And recursion was the ingredient that allowed `sum-up-to`

to calculate sums up to arbitrarily large numbers. There is no upper bound to its argument, so it works for infinitely many inputs. If we think of a function as a lookup table from inputs to outputs, then `sum-up-to`

is a table with infinitely many rows. But its definition is still finite, taking fewer than ten lines. What allows us to compact the definition this way is recursion.

The observation that recursion can be encoded in terms of non-recursive functions leads to the conclusion that non-recursive functions alone are capable of performing arbitrary computations. Anything a computer can do is expressible in terms of non-recursive functions.

There are few features left in our program. It is composed solely of (non-recursive) function definitions and applications. Can we make it even simpler? On the next section, we address functions with multiple arguments.

### Functions with Multiple Arguments§

Almost all functions in our program receive multiple arguments. In some of them, for example, `(pair left right)`

, it seems like the ability to receive multiple arguments is essential to their functionality. After all, the purpose of `pair`

is exactly to couple the arguments `left`

and `right`

together. But is this an essential feature of programming languages, or can functions with multiple arguments be *encoded away*, so that only functions with a single argument remain?

If we allow the encoding to include data structures, then we can find an intuitive encoding. For example, instead of `(+ number-left number-right)`

receiving two arguments, it could receive a pair containing the operands: `(+ number-pair)`

. Then, in its body, `+`

would extract the operands from the pair and proceed as before.

We already established an encoding for pairs and discussed how to use it to encode lists of arbitrary size, so the reasoning above would apply to functions with arbitrary number of arguments. But then how could we implement the encoding for pairs? Remember that `(pair left right)`

is itself a function with multiple arguments. To solve this impossible situation in which each encoding depends on one other, we need a new idea.

This new idea stems from two observations we have already explored: first, that functions can return functions as their return value; second, that inner functions (functions defined within other functions) have access to outer functions’ arguments. We used both of these features when defining our encoding for `pair`

s, for example. The following is its implementation one more time:

```
(define (pair left right)
(define (retriever selector)
(selector left right))
retriever)
```

In the listing above, the inner function `retriever`

has access to the arguments of the outer function `pair`

. Also, `pair`

outputs the function `retriever`

as its return value.

We can extend this idea to *break apart* `pair`

into a *cascade of functions*, each receiving a single argument and returning an intermediary function:

```
(define (pair left)
(define (pair/intermediary right)
(define (retriever selector)
(selector left right))
retriever)
pair/intermediary)
```

The implementation above works the same as before, but the way to call it has changed. Every invocation of `pair`

has to go through the cascade. Instead of writing, for example, `(define number-pair (pair five one))`

, the following is necessary:

```
(define number-pair/intermediary (pair five))
(define number-pair (number-pair/intermediary one))
```

More compactly, we can skip giving a name to the intermediary function and call it immediately:

```
(define number-pair ((pair five) one))
```

Cascades of this form extend to functions with arbitrarily many parameters. But what about functions with zero parameters? Our program includes a few of them, for example `else`

in `sum-up-to`

, which *guards* the computation of the recursive call. In these cases, the encoding is to add a *dummy* argument, which the function does not use. Also, we change the places that call such functions to pass a *dummy* argument in. The following is an extract of `sum-up-to`

including this treatment:

```
(define (else dummy)
___)
(define (dummy ignore-me)
ignore-me)
(else dummy)
```

The change described in this section is pervasive. It affects most defined functions and their invocations:

```
(define (sum-up-to number)
(define ((sum-up-to/partial sum-up-to/rest) number)
(define (then dummy)
zero)
(define (else dummy)
((+ number)
((sum-up-to/rest sum-up-to/rest) (sub1 number))))
(define branch-to-take
(((if (zero? number)) then) else))
(define (dummy ignore-me)
ignore-me)
(branch-to-take dummy))
((sum-up-to/partial sum-up-to/partial) number))
(define ((zero function) argument)
argument)
(define ((one function) argument)
(function argument))
(define ((five function) argument)
(function
(function
(function
(function
(function argument))))))
(define (zero? number)
(define (always-false ignored-argument)
false)
((number always-false) true))
(define ((+ number-left) number-right)
(define ((result function) argument)
((number-left function)
((number-right function) argument)))
result)
(define (sub1 number)
(define initial-pair ((pair zero) zero))
(define (slide-pair current-pair)
(define current-number (pair-right current-pair))
((pair current-number) ((+ current-number) one)))
(define final-pair
((number slide-pair) initial-pair))
(pair-left final-pair))
(define ((true first) second)
first)
(define ((false first) second)
second)
(define (((if condition) then) else)
((condition then) else))
(define ((pair left) right)
(define (retriever selector)
((selector left) right))
retriever)
(define (pair-left pair)
(define ((selector-left left) right)
left)
(pair selector-left))
(define (pair-right pair)
(define ((selector-right left) right)
right)
(pair selector-right))
(define (pretty-print number)
((number add1) 0))
(pretty-print (sum-up-to five)) ;; => 15
```

The program above is difficult to read. The only way to understand it is to retrace the steps we have took so far. Despite this difficulty, it is very *simple*. It uses almost no features from Racket, which means that we are near the essence of programming languages. The next section is about the last transformation we apply to our program.

### Named Definitions§

We defined functions and intermediary values using the `(define ___ ___)`

form all over our program. This form is convenient because it allows us to give names to concepts and computations. And this form is powerful. For example, using it we can define functions in any order, regardless of how they depend on each other. Consider the following excerpt:

```
(define (sum-up-to number)
___ (sub1 number) ___)
(define (sub1 number)
___)
```

When programming, it is often better to represent the high-level constructs (for example, `sum-up-to`

) first, and the details (for example, `sub1`

) later. That is why `(define ___ ___)`

form allows `sum-up-to`

to refer to `sub1`

even though it is only defined later. Is this an essential feature of programming languages?

The answer one more time is negative. Named definitions are not an essential feature and we can *encode them away*, in terms of simpler features. What can be simpler than a function with a name? A function with no name (*anonymous function*). In Racket, *anonymous functions* are spelled `(λ (argument) body)`

, in which `argument`

is an identifier naming the argument that the function receives, and `body`

is the expression representing the computation of its return value. For example, the following two definitions are equivalent:

```
(define (sub1 number)
___)
(define sub1
(λ (number)
___))
```

To *encode away* named definitions, we first reorder them so that they can only refer to previously defined names:

```
(define ((true first) second)
first)
(define ((false first) second)
second)
(define (((if condition) then) else)
((condition then) else))
(define ((pair left) right)
(define (retriever selector)
((selector left) right))
retriever)
(define (pair-left pair)
(define ((selector-left left) right)
left)
(pair selector-left))
(define (pair-right pair)
(define ((selector-right left) right)
right)
(pair selector-right))
(define ((zero function) argument)
argument)
(define ((one function) argument)
(function argument))
(define ((five function) argument)
(function
(function
(function
(function
(function argument))))))
(define (zero? number)
(define (always-false ignored-argument)
false)
((number always-false) true))
(define ((+ number-left) number-right)
(define ((result function) argument)
((number-left function)
((number-right function) argument)))
result)
(define (sub1 number)
(define initial-pair ((pair zero) zero))
(define (slide-pair current-pair)
(define current-number (pair-right current-pair))
((pair current-number) ((+ current-number) one)))
(define final-pair
((number slide-pair) initial-pair))
(pair-left final-pair))
(define (sum-up-to number)
(define ((sum-up-to/partial sum-up-to/rest) number)
(define (then dummy)
zero)
(define (else dummy)
((+ number)
((sum-up-to/rest sum-up-to/rest) (sub1 number))))
(define branch-to-take
(((if (zero? number)) then) else))
(define (dummy ignore-me)
ignore-me)
(branch-to-take dummy))
((sum-up-to/partial sum-up-to/partial) number))
(define (pretty-print number)
((number add1) 0))
(pretty-print (sum-up-to five)) ;; => 15
```

Now, we can *inline* the definitions where they are used. For example, `zero?`

’s current definition is:

```
(define (always-false ignored-argument)
false)
((number always-false) true)
```

We can rewrite the above such that each reference to the `always-false`

function is replaced with `always-false`

’s implementation, using anonymous functions:

```
((number (λ (ignored-argument) false)) true)
```

We are ready to see the final version of our program, in which all definitions are inlined:

```
(define (pretty-print number)
((number add1) 0))
(pretty-print
((λ (number)
(((λ (sum-up-to/rest)
(λ (number)
(((((λ (condition)
(λ (then)
(λ (else)
((condition then)
else))))
((λ (number)
((number
(λ (ignored-argument)
(λ (first)
(λ (second)
second))))
(λ (first)
(λ (second) first))))
number))
(λ (dummy)
(λ (function)
(λ (argument) argument))))
(λ (dummy)
(((λ (number-left)
(λ (number-right)
(λ (function)
(λ (argument)
((number-left
function)
((number-right
function)
argument))))))
number)
((sum-up-to/rest
sum-up-to/rest)
((λ (number)
((λ (pair)
(pair
(λ (left)
(λ (right) left))))
((number
(λ (current-pair)
(((λ (left)
(λ (right)
(λ (selector)
((selector
left)
right))))
((λ (pair)
(pair
(λ (left)
(λ (right)
right))))
current-pair))
(((λ (number-left)
(λ (number-right)
(λ (function)
(λ (argument)
((number-left
function)
((number-right
function)
argument))))))
((λ (pair)
(pair
(λ (left)
(λ (right)
right))))
current-pair))
(λ (function)
(λ (argument)
(function
argument)))))))
(((λ (left)
(λ (right)
(λ (selector)
((selector
left)
right))))
(λ (function)
(λ (argument)
argument)))
(λ (function)
(λ (argument)
argument))))))
number)))))
(λ (ignore-me) ignore-me))))
(λ (sum-up-to/rest)
(λ (number)
(((((λ (condition)
(λ (then)
(λ (else)
((condition then)
else))))
((λ (number)
((number
(λ (ignored-argument)
(λ (first)
(λ (second)
second))))
(λ (first)
(λ (second) first))))
number))
(λ (dummy)
(λ (function)
(λ (argument) argument))))
(λ (dummy)
(((λ (number-left)
(λ (number-right)
(λ (function)
(λ (argument)
((number-left
function)
((number-right
function)
argument))))))
number)
((sum-up-to/rest
sum-up-to/rest)
((λ (number)
((λ (pair)
(pair
(λ (left)
(λ (right) left))))
((number
(λ (current-pair)
(((λ (left)
(λ (right)
(λ (selector)
((selector
left)
right))))
((λ (pair)
(pair
(λ (left)
(λ (right)
right))))
current-pair))
(((λ (number-left)
(λ (number-right)
(λ (function)
(λ (argument)
((number-left
function)
((number-right
function)
argument))))))
((λ (pair)
(pair
(λ (left)
(λ (right)
right))))
current-pair))
(λ (function)
(λ (argument)
(function
argument)))))))
(((λ (left)
(λ (right)
(λ (selector)
((selector
left)
right))))
(λ (function)
(λ (argument)
argument)))
(λ (function)
(λ (argument)
argument))))))
number)))))
(λ (ignore-me) ignore-me)))))
number))
(λ (function)
(λ (argument)
(function
(function
(function
(function
(function argument)))))))))
```

The output of this program is still the same as when we started:

```
15
```

This version of the program is remarkably difficult to read. Only a few parts are familiar and most concepts that previously were abstracted and named are now obfuscated and intertwined. No programmer would write code this way. But, despite being *difficult* to understand, the final version of our program is *simple*. It uses almost no features from the underlying programming language (Racket). Namely, it uses only three features: (1) definitions of anonymous functions of a single argument and a single return value; (2) applications of those functions; and (3) references to variables.

It would not be possible to *encode away* any of these three features and still preserve the meaning of our program. Does this mean we reached the essence of programming languages? That is the subject of the next section.

### The Essence§

In this article, we started with a short program that was easy to understand, but which used many features of the underlying programming language: numbers, booleans, conditionals, recursion, and more. To look for the essence of programming languages, we *encoded features away*. We rewrote the program many times, preserving its meaning but encoding features in terms of other, simpler, features.

We iterated until we reached a minimal, irreducible set of features: definition and application of anonymous functions of a single argument and a single return value; and variable references. The result was an unrecognizable program, albeit a very *simple* one. Do these features represent the essence of programming languages?

Not quite. One evidence is that we had to choose our base programming language (Racket) based on certain criteria. For example, it had to a language in which functions were values. If our resulting program represented the essence of programming languages, then C—a language in which functions are not values—would not qualify as a programming language. And it does.

Moreover, had we taken a different turn on the road, we would have reached a different set of essential features. For example, we could have arrived at a machine with an infinite tape of cells, a moving head that reads and writes to the tape and a set of rules to follow for reading, writing and moving through the tape. This machine is known as Turing Machine. Or we could have arrived at something more esoteric, like the SKI combinator calculus or a tag system.

As a consequence, if we had decided for a different approach, we could have encoded the features from our final program in terms of other features. For example, we could have encoded anonymous inner functions in terms of regular C functions, which cannot be nested and must have names.

So we are still one step away from the essence. The essence must be what all these different minimal sets of features have in common. Thus, the essence of programming languages must be the essence of computation itself. Because the ability to perform arbitrary computations is the only similarity between the systems mentioned above.

This brings us to the most important result of this article: What is the essence of programming languages? What is the essence of computing? What is the common aspect of the different systems capable of performing computations? *Communication*.

The essence of programming languages is that they allow for arbitrary *communication* of data across the program. In our final program, communication is the only important feature that remained, and it manifested itself in terms of function application. We *encoded away* the numbers, booleans and more, and the only values left were functions.

Functions served two purposes in our program. First, functions served as *data*. This is why we had to choose a base language in which functions were values. The second purpose for functions was to work as a mechanism to *communicate* data. Data flowed from calling site to function body in the form of arguments, and flowed back from function body to calling site in the form of the returned value.

The minimal set of features at which we arrived after our rewrites is particularly elegant because of this dual nature of functions. It is simple to describe—if difficult to understand—because it is compact. And the compactness stems from the property that functions are simultaneously data and a means to *communicate* data.

But, in one way or another, with more or less elegance, all the minimal sets of features at which we could have arrived—for example, Turing Machines and the SKI combinator calculus—have the same essential capacity of enabling arbitrary *communication* of data across the system.

*Communication is the essence of programming languages and of computation.*

### Conclusion§

Our journey to the essence of programming languages is complete. We started with a regular program and transformed it several times to make it simpler, until we could finally observe that *communication* is the essence of programming languages. This is an important result by itself, but it is far from being the only interesting takeaway from this article. The encodings are based on techniques that are generally applicable in real-world programs.

The first and most important lesson regarding encodings is that whenever a language does not have a feature, we can encode it using the existing features. Depending on the case, it may not be convenient or practical, but theoretically it is always an option. Ultimately, any task in programming can be framed as encoding constructs that do not exist in the base language—or in any language. These constructs may be the ones that we *encoded away* in this article, or they may be constructs related to tracking bicycle trips, for example.

When encoding numbers, we chose to use functions. With this choice, we encoded numbers not by what *they are*, but by what *they do*. The primary utility of numbers is to count, so our encoding for them was to repeatedly apply a function, which effectively is performing a count. This shows that data (what numbers *are*) and computation (what they do *do*, in our encoding) are two sides of the same coin. Our final conclusion about the dual nature of functions manifested from the start.

The most complicated operation to implement in our encoded numbers was `sub1`

. We did it using a *sliding window* over the number line. This technique is applicable to all sorts of search in series in which each element depends on the previous ones. For example, calculating the Fibonacci numbers, in which each element is the sum of the previous two.

For the encoding of booleans, we again used an encoding in terms of what *they do*, instead of what *they are*. The purpose of booleans in to choose between two options—*true* and *false*—so our encoding for them were functions that received two arguments and chose one of them.

While encoding conditionals (`if`

), we had a problem due to the order in which Racket evaluates programs. Function arguments are evaluated to values before the function starts to execute. In the case of our program, this led to infinite recursion and a non-terminating program. The solution was to *wrap* the computations in functions to *delay* them. This technique is useful in situations when a computation does not need to happen immediately. For example, calls to a logger might include an expensive computation that should only occur in *debug* mode. In this case, the call might be *delayed* by *wrapping* it in a function, which the logger only calls if its log-level is *debug*.

The encoding of pairs used an important capability of functions: they *remember* the values they had in scope when defined. A fundamental part of this encoding were the inner functions that *remembered* the arguments of the outer functions even after the outer functions had returned.

Another interesting technique we introduced in the encoding for pairs is that, when a function does not have enough information to act, it can delegate to a helper function, which it receives as an argument. In the particular case of pairs, the `retriever`

did not know which element of the pair (`left`

or `right`

) to retrieve. So it received a `selector`

function as an argument, transferring the responsibility of deciding which element to retrieve to the calling site. The calling site knows which element of the pair it needs, and that is why this technique works.

The final lesson from the encoding of pairs is that any data structure is, in its essence, just a construct to couple data together. There is a wide variety of data structures to solve particular issues, for example, optimizing access time for certain elements. But their fundamental purpose is still simple: couple data together. Moreover, it is possible to construct sophisticated data structures from simpler ones—for example, construct lists out of pairs. To solve a complex problem, in many cases it is better to build more sophisticated data structures in which the problem can be phrased more naturally than to try to solve the problem directly. This was precisely the approach we took when introducing pairs in `sub1`

.

The encoding for recursion was another instance of the technique “if a function does not have enough information to act, it should receive another function that does as an argument.” In this case, the function that needs more information and the function that has the information happen to be the same. Even the *tying the knot* technique is an example of this. It relies on mutation of the program state (`set!`

), and mutation can be interpreted as an extra argument to every function, carrying the global program state. When using the *tying the knot* technique, the global program state includes the *function that has the necessary information to act*.

When encoding functions with multiple arguments, we took to an extreme the *memory* features of inner function definitions, which we had already explored in the encoding for pairs. We created cascades of functions that received a single argument and returned an intermediary function. In everyday programming, the ability to create inner functions is one of the most useful, and is a significant reason for the recent popularity of functional programming languages.

The final practical lesson for working programmers in this article comes from the encoding of named definitions. After the transformation, the program becomes unintelligible. This highlights the importance of giving good names to concepts in programming. Working programmers are not only writing programs that run correctly—computers interpret our unintelligible final version of the program without problems—but, more importantly, they are *communicating* ideas to other people. Programmers ideally write code that others can understand and improve in the future.

Again, coming from a different direction, we acknowledge the importance of *communication*. We have now come full circle:

*The essence of programming languages is communication.*

### References§

The main inspiration for this article were the talks by Jim Weirich on the Y-combinator: the Ruby version, in Ruby Conf 12, Y Not- Adventures in Functional Programming; and the JavaScript version, in ScotlandJS 2012, Adventures in Functional Programming. Also, Tom Stuart’s talk and article Programming with Nothing; and his book Understanding Computation were major influences. Together, Weirich and Stuart not only inspired this article, but motivated me to pursue a Ph.D. in programming-language theory.

Another talk that was hugely influential to me is Growing a Language, by Guy Steele in OOPSLA 1998. His presentation skills are remarkable.

But none of these sources touch on the essence of programming languages that we uncovered in this article: *communication*. For more on the relation between communication and computation, refer to A New Kind of Science, by Stephen Wolfram.

Finally, people interested in the academic side of programming-language theory can read the book Principles of Programming Languages, by Dr. Scott F. Smith, my advisor. It includes an introduction to the notation and jargon used in research and is essential to reach the level of understanding necessary to read conference and journal articles.

### Acknowledgments§

Thank you David Storrs for the comments on this article.

### Appendix: Full Listing§

```
#lang racket
(define ___ "omitted")
;; ---------------------------------------------------------------------------------------------------
;; Starting Point
(module+ original
(define (sum-up-to number)
(if (zero? number)
0
(+ number (sum-up-to (sub1 number)))))
(sum-up-to 5) ;; => 15
)
;; ---------------------------------------------------------------------------------------------------
;; Numbers
(module+ strings
(define (zero? number)
(equal? "0" number))
(define (sub1 number)
___)
(define (+ operand-left operand-right)
___)
(define (sum-up-to number)
(if (zero? number)
"0"
(+ number (sum-up-to (sub1 number)))))
(sum-up-to "5")
)
(module+ string-length
(define (zero? number)
(equal? "" number))
(define (sub1 number)
___)
(define (+ operand-left operand-right)
(string-append operand-left operand-right))
(define (sum-up-to number)
(if (zero? number)
""
(+ number (sum-up-to (sub1 number)))))
(sum-up-to "☺☺☺☺☺")
)
(module+ list-length
(define (zero? number)
(equal? '() number))
(define (sub1 number)
(if (zero? number)
'()
(rest number)))
(define (+ operand-left operand-right)
(append operand-left operand-right))
(define (sum-up-to number)
(if (zero? number)
'()
(+ number (sum-up-to (sub1 number)))))
(sum-up-to '(☺ ☺ ☺ ☺ ☺))
;; => '(☺ ☺ ☺ ☺ ☺ ☺ ☺ ☺ ☺ ☺ ☺ ☺ ☺ ☺ ☺)
)
(module+ numbers
(define (zero function argument)
argument)
(define (one function argument)
(function argument))
(define (five function argument)
(function
(function
(function
(function
(function argument))))))
)
(module+ numbers/pretty-print
(define (pretty-print number)
(number add1 0))
(define (zero function argument)
argument)
(define (one function argument)
(function argument))
(define (five function argument)
(function
(function
(function
(function
(function argument))))))
(pretty-print zero)
(pretty-print one)
(pretty-print five)
)
(module+ numbers/sum-up-to
(define (sum-up-to number)
(if (zero? number)
zero
(+ number (sum-up-to (sub1 number)))))
(define (zero function argument)
argument)
)
(module+ numbers/zero?
(define (zero? number)
(define (always-false ignored-argument)
#f)
(number always-false #t))
(define (zero function argument)
argument)
(define (one function argument)
(function argument))
(define (five function argument)
(function
(function
(function
(function
(function argument))))))
(zero? zero)
(zero? one)
(zero? five)
)
(module+ numbers/+
(define (+ number-left number-right)
(define (result function argument)
(number-left function (number-right function argument)))
result)
(define (zero function argument)
argument)
(define (one function argument)
(function argument))
(define (five function argument)
(function
(function
(function
(function
(function argument))))))
(define (pretty-print number)
(number add1 0))
(pretty-print (+ five five))
)
(module+ numbers/sub1
(struct pair (left right))
(define (sub1 number)
(define initial-pair (pair zero zero))
(define (slide-pair current-pair)
(define current-number (pair-right current-pair))
(pair current-number (+ current-number one)))
(define final-pair
(number slide-pair initial-pair))
(pair-left final-pair))
(define (+ number-left number-right)
(define (result function argument)
(number-left function (number-right function argument)))
result)
(define (zero function argument)
argument)
(define (one function argument)
(function argument))
(define (five function argument)
(function
(function
(function
(function
(function argument))))))
(define (pretty-print number)
(number add1 0))
(pretty-print (sub1 five))
)
;; ---------------------------------------------------------------------------------------------------
;; Booleans
(module+ booleans
(define (true first second)
first)
(define (false first second)
second)
)
(module+ booleans/zero?
(define (zero? number)
(define (always-false ignored-argument)
false)
(number always-false true))
(define (true first second)
first)
(define (false first second)
second)
)
(module+ booleans/if-as-function
(define (if condition then else)
(condition then else))
(define (sum-up-to number)
(if (zero? number)
zero
(+ number (sum-up-to (sub1 number)))))
(define (zero function argument)
argument)
)
(module+ booleans/delay-computation
(define (sum-up-to number)
(define (then)
zero)
(define (else)
(+ number (sum-up-to (sub1 number))))
(define branch-to-take
(if (zero? number) then else))
(branch-to-take))
(define (if condition then else)
(condition then else))
(define (zero? number)
(define (always-false ignored-argument)
false)
(number always-false true))
(define (true first second)
first)
(define (false first second)
second)
(struct pair (left right))
(define (sub1 number)
(define initial-pair (pair zero zero))
(define (slide-pair current-pair)
(define current-number (pair-right current-pair))
(pair current-number (+ current-number one)))
(define final-pair
(number slide-pair initial-pair))
(pair-left final-pair))
(define (+ number-left number-right)
(define (result function argument)
(number-left function (number-right function argument)))
result)
(define (zero function argument)
argument)
(define (one function argument)
(function argument))
(define (five function argument)
(function
(function
(function
(function
(function argument))))))
(define (pretty-print number)
(number add1 0))
(pretty-print (sum-up-to five))
)
;; ---------------------------------------------------------------------------------------------------
;; Pairs
(module+ pairs/store
(define (store value)
(define (retriever)
value)
retriever)
(define (zero function argument)
argument)
(define (one function argument)
(function argument))
(define (five function argument)
(function
(function
(function
(function
(function argument))))))
(define (pretty-print number)
(number add1 0))
(define stored-5 (store five))
(define stored-1 (store one))
(pretty-print (stored-5)) ;; => 5
(pretty-print (stored-1)) ;; => 1
)
(module+ pairs
(define (pair left right)
(define (retriever selector)
(selector left right))
retriever)
(define (selector-left left right)
left)
(define (selector-right left right)
right)
(define (zero function argument)
argument)
(define (one function argument)
(function argument))
(define (five function argument)
(function
(function
(function
(function
(function argument))))))
(define (pretty-print number)
(number add1 0))
(define number-pair (pair five one))
(pretty-print (number-pair selector-left)) ;; => 5
(pretty-print (number-pair selector-right)) ;; => 1
(define (pair-left pair)
(define (selector-left left right)
left)
(pair selector-left))
(define (pair-right pair)
(define (selector-right left right)
right)
(pair selector-right))
(pretty-print (pair-left number-pair)) ;; => 5
(pretty-print (pair-right number-pair)) ;; => 1
)
;; ---------------------------------------------------------------------------------------------------
;; Recursion
;; In this section, for simplicity, we do not use the encoding for numbers.
(module+ recursion/introduce-sum-up-to/rest
(define (sum-up-to/rest number)
(define (then)
zero)
(define (else)
(+ number (sum-up-to/rest (sub1 number))))
(define branch-to-take
(if (zero? number) then else))
(branch-to-take))
(define (sum-up-to number)
(define (then)
zero)
(define (else)
(+ number (sum-up-to/rest (sub1 number))))
(define branch-to-take
(if (zero? number) then else))
(branch-to-take))
(set! sum-up-to/rest sum-up-to)
(define zero 0)
)
(module+ recursion/tying-the-knot
(define (sum-up-to/rest number)
"TEMPORARY IMPLEMENTATION")
(define (sum-up-to number)
(define (then)
zero)
(define (else)
(+ number (sum-up-to/rest (sub1 number))))
(define branch-to-take
(if (zero? number) then else))
(branch-to-take))
(set! sum-up-to/rest sum-up-to)
(define zero 0)
(sum-up-to sum-up-to 5)
)
(module+ recursion/self-passing/failing
(define (sum-up-to sum-up-to/rest number)
(define (then)
zero)
(define (else)
(+ number
(sum-up-to/rest (sub1 number))))
(define branch-to-take
(if (zero? number) then else))
(branch-to-take))
(define zero 0)
(sum-up-to sum-up-to 5)
)
(module+ recursion/self-passing
(define (sum-up-to sum-up-to/rest number)
(define (then)
zero)
(define (else)
(+ number
(sum-up-to/rest sum-up-to/rest (sub1 number))))
(define branch-to-take
(if (zero? number) then else))
(branch-to-take))
(define zero 0)
(sum-up-to sum-up-to 5)
)
(module+ recursion/façade
(define (sum-up-to number)
(define (sum-up-to/partial sum-up-to/rest number)
(define (then)
zero)
(define (else)
(+ number
(sum-up-to/rest sum-up-to/rest (sub1 number))))
(define branch-to-take
(if (zero? number) then else))
(branch-to-take))
(sum-up-to/partial sum-up-to/partial number))
(define zero 0)
(sum-up-to 5)
)
;; ---------------------------------------------------------------------------------------------------
;; Functions with Multiple Arguments
(module+ functions-with-multiple-arguments/multiple-arguments
(define (pair left)
(define (pair/intermediary right)
(define (retriever selector)
(selector left right))
retriever)
pair/intermediary)
)
(module+ functions-with-multiple-arguments/zero-arguments
(define (else dummy)
___)
(define (dummy ignore-me)
ignore-me)
(else dummy)
)
(module+ functions-with-multiple-arguments/checkpoint
(define (sum-up-to number)
(define (sum-up-to/partial sum-up-to/rest number)
(define (then)
zero)
(define (else)
(+ number
(sum-up-to/rest sum-up-to/rest (sub1 number))))
(define branch-to-take
(if (zero? number) then else))
(branch-to-take))
(sum-up-to/partial sum-up-to/partial number))
(define (zero function argument)
argument)
(define (one function argument)
(function argument))
(define (five function argument)
(function
(function
(function
(function
(function argument))))))
(define (zero? number)
(define (always-false ignored-argument)
false)
(number always-false true))
(define (+ number-left number-right)
(define (result function argument)
(number-left function (number-right function argument)))
result)
(define (sub1 number)
(define initial-pair (pair zero zero))
(define (slide-pair current-pair)
(define current-number (pair-right current-pair))
(pair current-number (+ current-number one)))
(define final-pair
(number slide-pair initial-pair))
(pair-left final-pair))
(define (true first second)
first)
(define (false first second)
second)
(define (if condition then else)
(condition then else))
(define (pair left right)
(define (retriever selector)
(selector left right))
retriever)
(define (pair-left pair)
(define (selector-left left right)
left)
(pair selector-left))
(define (pair-right pair)
(define (selector-right left right)
right)
(pair selector-right))
(define (pretty-print number)
(number add1 0))
(pretty-print (sum-up-to five))
)
(module+ functions-with-multiple-arguments/complete
(define (sum-up-to number)
(define ((sum-up-to/partial sum-up-to/rest) number)
(define (then dummy)
zero)
(define (else dummy)
((+ number)
((sum-up-to/rest sum-up-to/rest) (sub1 number))))
(define branch-to-take
(((if (zero? number)) then) else))
(define (dummy ignore-me)
ignore-me)
(branch-to-take dummy))
((sum-up-to/partial sum-up-to/partial) number))
(define ((zero function) argument)
argument)
(define ((one function) argument)
(function argument))
(define ((five function) argument)
(function
(function
(function
(function
(function argument))))))
(define (zero? number)
(define (always-false ignored-argument)
false)
((number always-false) true))
(define ((+ number-left) number-right)
(define ((result function) argument)
((number-left function)
((number-right function) argument)))
result)
(define (sub1 number)
(define initial-pair ((pair zero) zero))
(define (slide-pair current-pair)
(define current-number (pair-right current-pair))
((pair current-number) ((+ current-number) one)))
(define final-pair
((number slide-pair) initial-pair))
(pair-left final-pair))
(define ((true first) second)
first)
(define ((false first) second)
second)
(define (((if condition) then) else)
((condition then) else))
(define ((pair left) right)
(define (retriever selector)
((selector left) right))
retriever)
(define (pair-left pair)
(define ((selector-left left) right)
left)
(pair selector-left))
(define (pair-right pair)
(define ((selector-right left) right)
right)
(pair selector-right))
(define (pretty-print number)
((number add1) 0))
(pretty-print (sum-up-to five)) ;; => 15
)
;; ---------------------------------------------------------------------------------------------------
;; Named Definitions
(module+ named-definitions/reorder
(define ((true first) second)
first)
(define ((false first) second)
second)
(define (((if condition) then) else)
((condition then) else))
(define ((pair left) right)
(define (retriever selector)
((selector left) right))
retriever)
(define (pair-left pair)
(define ((selector-left left) right)
left)
(pair selector-left))
(define (pair-right pair)
(define ((selector-right left) right)
right)
(pair selector-right))
(define ((zero function) argument)
argument)
(define ((one function) argument)
(function argument))
(define ((five function) argument)
(function
(function
(function
(function
(function argument))))))
(define (zero? number)
(define (always-false ignored-argument)
false)
((number always-false) true))
(define ((+ number-left) number-right)
(define ((result function) argument)
((number-left function)
((number-right function) argument)))
result)
(define (sub1 number)
(define initial-pair ((pair zero) zero))
(define (slide-pair current-pair)
(define current-number (pair-right current-pair))
((pair current-number) ((+ current-number) one)))
(define final-pair
((number slide-pair) initial-pair))
(pair-left final-pair))
(define (sum-up-to number)
(define ((sum-up-to/partial sum-up-to/rest) number)
(define (then dummy)
zero)
(define (else dummy)
((+ number)
((sum-up-to/rest sum-up-to/rest) (sub1 number))))
(define branch-to-take
(((if (zero? number)) then) else))
(define (dummy ignore-me)
ignore-me)
(branch-to-take dummy))
((sum-up-to/partial sum-up-to/partial) number))
(define (pretty-print number)
((number add1) 0))
(pretty-print (sum-up-to five)) ;; => 15
)
(module+ named-definitions/inlined
(define (pretty-print number)
((number add1) 0))
(pretty-print
((λ (number)
(((λ (sum-up-to/rest)
(λ (number)
(((((λ (condition)
(λ (then)
(λ (else)
((condition then)
else))))
((λ (number)
((number
(λ (ignored-argument)
(λ (first)
(λ (second)
second))))
(λ (first)
(λ (second) first))))
number))
(λ (dummy)
(λ (function)
(λ (argument) argument))))
(λ (dummy)
(((λ (number-left)
(λ (number-right)
(λ (function)
(λ (argument)
((number-left
function)
((number-right
function)
argument))))))
number)
((sum-up-to/rest
sum-up-to/rest)
((λ (number)
((λ (pair)
(pair
(λ (left)
(λ (right) left))))
((number
(λ (current-pair)
(((λ (left)
(λ (right)
(λ (selector)
((selector
left)
right))))
((λ (pair)
(pair
(λ (left)
(λ (right)
right))))
current-pair))
(((λ (number-left)
(λ (number-right)
(λ (function)
(λ (argument)
((number-left
function)
((number-right
function)
argument))))))
((λ (pair)
(pair
(λ (left)
(λ (right)
right))))
current-pair))
(λ (function)
(λ (argument)
(function
argument)))))))
(((λ (left)
(λ (right)
(λ (selector)
((selector
left)
right))))
(λ (function)
(λ (argument)
argument)))
(λ (function)
(λ (argument)
argument))))))
number)))))
(λ (ignore-me) ignore-me))))
(λ (sum-up-to/rest)
(λ (number)
(((((λ (condition)
(λ (then)
(λ (else)
((condition then)
else))))
((λ (number)
((number
(λ (ignored-argument)
(λ (first)
(λ (second)
second))))
(λ (first)
(λ (second) first))))
number))
(λ (dummy)
(λ (function)
(λ (argument) argument))))
(λ (dummy)
(((λ (number-left)
(λ (number-right)
(λ (function)
(λ (argument)
((number-left
function)
((number-right
function)
argument))))))
number)
((sum-up-to/rest
sum-up-to/rest)
((λ (number)
((λ (pair)
(pair
(λ (left)
(λ (right) left))))
((number
(λ (current-pair)
(((λ (left)
(λ (right)
(λ (selector)
((selector
left)
right))))
((λ (pair)
(pair
(λ (left)
(λ (right)
right))))
current-pair))
(((λ (number-left)
(λ (number-right)
(λ (function)
(λ (argument)
((number-left
function)
((number-right
function)
argument))))))
((λ (pair)
(pair
(λ (left)
(λ (right)
right))))
current-pair))
(λ (function)
(λ (argument)
(function
argument)))))))
(((λ (left)
(λ (right)
(λ (selector)
((selector
left)
right))))
(λ (function)
(λ (argument)
argument)))
(λ (function)
(λ (argument)
argument))))))
number)))))
(λ (ignore-me) ignore-me)))))
number))
(λ (function)
(λ (argument)
(function
(function
(function
(function
(function argument)))))))))
)
```