阴阳谜题
发表于更新于阅读时长 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上看到完整的代码.