新聞中心
關(guān)鍵字
解釋器, C#, Scheme, 函數(shù)式編程

成都創(chuàng)新互聯(lián)公司專注于企業(yè)營銷型網(wǎng)站建設(shè)、網(wǎng)站重做改版、久治網(wǎng)站定制設(shè)計、自適應(yīng)品牌網(wǎng)站建設(shè)、H5頁面制作、商城網(wǎng)站開發(fā)、集團(tuán)公司官網(wǎng)建設(shè)、外貿(mào)營銷網(wǎng)站建設(shè)、高端網(wǎng)站制作、響應(yīng)式網(wǎng)頁設(shè)計等建站業(yè)務(wù),價格優(yōu)惠性價比高,為久治等各大城市提供網(wǎng)站開發(fā)制作服務(wù)。
關(guān)于
本文介紹了如何使用C#實(shí)現(xiàn)一個簡化但全功能的Scheme方言——iScheme及其解釋器,通過從零開始逐步構(gòu)建,展示了編程語言/解釋器的工作原理。
作者
Lucida a.k.a Luc
如果你是通過移動設(shè)備閱讀本教程,或者認(rèn)為本文的代碼字體太小的,請使用該鏈接以獲得更好的可讀性(博客園的markdown解析器實(shí)在詭異,這里就不多吐槽了)。
提示
如果你對下面的內(nèi)容感興趣:
- 實(shí)現(xiàn)基本的詞法分析,語法分析并生成抽象語法樹。
- 實(shí)現(xiàn)嵌套作用域和函數(shù)調(diào)用。
- 解釋器的基本原理。
- 以及一些C#編程技巧。
那么請繼續(xù)閱讀。
如果你對以下內(nèi)容感興趣:
- 高級的詞法/語法分析技術(shù)。
- 類型推導(dǎo)/分析。
- 目標(biāo)代碼優(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)進(jìn)行求值,再下一行的>> 7表示上一行的求值結(jié)果,不同的求值用換行分開。可以把這里的>>理解成控制臺提示符(即Terminal中的PS)。
什么是解釋器
解釋器(Interpreter)是一種程序,能夠讀入程序并直接輸出結(jié)果,如上圖。相對于編譯器(Compiler),解釋器并不會生成目標(biāo)機(jī)器代碼,而是直接運(yùn)行源程序,簡單來說:
| 解釋器是運(yùn)行程序的程序。 |
計算器就是一個典型的解釋器,我們把數(shù)學(xué)公式(源程序)給它,它通過運(yùn)行它內(nèi)部的"解釋器"給我們答案。
iScheme編程語言
iScheme是什么?
- Scheme語言的一個極簡子集。
- 雖然小,但變量,算術(shù)|比較|邏輯運(yùn)算,列表,函數(shù)和遞歸這些編程語言元素一應(yīng)俱全。
- 非常非常慢——可以說它只是為演示本文的概念而存在。
OK,那么Scheme是什么?
- 一種函數(shù)式程序設(shè)計語言。
- 一種Lisp方言。
- 麻省理工學(xué)院程序設(shè)計入門課程使用的語言(參見MIT 6.001和《計算機(jī)程序的構(gòu)造與解釋》)。
- 使用波蘭表達(dá)式(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類型作為其內(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
對應(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中的操作符可以接受不止兩個參數(shù)——這在一定程度上控制了括號的數(shù)量。
- iScheme邏輯操作使用
and,or和not代替了常見的&&,||和!——這在一定程度上增強(qiáng)了程序的可讀性。
順序語句
iScheme使用begin關(guān)鍵字標(biāo)識順序語句,并以最后一條語句的值作為返回結(jié)果。以求兩個數(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)鍵字獲取列表的第一個元素;提供rest關(guān)鍵字獲取列表除第一個元素外的元素。
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))))
對應(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ù)操作的唯一選擇。
以計算最大公約數(shù)為例:
iScheme計算最大公約數(shù)
- (def gcd (func (a b)
- (if (= b 0)
- a
- (func (b (% a b))))))
對應(yīng)的C#代碼
- public static int GCD (int a, int b) {
- if (b == 0) {
- return a;
- } else {
- return GCD(b, a % b);
- }
- }
#p#
高階函數(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)
小結(jié)
對iScheme的介紹就到這里——事實(shí)上這就是iScheme的所有元素,會不會太簡單了? -_-
接下來進(jìn)入正題——從頭開始構(gòu)造iScheme的解釋程序。
解釋器構(gòu)造
iScheme解釋器主要分為兩部分,解析(Parse)和求值(Evaluation):
- 解析(Parse):解析源程序,并生成解釋器可以理解的中間(Intermediate)結(jié)構(gòu)。這部分包含詞法分析,語法分析,語義分析,生成語法樹。
- 求值(Evaluation):執(zhí)行解析階段得到的中介結(jié)構(gòu)然后得到運(yùn)行結(jié)果。這部分包含作用域,類型系統(tǒng)設(shè)計和語法樹遍歷。
詞法分析
詞法分析負(fù)責(zé)把源程序解析成一個個詞法單元(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
- 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#的擴(kuò)展方法(Extension Methods)對String類型做了一個擴(kuò)展。 - 相對于LINQ Syntax,我個人更喜歡LINQ Extension Methods,接下來的代碼也都會是這種風(fēng)格。
- 不要以為詞法分析都是這么離譜般簡單!vczh的詞法分析教程給出了一個完整編程語言的詞法分析教程。
語法樹生成
得到了詞素之后,接下來就是進(jìn)行語法分析。不過由于Lisp類語言的程序即是語法樹,所以語法分析可以直接跳過。
以下面的程序?yàn)槔?/p>
程序即語法樹
- ;
- (def x (if (> a 1) a 1))
- ; 換一個角度看的話:
- (
- def
- x
- (
- if
- (
- >
- a
- 1
- )
- a
- 1
- )
- )
更加直觀的圖片:
這使得抽象語法樹(Abstract Syntax Tree)的構(gòu)建變得極其簡單(無需考慮操作符優(yōu)先級等問題),我們使用SExpression類型定義iScheme的語法樹(事實(shí)上S Expression也是Lisp表達(dá)式的名字)。
抽象語法樹的定義
- public class SExpression {
- public String Value { get; private set; }
- public List
Children { get; private set; } - public SExpression Parent { get; private set; }
- public SExpression(String value, SExpression parent) {
- this.Value = value;
- this.Children = new List
(); - this.Parent = parent;
- }
- public override String ToString() {
- if (this.Value == "(") {
- return "(" + " ".Join(Children) + ")";
- } else {
- return this.Value;
- }
- }
- }
然后用下面的步驟構(gòu)建語法樹:
- 碰到左括號,創(chuàng)建一個新的節(jié)點(diǎn)到當(dāng)前節(jié)點(diǎn)(
current),然后重設(shè)當(dāng)前節(jié)點(diǎn)。 - 碰到右括號,回退到當(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];
- }
注意
- 使用自動屬性(Auto Property),從而避免重復(fù)編寫樣版代碼(Boilerplate Code)。
- 使用命名參數(shù)(Named Parameters)提高代碼可讀性:
new SExpression(value: "", parent: null)比new SExpression("", null)可讀。 - 使用擴(kuò)展方法提高代碼流暢性:
code.Tokenize().ParseAsIScheme比ParseAsIScheme(Tokenize(code))流暢。 - 大多數(shù)編程語言的語法分析不會這么簡單!如果打算實(shí)現(xiàn)一個類似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類型,我們可以很容易的實(shí)現(xiàn)iScheme的作用域SScope:
iScheme的作用域?qū)崿F(xiàn)
- public class SScope {
- public SScope Parent { get; private set; }
- private Dictionary
variableTable; - public SScope(SScope parent) {
- this.Parent = parent;
- this.variableTable = new Dictionary
(); - }
- 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)極其簡單——只有數(shù)值,Bool,列表和函數(shù),考慮到他們都是iScheme里面的值對象(Value Object),為了便于對它們進(jìn)行統(tǒng)一處理,這里為它們設(shè)置一個統(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可以被轉(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)對象就足矣。
- 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;
- }
- }
#p#
列表類型
iScheme使用.Net中的IEnumberable實(shí)現(xiàn)列表類型SList:
- public class SList : SObject, IEnumerable
{ - private readonly IEnumerable
values; - public SList(IEnumerable
values) { - this.values = values;
- }
- public override String ToString() {
- return "(list " + " ".Join(this.values) + ")";
- }
- public IEnumerator
GetEnumerator() { - return this.values.GetEnumerator();
- }
- IEnumerator IEnumerable.GetEnumerator() {
- return this.values.GetEnumerator();
- }
- }
實(shí)現(xiàn)IEnumerable后,就可以直接使用LINQ的一系列擴(kuò)展方法,十分方便。
函數(shù)類型
iScheme的函數(shù)類型(SFunction)由三部分組成:
- 函數(shù)體:即對應(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ù),無法被求值。
這個功能有什么用呢?生成高階函數(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的理解和測試。
內(nèi)置操作
iScheme的內(nèi)置操作有四種:算術(shù)|邏輯|比較|列表操作。
我選擇了表達(dá)力(Expressiveness)強(qiáng)的lambda方法表來定義內(nèi)置操作:
首先在SScope中添加靜態(tài)字段builtinFunctions,以及對應(yīng)的訪問屬性BuiltinFunctions和操作方法BuildIn。
- public class SScope {
- private static Dictionary
> builtinFunctions = - new Dictionary
>(); - public static Dictionary
> BuiltinFunctions { - get { return builtinFunctions; }
- }
- // Dirty HACK for fluent API.
- public SScope BuildIn(String name, Func
builtinFuntion) { - SScope.builtinFunctions.Add(name, builtinFuntion);
- return this;
- }
- }
注意:
Func是C#提供的委托類型,表示一個接受T1和T2,返回TRESULT- 這里有一個小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)行斷言,我對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ù)操作包含+ - * / %五個操作,它們僅應(yīng)用于數(shù)值類型(也就是SNumber)。
從加減法開始:
- .BuildIn("+", (args, scope) => {
- var numbers = args.Select(obj => obj.Evaluate(scope)).Cast
(); - return numbers.Sum(n => n);
- })
- .BuildIn("-", (args, scope) => {
- var numbers = args.Select(obj => obj.Evaluate(scope)).Cast
().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),考慮到接下來還有不少地方要用這個邏輯,我把這段邏輯抽象成擴(kuò)展方法:
- public static IEnumerable
Evaluate (this IEnumerable expressions, SScope scope) - where T : SObject {
- return expressions.Evaluate(scope).Cast
(); - }
- public static IEnumerable
Evaluate(this IEnumerable expressions, SScope scope) { - return expressions.Select(exp => exp.Evaluate(scope));
- }
然后加減法就可以如此定義:
- .BuildIn("+", (args, scope) => (args.Evaluate
(scope).Sum(s => s))) - .BuildIn("-", (args, scope) => {
- var numbers = args.Evaluate
(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
(scope).Aggregate((a, b) => a * b)) - .BuildIn("/", (args, scope) => {
- var numbers = args.Evaluate
(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
(scope).ToArray(); - return numbers[0] % numbers[1];
- })
邏輯操作
iScheme邏輯操作包括
分享文章:90分鐘實(shí)現(xiàn)一門編程語言——極簡解釋器教程
文章源于:http://m.fisionsoft.com.cn/article/ccioesg.html


咨詢
建站咨詢
