Enumerating the primitive recursive functions

Question

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[0];
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:

enter image description here

enter image description here

enter image description here

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 addition(12, 6)
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):
 return expression.head(*map(lambda argument: parse(argument), expression.arguments))
 else:
 return expression

For example, the predecessor function can be represented as

predecessorExpression = Expression(
 head=recursion,
 arguments=(
 zero,
 Expression(
 head=projection,
 arguments=(
 Expression(
 head=successor,
 arguments=(
 Expression(
 head=zero,
 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.

• sacundim: 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?
• user76284: @sacundim Clarified.
• Winston Ewert: Why are you trying to do this?
• user76284: @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.
• Winston Ewert: 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.

Answer 1

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[0].arity
 self._g = g
 self._h = h
 self.arity = h[0].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 addition(12, 6) == 18
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