Как ян иня озадачивает работу?

Question

Как ян иня озадачивает работу?

Я пытаюсь схватить семантику call/cc в Схеме, и страница Wikipedia на продолжениях показывает загадку яна иня примером:

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

Это должно произвести @*@**@***@****@..., но я не понимаю почему; я ожидал бы, что это произведет @*@*********...

Кто-то может объяснить подробно, почему загадка яна иня работает способ, которым она работает?

34

scheme callcc

задан Timwi 23 March 2012 в 22:15

2 ответа

Сначала размышления, в конце возможный ответ.

Я думаю, что код можно переписать следующим образом:

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

Или с некоторыми дополнительными операторами отображения, чтобы помочь увидеть, что происходит:

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

Или так:

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

Возможный ответ

Это может быть не так хорошо, но я пойду.

Я думаю, что ключевым моментом является то, что «вызываемое» продолжение возвращает стек в какое-то предыдущее состояние - как будто ничего другого не произошло. Конечно, он не знает, что мы отслеживаем его, отображая символы @ и * .

Изначально мы определяем инь как продолжение A , которое будет делать следующее:

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)

Но если мы вызываем продолжение ян , происходит следующее:

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)

Начнем здесь.

В первый раз вы получаете инь = A и ян = B , поскольку инициализируются инь и ян .

The output is @*

(Вычисляются оба A и B продолжения.)

Теперь (инь янь) оценивается как (AB) в первый раз.

Мы знаем, что делает A . Он делает это:

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

Теперь (инь ян) оценивается как (B B ') .

Мы знаем, что делает B .Он делает следующее:

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

Поскольку стек был восстановлен до точки, где инь = A , (инь янь) оценивается как (A B ') .

Мы знаем, что делает A . Он делает это:

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

Мы знаем, что делает B '. Он делает следующее:

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

Теперь (инь ян) оценивается как (BB ") .

Мы знаем, что делает B . Он делает это :

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

Поскольку стек был восстановлен до точки, где инь = A , (инь ян) оценивается как (A B '") .

.......

Думаю, теперь у нас есть образец.

Каждый раз, когда мы вызываем (инь ян) , мы перебираем стек из B продолжений, пока не вернемся к инь = A и отобразим @ . Мы перебираем стек продолжений B , каждый раз записывая * .

(Я был бы очень рад, если это примерно верно!)

Спасибо за вопрос.

6

ответ дан 27 November 2019 в 17:00

Другие вопросы по тегам:

scheme callcc

Похожие вопросы:

score 16 · Accepted Answer

Не думаю, что я полностью понимаю это, но могу придумать только одно ( чрезвычайно волнистое) объяснение это:

Первые @ и * печатаются, когда инь и ян сначала связываются в let * . Применяется (инь ян) , и он возвращается наверх сразу после завершения первого вызова / cc.
Следующие @ и * печатаются, затем печатается еще один *, потому что на этот раз yin повторно привязан к значению второго вызова / cc.
(инь ян) применяется снова, но на этот раз он выполняется в исходной среде ян , где инь привязан к первый вызов / cc, поэтому управление возвращается к печати другого @.Аргумент yang содержит продолжение, которое было повторно захвачено при втором проходе, что, как мы уже видели, приведет к печати ** . Таким образом, на этом третьем проходе будет напечатано @ * , затем будет вызвано это продолжение печати с двумя звездами, так что оно закончится с 3 звездами, а затем это продолжение с тремя звездами будет повторно захвачено,. ..