Alivs

阴阳谜题

发表于更新于阅读时长 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 - 2023Austaras Devas