90分钟实现一门编程语言(极简解释器教程)
本文介绍了如何使用 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)。 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 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 中的操作符可以接受不止两个参数――这在一定程度上控制了括号的数量。 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 的解释程序。 解释器构造 1、解析(Parse):解析源程序,并生成解释器可以理解的中间(Intermediate)结构。这部分包含词法分析,语法分析,语义分析,生成语法树。 词法分析负责把源程序解析成一个个词法单元(Lex),以便之后的处理。 iScheme 的词法分析极其简单――由于 iScheme 的词法元素只包含括号,空白,数字和变量名,因此C#自带的 String#Split 就足够。 iScheme的词法分析及测试 public static String[] Tokenize(String text) { String[] tokens = text.Replace("("," ( ").Replace(")"," ) ").Split(" trn".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','(',')','*',')'] 注意
语法树生成得到了词素之后,接下来就是进行语法分析。不过由于 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,SObject>>(); public static Dictionary<String,SObject>> BuiltinFunctions { get { return builtinFunctions; } } // Dirty HACK for fluent API. public SScope BuildIn(String name,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("-",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("+",scope) => (args.Evaluate<SNumber>(scope).Sum(s => s))) .BuildIn("-",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("*",scope) => args.Evaluate<SNumber>(scope).Aggregate((a,b) => a * b)) .BuildIn("/",scope) => { var numbers = args.Evaluate<SNumber>(scope).ToArray(); Int64 firstValue = numbers[0]; return firstValue / numbers.Skip(1).Aggregate((a,b) => a * b); }) .BuildIn("%",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",scope) => { (args.Length > 0).OrThrows(); return !args.Any(arg => !(SBool)arg.Evaluate(scope)); }) .BuildIn("or",scope) => { (args.Length > 0).OrThrows(); return args.Any(arg => (SBool)arg.Evaluate(scope)); }) .BuildIn("not",scope) => { (args.Length == 1).OrThrows(); return args[0].Evaluate(scope); }) 比较操作iScheme 的比较操作包括 = < > >= <= ,需要注意下面几点:
.BuildIn("=",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("=",scope) => args.ChainRelation(scope,(s1,s2) => (Int64)s1 == (Int64)s2)) .BuildIn(">",s2) => s1 > s2)) .BuildIn("<",s2) => s1 < s2)) .BuildIn(">=",s2) => s1 >= s2)) .BuildIn("<=",s2) => s1 <= s2)) 注意 = 操作的实现里面有 Int64 强制转型――因为我们没有重载 SNumber#Equals ,所以无法直接通过 == 来比较两个 SNumber 。 列表操作 iScheme 的列表操作包括 first , rest , empty? 和 append ,分别用来取列表的第一个元素,除第一个以外的部分,判断列表是否为空和拼接列表。 first 和 rest 操作如下: .BuildIn("first",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",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,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",scope) => args.RetrieveSList(scope,"first").First()) .BuildIn("rest",scope) => new SList(args.RetrieveSList(scope,"rest").Skip(1))) .BuildIn("append",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?","empty?").Count() == 0) 测试 iScheme 的内置操作完成之后,就可以测试下初步成果了。 首先添加基于控制台的分析/求值(Parse/Evaluation)循环: public static void KeepInterpretingInConsole(this SScope scope,Func<String,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("+",scope) => (args.Evaluate<SNumber>(scope).Sum(s => s))) // 省略若干内置函数 .BuildIn("empty?",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]; 处理 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,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,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("+",scope) => (args.Evaluate<SNumber>(scope).Sum(s => s))) // Other build .BuildIn("empty?",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 的两篇文章:
几种简单实用的语法分析技术:
(编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |