Verwendung von Lambda für Cons / Auto / Cdr Definition in SICP

Ich begann gerade zu fühlen, dass ich ein vages Verständnis für den Einsatz von Lambda in Racket und System hatte, als ich auf die folgenden alternativen Definitionen für Cons und Car in SICP stieß

(define (cons xy) (lambda (m) (mxy))) (define (car z) (z (lambda (pq) p))) (define (cdr z) (z (lambda (pq) q))) 

Für das Leben von mir kann ich sie einfach nicht analysieren.

Kann jemand erklären, wie man diese auf eine Art und Weise analysiert oder erweitert, die für Neophyten sinnvoll ist?

    Dies ist eine interessante Möglichkeit, Daten darzustellen: als functionen. Beachten Sie, dass diese Definition von cons ein lambda zurückgibt, das über die Parameter x und y schließt und deren Werte im Inneren erfasst. Beachten Sie auch, dass das zurückgegebene Lambda eine function m als Parameter erhält:

     ;creates a closure that "remembers' 2 values (define (cons xy) (lambda (m) (mxy))) ;recieves a cons holding 2 values, returning the 0th value (define (car z) (z (lambda (pq) p))) ;recieves a cons holding 2 values, returning the 1st value (define (cdr z) (z (lambda (pq) q))) 

    In dem obigen Code ist z ein Abschluss, derselbe, der durch cons , und im Körper des Verfahrens übergeben wir ihm einen weiteren lambda als Parameter, erinnern Sie sich an m ? es ist nur so dass! die function, die sie erwartet hat.

    Wenn man das Obige versteht, ist es einfach zu sehen, wie car und cdr funktionieren; Lassen Sie uns sezieren, wie car , cdr vom Dolmetscher Schritt für Schritt ausgewertet wird:

     ; lets say we started with a closure `cons`, passed in to `car` (car (cons 1 2)) ; the definition of `cons` is substituted in to `(cons 1 2)` resulting in: (car (lambda (m) (m 1 2))) ; substitute `car` with its definition ((lambda (m) (m 1 2)) (lambda (pq) p)) ; replace `m` with the passed parameter ((lambda (pq) p) 1 2) ; bind 1 to `p` and 2 to `q`, return p 1 

    Zusammenfassend: cons erzeugt eine Schließung, die sich an zwei Werte “merkt”, car erhält diese Schließung und übergibt sie entlang einer function, die als Selektor für den nullten Wert dient, und cdr fungiert als Selektor für den ersten Wert. Der Schlüsselpunkt zum Verständnis hier ist lambda als ein Abschluss, wie cool ist das? Wir brauchen nur functionen, um beliebige Daten zu speichern und abzurufen!

    Verschachtelte Kompositionen von car & cdr sind in den meisten LISPs bis zu 4 Deep definiert. Beispiel:

     (define caddr (lambda (x) (car (cdr (cdr x))))) 

    Dies sollte mit der kombinatorischen Notation leicht verständlich sein (implizit in Schema als Curry-functionen übersetzt, fxy = z ==> (define f (λ (x) (λ (y) z))) ):

     cons xym = mxy car z = z _K ; _K pq = p cdr z = z (_K _I) ; _I x = x _K _I pq = _I q = q 

    So kommen wir

     car (cons xy) = cons xy _K = _K xy = x cdr (cons xy) = cons xy (_K _I) = _K _I xy = _I y = y 

    also machen die Definitionen das, was wir erwarten. Einfach .

    Im Englischen ist der cons xy Wert eine function, die besagt: “Wenn Sie mir eine function von zwei Argumenten geben, werde ich sie mit den zwei Argumenten nennen, die ich halte. Lassen Sie sie entscheiden, was mit ihnen zu tun ist, dann!” .

    Mit anderen Worten, es erwartet eine “Fortsetzungs” -function und ruft sie mit den zwei Argumenten auf, die in ihrer (der “Paar”) -Erstellung verwendet werden.

    Der definitive Trick ist meines Erachtens das Lesen der Definitionen vom Ende bis zum Anfang , denn in allen dreien sind die freien Variablen immer diejenigen, die im Lambda innerhalb des Körpers gefunden werden können ( m , p und q ). Hier ist ein Versuch, den Code vom Ende (unten rechts) bis zum Anfang (oben links) ins Englische zu übersetzen:

     (define (cons xy) (lambda (m) (mxy)) 

    Was auch immer m ist, und wir vermuten, dass es eine function ist, weil es direkt neben a steht ( , es muss sowohl über x als auch über y angewendet werden: das ist die Definition von cons x und y .

     (define (car z) (z (lambda (pq) q))) 

    Was auch immer p und q sind, wenn etwas, das z wird, angewendet wird, und z etwas ist, das functionen als seine Eingabe akzeptiert, dann wird die erste von p und q ausgewählt: das ist die Definition von car .

    Für ein Beispiel von “etwas, das functionen als Input akzeptiert”, müssen wir nur auf die Definition von ” cons ” zurückblicken. Das bedeutet, car akzeptiert cons als Eingabe.

     (car (cons 1 2)) ; looks indeed familiar and reassuring (car (cons 1 (cons 2 '()))) ; is equivalent (car '(1 2)) ; is also equivalent (car z) ; if the previous two are equivalent, then z := '(1 2) 

    Die letzte Zeile bedeutet: Eine Liste ist “etwas, das eine function als Eingabe akzeptiert”.

    Lass deinen Kopf in diesem Moment nicht rotieren! Die Liste akzeptiert nur functionen, die ohnehin auf Listenelementen funktionieren können. Und das ist gerade der Fall, weil wir die cons die wir haben, neu definiert haben.

    Ich denke, der Hauptpunkt dieser Übung ist, dass “Berechnungen Operationen und Daten zusammenbringen, und es spielt keine Rolle, in welcher Reihenfolge Sie sie zusammenbringen”.

    Ich habe hier eine Version von Go erstellt, die Sie ausführen können: https://play.golang.org/p/3Hz6ss-9ghr