[Scheme]Understanding the Yin-Yang Puzzle

时间:2021-09-18 05:20:37

这题目确实比较杀脑细胞...

原题:

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

它会输出“@*@**@***@****@*****@******@*******@********...”

怎么理解呢?

我的方案是移除call/cc,以纯函数的方案重新表示该问题,然后应用代换模型

首先,continuation是什么?

它是一个过程,以一个值为参数,这个值对应call/cc的返回;将实参应用在continuation这个过程上,应该相当于运行程序本身

原则上,continuation中应该包含整个调用栈上各帧及运算的一系列closure,以free variable的方式链接起来,不过由于本题及其简单,大大简化了continuation的近似。

首先,yang-continuation怎么表达?

 (define (make-yang-continuation yin)
(lambda (yang)
(putc #\*)
(yin yang))
)

意思是,提供yin这个free variable,就返回一个continuation;如果你以参数yang(相当于call/cc的返回)调用continuation,就相当于运行程序(即原题中let*的第二部分)

再来看yin-continuation的表示:

 (define yin-continuation
(lambda (yin)
(putc #\@)
(let ((yang-continuation (make-yang-continuation yin)))
(yang-continuation yang-continuation)))
)

这个continuation不需要free variable,因此直接define;它接收一个值yin(即call/cc的返回),再以它为free variable定义yang-continuation,最后,以yang-continuation自身作为参数来继续执行(对应原题中call/cc的参数(lambda (c) c))。

最后,运行整个程序:

 (yin-continuation yin-continuation)

即,yin-continuation以continuation自身作为yin的初始值,运行整个程序。

完整代码:

 #lang racket

 (define n 0)
(define (putc c)
(cond
((< n 100) (set! n (+ n 1)) (display c))
((= n 100) (set! n (+ n 1)) (newline))
(else 'ok))
) (define (make-yang-continuation yin)
(lambda (yang)
(putc #\*)
(yin yang))
) (define yin-continuation
(lambda (yin)
(putc #\@)
(let ((yang-continuation (make-yang-continuation yin)))
(yang-continuation yang-continuation)))
) (yin-continuation yin-continuation)

这里putc打印无限输出串的前100个字符

因为只涉及纯函数,可以开始代换模型了。

下面我将yin-continuation记为y,make-yang-continuation记为m,(y x)可以代换,((m x1) x2)可以代换,前者代换的时候输出@,后者输出*:

(y y) =>

@ ((m y) (m y)) =>
@* (y (m y)) => @* @ ((m (m y)) (m (m y))) =>
@* @* ((m y) (m (m y))) =>
@* @** (y (m (m y))) => @* @** @ ((m (m (m y))) (m (m (m y)))) =>
@* @** @* ((m (m y)) (m (m (m y)))) =>
@* @** @** ((m y) (m (m (m y)))) =>
@* @** @*** (y (m (m (m y)))) => ...

总算找到一个能把自己糊弄过去的说法...

ps. 有人看不懂scheme,给个lua的翻译版,应该没有理解障碍了(是移除call/cc后的版本,包含了我部分解题思路)。你觉得这谜题容易懂吗:

 local n =
function putc(c)
if n < then
n = n +
io.write(c)
elseif n == then
n = n +
os.exit()
end
end function make_yang_continuation(yin)
return function(yang)
putc('*')
yin(yang)
end
end
function yin_continuation(yin)
putc('@')
local yang_continuation = make_yang_continuation(yin)
yang_continuation(yang_continuation)
end yin_continuation(yin_continuation)