特集記事

L2Lisp in Ruby

RubyによるモダンなLispの小さな実装

更新日: 2011/03/18
公開日: 2007/07/23

ポスト

Readerクラス

　式の読込みには、一般に先読みした字句の保持など状態の管理が必要です。最低限、関数とグローバル変数の組み合わせで実現することができますが、クラスを使えば両者をうまくまとめることができます。そこでReaderクラスを設けます。

　クラスの利用が唯一無二の方法というわけではありません。LispやPascalのように入れ子の関数が使えるならば、外側の関数のローカル変数を、入れ子の関数からグローバル変数のように使うことができます。ただし、Rubyではクラスの利用だけが唯一実際的な解です。

　外部から呼び出されるReaderインスタンスのメソッドはreadです。readは_read_tokenで先読みトークンを用意してから_parse_expressionで1個のLisp式を読み込んで戻り値とします。

　_read_tokenは読み込んだトークンをインスタンス変数@tokenにセットします。このとき、括弧やドットも便宜上シンボルとして扱います。整数はRubyのInteger関数で文字列を変換して取得します。浮動小数点数も同じように取得します。

　_read_tokenはテキスト行を@lineに読んだ後すぐに正規表現で分割し、@bufに格納しますから、本来の処理だけならば@lineを_read_tokenのローカル変数にすることもできます。インスンタンス変数にしているのは、構文誤り発生の際、元のテキスト行を例外情報に含めるためです。

Readerクラス

LPAREN = :"("; RPAREN = :")"; DOT = :"."; QUOTE = :"'"; EOF = :"#<eof>"

class Reader
  def initialize(rf)
    @rf = rf                  # 入力ファイル: IO
    @buf = []                 # 入力行から得たトークンの並び
    @line = nil               # 入力行: Stringまたはnil
  end

  def read
    begin
      _read_token
      return _parse_expression
    rescue SyntaxError => ex
      @buf.clear    # その行の残りのトークンを捨てて次回の回復を図る
      raise EvalError, 'SyntaxError: %s -- %d: %s' % 
        [ex, @rf.lineno, @line.inspect]
    end
  end

  def _parse_expression
    case @token
    when DOT, RPAREN
      raise SyntaxError, 'unexpected: %s' % @token
    when LPAREN
      _read_token
      return _parse_list_body
    when QUOTE
      _read_token
      return Cell.new(:quote, Cell.new(_parse_expression, nil))
    else
      return @token
    end
  end

  def _parse_list_body
    case @token
    …
    end
  end

  def _read_token
    while @buf.empty?
      @line = @rf.gets
      if @line.nil?
        @token = EOF
        @rf.close
        return
      end
      @line.chomp.scan(TOKEN_PAT) do |s,| @buf.push(s) unless s.nil? end
    end
    case t = @buf.shift
    when '(', ')', '.', '\'' then @token = t.to_sym
    when 'nil' then @token = nil
    when /\A\".*\"\z/ then @token = t[1..-2]
    else
      begin @token = Integer(t)
      rescue ArgumentError
        …
      end
    end
  end
  TOKEN_PAT = /\s+|;.*$|(".*?"|[^()' ]+|.)/
end # Reader

Interpクラス 1

　LispインタープリタそのものはInterpクラスで実装します。前述のようにInterpはインスタンス変数として@symbolを持ちます。インスタンス変数にはほかにLispのread関数のための@readerと環境リスト@environがあります。initializeメソッドはインスタンス変数を設定した後、初期化Lispスクリプトを格納する文字列PRELUDEをrunメソッドで実行してlistやifなど派生的な関数やマクロを定義します。

Interpクラス概観

class Interp
  attr :symbol                  # シンボルからその大域値への写像

  def initialize
    @reader = Reader.new(STDIN)
    @environ = nil
    @symbol = {}
    …
    @symbol[:car] = proc {|x| (x.nil?) ? nil : x.car}
    …
    @symbol[:prin1] = proc {|x| print(LL.str(x, true)); x}
    …
    @symbol[:read] = proc {@reader.read}
    …
    run(PRELUDE)
  end

  def eval(x, can_lose_current_env=false) … end
  def eval_cond_body(body) … end
  def eval_setq_body(body) … end
  def get_args(list, flag) … end
  def apply_lambda(j, args, can_lose_original_env) … end
  def compile_lambda(kdr, is_lambda) … end
  …
  def eval_catch_body(j) … end
  def eval_unwind_protect_body(j) … end

  def run(rf, interactive=(rf==STDIN))
    rf = StringIO.new(rf) if String === rf
    rr = Reader.new(rf)
    result = nil
    loop {
      print '> ' if interactive
      begin
        x = rr.read
        if x == EOF
          printf "Goodbye\n" if interactive
          return result
        end
        result = eval(x, false)
        puts LL.str(result) if interactive
      rescue EvalError => ex
        if interactive then print ex else raise end
      end
    }
  end
end # Interp

evalメソッドの概要

　上記のrunメソッドの定義から分かるように、Reader#readで読み込んだLisp式をeval（evaluateの意）で評価することによってLispプログラムの実行が行われます。evalメソッドの概要を示します。

MAX_EXC_TRACES = 10           # 例外発生時の評価トレースの記録段数
UNWIND_PROTECT = :"unwind-protect"

def eval(x, can_lose_current_env=false)
  begin
    loop {
      case x
      when Symbol then return @symbol.fetch(x, x)
      when Cell
        case x.car
        when :quote then return x.cdr.car
        …
        when :cond
          x, cont = eval_cond_body(x.cdr)
          return x unless cont
        when :setq then return eval_setq_body(x.cdr)
        …
        when :catch then return eval_catch_body(x.cdr)
        when UNWIND_PROTECT then return eval_unwind_protect_body(x.cdr)
        else
          case kar = x.car
          when Symbol then kar = @symbol.fetch(kar, kar)
          when Cell …
          end
          case kar
          when Cell …
          when Proc
            args = get_args(x.cdr, true)
            begin
              return kar.call(*args)
            rescue EvalError
              raise
            rescue => ex
              raise EvalError, '%s: %s -- %s %s' % 
                [ex.class, ex, kar.inspect, args.inspect]
            end
          else raise EvalError.new('not applicable atom', kar)
          end
        end
      else return x
      end
    }
  rescue EvalError => ex
    ex.trace << LL.str(x) if ex.trace.length < MAX_EXC_TRACES
    raise
  end
end

　シンボルの大域変数値は@symbol.fetch(x, x)で取り出します。L2Lispは記号計算の便宜のためシンボルの初期値を自分自身だとしていますから、xが@symbolに未登録のとき、fetchの第2引数によってx自身を返します。

未定義シンボルは自分自身を値とする

> nanja-monja
nanja-monja
>

　未定義シンボルをエラーにするには、シンボルが@symbolに未登録のときEvalError例外を発生するようにします。実験してみてください。

　特殊形式quoteならば式xの第2要素x.cdr.carをそのまま返します。

> (quote (1 2 3)
(1 2 3)
>

　特殊形式cond、setq、catch、unwind-protectについては、それぞれ専用のメソッドを呼び出します。ただし、条件式condについては単純に呼び出すのではなくx, cont = eval_cond_body(x.cdr); return x unless contとします。これは条件式の末尾の式に対して末尾呼出しの最適化を行うためです。末尾の式については、eval_cond_bodyで（evalを再帰的に呼び出して）評価することはしません。評価前の式とtrueを返します。evalメソッドは大きくloopで囲まれていますから、今度はxに代入された評価前の式が評価されます。

eval_cond_body は末尾の式をそのまま返す

while Cell === (d = clause.cdr)
  eval(clause.car, false)
  clause = d
end
d.nil? or raise ProperListExpected, d
return clause.car, true # 末尾呼出し ⇒ 戻った先で評価する

　組込み関数の関数適用は、@symbolからProcオブジェクトをkarに取り出した後、args = get_args(x.cdr, true)で引数を評価してから、return kar.call(*args)で行います。get_argsの定義を下記に示します。

get_argsメソッド

# リストで与えられた引数並びを（flagが真なら評価して）Arrayにする
def get_args(list, flag) 
  args = []        # ここは高頻度で呼ばれるからベタなwhileを使う
  while Cell === list
    x = list.car
    args << (flag ? eval(x, false) : x)
    list = list.cdr
  end
  list.nil? or raise ProperListExpected, list
  return args
end

　Cellクラスのイテレータを利用すれば、get_argsメソッドをもっと簡潔に記述できます。ただし、ここは高頻度で呼ばれる箇所ですから、そうすると（条件にもよりますが）インタープリタの速度がおよそ2割程度落ちます。どのような記述でどの程度影響があるか是非、実験してみてください。

次のページ
Interpクラス 2