1. 首頁
  2. 問答
  3. 如何實現延續？

如何實現延續？

2008-08-09 71 views
47

我正在研究用C語言編寫的Scheme解釋器。目前它使用C運行時棧作爲它自己的棧，這對於實現延續提出了一個小問題。我目前的解決方案是將C堆棧手動複製到堆，然後在需要時將其複製回來。除了不是標準的C，這個解決方案並不理想。如何實現延續？

什麼是在C中實現Scheme的延續最簡單的方法？

來源

2008-08-09 Kyle Cronin

回答

17

我記得看過一篇文章說可能是幫助你：Cheney on the M.T.A. :-)

方案的一些實施方案，我知道的，比如SISC，在堆上分配他們的呼叫幀。

@ollie：如果所有呼叫幀都在堆上，則不需要進行提升。當然，在性能方面存在折衷：提升的時間，與分配堆中所有幀所需的開銷。也許它應該是解釋器中的可調參數。 :-P

來源

2008-08-09 02:49:25

1

改爲使用顯式堆棧。

來源

2008-08-09 01:29:33 Patrick

+4

-1：顯式堆棧是什麼？一個堆分配的數據結構建模一個堆棧？堆分配的數據結構模擬堆用法的歷史？問題的相關性？ – 2009-12-26 18:11:22

1

帕特里克是正確的，真正做到這一點的唯一方法是在解釋器中使用顯式堆棧，並在需要轉換爲延續時將適當的堆棧段提升到堆中。

這與爲支持它們的語言（關閉和延續有些相關）支持閉包所需的基本相同。

來源

2008-08-09 02:55:01 olliej

+0

但是，爲了支持關閉，你不能只是做拉姆達？ – apg 2008-10-01 17:25:06

28

一個很好的總結，請在Implementation Strategies for First-Class Continuations，由克林格，Hartheimer，和OST的文章。我建議特別關注Chez計劃的實施。

堆棧複製並不那麼複雜，並且有許多可以提高性能的衆所周知的技術。使用堆分配的框架也相當簡單，但是您要爲「正常」情況創建開銷的權衡，因爲您不使用顯式延續。

如果您將輸入代碼轉換爲連續傳遞樣式（CPS），那麼您可以完全消除堆棧。然而，儘管CPS非常優雅，但它在前端增加了另一個處理步驟，並需要額外的優化來克服某些性能影響。

來源

2008-08-31 05:02:30

7

您可以查看的示例包括：Chicken（一種使用C語言編寫的支持延續的計劃實現）; Paul Graham的On Lisp - 他創建了一個CPS轉換器來實現Common Lisp中的延續子集;和Weblocks - 一個基於延續的Web框架，它也實現了Common Lisp中有限形式的延續。

來源

2008-09-25 17:59:39

12

如果你從頭開始，你真的應該看看延續傳遞風格（CPS）轉換。

良好的來源包括「小塊LISP」和Marc Feeley's Scheme in 90 minutes presentation。

來源

2008-12-05 08:00:30

+0

Queinnec的書Lisp In Small Pieces *是*可用的（至少在Paracampus的法文版中） – 2016-01-30 12:20:02

7

繼續不是問題：您可以使用CPS實現具有常規高階函數的那些問題。天真堆棧分配的問題是，尾部調用永遠不會被優化，這意味着你不能成爲方案。

目前最好的方法映射方案的麪條棧到堆棧中使用的蹦牀：基本上是額外的基礎設施，以處理程序的非類C調用和退出。見Trampolined Style (ps)。

有some code說明這兩種想法。

來源

2009-12-03 13:04:35

5

延續基本上在上下文切換點包括堆棧和CPU寄存器的保存的狀態的。至少在切換時不必將整個堆棧複製到堆中，只能重定向堆棧指針。

延續使用纖維平凡實現。 http://en.wikipedia.org/wiki/Fiber_%28computer_science%29 。唯一需要仔細封裝的是參數傳遞和返回值。

在Windows中的纖維使用CreateFiber/SwitchToFiber家庭電話來完成的。在POSIX兼容的系統 它可以與makecontext/swapcontext來完成。

的boost ::協程具有協同程序爲C++，可以作爲一個參考點爲執行工作落實。

來源

2010-01-04 10:33:52

+2

*瑣碎的實現...需要仔細的封裝* - 這段文字有一定的張力。通過鏈接到一些代碼可以改進這個答案。 – 2011-04-12 18:56:58

8

而且到目前爲止，你已經得到了很好的答案，我建議安德魯阿佩爾的Compiling with Continuations。它編寫得非常好，雖然沒有直接處理C，但它是編譯器編寫者非常好的想法的來源。

雞Wiki也有，你會發現很有趣的網頁，如internal structure和compilation process（其中CPS與彙編的實際例子解釋）。

來源

2010-06-08 00:25:17 Jay

+2

我很喜歡Appel的書。一個好處是你可以參考SML/NJ編譯器的源代碼，這是Appel在書中描述的一個非常好的活動例子。 – 2015-03-19 01:00:14

9

看來Dybvig的論點是沒有提到爲止。 這是一個閱讀的樂趣。基於堆的模型 是最容易實現的，但基於堆棧的 更高效。忽略基於字符串的模型。

肯特·代博維格。 「三項計劃實施模式」。 http://www.cs.indiana.edu/~dyb/papers/3imp.pdf

另請參閱ReadScheme.org上的實施文章。 http://library.readscheme.org/page8.html

摘要如下：

本文提出了三種模式以推行該計劃 計劃 - 明語言。第一種是基於堆的模型，在大多數Scheme實現中的某些 表單中使用;第二個是基於堆棧的新模型，在執行大多數程序時比基於堆的模型更有效;第三種是基於字符串的新型號，旨在用於Scheme的多處理器實現 。

基於堆的模型在堆中分配幾個重要的數據結構，包括實際參數列表，綁定環境和調用 幀。

基於堆棧的模型儘可能在堆棧 上分配這些相同的結構。這導致堆分配更少，內存更少，內存更少，指令序列更短，垃圾收集更少，內存使用更有效率。

基於字符串的模型將 中的這些結構的版本分配給程序文本，該文本表示爲一串符號。在 基於字符串的模型中，Scheme程序被翻譯成專門爲支持Scheme而設計的FFP 語言。這種 語言的程序由FFP機器，一個 多處理器字符串縮減計算機直接執行。

基於堆棧的模型是直接實用的模型;它是由作者的Chez Scheme系統使用的 模型，實現了Scheme的高性能 。一旦機器被實現，基於字符串的模型對於 將提供Scheme作爲在FFP機器 上的FFP的高級別替代方案將是有用的。

來源

2011-10-30 15:31:12 soegaard

1

正如soegaard指出，主要參考保持this one

的想法是，繼續是保持它的評估控制堆棧的封閉件。爲了從使用call/cc創建延續的那一刻起繼續進行評估，需要使用控制堆棧。

通常調用延續會導致很長的執行時間，並使用重複的堆棧填充內存。我寫了這個愚蠢的代碼來證明，在mit-scheme中它使計劃崩潰，

代碼總和了前1000個數字1+2+3+...+1000。

(call-with-current-continuation 
(lambda (break) 
    ((lambda (s) (s s 1000 break)) 
    (lambda (s n cc) 
     (if (= 0 n) 
      (cc 0) 
      (+ n 
      ;; non-tail-recursive, 
      ;; the stack grows at each recursive call 
      (call-with-current-continuation 
       (lambda (__) 
       (s s (- n 1) __)))))))))

如果您切換從1000到100000的代碼將花2秒，如果你的成長輸入數字，你會崩潰。

來源

2017-10-25 08:17:27 alinsoar

相關問題

 相關問題