什么是“延续”在函数式编程中意味着什么？（特别是SML） [英] What do "continuations" mean in functional programming?(Specfically SML)

问题描述

我正在学习SML中教授的函数式编程课程。

我们的教授将延续定义为：

跟踪我们仍然需要做的事情
; 让我们控制调用堆栈

他的很多示例都围绕着树。在本章之前，我们做了尾递归。我明白，尾递归允许通过有一个额外的参数来构建答案来让堆栈保持递归调用的函数。反转列表将建立在一个新的累加器中，我们可以相应地追加它。另外，他说有关函数的东西被调用（但没有被评估），除非我们到达结束的地方，我们将向后取代。他表示，尾部递归的改进版本将使用CPS（延续编程风格）。

有人可以简单地解释继续是什么以及为什么他们比其他编程风格更受青睐？

我发现这个帮助我的stackoverflow链接，但仍然没有澄清我的想法： / i-just-dont-get-continuations>我只是没有继续！

简单地将接下来发生的事情视为无条件使用的第一类对象，忽略其他内容或多次使用。 为了解决继续传递风格是，这里有一些表达式正常写入：

  let hx = f（gx）
  

g 适用于 x 和 f 应用于结果。
请注意， g 没有任何控制权。它的结果将被传递给f。无论如何。

这是写在

  let hx next =（gx（fun结果 - > f result next））
  

g 不仅有x作为参数，而且是一个接受g的输出并返回最终值的延续。这个函数以相同的方式调用 f ，并给出 next 作为延续。

发生了什么？是什么让这变得比 f（g x）更有用？区别在于，现在 g 处于控制之下。它可以决定是否使用接下来发生的事情。这就是continuations的本质。

延续出现的地方就是一个命令式编程语言，其中有控制结构。因为这些控制结构需要接下来发生的事情并决定如何处理它，例如我们可以有

  ... 
 while（condition1）{
 statement1; 
 if（condition2）break; 
 statement2; 
 if（condition3）continue; 
 statement3; 
} 
 return statement3; 
 ... 
  

while，the block，the statement，the break and the continue都可以通过延续描述在功能模型中。每个构造都可以被认为是一个接受包含

• 函数>封闭范围


• 可选函数接受当前环境，并从最内层循环返回到
  
  
  
  • 中断
  
  
  • 继续从最内层循环
  返回
  
  • 。
    
  
  
  
  • 与它相关的所有块（if-blocks，while-block等）
  
  
  • 延续到下一个语句
  
  
  
  
  

  并返回新环境。

  
  
  

  在while循环中，条件根据当前的环境进行评估。如果评估为true，则评估该块并返回新的环境。返回使用新环境再次评估while循环的结果。如果评估为false，则返回评估下一个语句的结果。
  
  

  使用break语句，我们查找环境中的break函数。如果没有找到函数，那么我们不在一个循环内，我们给出一个错误。否则，我们将当前环境赋予该函数并返回经过评估的延续，这将是while循环之后的语句。

  
  
  

  使用continue语句也会发生同样的情况，

  
  
  

  对于return语句，延续将是对当前函数的调用之后的语句，但它会删除当前的封闭作用域来自环境。
  

  I have read a lot about continuations and a very common definition I saw is, it returns the control state.

  I am taking a functional programming course taught in SML.

  Our professor defined continuations to be:

  "What keeps track of what we still have to do" ; "Gives us control of the call stack"

  A lot of his examples revolve around trees. Before this chapter, we did tail recursion. I understand that tail recursion lets go of the stack to hold the recursively called functions by having an additional argument to "build" up the answer. Reversing a list would be built in a new accumulator where we append to it accordingly. Also, he said something about functions are called(but not evaluated) except till we reach the end where we replace backwards. He said an improved version of tail recursion would be using CPS(Continuation Programming Style).

  Could someone give a simplified explanation of what continuations are and why they are favoured over other programming styles?

  I found this stackoverflow link that helped me, but still did not clarify the idea for me:

  I just don't get continuations!

  解决方案

  Continuations simply treat "what happens next" as first class objects that can be used once unconditionally, ignored in favour of something else, or used multiple times.

  To address what Continuation Passing Style is, here is some expression written normally:

  let h x = f (g x)
  

  g is applied to x and f is applied to the result. Notice that g does not have any control. Its result will be passed to f no matter what.

  in CPS this is written

  let h x next = (g x (fun result -> f result next))
  

  g not only has x as an argument, but a continuation that takes the output of g and returns the final value. This function calls f in the same manner, and gives next as the continuation.

  What happened? What changed that made this so much more useful than f (g x)? The difference is that now g is in control. It can decide whether to use what happens next or not. That is the essence of continuations.

  An example of where continuations arise are imperative programming languages where you have control structures. Whiles, blocks, ordinary statements, breaks and continues are all generalized through continuations, because these control structures take what happens next and decide what to do with it, for example we can have

  ...
  while(condition1) {
      statement1;
      if(condition2) break;
      statement2;
      if(condition3) continue;
      statement3;
  }
  return statement3;
  ...
  

  The while, the block, the statement, the break and the continue can all be described in a functional model through continuations. Each construct can be considered to be a function that accepts the

  • current environment containing
    • the enclosing scopes
    • optional functions accepting the current environment and returning a continuation to
      • break from the inner most loop
      • continue from the inner most loop
      • return from the current function.
  • all the blocks associated with it (if-blocks, while-block, etc)
  • a continuation to the next statement

  and returns the new environment.

  In the while loop, the condition is evaluated according to the current environment. If it is evaluated to true, then the block is evaluated and returns the new environment. The result of evaluating the while loop again with the new environment is returned. If it is evaluated to false, the result of evaluating the next statement is returned.

  With the break statement, we lookup the break function in the environment. If there is no function found then we are not inside a loop and we give an error. Otherwise we give the current environment to the function and return the evaluated continuation, which would be the statement after the the while loop.

  With the continue statement the same would happen, except the continuation would be the while loop.

  With the return statement the continuation would be the statement following the call to the current function, but it would remove the current enclosing scope from the environment.

  这篇关于什么是“延续”在函数式编程中意味着什么？（特别是SML）的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！