SECD抽象機
SECD機是有高度影響力的一種虛擬機和抽象機器，它意圖用作函數式程式語言編譯器的編譯目標。四個字母分別表示：Stack、Environment、Control、Dump，它們是這個機器的內部寄存器。寄存器Stack、Control和Dump指向堆疊（的某種實現），而Environment指向關聯數組（的某種實現）。
這個機器是第一個專門設計用來求值lambda演算表達式的機器。它最初描述於Peter J. Landin的1964年論文《表達式的機器求值》中[1]。Landin發表的描述非常抽象，留下了很多實現選擇待定（就像一種操作語義）。因此SECD機經常以一種更具體的形式出現，比如Peter Henderson的LispKit Lisp編譯器，它自從1980年開始發行。自此它已經被用作了一些其他的實驗編譯器的目標。
在1989年卡爾加里大學的研究者製作了這個機器的一個硬件實現[2]。
Landin的貢獻
[編輯]D. A. Turner在2012年指出，《Algol 60修訂報告》（Peter Naur的1963年版）規定了依據複製規則的過程調用，這避免了具有對標識符的系統性改變的變量捕獲[3]。這種方法被加入到了Algol 60實現之中，但是在函數是頭等公民的函數式編程語言之中，自由變量在調用棧上可能被錯誤的解引用[4]。
D. A. Turner注意到，Peter J. Landin通過他的SECD機解決了這個問題，在這個機器中函數轉而通過在堆中的閉包來表示[5]。
非正式描述
[編輯]在開始求值一個表達式的時候，這個表達式被裝載為控制C的唯一元素。環境E、堆疊S轉儲D開始時為空。
在C的求值期間，表達式被轉換成具有ap（就是apply）作為唯一算符的逆波蘭表示法（RPN）。例如，表達式F (G X)（一個單一的列表元素）被轉變為列表X:G:ap:F:ap。
C的求值進行得類似於其他的RPN表達式。如果在C中的第一個項目是值，把它壓入堆疊S。更準確的說，如果這個項目是個標識符，剛壓入到堆疊的這個值，將綁定於在當前環境E中的那個標識符。如果這個項目是個抽象，則構造一個閉包來保存它的自由變量的綁定（它們在E中），並把這個閉包壓入堆疊。
如果這個項目是ap，從堆疊彈出兩個值並完成應用（將第一個應用於第二個）。如果應用的結果是個值，把它壓入堆疊。
但是，如果應用是將一個抽象（已表示為閉包）應用於一個值，它結果的那個lambda演算表達式，自身可能就是應用（而非一個值），因而不能壓入堆疊。在這種情況下，S、E和C的當前內容被壓入D （它是這些三元組的堆疊），S被重新初始化為空，而C被重新初始化為這次應用的結果，具有E包含針對這個表達式的自由變量的環境，增加上對這個應用的實際參數值的綁定。求值繼續如上那樣進行。
求值完成由C為空來指示，在這種情況下結果在堆疊S之上。接着彈出在D上的最近保存的求值狀態，並把已經完成的計算的結果壓入堆疊，位於從D恢復的內容之上。恢復狀態的求值繼續如上那樣進行。
如果C和D二者為空，則整體求值完成，結果在堆疊S之上。
寄存器和內存
[編輯]SECD機是基於堆疊的。函數從堆疊得到它們的實際參數。在指令流之中給內建指令的實際參數立即編碼在它們之後。
像所有內部數據結構一樣，堆疊是個列表，具有S寄存器指向列表頭部或開始處。由於列表數據結構，堆疊不需要連續的內存塊，所以只要有一個單一空閒內存單元，就有堆疊空間可以獲得。即使在所有單元都已經使用了時候，垃圾回收可能產生額外的空閒內存。明顯的，SECD結構的特定實現者可以將堆疊實現為正規的堆疊結構，從而改進這個虛擬機的整體效能，假定在這個堆疊的尺寸上施加嚴格限定的話。
C寄存器指向要求值的代碼或指令列表的頭部。一旦這裏的指令已經被執行，類似於常規機器中的「指令指針」（或程序計數器），C將指向在列表中的下一個指令，除非後續指令總是在執行期間指定而不缺省的包含在後續內存位置上，如在常規機器的情況下那樣。
當前變量環境由E寄存器管理，它指向一個列表的列表。每個個體列表表示一個環境層級：當前函數的那些形式參數位於這個列表的頭部，在當前函數中是自由的但受到外圍函數所約束的那些變量，在E的另一個元素中。
D寄存器指向轉儲的頭部， 它被用作其他寄存器的值臨時存儲，比如在函數調用期間。它可以比擬於其他機器的返回堆疊。
SECD機的內存組織，類似於多數函數式語言解釋器所用的模型：一些內存單元，其中每個都持有要麼一個「原子」（一個單一的值比如13），要麼表示一個空或非空列表。在後者情況下，這個單元持有兩個到其他單元的指針，一個標識第一個個元素，而另一個標識排除第一個元素的列表。這兩個指針傳統上分別叫做car和cdr，但是更現代的術語是「head」和「tail」經常用作其替代。一個單元可以持有的不同類型單元，可以用通過一個標誌來區別。它還區分原子的常見不同類型（整數、字符串等）。
所以，持有數字1, 2, 3的列表，通常寫為(1 2 3)，可以表示為如下：
地址 标志 内容（对于整数是值，对于列表是car和cdr）
9 [ integer | 2 ]
8 [ integer | 3 ]
7 [ list | 8 | 0 ]
6 [ list | 9 | 7 ]
...
2 [ list | 1 | 6 ]
1 [ integer | 1 ]
0 [ nil ]
內存單元3到5不屬於這個列表，這個列表的那些單元可以隨機的分佈在內存中。單元2是這個列表的頭部，它指向持有第一個元素值的單元1，和只包含2和3的列表（開始於單元6）。單元6指向持有2的單元和單元7，它表示只包含3的列表。它指向包含值3的單元8，並把指向空列表（nil）作為cdr。在SECD機中，單元0總是隱含的表示空列表，所有不需要特殊的標誌來指示空列表（需要做的就是簡單的指向單元0）。
在列表中cdr必須指向另一個列表就是一個約定。如果car和cdr二者都指向原子，則產生一個有序對，通常寫為(1 . 2)。
指令
[編輯]nil：將一個nil指針壓入堆疊。ldc：將一個常量實際參數壓入堆疊。ld：將一個變量的值壓入堆疊。這個變量是由一個有序對實際參數來指示。這個有序對的car指定層級，而cdr指定位置。所以(1 . 3)給出當前函數（層級1）的第三個參數。sel：接受兩個列表實際參數，並從堆疊彈出一個值。如果彈出的值是非nil則執行第一個列表，否則執行第二個列表。在這些列表指針被製作成C的新值之前，把到跟隨在sel之後指令的指針保存於轉儲之上。join：從轉儲彈出一個列表引用，並使其成為C的新值。這個指令出現在sel的兩個可選列表的結束。ldf：接受表示一個函數的一個列表實際參數。它構造一個閉包（包含這個函數和當前環境的有序對），並把它壓入堆疊。ap：從堆疊彈出一個閉包和一個形式參數值的列表。通過安裝這個閉包的環境作為當前環境，將這個形式參數列表壓入到環境列表之前，清除堆疊，並設置C為這個閉包的函數指針，將這個閉包應用於這些形式參數。以前的S、E和C的下一個值被保存於轉儲之上。ret：從堆疊彈出一個返回值，從轉儲恢復S、E和C，並把這個返回值壓入新的當前堆疊。dum：將一個虛設（dummy）即空列表，壓入到環境列表之前。rap：作用如同ap，只是它將出現的虛設環境替代為當前的環境，這使得遞歸函數成為可能。
還存在一些用於基本函數的指令，比如car、cdr、列表構造、整數加法、I/O等。它們都從堆疊得到任何必須的實際參數。
參見
[編輯]引用
[編輯]- ^ Landin, P. J. The Mechanical Evaluation of Expressions (PDF). The Computer Journal. January 1964, 6 (4): 308–320 [2022-11-16]. doi:10.1093/comjnl/6.4.308. （原始內容存檔 (PDF)於2022-11-16）.
- ^ A paper on the design, SECD: DESIGN ISSUES is available.
- ^ D. A. Turner. Some History of Functional Programming Languages (PDF). in an invited lecture TFP12, St Andrews University. 12 June 2012 [2021-02-18]. （原始內容 (PDF)存檔於2020-04-15）.
Algol 60 is not normally thought of as a functional language but its rules for procedures (the Algol equivalent of functions) and variable binding were closely related to those of λ-calculus.
The Revised Report on Algol 60 (Naur 1963) is a model of precise technical writing. It defines the effect of a procedure call by a copying rule with a requirement for systematic change of identifiers where needed to avoid variable capture — exactly like β-reduction.
Although formal parameters could be declared value the default parameter passing mode was call by name, which required the actual parameter to be copied unevaluated into the procedure body at every occurrence of the formal parameter. This amounts to normal order reduction (but not graph reduction, there is no sharing). The use of call by name allowed an ingenious programming technique: Jensen’s Device. - ^ D. A. Turner. Some History of Functional Programming Languages (PDF). in an invited lecture TFP12, St Andrews University. 12 June 2012 [2021-02-18]. （原始內容 (PDF)存檔於2020-04-15）.
Algol 60 allowed textually nested procedures and passing procedures as parameters (but not returning procedures as results). The requirement in the copying rule for systematic change of identifiers has the effect of enforcing static (that is lexicographic) binding of free variables.
In their book 「Algol 60 Implementation」, Randell and Russell (1964, Sect. 2.2) handle this by two sets of links between stack frames. The dynamic chain links each stack frame, representing a procedure call, to the frame that called it. The static chain links each stack frame to that of the textually containing procedure, which might be much further away. Free variables are accessed via the static chain.
This mechanism works well for Algol 60 but in a language in which functions can be returned as results, a free variable might be held onto after the function call in which it was created has returned, and will no longer be present on the stack. - ^ D. A. Turner. Some History of Functional Programming Languages (PDF). in an invited lecture TFP12, St Andrews University. 12 June 2012 [2021-02-18]. （原始內容 (PDF)存檔於2020-04-15）.
Landin (1964) solved this in his SECD machine. A function is represented by a closure, consisting of code for the function plus the environment for its free variables. The environment is a linked list of name-value pairs. Closures live in the heap.
延伸閱讀
[編輯]- Olivier Danvy. A Rational Deconstruction of Landin's SECD Machine （頁面存檔備份，存於互聯網檔案館）. BRICS research report RS-04-30, 2004. ISSN 0909-0878
- Field, Anthony J. Field and Peter G. Harrison. 1988 Functional Programming. Addison-Wesley. ISBN 0-201-19249-7
- Graham, Brian T. 1992 "The SECD Microprocessor: A Verification Case Study". Springer. ISBN 0-7923-9245-0
- Henderson, Peter. 1980 Functional Programming: Application and Implementation. Prentice Hall. ISBN 0-13-331579-7
- Kogge, Peter M. The Architecture of Symbolic Computers. ISBN 0-07-035596-7
- Peter Landin. The next 700 programming languages (PDF). Comm. ACM. March 1966, 9 (3): 157–166 [2021-02-18]. doi:10.1145/365230.365257. （原始內容 (PDF)存檔於2010-06-20）.