Erstmal eine kleine Datenstruktur zum Testen und ein kleiner rekursiver Beispiel-Algorithmus, der der Struktur vom Robinson recht nahe kommt (jedoch ohne Resolving und Unifikation, und alles noch ohne TCO/CPS):
Code: Alles auswählen
from random import randint
class Node(object):
def __init__(self, value, children):
self.value = value
self.children = children
def __repr__(self):
return "%d" % self.value
def maketrees(n, *ns):
if ns:
return [Node(randint(1,9), maketrees(*ns)) for each in xrange(n)]
return [Node(randint(1,9), []) for each in xrange(n)]
def validpaths(nodes, path=[]):
if nodes == []:
yield path
else:
for node in nodes:
if isvalid(node):
for each in validpaths(node.children, path + [node]):
yield each
def isvalid(node):
return node.value > 3
for path in validpaths(maketrees(3,2,5,4)):
print path
Code: Alles auswählen
[6, 8, 9, 7]
[6, 8, 9, 7]
[6, 8, 9, 8]
[6, 8, 9, 6]
[9, 4, 5, 8]
[9, 4, 5, 9]
[9, 4, 5, 9]
[9, 4, 8, 8]
Code: Alles auswählen
def trampoline(bouncing, *args, **kwargs):
while bouncing:
throwing, bouncing, args, kwargs = bouncing(*args, **kwargs)
if throwing:
yield throwing()
def bouncy(f):
return lambda *args, **kwargs:(None, f, args, kwargs)
def land(*args, **kwargs):
return None, None, args, kwargs
def bounce(function, *args, **kwargs):
return None, function, args, kwargs
def throw(function, thrown, *args, **kwargs):
return lambda:thrown, function, args, kwargs
Code: Alles auswählen
@bouncy
def validpathsCT(nodes, path=[], result=throw, cont=land):
if nodes == []:
return result(cont, path)
def trail(*unused):
return validpathsCT(nodes[1:], path, cont, cont)
node = nodes[0]
if isvalid(node):
return validpathsCT(node.children, path + [node], throw, trail)
return trail()
def validpaths(trees):
return trampoline(validpathsCT, trees)
Hier ist die Schleife von oben (for node in nodes) durch einen weiteren rekursiven Aufruf ersetzt worden (return trail()). trail ist eine Closure, in der zweimal die zweite der beiden aktuellen Continuations (cont) weitergereicht wird. Beim rekursiven Abstieg dagegen werden als erste Continuation die Rückgabe-Funktion throw (für den Fall, dass ein gültiger Pfad gefunden wurde) übergeben, und als zweite die Backtracking-Funktion trail (für den Fall, dass es von hier aus keinen solchen Pfad gibt). Der eine Trick ist nun, dass in trail() cont == trail selbst ist, sofern node kein Root-Knoten ist, und das heisst, dass, wenn result ebenfalls == trail ist, return result(cont, value) "zurückkehrt" und der Algorithmus per Backtracking dort weitermacht, wo er soll, solange, bis er am Schluss "land"et. Oder, result != trail, dann ist aber result == throw und cont == trail. result ruft nun cont auf (das, wie gesagt, == trail ist), wodurch dann alle Lösungen generiert werden. trail wird also zweitverwertet, einmal als Abbruchs-Funktion nach einem Scheitern, und das andere mal als Fortsetzungs-Funktion nach der Generierung einer Route.
[edit]
Ich weiß nicht, ob die vorhergehende Erklärung was taugt, deswegen nochmal anders:
Es gibt vier mögliche Kombinationen von result und cont:
a) result == throw und cont == land. Das besteht nur beim allerersten Aufruf.
b) result == throw und cont == trail. Das besteht nur direkt beim rekursiven Abstieg.
c) result == trail und cont == trail. Das besteht beim Trailing, außer wenn
d) result == land und cont == land, wenn das Trailing entlang der rechten Außenkante verläuft.
Da einzig throw eine Ausgabe erzeugt, und nur trail die Abarbeitung fortsetzt, geschieht also immer folgendes, wenn nodes == [] erreicht ist:
Bei a) wird nochmal eine Ausgabe erzeugt und mit land fortgesetzt. (Termination)
bei b) wird eine Ausgabe erzeugt, aber mit trail fortgesezt. (Backtracking after success)
bei c) wird keine Ausgabe erzeugt, und cont wird ignoriert. Da result aber == trail ist, wird sowieso mit trail fortgesetzt. (Backtracking after failure)
bei d) der Algorithmus terminiert ohne weitere Ausgabe.
[/edit]
Lustig ist noch folgendes: wenn man @bouncy weglässt läuft das ganze immer noch, nur nicht mehr tail call optimized, was man einfach feststellen kann, wenn man eine Exception schmeisst:
Code: Alles auswählen
########## HIER NIX @bouncy
def validpathsCT(nodes, path=[], result=throw, cont=land):
if nodes == []:
raise Exception, "w/o tail call optimization"
...
Code: Alles auswählen
$ python bouncing.py
Traceback (most recent call last):
File "bouncing.py", line 185, in <module>
for path in validpaths(maketrees(3,2,3,4)):
File "bouncing.py", line 145, in trampoline
throwing, bouncing, args, kwargs = bouncing(*args, **kwargs)
File "bouncing.py", line 175, in validpathsCT
return trail()
File "bouncing.py", line 171, in trail
return validpathsCT(nodes[1:], path, cont, cont)
File "bouncing.py", line 175, in validpathsCT
return trail()
File "bouncing.py", line 171, in trail
return validpathsCT(nodes[1:], path, cont, cont)
File "bouncing.py", line 174, in validpathsCT
return validpathsCT(node.children, path + [node], throw, trail)
File "bouncing.py", line 174, in validpathsCT
return validpathsCT(node.children, path + [node], throw, trail)
File "bouncing.py", line 174, in validpathsCT
return validpathsCT(node.children, path + [node], throw, trail)
File "bouncing.py", line 174, in validpathsCT
return validpathsCT(node.children, path + [node], throw, trail)
File "bouncing.py", line 168, in validpathsCT
raise Exception, "w/o tail call optimization"
Exception: w/o tail call optimization
Code: Alles auswählen
@bouncy
def validpathsCT(nodes, path=[], result=throw, cont=land):
if nodes == []:
raise Exception, "with tail call optimization"
...
Code: Alles auswählen
$ python bouncing.py
Traceback (most recent call last):
File "bouncing.py", line 185, in <module>
for path in validpaths(maketrees(3,2,3,4)):
File "bouncing.py", line 145, in trampoline
throwing, bouncing, args, kwargs = bouncing(*args, **kwargs)
File "bouncing.py", line 168, in validpathsCT
raise Exception, "with tail call optimization"
Exception: with tail call optimization
(und wer baut mir dazu ein call/cc? )
Gruß und "May You Bounce In Peace!" (Brain Ball #1, Futurama, "War Is The H-Word"),
Mick.