CPS in Curry-Sprachen

Question

Wie macht CPS in Curry-Sprachen wie Lambda-Kalkül oder Ocaml überhaupt Sinn? Technisch gesehen haben alle Funktionen ein Argument. Also sagen wir eine CPS-Version zusätzlich in einer solchen Sprache haben:

cps-add k n m = k ((+) n m) 

Und wir nennen es wie

(cps-add random-continuation 1 2) 

Dies ist dann die gleiche wie:

(((cps-add random-continuation) 1) 2) 

ich schon sehen, zwei Aufrufe dort, die keine Tail-Aufrufe sind und in Wirklichkeit ein komplex verschachtelter Ausdruck ist, gibt die (cps-add random-continuation) einen Wert zurück, nämlich eine Funktion, die eine Zahl verbraucht und dann eine Funktion zurückgibt, die eine andere Zahl und verbraucht liefert dann die Summe von beiden an die random-continuation. Aber wir können diesen Wert nicht umgehen, indem wir ihn einfach wieder in CPS übersetzen, weil wir jeder Funktion nur ein Argument geben können. Wir müssen mindestens zwei haben, um Platz für die Fortsetzung und das "tatsächliche" Argument zu schaffen.

Oder fehlt mir etwas komplett?

Answer 1

ja, technisch können alle Funktionen mit einer Methode in Funktionen zerlegt werden. Wenn Sie jedoch CPS verwenden wollen, müssen Sie nur sagen, dass an einem bestimmten Punkt der Berechnung die Fortführungsmethode ausgeführt wird.

Lassen Sie uns anhand Ihres Beispiels einen Blick darauf werfen. Um die Dinge ein wenig einfacher zu machen, dekonstruieren wir cps-add in seine normale Form, wo es eine Funktion ist, die nur ein Argument verwendet.

(cps-Additions-k) -> n -> m = k ((+) nm)

Hinweis an dieser Stelle, dass die Fortsetzung, k, wird nicht ausgewertet werden (könnte dies der Punkt der Verwirrung für dich?).

Hier haben wir eine Methode namens cps-add k, die eine Funktion als Argument erhält und dann eine Funktion zurückgibt, die ein anderes Argument, n, übernimmt.

((cps-add k) n) -> m = k ((+) n m)

Jetzt haben wir eine Funktion, die ein Argument, m nimmt.

Also ich nehme an, was ich zu zeigen versuche ist, dass currying CPS style Programmierung nicht im Weg steht. Hoffe das hilft irgendwie.

Answer 2

Kurze Antwort: natürlich ist es sinnvoll ist, können Sie eine CPS-Transformation direkt anwenden, werden Sie nur eine Menge cruft haben, weil jedes Argument hat, wie Sie ihre eigene angebrachte Fortsetzung

In Ihrem Beispiel bemerken, Sehen Sie, ich will, dass es eine +(x,y) uncurried primitiv ist, und dass Sie fragen, was ist die Übersetzung von

let add x y = +(x,y) 

(Diese add repräsentieren treu (+) Bedienungs OCaml)

add ist syntaxically entspricht

let add = fun x -> (fun y -> +(x, y)) 

So haben Sie eine CPS transform¹ anwenden und

let add_cps = fun x kx -> kx (fun y ky -> ky +(x,y)) 

bekommen Wenn Sie eine übersetzte Code wollen, die eher wie etwas aussieht Sie gerne geschrieben haben könnte, können Sie eine feinere ersinnen Transformation, die die bekannte Arity-Funktion tatsächlich als nicht-Curry-Funktionen betrachtet und alle Parameter als Ganzes behandelt (wie Sie es in nicht-Curry-Sprachen getan haben, und wie funktionale Compiler bereits aus offensichtlichen Performance-Gründen tun).

¹: Ich schrieb "eine CPS-Transformation", weil es keine "eine echte CPS-Übersetzung" gibt. Verschiedene Übersetzungen wurden entwickelt, die mehr oder weniger fortsetzungsbedingten Müll produzieren. Die formalen CPS-Übersetzungen sind normalerweise direkt auf Lambda-Kalkül definiert, also nehme ich an, dass Sie eine weniger formelle, handgemachtere CPS-Transformation im Hinterkopf haben.

Die guten Eigenschaften von CPS (als Stil dieses Programm respektieren, und keine bestimmte Umwandlung in diesen Stil) sind, dass die Reihenfolge der Auswertung ist vollständig explizit, und dass alle Anrufe sind Tail-Anrufe. Solange Sie diese respektieren, sind Sie relativ frei in dem, was Sie tun können. Der gezielte Umgang mit Curry-Funktionen ist also völlig in Ordnung.

Anmerkung: Ihre (cps-add k 1 2) Version kann auch als tail rekursiv betrachtet werden, wenn Sie davon ausgehen, dass der Compiler erkennt und optimiert, dass cps-add tatsächlich immer 3 Argumente und keine Zwischenabschlüsse erstellt. Das mag weit hergeholt klingen, aber es ist die exakt gleiche Annahme, die wir verwenden, wenn wir über Tail-Calls in Nicht-CPS-Programmen in diesen Sprachen nachdenken.

Answer 3

Da Sie dies mit Haskell markiert habe, werde ich in dieser Hinsicht zu beantworten: In Haskell, das entspricht einer CPS-Transformation zu tun, arbeitet in der Cont Monade, der einen Wert x in eine Funktion höherer Ordnung transformiert, dass nimmt ein Argument und wendet es auf x an.

Also, mit zu beginnen, hier ist 1 + 2 in regelmäßiger Haskell: (1 + 2) Und hier ist es in der Fortsetzung Monade:

contAdd x y = do x' <- x 
       y' <- y 
       return $ x' + y' 

... nicht sehr informativ. Um zu sehen, was los ist, lass uns die Monade auseinander nehmen. Zunächst Entfernen der do Notation:

contAdd x y = x >>= (\x' -> y >>= (\y' -> return $ x' + y')) 

Die return Funktion einen Wert in das monadisch hebt, und in diesem Fall wird als \x k -> k x implementiert oder eine Infixoperator Abschnitt als \x -> ($ x) verwenden.

contAdd x y = x >>= (\x' -> y >>= (\y' -> ($ x' + y'))) 

Der (>>=) Operator (read "bind") -Ketten zusammen Berechnungen in dem monadisch, und in diesem Fall wird als \m f k -> m (\x -> f x k) umgesetzt. Ändern die Bindefunktion prefix Form und in der Lambda-Substitution, sowie einige Umbenennungs zur Klarheit:

contAdd x y = (\m1 f1 k1 -> m1 (\a1 -> f1 a1 k1)) x (\x' -> (\m2 f2 k2 -> m2 (\a2 -> f2 a2 k2)) y (\y' -> ($ x' + y'))) 

einige Funktionsanwendungen Reduzierung:

contAdd x y = (\k1 -> x (\a1 -> (\x' -> (\k2 -> y (\a2 -> (\y' -> ($ x' + y')) a2 k2))) a1 k1)) 

contAdd x y = (\k1 -> x (\a1 -> y (\a2 -> ($ a1 + a2) k1))) 

und ein wenig endgültigen Neuanordnung und Umbenennung:

contAdd x y = \k -> x (\x' -> y (\y' -> k $ x' + y')) 

Mit anderen Worten: Die Argumente für die Funktion wurden von Zahlen in Funktionen geändert, die eine Zahl nehmen und das Endergebnis des gesamten Ausdrucks zurückgeben, jus t wie Sie es erwarten würden.

Bearbeiten: Ein Kommentator weist darauf hin, dass contAdd selbst noch zwei Argumente im Curry-Stil dauert. Dies ist sinnvoll, da die Fortführung nicht direkt, sondern nicht notwendig ist. Um sonst zu tun, dann würden Sie müssen zunächst die Funktion auseinander zwischen den Argumenten brechen:

contAdd x = x >>= (\x' -> return (\y -> y >>= (\y' -> return $ x' + y'))) 

Und dann ist es wie folgt verwenden:

foo = do f <- contAdd (return 1) 
     r <- f (return 2) 
     return r 

Hinweis, dass dies wirklich nicht anders aus der früheren Version ; es packt einfach das Ergebnis jeder Teilanwendung als eine Fortsetzung, nicht nur das Endergebnis. Da Funktionen erstklassige Werte sind, gibt es keinen signifikanten Unterschied zwischen einem CPS-Ausdruck, der eine Zahl enthält, und einem, der eine Funktion hält.

Denken Sie daran, dass ich hier Dinge auf sehr ausführliche Art und Weise schreibe, um alle Schritte explizit zu machen, wo etwas im Fortsetzungsstil ist.

---

Nachtrag: Sie können feststellen, dass der endgültige Ausdruck der de-gezuckerten Version des monadischen Ausdruck sehr ähnlich sieht. Dies ist kein Zufall, da die einwärts verschachtelnde Natur der monadischen Ausdrücke, die es ihnen erlauben, die Struktur der Berechnung basierend auf vorherigen Werten zu ändern, eng mit dem Fortsetzungs-Passing-Stil verbunden ist; In beiden Fällen haben Sie in gewisser Weise einen Kausalitätsbegriff verdinglicht.