阴阳谜题

发表于更新于阅读时长 2 分钟

from my Yin to my Yang to my Yang Tze

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

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

(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)))是等价的,所以有

(define (f x) (x x))

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

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

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

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

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

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

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

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

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

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

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

(A0 A0)

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

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

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

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

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

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

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

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

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

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

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

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

© 2016 - 2024Austaras Devas