Lisp's grandfather paradox

Recursion is an idea often associated with infinity, a process that repeats ad aeternam. It is perhaps surprising, then, that the origin story of mathematical recursion is grounded in finitism, the rejection of all things infinite.

In 1923, Skolem developed a theory of recursive functions as a means of avoiding the so-called paradoxes of the infinite in his paper Begründung der elementären Arithmetik durch die rekurrierende Denkweise ohne Anwendung scheinbarer Veränderlichen mit unendlichem Ausdehnugsbereich¹ (Skolem, T., 1923)

Primitive recursion was originally introduced by Dedekind in 1888 (Dedekind, Richard, 1965), and proposed as a basis for arithmetic by Skolem in 1923. It is perhaps Gödel's contributions to recursion theory that had the biggest impact, because it gave a precise meaning to the notion of computability. (Gödel, Kurt, 1931) Finally, Rózsa Péter is the mathematician responsible for coining the term primitive recursion and for writing the first monograph dedicated to recursive functions. (Lambek, J., 1968)

We believe that programming languages are the best way to convey the concept of recursion. They share with mathematics the ability to give a formal meaning to a set of symbols. But unlike mathematics, programming languages can be directly experienced-you can take the programs in this book, observe their behavior, modify them and experience the effect of these modifications. (Friedman, Daniel P. and Felleisen, Matthias, 1996)

In The Little Schemer, Daniel Friedman and Matthias Felleisen taught recursion in Scheme through dialogue, arguing that the requirements to be a successful learner was not analytical reasoning but pattern recognition. To understand the practicalities of recursion in Lisp, The Little Schemer is indeed a great reference.

Contrary to recursion in Scheme, which is defined on symbolic expressions, primitive recursion is defined on the natural numbers. There is no lack of mathematical resources describing primitive recursion, but we are going to try and build an intuition for it by faithfully translating the rules of primitive recursion into a computer program.

The goal of the exercise that follows is an understanding of the framework of primitive recursion in the terms within which it appeared. The motivation for this endeavor lies in a quest to tackle the big ideas at the crossroads of Logic, Mathematics and Computer Science, such as:

• Grundlagenkrise der Mathematik
• Finitism
• Gödel's arithmetization of syntax
• Recursion theory
• The origins of Lisp

It might be interesting to start with a quick glance at the traditional presentation of the topic. Wikipedia has a decent entry, Stanford Encyclopedia of Philosophy too. Take a look at the formulas describing primitive recursion, no matter how opaque. At the end of our exercise, we will have a basis of comparison.

Note: We are going to stick close to some conventions found in the traditional treatment of the topic, up to the capitalized one-letter naming scheme for functions. This will make it easy for learners to switch back and forth between the code and the formalism. Please do not hesitate to replace the one-letter function names with something more palatable. And remember that you can trace the execution of the functions in the REPL.

Primitive recursion takes only three initial functions closed under two operations to produce all of the familiar functions on the natural numbers.

… most computable functions that are studied in number theory (and more generally in mathematics) are primitive recursive. For example, addition and division, the factorial and exponential function, and the function which returns the nth prime are all primitive recursive. (Brainerd, Walter S. and Landweber, Lawrence H., 1974)

Our first rule is the Zero rule.

(def Z #(fn [& _] 0))

This function returns a function that takes any number of arguments and always returns zero.

[((Z)) ((Z) 5) ((Z) 1 2 3)]

[0 0 0]

Our second basic function is the successor function. Yes, that one from number theory. It increments a number by one.

Being identical to inc in Clojure, we will just alias it.

(def S inc)

Our last basic function is trickier to explain because its purpose may not be immediately apparent. It is called the projection function, and it picks an element from a sequence. Its role is auxiliary, but nonetheless crucial. It is used to configure primitive recursion by rearranging function arguments. We will see it in action soon.

(defn P [i]
  (fn [& args] (nth args (dec i))))

Note: The projection function is not zero-based, but the ArraySeq containing the arguments is, so we make the decrement adjustment.

Our first operation is composition. We will call it capital C. Remember, the initial or basic functions operate on natural numbers, the operations act on those initial functions.

(defn C [f & gs]
  (fn [& xs] (apply f (map #(apply % xs) gs))))

Composition takes a function 𝑓 and any number of functions 𝑔, and returns a function that receives any number of arguments and applies f to the result of applying functions 𝑔 on those arguments.

In some textbooks it is called the substitution operator; it is used for substituting constants, permuting variable and composing functions.

The following usage example may help.

((C S (P 1)) 5 11)

6

Contrast with:

((C S (P 2)) 5 11)

12

Finally, the recursion operation.

(defn R [n & xs]
  (fn [f g]
    (loop [i 1
           j 0
           acc (apply f xs)]
      (if (<= i n)
        (recur (inc i) (inc j) (apply (partial g j acc) xs))
        acc))))

Function 𝑓 is used for the initial computation only. After such initialization, function 𝑔 is proceeding by applying its rules, whatever they may be, on the previous computed value. Hence, the recursion.

The most important thing to notice here is that the recursion is bounded. In other words, we know in advance the number of times the procedure will repeat itself, namely, 𝐧 number of times. Primitive recursion is always bounded, it is guaranteed to halt.

Now that we have the pieces in place we can start to build our algebra of primitive recursive functions. Addition is achieved by applying the successor function 𝐱 times on 𝐲 + 1.

(defn add [x y]
  (let [f (P 1)
        g (C S (P 2))]
    ((R x y) f g)))

(add 4 5)

9

We can leverage addition to define multiplication.

(defn mul [x y]
  (let [f (Z)
        g (C add (P 2) (P 3))]
    ((R x y) f g)))

Usage:

(mul 6 7)

42

By definition, any function composed from the basic function and the operations is primitive recursive. Likewise, any derivation, like addition or multiplication, is also primitive recursive. This is how we develop the algebra of primitive recursive functions.

Note that we can generate any number with zero and the successor function. We call this the constant function 𝐤.

(defn k [n]
  (fn [& _]
    (let [f (Z)
          g (C S (P 1))]
      ((R n) f g))))

Usage:

[((k 5) 5) ((k 5) 6) ((k 5) 7)]

[5 5 5]

No matter what the input is, the function returns the number of times we applied the successor function starting from zero.

Factorial leverages multiplication, predictably. As does exponentiation.

(defn fac [n]
  (let [f (k 1)
        g (C mul (P 2) (C S (P 1)))]
    ((R n) f g)))

[(fac 3) (fac 4) (fac 5)]

[6 24 120]

(defn pow [x y]
  (let [f (k 1)
        g (C mul (P 2) (P 3))]
    ((R y x) f g)))

[(pow 3 4) (pow 4 3) (pow 4 5) (pow 5 4)]

[81 64 1024 625]

Gödel showed that a logical calculus is embedded in the primitive recursive functions. If we adopt a mathematical understanding of how logic works, we will say that zero represents false and the positive numbers represent true. Conjunction, the AND operator, is just multiplication. If you multiply two numbers the only way to get a positive number is if both of them are positive. Likewise, disjunction, the OR operator, is addition. Again, this is a basic feature of addition. The sum of two natural numbers is positive if one or the other is positive, or both.

Sometimes it is not convenient to have all the positive numbers signifying true, and we might want to normalize them to 1. We can define bool, a recursive definition of a normalizing function such that true means 1 and false means 0.

(defn bool [x]
  (let [f (Z)
        g (k 1)]
    ((R x) f g)))

Notice that if we invert the initialization function with the recursive function, we get the predicate function zero? which doubles as negation, or not.

(defn z [n]
  (let [f (k 1)
        g (Z)]
    ((R n) f g)))

Usage:

[(z 0) (z 1) (z 2)]

[1 0 0]

Putting all of the above together, we can define and:

(def and (C bool mul))

And or:

(def or (C bool add))

Please head over to the gists to check how we can further define if-then-else, more junctors, modulo, a predicate function that checks if a number is prime, etc.

Both a Clojure version and a Scheme version are available.

Because it's possible to compose all the familiar arithmetic functions within the framework of primitive recursion, David Hilbert, who instigated the efforts to rehabilitate mathematics through finitistic means, conjectured that all computable functions were primitive recursive. In 1927, two of his students, Gabriel Sudan and Wilhelm Ackermann, proved him wrong.

(defn sudan [n x y]
  (cond
    (zero? n) (+ x y)
    (zero? y) x
    :else (recur (dec n) (sudan n x (dec y)) (+ y (sudan n x (dec y))))))

(defn ackermann [m n] 
  (cond (zero? m) (inc n)
        (zero? n) (ackermann (dec m) 1)
        :else (ackermann (dec m) (ackermann m (dec n)))))

These functions increase super-exponentially, even for very small input values. Running the Ackermann function with m = 4 results in a StackOverflowError and no optimizations are straightforward to leverage, not tail recursion, not managing the call stack manually in heap memory.

While primitive recursion doesn't capture all the computable functions, all functions that are primitive recursive are computable. In some settings, this is a desirable property. Dennis Ritchie, author of the C programming language, designed the LOOP language, restricted to primitive recursion, in order to ask the question that otherwise would be a non-starter: can one look at a program and determine an upper bound on its running time? Then he went on formulating theorems concerning the hierarchy of primitive recursion by looking at the structure of the loop, its nesting depth and the growth rate. (Meyer, Albert R. and Ritchie, Dennis M., 1967)

Intuitively, primitive recursion corresponds to functions that can be computed with an understanding in advance about how far one must search for an answer. General computability includes functions in which one needs to search finitely far but without knowing how far that might be.

In Gödel, Escher, Bach: an Eternal Golden Braid, Douglas Hofstadter devised the BlooP and the FlooP languages to illustrate the difference between bounded loops (FOR) and unbounded loops (WHILE, GOTO), corresponding to primitive recursion and general recursion respectively. Adding unbounded loops makes the language general recursive and Turing-complete, as are all real-world computer programming languages. (Hofstadter, Douglas R., 1999)

Systems that are Turing complete, like the lambda calculus, the Turing machine or the 𝛍-recursive functions (aka general recursive functions, aka partial recursive functions), capture the notion of computable functions, but in these systems, while mathematically definable, some functions are not computable. (Rado, T., 1962)

My desire for an algebraic list processing language for artificial intelligence work on the IBM 704 computer arose in the summer of 1956 during the Dartmouth Summer Research Project on Artificial Intelligence which was the first organized study of AI… While expressions could be handled easily in FLPL, and it was used successfully for the Geometry program, it had neither conditional expressions nor recursion, and erasing list structure was handled explicitly by the program. (McCarthy, John, 1978)

John McCarthy based Lisp on general recursion, but devised it to operate on symbols rather than numbers. He was interested in AI, where concepts, the way humans manipulate them, occupy the center stage. A symbol can stand in for any idea, whether code or data. Just today we've seen just how expressive symbolic expressions are, effortlessly encoding the formulas of primitive recursion. Somehow we have made Lisp revisit its conceptual ancestor. We've traveled in time like in the grandfather paradox. Not with the intent to kill the progenitor, but rather to embrace him, bring him back to life, even if for a moment.