"Yin and Yang Puzzle" in Scheme Language
There is a famous "YANG PUZZLE" in the Scheme language, probably such a few lines of code:
(let * (yin ((Lambda (foo) (newline) foo)
(Call / CC (Lambda (Bar))))))))
(YANG ((Lambda (Foo) (Write-char # / *) foo)
(Call / CC (Lambda Bar))))))))
(yin yang))
Although the program is short, I saw it for the first time, but I can't guess it. From the surface, I roughly know that the Call / CC will let the program fall into a dead cycle, but it is really unclear what logic is in the end. Take the program in the scheme environment, scare me, the result is actually like this:
*
**
***
****
*****
******
*******
...
Then, I wanted the finger to think about a whole day, and I can't understand this "yin and yang puzzle". There are many people who talk about this puzzle on the Internet. There are very few people who dismiss this puzzle. I simply write my understanding of this problem, not necessarily correct, for everyone.
The first thing to figure out is that this "yin and yang puzzle" procedure is what structure. We look out from the outside:
(Call / CC (Lambda (Bar) Bar)
This sentence transmits the current Continal Continual to anonymous process, while the latter simply returns the incoming parameters. That is, the role of this sentence is actually getting the current continues. The following combination
((NEWLINE) FOO
(Call / CC (Lambda (Bar) Bar)))
It means that the current continues to be used as a parameter, and the lambda (foo) foo), the latter is then output a newline, and then simply returns the incoming parameters. Further:
(YIN ((Lambda (Foo) (Newline) Foo
(Call / CC (Lambda (Bar))))))))
Its role is to make local variable YIN bind to the Call / CC to continue after outputting a wrap. Similar to YANG binding. And the following sentence
(YANG)
That is, in the current YIN and YANG binding environment, YIN is called as a parameter in yang. Because in Scheme, the so-called contingent is a process, which can be called or play a role of parameters. Therefore, (yin yang) syntax is no problem, the key is what is the result of such a call, this is not a look, maybe I am too dull, smart people can Soon find the answer).
Forget it, since you can't see it, you will first put the blame such as YANG. I have finished thinking, the whole "yin and yang puzzle" actually did such a few things:
1 Start execution (let *) structure
2 get the current continuation
3 outputting a newline
4 Continue to Yin 2
5 get the current continued
6 output an asterisk
7 Get the continuation of 5 get YANG
8 call yin as a parameter
It seems to be the 8 steps, but in order to refer to its running logic, you must determine two things:
1, (let *) What is the structure?
This question does not need me to answer, and there are many books and materials. Only a little most important: (let *) has a variable list, such as YIN and YANG, (let *) first created the binding of the first variable, then binds in the first variable In the known environment, the binding of the second variable is created, so as so far until all bindings are created, the value of the host expressions are obtained in the environment that contains all of these variables. In this example, the subject expression is a simple sentence: (YANG) 2, step 2 and 5 get the end of the end?
If the reader can't do anything is to continue, or if you don't know how to use it, it is best to check the book check. I only emphasize that the Call / CC has continued to be the "all future" of the current expression of the Call / CC. "All Future" This word is copied from Scheme's standard document R5RS. It means that when there is no Call / CC, what we want to do after seeking the value of the expression, now call CALL directly What will do when the / cc's result process.
That is, if 2 is not a Call / CC but a normal expression, then we will do these things after the value of the expression: output a newline, to give YIN, create a value Contains a new environment of YIN and then completes the follow-up step in the new environment - I record this matter (a).
Now, the code has obtained the current continuation at 2. This means that once we will call this continuation, it will repeat the same steps when calling, and the "expression value" used at this time is the parameter we passed during the call to continue.
Similarly, if you call 5, you will do these things: Output an asterisk, assign the value of the expression to yang, create a new environment with YANG, then complete the follow-up steps in the new environment - I Remember this matter (B).
Ok, after I figure out these two questions, we can try to run a "yin and yang puzzle". In the following parsing, we will continue to be called CA 2, and continue to be called CB:
1. Get the continuation of CA, output a newline, give CA to Yin, I put these steps to:
/ yin = ca (_)
Among them, / indicates that the output wrap, the CA (_) indicates the continuation of 2, and the value of YIN is not defined before the continuation of YIN, so the parentheses is notified as _
2, in the environment containing Yin, get the continuation of CB, output an asterisk, give CB to yang, remember:
* yang = CB (CA (_))
Among them, CB (CA (_)) represents the continuation obtained at 5, before the continuation of YANG, YIN value is CA (_)
3, calling (YANG). From the previous analysis, we can know that this call to do is to continue the YANG binding CB (Ca (_)) as a parameter, call YIN binding to continue CA (_). With the sentence (a) that just analyzed (a), it is: Output a newline, assigns YIN (CA (_)) value to YIN, create a new environment containing YIN, and then completes the follow-up step in the new environment. Referred to as
/ yin = cb (CA (_))
4, now "complete the follow-up step". The subsequent steps are 5, so the next should be:
* YANG = CB (CB (CA (_))))
5, it is a sentence that again (yin yang). The process of binding in YIN and YANG is now not the same. Most importantly, Yin is bound to CB (CA (_)) instead of CA (...), which means that the call to Yin will be (b) what is described, not (a) described. . If we can make a work, now this means: output an asterisk, gives YANG, creates a new environment containing YANG, and then completing the follow-up steps in a new environment. Remember * yang = CB (CB (CA (_)))
There is a question is, what is it in YIN now? Attention And we call Yin now, in a sense, this is equivalent to returning to the environment in which you have continued, we can simply think that after the call, YIN's value has changed back to CA (_). Record (only "approximation" here, then we will discuss why YIN's value will change):
YIN = CA (_)
6, this time I immediately met the next round, because YIN's value was CA (_), so we will return to (a) in the things described, remember:
/ yin = CB (CB (CA (_))))
7, just like this "running", write more steps:
* yang = CB (CB (CB (CA (_)))))))))))
* yang = CB (CB (CB (CA (_)))))))))))
YIN = CB (CA (_))
* yang = CB (CB (CB (CA (_)))))))))))
YIN = CA (_)
/ yin = CB (CB (CB (CA (_))))))))
...
Connect the output obtained from steps above:
/
* /
** /
*** /
...
Isn't this the "yin and yang puzzle" operation results? It seems that things are still more smooth, but we have a problem without solving: When Yin's value is CB (...), why is YIN's value going back? This issue is related to the environment model used by Scheme. It is recommended that you think about the contents of the "Computer Program Construction and Explanation (SICP)" Chapter 3. I explained the situation of the environment in the "yin and yang puzzle" in the SICP, in the two figures below:
1, before entering (let *), there is only one initial environment. Bind CA to YIN and create an environment containing YIN, which is actually equivalent to creating a sub-environment containing YIN, and a pointer pointing to the initial environment in the sub-environment. It is green Yin in the left. Wherein, the solid arrow indicates the reference parent environment, and the dotted arrow indicates the variable binding.
2. In the sub-environment just created, bind CB to yang, and create a new sub-environment containing YANG, and a pointer in the new sub-environment indicates a sub-environment that contains Yin. This is the green YANG in the left figure.
3, (yin yang) When the CA process of YIN Binding is a environment that contains Yin, the left picture has a blue YIN, but the binding of Yin points to the green CB. . Then create a blue yang, which points to a new CB. Now we use blue YIN and YANG.
4. Next (YIN YANG), because YIN's binding points to the green CB, its meaning is in the green Yin environment, recreate the environment that contains YANG. Thus, green Yang is replaced by the newly created red yang, and the red yang's binding points to the blue CB, the red yang's parent environment is also consistent with green YANG, is green Yin. This is the look in the right picture. Now, we use green Yin and red yang. In other words, I am still using Yin, which is pointing to CB, now restoring into Yin using green. This is why YIN's value will change back. At the same time, because the red yang point to the blue CB, the next YIN will change back to the blue yin, then the next time will change back to the green Yin, so "Yin and Yang Puzzle" will compare one by one Output an asterisk. This is the answer to the "yin and yang puzzle" I concluded (the above explanation is just a conceptual model, and the specific implementation of Scheme is not completely equivalent). However, this answer is manually reasoning, can it be automatically certified by the program? It should be ok, I extend the "yin and yang puzzle", allowing the program to automatically track each continued semantic and automatically print out. The modified code is as follows:
(Define CC-DICT '())
(Define (INSERT-CC! CC FLAG)
(if (ASSQ CC CC-DICT)
#f
(set! cc-dict
(cons)
(Cons Flag (Length CC-DICT))))
CC-DICT))))))))))))))))))))))
(DEFINE (Display-CC CC Prefix)
(Display Prefix)
(Display # / ()
(Lambda (CC-PAIR)
(COND (CC-PAIR
(Display (CADR CC-PAIR))
(Display # /,)
(Display (CDDR CC-PAIR))))))))))
(ASSQ CC CC-DICT)))
(Display # /)))))
(LET 5) (yang #f))
(Call / CC
(Lambda (exit)
(let * (yin ((Lambda (foo)
(Write-char # //)
NEWLINE
(INSERT-CC! Foo # / a)
(Display-cc foo "yin")
(Display-cc yang "yang")
(set! count (- count 1))
(if (= 0 count) (EXIT 'END) FOO))
(Call / CC (Lambda (Bar))))))))
(YANG (Lambda (Foo)
(write-char # / *)
(INSERT-CC! Foo # / b)
(Display-cc yin "yin")
(Display-cc foo "yang")
foo)
(Call / CC (Lambda Bar))))))))
(YANG))))))))))))))))))))
The above code shows the running process of the top 5 lines of the "yin and yang puzzle". Each time you assign the value for Yin, Yang, the code prints Yin, YANG, printing the format YIN (A, 0) yang (B, 1 ) Or similar format, where yin (a, 0) represents YIN's value to continue CA, which continues to continue (based on 0 index). The result of the above code is:
/
YIN (A, 0) yang () * yin (a, 0) yang (b, 1) /
YIN (B, 1) YANG () * yin (b, 1) yang (b, 2) * yin (a, 0) yang (b, 2) / yin (b, 2) yang () * yin (b, 2) YANG (B, 3) * YIN (B, 1) YANG (B, 3) * YIN (A, 0) YANG (B, 3) /
YIN (B, 3) yang () * yin (b, 3) yang (b, 4) * yin (b, 2) yang (b, 4) * yin (b, 1) yang (b, 4) * yin (a, 0) yang (b, 4) /
YIN (B, 4) yang ()
From this run, we can clearly see the changes of yin and yang, or see how YIN is changed back to the original value in each row, and eventually change back to CA to output change .
