Primitive Rekursion in Python

# Zum Rumprobieren diese Datei einfach laden mit -i (python[3] -i <Dateiname>) (zunächst kopieren/herunterladen).
# Warnung! Alle Funktionen hier sind auf natürliche Zahlen ausgelegt und bei negativen machen sie Quatsch.
# Die Funktionalität ist stark durch das Rekursionslimit bzw. die Stackgröße limitiert (naive Implementation).
# z.B. eine Fakultätsfunktion kann schon bei Eingabe Sieben das Limit überschreiten.
# Die Namen sind lang aber es werden weiter unten Abkürzungen definiert (Zeile 49).
# Beispiele add und mul sind bei Zeile 58.


# ==DEFINITIONEN==

# Komposition (f o (g_1, ...))
# Zweites Argument ist immer ein Tupel
def compose(f, gs, /):  # die Schrägstriche sind dafür da dass man es nicht als Schlüsselwortparameter übergeben kann
    def composition(*args):
        return f(*(g(*args) for g in gs))

    return composition


# Primitive Rekursion (pr(h, g))
def primitive_recursion(h, g, /):
    def f(n, /, *args):
        if n == 0:
            return g(*args)
        return h(n - 1, f(n - 1, *args), *args)

    return f


# Projektion (pi_k^n)
# Nicht Null-indiziert sondern Eins-indiziert
# Da Python nicht streng typisiert ist, muss die Tupelgröße nicht festgelegt werden
# also pi_17^78 = projection(17)
def projection(n, /):
    return lambda *args: args[n - 1]


# Nachfolger (succ)
def successor(n, /):
    return n + 1


# Konstante (n_k)
# Hier muss ebenfalls die Stelligkeit nicht angegeben werden
def constant(n, /):
    return lambda *args: n


# ==ABKÜRZUNGEN==

comp = compose
pr = primitive_recursion
pi = projection
succ = successor
const = constant


# ==BEISPIELE==

# add = pr(succ o pi_2^3, pi_1^1)
add = pr(comp(succ, (pi(2),)), pi(1))
                   # ^^^^^^^ Wichtig: compose/comp nimmt Tupel (bzw. Iterables),
                   #      ^  bei Einstelligkeit Komma nicht vergessen!

# mul = pr(add o (pi_2^3, pi_3^3), 0_1)
mul = pr(comp(add, (pi(2), pi(3))), const(0))


# ==SELBSTTEST==

from itertools import product
from sys import argv

# Wird nur ausgeführt wenn Command-Line-Argument "test" übergeben wird
if __name__ == '__main__':
    if len(argv) == 2 and argv[1] == 'test':
        for n, m in product(range(20), repeat=2):  # wesentlich größere Zahlen überschreiten das Rekursionslimit
            assert add(n, m) == n + m
            assert mul(n, m) == n * m