haskell - 用 CPS 编写的函数如何使许多事情变得明确？

Question

https://en.wikipedia.org/wiki/Continuation-passing_style说

A function written in continuation-passing style takes an extra argument: an explicit "continuation", i.e. a function of one argument. When the CPS function has computed its result value, it "returns" it by calling the continuation function with this value as the argument. That means that when invoking a CPS function, the calling function is required to supply a procedure to be invoked with the subroutine's "return" value. Expressing code in this form makes a number of things explicit which are implicit in direct style. These include: procedure returns, which become apparent as calls to a continuation; intermediate values, which are all given names; order of argument evaluation, which is made explicit; and tail calls, which simply call a procedure with the same continuation, unmodified, that was passed to the caller.

我该如何理解用 CPS 编写的函数“使许多事情变得明确”，其中包括“过程返回”、“中间值”、“参数评估顺序”和“尾部调用”？

例如，在我看来，用 CPS 编写的函数使函数的返回值对于函数的调用者来说是隐式的，而不是显式的。

例如，在 Haskell 中，CPS 中没有的函数是

add :: Float -> Float -> Float
add a b = a + b

虽然它在 CPS 中写为:

add' :: Float -> Float -> (Float -> a) -> a
add' a b cont = cont (a + b)

Scheme 中的示例类似。

Answer 1

使用 Sylwester 的答案中的表达式，解析器将生成一个看起来像这样的 AST(节点从左到右、从上到下任意编号，并在括号中注明数字以供以后引用):

                   +
                  (1)
           /               \
          +                 *
         (2)               (3)
       /     \           /     \
      *       *        fun      5
     (4)     (5)       (6)     (7)
     / \     / \        |
    3 fun   4  fun      c
   (8) (9) (10) (11)    (12)
       |        |
       a        b
      (13)     (14)

(这里假设一个左关联 + 运算符；我们也可以想象对于右关联 + 来说同样有效的树，甚至是一个完全关联运算符产生具有单个 + 节点和三个子节点的树。)

要计算表达式，您只需从下往上计算每个节点即可。树本身需要某些顺序:13 必须位于 9 之前； 4 和 5 都必须在 2 之前计算，依此类推。但是，对于其他节点对，顺序无关。例如，6 可以在 9 之前或之后进行计算。

不过，我们可以通过计算树的拓扑排序来强加排序，树只是一个节点列表，使得每个子节点在排序中始终位于其父节点之前。该树有多种有效的拓扑排序，其中任何一种都会为最终表达式产生正确的值。一些示例订单是

1. 13、14、12、9、11、6、8、10、7、4、5、3、2、1

   这首先计算所有函数参数，然后函数调用， 然后是乘法，最后是加法(全部按从左到右的顺序)

2. 8、13、9、10、14、11、12、6、7、4、5、2、3、1

   这会从左到右计算加法项，因此我们在计算下一个乘法的操作数之前完成乘法。

3. 8、13、9、10、11、14、4、5、2、12、7、6、3、1

   这与第二个示例类似，但也在处理之前计算第一个加法 第二次加法的操作数。

---

要点:CPS 风格简单地明确了使用哪种排序。