第十三號艦隊
0%

Continuation, Calll/cc and CPS

Posted on Edited on In , ,

又是一個很雜的題目。

Continuation

看了很多定義之後，覺得這定義是最好的。

所謂continuation，其實本來是一個函數調用機制。

我們熟悉的函數調用方法都是使用堆棧，采用Activation record或者叫Stack frame來記錄從最頂層函數到當前函數的所有context。一個frame/record就是一個函數的局部上下文信息，包括所有的局部變量的值和SP, PC指針的值（通過靜態分析，某些局部變量的信息是不必保存的，特殊的如尾調用的情況則不需要任何stack frame。不過，邏輯上，我們認爲所有信息都被保存了）。函數
的調用前往往伴隨著一些push來保存context信息，函數退出時則是取消當前的record/frame，恢複上一個調用者的record/frame。

如果有用過C/C++/Java等開發過，對於Stack Frame隊上面這段話應該不陌生。

Continuation則是另一種函數調用方式。它不采用堆棧來保存上下文，而是把這些信息保存在continuation record中。這些continuation record和堆棧的activation record的區別在於，它不采用後入先出的線性方式，所有record被組成一棵樹（或者圖），從一個函數調用另一個函數就等於給當前節點生成一個子節點，然後把系統寄存器移動到這個子節點。一個函數的退出等於從當前節點退回到父節點。　

這些節點的刪除是由garbage collection來管理。如果沒有引用這個record，則它就是可以被刪除的。　

舉例來說，我們假設目前我們的程式流程假設是A->B->C->D->E

  • 如果是以Stack Frame的方式的話，由E回到A必須一層一層回傳。
  • 如果是Continuation的話，可以直接透過E拿到A的Context直接回到A，而不用一層一層回覆。
    利用這種特性，可以做出很多奇特的特性，如Backtrack，Exception等。

Call/cc

雖然第一個引進Call/cc的是Scheme，不過我是看了C++的版本才懂，就以這個版本來解釋。
Call/CC 需要一個lambda function，表示之後該回到哪個地方帝續執行。

1
2
3
4
5
6
7
8
9
10
11
int f(cont<int> k) {
    std::cout << "f called" << std::endl;
    k(1);
    std::cout << "k called" << std::endl;
    return 0;
}

void example_f() {
    std::cout << "f returns " << call_cc<int>(f) << std::endl;
}
example_f();

上面的值行劫果是

f called
f returns 1

而底下的k called跟return 0就被忽略了，因此更改程式的控制流。不過要支援完整的 Call/cc 特性，程式語言本身需要考慮很細節。所以完整實現這特性的不多，更多的是continuation passing style的流傳

Continuation passing style

比起把控制權交回，直接把要處理的程式片段傳進去。
例如

1
2
3
4
5
6
7
8
function fact(n) {
  if (n == 0)
    return 1 ;
  else
    return n * fact(n-1) ;
}
var f = fact(5);
console.log(f);

轉換成CPS版就是這個樣子

1
2
3
4
5
6
7
function fact(n,ret) {
  if (n == 0)
    ret(1) ;
  else
    fact(n-1, function (t0) {
     ret(n * t0) }) ;
}

可以用CPS做些什麼

distributed computation

Implementing exceptions

Compilation

Reference