在上一篇文章中我们实现了对 scheme 代码的 parse 和 analyze 过程，并得到了一些可以直接 eval 的对象（String ，Symbol ，Number 和 Cons ），可是光凭这些并不足以让我们的解释器跑起来。这次我们要添加必要的代码，实现一个真正可运行的解释器。 在前面的代码中，我们已经实现了 scheme 中的几个基本对象的求值：作为 atom 的 String 、Symbol 和 Number 以及作为 list 的 Cons 都已具体实现了 eval 方法。事实上 atom 的求值已经不需要加什么其他代码了，但是 Cons 类却是耍了一个把戏，仔细看 Cons 类的 eval 方法：

    def eval(binding)
      func = @car.eval(binding)
      args = @cdr
      func.call(binding, args)
    end

其实把责任推脱给了 func 对象的 call 方法。那么 func 应该是一个什么对象呢？一个 scheme 解释器要能跑起来，至少需要一些内置的基本过程（primitive-procedures），并且要让用户能够自定义过程（compound-procedure）。要内置哪些基本过程？如何表示？它们的 call 方法如何工作？自定义过程的 call 方法又是如何表示和工作的？这些就是本文需要解决的问题了。 在着手构造 procedure 之前，让我们先来解决一个上次遗留下来的问题：binding 。所有的 eval 方法都接受一个 binding 参数，一个 binding 存储了一个上下文，说白了就是一张从 symbol 到值对应起来的表，对 symbol 求值的过程其实就是查表的过程：

  class Symbol
    def eval(binding)
      binding[self]
    end
  end

binding 的基本上就等价于一个 Hash 表了，稍微包装一下就可以了。我在每个 binding 构造的时候放入一个叫做 current-binding 的 symbol ，并引用到它自己，这样就可以在 scheme 程序中引用到“当前”的 binding 了：

  class Binding
    CURRENT = Symbol.new("current-binding")

    def initialize(parent=nil)
      @parent = parent
      @hash = Hash.new
      self[CURRENT] = self
    end
  end

一个 binding 通常还有一个 parent ，查找 symbol 的时候如果在当前 binding 中找不到，会递归地到 parent 中查找。而将一个 symbol 联系到某一个值的行为也有两种，一种会追溯到 parent （并且在没有 parent 的时候报错），一种直接在当前 binding 中建立对应关系。在 scheme 中就分别是 set! 和 define 的行为了：

  class Binding
    def [](symbol)
      @hash.fetch(symbol.name) do |name|
	@parent.nil? ? nil : @parent[symbol]
      end
    end
    def []=(symbol, value)
      @hash[symbol.name] = value
    end
    def assign(symbol, value)
      if @hash.has_key?(symbol.name)
        @hash[symbol.name] = value
      elsif ! @parent.nil?
        @parent.assign(symbol, value)
      else
        raise ArgumentError.new("Cannot assign undefined identifier #{symbol}")
      end
    end
  end

有了 binding ，再回来看我们的解释器，我们需要为解释器建立一个全局的（顶层的）binding ：

class SchemeInterpreter
  def initialize
    @binding = SchemeVM::Binding.new
    setup_default_bindings
  end
end

一个空的 binding 并不足以让一个 scheme 程序跑起来，我们还需要一些基本的东西，以构成一个基本的 scheme 执行环境。好在 scheme 是一门相当紧凑的语言，不需要初始化太多的东西，首先是一些常量：

  def setup_default_bindings
    b = @binding
    b[sym("nil")] = nil
    b[sym("#f")] = nil
    b[sym("#t")] = true
    b[sym("global-binding")] = @binding
    # to be continued ...

然后是那些 primitive-procedure 。我前面选择 call 作为调用 procedure 的方法也不是随便选择的，正好 Ruby 内置的 Proc 也有 call 方法，正好可以拿 Proc 来以“假”乱真了！ :)

    # ... continued
    b[sym("quote")] = lambda { |binding, arg| arg.car }
    b[sym("car")] = lambda { |binding, arg|
      arg.car.eval(binding).car
    }
    b[sym("cdr")] = lambda { |binding, arg|
      arg.car.eval(binding).cdr
    }
    b[sym("cons")] = lambda { |binding, arg|
      SchemeVM::Cons.new(arg.car.eval(binding),
                         arg.cadr.eval(binding))
    }
    # to be continued ...

注意这里传递过来的参数 arg 都是未求值的。对于 quote 来说，正好，直接返回这个未求值的参数。而 cons 、car 和 cdr 则需要先对参数求值，它们的实现基本上也是不言自明的了。 另外两个总要的过程是 define 和 set! 。其实它们的工作在 binding 中已经实现过了，只需要转发一下就可以了：

    # ... continued
    b[sym("set!")] = lambda { |binding, args|
      binding.assign(args.car, args.cadr.eval(binding))
    }
    b[sym("define")] = lambda { |binding, args|
      binding[args.car] = args.cadr.eval(binding)
    }
    # to be continued ...

接下来就是更令人期待的——用户自定义过程了（姑且称作 compound-procedure 吧，我是在 MIT 的教学视频中听到这个名词的，忘记是专门用于指代自定义的过程还是表示所有的过程的了 -,-bb）：

    # ... continued
    b[sym("lambda")] = lambda { |binding, args|
      SchemeVM::CompoundProcedure.new(binding, args.car, args.cdr)
    }
    # to be continued ...

又耍了个把戏，再次推卸责任！ :D 不过，在实现 CompoundProcedure 之前，让我们先回过头修改一下我们关于 define 的实现，至少要支持 scheme 里 (define (proc args) body) 这样的语法糖啊：

    # ... continued
    b[sym("define")] = lambda { |binding, args|
      if pair?(args.car)
	binding[args.caar] = SchemeVM::CompoundProcedure.new(binding, args.car.cdr, args.cdr)
      else
        binding[args.car] = args.cadr.eval(binding)
      end
    }
    # to be continued ...

接下来便是期待已久的 CompoundProcedure 的实现！

  class CompoundProcedure
    include SchemeVM::EvalHelper

    def initialize(context, arg_list, body)
      @context, @args, @body = context, arg_list, body
    end

    def call(binding, args)
      proc_binding = setup_binding(binding, args)
      eval_expressions(proc_binding, @body)
    end
  end

唉！我都不好意思了！ :p 代码竟然只有两行——仍然是啥都没干，又推卸责任了！不过先别发火，我保证下一次绝对是最终代码了，不过在这之前，我们还是先来看看 CompoundProcedure 的 call 方法的行为。 CompoundProcedure 首先需要新建一个 binding ，在这里把 parameter （形参）bind 到 argument （实参）上，然后在这个 binding 里执行函数体。上面代码里的两句话就是分别完成了这两件事。 需要注意的是这个新建的 binding 的 parent 是 CompoundProcedure 构造时候拿到的那个 binding （记为 b1） 而不是 call 方法传递过来的 binding （记为 b2）。就是说（忽略掉 argument 的话）CompoundProcedure 其实是在 b1 中求值的，这正是 scheme 引入的 lexical scope 。如果在 CompoundProcedure 中引用到了 b1 中的变量，就是 closure 了。 以前我也是对这些概念一知半解，现在却是清楚得不能再清楚了：lexical scope 和 dynamic scope 的区别其实就在于求值的时候是用 b1 还是 b2 。但是即使是 lexical scope 也并不代表 b2 没有作用：所有的参数值都是在 b2 中求得的。 好了，如果你也如我一样大彻大悟了，就让我们来看关于 CompoundProcedure 的“最终代码”吧：

  class CompoundProcedure
    def setup_binding(binding, args)
      b = Binding.new(@context)
      syms = @args
      vals = args.map { |val| val.eval(binding) }
      while pair?(syms)
	b[syms.car] = vals.car
	syms = syms.cdr
	vals = vals.cdr
      end
      b
    end
  end

  module EvalHelper
    def eval_expressions(binding, expressions)
      return expressions.eval(binding) if expressions == sym("nil")
      result = expressions.car.eval(binding)
      expressions = expressions.cdr
      while pair?(expressions)
	result = expressions.car.eval(binding)
	expressions = expressions.cdr
      end
      result
    end
  end

其实上面关于 CompoundProcedure 行为的内容搞清楚之后，真正的实现基本上就是体力活了，多少有些无聊吧？ :p 还是期望太高了，其实 CompoundProcedure 也不过如此了。 还有其他一些东西，比如 let ，其实这只是 lambda 的一个语法糖：

(let ((var val))
   body)

其实等价于：

((lambda (var)
    body)
 val)

因此它的实现也就明了了：

    # ... continued
    b[sym("let")] = lambda { |binding, args|
      bindings = args.car
      body = args.cdr
      vars = bindings.map { |cons| cons.car }
      vals = bindings.map { |cons| cons.cadr }
      SchemeVM::CompoundProcedure.new(binding, vars, body).call(binding, vals)
    }
    # to be continued ...

接下来是 cond 和 if ，其实这两者是等价的，可以把其中一个做成另外一个的语法糖包装，不过我还是分别实现了它们，反正也不麻烦：

    # ... continued
    b[sym("cond")] = lambda { |binding, args|
      conds = args
      while pair?(conds)
        if conds.caar == sym("else") or conds.caar.eval(binding)
	  return conds.car.cadr.eval(binding)
        end
        conds = conds.cdr
      end
    }
    b[sym("if")] = lambda { |binding, args|
      cond = args.car
      args = args.cdr
      if cond.eval(binding)
        args.car.eval(binding)
      else
        args.cadr.eval(binding)
      end
    }
    # to be continued ...

实现了这么多的基本过程，按照 goncha 在我上一篇文章的评论中给的链接中的文件的描述的话，只需要再添加一个 atom? 和一个 eq? 就够了：

    # ... continued
    b[sym("atom?")] = lambda { |binding, arg|
      val = arg.car.eval(binding)
      val.instance_of? SchemeVM::String or
        val.instance_of? SchemeVM::Symbol or
        val.instance_of? SchemeVM::Number
    }
    b[sym("eq?")] = lambda { |binding, arg|
      val1 = arg.car.eval(binding)
      val2 = arg.cadr.eval(binding)
      val1 == val2
    }
    # to be continued ...

好了，到此为止了！再添加其他过程（例如算术运算或者 IO 操作），套路基本上都是这样了，也就不一一列举了。关键是，现在我们的 top-level binding 已经有相当多的内容了。让我们来为我们的解释器加上一个入口吧！

  def run(program)
    program.eval(@binding)
  end

看看效果吧！测试代码早就写好了（就不全部列出来了）：

  def test_lexical_binding
    src = "
    (begin
      (define proc
        (let ((i 10))
          (lambda (x)
	    (+ x i))))
      (let ((i 20))
        (proc 10)))
    "
    assert_equal 20, interpret(src).value
  end

到此为止，我们的 scheme interpreter 基本完成了！不过，与其说是 scheme interpreter ，还不如说是 scheme 的一个子集（或者变形）的解释器，因为我完全是按照我对 scheme 的理解来做的。作为一个玩具，我也不想去一字一句地读 r6rs 去做一个完全标准的解释器出来（那和玩具不同，应当是相当有难度的了）。 我会不断修改这个解释器，事实上，由于 parser 的原因，目前还无法比较高效地实现一个 REPL 出来，至少在明年学习编译原理的时候我会在回过来看看。总之，如果有有趣的东西，我还会继续写关于它的 Blog 。 :)