Как работает головоломка инь-ян?

Ответ 1

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

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

Ответ 2

Схема понимания

Я думаю, что по крайней мере половина проблемы с пониманием этой головоломки - это синтаксис схемы, о котором большинство не знакомо.

Прежде всего, я считаю, что call/cc x сложнее понять, чем эквивалентная альтернатива, x get/cc. Он по-прежнему вызывает х, передавая ему текущее продолжение, но как-то более поддается тому, чтобы быть представленным в моей мозговой схеме.

С учетом этого конструкция (call-with-current-continuation (lambda (c) c)) становится просто get-cc. Были ли до этого:

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

Следующий шаг - тело внутренней лямбды. (display #\@) cc, в более знакомом синтаксисе (для меня, во всяком случае) означает print @; return cc;. В то время как были на нем, давайте также переписать lambda (cc) body как function (arg) { body }, удалить связку круглых скобок и сменить вызовы функций на синтаксис C-типа, чтобы получить следующее:

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

Теперь он начинает иметь больше смысла. Теперь это небольшой шаг, чтобы переписать это полностью в синтаксис C-like (или JavaScript-like, если хотите), чтобы получить следующее:

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

Самая сложная часть теперь закончена, weve расшифровал ее с Scheme! Просто шучу; это было сложно, потому что у меня не было предыдущего опыта работы с Scheme. Итак, давайте выясним, как это работает.

Праймер на продолжениях

Наблюдайте за странно сформулированным ядром инь и ян: он определяет функцию, а затем сразу вызывает ее. Он выглядит так же, как (function(a,b) { return a+b; })(2, 3), который можно упростить до 5. Но упрощение вызовов внутри yin/yang было бы ошибкой, поскольку они не передавали ему обычное значение. Провели функцию продолжение.

Продолжение - это странный зверь с первого взгляда. Рассмотрим гораздо более простую программу:

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

Изначально x устанавливается на текущий объект продолжения (переносите со мной), а print x выполняется, печатая что-то вроде <ContinuationObject>. Пока все хорошо.

Но продолжение подобно функции; его можно вызвать с одним аргументом. Что он делает, это: принять аргумент, а затем перейти туда, где это продолжение было создано, восстановить все контексты и сделать так, чтобы get-cc возвращал этот аргумент.

В нашем примере аргумент 5, поэтому мы по существу прыгаем обратно в середину этого оператора var x = get-cc, только на этот раз get-cc возвращает 5. Таким образом, x становится 5, и следующий оператор переходит к печати 5. После этого мы пытаемся вызвать 5(5), который является ошибкой типа, и программа вылетает.

Обратите внимание, что вызов продолжения - это прыжок, а не вызов. Он никогда не возвращается обратно туда, где было вызвано продолжение. Это важно.

Как работает программа

Если вы следовали за этим, тогда не получите надежду: эта часть действительно самая сложная. Heres наша программа снова, отбрасывая объявления переменных, потому что это псевдокод в любом случае:

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

Первая строка 1 и 2 ударяется, теперь они просты: получите продолжение, вызовите функцию (arg), напечатайте @, return, сохраните это продолжение в yin. То же самое с yang. Теперь Weve напечатано @*.

Далее, мы будем называть продолжение в yin, передавая его yang. Это заставляет нас перейти к строке 1, прямо внутри этого get-cc, и заставить его возвращать yang. Значение yang теперь передается в функцию, которая печатает @, а затем возвращает значение yang. Теперь yin назначается продолжение, которое yang имеет. Затем переходим к строке 2: получаем c/c, печатаем *, сохраняем c/c в yang. Теперь имеем @*@*. И, наконец, мы переходим к строке 3.

Помните, что yin теперь имеет продолжение, когда первая строка была выполнена. Итак, мы переходим к строке 2, печатаем второй * и обновляем yang. Теперь имеем @*@**. Наконец, снова вызовите yin продолжение, которое перейдет к строке 1, распечатав @. И так далее. Честно говоря, в этот момент мой мозг выбрасывает исключение OutOfMemory, и я теряю все. Но по крайней мере мы добрались до @*@**!

Это трудно понять, и еще труднее объяснить, очевидно. Идеальный способ сделать это - пройти через него в отладчике, который может представлять собой продолжение, но, увы, я не знаю ни о каком. Надеюсь, вам это понравилось; У меня, конечно, есть.

Ответ 3

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

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

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

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

Это может быть неправильно, но я поеду.

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

Сначала мы определяем yin как продолжение 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)

Но если мы назовем продолжение 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)

Мы начинаем здесь.

Сначала вы получаете yin=A и yang=B, когда инициализируются yin и yang.

The output is @*

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

Теперь (yin yang) оценивается как (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')

Теперь (yin yang) оценивается как (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')

Так как стек был восстановлен до точки, где yin=A, (yin yang) оценивается как (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")

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

Мы знаем, что делает 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'")

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

.......

Я думаю, что у нас есть шаблон сейчас.

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

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

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

Ответ 4

Пазл YinYang написан на Схеме. Предполагаю, что вы знаете базовый синтаксис схемы.

Но я предполагаю, что вы не знаете let* или call-with-current-continuation, я объясню эти два ключевых слова.

Объяснить let*

Если вы уже знаете это, вы можете перейти к Explain call-with-current-continuation

let*, который выглядит как let, действует как let, но будет оценивать его определенные переменные ((yin ...) и (yang ...)) один за другим и с нетерпением. Это означает, что он сначала оценит yin, а не yang.

Здесь вы можете прочитать больше: Использование Let in Scheme

Объяснить 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))

Позвольте сделать его более читаемым.

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

Позвольте запустить программу в нашем мозгу.

Раунд 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 -

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

Святая Ш * Т!

Но, наконец, вызывается C_0. Таким образом, мы летаем во вселенную C_0 и забываем обо всех этих sh * ts. Мы больше никогда не вернемся к этой вселенной.

Раунд 1

C_0 возьмите с C_1 назад. Теперь программа становится (если вы забудете, что означает C_0, вернитесь, чтобы увидеть ее):

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

Ah, мы находим, что значение 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 is C_2, и мы создаем новое продолжение C_3, которое означает:

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

И мы показываем *, yang is C_3, и он становится

(C_2 C_3)

И мы можем продолжить. Но я остановлюсь здесь, я показал вам, что первая загадка в Yin-Yang.

Почему число * увеличивается?

Теперь ваша голова полна деталей. Я сделаю сводку для вас.

Я буду использовать синтаксис 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 ; @ * * *
...

Это не так строго, но я бы хотел написать:

Q.E.D.

Ответ 5

Как сказал еще один ответ, мы сначала упростим (call-with-current-continuation (lambda (c) c)) с помощью get-cc.

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

Теперь две лямбда - это просто идентичная функция, связанная с побочными эффектами. Позвольте называть те функции f (для display #\@) и g (для display #\*).

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

Далее нам нужно разработать порядок оценки. Чтобы быть ясным, я представлю "ступенчатое выражение", которое делает каждый шаг оценки явным. Сначала позвольте спросить: что требует вышеуказанная функция?

Для этого требуются определения f и g. В выражении шага пишем

s0 f g =>

Первым шагом является вычисление yin, но для этого требуется оценка (f get-cc), а в дальнейшем требуется get-cc.

Грубо говоря, get-cc дает вам значение, которое представляет "текущее продолжение". Скажем, это s1, так как это следующий шаг. Поэтому мы пишем

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

Обратите внимание, что параметры являются scopeless, что означает, что f и g в s0 и s1 не нужны одинаково, и они должны использоваться только на текущем шаге. Это делает контекстную информацию явной. Теперь, каково значение для cc? Поскольку это "текущее продолжение", оно является тем же самым s1 с f и g, привязанным к одному и тому же значению.

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

Как только мы получим cc, мы можем оценить f get-cc. Кроме того, поскольку f не используется в следующем коде, нам не нужно передавать это значение.

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

Следующий пример аналогичен для 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 => 

Наконец, последний шаг - применить 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

Это закончило конструкцию выражения шага. Перевести его обратно на схему очень просто:

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

Подробный порядок оценки (здесь лямбда внутри тела s2 была просто выражена как частичная оценка s3 yin, а не (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)))
=> ...

(Помните, что при оценке s2 или s4 параметр будет оцениваться первым

Ответ 6

Это старая головоломка от мастера обфускации Дэвида Мадора, который создал Unlambda. В головоломке обсуждалось comp.lang.scheme несколько раз.

Хорошее решение от Тейлора Кэмпбелла: https://groups.google.com/d/msg/comp.lang.scheme/pUedvrKYY5w/uIjTc_T1LOEJ

Оригинальный пост от Дэвида Мадора (1999): https://groups.google.com/d/msg/comp.lang.scheme/Fysq_Wplxsw/awxEZ_uxW20J