没写过 Scheme 解释器的人生是不完整的

如题！ 下面的 scheme 解释器用了本人新造的一个解析器生成器： rsec。

如何装 rsec：

gem install rsec -s http://rubygems.org

系统需求 Ruby 1.9
其中用了大量模式匹配等新特性，没法兼容 Ruby 1.8 了 = .=

rsec 的详细用法可参考：
http://hllvm.group.iteye.com/group/topic/17817


上代码之前先对下面这个浓缩版 Scheme 作一些说明。

语法说明：

scheme 程序是由表（list）组成的，表的元素为 cell，cell 可以是表。
每个表可能有不同的语义，但语法就这么简单，可以直接转化为 AST。

Scheme#initialize 方法新建了一个 parser，将源代码文本解析成大表套小表的树形结构，然后递归调用 eval 方法（树遍历解释）产生程序运行的结果。

语义说明：

define： 定义一个量，这个量可以是整数，也可以是布尔值（#t 或者 #f），还可以是 lambda
如下面分别定义了 a = 12 和 plus4 = \x -> x+4

(define a 12)
(define (plus4 x) (+ x 4))

lambda： 定义一个 lambda 表达式。每个 lambda 表达式引入一个局部作用域，局部作用域中定义的量在外面不可见。下面代码中用一个哈希表（见 Bind 类）表示一个层级的局部作用域，其 parent 属性为上一层作用域。

if： 条件跳转语句。用法为

(if cond true-clause false-clause)

display： 显示语句。用法为

(display something)

下面是完整代码：

# coding: utf-8
require "rsec"

class Scheme
  include Rsec::Helpers

  # 语法部分，只支持布尔值和整数值
  def initialize
    bra     = /\(\s*/.r.skip
    ket     = /\s*\)/.r.skip
    boolean = /\#[tf]/.    r.map {|n| ValueNode[n=='#t'] }
    integer = /0|[1-9]\d*/.r.map {|n| ValueNode[n.to_i]  }
    spacee  = /\s*/.r.skip
    id      = /[^\s\(\)\[\]]+/.r.on {|n|
                def n.eval bind, *xs
                  bind[self]
                end
              }
    atom    = boolean | integer | id
    list    = nil # declare for lazy
    cell    = atom | lazy{list}
    list    = (   bra >> cell.join_(spacee) << ket   ).map {|n| ListNode[*n] }
    program = (spacee >> cell.join_(spacee) << spacee).map {|n| ListNode[*n] }
    @parser = program.eof
  end

  # 运行解释器     
  def run source
    # 解析结果（如果 pp 它，可以看到一个 AST）
    res = @parser.parse! source

    # 运行程序
    res.eval Runtime.new
  end
  
  # 值结点
  ValueNode = Struct.new :val
  class ValueNode
    def eval *xs
      val
    end
    def pretty_print q
      q.text "<#{val}>"
    end
  end
  
  # (表 结 点)
  class ListNode < Array
    def eval bind
      head, *tail = self
      case head
      when String
        pr = bind[head]
        pr.is_a?(Proc) ? pr[bind, tail] : pr
      when ListNode
        map{|n| n.eval bind }.last
      end
    end
  end
  
  # 作(用(域))
  class Bind < Hash
    def initialize parent = {}
      @parent = parent
    end
    
    def [] key
      super(key) || @parent[key]
    end
    
    # define a function
    def define id, &p
      self[id] = proc do |bind, xs|
        p[* xs.map{|x| x.eval bind }]
      end
    end
  end

  # 运行时 -- 顶级作用域
  class Runtime < Bind
    def initialize
      super()
      
      # 语法： 声明一个局部量
      self['define'] = proc do |bind, (param, body)|
        case param
        # (define (name plist[0]) body)
        when ListNode
          func, *xs = param
          self[func] = self['lambda'][bind, [xs, body]]
        # (define param body)
        when String
          self[param] = body.eval bind
        end
      end
      
      # 语法： 声明一个 lambda 表达式
      # (lambda (xs[0] xs[1]) body)
      self['lambda'] = proc do |bind_def, (xs, body)|
        xs = [xs] if xs.is_a?(String)
        new_bind = Bind.new bind_def
        # (some vs[0] vs[1])
        proc do |bind_call, vs|
          vs = vs.map{|v| v.eval bind_call}
          body.eval new_bind.merge Hash[xs.zip vs]
        end
      end
      
      # 语法： 条件判断 （注意这不是一般函数，因为它是 lazy 求值的）
      self['if'] = proc do |bind, (p, left, right)|
        p.eval(bind) ? left.eval(bind) : right.eval(bind)
      end
      
      # 一些杂碎的基本函数
      %w|+ - * / ** %|.each do |s|
        define s, &s.to_sym
      end

      define '=', &:==
      
      # 预定义一个 display 来显示结果
      define 'display' do |x|
        puts x
      end
    end
  end
end

s = Scheme.new
s.run File.read ARGV[0]

用来测试的 hello.scm 如下

(define (fact x)
  (if (= x 0)
      1
      (* x (fact (- x 1)))))
 
(display (fact 6))

>>= 运行 =<<

$ ruby scheme.rb hello.scm
720

以上代码用意是显示 rsec 的用法，并不是彻底完整的 scheme 解释器。
当然不支持其它的值类型，macro 等东西 ……

附链接： Writing a scheme in 15 minutes, treetop 版本
http://blog.jcoglan.com/2009/05/19/talk-writing-a-language-in-15-minutes/

我的人生何时才能完整....

不明白.   

楼主标题党~

在看clojure的实现，希望我的人生能够完整

谢谢楼主分享

又见半个btd。。。。。

还有人给俩新手贴?

太不像话了.

-_-!!!,没看懂，给个精华吧.-_-!!

学习了。以前试着做过lisp解释器（自己的方言），结果被我做成了过程式语言。一直不知道lambda怎么实现。

另外，这样实现lambda，如果lambda嵌套的话，会不会导致闭包（这里的Bind和Runtime）的符号表大小以O(n**2)的的数量级膨胀？

还有let-binding的实现呢？比如
[code='lisp']
(let (a 10) (+ a 2)) ; 值应该是12


这也是个需要考虑膨胀的问题。