Ich fand diesen Abschnitt auch beim ersten Lesen verwirrend, und fing erst an, es zu bekommen, nachdem ich woanders über Fortsetzungen und Fortsetzungsstil gelesen hatte (was das ist).
Auf die Gefahr der Erklärung etwas, das Sie bereits erhalten, eine Art zu sehen, die mir geholfen hat, ist zu denken, der "Sammler" oder "Fortsetzung" als den normalen Weg für die Funktion zu ersetzen, um Werte zurückzugeben. Im normalen Stil der Programmierung rufen Sie eine Funktion auf, erhalten einen Wert und tun etwas damit im Aufrufer. Zum Beispiel enthält die rekursive Standardfunktion length den Ausdruck (+ 1 (length (cdr list))) für den nicht leeren Fall. Das heißt, sobald (length (cdr list)) einen Wert zurückgibt, gibt es eine Berechnung, die darauf wartet, mit dem von ihr erzeugten Wert zu passieren, den wir uns als (+ 1 [returned value]) vorstellen könnten. Bei der normalen Programmierung verfolgt der Interpreter diese ausstehenden Berechnungen, die dazu neigen, sich zu "stapeln", wie Sie in den ersten paar Kapiteln des Buches sehen können. Zum Beispiel haben wir bei der rekursiven Berechnung der Länge einer Liste ein Nest von "Warteberechnungen" so viele Ebenen tief wie die Liste lang ist.
In Fortsetzung-Passing-Stil, sondern eine Funktion aufrufen und mit der Ergebnis in der aufrufenden Funktion zurück, sagen wir die Funktion, was zu tun ist, wenn es seinen Wert erzeugt, indem sie es mit einer „Fortsetzung“ Bereitstellung zu nennen. (Dies ähnelt dem, was Sie mit Callbacks in der asynchronen JavaScript-Programmierung tun müssen, zum Beispiel: Anstatt zu schreiben, schreiben Sie someFunction(function (result) { ... }), und der gesamte Code, der result verwendet, geht in die Callback-Funktion).
Hier ist length im Fortsetzungsmodus, nur zum Vergleich. Ich habe den Fortsetzungsparameter return aufgerufen, der vorschlagen sollte, wie es hier funktioniert, aber denken Sie daran, dass es nur eine normale Schema-Variable wie jede andere ist. (Oft wird der Fortsetzungsparameter in diesem Stil k genannt).
(define (length/k lis return)
(cond ((null? lis) (return 0))
(else
(length/k (cdr lis)
(lambda (cdr-len)
(return (+ cdr-len 1)))))))
Es gibt einen hilfreichen Tipp zum Lesen dieser Art von Code in an article on continuations by Little Schemer co-author Dan Friedman. (Siehe Abschnitt II-5 ab Seite 8).Paraphrasieren, ist hier, was die else Klausel oben sagt:
stellen Sie sich das Ergebnis des Aufrufs length/k auf (cdr lis) haben, und nennen es cdr-len, dann ein addieren und das Ergebnis dieser Addition auf Ihre Fortsetzung passieren (return) .
Beachten Sie, dass diese fast genau das, was der Dolmetscher bei der Bewertung (+ 1 (length (cdr lis))) in der normalen Version der Funktion zu tun hat (außer, dass es nicht (length (cdr lis)) einen Namen für das Zwischenergebnis zu geben hat. Indem um die Fortsetzungen oder Rückrufe Wir haben den Kontrollfluss (und die Namen der Zwischenwerte) explizit gemacht, anstatt dass der Interpreter den Überblick behält.
Wir wenden diese Methode auf jede Klausel in evens-only*&co an Tatsache, dass diese Funktion drei Werte statt eins erzeugt: die verschachtelte Liste mit ungeraden Zahlen entfernt; das Produkt der geraden Zahlen; und die Summe der ungeraden Zahlen. Hier ist die erste Klausel, wo (car l) bekannt ist, eine gerade Zahl zu sein:
(evens-only*&co (cdr l)
(lambda (newl product sum)
(col (cons (car l) newl)
(opx (car l) product)
sum)))
Stellen Sie sich vor, dass Sie die Ergebnisse der Entfernung von ungeraden Zahlen haben, Multiplikation Evens, und das Hinzufügen von ungeraden Zahlen aus den cdr der Liste, und rufen Sie sie newl, product bzw. sum. cons der Kopf der Liste auf newl (da es eine gerade Zahl ist, sollte es im Ergebnis gehen); Multiplizieren Sie product mit dem Kopf der Liste (seit berechnen wir Produkt von Evens); Lassen Sie sum allein; und übergeben Sie diese drei Werte an Ihre wartende Fortsetzung col.
Hier ist der Fall, in dem der Kopf der Liste eine ungerade Zahl ist:
(evens-only*&co (cdr l)
(lambda (newl product sum)
(col newl product (op+ (car l) sum))))
Wie zuvor, aber die gleichen Werte von newl und product zur Fortsetzung (dh „Rückkehr“ sie) übergeben, zusammen mit der Summe von sum und dem Kopf der Liste, da wir ungerade Zahlen summieren.
Und hier ist das letzte, wo (car l) eine verschachtelte Liste ist, und die durch die doppelte Rekursion etwas kompliziert:
(evens-only*&co (car l)
(lambda (newl product sum)
(evens-only*&co (cdr l)
(lambda (dnewl dproduct dsum)
(col (cons newl dnewl)
(opx product dproduct)
(op+ sum dsum))))))
Stellen Sie die Ergebnisse aus dem Entfernen haben, Summieren und das Hinzufügen der Zahlen in (car l) und rufen Sie diese newl, product und sum; dann stellen Sie sich vor, Sie haben die Ergebnisse aus der gleichen Sache zu (cdr l), und rufen Sie sie dnewl, dproduct und dsum.Zu Ihrer wartenden Fortsetzung, geben Sie die Werte von cons ing newl und dnewl (da wir eine Liste von Listen erstellen); zusammen multiplizieren product und dproduct; und Hinzufügen von sum und dsum.
Hinweis: jedes Mal, wenn wir einen rekursiven Aufruf zu machen, haben wir eine neue Fortsetzung für den rekursiven Aufruf konstruieren, die „schließt sich über“ die aktuellen Werte des Arguments, l, und die Rückkehr Fortsetzung - col, mit anderen Worten Man kann sich die Kette von Fortsetzungen vorstellen, die wir während der Rekursion aufbauen, indem wir den "Call-Stack" einer konventioneller geschriebenen Funktion modellieren!
Hoffe, dass gibt einen Teil einer Antwort auf Ihre Frage. Wenn ich etwas über Bord gegangen bin, dann nur deshalb, weil ich dachte, dass nach der Rekursion selbst Fortsetzungen die zweite, wirklich nette, Gedanken erweiternde Idee in der Programmierung und im Allgemeinen sind.
Zum Einrichten der Stepper, siehe http://StackOverflow.com/Questions/10499514/Y-Combinator-Discussion-in-the-Little-Schemer/10500358#10500358 – soegaard