高阶编程语言与continuation passing style的关系问题

明确结论 #

你给出的BNF定义的高阶Lisp风格语言编写的程序，并非隐式属于续体传递风格（CPS）。

c ::= constants
v ::= variables
e ::= c | v | (if e e e) | (e e_1 e_2 ... e_n) | (fn [v_1 v_2 ... v_n] e)

上述语法是典型的直接风格（Direct Style, DS）高阶函数式语言的语法定义，没有强制满足CPS的约束要求。

CPS的核心约束 #

CPS是一种特殊的程序书写风格，对代码结构有强约束：

• 所有函数必须额外接收一个continuation（续体）参数，该参数代表函数执行完成后要执行的后续逻辑
• 函数不允许直接返回值，所有执行结果只能通过调用传入的续体、将结果作为参数传递给续体的方式向外传递
• 不存在隐式嵌套求值：所有子表达式的计算结果都要先传递给续体，再在续体内部执行外层逻辑，所有中间计算的依赖关系完全显式，不依赖隐式调用栈保存上下文

二者核心区别 #

• 参数规则不同：CPS要求所有函数必须携带续体参数，你给出的语法没有这个强制要求，函数参数列表可以自由定义，不需要内置续体参数。
• 值传递逻辑不同：CPS没有“返回值”的概念，所有结果通过续体调用传递；你给出的语言支持直接返回值，结果会隐式交给外层求值上下文处理，依赖隐式调用栈存放下游执行逻辑。
• 表达式结构不同：CPS不允许隐式嵌套求值，比如直接风格下合法的(+ (* 2 3) 1)，在CPS中必须拆分为先计算(* 2 3)，将结果传递给续体后再执行加1逻辑；你给出的语法天然支持嵌套表达式的隐式求值，不需要显式拆分逻辑。

举个简单的对比示例：

• 给出语法下的直接风格加法程序：(fn [a b] (+ a b)) 1 2，执行后直接返回结果3
• 等价的CPS风格程序：(fn [a b cont] (cont (+ a b))) 1 2 (fn [res] res)，函数执行后将结果传给续体cont输出

内容的提问来源于stack exchange，提问作者bzm3r