3.2 Primitive Rekursion: Konstruktionen und Tricks

Ich beginne dieses Teilkapitel, manche der primitiv-rekursive Implementierungen in stockpile.py zu erklären und werde dann weitere, weniger offensichtliche Konstruktionen diskutieren.

Arithmetische Operationen

Wir haben bereits gesehen, dass wir die Addition per \({\rm add} = \primrec (\pi_0, \comp(\succ, \pi_0)) \) schreiben können. Beachten Sie, dass ich hier die Indizierung immer bei 0 beginnen lasse, im Python-Code sowie im Mathematik-Modus (in der Vorlesung hatte ich an der Tafel das oft bei 1 beginnen lassen, entschuldigen Sie die Inkonsistenz). Multiplikation geht nach dem gleichen Schema. Wir schreiben mult in der Schleifenform, wie sie die primitive Rekursion zulässt, und schreiben in Orange auch gleich die Funktionen \(g\) und \(h\) dazu:

def mult(t,x):
    temp = 0 = zero(x)
    for i in range(t):
        temp = add(temp,x) = Comp(add, p_0, p2) (temp,i,x)
    return temp

erinnern Sie sich daran: \(h\) muss immer eine Funktion in der lokalen Variable temp, der Laufvariable \(i\) und \(\vec{x}\) sein. Daher: \begin{align*} {\rm mult} = \primrec(\zero, \comp({\rm add}, \pi_0, \pi_2)) \end{align*} Genauso erhalten wir \(x^t\), indem wir statt bei 0 bei 1 beginnen und statt \(x\) draufzuzählen, es draufmultiplizieren: \begin{align*} {\rm expReverse} = \primrec({\rm one}, \comp({\rm mult}, \pi_0, \pi_2)) \end{align*} Allerdings gibt uns das \((t,x) \mapsto x^t\). Für \({\rm exp}(a,b) = a^b\) müssen wir die Argumente umdrehen: \begin{align*} {\rm exp} = \comp({\rm expReverse}, \pi_1, \pi_0) \end{align*} Die Fakultätsfunktion \(t!\) ist konzeptuell ähnlich, allerdings etwas interessanter, weil wir hier auf das Zwischenergebnis und die Laufvariable zugreifen müssen:

def factorial(t):
    temp = 1 = one()
    for i in range(t):
        temp = mult(temp,i+1) = Comp(mult, p_0, Comp(succ, p_1)) (temp,i)
    return temp

Wir können nicht einfach \(i+1\) schreiben! Wir müssen dies via \(\comp(\succ,\pi_1)\) konstruieren. Denn: die Funktion \(h\) bekommt \({\rm temp}, i, \vec{x}\) als Input; \(\pi_1\) gibt uns davon das \(i\) zurück und \(\comp(\succ, \pi_1)\) gibt uns \(i+1\).

Operationen wie \(\pred: t \mapsto t-1\) und \({\rm minus}\) sind konzeptuell nur ein bisschen anders. Das liegt auch daran, dass wir keine negativen Zahlen haben. Was ist \(\pred(0)\)? Wir definieren das als 0. So können wir pred implementieren:

def pred(t):
    temp = 0 = zero()
    for i in range(t):
        temp = i = p1 (temp,i) 
    return temp

In Worten: wenn \(t=0\), dann geben wir einfach \(\zero()\) zurück, also \(0\). Ansonsten durchlaufen wir die Schleife \(t\) mal; der letzte Schleifenindex ist \(t-1\), und das ist dann auch der Wert von temp, der zurückgegeben wird. Daher: \begin{align*} \pred = \primrec(\zero, \pi_1) \end{align*}

Für minus schreiben wir uns erst mal \({\rm subtractFrom}: (t,x) \mapsto x-t\). Hierfür wenden wir einfach pred \(t\) mal auf \(x\) an: \begin{align*} {\rm subtractFrom} & = \primrec(\pi_0, \comp(\pred, \pi_0)) \\ {\rm minus} & = \comp({\rm subtractFrom}, \pi_1, \pi_0) \end{align*}

Boolesche Werte

Die primitive Rekursion stellt uns als "Datentyp" nur die natürlichen Zahlen zur Verfügung. Alles andere müssen wir als natürliche Zahlen nach einem von uns selbst gewählten Schema codieren. Für Boolesche Werte ist das recht naheliegend. Wir codieren True als 1 und False als 0. Unser erstes Prädikat, also Funktion mit Booleschem Ausgabewert, ist isPositive:

def pred(t):
    temp = 0 = zero()
    for i in range(t):
        temp = 1 = one 
    return temp

und somit \begin{align*} {\rm isPositive} = \primrec(\zero, {\rm one}) \end{align*}

Auf ähnliche Weise können wir uns nun lessThan, lessEqual, and, or, not, ifThenElse konstruieren.

Wurzel und Suchen im Allgemeinen

Eine größere Herausforderung stellt die ganzzahlige Wurzel \(x \mapsto \floor{\sqrt{x}}\) dar. Hierfür haben wir keine Formel mit \(+, *, -\), auch keine schöne rekursive Formel zur Hand. Es handelt sich um ein Suchproblem:

\(\floor{\sqrt{x}}\) ist die größte natürliche Zahl \(i\) mit \(i^2 \leq x\).

Wir können auch den Suchraum begrenzen: da \(\sqrt{x} \leq x\) für alle natürlichen Zahlen, so gilt:

\(\floor{\sqrt{x}}\) ist die größte natürliche Zahl \(i \in \{0,1,\dots,x\}\) mit \(i^2 \leq x\).

Das Prädikat \begin{align*} {\rm iSquareLessEqualX } (i,x) & = [ i^2 \leq x ] \end{align*} ist primitiv rekursiv: \begin{align*} {\rm iSquareLessEqualX } = \comp({\rm lessEqual}, \comp({\rm mult}, \pi_0, \pi_0), \pi_1) \end{align*} und damit können wir die ganzzahlige Wurzel schreiben als

def largestIbelowTwithISquareLessEqualX(t,x):
    temp = 0 = zero(x)
    for i in range(t):
        temp = ifThenElse(iSquareLessEqualX(i,x), i, temp) = Comp(ifThenElse, Comp(iSquareLessEqual, p_1, p_2), p_1, p_0) (temp,i,x)
    return temp

Was geht hier vor? Wenn \({\rm iSquareLessEqualX}(i,x))\) True ist, dann ersetzen wir temp durch \(i\). Ansonsten belassen wir es beim alten Wert; der endgültige Wert von temp ist also das letzte \(i\), für das das Prädikat True wahr.

\begin{align*} {\rm largestIbelowTwithISquareLessEqualX = \primrec(zero, \comp(ifThenElse, \comp(iSquareLessEqual, \pi_1, \pi_2), \pi_1, \pi_0))} \end{align*} Und schließlich ist \begin{align*} {\rm sqrt} = \comp({\rm largestIbelowTwithISquareLessEqualX}, \pi_0, \pi_0) \end{align*} da wir zum Suchen der Wurzel von \(t\) gleich \(t\) als Obergrenze des Suchraumes angeben können. Ganz allgemein können wir für ein Prädikat \({\rm predicate}(i,x)\) das größte \(i \in \{0,\dots,t\}\) finden, für das \({\rm predicate}(i,x)\) True ergibt. Da wir wissen, wie wir das primitiv rekursiv machen können, erlauben wir uns, einen neuen Kombinator zu definieren, anstatt diese Konstruktion jedes Mal "von Hand" durchzuführen:

def LargestLessThan(upperBound, predicate):
	def new_function(*x):
		temp = 0 
		for i in range(upperBound(*x)):
			if (predicate(i,*x)):
				temp = i 
		return temp 
	return new_function

und somit können wir sqrt schreiben als

\begin{align*} {\rm sqrt} = {\rm LargestLessThan} (\pi_0, {\rm iSquareLessEqual}) \end{align*}

Paare und Listen

Eine recht stark anmutende Beschränkung primitiv rekursiver Funktionen ist die Tatsache, dass wir in der Schleife nur eine lokale Variable führen dürfen, hier meistens temp genannt. Manche Funktionen scheinen inhärent mindestens zwei zu benötigen. Betrachten wir den Fall der Fibonacci-Zahlen:

def fibIterative(t):
    a = 0
    b = 1
    for i in range(t):
        c = a+b 
        a = b 
        b = c 
    return a

Wir führen hier zwei lokale Variable, \(a\) und \(b\). Das \(c\) könnten wir mit diesem schönen Trick eliminieren:

b = a+b 
a = b-a

Doch selbst dann hätten wir immer noch zwei lokale Variable. Die Fibonacci-Zahlen rekursiv per return F(n-1)+F(n-2) scheint noch weiter weg zu sein vom Paradigma der primitiven Rekursion; primitive Rekursion verzweigt sich nie. Dennoch ist es möglich, fib primitiv rekursiv zu implementieren. Hauptzutat hierbei ist es, dass wir Paare als neue Datenstruktur verwenden.

Erinnern Sie sich: die primitive Rekursion stellt uns als Datentyp von Haus aus nur die natürlichen Zahlen zur Verfügung. Alles andere müssen wir nach einem selbst gewählten Schema codieren. Bei Booleschen Werten war es einfach. Wie steht es mit Paaren von natürlichen Zahlen? In Kapitel 2: Unendliche Mengen haben wir die bijektive Funktion

\begin{align*} \pair : \N^2 & \rightarrow \N \\ (x,y) & \mapsto {x + y + 1 \choose 2} + x \end{align*} kennengelernt. Diese Funktion ist primitiv rekursiv: es gilt \({n \choose 2} = 1 + 2 + \cdots + (n-1)\) und somit

def choose2(t):
    temp = 0 = zero()
    for i in range(t):
        temp = add(temp,i) = Comp(add, p0, p1)

und somit \begin{align*} {\rm choose2} & = \primrec(\zero, \comp({\rm add},\pi_0,\pi_1)) \\ \pair & = \comp( {\rm add}, \comp({\rm choose2}, \comp({\rm add}, \pi_0, \comp(\succ, \pi_1))), \pi_0) \end{align*}

Um die Umkehrfunktionen \(\first, \second\) zu implementieren, die uns aus \(\pair(x,y)\) wieder \(x\) und \(y\) berechnen, bestimmen wir erst den Wert von \(x+y\). Wenn \(\pair(x,y) = n\) gilt und \(x+y=i\) ist, dann ist \begin{align*} n = \pair(x,y) = {i + 1 \choose 2} + x \geq {i+1 \choose 2} + 0 = \pair(0,i) \ , \end{align*} und somit ist \(x+y\) der größte Wert von \(i\), so dass \(n \geq \pair(0,i)\) ist. Aus \(x+y\) und \({x+y+1 \choose 2} + x\) können wir dann leicht \(x\) und \(y\) berechnen:

\begin{align*} {\rm getXplusY} & = {\rm LargestLessThan}(\pi_0, \comp({\rm greaterEqual}, \pi_1, \comp(\pair, \zero, \pi_0)))\\ \first & = \comp({\rm minus}, \pi_0, \comp(\pair, \zero, {\rm getXplusY}))\\ \second & = \comp({\rm minus}, {\rm getXplusY}, \first) \end{align*}

Listen können wir implementieren, indem wir Paare verschachtelt zusammenhängen, z.B. \([5,7,9]\) wird zu \(\pair(5, \pair(7, 9))\). Das ist natürlich inkorrekt:

pair(5,pair(7,9))                        
11031
pair(7,9)
143
pair(5,143)
11031

Das Problem ist, dass wir das Ende der Liste nicht kennen. Wir lösen das Problem, indem wir die leere Liste mit \(0\) codieren und dann aber beim Davorhängen eines Elements 1 draufaddieren müssen, also

\begin{align*} {\rm push} (x, {\rm restlist}) & = 1 + \pair(x, {\rm restlist}) \\ {\rm head} ({\rm list}) & = \first({\rm list} - 1)\\ {\rm second} ({\rm list}) & = \second({\rm list} - 1) \end{align*}

Jetzt klappt alles wunderbar:

push(11, push(7, push(5, 0)))                        
90537
head(90537)
11
head(tail(90537))
7

head(tail(tail(90537))) 5

Native Implementierung. Die primitive Rekursion ist ein theoretischer Berechenbarkeitsbegriff für Funktionen auf natürlichen Zahlen. Es ist definitiv keine ernstzunehmende Programmiersprache. Ich finde allerdings, dass es hilfreich ist, sie als Programmiersprache zu begreifen und zu verwenden, rein experimentell. Leider ist sie extrem ineffizient: selbst Subtraktion hat quadratische Komplexität. Längere Listen wie die gerade werden Sie in vertretbarer Zeit nicht behandeln können. Bei meinen eigenen Experimenten mit meinem Python-Framework bin ich daher dazu übergegangen, dass ich, sobald ich gezeigt habe, dass eine Funktion \(f\) primitiv rekursiv ist, sie nativ in Python zu implementieren, also beispielsweise in meiner Datei stockpile.py:

def pair(x,y):code>
  return int(((x+y+1) * (x+y)) / 2 + x )