Write a Scheme Interpreter in Ruby(2): THE Interpreter

December 16, 2007 – 1:11 am

leaf.gif上一篇文章中我们实现了对 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-bindingsymbol ,并引用到它自己,这样就可以在 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 来说,正好,直接返回这个未求值的参数。而 conscarcdr 则需要先对参数求值,它们的实现基本上也是不言自明的了。

另外两个总要的过程是 defineset! 。其实它们的工作在 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 代码竟然只有两行——仍然是啥都没干,又推卸责任了!不过先别发火,我保证下一次绝对是最终代码了,不过在这之前,我们还是先来看看 CompoundProcedurecall 方法的行为。

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 ...

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

    # ... 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 。 :)

Post a Comment