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:

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.

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