# 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
- Source code
- Python code guide
- Haskell code guide
- Java code guide
- Library of primitive recursive functions
- More info

## 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}\).

Properties of PRFs:

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.

## 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 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 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 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 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`

:`n`^{th}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