Continuation Monad和rest of the computation

Haskell的Cont Monad

最先接触的关于Continuation的东西是Scheme的call/cc, 因为过于怪异, 大脑始终没有翻转过来. 所以就浅尝辄止了. 这个障碍可能比接受LISP的语法还要大. 而要研究Monad, Haskell, Continuation是绕不过去的. Continuation是理解Monad的关键一环.

下面是Haskell的Cont类型定义.

 
newtype Cont r a = Cont {runCont::(a -> r) -> r}
 
instance Monad (Cont r) where
  return a = \k -> k a
  m >>= f = \k -> m (\a -> f a k)
 

首先需要记住的一点: 在函数式中一切不外乎function application. 这里讲的所有东西最终都归结到function application, 毫无神奇的地方. 在Haskell中function application处于极简的状态

 
f a
 

这已经把能去掉的全部去掉了. 下面是其他几种语言中的function application

 
// c系列
f(arg);
 
// LISP
(f a)
 
// OOP
object.method(arg);
 
 

上面的定义中 return函数返回一个函数, 而这个函数所做的唯一一件事情就是function application: k a. 这不是偶然的, 这些定义中没有一个字符是多余的, 这里的k实际就是Continuation, 而a是当前的computation的结果.

Continuation在命令式和函数式语言中的特点

命令式语言的Continuation是符合人的直觉的, 无论在时间上和空间上. 无论是在高级语言(Java,C/C++)中还是底层的执行语言(汇编语言, 机器指令)中. 在高级语言层面上, 代码是一条一条语句构成的, 一句接着一句, 一般情况下语句用semicolon分隔, 没有特殊情况, 代码会按照视觉上的顺序从上往下执行. 如果需要跳转, 分支, 回溯, 循环, 这些语言提供了特别的语法, 或者内置的语法, 实际是对jmp, call, ret之类的机器指令的一种封装.

而函数式语言的执行却没有明显的顺序, 至少是视觉上的顺序. 甚至有时候和视觉效果或者直觉是相反的.

一般的函数式表达式, 其实是从内往外执行的

 
(println (+ 3 4 (* 5 6)))
 

这就是为什么Clojure里面有个threading macro, 将顺序翻过来了, 这只是一种方便程序员的语法糖. Clojure的let form也是同样的, 如果将let form编译到lambda calculus, 就会是一个嵌套的结构, 而且顺序是相反的.

而从某个角度看, 所有的函数式代码本质上是一个巨大的lambda表达式, 在这样的系统中, 语句的概念不存在了. 只有表达式, 一层一层的嵌套在一起, 事实上函数式代码中每做一次计算, 嵌套就会增加一层, 执行的过程就是从最边缘的叶子节点逐步收缩到顶层的过程, 这对某个局部的计算还是整个项目, 都是适用的.

什么是continuation passing style

先来看看wiki的定义

 
an explicit "continuation" i.e. a function of one argument.
 

而执行Continuation就是将这个function应用到参数上. 这里还提到了一个词: explicit. 既然有explict那么也就会有implicit. 所谓implicit就是正常情形下的lambda表达式的执行方式, 下面的Clojure代码可以说明这一点

 
;; implicit continuation
(* (inc 1 ) 1)
 
;; explicit continuation  
( (fn [a]  ( (fn [b] (* a b)) (inc a) ) )  1 )
 

通过引入一个辅助函数flip, explicit Continuation就更加明显.

 
(defn flip [v f]
  (f v)
)
 
(flip 1 (fn [a]
  (flip (inc a) (fn [b]
    (* a b)))
))
 

可以将implicit Continuation想象为一个布袋, 现在将手伸入布袋, 握住底部, 然后向外整个翻转过来, 这就是explicit Continuation.

什么是notions of computation

所谓Computation, 就是计算, 本来是一个非常直白的概念, 但是FP却把它复杂化了. 当我们研究Monad的时候, 很多材料都会以这个做为一个基本概念, 衍生出来的概念包括: chain of computation, sequence of computation, computation composition, model of computation.

那么在函数式的语境下, computation是什么? 我的理解是: computation is nothing more than function application.

什么是 the rest of the computation

归根到底, 所谓the rest of the computation, 所谓Continuation, 说白就是计算如何进行下去, 下一步往哪里走的问题, 当前的计算完成了, 产生了一个结果, 下一步去哪里. 不管接下来要做什么, 无论是将这个结果和另一个数相加, 相减, 还是打印输出, 还是根本不理会这个结果, 姑且就用?来代表这个the rest of the computation, 不论具体做什么, 他的执行方式必然是一个function application, 无非像下面这样.

 
( (fn [a] (? a)) 3)
 

事实上在函数式中一切都是function application, 即便是if语句, for循环, 这些看起来很命令式的控制结构, 本质上也是function application. 我们所熟知的let语句

 
(let [ a 1
       b (+ a 3)
       c (* b a)
     ]
  (* a b c)     
)
 

实际上和Haskell的do notation一样是一种伪装, 伪装成命令式语言的样子, 伪装成带有semicolon的语法, 本质上就是语法糖. 在命令式语言中类似的结构最终被编译成汇编语言, 在函数式中这些结构被编译成lambda calculus. 如果说命令式语言中的一切高级语法结构都是汇编语言的语法糖, 那么所有函数式的高级语法结构都是lambda calculus的语法糖. 这也同样适用于那些看起来很难懂的高级语法例如Monad和Continuation.

在命令式语言中, 我们只有将高级语言生成的机器代码反汇编出来, 并分析其中的指令, 才能彻底的搞清楚类似于if, for, while这些高级结构到底做了什么. 与此类似, 在函数式语言中, 我们反汇编的结果是lambda calculus, 当搞清楚了他具体做的事情, 一切的高级语法结构的含义也就明了了.

语法糖的别名又叫做设计模式, 所不同的唯一区别在于, 语法糖是内置到语言中的, 也就是first class, 而设计模式则是在语言的基础上实现的. 所以命令式语言中的if, for, while, switch其实就是内置的设计模式, 当我们在汇编语言中反复的重复使用某种结构的时候, 我们将不变的部分抽出来用一个符号代替, 变化的部分作为参数, 那么我们就可以用简短的符号来反复应用这一模式. 到时候只需要将符号展开即可.

从上面的意义讲, 下面的公式是成立的

 
Monad == Syntax Sugar == design pattern
 

Maybe Monad中的Continuation

Maybe Monad的源码

 
instance Monad Maybe where
    return x = Just x
    val >>= f = case val of
        Nothing -> Nothing
        Just x -> f x
 

注意第五行和第四行, 第五行中的f, 就是rest of the computation. Monad所构成的computation chain并不是线性的形状, 而是nested, 每一步的computation中, rest computation作为一个nest的lambda 块, 即这里的f, 可以被选择或者放弃, 如果是Nothing的话, rest computation就不会执行.

如下图:

monad chain

bind的作用就是接受作为rest computation 的函数f 和当前computation step产生的结果, 然后根据结果决定如何进行Continuation: 返回Nothing, 结束chain, 或者继续进行, 而继续进行就是简单的function application.

同时搜到了另一幅图, 在这篇文章中Monads for the Curious Programmer: Part 2

monad chain from bartoszmilewski.com

参考

https://github.com/khinsen/monads-in-clojure/blob/master/PART1.md

这个例子更好的解释了Monad的本质.