Project Nayuki

Primitive recursive functions

This page explains what primitive recursive functions (PRFs) are, provides runnable code (Python, Haskell, Java) for constructing and evaluating them, and includes a large library of familiar arithmetic functions implemented as PRFs.

Contents

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 → \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} → \mathbb{N}\) is a PRF.
    For each \(x ∈ \mathbb{N}\), \(\:Z(x) = 0\).

  • (Successor) \(S : \mathbb{N} → \mathbb{N}\) is a PRF.
    For each \(x ∈ \mathbb{N}\), \(\:S(x) = x + 1\).

  • (Projection) \(I_{n,i} : \mathbb{N}^n → \mathbb{N}\) is a PRF.
    For each \(\vec{x} ∈ \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 → \mathbb{N}\) is a PRF.
    It is based on a PRF \(f : \mathbb{N}^k → \mathbb{N}\) and \(k\) PRFs \(g_0, \ldots, g_{k-1}\) each of type \(\mathbb{N}^n → \mathbb{N}\).
    For each \(\vec{x} ∈ \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} → \mathbb{N}\) is a PRF.
    It is based on a PRF \(f : \mathbb{N}^n → \mathbb{N}\) and a PRF \(g : \mathbb{N}^{n+2} → \mathbb{N}\).
    For each \((y, \vec{x}) ∈ \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 ≥ 1 \end{cases}\).

Properties of PRFs:

  • Every primitive recursive function terminates on every input, thus these functions 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.

Source code

Python version: primrecfunc.py, primrecfunc-test.py

Haskell version: PrimRecFunc.hs, PrimRecFuncTest.hs

Java version: Prf.java, PrfTest.java

(All versions are designed to have the same set of features. Please choose the language that is most familiar or convenient for you.)

PrimRecFuncTest contains an extensive test suite for each function, and it 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 guide

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:

  • Z is an object.

  • S is an object.

  • I(n,i) is a constructor that takes two integers: n is the size of the input vector, and i is the index to extract.
    Zero-based indexing is used.

  • C(f,gs) is a constructor that takes a PRF f followed by a list of PRFs gs = [g_0, ..., g_{k-1}].
    These PRFs must have the correct number of input arguments, but this is not checked when the C is constructed.

  • R(f,g) is a constructor that takes a PRF f followed by a PRF g.
    These PRFs must have the correct number of input arguments, but this is not checked when the R is 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 Native subclass allows you to smuggle a native Python function as a PrimRecFunc, which can let you speed up function evaluation. For example: mul = Native(lambda xs: xs[0] * xs[1]). For example, the prime function uses the PRF divisible, which can be substituted for a faster native function. Generally, if you are replacing a PRF with a native function, you should first ensure that the PRF has been mathematically proven to be correctly implemented.

Haskell code guide

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:

  • Z is immediately usable, taking no parameters.

  • S is immediately usable, taking no parameters.

  • I takes two integers: the first is the size of the input vector, and the second is the index to extract.
    Zero-based indexing is used.

  • C takes 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 the C is constructed.

  • R takes a PRF \(f\) followed by a PRF \(g\).
    These PRFs must have the correct number of input arguments, but this is not checked when the R is 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: 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 Native data constructor allows you to smuggle a native Haskell function as a Prf, which can let you speed up function evaluation. For example: mul = Native (\[x, y] -> x * y). For example, the prime function uses the PRF divisible, which can be substituted for a faster native function. Generally, if you are replacing a PRF with a native function, you should first ensure that the PRF has been mathematically proven to be correctly implemented.

  • The checkAndGetArgs function calculates the number of input arguments that the given Prf takes, and it also checks that the entire function structure is internally consistent.

  • The evalCount function is an extension of eval that 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.

Java code guide

Data type: Prf

Prf is a class that represents a primitive recursive function. To get a PRF, use one of these subclass objects or constructors:

  • Z is an object.

  • S is an object.

  • I(int n, int i) is a factory method that takes two integers: n is the size of the input vector, and i is the index to extract.
    Zero-based indexing is used.

  • C(Prf f, Prf... gs) is a factory method that takes a PRF f followed by a list of PRFs gs = {g_0, ..., g_{k-1}}.
    These PRFs must have the correct number of input arguments, but this is not checked when the C is constructed.

  • R(Prf f, Prf g) is a factory method that takes a PRF f followed by a PRF g.
    These PRFs must have the correct number of input arguments, but this is not checked when the R is 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(konst(1), C(mul, C(S, I(3,1)), I(3,0))), I(1,0), Z) (1 input argument) computes \(x!\).

Evaluation: Prf.eval()

To evaluate a PRF f with an array or varargs 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

  • You can smuggle a native Java function as a Prf by subclassing Prf and implementing eval() and toString(). This can let you speed up function evaluation for large arguments or very complicated functions. For example, the prime function uses the PRF divisible, which can be substituted for a faster native function. Generally, if you are replacing a PRF with a native function, you should first ensure that the PRF has been mathematically proven to be correctly implemented.

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 input values yield arbitrary output values):

  • not: NOT (1 argument) (named prnot in the Python version)
  • and: AND (2 arguments) (named prand in the Python version)
  • or: OR (2 arguments) (named pror in the Python version)
  • xor: XOR (2 arguments) (named prxor in 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) (named konst in the Java version)
  • 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)

To see examples of input/output values for each library function, please read the test suites: primrecfunc-test.py, PrimRecFuncTest.hs, PrfTest.java

More info