90分鐘實(shí)現(xiàn)一門編程語言(極簡(jiǎn)解釋器教程)
本文介紹了如何使用 C# 實(shí)現(xiàn)一個(gè)簡(jiǎn)化 Scheme——iScheme 及其解釋器。
如果你對(duì)下面的內(nèi)容感興趣：
- 實(shí)現(xiàn)基本的詞法分析，語法分析并生成抽象語法樹。
- 實(shí)現(xiàn)嵌套作用域和函數(shù)調(diào)用。
- 解釋器的基本原理。
- 以及一些 C# 編程技巧。
那么請(qǐng)繼續(xù)閱讀。
如果你對(duì)以下內(nèi)容感興趣：
- 高級(jí)的詞法/語法分析技術(shù)。
- 類型推導(dǎo)/分析。
- 目標(biāo)代碼優(yōu)化。
本文則過于初級(jí)，你可以跳過本文，但歡迎指出本文的錯(cuò)誤 :-)
代碼樣例
public static int Add(int a, int b) {
return a + b;
}
>> Add(3, 4)
>> 7
>> Add(5, 5)
>> 10
這段代碼定義了 Add 函數(shù)，接下來的 >> 符號(hào)表示對(duì) Add(3, 4) 進(jìn)行求值，再下一行的 >> 7 表示上一行的求值結(jié)果，不同的求值用換行分開。可以把這里的 >> 理解成控制臺(tái)提示符（即Terminal中的PS）。
什么是解釋器
解釋器（Interpreter）是一種程序，能夠讀入程序并直接輸出結(jié)果，如上圖。相對(duì)于編譯器（Compiler），解釋器并不會(huì)生成目標(biāo)機(jī)器代碼，而是直接運(yùn)行源程序，簡(jiǎn)單來說：
解釋器是運(yùn)行程序的程序。
計(jì)算器就是一個(gè)典型的解釋器，我們把數(shù)學(xué)公式（源程序）給它，它通過運(yùn)行它內(nèi)部的”解釋器”給我們答案。
iScheme 編程語言
iScheme 是什么？
- Scheme 語言的一個(gè)極簡(jiǎn)子集。
- 雖然小，但變量，算術(shù)|比較|邏輯運(yùn)算，列表，函數(shù)和遞歸這些編程語言元素一應(yīng)俱全。
- 非常非常慢——可以說它只是為演示本文的概念而存在。
OK，那么 Scheme 是什么？
- 一種函數(shù)式程序設(shè)計(jì)語言。
- 一種 Lisp 方言。
- 麻省理工學(xué)院程序設(shè)計(jì)入門課程使用的語言（參見 MIT 6.001 和 計(jì)算機(jī)程序的構(gòu)造與解釋）。
使用 波蘭表達(dá)式（Polish Notation）。
更多的介紹參見 [Scheme編程語言]。
以計(jì)算階乘為例：
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 只是一個(gè)用于演示的語言，所以目前只提供對(duì)整數(shù)的支持。iScheme 使用 C# 的 Int64 類型作為其內(nèi)部的數(shù)值表示方法。
定義變量
iScheme使用`def`關(guān)鍵字定義變量
>> (def a 3) >> 3 >> a >> 3
算術(shù)|邏輯|比較操作
與常見的編程語言（C#, Java, C++, C）不同，Scheme 使用 波蘭表達(dá)式，即前綴表示法。例如：
C#中的算術(shù)|邏輯|比較操作
// Arithmetic ops a + b * c a / (b + c + d) // Logical ops (cond1 && cond2) || cond3 // Comparing ops a == b 1 < a && a < 3
對(duì)應(yīng)的iScheme代碼
; Arithmetic ops (+ a (* b c)) (/ a (+ b c d)) ; Logical ops (or (and cond1 cond2) cond3) ; Comparing ops (= a b) (< 1 a 3)
需要注意的幾點(diǎn)：
iScheme 中的操作符可以接受不止兩個(gè)參數(shù)——這在一定程度上控制了括號(hào)的數(shù)量。
iScheme 邏輯操作使用 and , or 和 not 代替了常見的 && , || 和 ! ——這在一定程度上增強(qiáng)了程序的可讀性。
順序語句
iScheme使用 begin 關(guān)鍵字標(biāo)識(shí)順序語句，并以最后一條語句的值作為返回結(jié)果。以求兩個(gè)數(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 關(guān)鍵字定義列表，并提供 first 關(guān)鍵字獲取列表的第一個(gè)元素；提供 rest 關(guān)鍵字獲取列表除第一個(gè)元素外的元素。
iScheme的列表示例
>> (define alist (list 1 2 3 4)) >> (list 1 2 3 4) >> (first alist) >> 1 >> (rest alist) >> (2 3 4)
定義函數(shù)
iScheme 使用 func 關(guān)鍵字定義函數(shù)：
iScheme的函數(shù)定義
(def square (func (x) (* x x))) (def sum_square (func (a b) (+ (square a) (square b))))
對(duì)應(yīng)的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)結(jié)構(gòu)，遞歸成了重復(fù)操作的唯一選擇。
以計(jì)算最大公約數(shù)為例：
iScheme計(jì)算最大公約數(shù)
(def gcd (func (a b)
(if (= b 0)
a
(func (b (% a b))))))
對(duì)應(yīng)的C#代碼
public static int GCD (int a, int b) {
if (b == 0) {
return a;
} else {
return GCD(b, a % b);
}
}
高階函數(shù)
和 Scheme 一樣，函數(shù)在 iScheme 中是頭等對(duì)象，這意味著：
- 可以定義一個(gè)變量為函數(shù)。
- 函數(shù)可以接受一個(gè)函數(shù)作為參數(shù)。
- 函數(shù)返回一個(gè)函數(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)
小結(jié)
對(duì) iScheme 的介紹就到這里——事實(shí)上這就是 iScheme 的所有元素，會(huì)不會(huì)太簡(jiǎn)單了？ -_-
接下來進(jìn)入正題——從頭開始構(gòu)造 iScheme 的解釋程序。
解釋器構(gòu)造
iScheme 解釋器主要分為兩部分，解析（Parse）和求值（Evaluation）：
1、解析（Parse）：解析源程序，并生成解釋器可以理解的中間（Intermediate）結(jié)構(gòu)。這部分包含詞法分析，語法分析，語義分析，生成語法樹。
2、求值（Evaluation）：執(zhí)行解析階段得到的中介結(jié)構(gòu)然后得到運(yùn)行結(jié)果。這部分包含作用域，類型系統(tǒng)設(shè)計(jì)和語法樹遍歷。
詞法分析
詞法分析負(fù)責(zé)把源程序解析成一個(gè)個(gè)詞法單元（Lex），以便之后的處理。
iScheme 的詞法分析極其簡(jiǎn)單——由于 iScheme 的詞法元素只包含括號(hào)，空白，數(shù)字和變量名，因此C#自帶的 String#Split 就足夠。
iScheme的詞法分析及測(cè)試
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', ')', ')']
注意
- 個(gè)人不喜歡 String.Join 這個(gè)靜態(tài)方法，所以這里使用C#的擴(kuò)展方法（Extension Methods）對(duì)String類型做了一個(gè)擴(kuò)展。
- 相對(duì)于LINQ Syntax，我個(gè)人更喜歡LINQ Extension Methods，接下來的代碼也都會(huì)是這種風(fēng)格。
- 不要以為詞法分析都是這么離譜般簡(jiǎn)單！vczh的詞法分析教程給出了一個(gè)完整編程語言的詞法分析教程。
語法樹生成
得到了詞素之后，接下來就是進(jìn)行語法分析。不過由于 Lisp 類語言的程序即是語法樹，所以語法分析可以直接跳過。
以下面的程序?yàn)槔?/p>
程序即語法樹
;
(def x (if (> a 1) a 1))
; 換一個(gè)角度看的話：
(
def
x
(
if
(
>
a
1
)
a
1
)
)
更加直觀的圖片：
這使得抽象語法樹（Abstract Syntax Tree）的構(gòu)建變得極其簡(jiǎn)單（無需考慮操作符優(yōu)先級(jí)等問題），我們使用 SExpression 類型定義 iScheme 的語法樹（事實(shí)上S Expression也是Lisp表達(dá)式的名字）。
抽象語法樹的定義
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;
}
}
}
然后用下面的步驟構(gòu)建語法樹：
- 碰到左括號(hào)，創(chuàng)建一個(gè)新的節(jié)點(diǎn)到當(dāng)前節(jié)點(diǎn)（ current ），然后重設(shè)當(dāng)前節(jié)點(diǎn)。
- 碰到右括號(hào)，回退到當(dāng)前節(jié)點(diǎn)的父節(jié)點(diǎn)。
- 否則把為當(dāng)前詞素創(chuàng)建節(jié)點(diǎn)，添加到當(dāng)前節(jié)點(diǎn)中。
抽象語法樹的構(gòu)建過程
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];
}
注意
- 使用 自動(dòng)屬性（Auto Property），從而避免重復(fù)編寫樣版代碼（Boilerplate Code）。
- 使用 命名參數(shù)（Named Parameters）提高代碼可讀性： new SExpression(value: "", parent: null) 比 new SExpression("", null) 可讀。
- 使用 擴(kuò)展方法 提高代碼流暢性： code.Tokenize().ParseAsIScheme 比 ParseAsIScheme(Tokenize(code)) 流暢。
- 大多數(shù)編程語言的語法分析不會(huì)這么簡(jiǎn)單！如果打算實(shí)現(xiàn)一個(gè)類似C#的編程語言，你需要更強(qiáng)大的語法分析技術(shù)：
- 如果打算手寫語法分析器，可以參考 LL(k), Precedence Climbing 和Top Down Operator Precedence。
- 如果打算生成語法分析器，可以參考 ANTLR 或 Bison。
作用域
作用域決定程序的運(yùn)行環(huán)境。iScheme使用嵌套作用域。
以下面的程序?yàn)槔?/p>
>> (def x 1) >> 1 >> (def y (begin (def x 2) (* x x))) >> 4 >> x >> 1
利用C#提供的 Dictionary<TKey, TValue> 類型，我們可以很容易的實(shí)現(xiàn) iScheme 的作用域 SScope ：
iScheme的作用域?qū)崿F(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;
}
}
類型實(shí)現(xiàn)
iScheme 的類型系統(tǒng)極其簡(jiǎn)單——只有數(shù)值，Bool，列表和函數(shù)，考慮到他們都是 iScheme 里面的值對(duì)象（Value Object），為了便于對(duì)它們進(jìn)行統(tǒng)一處理，這里為它們?cè)O(shè)置一個(gè)統(tǒng)一的父類型 SObject ：
public class SObject { }
數(shù)值類型
iScheme 的數(shù)值類型只是對(duì) .Net 中 Int64 （即 C# 里的 long ）的簡(jiǎn)單封裝：
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 可以被轉(zhuǎn)換為 SNumber 且 SNumber 繼承自 SObject ，但 .Net 無法直接把 Int64 轉(zhuǎn)化為 SObject ）：
public class SObject {
...
public static implicit operator SObject(Int64 value) {
return (SNumber)value;
}
}
Bool類型
由于 Bool 類型只有 True 和 False，所以使用靜態(tài)對(duì)象就足矣。
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> 實(shí)現(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();
}
}
實(shí)現(xiàn) IEnumerable<SObject> 后，就可以直接使用LINQ的一系列擴(kuò)展方法，十分方便。
函數(shù)類型
iScheme 的函數(shù)類型（ SFunction ）由三部分組成：
- 函數(shù)體：即對(duì)應(yīng)的 SExpression 。
- 參數(shù)列表。
- 作用域：函數(shù)擁有自己的作用域
SFunction的實(shí)現(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();
}
}
需要注意的幾點(diǎn)
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
也就是說，當(dāng) SFunction 的實(shí)際參數(shù)（Argument）數(shù)量小于其形式參數(shù)（Parameter）的數(shù)量時(shí)，它依然是一個(gè)函數(shù)，無法被求值。
這個(gè)功能有什么用呢？生成高階函數(shù)。有了部分求值，我們就可以使用
(def mul (func (a b) (* a b))) (def mul3 (mul 3)) >> (mul3 3) >> 9
而不用專門定義一個(gè)生成函數(shù)：
(def times (func (n) (func (n x) (* n x)) ) ) (def mul3 (times 3)) >> (mul3 3) >> 9
SFunction#ToString 可以將其自身還原為源代碼——從而大大簡(jiǎn)化了 iScheme 的理解和測(cè)試。
內(nèi)置操作
iScheme 的內(nèi)置操作有四種：算術(shù)|邏輯|比較|列表操作。
我選擇了表達(dá)力（Expressiveness）強(qiáng)的 lambda 方法表來定義內(nèi)置操作：
首先在 SScope 中添加靜態(tài)字段 builtinFunctions ，以及對(duì)應(yīng)的訪問屬性 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# 提供的委托類型，表示一個(gè)接受 T1 和 T2 ，返回 TRESULT
- 這里有一個(gè)小 HACK，使用實(shí)例方法（Instance Method）修改靜態(tài)成員（Static Member），從而實(shí)現(xiàn)一套流暢的 API（參見Fluent Interface）。
接下來就可以這樣定義內(nèi)置操作：
new SScope(parent: null)
.BuildIn("+", addMethod)
.BuildIn("-", subMethod)
.BuildIn("*", mulMethod)
.BuildIn("/", divMethod);
一目了然。
斷言（Assertion）擴(kuò)展
為了便于進(jìn)行斷言，我對(duì) Boolean 類型做了一點(diǎn)點(diǎn)擴(kuò)展。
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.");
}
算術(shù)操作
iScheme 算術(shù)操作包含 + - * / % 五個(gè)操作，它們僅應(yīng)用于數(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);
})
注意到這里有一段重復(fù)邏輯負(fù)責(zé)轉(zhuǎn)型求值（Cast then Evaluation），考慮到接下來還有不少地方要用這個(gè)邏輯，我把這段邏輯抽象成擴(kuò)展方法：
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 為假，那么整個(gè)表達(dá)式為假，無需對(duì) condB 求值。
- (or condA condB) ，如果 condA 為真，那么整個(gè)表達(dá)式為真，無需對(duì) condB 求值。
此外和 + - * / 一樣， and 和 or 也可以接收任意數(shù)量的參數(shù)。
需求明確了接下來就是實(shí)現(xiàn)，iScheme 的邏輯操作實(shí)現(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 的比較操作包括 = < > >= <= ，需要注意下面幾點(diǎn)：
- = 是比較操作而非賦值操作。
-
同算術(shù)操作一樣，它們應(yīng)用于數(shù)值類型，并支持任意數(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;
})
可以預(yù)見所有的比較操作都將使用這段邏輯，因此把這段比較邏輯抽象成一個(gè)擴(kuò)展方法：
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))
注意 = 操作的實(shí)現(xiàn)里面有 Int64 強(qiáng)制轉(zhuǎn)型——因?yàn)槲覀儧]有重載 SNumber#Equals ，所以無法直接通過 == 來比較兩個(gè) SNumber 。
列表操作
iScheme 的列表操作包括 first ， rest ， empty? 和 append ，分別用來取列表的第一個(gè)元素，除第一個(gè)以外的部分，判斷列表是否為空和拼接列表。
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)相當(dāng)?shù)闹貜?fù)邏輯——判斷參數(shù)是否是一個(gè)合法的列表，重復(fù)代碼很邪惡，所以這里把這段邏輯抽象為擴(kuò)展方法：
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;
}
有了這個(gè)擴(kuò)展方法，接下來的列表操作就很容易實(shí)現(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)
測(cè)試
iScheme 的內(nèi)置操作完成之后，就可以測(cè)試下初步成果了。
首先添加基于控制臺(tái)的分析/求值（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 中補(bǔ)充調(diào)用代碼：
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 中調(diào)用該解釋/求值循環(huán)：
static void Main(String[] cmdArgs) {
new SScope(parent: null)
.BuildIn("+", (args, scope) => (args.Evaluate<SNumber>(scope).Sum(s => s)))
// 省略若干內(nèi)置函數(shù)
.BuildIn("empty?", (args, scope) => args.RetrieveSList("empty?").Count() == 0)
.KeepInterpretingInConsole((code, scope) => code.ParseAsScheme().Evaluate(scope));
}
運(yùn)行程序，輸入一些簡(jiǎn)單的表達(dá)式：
看樣子還不錯(cuò) :-)
接下來開始實(shí)現(xiàn)iScheme的執(zhí)行（Evaluation）邏輯。
執(zhí)行邏輯
iScheme 的執(zhí)行就是把語句（SExpression）在作用域（SScope）轉(zhuǎn)化成對(duì)象（SObject）并對(duì)作用域（SScope）產(chǎn)生作用的過程，如下圖所示。
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))
- 處理內(nèi)置函數(shù)調(diào)用：(+ 1 2 3 (first (list 1 2)))
- 處理自定義函數(shù)調(diào)用：(map (func (x) (* x x)) (list 1 2 3))
此外，情況1和2中的 SExpression 沒有子節(jié)點(diǎn)，可以直接讀取其 Value 進(jìn)行求值，余下的情況需要讀取其 Children 進(jìn)行求值。
首先處理沒有子節(jié)點(diǎn)的情況：
處理字面量和具名量
if (this.Children.Count == 0) {
Int64 number;
if (Int64.TryParse(this.Value, out number)) {
return number;
} else {
return scope.Find(this.Value);
}
}
接下來處理帶有子節(jié)點(diǎn)的情況：
首先獲得當(dāng)前節(jié)點(diǎn)的第一個(gè)節(jié)點(diǎn)：
SExpression first = this.Children[0];
然后根據(jù)該節(jié)點(diǎn)的 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 構(gòu)建 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)));
}
處理內(nèi)置操作
首先得到參數(shù)的表達(dá)式，然后調(diào)用對(duì)應(yīng)的內(nèi)置函數(shù)：
else if (SScope.BuiltinFunctions.ContainsKey(first.Value)) {
var arguments = this.Children.Skip(1).ToArray();
return SScope.BuiltinFunctions[first.Value](arguments, scope);
}
處理自定義函數(shù)調(diào)用
自定義函數(shù)調(diào)用有兩種情況：
- 非具名函數(shù)調(diào)用：((func (x) (* x x)) 3)
- 具名函數(shù)調(diào)用：(square 3)
調(diào)用自定義函數(shù)時(shí)應(yīng)使用新的作用域，所以為 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ù)調(diào)用的實(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 解釋器就算完成了。但仔細(xì)觀察求值過程還是有一個(gè)很大的問題，尾遞歸調(diào)用：
- 處理 if 的尾遞歸調(diào)用。
- 處理函數(shù)調(diào)用中的尾遞歸調(diào)用。
Alex Stepanov 曾在 Elements of Programming 中介紹了一種將嚴(yán)格尾遞歸調(diào)用（Strict tail-recursive call）轉(zhuǎn)化為迭代的方法，細(xì)節(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;
}
}
}
應(yīng)用這種方法到 SExpression#Evaluate ，得到轉(zhuǎn)換后的版本：
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;
}
}
}
}
}
一些演示
基本的運(yùn)算
高階函數(shù)
回顧
小結(jié)
除去注釋（貌似沒有注釋-_-），iScheme 的解釋器的實(shí)現(xiàn)代碼一共 333 行——包括空行，括號(hào)等元素。
在這 300 余行代碼里，實(shí)現(xiàn)了函數(shù)式編程語言的大部分功能：算術(shù)|邏輯|運(yùn)算，嵌套作用域，順序語句，控制語句，遞歸，高階函數(shù)，部分求值。
與我兩年之前實(shí)現(xiàn)的 Scheme 方言 Lucida相比，iScheme 除了沒有字符串類型，其它功能和Lucida相同，而代碼量只是前者的八分之一，編寫時(shí)間是前者的十分之一（Lucida 用了兩天，iScheme 用了一個(gè)半小時(shí)），可擴(kuò)展性和易讀性均秒殺前者。這說明了：
- 代碼量不能說明問題。
- 不同開發(fā)者生產(chǎn)效率的差別會(huì)非常巨大。
- 這兩年我還是學(xué)到了一點(diǎn)東西的。-_-
一些設(shè)計(jì)決策
使用擴(kuò)展方法提高可讀性
例如，通過定義 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.");
聲明式編程風(fēng)格
以 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 即可。
不足
當(dāng)然iScheme還是有很多不足：
語言特性方面：
- 缺乏實(shí)用類型：沒有 Double 和 String 這兩個(gè)關(guān)鍵類型，更不用說復(fù)合類型（Compound Type）。
- 沒有IO操作，更不要說網(wǎng)絡(luò)通信。
- 效率低下：盡管去除尾遞歸挽回了一點(diǎn)效率，但iScheme的執(zhí)行效率依然慘不忍睹。
- 錯(cuò)誤信息：錯(cuò)誤信息基本不可讀，往往出錯(cuò)了都不知道從哪里找起。
- 不支持延續(xù)調(diào)用（Call with current continuation，即call/cc）。
- 沒有并發(fā)。
- 各種bug：比如可以定義文本量，無法重載默認(rèn)操作，空括號(hào)被識(shí)別等等。
設(shè)計(jì)實(shí)現(xiàn)方面：
- 使用了可變（Mutable）類型。
- 沒有任何注釋（因?yàn)橛X得沒有必要 -_-）。
- 糟糕的類型系統(tǒng)：Lisp類語言中的數(shù)據(jù)和程序可以不分彼此，而iScheme的實(shí)現(xiàn)中確把數(shù)據(jù)和程序分成了 SObject 和 SExpression ，現(xiàn)在我依然沒有找到一個(gè)融合他們的好辦法。
這些就留到以后慢慢處理了 -_-（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/
注：帶*號(hào)的沒有中譯本。
文章
大多和編譯前端相關(guān)，自己沒時(shí)間也沒能力研究后端。-_-
為什么編譯技術(shù)很重要？看看 Steve Yegge（沒錯(cuò)，就是被王垠黑過的 Google 高級(jí)技術(shù)工程師）是怎么說的（需要翻墻）。
http://steve-yegge.blogspot.co.uk/2007/06/rich-programmer-food.html
本文重點(diǎn)參考的 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
幾種簡(jiǎn)單實(shí)用的語法分析技術(shù)：
- LL(k) Parsing：
- Top Down Operator Precendence：http://javascript.crockford.com/tdop/tdop.html
- Precendence Climbing Parsing：http://en.wikipedia.org/wiki/Operator-precedence_parser
相關(guān)文章
這篇文章主要介紹了c#實(shí)現(xiàn)metro文件壓縮解壓示例,實(shí)現(xiàn)了zip中增加一張新圖片、刪除文件的方法,需要的朋友可以參考下2014-03-03
深入DropDownList用法的一些學(xué)習(xí)總結(jié)分析
本篇文章是對(duì)DropDownList的用法進(jìn)行了詳細(xì)的分析介紹，需要的朋友參考下2013-06-06
關(guān)于正則表達(dá)式，我們都知道挺繁瑣的。本文介紹的是C#中的正則表達(dá)式，希望對(duì)你有幫助，一起來看。2015-10-10
c# 兩個(gè)數(shù)組比較,將重復(fù)部分去掉,返回不重復(fù)部分的實(shí)現(xiàn)
下面小編就為大家?guī)硪黄猚# 兩個(gè)數(shù)組比較,將重復(fù)部分去掉,返回不重復(fù)部分的實(shí)現(xiàn)方法。小編覺得挺不錯(cuò)的，現(xiàn)在就分享給大家，也給大家做個(gè)參考。一起跟隨小編過來看看吧2016-12-12
WPF仿三星手機(jī)充電界面實(shí)現(xiàn)代碼
這篇文章主要為大家詳細(xì)介紹了WPF仿三星手機(jī)充電界面實(shí)現(xiàn)代碼，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2016-08-08
本篇文章是對(duì)C#控件命名規(guī)范進(jìn)行了詳細(xì)的分析介紹，需要的朋友參考下2013-06-06
Thread?是?1.0?時(shí)代的產(chǎn)物，當(dāng)時(shí)?C#?就考慮到了多線程，于是就設(shè)計(jì)了?Thread?。其實(shí)現(xiàn)在不推薦使用，除非在維護(hù)老的項(xiàng)目已經(jīng)用了的。Thread?也是比較雞肋的，有很多缺陷，但也并不是一無是處2021-11-11
這篇文章主要為大家詳細(xì)介紹了如何利用C#實(shí)現(xiàn)簡(jiǎn)單的記事本的功能,文中的示例代碼講解詳細(xì),感興趣的小伙伴可以跟隨小編一起學(xué)習(xí)一下2023-12-12
C#實(shí)現(xiàn)公式計(jì)算驗(yàn)證碼的示例詳解
現(xiàn)在很多的平臺(tái)已經(jīng)不使用普通的數(shù)字、字母等驗(yàn)證碼了，取而代之的是拼圖類、選圖類、旋轉(zhuǎn)類或者計(jì)算類的驗(yàn)證碼。本文將利用C#實(shí)現(xiàn)一個(gè)公式計(jì)算驗(yàn)證碼，感興趣的可以了解一下2022-10-10
c# 免費(fèi)組件html轉(zhuǎn)pdf的實(shí)現(xiàn)過程
這篇文章主要介紹了c# 免費(fèi)組件html轉(zhuǎn)pdf的實(shí)現(xiàn)過程，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教2022-06-06