90分鐘實現(xiàn)一門編程語言(極簡解釋器教程)

來源：本站原創(chuàng)|時間：2020-01-10|欄目：C#教程|點擊：次

本文介紹了如何使用 C# 實現(xiàn)一個簡化 Scheme——iScheme 及其解釋器。

如果你對下面的內容感興趣：

實現(xiàn)基本的詞法分析，語法分析并生成抽象語法樹。
實現(xiàn)嵌套作用域和函數(shù)調用。
解釋器的基本原理。
以及一些 C# 編程技巧。

那么請繼續(xù)閱讀。

如果你對以下內容感興趣：

高級的詞法/語法分析技術。
類型推導/分析。
目標代碼優(yōu)化。

本文則過于初級，你可以跳過本文，但歡迎指出本文的錯誤 :-)

代碼樣例

public static int Add(int a, int b) {
  return a + b;
}
>> Add(3, 4)
>> 7
>> Add(5, 5)
>> 10

這段代碼定義了 Add 函數(shù)，接下來的 >> 符號表示對 Add(3, 4) 進行求值，再下一行的 >> 7 表示上一行的求值結果，不同的求值用換行分開?？梢园堰@里的 >> 理解成控制臺提示符（即Terminal中的PS）。

什么是解釋器

解釋器（Interpreter）是一種程序，能夠讀入程序并直接輸出結果，如上圖。相對于編譯器（Compiler），解釋器并不會生成目標機器代碼，而是直接運行源程序，簡單來說：

解釋器是運行程序的程序。

計算器就是一個典型的解釋器，我們把數(shù)學公式（源程序）給它，它通過運行它內部的”解釋器”給我們答案。

iScheme 編程語言

iScheme 是什么？

Scheme 語言的一個極簡子集。
雖然小，但變量，算術|比較|邏輯運算，列表，函數(shù)和遞歸這些編程語言元素一應俱全。
非常非常慢——可以說它只是為演示本文的概念而存在。

OK，那么 Scheme 是什么？

一種函數(shù)式程序設計語言。
一種 Lisp 方言。
麻省理工學院程序設計入門課程使用的語言（參見 MIT 6.001 和計算機程序的構造與解釋）。

使用波蘭表達式（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))))))

數(shù)值類型

由于 iScheme 只是一個用于演示的語言，所以目前只提供對整數(shù)的支持。iScheme 使用 C# 的 Int64 類型作為其內部的數(shù)值表示方法。

定義變量

iScheme使用`def`關鍵字定義變量

>> (def a 3)
>> 3
>> a
>> 3

算術|邏輯|比較操作

與常見的編程語言（C#, Java, C++, C）不同，Scheme 使用波蘭表達式，即前綴表示法。例如：

C#中的算術|邏輯|比較操作

// Arithmetic ops
a + b * c
a / (b + c + d)
// Logical ops
(cond1 && cond2) || cond3
// Comparing ops
a == b
1 < 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 中的操作符可以接受不止兩個參數(shù)——這在一定程度上控制了括號的數(shù)量。
iScheme 邏輯操作使用 and , or 和 not 代替了常見的 && , || 和 ! ——這在一定程度上增強了程序的可讀性。
順序語句

iScheme使用 begin 關鍵字標識順序語句，并以最后一條語句的值作為返回結果。以求兩個數(shù)的平均值為例：

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)

定義函數(shù)

iScheme 使用 func 關鍵字定義函數(shù)：

iScheme的函數(shù)定義

(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）的循環(huán)結構，遞歸成了重復操作的唯一選擇。

以計算最大公約數(shù)為例：

iScheme計算最大公約數(shù)

(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);
  }
}

高階函數(shù)

和 Scheme 一樣，函數(shù)在 iScheme 中是頭等對象，這意味著：

可以定義一個變量為函數(shù)。
函數(shù)可以接受一個函數(shù)作為參數(shù)。
函數(shù)返回一個函數(shù)。

iScheme 的高階函數(shù)示例

; 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）：執(zhí)行解析階段得到的中介結構然后得到運行結果。這部分包含作用域，類型系統(tǒng)設計和語法樹遍歷。
詞法分析

詞法分析負責把源程序解析成一個個詞法單元（Lex），以便之后的處理。

iScheme 的詞法分析極其簡單——由于 iScheme 的詞法元素只包含括號，空白，數(shù)字和變量名，因此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', ')', ')']

注意

個人不喜歡 String.Join 這個靜態(tài)方法，所以這里使用C#的擴展方法（Extension Methods）對String類型做了一個擴展。
相對于LINQ Syntax，我個人更喜歡LINQ Extension Methods，接下來的代碼也都會是這種風格。
不要以為詞法分析都是這么離譜般簡單！vczh的詞法分析教程給出了一個完整編程語言的詞法分析教程。

語法樹生成

得到了詞素之后，接下來就是進行語法分析。不過由于 Lisp 類語言的程序即是語法樹，所以語法分析可以直接跳過。

以下面的程序為例：

程序即語法樹

;
(def x (if (> a 1) a 1))
; 換一個角度看的話：
(
  def
  x
  (
    if
    (
      >
      a
      1
    )
    a
    1
  )
)

更加直觀的圖片：

這使得抽象語法樹（Abstract Syntax Tree）的構建變得極其簡單（無需考慮操作符優(yōu)先級等問題），我們使用 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;
    }
  }
}

然后用下面的步驟構建語法樹：

碰到左括號，創(chuàng)建一個新的節(jié)點到當前節(jié)點（ current ），然后重設當前節(jié)點。
碰到右括號，回退到當前節(jié)點的父節(jié)點。
否則把為當前詞素創(chuàng)建節(jié)點，添加到當前節(jié)點中。

抽象語法樹的構建過程

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];
}

注意

使用自動屬性（Auto Property），從而避免重復編寫樣版代碼（Boilerplate Code）。
使用命名參數(shù)（Named Parameters）提高代碼可讀性： new SExpression(value: "", parent: null) 比 new SExpression("", null) 可讀。
使用擴展方法提高代碼流暢性： code.Tokenize().ParseAsIScheme 比 ParseAsIScheme(Tokenize(code)) 流暢。
大多數(shù)編程語言的語法分析不會這么簡單！如果打算實現(xiàn)一個類似C#的編程語言，你需要更強大的語法分析技術：
- 如果打算手寫語法分析器，可以參考 LL(k), Precedence Climbing 和Top Down Operator Precedence。
- 如果打算生成語法分析器，可以參考 ANTLR 或 Bison。

作用域

作用域決定程序的運行環(huán)境。iScheme使用嵌套作用域。

以下面的程序為例

>> (def x 1)
>> 1
>> (def y (begin (def x 2) (* x x)))
>> 4
>> x
>> 1

利用C#提供的 Dictionary<TKey, TValue> 類型，我們可以很容易的實現(xiàn) iScheme 的作用域 SScope ：

iScheme的作用域實現(xiàn)

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;
  }
}

類型實現(xiàn)

iScheme 的類型系統(tǒng)極其簡單——只有數(shù)值，Bool，列表和函數(shù)，考慮到他們都是 iScheme 里面的值對象（Value Object），為了便于對它們進行統(tǒng)一處理，這里為它們設置一個統(tǒng)一的父類型 SObject ：

public class SObject { }

數(shù)值類型

iScheme 的數(shù)值類型只是對 .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，所以使用靜態(tài)對象就足矣。

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> 實現(xiàn)列表類型 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();
  }
}

實現(xiàn) IEnumerable<SObject> 后，就可以直接使用LINQ的一系列擴展方法，十分方便。

函數(shù)類型

iScheme 的函數(shù)類型（ SFunction ）由三部分組成：

函數(shù)體：即對應的 SExpression 。
參數(shù)列表。
作用域：函數(shù)擁有自己的作用域

SFunction的實現(xiàn)

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 的實際參數(shù)（Argument）數(shù)量小于其形式參數(shù)（Parameter）的數(shù)量時，它依然是一個函數(shù)，無法被求值。

這個功能有什么用呢？生成高階函數(shù)。有了部分求值，我們就可以使用

(def mul (func (a b) (* a b)))
(def mul3 (mul 3))
>> (mul3 3)
>> 9

而不用專門定義一個生成函數(shù)：

(def times (func (n) (func (n x) (* n x)) ) )
(def mul3 (times 3))
>> (mul3 3)
>> 9

SFunction#ToString 可以將其自身還原為源代碼——從而大大簡化了 iScheme 的理解和測試。
內置操作

iScheme 的內置操作有四種：算術|邏輯|比較|列表操作。

我選擇了表達力（Expressiveness）強的 lambda 方法表來定義內置操作：

首先在 SScope 中添加靜態(tài)字段 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;
  }
}

注意：

Func<T1, T2, TRESULT> 是 C# 提供的委托類型，表示一個接受 T1 和 T2 ，返回 TRESULT
這里有一個小 HACK，使用實例方法（Instance Method）修改靜態(tài)成員（Static Member），從而實現(xiàn)一套流暢的 API（參見Fluent Interface）。

接下來就可以這樣定義內置操作：

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 算術操作包含 + - * / % 五個操作，它們僅應用于數(shù)值類型（也就是 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 condA condB) ，如果 condA 為假，那么整個表達式為假，無需對 condB 求值。
(or condA condB) ，如果 condA 為真，那么整個表達式為真，無需對 condB 求值。

此外和 + - * / 一樣， and 和 or 也可以接收任意數(shù)量的參數(shù)。

需求明確了接下來就是實現(xiàn)，iScheme 的邏輯操作實現(xiàn)如下：

.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 的比較操作包括 = < > >= <= ，需要注意下面幾點：

= 是比較操作而非賦值操作。
同算術操作一樣，它們應用于數(shù)值類型，并支持任意數(shù)量的參數(shù)。

= 的實現(xiàn)如下：

.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))

注意 = 操作的實現(xiàn)里面有 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));
})

又發(fā)現(xiàn)相當?shù)闹貜瓦壿嫛袛鄥?shù)是否是一個合法的列表，重復代碼很邪惡，所以這里把這段邏輯抽象為擴展方法：

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;
}

有了這個擴展方法，接下來的列表操作就很容易實現(xiàn)：

.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）循環(huán)：

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 中調用該解釋/求值循環(huán)：

static void Main(String[] cmdArgs) {
  new SScope(parent: null)
    .BuildIn("+", (args, scope) => (args.Evaluate<SNumber>(scope).Sum(s => s)))
    // 省略若干內置函數(shù)
    .BuildIn("empty?", (args, scope) => args.RetrieveSList("empty?").Count() == 0)
    .KeepInterpretingInConsole((code, scope) => code.ParseAsScheme().Evaluate(scope));
}

運行程序，輸入一些簡單的表達式：

看樣子還不錯 :-)

接下來開始實現(xiàn)iScheme的執(zhí)行（Evaluation）邏輯。

執(zhí)行邏輯

iScheme 的執(zhí)行就是把語句（SExpression）在作用域（SScope）轉化成對象（SObject）并對作用域（SScope）產生作用的過程，如下圖所示。

iScheme的執(zhí)行邏輯就在 SExpression#Evaluate 里面：

public class SExpression {
  // ...
  public override SObject Evaluate(SScope scope) {
    // TODO: Todo your ass.
  }
}

首先明確輸入和輸出：

處理字面量（Literals）： 3 ；和具名量（Named Values）： x
處理 if ：(if (< a 3) 3 a)
處理 def ：(def pi 3.14)
處理 begin ：(begin (def a 3) (* a a))
處理 func ：(func (x) (* x x))
處理內置函數(shù)調用：(+ 1 2 3 (first (list 1 2)))
處理自定義函數(shù)調用：(map (func (x) (* x x)) (list 1 2 3))

此外，情況1和2中的 SExpression 沒有子節(jié)點，可以直接讀取其 Value 進行求值，余下的情況需要讀取其 Children 進行求值。

首先處理沒有子節(jié)點的情況：

處理字面量和具名量

if (this.Children.Count == 0) {
  Int64 number;
  if (Int64.TryParse(this.Value, out number)) {
    return number;
  } else {
    return scope.Find(this.Value);
  }
}

接下來處理帶有子節(jié)點的情況：

首先獲得當前節(jié)點的第一個節(jié)點：

SExpression first = this.Children[0];
然后根據(jù)該節(jié)點的 Value 決定下一步操作：

處理 if

if 語句的處理方法很直接——根據(jù)判斷條件（condition）的值判斷執(zhí)行哪條語句即可：

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 里的元素依次求值，然后創(chuàng)建 SList ：

else if (first.Value == "list") {
  return new SList(this.Children.Skip(1).Select(exp => exp.Evaluate(scope)));
}

處理內置操作

首先得到參數(shù)的表達式，然后調用對應的內置函數(shù)：

else if (SScope.BuiltinFunctions.ContainsKey(first.Value)) {
  var arguments = this.Children.Skip(1).ToArray();
  return SScope.BuiltinFunctions[first.Value](arguments, scope);
}

處理自定義函數(shù)調用

自定義函數(shù)調用有兩種情況：

非具名函數(shù)調用：((func (x) (* x x)) 3)
具名函數(shù)調用：(square 3)

調用自定義函數(shù)時應使用新的作用域，所以為 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);
}

為了便于創(chuàng)建自定義作用域，并判斷函數(shù)的參數(shù)是否被賦值，為 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;
}

下面是函數(shù)調用的實現(xiàn)：

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 解釋器就算完成了。但仔細觀察求值過程還是有一個很大的問題，尾遞歸調用：

處理 if 的尾遞歸調用。
處理函數(shù)調用中的尾遞歸調用。

Alex Stepanov 曾在 Elements of Programming 中介紹了一種將嚴格尾遞歸調用（Strict tail-recursive call）轉化為迭代的方法，細節(jié)恕不贅述，以階乘為例：

// 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;
        }
      }
    }
  }
}

一些演示

基本的運算

高階函數(shù)

回顧

小結

除去注釋（貌似沒有注釋-_-），iScheme 的解釋器的實現(xiàn)代碼一共 333 行——包括空行，括號等元素。

在這 300 余行代碼里，實現(xiàn)了函數(shù)式編程語言的大部分功能：算術|邏輯|運算，嵌套作用域，順序語句，控制語句，遞歸，高階函數(shù)，部分求值。

與我兩年之前實現(xiàn)的 Scheme 方言 Lucida相比，iScheme 除了沒有字符串類型，其它功能和Lucida相同，而代碼量只是前者的八分之一，編寫時間是前者的十分之一（Lucida 用了兩天，iScheme 用了一個半小時），可擴展性和易讀性均秒殺前者。這說明了：

代碼量不能說明問題。
不同開發(fā)者生產效率的差別會非常巨大。
這兩年我還是學到了一點東西的。-_-

一些設計決策

使用擴展方法提高可讀性

例如，通過定義 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 函數(shù)為例：

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));
}

非常直觀，而且

如果需要添加新的操作，添加寫一行 BuildIn 即可。
如果需要使用其它語法，替換解析函數(shù) ParseAsIScheme 即可。
如果需要從文件讀取代碼，替換執(zhí)行函數(shù) KeepInterpretingInConsole 即可。

不足

當然iScheme還是有很多不足：

語言特性方面：

缺乏實用類型：沒有 Double 和 String 這兩個關鍵類型，更不用說復合類型（Compound Type）。
沒有IO操作，更不要說網(wǎng)絡通信。
效率低下：盡管去除尾遞歸挽回了一點效率，但iScheme的執(zhí)行效率依然慘不忍睹。
錯誤信息：錯誤信息基本不可讀，往往出錯了都不知道從哪里找起。
不支持延續(xù)調用（Call with current continuation，即call/cc）。
沒有并發(fā)。
各種bug：比如可以定義文本量，無法重載默認操作，空括號被識別等等。

設計實現(xiàn)方面：

使用了可變（Mutable）類型。
沒有任何注釋（因為覺得沒有必要 -_-）。
糟糕的類型系統(tǒng)：Lisp類語言中的數(shù)據(jù)和程序可以不分彼此，而iScheme的實現(xiàn)中確把數(shù)據(jù)和程序分成了 SObject 和 SExpression ，現(xiàn)在我依然沒有找到一個融合他們的好辦法。

這些就留到以后慢慢處理了 -_-（TODO YOUR ASS）

延伸閱讀
書籍

Compilers: Priciples, Techniques and Tools Principles: http://www.amazon.co.uk/Compilers-Principles-Techniques-V-Aho/dp/1292024348/
Language Implementation Patterns: http://www.amazon.co.uk/Language-Implementation-Patterns-Domain-Specific-Programming/dp/193435645X/
*The Definitive ANTLR4 Reference: http://www.amazon.co.uk/Definitive-ANTLR-4-Reference/dp/1934356999/
Engineering a compiler: http://www.amazon.co.uk/Engineering-Compiler-Keith-Cooper/dp/012088478X/
Flex & Bison: http://www.amazon.co.uk/flex-bison-John-Levine/dp/0596155972/
*Writing Compilers and Interpreters: http://www.amazon.co.uk/Writing-Compilers-Interpreters-Software-Engineering/dp/0470177071/
Elements of Programming: http://www.amazon.co.uk/Elements-Programming-Alexander-Stepanov/dp/032163537X/

注：帶*號的沒有中譯本。

文章

大多和編譯前端相關，自己沒時間也沒能力研究后端。-_-

為什么編譯技術很重要？看看 Steve Yegge（沒錯，就是被王垠黑過的 Google 高級技術工程師）是怎么說的（需要翻墻）。

http://steve-yegge.blogspot.co.uk/2007/06/rich-programmer-food.html

本文重點參考的 Peter Norvig 的兩篇文章：

How to write a lisp interpreter in Python: http://norvig.com/lispy.html
An even better lisp interpreter in Python: http://norvig.com/lispy2.html

幾種簡單實用的語法分析技術：

LL(k) Parsing：
- http://eli.thegreenplace.net/2008/09/26/recursive-descent-ll-and-predictive-parsers/
- http://eli.thegreenplace.net/2009/03/20/a-recursive-descent-parser-with-an-infix-expression-evaluator/
- http://eli.thegreenplace.net/2009/03/14/some-problems-of-recursive-descent-parsers/
Top Down Operator Precendence：http://javascript.crockford.com/tdop/tdop.html
Precendence Climbing Parsing：http://en.wikipedia.org/wiki/Operator-precedence_parser

上一篇：C# CheckedListBox控件的用法總結

欄目：C#教程

下一篇：C#實現(xiàn)文件上傳與下載功能實例

本文標題：90分鐘實現(xiàn)一門編程語言(極簡解釋器教程)

本文地址：http://www.jygsgssxh.com/a1/C_jiaocheng/6136.html

更多C#教程

雷火电竞-中国电竞赛事及体育赛事平台

C#教程

90分鐘實現(xiàn)一門編程語言(極簡解釋器教程)

高階函數(shù)

注意

語法樹生成

注意

作用域

函數(shù)類型

邏輯操作

比較操作

處理字面量和具名量

處理自定義函數(shù)調用

去除尾遞歸

回顧

小結

一些設計決策

使用擴展方法提高可讀性

文章

您可能感興趣的文章

閱讀排行

本欄相關

隨機閱讀