This post describes the implementation of the HyperOpreation Function, aka Ackermann’s Function, which I call RepliCount, in the Scheme Programming Language. RepliCount is a recursive function that performs arithmetic operations on natural numbers by reducing the operation by stages to a succession of “counting” operations, i.e. the Peano Successor Function.
In this post I will use Lisp / Scheme notation, which has operator-prefix form. In conventional notation, a function f with arguments x, y, z defined by some expression in x y and z would be notated as:
f( x, y, z) = ...
x y z are variable names,
… is the expression that computes the value of the function.
The application of f to arguments a, b, c would be notated
f( a, b, c)
where: a b c are expressions
In Scheme notation, the operator is moved inside the parentheses as the first element of a “list”, thus:
(f, x, y, z)The definition of the function would be notated with the aid of another function “define” replacing the “=” of traditional notation:
(define (f x y z) ...)The … above would also consist of a list representing the expression to be evaluated with parameter variables x y z. The application of the function f to arguments a b c would be notated:
(f a b c)
Recursive FunctionsRecursive functions are functions defined by at least two separate cases, one of which involves the function itself and one of which does not, and the choice of which depends on the values of the arguments. A recursive function is expressed in Scheme using a “conditional expression” which evaluates a logical expression to choose one of the two (or more) value expressions.
The Scheme notation for a conditional expression is:
(if condition t-expression f-expression)
“condition” is a logical expression that evaluates to true or false
(represented in Scheme by #t or #f)
“t-expression” is the expression that gives the value of the function when condition is true
“f-expression” is the expression that gives the value of the function when condition is false.
A generalized form allows multiple conditions:
(cond (condition-1 expression-1) (condition-2 expression-2) ... (condition-n expression-n) )
“cond” is the operator,
“condition-1” is the first condition tested,
“expression-1 is the expression that gives the value of the function when condition-1 is true,
“condition-2” is the next condition tested if condition-1 was false,
“expression-2 is the expression that gives the value of the function when condition-2 is true,
etc. for additional conditions,
“condition-n” is the last condition tested if all previous conditons were false,
“expression-n is the expression that gives the value of the function when condition-n is true.
Examples of recursive functions
Two common examples of recursive functions are the factorial function and the Fibonacci series:
Factorial: usually written n! defined by:
n! is defined: 0! = 1; n! = n * (n-1)! for n > 0would be defined in Scheme:
(define (! n) (if (= n 0) 1 (* n (! (- n 1) ) ) ) )
Fibonacci F(n) is defined: F(0)=0; F(1) = 1; F(n) = F(n-1) + F(n-2) for n > 1In Scheme:
(define (F n) (cond ( (= n 0) 0) ( (= n 1) 1) ( (> n 1) (+ (F (- n 1)) (F (- n 2))) ) ) )
A CAVEAT ON EFFICINCY
The expression of the Hyperfunction is Scheme is meant to illustrate that the basic arithmetic functions can be defined in terms of the primitives of the Peano postulates, that is, to the Succesor Function (next natural number) and the number zero. For convenience of coding in Scheme, I represent numbers in “unary” or tally notation with lists.
Although the program actually computes the correct value, the algorithm and number representation used by the program is emphatically not an efficient or compact way to perform arithmetic. In fact, for operation orders above 3 (beyond exponentiation), or even large vaules of other operations, the time and storage required to compute the result may well exceed the capacity of the computer, so such computations should be approached with caution.
H(m, n, p) computes a binary arithmetic operation on natural numbers m and n, which depends on p as follows:
p=0: H(m,n,p) = S(n) Peano Successor; next whole number after n p=1 H(m,n,p) = m+n Addition (successive counting) p=2 H(m,n,p) = m*n Multiplication (successive addition) p=3 H(m,n,p) = m^n Exponentiation (successive multiplication) p=4 H(m,n,p) - m^^n Tetration (successive exponentiation, right-associative) p>4 H(m,n,p) = higher-order operations, each defined as successive composition of the next lower-order operation.
The mathematics of the HyperOperation function was discussed in a previous post.
REPRESENTATION OF NUMBERS
We represent tne natural numbers in “unary” or “tally” notation. In Scheme, zero is coded as the null list, and other natural numbers are codes as lists with a number of elements equal to the natural number. Thus this is a “unary” representation of numbers.
Define the constant zero as the null list:
(define zero '() )
SOME PRELIMINARY FUNCTION DEFINITIONS
Define Boolean operators to test for zero:
(define (zero? x) (null? x) ) (define (!zero? x) (not (null? x)) )
Next we define the Peano successor operator S as pushing (cons) another null list to the list representing the orginal number, returning a list with one more element.
(define (S x) (cons '() x) )
Next we define the predecessor for a non-zero number (a non-null list) as popping (cdr) one null list from the list representing the number, returning a list with one fewer elements, or returning an error message if the argument list is null.
(define (P x) (if (null? x) "Pnull" (cdr x)))
We can now give names to specific natural numbers. Here I define the numbers one through ten with their common English names:
(define one (S zero)) (define two (S one)) (define three (S two)) (define four (S three)) (define five (S four)) (define six (S five)) (define seven (S six)) (define eight (S seven)) (define nine (S eight)) (define ten (S nine))
For convenience and to facilitate printing values of numbers, we define a function to express the list representation of a natural number as a Scheme integer:
(define (N x) (if (null? x) 0 (+ 1 (N (cdr x))) ) )
Also for convenience we define another function to create a list representation of a Scheme integer:
(define (I x) (if (= x 0) '() (cons '() (I (- x 1)) ) ) )
DEFINING REPLICOUNT IN SCHEME
We can now define the RepliCount function in scheme.
The original Hyper-Operation function:
H(m,n,p) is defined: H(m,n,0)= S(n) for m >=0, n >= 0 [H0] p=0 succession H(m,0,1)= m for m >= 0 [H1] p=1 addition H(m,0,2)= 0 for m >= 0 [H2} p=2 multiplication H(m,0,3)= 1 for m >= 0 [H3] p=3 exponentiation H(m,0,p)= 1 for m >= 0, p > 3 [H4] p=4 tetration, p=5 pentation, etc. H(m,n,p)= H(m, H(m,P(n),p), P(p) ) for m >= 0, n > 0, p > 0 [H5]
First, to better match the Scheme operator-prefix convention,
we move the operand p, representing the arithmetic operation being performed, to the leftmost operand;
we rename it k to preserve alphabetical order of operands.
We call the the resulting function “RepliCount,” R(k,m,n).
Then, the Scheme version is converted to the “pure Peano” form:
All numbers other than zero have been expressed in terms of the successor function,
All comparisons to numbers greater than zero have been reduced to comparison to zero using the predecessor function.
Since exponentiation (p=3) has the same boundary conditions as higher-rank operations (P = 4, 5, …), we do not need a separate boundary case for p=3.
R(k,m,n) is defined: R(0,m,n) = S(n) for m >=0, n >= 0 [R0] k=0 successor R(1,m,0) = m for m >= 0 [R1] k=1 addition R(2,m,0) = 0 for m >= 0 [R2} k=2 multiplication R(3,m,0) = S(0) for m >= 0, k > 2 [R3-4] k=3 exponentiation, k=4 tetration, etc. R(k,m,n) = R(P(k), m, R(k, m, P(n)) ) for m >= 0, n > 0, k >2 [R5]
RepliCount, the “Peano Form” of the HyperOperation function, can now be expressed in Scheme as:
(define (R k m n) (cond ( (zero? k) (S n) ) ( (zero? n) (cond ( (zero? (P k) ) m ) ( (zero? (P(P k)) ) zero ) ( (!zero? (P(P k)) ) (S zero) ) ) ) ( (!zero? n) (R (P k) m (R k m (P n) ) ) ) ) )
This program was tested by the author with a version of guile. If you have any questions, corrections, or comments, please post.