综上所述，求值代码如下
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 的尾递归调用。 处理函数调用中的尾递归调用。Alex Stepanov 曾在 Elements of Programming 中介绍了一种将严格尾递归调用（Strict tail-recursive call）转化为迭代的方法，细节恕不赘述，以阶乘为例：
// Recursive factorial.
int fact (int n) {
if (n == 1)
return result;
return n * fact(n - 1);
}
// First tranform to tail recursive version.
int fact (int n, int result) {
if (n == 1)
return result;
else {
result *= n;
n -= 1;
return fact(n, result);// This is a strict tail-recursive call which can be omitted
}
}
// Then transform to iterative version.
int fact (int n, int result) {
while (true) {
if (n == 1)
return result;
else {
result *= n;
n -= 1;
}
}
}
应用这种方法到 SExpression#Evaluate ，得到转换后的版本：
public SObject Evaluate(SScope scope) {
SExpression current = this;
while (true) {
if (current.Children.Count == 0) {
Int64 number;
if (Int64.TryParse(current.Value, out number)) {
return number;
} else {
return scope.Find(current.Value);
}
} else {
SExpression first = current.Children[0];
if (first.Value == "if") {
SBool condition = (SBool)(current.Children[1].Evaluate(scope));
current = condition ? current.Children[2] : current.Children[3];
} else if (first.Value == "def") {
return scope.Define(current.Children[1].Value, current.Children[2].Evaluate(new SScope(scope)));
} else if (first.Value == "begin") {
SObject result = null;
foreach (SExpression statement in current.Children.Skip(1)) {
result = statement.Evaluate(scope);
}
return result;
} else if (first.Value == "func") {
SExpression body = current.Children[2];
String[] parameters = current.Children[1].Children.Select(exp => exp.Value).ToArray();
SScope newScope = new SScope(scope);
return new SFunction(body, parameters, newScope);
} else if (first.Value == "list") {
return new SList(current.Children.Skip(1).Select(exp => exp.Evaluate(scope)));
} else if (SScope.BuiltinFunctions.ContainsKey(first.Value)) {
var arguments = current.Children.Skip(1).ToArray();
return SScope.BuiltinFunctions[first.Value](arguments, scope);
} else {
SFunction function = first.Value == "(" ? (SFunction)first.Evaluate(scope) : (SFunction)scope.Find(first.Value);
var arguments = current.Children.Skip(1).Select(s => s.Evaluate(scope)).ToArray();
SFunction newFunction = function.Update(arguments);
if (newFunction.IsPartial) {
return newFunction.Evaluate();
} else {
current = newFunction.Body;
scope = newFunction.Scope;
}
}
}
}
}
