Wie konvertiere ich diese Prozeduren in Scheme in CPS-Formular?
(lambda (x y)
((x x) y))
(lambda (x)
(lambda (f)
(f (lambda (y)
(((x x) f) y))))
((lambda (x) (x x)
(lambda (x) (x x))
* Das sind keine Hausaufgaben!
Siehe Programmiersprachen, Anwendung und Interpretation , beginnend mit Kapitel 15. Kapitel 18 spricht darüber, wie es automatisch gemacht wird, aber wenn Sie nicht damit vertraut sind, eine Funktion auszudrücken, die "was als nächstes zu tun" macht, werden Sie wahrscheinlich zuerst die Fingerübungen ausprobieren wollen.
Lassen Sie sich von niemandem etwas vormachen: Sie werden den Prozess wirklich verstehen und in der Lage sein, dies von Hand zu tun, unabhängig von Schema oder anderweitig. Es kommt besonders in der asynchronen JavaScript-Webprogrammierung vor, wo Sie wirklich keine andere Wahl haben, als die Transformation durchzuführen.
In der CPS-Transformation müssen alle nicht-primitiven Funktionen nun eine Funktion konsumieren, die "was-zu-nächstes" darstellt. Das schließt alle Lambdas ein. Symmetrisch muss jede Anwendung einer nicht-primitiven Funktion eine "Was-zu-Nächste-Ausführung" -Funktion bereitstellen und den Rest der Berechnung in diese Funktion einfügen.
Wenn wir also ein Programm zur Berechnung der Hypothenuse eines Dreiecks hätten:
%Vor% Wenn wir angeben, dass die einzigen primitiven Anwendungen hier * , + und sqrt sind, müssen alle anderen Funktionsdefinitionen und Funktionsaufrufe wie folgt übersetzt werden:
Der letzte Ausdruck zeigt, dass Sie am Ende "inside-out" berechnen müssen, und dass die Transformation allgegenwärtig ist: Alle Lambdas im ursprünglichen Quellprogramm benötigen ein zusätzliches Argument, und alle nicht-primitiven Anwendungen brauchen es "what-to-do-next" als dieses Argument stopfen.
Sehen Sie sich Abschnitt 17.2 des zitierten Buches genau an: Es behandelt dies ebenso wie 17.5, was davon handelt, warum Sie ALLE lambdas im Quellprogramm berühren müssen, damit auch der Fall höherer Ordnung funktioniert.
Als weiteres Beispiel für die Transformation, die für einen Fall höherer Ordnung angewendet wurde, sagen wir:
%Vor%Dann ist die Übersetzung von etwas wie diesem:
%Vor% ... weil dieses Lambda nur ein Wert ist, der an k1 übergeben werden kann. Aber natürlich muss die Übersetzung auch das Lambda durchlaufen.
Wir müssen zuerst den inneren Aufruf von f mit x ausführen (und daran denken, dass alle nicht-primitiven Funktionsanwendungen ein passendes "what-to-do-next!" übergeben müssen):
... nimm diesen Wert und wende ihn erneut an f ... an
%Vor% ... und schließlich diesen Wert an k2 zurückgeben:
Sie müssen wählen, auf welcher Ebene Sie CPS-transformieren möchten / wollen.
Wenn Sie (lambda (x y) ((x x) y)) nur im Continuation-Passing (CP) Style haben wollen, dann wird (lambda (k x y) (k ((x x) y))) funktionieren.
Wenn Sie möchten, dass seine Argumente auch im CP-Stil behandelt werden, brauchen Sie ein wenig mehr.
Nehmen wir an, dass nur das zweite Argument ( y ) in CP-Form ist und somit wirklich etwas wie (lambda (k) (k y0)) ist und daher mit einer Fortsetzung aufgerufen werden muss, um seinen Wert zu extrahieren, dann müssten Sie:
Schließlich nehmen wir an, dass sowohl x als auch y im CP Stil sind. Dann brauchst du etwas wie:
Hier haben Sie die Möglichkeit, die Aufrufe von x und y neu anzuordnen. Oder vielleicht brauchen Sie nur einen Aufruf von x , weil Sie wissen, dass sein Wert nicht von der Fortsetzung abhängt, mit der er aufgerufen wird. Zum Beispiel:
Die anderen Ausdrücke, nach denen Sie gefragt haben, können ähnlich transformiert werden.
Tags und Links scheme continuation-passing