Primitive recursive functions
This page explains what primitive recursive functions (PRFs) are, and provides working code (Python, Haskell) for constructing and evaluating them.
Mathematical definition
A primitive recursive function maps each vector of natural numbers to a natural number. In other words, a PRF \(f\) with \(n\) arguments has the type \(f : \mathbb{N}^n \rightarrow \mathbb{N}\). The set of all possible PRFs is constructed in a special way, using only these 5 building blocks:
Basic:
(Zero) \(Z : \mathbb{N} \rightarrow \mathbb{N}\) is a PRF.
For each \(x \in \mathbb{N}\), \(\:Z(x) = 0\).(Successor) \(S : \mathbb{N} \rightarrow \mathbb{N}\) is a PRF.
For each \(x \in \mathbb{N}\), \(\:S(x) = x + 1\).(Projection) \(I_{n,i} : \mathbb{N}^n \rightarrow \mathbb{N}\) is a PRF.
For each \(\vec{x} \in \mathbb{N}^n\), \(\:I_{n,i}(\vec{x}) = x_i\). (Using zero-based indexing)
Inductive:
(Composition) \(C_{f,(g_0,...,g_{k-1})} : \mathbb{N}^n \rightarrow \mathbb{N}\) is a PRF.
It is based on a PRF \(f : \mathbb{N}^k \rightarrow \mathbb{N}\) and \(k\) PRFs \(g_0, \ldots, g_{k-1}\) each of type \(\mathbb{N}^n \rightarrow \mathbb{N}\).
For each \(\vec{x} \in \mathbb{N}^n\), \(\: C_{f,(g_0,...,g_{k-1})}(\vec{x}) = f(g_0(\vec{x}), \ldots, g_{k-1}(\vec{x}))\).(Primitive recursion) \(R_{f,g} : \mathbb{N}^{n+1} \rightarrow \mathbb{N}\) is a PRF.
It is based on a PRF \(f : \mathbb{N}^n \rightarrow \mathbb{N}\) and a PRF \(g : \mathbb{N}^{n+2} \rightarrow \mathbb{N}\).
For each \((y, \vec{x}) \in \mathbb{N}^{n+1}\), \(\: R_{f,g}(y, \vec{x}) = \begin{cases} f(\vec{x}), & \text{if } y = 0 \\ g(R_{f,g}(y-1, \vec{x}), y-1, \vec{x}), & \text{if } y \ge 1 \end{cases}\).
Source code
Python version: primrecfunc.py, primrecfunctest.py
Haskell version: PrimRecFunc.hs, PrimRecFuncTest.hs
PrimRecFuncTest can be run as a main program. PrimRecFunc contains data structures that you can use to build your own computations. PrimRecFunc also contains a library of useful PRFs for arithmetic, Boolean logic, and comparisons. This library of PRFs is described near the bottom of the page.
Python code
Data type: PrimRecFunc
PrimRecFunc is a class that represents a primitive recursive function. To get a PRF, use one of these subclass objects or constructors:
Zis an object, taking no parameters.Sis an object, taking no parameters.I(n,i)is a constructor that takes two integers:nis the size of the input vector, andiis the index to extract.
Zero-based indexing is used.C(f,gs)is a constructor that takes a PRFffollowed by a list of PRFsgs = [g_0, ..., g_{k-1}].
These PRFs must have the correct number of input arguments, but this is not checked when theCis constructed.R(f,g)is a constructor that takes a PRFffollowed by a PRFg.
These PRFs must have the correct number of input arguments, but this is not checked when theRis constructed.
Examples:
I(3,1)represents the PRF \(I_{3,1}(x, y, z) = y\).C(S, [Z])represents the PRF \(C_{S,(Z)}(x) = S(Z(x)) = S(0) = 1\).C(R(Z, I(3,1)), [Z, I(1,0)])represents the PRF
\(C_{R_{Z, I_{3,1}}, (Z, I_{1,0})}(x) = R_{Z, I_{3,1}}(Z(x), I_{1,0}(x)) = R_{Z, I_{3,1}}(0, x) = \max(x - 1, 0)\).R(I(1,0), C(S, [I(3,0)]))(2 input arguments) computes \(x + y\).R(Z, C(add, [I(3,0), I(3,2)]))(2 input arguments) computes \(xy\).C(R(const(1), C(mul, [C(S, [I(3,1)]), I(3,0)])), [I(1,0), Z])(1 input argument) computes \(x!\).
Evaluation: PrimRecFunc.eval()
To evaluate a PRF f with a vector (list) of natural numbers xs, use the expression f.eval(xs), which yields a natural number.
Examples:
Z.eval([3]) = 0.S.eval([1]) = 2.I(4,2).eval([9, 8, 7, 6]) = 7.
Extra features
The
Nativesubclass allows you to smuggle a native Python function as aPrimRecFunc, which can let you speed up function evaluation. For example:mul = Native(lambda xs: xs[0] * xs[1]). For example, theprimefunction uses the PRFdivisible, which can be substituted for a faster native function. Generally, if you are replacing a PRF with a native function, you should ensure that the PRF has been mathematically proven to be correctly implemented.
Haskell code
Data type: Prf
data Prf = Z | S | I Int Int | C Prf [Prf] | R Prf Prf | Native ([Int] -> Int)
Prf is a data type representing a primitive recursive function. To get a PRF, use one of these data constructors:
Zis immediately usable, taking no parameters.Sis immediately usable, taking no parameters.Itakes two integers: the first is the size of the input vector, and the second is the index to extract.
Zero-based indexing is used.Ctakes a PRF \(f\) followed by a list of PRFs \(g_0, \ldots, g_{k-1}\).
These PRFs must have the correct number of input arguments, but this is not checked when theCis constructed.Rtakes a PRF \(f\) followed by a PRF \(g\).
These PRFs must have the correct number of input arguments, but this is not checked when theRis constructed.
Examples:
I 3 1represents the PRF \(I_{3,1}(x, y, z) = y\).C S [Z]represents the PRF \(C_{S,(Z)}(x) = S(Z(x)) = S(0) = 1\).C (R Z (I 3 1)) [Z, I 1 0]represents the PRF
\(C_{R_{Z, I_{3,1}}, (Z, I_{1,0})}(x) = R_{Z, I_{3,1}}(Z(x), I_{1,0}(x)) = R_{Z, I_{3,1}}(0, x) = \max(x - 1, 0)\).R (I 1 0) (C S [I 3 0])(2 input arguments) computes \(x + y\).R Z (C add [I 3 0, I 3 2])(2 input arguments) computes \(xy\).C (R (const 1) (C mul [C S [I 3 1], I 3 0])) [I 1 0, Z](1 input argument) computes \(x!\).
Evaluation: eval
eval :: Prf -> [Int] -> Int
To evaluate a PRF f with a vector (list) of natural numbers xs, use the expression eval f xs, which yields a natural number.
Examples:
eval Z [3] = 0.eval S [1] = 2.eval (I 4 2) [9, 8, 7, 6] = 7.
Extra features
The
Nativedata constructor allows you to smuggle a native Haskell function as aPrf, which can let you speed up function evaluation. For example:mul = Native (\[x, y] -> x * y). For example, theprimefunction uses the PRFdivisible, which can be substituted for a faster native function. Generally, if you are replacing a PRF with a native function, you should ensure that the PRF has been mathematically proven to be correctly implemented.The
checkAndGetArgsfunction calculates the number of input arguments that the givenPrftakes, and it also checks that the entire function structure is internally consistent.The
evalCountfunction is an extension ofevalthat returns a tuple of numbers: (result, number of evaluation steps, maximum recursion depth). This can help in understanding PRFs evaluations that run slowly and PRFs evaluations that overflow the stack.
Notes
If you are using the Glasgow Haskell Compiler (GHC), using compiled mode instead of interpreted mode will make the code run much faster.
Library of primitive recursive functions
These included PRFs serve as excellent examples of how to implement familiar, useful functions in terms of PRFs.
Boolean functions (0 means false, 1 means true, and all other values cause unspecified behavior):
not: NOT (1 argument) (namedprnotin the Python version)and: AND (2 arguments) (namedprandin the Python version)or: OR (2 arguments) (namedprorin the Python version)xor: XOR (2 arguments) (namedprxorin the Python version)mux: Multiplex/select (3 arguments)
Comparison functions (each returns a Boolean value):
z: Is zero (1 argument)nz: Is nonzero (1 argument)eq: Equal (2 arguments)neq: Not equal (2 arguments)lt: Less than (2 arguments)le: Less than or equal (2 arguments)gt: Greater than (2 arguments)ge: Greater than or equal (2 arguments)even: Is even (1 argument)odd: Is odd (1 argument)divisible: Is divisible (2 arguments)prime: Is prime (1 argument)
Arithmetic functions:
const n: Constant (1 argument)pred: Predecessor (1 argument)add: Addition (2 arguments)sub: Subtraction (2 arguments)subrev: Reverse subtraction (2 arguments)diff: Absolute difference (2 arguments)min: Minimum (2 arguments)max: Maximum (2 arguments)mul: Multiplication (2 arguments)pow: Power/exponentiation (2 arguments)sqrt: Square root (1 argument)log: Logarithm (2 arguments)div: Truncating division (2 arguments)mod: Modulo (2 arguments)factorial: Factorial (1 argument)gcd: Greatest common divisor (2 arguments)lcm: Least common multiple (2 arguments)divisiblecount: Divisibility count (2 arguments)nthprime: nth prime number (1 argument)fibonacci: Fibonacci sequence (1 argument)
Bitwise functions:
shl: Left shift (2 arguments)shr: Right shift (2 arguments)band: Bitwise AND (2 arguments)bandnot: Bitwise AND-NOT (2 arguments)bor: Bitwise OR (2 arguments)bxor: Bitwise XOR (2 arguments)getbit: Get bit (2 arguments)
Read the test programs for examples of the input/output values of each library function: primrecfunctest.py, PrimRecFuncTest.hs
Mathematical properties
All primitive recursive functions terminate, and thus are computable.
The set of all PRFs has countable cardinality. Thus it is a strict subset of the set of all natural number functions, which has uncountable cardinality.
A non-PRF can be constructed by diagonalizing on the set of PRFs. Also, the Ackermann function is specifically a non-PRF.
As shown in the code and examples, these basic functions are primitive recursive: addition, multiplication, factorial.
