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.


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)
            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))
        return expression

For example, the predecessor function can be represented as

predecessorExpression = Expression(

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?
    – sacundim
    Feb 4, 2016 at 0:37
  • @sacundim Clarified.
    – user76284
    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.
    – user76284
    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

1 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)
           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.
    elif size == 1:
        # for size one, only the trivial functions can be generated
        yield Zero()
        yield Successor()
        # 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 []
        # 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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.