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 \rightarrow \mathbb{N}\). The set of all possible PRFs is constructed in a special way, using only these 5 building blocks:

Basic:

Inductive:

Properties of PRFs:

Source code

Python version: primrecfunc.py, primrecfunctest.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:

Examples:

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:

Extra features

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:

Examples:

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:

Extra features

Notes

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:

Examples:

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:

Extra features


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):

Comparison functions (each returns a Boolean value):

Arithmetic functions:

Bitwise functions:

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

More info