Comment fonctionne le puzzle yin-yang?

Question

Je suis en train de saisir la sémantique de l'appel / cc dans le schéma, et la page de Wikipédia sur continuations montre le puzzle yin-yang comme exemple:

(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))

Il devrait @*@**@***@****@... de sortie, mais je ne comprends pas pourquoi; Je pense à la sortie @*@********* ...

Quelqu'un peut-il expliquer en détail pourquoi le casse-tête yin-yang fonctionne comme ça marche?

Answer 1

Je ne pense pas que je comprends entièrement celui-ci, mais je ne peux penser à un ( très main ondulé) explication de ceci:

• Le premier @ et * sont imprimées lorsque yin et yang sont d'abord liés au let*. (yin yang) est appliqué, et il remonte vers le haut, à droite après le premier appel / cc est terminée.
• La prochaine @ et * sont imprimés, puis un autre * est imprimé parce que cette fois par le biais, yin est lié à nouveau la valeur du deuxième appel / cc.
• (yin yang) est appliqué à nouveau, mais cette fois il est dans l'exécution de l'environnement de yang d'origine , où yin est lié au premier appel / cc, donc le contrôle revient à imprimer un autre @. L'argument yang contient la suite qui a été rattrapées au deuxième passage, qui comme nous l'avons déjà vu, entraînera l'impression **. Donc, sur ce troisième passage, @* sera imprimé, cette suite double étoile impression s'invoqué, il finit avec 3 étoiles, puis cette suite à trois étoiles est capturé re, ...

Answer 2

Comprendre le schéma

Je pense qu'au moins la moitié du problème avec la compréhension de ce casse-tête est la syntaxe Scheme, dont la plupart ne connaissent pas bien.

Tout d'abord, je trouve personnellement le call/cc x d'être plus difficile à comprendre que l'alternative équivalente, x get/cc. Il reste appels x, faisant passer la continuation courante , mais il est en quelque sorte plus prête à être représenté dans mon circuit du cerveau.

Dans cet esprit, la construction (call-with-current-continuation (lambda (c) c)) devient simplement get-cc. Nous sommes maintenant à ceci:

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

L'étape suivante est le corps de la lambda intérieure. (display #\@) cc, dans la syntaxe plus familière (pour moi, de toute façon) signifie print @; return cc;. Alors que nous sommes, Réécrivons aussi lambda (cc) body que function (arg) { body }, supprimer un groupe de parenthèses, et les appels de fonction de modification de la C-comme la syntaxe, pour obtenir ceci:

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

Il commence à faire plus de sens maintenant. Il est maintenant un petit pas de réécrire complètement dans ce type C syntaxe (ou JavaScript comme, si vous préférez), pour obtenir ceci:

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

Le plus dur est maintenant terminée, nous avons décodés ce schéma de! Je rigole; il était difficile parce que je n'avais pas d'expérience avec le schéma. Donc, nous allons apprendre à comprendre comment cela fonctionne réellement.

Une amorce sur continuations

Observez le noyau étrangement formulé du yin et du yang: il définit une fonction et puis appelle immédiatement . Il ressemble (function(a,b) { return a+b; })(2, 3), qui peut être simplifié à 5. Mais simplifier les appels à l'intérieur yin / yang serait une erreur, parce que nous ne sommes pas ce passage une valeur ordinaire. Nous passons la fonction continuation .

Une suite est une bête étrange à première vue. Considérons le programme beaucoup plus simple:

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

Dans un premier temps x est réglé sur l'objet de poursuite en cours (ours avec moi), et print x est exécuté, quelque chose comme l'impression <ContinuationObject>. Jusqu'à présent, si bon.

Mais la poursuite est comme une fonction; il peut être appelé avec un argument. Ce qu'il fait est:. Prendre l'argument, puis sur saut où que la poursuite a été créé, la restauration de tout contexte, et faisant en sorte que revient get-cc cet argument

Dans notre exemple, l'argument est 5, donc nous sautons essentiellement en arrière en plein milieu de cette déclaration de var x = get-cc, mais cette fois revient get-cc 5. Alors x devient 5, et l'instruction suivante continue d'imprimer 5. Une fois que nous essayons d'appel 5(5), ce qui est une erreur de type, et le programme se bloque.

Notez que l'appel de la poursuite est un saut , pas un appel. Il ne retourne jamais à l'endroit où la poursuite a été appelé. C'est important.

Comment fonctionne le programme

Si vous avez suivi cela, alors ne soyez pas vos espoirs: cette partie est vraiment le plus dur. Voici notre programme nouveau, laissant tomber les déclarations de variables parce que c'est pseudo-code de toute façon:

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

La première ligne de temps 1 et 2 sont touchés, ils sont simples maintenant: obtenir la suite, appelez la fonction (arg), impression @, retour, magasin que la poursuite en yin. Même avec yang. Nous avons maintenant imprimé @*.

Ensuite, nous appelons à la poursuite yin, en lui passant yang. Cela nous fait sauter à la ligne 1, à l'intérieur que get-cc, et le faire revenir yang à la place. La valeur de yang est maintenant passée dans la fonction, qui imprime @, puis retourne la valeur de yang. Maintenant yin est affecté que la poursuite qui a yang. Ensuite, nous procédons simplement à la ligne 2: get c / c, impression *, magasin ee c / c en yang. Nous avons maintenant @*@*. Et enfin, nous allons à la ligne 3.

Rappelez-vous que yin a maintenant la poursuite de lorsque la ligne 2 a été exécuté. Donc, on saute à la ligne 2, l'impression d'une seconde * et la mise à jour yang. Nous avons maintenant @*@**. Enfin, appelez la poursuite de yin à nouveau, qui va sauter à la ligne 1, l'impression d'un @. Etc. Franchement, à ce stade, mon cerveau lance une exception OutOfMemory et je perds la trace de tout. Mais au moins nous sommes arrivés à @*@**!

Il est difficile de suivre et encore plus difficile à expliquer, évidemment. La meilleure façon de le faire serait de parcourir dans un débogueur qui peut représenter continuations, mais hélas, je ne sais pas de tout. J'espère que vous avez apprécié cette; J'ai certainement.

Answer 3

Rêveries d'abord, réponse possible à la fin.

Je pense que le code peut être réécrite comme ceci:

; 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)) )
     )
)

Ou avec quelques déclarations d'affichage supplémentaires pour aider à voir ce qui se passe:

; 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) )
     )
)

Ou comme ceci:

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

Réponse possible

Cela peut ne pas être juste, mais je vais avoir un aller.

Je pense que le point essentiel est qu'une continuation « appelé » retourne la pile à un état précédent - comme si rien d'autre était arrivé. Bien sûr, il ne sait pas que nous l'avons suivi en affichant des caractères @ et *.

Nous définissons d'abord yin être une A de continuation qui le fera:

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)

Mais si l'on appelle une continuation de yang, cela se produit:

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)

Nous commençons ici.

La première fois que vous obtenez par yin=A et yang=B comme yin et yang sont en cours d'initialisation.

The output is @*

(Les deux A et B continuations sont calculées.)

(yin yang) est évalué comme (A B) pour la première fois.

Nous savons ce que A fait. Il fait ceci:

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')

(yin yang) est évaluée comme (B B').

Nous savons ce que B fait. Il fait ceci:

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')

Depuis la pile a été restaurée au point où yin=A, (yin yang) est évaluée comme (A B').

Nous savons ce que A fait. Il fait ceci:

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")

Nous savons ce que B' fait. Il fait ceci:

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")

(yin yang) est évaluée comme (B B").

Nous savons ce que B fait. Il fait ceci:

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'")

Depuis la pile a été restaurée au point où yin=A, (yin yang) est évaluée comme (A B'").

.......

Je pense que nous avons un modèle maintenant.

Chaque fois que nous nommerons en boucle de (yin yang) de nous à travers une pile de B continuations jusqu'à ce que nous reviendrons quand yin=A et nous affichons @. La boucle de nous à travers la pile de continuations de B écriture un * à chaque fois.

(je serais vraiment heureux si cela est à peu près juste!)

Merci pour la question.

Answer 4

YinYang puzzle est écrit dans le schéma. Je suppose que vous connaissez la syntaxe de base du schéma.

Mais je suppose que vous ne savez pas let* ou call-with-current-continuation, je vais vous expliquer ces deux mots-clés.

Expliquez let*

Si vous savez déjà que, vous pouvez passer à Explain call-with-current-continuation

let*, qui ressemble let, agit comme let, mais évaluera ses variables définies (le (yin ...) et (yang ...)) un par un et avec empressement. Cela signifie, il va d'abord évaluer yin et que yang.

Vous pouvez en lire plus ici: En utilisant Soit dans le schéma

Expliquez call-with-current-continuation

Si vous savez déjà que, vous pouvez passer à Yin-Yang puzzle.

Il est un peu difficile à expliquer call-with-current-continuation. Je vais donc utiliser une métaphore pour l'expliquer.

Image d'un assistant qui connaissait un sort qui était call-with-current-continuation. Une fois qu'il a jeté le sort, il créerait un nouvel univers, et lui envoyer-moi à lui. Mais il ne pouvait ne rien faire dans le nouvel univers, mais en attendant que quelqu'un appelle son nom. Une fois appelé , l'assistant retournerait à l'univers d'origine, ayant le pauvre gars - « quelqu'un » - à la main, et continuer sa vie assistant. Si pas été appelé, lorsque le nouvel univers terminé, l'assistant aussi retourné à l'univers d'origine.

Ok, nous allons être plus technique.

call-with-current-continuation est une fonction qui accepte une fonction en tant que paramètre. Une fois que vous appelez call-with-current-continuation avec une fonction F, il emballera l'environnement en cours d'exécution en cours, qui est appelé current-continuation, en tant que paramètre C, et l'envoyer à la fonction F et exécuter F. Donc, tout le programme devient (F C). Ou être plus JavaScript: F(C);. C agit comme une fonction. Si C n'est pas appelé F, alors il est un programme ordinaire, lors du retour de F, call-with-current-continuation a une valeur en tant que valeur de retour de F. Mais si C est appelée avec un paramètre V, il va changer à nouveau l'ensemble du programme. Le programme revient à État lorsque call-with-current-continuation été appelé. Mais maintenant, les rendements call-with-current-continuation une valeur, qui est V. Et le programme se poursuit.

Prenons un exemple.

(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

Le premier display de sortie de 3, de la cause.

Mais la deuxième display de sortie 2. Pourquoi?

Soit Plongeons en elle.

Lors de l'évaluation (display (call-with-current-continuation f)), il va d'abord évaluer (call-with-current-continuation f). Nous savons que cela va changer l'ensemble du programme à

(f C)

Compte tenu de la définition de f, il a un (return 2). Nous devons évaluer (C 2). C'est quand le continuation appelé. Elle peut changer l'arrière tout programme à

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

Mais maintenant, call-with-current-continuation a une valeur 2. Ainsi, le programme devient:

(display 2)

casse-tête Yin-Yang

look Let au puzzle.

(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))

La marque Let plus lisible.

(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))

run Let le programme dans notre cerveau.

Ronde 0

let* nous faire d'évaluer yin premier. yin est

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

Nous évaluons (call-with-current-continuation id) premier. Il emballe l'environnement actuel, que nous appelons C_0 de distinguer avec d'autres continuation dans la ligne de temps, et il entre dans un nouvel univers: id. Mais id retourne juste C_0.

Nous devons nous rappeler ce que C_0 est. C_0 est un programme comme celui-ci:

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

### est un espace réservé, qui à l'avenir sera rempli par la valeur C_0 ramène.

Mais id retourne juste C_0. Il ne remet pas C_0. Si elle appelle, nous allons entrer dans l'univers de C_0. Mais il n'a pas, donc nous continuons à évaluer yin.

(f C_0) ;; yields C_0

f est une fonction comme id, mais il a un effet secondaire. - délivrer en sortie @

Ainsi, le @ de sortie du programme et laissez yin être C_0. Maintenant, le programme devient

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

Après yin évalué, nous commençons à évaluer yang. yang est

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

call-with-current-continuation ici créer une autre poursuite, C_1 nommé. C_1 est:

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

### est espace réservé. Notez que dans cette suite, la valeur de yin est déterminée (c'est ce que let* faire). Nous sommes sûrs que la valeur de yin est C_0 ici.

Depuis (id C_1) est C_1, si la valeur de yang est

(g C_1)

g a un effet secondaire - délivrer en sortie *. Ainsi, le programme fait.

La valeur de yang est maintenant C_1.

A l'heure actuelle, nous avons affiché @*

Alors maintenant, il devient:

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

à la fois yin et yang sont résolus, nous devons évaluer (yin yang). Il est

(C_0 C_1)

Saint-SH * T!

Mais enfin, C_0 est appelé. Donc, nous volons dans l'univers de C_0 et oublier tout au sujet de ces Sh * ts. Nous ne reviendrons jamais dans cet univers nouveau.

Round 1

C_0 prendre avec le dos de C_1. Le programme devient maintenant (Si vous oubliez ce que C_0 signifie, revenir en arrière pour le voir):

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

Ah, on trouve la valeur de cette yin n'a pas encore été déterminé. Donc, nous évaluons. Dans le processus d'évaluation yin, nous affichons un @ comme effet secondaire de f. Et nous savons yin est C_1 maintenant.

Nous commençons à évaluer yang, nous avons rencontré call-with-current-continuation à nouveau. Nous pratiquons. Nous créons une C_2 de continuation qui signifie:

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

Et nous affichons un * comme g d'exécution. Et nous venons ici

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

Nous avons donc obtenu:

(C_1 C_2)

Vous savez où nous allons. Nous allons à l'univers de C_1. Nous rappelons de la mémoire (ou copier-coller de la page Web). Il est maintenant:

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

Nous savons que dans l'univers de C_1, la valeur de yin a été déterminée. Donc, nous commençons à évaluer yang. Comme nous pratiquons, je directement vous dire qu'il affiche * et devient:

(C_0 C_2)

Maintenant, nous avons imprimé @*@**, et nous allons à l'univers de la prise de vue avec C_0 C_2.

Round 2

Comme nous pratiquons, je vais vous dire que nous affichons « @ », yin est C_2, et nous créons une nouvelle continuation C_3, qui signifie:

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

Et nous affichons *, yang est C_3, et il devient

(C_2 C_3)

Et nous pouvons continuer. Mais je vais arrêter ici, je vous ai montré ce que plusieurs premières sorties de casse-tête Yin-Yang sont.

Pourquoi le nombre d'augmentations de *?

Maintenant, votre tête est pleine de détails. Je vais faire un résumépour vous.

Je vais utiliser une syntaxe Haskell comme pour simplifier. Et cc est court pour call-with-current-continuation.

Lorsque #C_i# est encadrée par #, cela signifie que la poursuite est de créer ici. des moyens de sortie ;

---

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

Si vous observez attentivement, il sera évident pour vous que

1. Il y a beaucoup d'univers (en fait infini), mais C_0 est le seul univers qui a commencé par f. D'autres ont commencé par se g.
2. C_0 C_n fait toujours une nouvelle continuation C_max. C'est parce que C_0 est le premier univers qui a g cc id pas été exécutée.
3. C_0 C_n afficher également @. C_n C_m qui n est pas 0 affichera *.
4. Heure par heure le programme est déduit de C_0 C_n, et je vais prouver que C_0 C_n est séparé par une expression de plus en plus d'autres, ce qui conduit à @*@**@***...

Un peu de mathématiques

Supposons (n! = 0) est le plus grand numéro dans tous les continuations, puis C_0 C_n est appelé .

Hypothèse:. Quand C_0 C_n est appelé, C_n est le courant maximal suite numéroté

est créé par C_0 C_n comme ceci:

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

Nous en concluons que:

Théorème I. Si C_0 C_n est appelée, elle produira une suite , dans lequel yin est C_n .

Ensuite, l'étape suivante est C_n C_{n+1}.

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

La raison pour laquelle yin est C_{n-1} est que lorsque l'être de C_n créé obéit Théorème I .

Et puis C_{n-1} C_{n+1} est appelé, et nous savons quand C_{n-1} est créé, il a également obéi Théorème I . Nous avons donc C_{n-2} C_{n+1}.

C_{n+1} est en variation. Nous avons donc le second théorème:

Théorème II. Si C_n C_m qui n < m et n > 0 est appelée, elle deviendra C_{n-1} C_m.

Et nous avons manuellement vérifié C_0 C_1 C_2 C_3. Ils obéissent à l'Assomption et tous Theorems. Et nous savons d'abord @ et * est créé.

On peut donc écrire des motifs ci-dessous.

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

pas stricte, mais je voudrais écrire:

Q.E.D.

Answer 5

Comme une autre réponse dit, nous avons d'abord Simplify (call-with-current-continuation (lambda (c) c)) avec get-cc.

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

Maintenant, les deux lambda sont juste une fonction identique associée à des effets secondaires. Appelons les fonctions f (pour display #\@) et g (pour display #\*).

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

Ensuite, nous devons travailler sur l'ordre d'évaluation. Pour être clair, je vais vous présenter une « expression étape » qui fait toutes les étapes d'évaluation explicite. D'abord nous allons demander: quelle est la fonction ci-dessus nécessite

Il faut des définitions de f et g. Dans l'expression étape, nous écrivons

s0 f g =>

La première étape consiste à calculer yin, mais qui nécessitent d'évaluer des (f get-cc) et le besoin plus tard get-cc.

grosso modo, get-cc vous donne une valeur qui représente la « continuation actuelle ». Disons que cela est s1 puisque c'est l'étape suivante. Donc nous écrivons

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

Notez que les paramètres sont scopeless, ce qui signifie la f et g dans s0 et s1 ne sont pas nécessairement les mêmes et ils ne doivent être utilisés dans l'étape en cours. Cela rend les informations de contexte explicite. Maintenant, quelle est la valeur pour cc? Comme il est « continuation courante », il est un peu la même s1 avec f et g lié à la même valeur.

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

Une fois que nous avons cc, nous pouvons évaluer f get-cc. En outre, étant donné que f n'est pas utilisé dans le code suivant, nous ne devons pas transmettre cette valeur.

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

La prochaine est similaire pour yang. Mais maintenant, nous avons une plus grande valeur à transmettre. 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 => 

Enfin, la dernière étape consiste à appliquer à yang 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 => yin yang

a terminé la construction d'expression de l'étape. Retraduire le schéma est simple:

(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))

L'ordre d'évaluation détaillée (ici le lambda à l'intérieur du corps de s2 a simplement exprimé en s3 yin d'évaluation partielle plutôt que (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)))
=> ...

(Rappelez-vous, lors de l'évaluation s2 ou s4, le paramètre va être évaluée premier

Answer 6

un vieux casse-tête du maître de l'obscurcissement David Madore, qui créé unlambda. Le casse-tête a été discuté plusieurs comp.lang.scheme fois.

Une belle solution de Taylor Campbell: https://groups.google.com/d/msg/comp .lang.scheme / pUedvrKYY5w / uIjTc_T1LOEJ

Le message original de David Madore (1999): https://groups.google.com/d/msg/comp .lang.scheme / Fysq_Wplxsw / awxEZ_uxW20J