Y-Kombinator- und Tail-Call-Optimierungen

20

Die Definition eines Y-Kombinators in F # lautet

let rec y f x = f (y f) x

Als erstes Argument erwartet f eine Fortsetzung der rekursiven Teilprobleme. Wenn wir das yf als Fortsetzung verwenden, sehen wir, dass f auf aufeinander folgende Aufrufe angewendet wird, sobald wir uns entwickeln können

let y f x = f (y f) x = f (f (y f)) x = f (f (f (y f))) x etc...

Das Problem ist, dass dieses Schema a priori die Verwendung von Tail-Call-Optimierungen ausschließt: In der Tat könnte eine Operation in den fs anstehen. In diesem Fall können wir den lokalen Stapelrahmen, der mit f assoziiert ist, nicht einfach mutieren.

So :

  • Zum einen erfordert die Verwendung des Y-Kombinators eine explizit andere Fortsetzung als die eigentliche Funktion.
  • Wenn Sie TCO anwenden möchten, möchten wir, dass in f keine Operation ansteht und nur f selbst aufgerufen wird.

Kennen Sie eine Möglichkeit, diese beiden zu versöhnen? Wie ein Y mit Akkumulator-Trick oder ein Y mit CPS-Trick? Oder ein Argument, das beweist, dass es unmöglich ist, es zu tun?

nicolas
quelle
Haben Sie die Rec-Keywork zu Ihrer y-Implementierung hinzugefügt? Ich sollte denken, es braucht es aus meiner Lektüre ..
Jimmy Hoffa
Haben Sie den Beweis, dass es den Tail Call nicht optimiert? Ich sollte denken, Sie möchten vielleicht die IL für diese Funktion lesen und sehen, ich wäre nicht überrascht, wenn der Compiler klug genug ist, um sich etwas auszudenken.
Jimmy Hoffa
Im Fall einer reinen ungebundenen Rekursion ist dies nicht der Fall: Sie können sie jedoch umschreiben, um dies zu ermöglichen , sofern der Stapelrahmen durch den y-Aufruf wiederverwendet wird. Ja, vielleicht muss ich die IL sehen, keine Erfahrung damit.
Nicolas
5
Ich habe einen Account erstellt und 50 Punkte bekommen, nur um dies zu kommentieren. Diese Frage ist wirklich interessant. Ich denke, es kommt ganz darauf an f. Wir können sehen, dass ydas fmit einem Thunk klappen könnte (y f), aber wie Sie sagen, fkönnte eine Operation anstehen. Ich denke, es wäre interessant zu wissen, ob es einen separaten Kombinator gibt, der die Rückrufe erleichtert. Ich frage mich, ob diese Frage auf der CS Stackexchange-Website mehr Beachtung finden würde.
John Cartwright

Antworten:

4

Kennen Sie eine Möglichkeit, diese beiden zu versöhnen?

Nein, und das aus gutem Grund, IMHO.

Der Y-Kombinator ist ein theoretisches Konstrukt und wird nur benötigt, um die Lambda-Berechnung zu vervollständigen.

Daher ist der Y-Kombinator wirklich faszinierend.

Aber : Niemand benutzt den Y-Kombinator tatsächlich zur Rekursion! (Außer vielleicht zum Spaß, um zu zeigen, dass es wirklich funktioniert.)

Die Tail-Call-Optimierung OTOH ist, wie der Name schon sagt, eine Optimierung. Es trägt nichts zur Ausdruckskraft einer Sprache bei, sondern ist nur aufgrund praktischer Überlegungen wie Stapelspeicher und Leistung von rekursivem Code wichtig.

Ihre Frage lautet also: Gibt es Hardware-Unterstützung für die Beta-Reduzierung? (Mit der Beta-Reduzierung werden Lambda-Ausdrücke reduziert, wissen Sie.) Aber keine funktionale Sprache (soweit mir bekannt ist) kompiliert ihren Quellcode zu einer Darstellung von Lambda-Ausdrücken, die zur Laufzeit Beta-reduziert werden.

Ingo
quelle
2
Der Y-Kombinator ist wie ein Knoten, der sich nach jedem Gebrauch löst. Die meisten Systeme kürzen dies und binden den Knoten auf der Metaebene, sodass er nie wieder gebunden werden muss.
Dan D.
1
Betrachten Sie als letzten Absatz Haskell, der im Kern die Graphenreduktion verwendet , um eine verzögerte Auswertung durchzuführen. Aber mein Favorit ist die optimale Reduktion, die immer den Weg im Church-Rosser-Gitter mit den geringsten Reduktionen zur vollen Normalform nimmt. So wie es in Asperti und Guerrinis The Optimal Implementation of Functional Programming Languages ​​zu sehen ist . Siehe auch BOHM 1.1 .
Dan D.
@DanD. Vielen Dank für die Links, ich werde sie später in einem PostScript-fähigen Browser ausprobieren. Klar, es gibt etwas zu lernen für mich. Aber sind Sie sicher, dass das kompilierte Haskell die Grafikverringerung bewirkt? Das bezweifle ich.
Ingo
1
Tatsächlich wird die Grafikverkleinerung verwendet: "GHC wird auf die spineless tagless G-Maschine (STG) kompiliert. Dies ist eine fiktive Grafikverkleinerungsmaschine (dh eine virtuelle Maschine, die die oben beschriebenen Grafikverkleinerungen durchführt)." From ... Weitere Informationen zur STG-Maschine finden Sie in Simon Peyton Jones ' Implementing Lazy Functional Languages ​​on Stock Hardware: Die Spineless Tagless G-Maschine .
Dan D.
@DanD. In demselben Artikel, den Sie verlinkt haben, heißt es weiter unten, dass GHC "eine Reihe von Optimierungen an dieser Darstellung vornimmt, bevor es sie schließlich in echten Maschinencode kompiliert (möglicherweise über C mit GCC)".
Ingo
0

Ich bin mir bei dieser Antwort nicht ganz sicher, aber es ist das Beste, was ich mir einfallen lassen konnte.

Der y-Kombinator ist von Natur aus faul, in strengen Sprachen muss die Faulheit manuell durch zusätzliche Lambdas hinzugefügt werden.

let rec y f x = f (y f) x

Ihre Definition sieht so aus, als ob zum Beenden Faulheit erforderlich ist, oder das (y f)Argument würde die Auswertung nie beenden und müsste evaluiert werden, ob es verwendet wird oder nicht f. TOC in einem faulen Kontext ist komplizierter und darüber hinaus das Ergebnis einer (y f)wiederholten Funktionszusammensetzung ohne Anwendung mit dem x. Ich bin mir nicht sicher, ob hierfür O (n) -Speicher erforderlich ist, wobei n die Tiefe der Rekursion ist, aber ich bezweifle, dass Sie dieselbe Art von Inhaltsverzeichnis erzielen können, die mit so etwas möglich ist (Wechsel zu Haskell, weil ich es eigentlich nicht weiß F #)

length acc []    = acc
length acc (a:b) = length (acc+1) b 

Wenn Sie sich dessen noch nicht bewusst sind, kann der Unterschied zwischen foldlund foldl'in Haskell Aufschluss über die Situation geben. foldlist so geschrieben, als würde man es in einer eifrigen Sprache tun. Es ist jedoch schlimmer, als foldrdass der Akku einen potenziell enormen Thunk speichert, der nicht teilweise ausgewertet werden kann. (Dies hängt damit zusammen, warum sowohl foldl als auch foldl 'nicht für unendliche Listen funktionieren.) Daher wurde in neueren Versionen von Haskell foldl'hinzugefügt, dass die Bewertung des Akkumulators jedes Mal erzwungen wird, wenn die Funktion wiederholt wird, um sicherzustellen, dass kein enormer Thunk erstellt wird. Ich bin sicher, dass http://www.haskell.org/haskellwiki/Foldr_Foldl_Foldl%27 dies besser erklären kann als ich.

Ericson2314
quelle