https://danielsz.github.io/20240718T060528--lisps-grandfather-paradox__clojure_lisp_scheme.html

UP | HOME

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 Begrundung der elementaren Arithmetik durch die
    rekurrierende Denkweise ohne Anwendung scheinbarer Veranderlichen
    mit unendlichem Ausdehnugsbereich^1 (Skolem, T., 1923)

Primitive recursion was originally introduced by Dedekind in 1888,
and proposed as a basis for arithmetic by Skolem in 1923. There is no
lack of mathematical resources describing primitive recursion, but in
this post we are going to try and build an intuition for it.

    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 fantastic reference. In contrast, to
understand the theoretical foundation of Lisp, the traditional
treatment of the topic cannot be avoided.

Still, our bet is that the use of computer programs can be beneficial
here as well. By faithfully translating the rules of primitive
recursion into a computer program, we hope to breathe life into the
subject. This is the constructivist approach: learning means
constructing an understanding through experience and interaction.

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
  * Godel'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. We might answer the
question how Lisp improves our understanding.

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 is not complicated, but surprising. Indeed, it
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 f and any number of functions g, and
returns a function that receives any number of arguments and applies
f to the result of applying functions g 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 f is used for the initial computation only. After such
initialization, function g 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, n 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. First, note that we can
generate any number with zero and the successor function. We call
this the constant function k.

(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.

Addition is achieved by applying the successor function x times on y
+ 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.

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]

By interpreting 1 and 0 as boolean values, we can define predicates,
like zero?.

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

Usage:

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

[1 0 0]

And now we can define an if-then-else function.

(defn ite [x y z]
  (let [f (P 2)
        g (P 3)]
    ((R x y z) f g)))

Usage:

[(ite 1 3 4) (ite 0 3 4)]

[3 4]

Head over to the gists to check how we can further define junctors,
modulo, a predicate function that checks if a number is prime, etc.

Both a Clojure version and a Scheme version are available.

Open for work

Are you hiring? Do you know someone that is? Looking for a
collaborator? A team lead or member? A consultant, maybe? Need a
little boost or a long-term commitment? Let's talk.

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 Godel, 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 mu-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.

Wow, you've made it! Right up to the end! So you're into this kind of
stuff, aren't you?! Maybe we should be friends! What's more, I might
be writing more on the topic. Would you like to be notified? Also,
I'm gauging interest in long-form writing, maybe a book. If that's
something you'd sign up for, please let me know.

Bibliography

Brainerd, Walter S. and Landweber, Lawrence H. (1974). Theory of
Computation, John Wiley & Sons, Inc.

Friedman, Daniel P. and Felleisen, Matthias (1996). The little
Schemer (4th ed.), MIT Press.

Hofstadter, Douglas R. (1999). Godel, Escher, Bach: An Eternal Golden
Braid, Basic Books, Inc.

McCarthy, John (1978). History of LISP, Association for Computing
Machinery (ACM).

Meyer, Albert R. and Ritchie, Dennis M. (1967). The complexity of
loop programs, ACM Press.

Rado, T. (1962). On Non-Computable Functions, Institute of Electrical
and Electronics Engineers (IEEE).

Skolem, T. (1923). Begrundung der Elementaren Arithmetik durch die
rekurrierende Denkweise ohne Anwendung scheinbarer Veranderlichen mit
unendlichem Ausdehnungsbereich.

Footnotes:

^1

Justification of elementary arithmetic by the recurrent mindset
without the use of apparent variables with infinite extension area.