Пазл Инь Янь написан на схеме.Я предполагаю, что вы знаете основной синтаксис Схемы.
Но я предполагаю, что вы не знаете let* или call-with-current-continuation, я объясню эти два ключевых слова.
Объясните let*
Если вы уже знаете это, вы можете перейти к Explain call-with-current-continuation
let*, который выглядит как let, действует как let, но оценивает его определенные переменные ((yin ...) и (yang ...)) по очереди и с нетерпением.Это означает, что он сначала оценит yin, а затем yang.
. Подробнее читайте здесь: Использование схемы Let in
Объяснение call-with-current-continuation
Если вы уже это знаете, вы можете перейти к Yin-Yang puzzle.
Это немного сложно объяснить call-with-current-continuation.Поэтому я буду использовать метафору, чтобы объяснить это.
Представьте себе волшебника, который знал заклинание, которое было call-with-current-continuation.Как только он разыграет заклинание, он создаст новую вселенную и отправит себя в нее.Но он мог ничего не делать в новой вселенной, кроме как ждать, пока кто-нибудь позовет его по имени.Как только был назван , волшебник возвращался в исходную вселенную, имея бедного парня - «кого-то» - в руках, и продолжал свою жизнь волшебника.Если не было вызвано, когда новая вселенная закончилась, мастер также вернулся в исходную вселенную.
Хорошо, давайте будем более техническими.
call-with-current-continuation - это функция, которая принимает функцию какпараметр.Как только вы вызовете call-with-current-continuation с функцией F, она упакует текущую рабочую среду, которая называется current-continuation, в параметр C, и отправит ее в функцию F и выполнит F.Таким образом, вся программа становится (F C).Или быть более JavaScript: F(C);.C действует как функция.Если C не вызывается в F, то это обычная программа, когда F возвращает, call-with-current-continuation имеет значение в качестве возвращаемого значения F.Но если C вызывается с параметром V, это снова изменит всю программу.Программа возвращается в состояние при вызове call-with-current-continuation.Но теперь call-with-current-continuation дает значение, которое V.И программа продолжается.
Давайте рассмотрим пример.
(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
Первый display вывод 3, причины.
Но второй displayвывод 2.Почему?
Давайте окунемся в нее.
При оценке (display (call-with-current-continuation f)) сначала будет оцениваться (call-with-current-continuation f).Мы знаем, что он изменит всю программу на
(f C)
Учитывая определение для f, он имеет (return 2).Мы должны оценить (C 2).Вот когда continuation вызывается.Таким образом, вся программа вернется обратно к
(display (call-with-current-continuation f))
Но теперь call-with-current-continuation имеет значение 2.Таким образом, программа становится:
(display 2)
Головоломка Инь-Ян
Давайте посмотрим на головоломку.
(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))
Давайте сделаем ее более читабельной.*
Давайте запустим программу в нашем мозгу.
Раунд 0
let* заставит нас сначала оценить yin.yin - это
(f (call-with-current-continuation id))
Итак, сначала мы оценим (call-with-current-continuation id).Он упаковывает текущую среду, которую мы называем C_0, чтобы отличить ее от другого продолжения на временной шкале, и входит в совершенно новую вселенную: id.Но id просто возвращает C_0.
Мы должны помнить, что такое C_0.C_0 - это программа, подобная этой:
(let* ((yin
(f ###))
(yang
(g (call-with-current-continuation id))))
(yin yang))
### - это заполнитель, который в будущем будет заполнен значением, которое C_0 возвращает.
Но id просто возвращает C_0.Это не звонит C_0.Если он позвонит, мы войдем во вселенную C_0.Но это не так, поэтому мы продолжаем оценивать yin.
(f C_0) ;; yields C_0
f - это функция, подобная id, но у нее есть побочный эффект - вывод @.
Итак, программа выведет @ и пусть yin будет C_0.Теперь программа становится
(let* ((yin C_0)
(yang
(g (call-with-current-continuation id))))
(yin yang))
После оценки yin мы начинаем оценивать yang.yang is
(g (call-with-current-continuation id))
call-with-current-continuation здесь создайте еще одно продолжение с именем C_1.C_1 является:
(let* ((yin C_0)
(yang
(g ###)))
(yin yang))
### является заполнителем.Обратите внимание, что в этом продолжении определяется значение yin (это то, что делает let*).Мы уверены, что значение yin здесь C_0.
Поскольку (id C_1) равно C_1, поэтому значение yang равно
(g C_1)
g имеет побочный эффект - вывод *.Так что программа делает.
yang значение теперь C_1.
К настоящему времени мы отобразили @*
Так что теперь оно становится:
(let* ((yin C_0)
(yang C_1))
(yin yang))
Поскольку и yin, и yang решены, мы должны оценить (yin yang).Это
(C_0 C_1)
Святой SH * T!
Но, наконец, C_0 называется.Итак, мы летим во вселенную C_0 и забываем все об этих дерьмах.Мы больше никогда не вернемся в эту вселенную.
Раунд 1
C_0 Возьми с C_1 назад.Теперь программа выглядит так: (Если вы забудете, что означает C_0, вернитесь, чтобы увидеть его):
(let* ((yin
(f C_1))
(yang
(g (call-with-current-continuation id))))
(yin yang))
Ах, мы обнаружим, что значение yin еще не определено.Поэтому мы оцениваем это.В процессе оценки yin мы выводим @ как побочный эффект f.И мы знаем, что yin сейчас C_1.
Мы начинаем оценивать yang, мы снова сталкиваемся с call-with-current-continuation.Мы практикуемся.Мы создаем продолжение C_2, которое обозначает:
(let* ((yin C_1)
(yang
(g ###)))
(yin yang))
И мы отображаем * как g при выполнении.И мы приходим сюда
(let* ((yin C_1)
(yang C_2))
(yin yang))
Итак, мы получили:
(C_1 C_2)
Вы знаете, куда мы идем.Мы собираемся во вселенную C_1.Мы вспоминаем это из памяти (или копируем и вставляем с веб-страницы).Теперь это:
(let* ((yin C_0)
(yang
(g C_2)))
(yin yang))
Мы знаем, что во вселенной C_1 определено значение yin.Итак, мы начинаем оценивать yang.Когда мы будем практиковаться, я прямо скажу вам, что он отображает * и становится:
(C_0 C_2)
Теперь мы напечатали @*@**, и мы собираемся во вселенную C_0 с C_2.
Раунд 2
По мере практики я скажу вам, что мы показываем '@', yin - это C_2, и мы создаем новое продолжение C_3, что означает:
(let* ((yin C_2)
(yang
(g ###)))
(yin yang))
И мы отображаем *, yang это C_3, и оно становится
(C_2 C_3)
И мы можем продолжать.Но я на этом остановлюсь, я показал вам, какие первые несколько выводов головоломки Инь-Ян являются следующими:
Почему число * увеличивается?
Теперь ваша голова полна деталей.Я сделаю резюме для вас.
Я буду использовать подобный синтаксису Haskell для упрощения.И cc является сокращением от call-with-current-continuation.
Когда #C_i# заключен в скобки #, это означает, что продолжение здесь создается.; означает вывод
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
Если вы внимательно наблюдаете, для вас будет очевидно, что
- Существует множество вселенных (фактически бесконечных), но
C_0 - единственная вселенная, основанная f.Другие запускаются g. C_0 C_n всегда делает новое продолжение C_max.Это потому, что C_0 - это первая вселенная, в которой g cc id было выполнено , а не . C_0 C_n также отображают @.C_n C_m Если n не равно 0, будет отображаться *. - Время от времени программа выводится на
C_0 C_n, и я докажу, что C_0 C_n отделяется все большим количеством других выражений, которыеприводит к @*@**@***...
Немного математики
Предположим, 
(n! = 0) - это наибольшее число во всех продолжениях, и затем вызывается C_0 C_n.
Предположение: когда вызывается C_0 C_n, C_n - это текущее максимальное пронумерованное продолжение.
Теперь 
создается C_0 C_n следующим образом:
yin = f C_n ; @
yang = g #C_{n+1}#
yin yang
Итак, мы заключаем, что:
Теорема I. Если вызывается C_0 C_n, то будет получено продолжение , в котором yin равно C_n.
Тогда следующим шагом будет C_n C_{n+1}.
yin = C_{n-1}
yang = g C_{n+1} ; *
yin yang
Причина, по которой yin является C_{n-1}, заключается в том, что при создании C_n он подчиняется Теорема I .
И затем вызывается C_{n-1} C_{n+1}, и мы знаем, что когда создается C_{n-1}, он также подчиняется Теорема I .Итак, у нас C_{n-2} C_{n+1}.
C_{n+1} - это вариация.Итак, у нас есть вторая теорема:
Теорема II.Если C_n C_m который n < m и n > 0 называется, он станет C_{n-1} C_m.
И мы проверили вручную C_0 C_1 C_2 C_3. Они подчиняются предположению и всем теоремам. И мы знаем, как сначала создаются @ и *.
Итак, мы можем написать шаблоны ниже.
C_0 C_1 ; @ *
C_[1-0] C_2 ; @ * *
C_[2-0] C_3 ; @ * * *
...
Это не так строго, но я бы хотел написать:
1377 * что и требовалось доказать *