本文介紹了如何使用 C# 實現一個簡化 Scheme——iScheme 及其解釋器。
如果你對下面的內容感興趣：
那么請繼續閱讀。
如果你對以下內容感興趣：
本文則過于初級，你可以跳過本文，但歡迎指出本文的錯誤 :-)
代碼樣例
public static int Add(int a, int b) { return a + b;}>> Add(3, 4)>> 7>> Add(5, 5)>> 10這段代碼定義了 Add 函數，接下來的 >> 符號表示對 Add(3, 4) 進行求值，再下一行的 >> 7 表示上一行的求值結果，不同的求值用換行分開?？梢园堰@里的 >> 理解成控制臺提示符（即Terminal中的PS）。
什么是解釋器
解釋器（Interpreter）是一種程序，能夠讀入程序并直接輸出結果，如上圖。相對于編譯器（Compiler），解釋器并不會生成目標機器代碼，而是直接運行源程序，簡單來說：
解釋器是運行程序的程序。
計算器就是一個典型的解釋器，我們把數學公式（源程序）給它，它通過運行它內部的”解釋器”給我們答案。
iScheme 編程語言
iScheme 是什么？
OK，那么 Scheme 是什么？
使用 波蘭表達式（Polish Notation）。
更多的介紹參見 [Scheme編程語言]。
以計算階乘為例：
C#版階乘
public static int Factorial(int n) { if (n == 1) { return 1; } else { return n * Factorial(n - 1); }}iScheme版階乘
(def factorial (lambda (n) ( if (= n 1) 1 (* n (factorial (- n 1))))))
數值類型
由于 iScheme 只是一個用于演示的語言，所以目前只提供對整數的支持。iScheme 使用 C# 的 Int64 類型作為其內部的數值表示方法。
定義變量
iScheme使用`def`關鍵字定義變量
>> (def a 3)>> 3>> a>> 3
算術|邏輯|比較操作
與常見的編程語言（C#, Java, C++, C）不同，Scheme 使用 波蘭表達式，即前綴表示法。例如：
C#中的算術|邏輯|比較操作
// Arithmetic opsa + b * ca / (b + c + d)// Logical ops(cond1 && cond2) || cond3// Comparing opsa == b1 < a && a < 3
對應的iScheme代碼
; Arithmetic ops(+ a (* b c))(/ a (+ b c d)); Logical ops(or (and cond1 cond2) cond3); Comparing ops(= a b)(< 1 a 3)
需要注意的幾點：
iScheme 中的操作符可以接受不止兩個參數——這在一定程度上控制了括號的數量。
iScheme 邏輯操作使用 and , or 和 not 代替了常見的 && , || 和 ! ——這在一定程度上增強了程序的可讀性。
順序語句
iScheme使用 begin 關鍵字標識順序語句，并以最后一條語句的值作為返回結果。以求兩個數的平均值為例：
C#的順序語句
int a = 3;int b = 5;int c = (a + b) / 2;
iScheme的順序語句
(def c (begin (def a 3) (def b 5) (/ (+ a b) 2)))
控制流操作
iScheme 中的控制流操作只包含 if 。
if語句示例
>> (define a (if (> 3 2) 1 2))>> 1>> a>> 1
列表類型
iScheme 使用 list 關鍵字定義列表，并提供 first 關鍵字獲取列表的第一個元素；提供 rest 關鍵字獲取列表除第一個元素外的元素。
iScheme的列表示例
>> (define alist (list 1 2 3 4))>> (list 1 2 3 4)>> (first alist)>> 1>> (rest alist)>> (2 3 4)
定義函數
iScheme 使用 func 關鍵字定義函數：
iScheme的函數定義
(def square (func (x) (* x x)))(def sum_square (func (a b) (+ (square a) (square b))))
對應的C#代碼
public static int Square (int x) { return x * x;}public static int SumSquare(int a, int b) { return Square(a) + Square(b);}遞歸
由于 iScheme 中沒有 for 或 while 這種命令式語言（Imperative Programming Language）的循環結構，遞歸成了重復操作的唯一選擇。
以計算最大公約數為例：
iScheme計算最大公約數
(def gcd (func (a b) (if (= b 0) a (func (b (% a b))))))
對應的C#代碼
public static int GCD (int a, int b) { if (b == 0) { return a; } else { return GCD(b, a % b); }}和 Scheme 一樣，函數在 iScheme 中是頭等對象，這意味著：
iScheme 的高階函數示例
; Defines a multiply function.(def mul (func (a b) (* a b))); Defines a list map function.(def map (func (f alist) (if (empty? alist) (list ) (append (list (f (first alist))) (map f (rest alist))) ))); Doubles a list using map and mul.>> (map (mul 2) (list 1 2 3))>> (list 2 4 6)
小結
對 iScheme 的介紹就到這里——事實上這就是 iScheme 的所有元素，會不會太簡單了？ -_-
接下來進入正題——從頭開始構造 iScheme 的解釋程序。
解釋器構造
iScheme 解釋器主要分為兩部分，解析（Parse）和求值（Evaluation）：
1、解析（Parse）：解析源程序，并生成解釋器可以理解的中間（Intermediate）結構。這部分包含詞法分析，語法分析，語義分析，生成語法樹。
2、求值（Evaluation）：執行解析階段得到的中介結構然后得到運行結果。這部分包含作用域，類型系統設計和語法樹遍歷。
詞法分析
詞法分析負責把源程序解析成一個個詞法單元（Lex），以便之后的處理。
iScheme 的詞法分析極其簡單——由于 iScheme 的詞法元素只包含括號，空白，數字和變量名，因此C#自帶的 String#Split 就足夠。
iScheme的詞法分析及測試
public static String[] Tokenize(String text) { String[] tokens = text.Replace("(", " ( ").Replace(")", " ) ").Split(" /t/r/n".ToArray(), StringSplitOptions.RemoveEmptyEntries); return tokens;}// Extends String.Join for a smooth API.public static String Join(this String separator, IEnumerable<Object> values) { return String.Join(separator, values);}// Displays the lexes in a readable form.public static String PrettyPrint(String[] lexes) { return "[" + ", ".Join(lexes.Select(s => "'" + s + "'") + "]";}// Some tests>> PrettyPrint(Tokenize("a"))>> ['a']>> PrettyPrint(Tokenize("(def a 3)"))>> ['(', 'def', 'a', '3', ')']>> PrettyPrint(Tokenize("(begin (def a 3) (* a a))"))>> ['begin', '(', 'def', 'a', '3', ')', '(', '*', 'a', 'a', ')', ')']得到了詞素之后，接下來就是進行語法分析。不過由于 Lisp 類語言的程序即是語法樹，所以語法分析可以直接跳過。
以下面的程序為例：
程序即語法樹
;(def x (if (> a 1) a 1)); 換一個角度看的話：( def x ( if ( > a 1 ) a 1 ))
更加直觀的圖片：
這使得抽象語法樹（Abstract Syntax Tree）的構建變得極其簡單（無需考慮操作符優先級等問題），我們使用 SExpression 類型定義 iScheme 的語法樹（事實上S Expression也是Lisp表達式的名字）。
抽象語法樹的定義
public class SExpression { public String Value { get; private set; } public List<SExpression> Children { get; private set; } public SExpression Parent { get; private set; } public SExpression(String value, SExpression parent) { this.Value = value; this.Children = new List<SExpression>(); this.Parent = parent; } public override String ToString() { if (this.Value == "(") { return "(" + " ".Join(Children) + ")"; } else { return this.Value; } }}然后用下面的步驟構建語法樹：
抽象語法樹的構建過程
public static SExpression ParseAsIScheme(this String code) { SExpression program = new SExpression(value: "", parent: null); SExpression current = program; foreach (var lex in Tokenize(code)) { if (lex == "(") { SExpression newNode = new SExpression(value: "(", parent: current); current.Children.Add(newNode); current = newNode; } else if (lex == ")") { current = current.Parent; } else { current.Children.Add(new SExpression(value: lex, parent: current)); } } return program.Children[0];}作用域決定程序的運行環境。iScheme使用嵌套作用域。
以下面的程序為例
>> (def x 1)>> 1>> (def y (begin (def x 2) (* x x)))>> 4>> x>> 1
利用C#提供的 Dictionary<TKey, TValue> 類型，我們可以很容易的實現 iScheme 的作用域 SScope ：
iScheme的作用域實現
public class SScope { public SScope Parent { get; private set; } private Dictionary<String, SObject> variableTable; public SScope(SScope parent) { this.Parent = parent; this.variableTable = new Dictionary<String, SObject>(); } public SObject Find(String name) { SScope current = this; while (current != null) { if (current.variableTable.ContainsKey(name)) { return current.variableTable[name]; } current = current.Parent; } throw new Exception(name + " is not defined."); } public SObject Define(String name, SObject value) { this.variableTable.Add(name, value); return value; }}類型實現
iScheme 的類型系統極其簡單——只有數值，Bool，列表和函數，考慮到他們都是 iScheme 里面的值對象（Value Object），為了便于對它們進行統一處理，這里為它們設置一個統一的父類型 SObject ：
public class SObject { }
數值類型
iScheme 的數值類型只是對 .Net 中 Int64 （即 C# 里的 long ）的簡單封裝：
public class SNumber : SObject { private readonly Int64 value; public SNumber(Int64 value) { this.value = value; } public override String ToString() { return this.value.ToString(); } public static implicit operator Int64(SNumber number) { return number.value; } public static implicit operator SNumber(Int64 value) { return new SNumber(value); }}注意這里使用了 C# 的隱式操作符重載，這使得我們可以：
SNumber foo = 30;SNumber bar = 40;SNumber foobar = foo * bar;
而不必：
SNumber foo = new SNumber(value: 30);SNumber bar = new SNumber(value: 40);SNumber foobar = new SNumber(value: foo.Value * bar.Value);
為了方便，這里也為 SObject 增加了隱式操作符重載（盡管 Int64 可以被轉換為 SNumber 且 SNumber 繼承自 SObject ，但 .Net 無法直接把 Int64 轉化為 SObject ）：
public class SObject { ... public static implicit operator SObject(Int64 value) { return (SNumber)value; }}Bool類型
由于 Bool 類型只有 True 和 False，所以使用靜態對象就足矣。
public class SBool : SObject { public static readonly SBool False = new SBool(); public static readonly SBool True = new SBool(); public override String ToString() { return ((Boolean)this).ToString(); } public static implicit operator Boolean(SBool value) { return value == SBool.True; } public static implicit operator SBool(Boolean value) { return value ? True : False; }}這里同樣使用了 C# 的 隱式操作符重載，這使得我們可以：
SBool foo = a > 1;if (foo) { // Do something...}而不用
SBool foo = a > 1 ? SBool.True: SBool.False;if (foo == SBool.True) { // Do something...}同樣，為 SObject 增加 隱式操作符重載：
public class SObject { ... public static implicit operator SObject(Boolean value) { return (SBool)value; }}列表類型
iScheme使用.Net中的 IEnumberable<T> 實現列表類型 SList ：
public class SList : SObject, IEnumerable<SObject> { private readonly IEnumerable<SObject> values; public SList(IEnumerable<SObject> values) { this.values = values; } public override String ToString() { return "(list " + " ".Join(this.values) + ")"; } public IEnumerator<SObject> GetEnumerator() { return this.values.GetEnumerator(); } IEnumerator IEnumerable.GetEnumerator() { return this.values.GetEnumerator(); }}實現 IEnumerable<SObject> 后，就可以直接使用LINQ的一系列擴展方法，十分方便。
iScheme 的函數類型（ SFunction ）由三部分組成：
SFunction的實現
public class SFunction : SObject { public SExpression Body { get; private set; } public String[] Parameters { get; private set; } public SScope Scope { get; private set; } public Boolean IsPartial { get { return this.ComputeFilledParameters().Length.InBetween(1, this.Parameters.Length); } } public SFunction(SExpression body, String[] parameters, SScope scope) { this.Body = body; this.Parameters = parameters; this.Scope = scope; } public SObject Evaluate() { String[] filledParameters = this.ComputeFilledParameters(); if (filledParameters.Length < Parameters.Length) { return this; } else { return this.Body.Evaluate(this.Scope); } } public override String ToString() { return String.Format("(func ({0}) {1})", " ".Join(this.Parameters.Select(p => { SObject value = null; if ((value = this.Scope.FindInTop(p)) != null) { return p + ":" + value; } return p; })), this.Body); } private String[] ComputeFilledParameters() { return this.Parameters.Where(p => Scope.FindInTop(p) != null).ToArray(); }}需要注意的幾點
iScheme 支持部分求值（Partial Evaluation），這意味著：
部分求值
>> (def mul (func (a b) (* a b)))>> (func (a b) (* a b))>> (mul 3 4)>> 12>> (mul 3)>> (func (a:3 b) (* a b))>> ((mul 3) 4)>> 12
也就是說，當 SFunction 的實際參數（Argument）數量小于其形式參數（Parameter）的數量時，它依然是一個函數，無法被求值。
這個功能有什么用呢？生成高階函數。有了部分求值，我們就可以使用
(def mul (func (a b) (* a b)))(def mul3 (mul 3))>> (mul3 3)>> 9
而不用專門定義一個生成函數：
(def times (func (n) (func (n x) (* n x)) ) )(def mul3 (times 3))>> (mul3 3)>> 9
SFunction#ToString 可以將其自身還原為源代碼——從而大大簡化了 iScheme 的理解和測試。
內置操作
iScheme 的內置操作有四種：算術|邏輯|比較|列表操作。
我選擇了表達力（Expressiveness）強的 lambda 方法表來定義內置操作：
首先在 SScope 中添加靜態字段 builtinFunctions ，以及對應的訪問屬性 BuiltinFunctions 和操作方法 BuildIn 。
public class SScope { private static Dictionary<String, Func<SExpression[], SScope, SObject>> builtinFunctions = new Dictionary<String, Func<SExpression[], SScope, SObject>>(); public static Dictionary<String, Func<SExpression[], SScope, SObject>> BuiltinFunctions { get { return builtinFunctions; } } // Dirty HACK for fluent API. public SScope BuildIn(String name, Func<SExpression[], SScope, SObject> builtinFuntion) { SScope.builtinFunctions.Add(name, builtinFuntion); return this; }}注意：
接下來就可以這樣定義內置操作：
new SScope(parent: null) .BuildIn("+", addMethod) .BuildIn("-", subMethod) .BuildIn("*", mulMethod) .BuildIn("/", divMethod);一目了然。
斷言（Assertion）擴展
為了便于進行斷言，我對 Boolean 類型做了一點點擴展。
public static void OrThrows(this Boolean condition, String message = null) { if (!condition) { throw new Exception(message ?? "WTF"); }}從而可以寫出流暢的斷言：
(a < 3).OrThrows("Value must be less than 3.");
而不用
if (a < 3) { throw new Exception("Value must be less than 3.");}算術操作
iScheme 算術操作包含 + - * / % 五個操作，它們僅應用于數值類型（也就是 SNumber ）。
從加減法開始：
.BuildIn("+", (args, scope) => { var numbers = args.Select(obj => obj.Evaluate(scope)).Cast<SNumber>(); return numbers.Sum(n => n);}).BuildIn("-", (args, scope) => { var numbers = args.Select(obj => obj.Evaluate(scope)).Cast<SNumber>().ToArray(); Int64 firstValue = numbers[0]; if (numbers.Length == 1) { return -firstValue; } return firstValue - numbers.Skip(1).Sum(s => s);})注意到這里有一段重復邏輯負責轉型求值（Cast then Evaluation），考慮到接下來還有不少地方要用這個邏輯，我把這段邏輯抽象成擴展方法：
public static IEnumerable<T> Evaluate<T>(this IEnumerable<SExpression> expressions, SScope scope)where T : SObject { return expressions.Evaluate(scope).Cast<T>();}public static IEnumerable<SObject> Evaluate(this IEnumerable<SExpression> expressions, SScope scope) { return expressions.Select(exp => exp.Evaluate(scope));}然后加減法就可以如此定義：
.BuildIn("+", (args, scope) => (args.Evaluate<SNumber>(scope).Sum(s => s))).BuildIn("-", (args, scope) => { var numbers = args.Evaluate<SNumber>(scope).ToArray(); Int64 firstValue = numbers[0]; if (numbers.Length == 1) { return -firstValue; } return firstValue - numbers.Skip(1).Sum(s => s);})乘法，除法和求模定義如下：
.BuildIn("*", (args, scope) => args.Evaluate<SNumber>(scope).Aggregate((a, b) => a * b)).BuildIn("/", (args, scope) => { var numbers = args.Evaluate<SNumber>(scope).ToArray(); Int64 firstValue = numbers[0]; return firstValue / numbers.Skip(1).Aggregate((a, b) => a * b);}).BuildIn("%", (args, scope) => { (args.Length == 2).OrThrows("Parameters count in mod should be 2"); var numbers = args.Evaluate<SNumber>(scope).ToArray(); return numbers[0] % numbers[1];})iScheme 邏輯操作包括 and ， or 和 not ，即與，或和非。
需要注意的是 iScheme 邏輯操作是 短路求值（Short-circuit evaluation），也就是說：
此外和 + - * / 一樣， and 和 or 也可以接收任意數量的參數。
需求明確了接下來就是實現，iScheme 的邏輯操作實現如下：
.BuildIn("and", (args, scope) => { (args.Length > 0).OrThrows(); return !args.Any(arg => !(SBool)arg.Evaluate(scope));}).BuildIn("or", (args, scope) => { (args.Length > 0).OrThrows(); return args.Any(arg => (SBool)arg.Evaluate(scope));}).BuildIn("not", (args, scope) => { (args.Length == 1).OrThrows(); return args[0].Evaluate(scope);})iScheme 的比較操作包括 = < > >= <= ，需要注意下面幾點：
同算術操作一樣，它們應用于數值類型，并支持任意數量的參數。
= 的實現如下：
.BuildIn("=", (args, scope) => { (args.Length > 1).OrThrows("Must have more than 1 argument in relation operation."); SNumber current = (SNumber)args[0].Evaluate(scope); foreach (var arg in args.Skip(1)) { SNumber next = (SNumber)arg.Evaluate(scope); if (current == next) { current = next; } else { return false; } } return true;})可以預見所有的比較操作都將使用這段邏輯，因此把這段比較邏輯抽象成一個擴展方法：
public static SBool ChainRelation(this SExpression[] expressions, SScope scope, Func<SNumber, SNumber, Boolean> relation) { (expressions.Length > 1).OrThrows("Must have more than 1 parameter in relation operation."); SNumber current = (SNumber)expressions[0].Evaluate(scope); foreach (var obj in expressions.Skip(1)) { SNumber next = (SNumber)obj.Evaluate(scope); if (relation(current, next)) { current = next; } else { return SBool.False; } } return SBool.True;}接下來就可以很方便的定義比較操作：
.BuildIn("=", (args, scope) => args.ChainRelation(scope, (s1, s2) => (Int64)s1 == (Int64)s2)).BuildIn(">", (args, scope) => args.ChainRelation(scope, (s1, s2) => s1 > s2)).BuildIn("<", (args, scope) => args.ChainRelation(scope, (s1, s2) => s1 < s2)).BuildIn(">=", (args, scope) => args.ChainRelation(scope, (s1, s2) => s1 >= s2)).BuildIn("<=", (args, scope) => args.ChainRelation(scope, (s1, s2) => s1 <= s2))注意 = 操作的實現里面有 Int64 強制轉型——因為我們沒有重載 SNumber#Equals ，所以無法直接通過 == 來比較兩個 SNumber 。
列表操作
iScheme 的列表操作包括 first ， rest ， empty? 和 append ，分別用來取列表的第一個元素，除第一個以外的部分，判斷列表是否為空和拼接列表。
first 和 rest 操作如下：
.BuildIn("first", (args, scope) => { SList list = null; (args.Length == 1 && (list = (args[0].Evaluate(scope) as SList)) != null).OrThrows("<first> must apply to a list."); return list.First();}).BuildIn("rest", (args, scope) => { SList list = null; (args.Length == 1 && (list = (args[0].Evaluate(scope) as SList)) != null).OrThrows("<rest> must apply to a list."); return new SList(list.Skip(1));})又發現相當的重復邏輯——判斷參數是否是一個合法的列表，重復代碼很邪惡，所以這里把這段邏輯抽象為擴展方法：
public static SList RetrieveSList(this SExpression[] expressions, SScope scope, String operationName) { SList list = null; (expressions.Length == 1 && (list = (expressions[0].Evaluate(scope) as SList)) != null) .OrThrows("<" + operationName + "> must apply to a list"); return list;}有了這個擴展方法，接下來的列表操作就很容易實現：
.BuildIn("first", (args, scope) => args.RetrieveSList(scope, "first").First()).BuildIn("rest", (args, scope) => new SList(args.RetrieveSList(scope, "rest").Skip(1))).BuildIn("append", (args, scope) => { SList list0 = null, list1 = null; (args.Length == 2 && (list0 = (args[0].Evaluate(scope) as SList)) != null && (list1 = (args[1].Evaluate(scope) as SList)) != null).OrThrows("Input must be two lists"); return new SList(list0.Concat(list1));}).BuildIn("empty?", (args, scope) => args.RetrieveSList(scope, "empty?").Count() == 0)測試
iScheme 的內置操作完成之后，就可以測試下初步成果了。
首先添加基于控制臺的分析/求值（Parse/Evaluation）循環：
public static void KeepInterpretingInConsole(this SScope scope, Func<String, SScope, SObject> evaluate) { while (true) { try { Console.ForegroundColor = ConsoleColor.Gray; Console.Write(">> "); String code; if (!String.IsNullOrWhiteSpace(code = Console.ReadLine())) { Console.ForegroundColor = ConsoleColor.Green; Console.WriteLine(">> " + evaluate(code, scope)); } } catch (Exception ex) { Console.ForegroundColor = ConsoleColor.Red; Console.WriteLine(">> " + ex.Message); } }}然后在 SExpression#Evaluate 中補充調用代碼：
public override SObject Evaluate(SScope scope) { if (this.Children.Count == 0) { Int64 number; if (Int64.TryParse(this.Value, out number)) { return number; } } else { SExpression first = this.Children[0]; if (SScope.BuiltinFunctions.ContainsKey(first.Value)) { var arguments = this.Children.Skip(1).Select(node => node.Evaluate(scope)).ToArray(); return SScope.BuiltinFunctions[first.Value](arguments, scope); } } throw new Exception("THIS IS JUST TEMPORARY!");}最后在 Main 中調用該解釋/求值循環：
static void Main(String[] cmdArgs) { new SScope(parent: null) .BuildIn("+", (args, scope) => (args.Evaluate<SNumber>(scope).Sum(s => s))) // 省略若干內置函數 .BuildIn("empty?", (args, scope) => args.RetrieveSList("empty?").Count() == 0) .KeepInterpretingInConsole((code, scope) => code.ParseAsScheme().Evaluate(scope));}運行程序，輸入一些簡單的表達式：
看樣子還不錯 :-)
接下來開始實現iScheme的執行（Evaluation）邏輯。
執行邏輯
iScheme 的執行就是把語句（SExpression）在作用域（SScope）轉化成對象（SObject）并對作用域（SScope）產生作用的過程，如下圖所示。
iScheme的執行邏輯就在 SExpression#Evaluate 里面：
public class SExpression { // ... public override SObject Evaluate(SScope scope) { // TODO: Todo your ass. }}首先明確輸入和輸出：
此外，情況1和2中的 SExpression 沒有子節點，可以直接讀取其 Value 進行求值，余下的情況需要讀取其 Children 進行求值。
首先處理沒有子節點的情況：
if (this.Children.Count == 0) { Int64 number; if (Int64.TryParse(this.Value, out number)) { return number; } else { return scope.Find(this.Value); }}接下來處理帶有子節點的情況：
首先獲得當前節點的第一個節點：
SExpression first = this.Children[0];
然后根據該節點的 Value 決定下一步操作：
處理 if
if 語句的處理方法很直接——根據判斷條件（condition）的值判斷執行哪條語句即可：
if (first.Value == "if") { SBool condition = (SBool)(this.Children[1].Evaluate(scope)); return condition ? this.Children[2].Evaluate(scope) : this.Children[3].Evaluate(scope);}處理 def
直接定義即可：
else if (first.Value == "def") { return scope.Define(this.Children[1].Value, this.Children[2].Evaluate(new SScope(scope)));}處理 begin
遍歷語句，然后返回最后一條語句的值：
else if (first.Value == "begin") { SObject result = null; foreach (SExpression statement in this.Children.Skip(1)) { result = statement.Evaluate(scope); } return result;}處理 func
利用 SExpression 構建 SFunction ，然后返回：
else if (first.Value == "func") { SExpression body = this.Children[2]; String[] parameters = this.Children[1].Children.Select(exp => exp.Value).ToArray(); SScope newScope = new SScope(scope); return new SFunction(body, parameters, newScope);}處理 list
首先把 list 里的元素依次求值，然后創建 SList ：
else if (first.Value == "list") { return new SList(this.Children.Skip(1).Select(exp => exp.Evaluate(scope)));}處理內置操作
首先得到參數的表達式，然后調用對應的內置函數：
else if (SScope.BuiltinFunctions.ContainsKey(first.Value)) { var arguments = this.Children.Skip(1).ToArray(); return SScope.BuiltinFunctions[first.Value](arguments, scope);}自定義函數調用有兩種情況：
調用自定義函數時應使用新的作用域，所以為 SFunction 增加 Update 方法：
public SFunction Update(SObject[] arguments) { var existingArguments = this.Parameters.Select(p => this.Scope.FindInTop(p)).Where(obj => obj != null); var newArguments = existingArguments.Concat(arguments).ToArray(); SScope newScope = this.Scope.Parent.SpawnScopeWith(this.Parameters, newArguments); return new SFunction(this.Body, this.Parameters, newScope);}為了便于創建自定義作用域，并判斷函數的參數是否被賦值，為 SScope 增加 SpawnScopeWith 和 FindInTop 方法：
public SScope SpawnScopeWith(String[] names, SObject[] values) { (names.Length >= values.Length).OrThrows("Too many arguments."); SScope scope = new SScope(this); for (Int32 i = 0; i < values.Length; i++) { scope.variableTable.Add(names[i], values[i]); } return scope;}public SObject FindInTop(String name) { if (variableTable.ContainsKey(name)) { return variableTable[name]; } return null;}下面是函數調用的實現：
else { SFunction function = first.Value == "(" ? (SFunction)first.Evaluate(scope) : (SFunction)scope.Find(first.Value); var arguments = this.Children.Skip(1).Select(s => s.Evaluate(scope)).ToArray(); return function.Update(arguments).Evaluate();}完整的求值代碼
綜上所述，求值代碼如下
public SObject Evaluate(SScope scope) { if (this.Children.Count == 0) { Int64 number; if (Int64.TryParse(this.Value, out number)) { return number; } else { return scope.Find(this.Value); } } else { SExpression first = this.Children[0]; if (first.Value == "if") { SBool condition = (SBool)(this.Children[1].Evaluate(scope)); return condition ? this.Children[2].Evaluate(scope) : this.Children[3].Evaluate(scope); } else if (first.Value == "def") { return scope.Define(this.Children[1].Value, this.Children[2].Evaluate(new SScope(scope))); } else if (first.Value == "begin") { SObject result = null; foreach (SExpression statement in this.Children.Skip(1)) { result = statement.Evaluate(scope); } return result; } else if (first.Value == "func") { SExpression body = this.Children[2]; String[] parameters = this.Children[1].Children.Select(exp => exp.Value).ToArray(); SScope newScope = new SScope(scope); return new SFunction(body, parameters, newScope); } else if (first.Value == "list") { return new SList(this.Children.Skip(1).Select(exp => exp.Evaluate(scope))); } else if (SScope.BuiltinFunctions.ContainsKey(first.Value)) { var arguments = this.Children.Skip(1).ToArray(); return SScope.BuiltinFunctions[first.Value](arguments, scope); } else { SFunction function = first.Value == "(" ? (SFunction)first.Evaluate(scope) : (SFunction)scope.Find(first.Value); var arguments = this.Children.Skip(1).Select(s => s.Evaluate(scope)).ToArray(); return function.Update(arguments).Evaluate(); } }}到了這里 iScheme 解釋器就算完成了。但仔細觀察求值過程還是有一個很大的問題，尾遞歸調用：
Alex Stepanov 曾在 Elements of Programming 中介紹了一種將嚴格尾遞歸調用（Strict tail-recursive call）轉化為迭代的方法，細節恕不贅述，以階乘為例：
// Recursive factorial.int fact (int n) { if (n == 1) return result; return n * fact(n - 1);}// First tranform to tail recursive version.int fact (int n, int result) { if (n == 1) return result; else { result *= n; n -= 1; return fact(n, result);// This is a strict tail-recursive call which can be omitted }}// Then transform to iterative version.int fact (int n, int result) { while (true) { if (n == 1) return result; else { result *= n; n -= 1; } }}應用這種方法到 SExpression#Evaluate ，得到轉換后的版本：
public SObject Evaluate(SScope scope) { SExpression current = this; while (true) { if (current.Children.Count == 0) { Int64 number; if (Int64.TryParse(current.Value, out number)) { return number; } else { return scope.Find(current.Value); } } else { SExpression first = current.Children[0]; if (first.Value == "if") { SBool condition = (SBool)(current.Children[1].Evaluate(scope)); current = condition ? current.Children[2] : current.Children[3]; } else if (first.Value == "def") { return scope.Define(current.Children[1].Value, current.Children[2].Evaluate(new SScope(scope))); } else if (first.Value == "begin") { SObject result = null; foreach (SExpression statement in current.Children.Skip(1)) { result = statement.Evaluate(scope); } return result; } else if (first.Value == "func") { SExpression body = current.Children[2]; String[] parameters = current.Children[1].Children.Select(exp => exp.Value).ToArray(); SScope newScope = new SScope(scope); return new SFunction(body, parameters, newScope); } else if (first.Value == "list") { return new SList(current.Children.Skip(1).Select(exp => exp.Evaluate(scope))); } else if (SScope.BuiltinFunctions.ContainsKey(first.Value)) { var arguments = current.Children.Skip(1).ToArray(); return SScope.BuiltinFunctions[first.Value](arguments, scope); } else { SFunction function = first.Value == "(" ? (SFunction)first.Evaluate(scope) : (SFunction)scope.Find(first.Value); var arguments = current.Children.Skip(1).Select(s => s.Evaluate(scope)).ToArray(); SFunction newFunction = function.Update(arguments); if (newFunction.IsPartial) { return newFunction.Evaluate(); } else { current = newFunction.Body; scope = newFunction.Scope; } } } }}一些演示
基本的運算
高階函數
除去注釋（貌似沒有注釋-_-），iScheme 的解釋器的實現代碼一共 333 行——包括空行，括號等元素。
在這 300 余行代碼里，實現了函數式編程語言的大部分功能：算術|邏輯|運算，嵌套作用域，順序語句，控制語句，遞歸，高階函數，部分求值。
與我兩年之前實現的 Scheme 方言 Lucida相比，iScheme 除了沒有字符串類型，其它功能和Lucida相同，而代碼量只是前者的八分之一，編寫時間是前者的十分之一（Lucida 用了兩天，iScheme 用了一個半小時），可擴展性和易讀性均秒殺前者。這說明了：
例如，通過定義 OrThrows
public static void OrThrows(this Boolean condition, String message = null) { if (!condition) { throw new Exception(message ?? "WTF"); }}寫出流暢的斷言：
(a < 3).OrThrows("Value must be less than 3.");聲明式編程風格
以 Main 函數為例：
static void Main(String[] cmdArgs) { new SScope(parent: null) .BuildIn("+", (args, scope) => (args.Evaluate<SNumber>(scope).Sum(s => s))) // Other build .BuildIn("empty?", (args, scope) => args.RetrieveSList("empty?").Count() == 0) .KeepInterpretingInConsole((code, scope) => code.ParseAsIScheme().Evaluate(scope));}非常直觀，而且
不足
當然iScheme還是有很多不足：
語言特性方面：
設計實現方面：
這些就留到以后慢慢處理了 -_-（TODO YOUR ASS）
延伸閱讀
書籍
注：帶*號的沒有中譯本。
大多和編譯前端相關，自己沒時間也沒能力研究后端。-_-
為什么編譯技術很重要？看看 Steve Yegge（沒錯，就是被王垠黑過的 Google 高級技術工程師）是怎么說的（需要翻墻）。
http://steve-yegge.blogspot.co.uk/2007/06/rich-programmer-food.html
本文重點參考的 Peter Norvig 的兩篇文章：
幾種簡單實用的語法分析技術：
新聞熱點
疑難解答
