Continuation Passing Style and Tail Recursion
之前在"Essentials of Programming Languages"中学习过CPS(Continuation Passing Style), 而笔记在blog改版后被丢弃, 故在这篇文章中重新详细的探讨下CPS以及尾递归, 就当是温故而知新. Continuation 在理解什么是"Continuation Passing Style"之前, 我们首先需要定义Continuation(惭愧的是我都不知道中文叫啥, 查了下好像是"续延"). Continuation是计算机程序控制状态的抽象表示, 换言之, 其就是一种表示程序执行中间某一计算步骤的控制上下文的数据结构, 即表示某一计算的未来. 一个形象的例子是阶乘函数: 1 2 3 4 let rec fact n = if n = 0 then 1 else n * (fact (n - 1)) 当我们计算(fact 4)时, 其执行过程为(用lisp的形式是因为更加形象): 1 2 3 4 5 6 7 8 9 10 (fact 4) => (* 4 (fact 3)) => (* 4 (* 3 (fact 2))) => (* 4 (* 3 (* 2 (fact 1)))) => (* 4 (* 3 (* 2 (* 1 (fact 0))))) => (* 4 (* 3 (* 2 (* 1 1)))) => (* 4 (* 3 (* 2 1))) => (* 4 (* 3 2)) => (* 4 6) => 24 这过程中, (* 4 #)就是一个continuation, 是(fact 3)的控制上下文, 等待着(fact 3)的计算结果传入我们的"#", (* 4 (* 3 #))也是一个continuation. 容易看到的是在这样一个计算过程中, continuation在不断增长, 因为调用栈在不断增长, 程序不得不保存*的左操作数, 计算右操作数. 接下来, 我们来看fact的尾递归版本, 所谓的尾递归(tail recursion)指的是递归函数的递归调用部分只有函数调用, 即: ...