SICP中環境模型可以等價為龍書中(第七章)講的的運行時刻環境么？

01-28

SICP看到第三章，求值的環境模型。感覺很多概念和程序運行時的堆棧，活動記錄(棧幀)有相似的地方。SICP中的環境模型和編譯原理中的棧，活動記錄，訪問鏈等是否就是講了同一件事, 或類似的事？

不是一個層次的東西。

龍書7.2 Stack Allocation of Space描述的Stack是一種用來實現函數調用的機制，每次函數調用會壓一個棧幀，棧幀內包含了函數的本地變數。C/C++編譯器都是這麼乾的。問題在於：

1. 這個模型不管尾遞歸優化。

2. 這個模型不管閉包。

第一個問題，尾遞歸優化的編譯怎麼辦？scheme里是用continuation來做這件事，按下不表。

第二個問題，閉包是怎麼回事？C沒有閉包，C也沒有nested function，你在函數定義里除了參數和本地變數之外，用到的其他變數都在global environment里，編譯期就能把它們內存位置確定然後送進函數體里去。

對於有高階函數的語言而言，當然就需要引入SICP3.2 The Environment Model of Evaluation里提到的閉包了，其實就是對每個lambda表達式求值時，要把當前環境捆進來，要不然以後這個函數拿出來apply的時候，遇到自由變數就傻逼了。。

解釋器這麼寫是為了讓你明白lexical scoping的工作原理如此。至於真正編譯的時候是否直接用龍書描述的call stack？不直接用的話，程序怎麼變換，閉包怎麼優化？那就是其他的事了，欲知詳情可以看Compiling with Continuations一書。

閉包完全可以用面向對象來模擬，某種程度上它們是一回事。比如你用C++11對你自定義的類的對象sort，需要一個比較符，C++11以前你需要傳函數指針，或者一個實現了operator ()的函數對象。其中函數對象只要實現了operator ()可以比較兩個對象返回bool就行，假設它是Comp類的，那麼Comp類還可以有其他的成員，你把這其他的成員當作函數式語言的閉包里的free variable就行了。。然後執行這個類的構造函數實際上跟對lambda表達式求值，生成閉包，把環境加進來差不多就是一回事。如果這樣的函數類里有其他的函數類成員，那就是nested function。。C++11里就可以直接寫lambda表達式了，而編譯器的處理方式就是生成了匿名類來做這事。

@邵成的答案說了問題的一方面——概念的差異，我覺得講得不錯，但是應該把另一方面——概念的相似點——也補充上。我下面的答案基本上是邵成的答案的改述。

SICP 3.2說的environment of evaluation是一個抽象概念，講編程語言原理的書上說的activation record（活動記錄）也是抽象概念，這倆可以說是同一個東西。EE和AR的重點都是(名字 -&> 值)的binding。

當一個語言的函數調用能滿足LIFO順序時，它的activation record就可以按照LIFO順序組織起來。以這種方式組織起來的AR就形成了調用棧（call stack），此時AR就可以叫做棧幀（stack frame）。

由於這種情況在主流語言中很常見，硬體為了加速調用棧的實現，就設計了專門的硬體支持，也就是常見的棧指針寄存器（stack pointer register，例如x86上的ESP/RSP，ARM上的R13），以及能夠間接操縱棧指針的push/pop系指令。使用這樣的硬體支持的棧通常叫做native stack；由於C語言的實現廣泛使用native stack，現代操作系統又常由C實現，這種棧也常被稱為「the C stack」，或者省略為「the stack」。

一門語言在實現調用棧的時候可以選擇使用硬體支持的調用棧，也可以選擇自行管理棧空間（例如在堆上分配棧幀），或者是混合兩者。混合的例子：例如CPython的解釋器，每調用一個Python函數既會在native stack上分配一個解釋器自己的棧幀，同時又會在堆上分配一個解釋器管理的PyFrameObject。

當一門語言含有使函數調用不滿足LIFO順序的功能，例如closure、generator、coroutine、continuation時，那它對應的EE/AR就不一定會用棧的方式組織起來。此時的AR就不應該叫做「stack frame」了。

一個有函數（或類似函數的語言結構）的語言，就算其函數調用並非完全滿足LIFO順序，可能不滿足LIFO順序的只是較小比例的情況，此時一種實現上的優化就是盡量用調用棧來組織AR，找出那些不滿足LIFO順序的部分（例如被閉包捕獲了的局部變數）然後只在堆上為那些變數分配空間。這樣的AR大部分還是在棧上的，但也會有小部分在堆上。

舉一個C#的generator的例子。

C#給許多人的印象是一門比較傳統的面向對象語言，但其實它也有不少「函數式風格」的語言功能，例如generator。用該功能來寫個簡單的算Fibonacci數列的生成器：

using System; using System.Collections.Generic;

public class FibonacciGenerator { public static IEnumerable& Generate(int ord) { int first = 1; int second = 1; int maxord = (ord &< 46)? ord : 46; for (int i = 0; i &< maxord; ++i) { int current = first + second; yield return first; first = second; second = current; } } } sealed class Program { static void Main(string[] args) { int n = 10; foreach (int i in FibonacciGenerator.Generate(n)) { Console.WriteLine(i); } } }

看起來Generate()「方法」里的first、second、maxord、i、current這些都是「局部變數」，但這個「方法」可以被多次返回和再入，其調用並不滿足LIFO順序。所以這些看似「局部變數」的東西也不是放在stack frame上，而是放在一個在堆上分配的、由編譯器自動生產的對象實例里：

using System; using System.Collections; using System.Collections.Generic; using System.Diagnostics; using System.Runtime.CompilerServices; using System.Threading;


public class FibonacciGenerator {

    public static IEnumerable& Generate(int ord) {

        &d__0 d__ = new &d__0(-2);

        d__.&<&>3__ord = ord;

        return d__;

    }
    [CompilerGenerated]

    private sealed class &d__0 : IEnumerable&, IEnumerable, IEnumerator&, IEnumerator, IDisposable {

        private int &<&>1__state;

        private int &<&>2__current;

        public int &<&>3__ord;

        private int &<&>l__initialThreadId;

        public int &5__5;

        public int &5__1;

        public int &5__4;

        public int &5__3;

        public int &5__2;

        public int ord;
        [DebuggerHidden]

        public &d__0(int &<&>1__state) {

            this.&<&>1__state = &<&>1__state;

            this.&<&>l__initialThreadId = Thread.CurrentThread.ManagedThreadId;

        }
        private bool MoveNext() {

            switch (this.&<&>1__state) {

                case 0:

                    this.&<&>1__state = -1;

                    this.&5__1 = 1;

                    this.&5__2 = 1;

                    this.&5__3 = (this.ord &< 0x2e) ? this.ord : 0x2e;
                    this.&5__4 = 0;

                    while (this.&5__4 &< this.&5__3) {

                        this.&5__5 = this.&5__1 + this.&5__2;

                        this.&<&>2__current = this.&5__1;

                        this.&<&>1__state = 1;

                        return true;

                    Label_0084:

                        this.&<&>1__state = -1;

                        this.&5__1 = this.&5__2;

                        this.&5__2 = this.&5__5;

                        this.&5__4++;

                    }

                    break;
                case 1:

                    goto Label_0084;

            }

            return false;

        }
        [DebuggerHidden]

        IEnumerator& IEnumerable&.GetEnumerator() {

            FibonacciGenerator.&d__0 d__;

            if ((Thread.CurrentThread.ManagedThreadId == this.&<&>l__initialThreadId)  (this.&<&>1__state == -2)) {

                this.&<&>1__state = 0;

                d__ = this;

            } else {

                d__ = new FibonacciGenerator.&d__0(0);

            }

            d__.ord = this.&<&>3__ord;

            return d__;

        }
        [DebuggerHidden]

        IEnumerator IEnumerable.GetEnumerator() {

            return this.System.Collections.Generic.IEnumerable&.GetEnumerator();

        }
        [DebuggerHidden]

        void IEnumerator.Reset() {

            throw new NotSupportedException();

        }
        void IDisposable.Dispose() { }
        int IEnumerator&.Current {

            [DebuggerHidden]

            get { return this.&<&>2__current; }

        }

object IEnumerator.Current { [DebuggerHidden] get { return this.&<&>2__current; } } } }

這跟邵成答案里說閉包可以用對象實現是同一個道理。

SICP Environment Model 和語言中的 closure 並不是對等的。特別是 SICP Chapter 3 的 model 是簡化的。理解 SICP Environment Model 和常用的 closure 的差別，就能解釋很多東西。因為「龍書」更強調為實現實用的編譯器，而 SICP Chapter 3 只是一個理想模型。

首先是這個 Chapter 3 model 並不管理資源的回收。它的資源回收是通過 Scheme GC 來完成的。如果使用沒有 GC 的語言來舉例子，就無法忽略資源回收這方面。加入資源回收之後，Evniorment Model 就會大幅度向傳統的 stack 靠攏。所以 Chapter 3 看似理想，是因為倚靠了 GC 來掩蓋了 stack 這個大多數程序員都熟悉的概念。

第二，這個 model 完全沒有考慮性能，以至於它非常強大，涵蓋了一切 create function 的方式。包括 eval。而現實中，closure 出於性能和資源回收的考慮，只支持 in-source-code nested function creation。我認為這就是造成著名的 eval 語義不嚴格問題的原因。實用語言的 eval （比如 Lua 中的 load string ）通常不會支持 Environment Model。這樣 Environment Model 中大量的 runtime overhead 可以提前到 compile time 來完成。這也是 SICP Chapter 5 的主要內容。動態語言的 compile 很大程度上是對 local variable 和 upval 的優化。大多數動態語言用 closure 來實現 object 比用 table/list 之類的數據結構實現還快也是這個道理。

可以參看：Closure 與 Unbound 變數 ? 技術奇異點