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 之前或之后评估， 例如。

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

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

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

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

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

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

这就像第二个例子，但也在处理之前计算第一个加法
第二次加法的操作数。

重点:CPS 风格只是明确说明使用哪种排序方式。