Rust 阴阳谜题，及纯基于代码的分析与化简

雾雨魔法店专栏 https://zhuanlan.zhihu.com/marisa

来源 https://zhuanlan.zhihu.com/p/52249705

0. 前（请务必跳过）

之前用 Haskell 通过 Cont Monad 模拟过 call/cc （实际上在阴阳谜题中用作 get-current-continuation，这里我们只讨论 get/cc），但似乎确实是搞个 DSL 再模拟。

但我是觉得这和动态类型其实关系不大，只是通常语言是栈机模型，而 call/cc 的“栈”是一棵树，还可能到处跳。唯一和类型有关的是 get/cc 类型是递归类型 a where a ~ (a -> _|_)，但我们可以用类似 data Out a = In (Out a) (Out a) 的实现，在需要的时候把Cont翻成Cont -> Cont，或者反过来即可。

1. Rust 代码实现

因为不想搞得那么学术派，我们不用 Haskell 那种数学语言，用很工程很靠谱的 Rust 实现以下这个阴阳谜题/YinYang Puzzle。

首先，我们直译一下：

yin = getcc(); print!("@"); yin = getcc(); print!("*"); yin(yang);

但这当然是搞不了的。

我们 getcc 拿来的 yin不可能在全局都能用（主程序还是栈机啊喂，超级 goto 过分了），我们限定它在一个闭包里面才能用（这里我们要手动 CPS 一下），具体多大范围按需即可。

此外，由于函数调用的重载还没 stable，用了怕一下有 stable 癖的人觉得这不 Rust，所以这里用成员函数实现。

所以我们的代码应该是这样，然后一跑发现已经是预期行为了：()

/// Continuation./// Cont ~ (Cont -> !)    We use `()` instead of `!` here since `!` not stablestruct Cont<'a>(&'a dyn Fn(&Cont)); impl Cont<'_> { fn call(&self, value: &Cont) { (self.0)(value); // Simple proxy. Note that it is dynamic dispatch. } } /// Equal to `{ let cc_ = getcc(); cc(cc_); }` /// Apparently, `cc_` and `cc` is the same continuation. fn with_cc(cc: impl Fn(&Cont)) { cc(&Cont(&cc)); // Call `cc` with `cc` itself (current continuation) } fn puzzle() { with_cc(|yin| { print!("@"); with_cc(|yang| { print!("*"); yin.call(yang); }); }); }

输出：

@*@**@***@****@*****@******@*******@********@**** .....stack overflow

PS：惊奇地发现这份代码在 Release 下跑可以避免栈溢出，一直输出下去，看来是 TCO 了，果然优化还是很强劲的。当然记得本地编译跑，在线会被杀掉而看不到输出。

PSS：因为这里闭包引用结构的嵌套无法消去（我觉得 Rust 应该做不了 Idris 的 Nat <=> Int 优化），所以内存应该还是会缓慢（ $O(\sqrt {\text{Len}})$ ）增长的。

2. 分析与化简

现在我们试着只从代码上分析，尽量避免数学推导，证明为何是这样的输出。

（才不是因为看不懂 pi-calculus / 不会分析平行宇宙呢）

首先，我们这里有两个闭包，|yin| { .. }没有捕获东西，|yang| { .. }捕获了上一层的yin的引用，我们要手动展开闭包语法糖。

然后考虑到&dyn Fn(&Cont) 是动态分发，但只可能是两个闭包之一，直接用 enum实现这个 Trait Object 引用，也是展开语法糖。

因为闭包代码都很少，这里我们直接把函数体代码 inline 进动态分发的call里去了。

()

enum Cont<'a> { // Desugar of `&dyn Fn(&Cont)` ClosureA, ClosureB { yin: &'a Cont<'a> }, } impl Cont<'_> { fn call(&self, value: &Cont) { match self { // Manually dynamic dispatch Cont::ClosureA => { let yin = value; print!("@"); with_cc(Cont::ClosureB { yin }); } Cont::ClosureB { yin } => { let yang = value; print!("*"); yin.call(yang); } } } } fn with_cc(cc: Cont) { cc.call(&cc); } fn puzzle() { with_cc(Cont::ClosureA); }

可能还看不出来调用顺序如何，但call经过或不经过with_cc，最终递归调用自己，至少可以知道它是个死循环，而且似乎还是尾递归的。

然后我们可以发现，这个 enum Cont实际上就是一个不带值的链表结构（ Cont::ClosureA <=> Null，Cont::ClosureB <=> Next），它只包含长度信息。

所以我们只用一个自然数即可和它一一对应。

（对，这就是皮亚诺自然数定义的 Nat，但因为不要学术，不展开）

0 <=> Cont::ClosureA1 <=> Cont::ClosureB { yin: &Cont::ClosureA }2 <=> Cont::ClosureB { yin: &Cont::ClosureB { yin: &Cont::ClosureA }  }...

我们直接定义 type Cont = usize来重写简化一下call函数。

多套一层就是加一，模式匹配就是判零/减一。

type Cont = usize; fn call(this: Cont, value: Cont) { if this == 0 { let yin = value; print!("@"); let cc = yin + 1; call(cc, cc); } else { let yin = this - 1; let yang = value; print!("*"); call(yin, yang); } } fn puzzle() { call(0, 0); }

哇，尾递归！就是循环！

然后我们把两个函数 inline 到一起：

（上把死循环改成 for了，不然卡死看不到输出）

fn puzzle() { let (mut this, mut value) = (0, 0); loop { // for _ in 0..1024 { // For test running online if this == 0 { print!("@"); this = value + 1; value = value + 1; } else { print!("*"); this = this - 1; // value = value; // Unchanged } } }

这下可以清楚看到这个拍扁的二重循环结构了：

this == 0 时，value自增 1，并设this = value，输出一个@；

否则一次this自减 1，输出一个*；

最后重写成更语义化的二重循环就好啦：

3. 最终化简代码

( 限制了第一个for范围以防止死循环)

子循环是this从value自减到 1,（0 不输出了 *，直接返回上一层了）。当然显然这个循环顺序其实没啥关系，为了和上面对应还是反过来了。

fn puzzle() { for value in 1.. { // The value after `print`, starting from 1 // for value in 1..64 { // For test running online print!("@"); for _this in (1..=value).rev() { print!("*"); } } }

大循环一次一个@，然后小循环输出 value个*，自增value，重复。

输出结果当然就是 @*@**@***@****@*****@******@*******@********@....啦。

================= End

转载地址：http://zhmax.baihongyu.com/

你可能感兴趣的文章