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

https://stackoverflow.com/questions/2694679

01-10-2019
|

Вопрос

Я пытаюсь понять семантику call / cc в Scheme, и на странице Википедии, посвященной продолжениям, в качестве примера приведена головоломка инь-ян:

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

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

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

Решение

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

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

Другие советы

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

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

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

Имея это в виду, конструкция (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-подобный синтаксис (или JavaScript-подобный, если вы предпочитаете), чтобы получить это:

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

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

Учебное пособие по продолжениям

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

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

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), что является ошибкой типа, и программа выходит из строя.

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

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

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

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

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

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

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

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

Вызов первого, возможный ответ в конце.

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

; 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 Продолжение, написание А. * каждый раз.

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

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

Yinyang Puzzle написан на схеме. Я предполагаю, что вы знаете основной синтаксис схемы.

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

Объяснять `let*`

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

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

Вы можете прочитать больше здесь:Использование пусть в схеме

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

Ах, мы находим, что 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)

И мы можем продолжить. Но я остановлюсь здесь, я показал вам, что на первом выходе из 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 разделены все более и более иным выражением, которое приводит к @*@**@***...

Немного математики

Предполагать $C_n$ (n! = 0) самый большой пронумерован во всех продолжениях, а затем C_0 C_n называется.

Успение: когда C_0 C_n называется, C_n Является ли текущее максимальное пронумерованное продолжение.

Сейчас $C_{n+1}$ создается C_0 C_n так:

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

Итак, мы заключаем, что:

Теорема I. Если C_0 C_n называется, он будет производить продолжение $C_{n+1}$ , в котором 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 ; @ * * *
...

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

Qed.

Как сказал другой ответ, мы впервые упростим (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 =>

Обратите внимание, что параметры являются незаменимыми, что означает 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, Параметр будет оценен первым

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

Хорошее решение от Taylor Campbell:https://groups.google.com/d/msg/comp.lang.scheme/pedvrky5w/uijtc_t1loej.

Оригинальный пост от David Madore (1999):https://groups.google.com/d/msg/comp.lang.scheme/fysq_wplxsw/awxez_uxw20j.

Лицензировано под: CC-BY-SA с атрибуция

Не связан с StackOverflow