# Enumerating the primitive recursive functions

How can I enumerate (by expression tree size, for example) all of the primitive recursive functions that map natural numbers to natural numbers in a traditional programming language like C?

For example, in Mathematica, one can express the basic primitive recursive functions as follows:

``````zero = Function;
succ = Function[# + 1];
proj[n_Integer] = Function[Part[{##}, n]];
comp[f_, gs__] = Function[Apply[f, Through[{gs}[##]]]];
prec[f_, g_] =
Function[If[#1 == 0, f[##2], g[#1 - 1, #0[#1 - 1, ##2], ##2]]];
``````

Hence, for example, the primitive recursive expression trees for addition, predecessor, and monus (truncated subtraction) are:   Ideally it should be possible to actually evaluate these primitive recursive functions on the natural numbers, so that one can obtain the outputs of these functions on them.

EDIT:

For example, here are the basic primitive recursive functions implemented in Python:

``````def zero():
# Takes no arguments
# Returns zero
return 0

def successor(x):
# Takes a natural number
# Returns its successor
return x + 1

def projection(n):
# Takes at least n+1 arguments
# Returns the nth argument
def f(*x):
return x[n]
return f

def composition(g, *h):
# Takes a k-ary function and k m-ary functions
# Returns an m-ary function
def f(*x):
return g(*map(lambda h_: h_(*x), h))
return f

def recursion(g, h):
# Takes a k-ary function and a (k+2)-ary function
# Returns a (k+1)-ary function
def f(n, *x):
if n == 0:
return g(*x)
else:
return h(f(n - 1, *x), n - 1, *x)
return f
``````

Hence we can implement addition, predecessor, and monus (truncated subtraction) as follows:

``````addition = recursion(projection(0), composition(successor, projection(0)))
predecessor = recursion(zero, projection(1))
monus = recursion(projection(0), composition(predecessor, projection(0)))

print predecessor(16)
print monus(10, 19)
``````

I then constructed a way to represent (and parse/evaluate) the structure of different primitive recursive functions:

``````Expression = collections.namedtuple('Expression', ['head', 'arguments'])

def parse(expression):
if isinstance(expression, Expression):
else:
return expression
``````

For example, the predecessor function can be represented as

``````predecessorExpression = Expression(
arguments=(
zero,
Expression(
arguments=(
Expression(
arguments=(
Expression(
arguments=()
),
)
),
)
)
)
)
``````

The parser works successfully when evaluating the predecessor expression:

``````predecessorFunction = parse(predecessorExpression)
print predecessorFunction(42)
``````

What remains is to construct the expression trees that represent the primitive recursive functions. Does anyone know what the best way to approach this would be?

EDIT 2: Just came across this promising paper.

• I think you need to define your problem better to get a concrete answer. For example, do you expect the C (or other language) program to print a sequence of descriptions that correspond to all the primitive recursive functions? Or to actually be able to execute all such functions as well? Feb 4, 2016 at 0:37
• @sacundim Clarified. Feb 4, 2016 at 5:52
• Why are you trying to do this? Feb 13, 2016 at 3:02
• @WinstonEwert One reason is I'm interested in seeing what "small" primitive recursive functions are like and where familiar elementary functions like predecessor, addition, truncated subtraction, multiplication, etc. of increasing complexity tend to emerge in the hierarchy. Feb 13, 2016 at 4:15
• Ok, then you need to define exactly what you mean by small. How are you intending to measure the size? There are lots of variations, so you'll need to pick one. Feb 13, 2016 at 6:28

Here is the code in python.

``````# Define common function logic
class Function(object):

def __repr__(self):
return '{}[{}]'.format(self.__class__.__name__, ",".join(map(repr, self.arguments())))

def __call__(self, *args):
# make sure that a function isn't lying about its arity
assert len(args) == self.arity
return self.call(*args)

# define each of the basic elements of primitive recursive functions.
# each type of function is implements a call() method to perform the
# the function. It also has an "arity" attribute which tells us what
# the arity of the function is.

# Each function type checks its arguments for sanity, the construct
# should raise an exception if the arities are not correct.

class Zero(Function):
arity = 0

def arguments(self):
return []

def call(self):
return 0

class Successor(Function):
arity = 1

def arguments(self):
return []

def call(self, other):
return other + 1

class Projection(Function):
def __init__(self, item, arity):
assert item.arity == 0
assert arity.arity == 0

self._item = item
self._arity = arity

self.arity = arity()

def arguments(self):
return [self._item, self._arity]

def call(self, *args):
return args[self._item()]

class Composition(Function):
def __init__(self, g, h):

assert len(h) == g.arity
for function in h:
assert function.arity == h.arity

self._g = g
self._h = h
self.arity = h.arity

def arguments(self):
return [self._g] + self._h

def call(self, *x):
return self._g(*(h(*x) for h in self._h))

class Recursion(Function):
def __init__(self, g, h):
assert h.arity == g.arity + 2

self._g = g
self._h = h

self.arity = g.arity + 1

def arguments(self):
return [self._g, self._h]

def call(self, n, *x):
if n == 0:
return self._g(*x)
else:
return self._h(self(n - 1, *x), n - 1, *x)

# We can build various integers by using composition and successor.
zero = Zero()
one = Composition(Successor(), [zero])
two = Composition(Successor(), [one])
three = Composition(Successor(), [two])

# Take the three examples from the original post, and make sure
# they work.
addition = Recursion(Projection(zero, one), Composition(Successor(), [Projection(zero, three)]))
predecessor = Recursion(Zero, Projection(one, two))
monus = Recursion(Projection(zero, one), Composition(predecessor, [Projection(zero, three)]))

assert predecessor(16) == 15
assert monus(10, 19) == 9

def functions(size):
"""
Generate all possible functions of a given size
"""
if size <= 0:
# for 0 or negative size, we cannot generate the function.
pass
elif size == 1:
# for size one, only the trivial functions can be generated
yield Zero()
yield Successor()
else:
# for any other size, see what can be created of the various
# types.
for composition in compositions(size):
yield composition
for projection in projections(size):
yield projection
for recursionion in recursions(size):
yield recursionion

def functions_with_maxsize(size):
"""
For a given size, return an iterator over the sequence of functions
up to that size, along with the remaining size.
"""
for subsize in range(1, size + 1):
for function in functions(subsize):
yield function, size - subsize

def compositions(size):
"""
Return all possible compositions that can be constructed with the
given size
"""
# - 1 is for the composition node itself.
# First, we pick the "head" function.
for g, after_g_size in functions_with_maxsize(size - 1):
if g.arity > 0:
# generate all possible lists of arguments to the function.
for function_list in composition_function_lists(g.arity, after_g_size):
yield Composition(g, function_list)

def composition_function_lists(length, size, arity = None):
"""
Generate the sequence of possible lists of function with the given
length, size, and arity.
"""
# the trivial case, the only valid case for length zero is zero cost.
if length == 0:
if size == 0:
yield []
else:
pass
else:
# pick the next function
for function, remaining_size in functions_with_maxsize(size):
if arity is None or arity == function.arity:
# build all possible lists of size n - 1,
# then add this function to the start of that list.
for sublist in composition_function_lists(length - 1, remaining_size, function.arity):
yield [function] + sublist

def projections(size):
"""
Generate all possible projections functions of the given size
"""
for function, size_2 in functions_with_maxsize(size - 1):
if function.arity == 0:
for function2 in functions(size_2):
if function2.arity == 0:
# the index must be less then the arity.
if function() < function2():
yield Projection(function, function2)

def recursions(size):
"""
Generate all possible recursions
"""
for function, size_2 in functions_with_maxsize(size - 1):
for function2 in functions(size_2):
if function2.arity == function.arity + 2:
yield Recursion(function, function2)

for function, _ in functions_with_maxsize(20):
print function
``````