This chapter describes how to harness the unbounded power of ((lambda (x) (x x)) (lambda (x) (x x))) to carry out bounded computations.
Last week, we saw how self-reference induces divergence:
(define diverge
(lambda ()
((lambda (x) (x x))
(lambda (x) (x x)))))
Applying diverge to zero arguments induces a computation that does not terminate.
Let us parameterize the number of self-applications:
(define converge
(lambda (mt)
((lambda (x) (x x))
(lambda (x) (lambda (g) (if (<= g 0) mt ((x x) (1- g))))))))
For all mt and for all non-negative integers g (mt stands for “empty” and g stands for “gas”), evaluating ((converge mt) g) where mt denotes mt and g denotes g yields mt with g+1 applications of (lambda (g) ...).
To wit, let us trace (lambda (g) ...):
(define traced-converge
(lambda (mt)
((lambda (x) (x x))
(lambda (x) (trace-lambda chug (g) (if (<= g 0) mt ((x x) (1- g))))))))
When applying traced-converge to 33 and then 0, chug is applied once, when applying traced-converge to 33 and then 1, chug is applied twice, and when applying traced-converge to 33 and then 2, chug is applied thrice:
> ((traced-converge 33) 0)
|(chug 0)
|33
33
> ((traced-converge 33) 1)
|(chug 1)
|(chug 0)
|33
33
> ((traced-converge 33) 2)
|(chug 2)
|(chug 1)
|(chug 0)
|33
33
>
Given mt and g (denoted by g), applying a procedure to the result of ((x x) (1- g)) has the effect of applying this procedure g times:
(define PI
(lambda (mt f)
((lambda (x)
(x x))
(lambda (x)
(lambda (g)
(if (<= g 0)
mt
(f ((x x) (1- g)))))))))
For all mt (denoted by mt), for all f (denoted by f), and for all non-negative integers g (denoted by g), evaluating ((PI mt f) g) reduces to evaluating (f (f ...(f mt)...)) with g applications of f.
To wit, let us trace (lambda (g) ...):
(define traced-PI
(lambda (mt f)
((lambda (x)
(x x))
(lambda (x)
(trace-lambda chug (g)
(if (<= g 0)
mt
(f ((x x) (1- g)))))))))
When applying traced-PI to 33 and the identity procedure and then 3, chug is applied four times and then identity is applied three times:
> ((traced-PI 33 (trace-lambda identity (a) a)) 3)
|(chug 3)
| (chug 2)
| |(chug 1)
| | (chug 0)
| | 33
| |(identity 33)
| |33
| (identity 33)
| 33
|(identity 33)
|33
33
>
In computability theory, this pattern – i.e., (f (f ...(f mt)...)) with g applications of f – is known as “primitive iteration”.
Adding two natural numbers is defined by induction on the first argument:
forall y : nat, (add 0 y) = y
forall x y : nat, (add (1+ x) y) = (1+ (add x y))
So we can implement addition by primitive iteration:
(define add_PI
(lambda (x y)
((PI y 1+) x)))
As illustrated in the accompanying .scm file, this definition passes the unit tests of the previous chapter.
We can also trace it to visualize the computation:
(define traced-add_PI
(lambda (x y)
((traced-PI y (trace-lambda succ (n) (1+ n))) x)))
Applying traced-add_PI to 3 and 2 induces four calls to chug and three calls to succ:
> (traced-add_PI 3 2)
|(chug 3)
| (chug 2)
| |(chug 1)
| | (chug 0)
| | 2
| |(succ 2)
| |3
| (succ 3)
| 4
|(succ 4)
|5
5
>
Multiplying two natural numbers is defined by induction on the first argument:
forall y : nat, (mul 0 y) = 0
forall x y : nat, (mul (1+ x) y) = (mul x y) + y
So we can implement multiplication by primitive iteration:
(define mul_PI
(lambda (x y)
((PI 0 (lambda (z) (+ z y))) x)))
As illustrated in the accompanying .scm file, this definition passes the unit tests of the previous chapter.
We can also trace it to visualize the computation:
(define traced-mul_PI
(lambda (x y)
((traced-PI 0 (trace-lambda plus (z) (+ z y))) x)))
Applying traced-mul_PI to 3 and 2 induces four calls to chug and three calls to plus:
> (traced-mul_PI 3 2)
|(chug 3)
| (chug 2)
| |(chug 1)
| | (chug 0)
| | 0
| |(plus 0)
| |2
| (plus 2)
| 4
|(plus 4)
|6
6
>
Exponentiating a natural number (the base) with another natural number (the exponent) is defined by induction on the first argument:
forall x : nat, (exp x 0) = 1
forall x n : nat, (exp x (1+ n)) = x * (exp x n)
So we can implement exponentiation by primitive iteration:
(define exp_PI
(lambda (x n)
((PI 1 (lambda (a) (* x a))) n)))
As illustrated in the accompanying .scm file, this definition passes the unit tests of the previous chapter.
We can also trace it to visualize the computation:
(define traced-exp_PI
(lambda (x n)
((traced-PI 1 (trace-lambda times (a) (* x a))) n)))
Applying traced-exp_PI to 2 and 3 induces four calls to chug and three calls to times:
> (traced-exp_PI 2 3)
|(chug 3)
| (chug 2)
| |(chug 1)
| | (chug 0)
| | 1
| |(times 1)
| |2
| (times 2)
| 4
|(times 4)
|8
8
>
This exercise is about mystery procedures that are implemented by primitive iteration.
Characterize the result of the following procedure when it is applied to a non-negative integer:
(define pi1
(PI "!" (lambda (s) (string-append "ha" s))))
(Reminder: string-append denotes the predefined procedure for concatenating strings.)
Justify your characterization.
Characterize the result of the following procedure when it is applied to a non-negative integer that is even:
(define pi2
(PI #t not))
(Reminder: not denotes the predefined procedure for negating Booleans.)
Justify your characterization.
Characterize the result of the following procedure when it is applied to a non-negative integer that is odd:
(define pi3
(PI #f not))
Justify your characterization.
Characterize the result of the following procedure when it is successively applied to two integers:
(define pi4
(lambda (m)
(PI m 1-)))
(Reminder: 1- denotes the predefined procedure that subtracts 1 to its integer argument.)
In other words, if m and n denote integers, what is the result of evaluating ((p4 m) n)?
Justify your characterization.
As for primitive iteration, given mt and g (denoted by g), applying a procedure to the result of ((x x) (1- g)) has the effect of applying this procedure g times:
(define PR
(lambda (mt f)
((lambda (x)
(x x))
(lambda (x)
(lambda (g)
(if (<= g 0)
mt
(f (1- g) ((x x) (1- g)))))))))
For all mt (denoted by mt), for all f (denoted by f), and for all non-negative integers g (denoted by g), evaluating ((PR mt f) g) reduces to evaluating (f (- g 1) (f (- g 2) ...(f 0 mt)...)) with g applications of f.
To wit, let us trace (lambda (g) ...):
(define traced-PR
(lambda (mt f)
((lambda (x)
(x x))
(lambda (x)
(trace-lambda chug (g)
(if (<= g 0)
mt
(f (1- g) ((x x) (1- g)))))))))
When applying traced-PR to 33 and the second-projection procedure and then 5, chug is applied six times and then second-projection is applied five times:
> ((traced-PR 0 (trace-lambda second-projection (i a) a)) 5)
|(chug 5)
| (chug 4)
| |(chug 3)
| | (chug 2)
| | |(chug 1)
| | | (chug 0)
| | | 0
| | |(second-projection 0 0)
| | |0
| | (second-projection 1 0)
| | 0
| |(second-projection 2 0)
| |0
| (second-projection 3 0)
| 0
|(second-projection 4 0)
|0
0
>
In computability theory, this pattern – i.e., (f (- g 1) (f (- g 2) ...(f 0 mt)...)) with g applications of f – is known as “primitive recursion”.
A function that computes factorial numbers is defined by induction on its argument:
fac 0 = 1
forall n : nat, fac (1+ n) = (1+ n) * (fac n)
So we can implement the factorial function by primitive recursion:
(define fac_PR
(lambda (n)
((PR 1 (lambda (i a) (* (1+ i) a))) n)))
As illustrated in the accompanying .scm file, this implementation passes the unit tests of the previous chapter.
We can also trace it to visualize the computation:
(define traced-fac_PR
(lambda (n)
((traced-PR 1 (trace-lambda times (i a) (* (1+ i) a))) n)))
Applying traced-fac_PR to 4 induces five calls to chug and four calls to times:
> (traced-fac_PR 4)
|(chug 4)
| (chug 3)
| |(chug 2)
| | (chug 1)
| | |(chug 0)
| | |1
| | (times 0 1)
| | 1
| |(times 1 1)
| |2
| (times 2 2)
| 6
|(times 3 6)
|24
24
>
This exercise is about mystery procedures that are implemented by primitive recursion.
Characterize the result of the following procedure when it is applied to a non-negative integer:
(define pr1
(PR "" (lambda (i a)
((lambda (s)
(string-append s a s))
(string (lowercase-char i))))))
This procedure uses lowercase-character that maps a non-negative integer to a lowercase character. For example, it maps 0 to \#a, 1 to \#b, 2 to \#c, etc.
For the rest, string-append denotes the predefined procedure for concatenating strings and string denotes the predefined procedure that maps characters to the string of these characters.
Justify your characterization.
Characterize the result of the following procedure when it is applied to a non-negative integer:
(define pr2
(PR "z" (lambda (i a)
((lambda (s)
(string-append s a s))
(string (lowercase-char i))))))
Justify your characterization.
Characterize the result of the following procedure when it is applied to a string:
(define pr3
(lambda (s)
((PR "" (lambda (i a)
(string-append a (string (string-ref s i)))))
(string-length s))))
Justify your characterization.
Characterize the result of the following procedure when it is applied to a string:
(define pr4
(lambda (s)
((PR "" (lambda (i a)
(string-append (string (string-ref s i)) a)))
(string-length s))))
Justify your characterization.
Characterize the result of the following procedure when it is applied to a procedure that maps non-negative integers to integers and to a non-negative integer:
(define pr5
(lambda (f n)
((PR 0 (lambda (i a) (+ (f i) a))) (1+ n))))
Examples of procedures that map non-negative integers to integers include (lambda (i) 0), (lambda (i) 1), and (lambda (i) i).
(Hint: This procedure implements a function that is very well known in Discrete Mathematics.)
Justify your characterization.
Implement PI as an instance of PR.
Implement PR as an instance of PI.
Fixed a typo in the statements of Exercise 05.2 and of Exercise 05.3, thanks to Xu Zhiwen’s eagle eye [14 Sep 2025]
Added exercises [13 Sep 2025]
Completed [11 Sep 2025]
Created [07 Sep 2025]