Enumerating the primitive recursive functions
https://softwareengineering.stackexchange.com/questions/308978
-
11-12-2020 - |
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.
Solution
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