Enumerazione delle funzioni ricorsive primitive

Ecco il codice 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