阴阳谜题

from my Yin to my Yang to my Yang Tze

本文的解法重度参考王垠的博客.

阴阳谜题(yinyang puzzle)是指的这样一个问题，即使用递归的方式输出@\*@**@\***@\***\*@\*\*\***...这样的字符串序列。它常常被用来展示 scheme 中 call/cc 的优越性。不妨先看看 wiki 上给出的解法

scheme
(let* ((yin
        ((λ (cc) (display #\@) cc) (call/cc (λ (c) c))))
       (yang
        ((λ (cc) (display #\*) cc) (call/cc (λ (c) c)))))
  (yin yang))

虽然我们知道图灵完备的编程语言都可以互相翻译，但是 JS 中并没有call/cc这样强大的语法，因此凭空翻译上面这段程序的难度非常大。不过不用着急，我们可以一步步地来.

先把let*化简为普通的表达式。此外，显然(call/cc (λ (c) c))和(call/cc (λ (c) (c c)))是等价的，所以有

scheme
(define (f x) (x x))
(((λ (cc) (display #\@) cc) (call/cc f)) ((λ (cc) (display #\*) cc) (call/cc f)))

不妨记表达式的第二部分为 B

scheme
(define (B) ((λ (cc) (display #\*) cc) (call/cc f)))
(
  (
    (λ (cc) (display #\@) cc) (call/cc f)
  ) (B)
)

这样我们就可以把表达式中的第一个call/cc消去了。

scheme
(
  f (λ (k) (
    (
      (λ (cc) (display #\@) cc) k
    ) (B)
  ))
)

这里用到的方法就是消去call/cc最常用的方法，把含有call/cc的表达式改写成一个单参数的函数，把call/cc的值替换成参数，再把这个函数传给 call/cc的参数f。

对λ (k)内部表达式化简可得

scheme
(
  f (λ (k)
    (display #\@)
    (k (B))
  )
)

不妨把这个函数称为 A0，那么表达式就可以写成(A0 A0)，此时再把 B 代入 A0

scheme
(define (A0 k)
  (display #\@)
  (k ((λ (cc) (display #\*) cc) (call/cc f)))
)
(A0 A0)

让我们对 A0 里的第二个表达式再来一次刚刚的步骤

scheme
(define (A1 k)
  (display #\@)
  (f (λ (h) ((k ((λ (cc) (display #\*) cc) h)))))
)
(define (A2 k)
  (display #\@)
  (f (λ (h)
      (display #\*)
      (k h)
    )
  )
)

到 A2 我们就已经很接近成功了，它已经可以直接翻译成 JS，只不过稍稍需要一点动作

js
function A3(k) {
  console.log('@')
  function A30(h) {
    console.log('*')
    k(h)
  }
  A30(A30)
}

此时如果继续使用 scheme，则最简单的方法是消去 f

scheme
(define (A31 k)
  (display #\@)
  (display #\*)
  (k (λ (h) (
    (display #\*)
    (k h)
  )))
)

显然上面的函数可以平凡地翻译成 JS

js
function A31(k) {
  console.log('@')
  console.log('*')
  k(h => {
    console.log('*')
    k(H)
  })
}

到此已经大功告成了，不过这样会无限运行运行下去(在大部分 JS 运行时里会因为没有 TCO 而爆栈)，怎么样让它变得可控呢? 答案是生成器，对 A3 进行改写的话则有

js
function* AG(k) {
  yield '@'
  function* AGI(h) {
    yield '*'
    yield* k(h)
  }
  yield* AGI(AGI)
}

这样就可以按需取出输出结果了。可以在我的 Github 上看到完整的代码。