Fortsetzung Passing Style in ocaml

Question

Ich bin ein bisschen verwirrt über das Konzept. So habe ich die folgende Funktion

let rec sumlist lst = 
      match lst with 
      | [] -> 0 
      | (h::t) -> h + (sumlist t) 

Mit Fortsetzung, kann es als

geschrieben werden

let rec cont_sumlist lst c = 
match lst with 
| [] -> (c 0) 
| (h::t) -> cont_sumlist t (fun x -> c (h + x)) 

Ich bin immer noch verwirrt, was die c bedeutet und was es tut

Answer 1

Eine allgemeine Antwort ist bereits gegeben, aber insbesondere für cont_sumlist,

• bei [] wir "Rückkehr" (dh Feed) 0inc, die wir gegeben sind (0ist die Summe aus einer leeren Liste) und

• bei (h::t) wir die Fortsetzung für cont_sumlist t so konstruieren, dass nach das Ergebnis für t (d.h. x) ist bereit, wird es mit h (von h + x) kombiniert und weiter in c gegeben, die uns für (h::t) gegeben wird.

Dies ist somit Ausdruck der Gleichung sumlist (h::t) = h + sumlist t, aber die Auswertungskette explizite als Kette dieser Fortsetzungsfunktionen, die jeweils das Ergebnis der Fortsetzung Funktion darüber zuzuführen; im Gegensatz zu implizit im Stack-basierten Evaluierungsmechanismus.

Mit anderen Worten fun x -> c (h + x) = c ∘ (h +), so wie wir entlang der Liste gehen [h1; h2; h3; ...] wird die Fortsetzung progressiv c0 ∘ (h1 +) ∘ (h2 +) ∘ (h3 +) ∘ ... ausgebildet ist, und wird schließlich mit 0 aufgerufen, wenn die Liste vollständig durchsucht wurde; wobei c0 die oberste Fortsetzung ist, die ein Benutzer dem obersten Anruf gegeben hat, z.

cont_sumlist [1,2] (fun x -> x) 
= 
(fun x -> (fun x -> (fun x -> x) (1 + x)) (2 + x)) 0 
= 
        (fun x -> x) 
      (fun x ->    (1 + x)) 
(fun x ->         (2 + x)) 0 
= 
(1 + (2 + 0)) 

Also insgesamt cont_sumlist [x; y; z; ... ; n] c verwandelt sich in

(c ∘ (x +) ∘ (y +) ∘ (z +) ∘ ... ∘ (n +)) 0 
= 
    c (x + (y + (z + .... + (n + 0) ....))) 

mit dem entscheidenden Unterschied, dass es kein Stapel ist Wicklung und beteiligte Abwickeln und die Summe von rechts berechnet wird direkt nach links, in einem C-ähnlichen Pseudocode gegeben als eine Reihe von einfachen Schritten

Man könnte sagen, dass die Konstruktion der gesamten Fortsetzung ist ähnlich dem Aufwickeln des Stapels, und Ihre Anwendung entspricht dem Abwickeln des Stapels bei herkömmlicher stapelbasierter Auswertung.

Eine andere Möglichkeit ist, dass CPS eine spezielle Art von Funktionsaufrufprotokoll definiert, im Gegensatz zu der üblichen C-ähnlichen, die erwartet, dass jeder Funktionsaufruf zurückkehrt.

Jeder Fall in der CPS-Definition kann so interpretiert werden, dass er eine Kleinschritt-Semantik-Übergangsregel für die Funktion gibt: [] --> 0 ; (h::t) --> (h +).

Answer 2

Eine Möglichkeit, zu betrachten Fortsetzungs-Übergabestil ist, sich vorzustellen, wie Sie Code schreiben würden, wenn Funktionen nicht zurückgegeben werden könnten. Sie könnten die Dinge dennoch funktionieren lassen, indem Sie für jede Funktion einen zusätzlichen Parameter angeben, der angibt, was Sie nach der Berechnung der Funktion tun möchten. Das heißt, Sie übergeben eine Funktion, die als "Fortsetzung" der Gesamtberechnung fungiert.

Der Code, den Sie geben, wird genau so geschrieben, und c ist die Fortsetzung. Das heißt, es ist eine Funktion, die der Aufrufer eingibt, die angibt, was als nächstes zu tun ist, nachdem die Funktion ihre beabsichtigte Berechnung durchgeführt hat.

Der Fortsetzungs-Durchgangsstil ist vollständig allgemein, d. H. Alle Berechnungen können auf diese Weise ausgedrückt werden. Und tatsächlich gibt es eine mechanische Umwandlung von gewöhnlichem Funktionscode in Fortsetzungsstil.