SECD机器

**SECD 機**是有高度影響力的一種虛擬機和抽象機器，它意圖用作函數式程式語言編譯器的編譯目標。四個字母分別表示：**S**tack、**E**nvironment、**C**ontrol、**D**ump，它們是這個機器的內部暫存器。暫存器 Stack、Control 和 Dump 指向堆疊（的某種實現），而 Environment 指向關聯數組（的某種實現）。

這個機器是第一個專門設計用來求值 lambda 演算表達式的機器。它最初描述於 Peter J. Landin 的 1964 年論文《表達式的機器求值》中。Landin 發表的描述非常抽象，留下了很多實現選擇待定（就像一種操作語義）。因此 SECD 機經常以一種更具體的形式出現，比如 Peter Henderson 的 LispKit Lisp 編譯器，它自從 1980 年開始發行。自此它已經被用作了一些其他的實驗編譯器的目標。

在 1989 年卡爾加里大學的研究者製作了這個機器的一個硬體實現。

## Landin 的貢獻

D. A. Turner 在 2012 年指出，《Algol 60 修訂報告》（Peter Naur 的 1963 年版）規定了依據複製規則的過程調用，這避免了具有對標識符的系統性改變的變量捕獲。這種方法被加入到了 Algol 60 實現之中，但是在函數是頭等公民的函數式編程語言之中，自由變量在調用棧上可能被錯誤的解引用。

D. A. Turner 注意到，Peter J. Landin 通過他的 SECD 機解決了這個問題，在這個機器中函數轉而通過在堆中的閉包來表示。

## 非正式描述

在開始求值一個表達式的時候，這個表達式被裝載為控制 **`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 等。它們都從堆疊得到任何必須的實際參數。

## 參見

* ISWIM
* Krivine 機

## 引用

## 延伸閱讀

* 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）.

## 外部連結

* SECD collection （頁面存檔備份，存於網際網路檔案館）