Wie funktioniert die Yin-Yang-Puzzle-Arbeit?

StackOverflow https://stackoverflow.com/questions/2694679

  •  01-10-2019
  •  | 
  •  

Frage

Ich versuche, die Semantik von Call / cc in Schema und die Wikipedia-Seite über Fortsetzungen zeigen das Yin-Yang-Puzzle als Beispiel zu verstehen: 

(let* ((yin
         ((lambda (cc) (display #\@) cc) (call-with-current-continuation (lambda (c) c))))
       (yang
         ((lambda (cc) (display #\*) cc) (call-with-current-continuation (lambda (c) c)))) )
    (yin yang))

Es sollte Ausgang @*@**@***@****@..., aber ich verstehe nicht, warum; Ich würde es Ausgang erwarten @*@********* ...

erklären kann jemand im Detail, warum das Yin-Yang-Puzzle so funktioniert, es funktioniert?

War es hilfreich?

Lösung

Ich glaube nicht, dass ich diese ein ganz verstehen, aber ich kann nur an einem ( extrem von Hand wellig) Erklärung:

  • Die erste @ und * gedruckt werden, wenn yin und yang zuerst in den let* gebunden sind. (yin yang) angewandt wird, und es geht wieder nach oben, direkt nach dem ersten Anruf / cc beendet ist.
  • Die nächste @ und * gedruckt wird, dann wird eine andere * gedruckt, weil dieses Mal durch, yin ist wieder gebunden an den Wert des zweiten Anruf / cc.
  • (yin yang) wird wieder angelegt, aber diesmal Es ist in den ursprünglichen yang Umgebung ausführen , wobei yin zum ersten Anruf / cc gebunden ist, so daß die Steuerung von Druck andere geht zurück @. Das yang Argument enthält die Fortsetzung, die auf dem zweiten Durchlauf durch wieder eingefangen wurde, die, wie wir bereits gesehen haben, beim Drucken ** führen. Also auf diesem dritten Durchlauf wird @* gedruckt wird, dann ist diese Doppelstern-Druck Fortsetzung wird aufgerufen, so dass es mit 3 Sternen endet, und dann dieser Triple-Sterne-Fortsetzung ist wieder eingefangen, ...

Andere Tipps

Legendes Schema

ich denke, zumindest die Hälfte des Problems mit diesem Puzzle Verständnis der Scheme-Syntax, die die meisten nicht vertraut sind.

Zunächst einmal finde ich persönlich die call/cc x härter als die gleichwertige Alternative zu verstehen sein, x get/cc. Es ist immer noch Anrufe x, wird die aktuelle Fortsetzung vorbei , aber irgendwie ist zugänglicher in meinem Gehirn-Schaltung dargestellt ist.

In diesem Sinne wird das Konstrukt (call-with-current-continuation (lambda (c) c)) einfach get-cc. Wir sind jetzt auf diese: 

(let* ((yin
         ((lambda (cc) (display #\@) cc) get-cc))
       (yang
         ((lambda (cc) (display #\*) cc) get-cc)) )
    (yin yang))

Der nächste Schritt ist der Körper des inneren Lambda. (display #\@) cc, in der vertrauteren Syntax (für mich jedenfalls) bedeutet print @; return cc;. Während wir gerade dabei sind, wollen sie auch lambda (cc) body als function (arg) { body } umschreiben, eine Reihe von Klammern und Änderungsfunktion Anrufe an den C-ähnliche Syntax entfernen, zu erhalten: 

(let*  yin =
         (function(arg) { print @; return arg; })(get-cc)
       yang =
         (function(arg) { print *; return arg; })(get-cc)
    yin(yang))

Es fängt mehr Sinn, jetzt zu machen. Es ist jetzt ein kleiner Schritt, um diese vollständig in C-ähnlicher Syntax neu zu schreiben (oder JavaScript-like, wenn Sie bevorzugen), zu erhalten: 

var yin, yang;
yin = (function(arg) { print @; return arg; })(get-cc);
yang = (function(arg) { print *; return arg; })(get-cc);
yin(yang);

Der schwierigste Teil ist jetzt vorbei, haben wir dies aus Schema decodiert! Ich mache nur Spaß; es war nur schwer, weil ich keine Erfahrung mit Scheme hatte. Also, lassen Sie uns zu herauszufinden, wie dies tatsächlich funktioniert.

Ein Primer auf Fortsetzungen

Beachten Sie die seltsam formulierte Kern von Yin und Yang: Es definiert eine Funktion und dann sofort nennt es . Es sieht genauso aus wie (function(a,b) { return a+b; })(2, 3), die 5 vereinfacht werden kann. Aber die Anrufe innerhalb Yin / Yang Vereinfachung wäre ein Fehler, weil wir es nicht einen gewöhnlichen Wert übergeben. Wir vorbei die Funktion einer Fortsetzung .

Eine Fortsetzung ist ein seltsames Tier auf den ersten Blick. Betrachten wir die viel einfacheres Programm: 

var x = get-cc;
print x;
x(5);

Am Anfang x wird auf das aktuelle Fortsetzung Objekt (Bär mit mir) gesetzt, und print x ausgeführt wird, so etwas wie <ContinuationObject> Druck. So weit so gut.

Aber eine Fortsetzung wie eine Funktion ist; es kann mit einem Argument aufgerufen werden. Was sie tut, ist:. Das Argument nehmen, und dann Sprung , um überall dort, wo die Fortsetzung erstellt wurde, alle Kontext wiederherstellen und es damit get-cc kehrt dieses Argument zu machen

In unserem Beispiel ist das Argument 5, so dass wir im Wesentlichen gleich wieder in die Mitte dieser var x = get-cc Anweisung springen, nur diesmal get-cc kehrt 5. So x wird 5, und die nächste Anweisung geht auf 5 zu drucken Danach wir Anruf 5(5) versuchen, eine Art Fehler ist, und das Programm stürzt ab.

Beachten Sie, dass die Fortsetzung Aufruf ist ein Sprung , kein Anruf. Er kehrt nie zurück, wo die Fortsetzung genannt wurde. Das ist wichtig.

Wie das Programm funktioniert

Wenn Sie, dass gefolgt, dann bekommen Sie nicht Ihre Hoffnungen: Dieser Teil ist wirklich das härteste. Hier ist unser Programm wieder, die Variablendeklarationen fallen, weil dieser Pseudo-Code ist auf jeden Fall: 

yin = (function(arg) { print @; return arg; })(get-cc);
yang = (function(arg) { print *; return arg; })(get-cc);
yin(yang);

Die erste Zeitlinie 1 und 2 treffen, sind sie nun einfach: die Fortsetzung erhalten, rufen Sie die Funktion (ARG), Druck @, Rückkehr, zu speichern, dass die Fortsetzung in yin. Das Gleiche gilt für yang. Wir haben jetzt gedruckt @*.

Als nächstes rufen wir die Fortsetzung in yin, vorbei es yang. Dies macht uns zu springen 1, direkt in der Linie, dass get-cc, und es stattdessen zurückgeben yang machen. Der Wert von yang wird nun in die Funktion übergeben, die @ druckt, und gibt dann den Wert von yang. Nun wird yin, dass eine Fortsetzung zugewiesen, dass yang hat. Als nächstes gehen wir nur auf Linie 2: get c / c, Print *, speichern the c / c in yang. Wir haben jetzt @*@*. Und schließlich gehen wir in Zeile 3.

Beachten Sie, dass yin jetzt die Fortsetzung hat aus, wenn Leitung 2 wurde zum ersten Mal ausgeführt wird. Also springen wir in die Linie 2, ein zweites * Drucken und Aktualisieren yang. Wir haben jetzt @*@**. Schließlich ruft erneut die yin Fortsetzung, die auf der Linie 1 springen, einen @ Druck. Und so weiter. Ehrlich gesagt, an dieser Stelle mein Gehirn löst eine OutOfMemory Ausnahme und ich verliere den Überblick über alles. Aber zumindest haben wir zu @*@**!

Das ist schwer zu folgen und noch schwerer, offensichtlich zu erklären. Der perfekte Weg, dies zu tun wäre, um durch sie in einem Debugger zu Schritt, die Fortsetzungen darstellen kann, aber leider, ich weiß nicht jeder. Ich hoffe, dass Sie diese genossen haben; Ich habe auf jeden Fall.

Musings erster, mögliche Antwort am Ende.

Ich denke, der Code kann wie folgt neu geschrieben werden: 

; call (yin yang)
(define (yy yin yang) (yin yang))

; run (call-yy) to set it off
(define (call-yy)
    (yy
        ( (lambda (cc) (display #\@) cc) (call/cc (lambda (c) c)) )
        ( (lambda (cc) (display #\*) cc) (call/cc (lambda (c) c)) )
     )
)

oder mit einer zusätzlichen Display-Anweisungen, um Hilfe zu sehen, was passiert: 

; create current continuation and tell us when you do
(define (ccc)
    (display "call/cc=")
    (call-with-current-continuation (lambda (c) (display c) (newline) c))
)

; call (yin yang)
(define (yy yin yang) (yin yang))

; run (call-yy) to set it off
(define (call-yy)
    (yy
        ( (lambda (cc) (display "yin : ") (display #\@) (display cc) (newline) cc) 
            (ccc) )
        ( (lambda (cc) (display "yang : ") (display #\*) (display cc) (newline) cc) 
            (ccc) )
     )
)

Oder wie folgt: 

(define (ccc2) (call/cc (lambda (c) c)) )
(define (call-yy2)
    (
        ( (lambda (cc) (display #\@) cc) (ccc2) )
        ( (lambda (cc) (display #\*) cc) (ccc2) )
    )
)

Mögliche Antwort

Das kann nicht richtig sein, aber ich werde mal ran.

ich glaube, der entscheidende Punkt ist, dass eine ‚genannte‘ Fortsetzung des Stapels zu einem früheren Zustand zurückkehrt - als ob nichts anderes geschehen war. Natürlich weiß er nicht, dass wir es durch die Anzeige @ und * Zeichen zu überwachen.

Wir definieren zunächst yin eine Fortsetzung A sein, dass dies tun: 

1. restore the stack to some previous point
2. display @
3. assign a continuation to yin
4. compute a continuation X, display * and assign X to yang
5. evaluate yin with the continuation value of yang - (yin yang)

Aber wenn wir eine yang Fortsetzung nennen, geschieht dies: 

1. restore the stack to some point where yin was defined
2. display *
3. assign a continuation to yang
4. evaluate yin with the continuation value of yang - (yin yang)

Wir beginnen hier.

Zum ersten Mal durch Sie yin=A und yang=B als yin und yang erhalten initialisiert werden. 

The output is @*

(Beide A und B Fortsetzungen berechnet.)

Jetzt (yin yang) als (A B) zum ersten Mal ausgewertet.

Wir wissen, was A tut. Es tut dies: 

1. restores the stack - back to the point where yin and yang were being initialised.
2. display @
3. assign a continuation to yin - this time, it is B, we don't compute it.
4. compute another continuation B', display * and assign B' to yang

The output is now @*@*

5. evaluate yin (B) with the continuation value of yang (B')

Jetzt (yin yang) als (B B') ausgewertet.

Wir wissen, was B tut. Es tut dies: 

1. restore the stack - back to the point where yin was already initialised.
2. display *
3. assign a continuation to yang - this time, it is B'

The output is now @*@**

4. evaluate yin with the continuation value of yang (B')

Da der Stapel wurde bis zu dem Punkt, wo wiederhergestellt yin=A, (yin yang) als (A B') ausgewertet wird.

Wir wissen, was A tut. Es tut dies: 

1. restores the stack - back to the point where yin and yang were being initialised.
2. display @
3. assign a continuation to yin - this time, it is B', we don't compute it.
4. compute another continuation B", display * and assign B" to yang

The output is now @*@**@*

5. evaluate yin (B') with the continuation value of yang (B")

Wir wissen, was B' tut. Es tut dies: 

1. restore the stack - back to the point where yin=B.
2. display *
3. assign a continuation to yang - this time, it is B"

The output is now @*@**@**

4. evaluate yin (B) with the continuation value of yang (B")

Jetzt (yin yang) als (B B") ausgewertet.

Wir wissen, was B tut. Es tut dies: 

1. restore the stack - back to the point where yin=A and yang were being initialised.
2. display *
3. assign a continuation to yang - this time, it is B'"

The output is now @*@**@***

4. evaluate yin with the continuation value of yang (B'")

Da der Stapel wurde bis zu dem Punkt, wo wiederhergestellt yin=A, (yin yang) als (A B'") ausgewertet wird.

.......

Ich denke, wir haben ein Muster jetzt.

Jedes Mal, wenn wir (yin yang) wir Schleife durch einen Stapel von B Fortsetzungen nennen, bis wir an, wenn yin=A zurück und wir @ anzuzeigen. Die wir Schleife durch den Stapel von B Fortsetzungen eines * jedes Mal zu schreiben.

(ich würde mich wirklich freuen, wenn diese grob richtig!)

Danke für die Frage.

YinYang Puzzle ist in Schema geschrieben. Ich nehme an, Sie die grundlegende Syntax von Schema kennen.

Aber ich nehme an, Sie wissen nicht, let* oder call-with-current-continuation, ich werde diese beiden Schlüsselwörter erklären.

Erklären Sie

let*

Wenn Sie bereits wissen, dass, können Sie überspringen zu Explain call-with-current-continuation

let*, die wie let aussieht, wirkt wie let, wird aber seine definierte Variablen (die (yin ...) und (yang ...)) eins nach dem anderen und mit Spannung bewerten. Das heißt, es wird zunächst bewerten yin und als yang.

Sie können mehr hier lesen: Let in Schema Mit

Erklären Sie

call-with-current-continuation

Wenn Sie bereits wissen, dass Sie zu Yin-Yang puzzle überspringen.

Es ist ein bisschen schwer call-with-current-continuation zu erklären. Also habe ich eine Metapher erklären verwenden wird.

Bild ein Zauberer, der einen Bann wusste, was call-with-current-continuation war. Sobald er den Zauber wirkt, würde er ein neues Universum erstellen und senden ihn selbst zu. Aber er konnte nichts im neuen Universum, sondern warten, dass jemand seinen Namen rief. Sobald genannt , der Assistent zum ursprünglichen Universum zurückkehren würde, den armen Kerl mit - ‚jemand‘ - in der Hand, und auf seinem Assistenten das Leben gehen. Wenn nicht genannt worden, wenn das neue Universum beendet, der Assistent auch auf die ursprüngliche Universum zurück.

Ok, lassen Sie uns mehr technischer Natur sein.

call-with-current-continuation ist eine Funktion, die eine Funktion als Parameter akzeptieren. Sobald Sie call-with-current-continuation mit einer Funktion F aufrufen, wird die aktuelle Fahrumgebung packen, die current-continuation genannt wird, als Parameter C, und an Funktion F senden und F auszuführen. Also das ganze Programm wird (F C). Oder mehr JavaScript ist: F(C);. C wirkt wie eine Funktion. Wenn C nicht in F genannt wird, dann ist es ein gewöhnliches Programm, wenn F zurückkehrt, call-with-current-continuation Wert als F Rückgabewert hat. Aber wenn C mit einem Parameter V aufgerufen wird, wird es wieder das ganze Programm ändern. Das Programm wechselt zurück zu einem Staat , wenn call-with-current-continuation genannt. Aber jetzt ergibt einen Wert call-with-current-continuation, die V ist. Und das Programm fortgesetzt wird.

Lassen Sie uns ein Beispiel nehmen. 

(define (f return)
  (return 2)
  3)
(display (f whatever)) ;; 3
(display (call-with-current-continuation f)) ;; 2
(display (call-with-current-continuation (lambda (x) 4))) ;; 4

Der erste display Ausgang 3, der Ursache.

Aber die zweite display Ausgang 2. Warum?

Lassen Sie uns tauchen hinein.

Wenn (display (call-with-current-continuation f)) Auswertung, wird es zunächst (call-with-current-continuation f) bewerten. Wir wissen, dass es das gesamte Programm

ändern 
(f C)

Unter Berücksichtigung der Definition für f, hat es eine (return 2). Wir müssen (C 2) bewerten. Das ist, wenn die continuation aufgerufen wird. So ist es das ganze Programm zurück zu

ändern 
(display (call-with-current-continuation f))

Aber jetzt hat call-with-current-continuation Wert 2. Also das Programm wird: 

(display 2)

Yin-Yang-Puzzle

Schauen wir uns das Rätsel. 

(let* ((yin
         ((lambda (cc) (display #\@) cc) (call-with-current-continuation (lambda (c) c))))
       (yang
         ((lambda (cc) (display #\*) cc) (call-with-current-continuation (lambda (c) c)))))
      (yin yang))

Machen wir es besser lesbar. 

(define (id c) c)
(define (f cc) (display #\@) cc)
(define (g cc) (display #\*) cc)
(let* ((yin
         (f (call-with-current-continuation id)))
       (yang
         (g (call-with-current-continuation id))))
      (yin yang))

Lassen Sie sich läuft das Programm in unserem Gehirn.

Rund 0

let* machen uns yin zuerst zu bewerten. yin ist 

(f (call-with-current-continuation id))

So bewerten wir (call-with-current-continuation id) zuerst. Es packt die aktuelle Umgebung, die wir nennen es C_0 mit anderer Fortsetzung in der Zeitlinie zu unterscheiden, und es tritt ein ganz neues Universum: id. Aber id gerade zurück C_0.

Wir sollten Denken Sie daran, was C_0 ist. C_0 ist ein Programm wie folgt aus: 

(let* ((yin
         (f ###))
       (yang
         (g (call-with-current-continuation id))))
      (yin yang))

### ist ein Platzhalter, die in der Zukunft wird durch den Wert gefüllt werden, dass C_0 zurücknimmt.

Aber id gibt nur C_0. Es ist nicht C_0 nennen. Wenn es nennt, werden wir C_0 Universum ein. Aber es hat nicht, so dass wir auch weiterhin yin bewerten. 

(f C_0) ;; yields C_0

f ist eine Funktion wie id, aber es hat einen Nebeneffekt -. Ausgeben @

So die Programmausgabe @ und lassen yin C_0 sein. Jetzt wird das Programm wird 

(let* ((yin C_0)
       (yang
         (g (call-with-current-continuation id))))
      (yin yang))

Nach yin ausgewertet, beginnen wir yang zu bewerten. yang ist 

(g (call-with-current-continuation id))

call-with-current-continuation hier eine weitere Fortsetzung, namens C_1 erstellen. C_1 ist: 

(let* ((yin C_0)
       (yang
         (g ###)))
      (yin yang))

### ist Platzhalter. Beachten Sie, dass in dieser Fortsetzung, yin Wert bestimmt wird (das ist, was let* tun). Wir sind sicher, dass yin Wert ist C_0 hier.

Da (id C_1) C_1 ist, so yang Wert ist 

(g C_1)

g hat einen Nebeneffekt - Ausgabe von *. So macht das Programm.

yang Wert ist jetzt C_1.

Inzwischen haben wir angezeigt @*

So, jetzt wird es: 

(let* ((yin C_0)
       (yang C_1))
      (yin yang))

Da beide yin und yang gelöst werden, sollten wir (yin yang) bewerten. Es ist 

(C_0 C_1)

Holy SH * T!

Aber schließlich wird C_0 genannt. So haben wir in den C_0 Universum fliegen und alles über diese sh * ts vergessen. Wir werden nie wieder in dieses Universum zurück.

Runde 1

C_0 nehmen mit C_1 zurück. Das Programm wird jetzt (Wenn Sie vergessen, was C_0 steht, gehen zurück, um es zu sehen): 

(let* ((yin
         (f C_1))
       (yang
         (g (call-with-current-continuation id))))
      (yin yang))

Ach, finden wir, dass yin den Wert noch nicht bestimmt. Also haben wir es bewerten. Im Prozess yin auszuwerten, geben wir einen @ als f der Nebenwirkung. Und wir wissen, yin ist C_1 jetzt.

Wir beginnen yang zu bewerten, wir über call-with-current-continuation kam wieder. Wir sind geübt. Wir schaffen eine Fortsetzung C_2 das steht für: 

(let* ((yin C_1)
       (yang
         (g ###)))
      (yin yang))

Und wir, * als g ausgeführt wird. Und wir kommen hier 

(let* ((yin C_1)
       (yang C_2))
      (yin yang))

So wir haben: 

(C_1 C_2)

Sie wissen, wohin wir gehen. Wir werden uns C_1 Universum. Wir erinnern daran, sie aus dem Speicher (oder Kopieren und Einfügen von Webseite). Es ist nun: 

(let* ((yin C_0)
       (yang
         (g C_2)))
      (yin yang))

Wir wissen, in C_1 Universum, yin Wert ermittelt wurde. So beginnen wir yang zu bewerten. Wie wir geübt sind, werde ich Ihnen direkt sagen, dass es * zeigt und wird: 

(C_0 C_2)

Jetzt haben wir gedruckt @*@**, und wir werden zu C_0 Universum Mitnahmen mit C_2.

Runde 2

Wie wir geübt sind, werde ich Ihnen sagen, dass wir zeigen ‚@‘, yin C_2 ist, und wir schaffen eine neue Fortsetzung C_3, das steht für: 

(let* ((yin C_2)
       (yang
         (g ###)))
      (yin yang))

Und wir * anzuzeigen, ist yang C_3, und es wird 

(C_2 C_3)

Und wir können weiter. Aber ich werde hier aufhören, ich habe Ihnen gezeigt, was Yin-Yang-Puzzle erste mehrere Ausgänge sind.

Warum die Zahl der * steigt?

Jetzt ist Ihr Kopf ist voll von Details. Ich werde eine Zusammenfassung machenfür Sie.

werde ich eine Haskell wie Syntax zu vereinfachen. Und cc ist die Abkürzung für call-with-current-continuation.

Wenn #C_i# von # klammert wird, bedeutet dies die Fortsetzung ist hier erstellen. ; Mittel Ausgabe 

yin = f cc id
yang = g cc id
yin yang

---

yin = f #C_0# ; @
yang = g cc id
yin yang

---

yin = C_0
yang = g #C_1# ; *
yin yang

---

C_0 C_1

---

yin = f C_1 ; @
yang = g #C_2# ; *
yin yang

---

C_1 C_2

---

yin = C_0
yang = g C_2 ; *
yin yang

---

C_0 C_2

---

yin = f C_2 ; @
yang = g #C_3#; *
yin yang

---

C_2 C_3

---

yin = C_1
yang = g C_3 ; *
yin yang

---

C_1 C_3

---

yin = C_0
yang = g C_3 ; *
yin yang

---

C_0 C_3

Wenn Sie genau beobachten, wird es Ihnen klar sein, dass

  1. Es gibt viele Universen (in der Tat unendlich), aber C_0 ist das einzige Universum, das von f gestartet. Andere gestartet von g.
  2. C_0 C_n macht immer eine neue Fortsetzung C_max. Es ist, weil C_0 das erste Universum ist die g cc id hat nicht ausgeführt worden ist.
  3. C_0 C_n auch @ anzuzeigen. C_n C_m die n nicht 0 wird * angezeigt werden soll.
  4. Von Zeit zu Zeit wird das Programm auf C_0 C_n abgeleitet, und ich werde beweisen, dass C_0 C_n von mehr und mehr anderen Ausdruck getrennt wird, was zu @*@**@***...

Ein wenig Mathematik

Angenommen c_n (n! = 0) ist die größte in allen Fortsetzungen nummeriert, und dann wird C_0 C_n genannt .

Annahme:. Wenn C_0 C_n genannt wird, C_n ist die aktuelle maximale nummerierte Fortsetzung

C_ {n + 1} durch C_0 C_n wie folgt erstellt: 

yin = f C_n ; @
yang = g #C_{n+1}#
yin yang

So schließen wir, dass:

Satz I. Wenn C_0 C_n genannt wird, wird es eine Fortsetzung produzieren C_ {n + 1} , wobei yin ist C_n .

Dann nächster Schritt ist C_n C_{n+1}. 

yin = C_{n-1}
yang = g C_{n+1} ; *
yin yang

Der Grund, warum yin C_{n-1} ist, dass, wenn C_n Wesen geschaffen es gehorcht Satz I .

Und dann C_{n-1} C_{n+1} genannt wird, und wir wissen, wann C_{n-1} erstellt wird, ist es auch befolgt Satz I . So haben wir C_{n-2} C_{n+1}.

C_{n+1} ist die in-Variation. Also haben wir den zweiten Satz haben:

Satz II. Wenn C_n C_m welche n < m und n > 0 genannt wird, wird es C_{n-1} C_m werden.

Und wir haben manuell geprüft C_0 C_1 C_2 C_3. Sie gehorchen die Annahme und alle Theoreme. Und wir wissen, wie erste @ und * erstellt wird.

So wir Muster unten schreiben können. 

C_0 C_1 ; @ *
C_[1-0] C_2 ; @ * *
C_[2-0] C_3 ; @ * * *
...

Es ist nicht so streng, aber ich möchte schreiben:

Q.E.D.

Als eine andere Antwort, sagte, wir erste simplify (call-with-current-continuation (lambda (c) c)) mit get-cc. 

(let* ((yin
         ((lambda (cc) (display #\@) cc) get-cc))
       (yang
         ((lambda (cc) (display #\*) cc) get-cc)) )
    (yin yang))

Nun sind die beiden Lambda nur eine identische Funktion mit Nebenwirkungen verbunden. Nennen wir diese Funktionen f (für display #\@) und g (für display #\*). 

(let* ((yin (f get-cc))
       (yang (g get-cc)))
    (yin yang))

Als nächstes müssen wir aus der Auswertung, um zu arbeiten. Um klar zu sein, werde ich einen „Schritt Ausdruck“ einführen, die jeder Auswertungsschritt explizit macht. Lassen Sie uns zuerst fragen: was ist die obige Funktion erfordert

Es erfordert Definitionen von f und g. In Schritt Ausdruck schreiben wir 

s0 f g =>

Der erste Schritt ist, zu berechnen yin, sondern über die zu bewerten von (f get-cc) und später erfordert get-cc.

Grob gesagt, get-cc gibt Ihnen einen Wert, den die „aktuelle Fortsetzung“ darstellt. Lassen Sie uns sagen, dass dies s1 ist, da dies der nächste Schritt ist. So schreiben wir 

s0 f g => s1 f g ?
s1 f g cc =>

Beachten Sie, dass die Parameter scopeless sind, was bedeutet, die f und g in s0 und s1 sind nicht notwendig, die gleichen und sie sind nur innerhalb des aktuellen Schritt verwendet werden. Dies macht die Kontextinformation explizit. Nun, was ist der Wert für cc? Da es „aktuelle Fortsetzung“ ist, es ist eine Art des gleichen s1 mit f und g auf den gleichen Wert gebunden. 

s0 f g => s1 f g (s1 f g)
s1 f g cc =>

Sobald wir cc haben, können wir f get-cc bewerten. Da auch f nicht in dem folgenden Code verwendet wird, wir müssen nicht auf diesem Wert übergeben. 

s0 f g => s1 f g (s1 f g)
s1 f g cc => s2 g (f cc)
s2 g yin =>

Der nächste Schritt ist das ähnlich für yang. Aber jetzt haben wir noch einen Wert weitergeben. yin 

s0 f g => s1 f g (s1 f g)
s1 f g cc => s2 g (f cc)
s2 g yin => s3 g yin (s3 g yin)
s3 g yin cc => s4 yin (g cc)
s4 yin yang =>

Schließlich ist der letzte Schritt yang zu yin anzuwenden. 

s0 f g => s1 f g (s1 f g)
s1 f g cc => s2 g (f cc)
s2 g yin => s3 g yin (s3 g yin)
s3 g yin cc => s4 yin (g cc)
s4 yin yang => yin yang

Dies beendet das Konstrukt aus Schritt Ausdruck. Übersetzt es zurück an Schema ist einfach: 

(let* ([s4 (lambda (yin yang) (yin yang))]
       [s3 (lambda (yin cc) (s4 yin (g cc))]
       [s2 (lambda (yin) (s3 yin ((lambda (cc) (s3 yin cc))))]
       [s1 (lambda (cc) (s2 (f cc)))])
      (s1 s1))

Die detaillierte Auswertung Ordnung (hier das Lambda im Innern des Körpers von s2 wurde einfach als Teilbewertung s3 yin ausgedrückt statt (lambda (cc) (s3 yin cc))): 

(s1 s1)
=> (s2 (f s1))
=> @|(s2 s1)
=> @|(s3 s1 (s3 s1))
=> @|(s4 s1 (g (s3 s1)))
=> @*|(s4 s1 (s3 s1))
=> @*|(s1 (s3 s1))
=> @*|(s2 (f (s3 s1)))
=> @*@|(s2 (s3 s1))
=> @*@|(s2 (s3 s1))
=> @*@|(s3 (s3 s1) (s3 (s3 s1)))
=> @*@|(s4 (s3 s1) (g (s3 (s3 s1))))
=> @*@*|(s4 (s3 s1) (s3 (s3 s1)))
=> @*@*|(s3 s1 (s3 (s3 s1)))
=> @*@*|(s4 s1 (g (s3 (s3 s1))))
=> @*@**|(s4 s1 (s3 (s3 s1)))
=> @*@**|(s1 (s3 (s3 s1)))
=> ...

(Denken Sie daran, wenn s2 oder s4 Auswertung der Parameter wird zuerst ausgewertet werden

Dies ist ein altes Rätsel vom Meister der Verschleierung David Madore, der erstellt unlambda. Das Puzzle hat comp.lang.scheme mehrere diskutiert Zeiten.

Eine schöne Lösung von Taylor Campbell: https://groups.google.com/d/msg/comp .lang.scheme / pUedvrKYY5w / uIjTc_T1LOEJ

Der Original-Beitrag von David Madore (1999): https://groups.google.com/d/msg/comp .lang.scheme / Fysq_Wplxsw / awxEZ_uxW20J

Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit StackOverflow
scroll top