Rubyを理解するためにSchemeを作ってみました

2018-11-08 · 3217 文字 · 7 分くらいで読めます

Ruby

tamuraです。

Rubyを使う会社で働いているのですが、未だにRubyを理解したと言えない状況なので、 SICPに実装が載っているSchemeを作ってみました。

まずは

慣れているJavaで軽く実装してクラス構成などを決めました。（捨てることをあらかじめ予定しておけ。どうせいやでも捨てることになるんだから：人月の神話）

結論

学んだこと

文法はだいたい大丈夫そう
- superが親クラスの同じメソッドを実行というのにちょっとだけハマった（コードリーディング時）
- super.method() ってあったら親クラスのmethodを実行すると思っていたけど、親クラスの同じメソッドを実行して返ってきたオブジェクトのmethodを実行とわかった時に異文化コミュニケーションの必要性を感じた
RSpecを使ったテスト
binding.pry を使ったデバッグ
Abstractなクラスは作れない
- サブクラスで何かを強制することはできない（inheritedでチェックすればいけるかもしれないけど実行しないとわからない（JavaとかC++ならコンパイル時にチェックできる））
- → 規約で縛るしかない
コメント重要。どういうクラスが来て欲しいのか書いておかないと自分でも忘れる
内部イテレータと外部イテレータがあること

実装内容

https://github.com/tamurashingo/rscheme

いちおうカバレッヂは100%

実行はこんな感じ

クラス図

シーケンス図

AtomとPair

LispはS式からできていて、S式はAtomかS式でできているのでまずはその基本的なオブジェクトを定義しました。 LObjというのはJavaではPairとAtomを共通的に扱うために必要な抽象クラスだったのですが、Rubyだと必要なメソッドがあれば同じクラスとして扱う(Duck Typing)というのがある(らしい)のであまり意味がないクラスでした。

module Rscheme
  class Atom < LObj
  end
end

module Rscheme
  class Pair < LObj
  end
end

Lexer と Parser

Lispは構文があってないようなものなので、一瞬でできます。(Java版は瞬殺でした) Ruby版はちょっと手こずりました。

Lexer

module Rscheme
  class Lexer

    def initialize(s)
      @s = s
      @it = s.each_char
      @buf = nil
    end

    def lex
      # バッファに字句があればそれを返す

      # スペースとかタブとか改行とかそういう文字をスキップする

      # ここからLexerの主処理
      if ch == '('
        # ヒラキカッコを返す
        return lex_open_parenthesis ch
      elsif ch == ')'
        # トジカッコを返す
        return lex_close_parenthesis ch
      elsif ch == '\''
        # クオートを返す
        return lex_quote ch
      elsif ch == '"'
        # 文字列処理を行う
        return lex_string ch
      elsif ch == '-'
        # マイナス文字なのか、-10みたいな数字なのかを判別する
        return lex_minus ch
      elsif ch.match(/[0-9.]/)
        # 数字は数字で返す
        return lex_number ch
      else
        # それ以外はシンボル（変数名みたいなやつ）として扱う
        return lex_symbol ch
      end
    end

    # 文字列処理
    def lex_string(ch)
      # 基本的に " が出るまで読み込み続けて、最後に文字列として返す
      # 文字列中の改行も関係なし
    end

    # マイナス処理
    def lex_minus(ch)
      # 次の文字が数字かドットならマイナス数字
      c = @it.peek
      if c.match(/[0-9.]/)
        return lex_number(ch)
      else
      # マイナスのシンボル
        return [:symbol, '-']
      end
    end
  
    # 数値処理
    def lex_number(ch)
      # 連続した数字を数値として扱う
      # ただし、ドットのみの場合はドットとして返す
      return [:number, str]
    end

    # シンボル処理
    def lex_symbol(ch)
      # スペースとか改行とかタブとかカッコとか出るまで変数名として読み込み続ける
      return [:symbol, str]
    end
  end
end

loop do end をCでいうところのfor(;;){ }だと思っていたのですが実際は関数で、その中で発生したStopIterationはもみ消されていたので、意図したエラーが発生せずにかなり詰まりました。今度からはマニュアルをちゃんと確認します。

Parser

LispはParserもあって無いようなものです。 Lexerから受け取った値がAtomならAtomとして、ヒラキカッコならトジカッコまでをリストとして読み込んであげるだけです。

module Rscheme
  class Parser

    def initialize(sexp)
      @lexer = Lexer.new sexp
    end

    def parse
      parse_base
    end

    def parse_base
      type = @lexer.lex
      if type[0] == :open_parenthesis
        # ヒラキカッコならカッコの処理を行う
        parse_list
      elsif type[0] == :string
        Atom.of_string type[1]
      elsif type[0] == :symbol
        Atom.of_symbol type[1]
      elsif type[0] == :number
        if type[1].include? '.'
          Atom.of_value type[1].to_f
        else
          Atom.of_value type[1].to_i
        end
      elsif type[0] == :quote
        parse_quote
      else
        raise ParseException, 'parse error:' + type[1]
      end
    end

    def parse_list
      obj = Pair.of_pair Atom.of_nil, Atom.of_nil
      type = @lexer.lex
      loop do
        if type[0] == :close_parenthesis
          return obj
        else
          @lexer.push type
          obj2 = parse_base
          obj = ListUtil.append obj, Pair.of_pair(obj2, Atom.of_nil)
          type = @lexer.lex
        end
      end
    end

    def parse_quote
      Pair.of_pair Atom.of_symbol("QUOTE"), Pair.of_pair(parse_base, Atom.of_nil)
    end
  end
end

EvalとApply

Eval

Evalはこれだけです。

module Rscheme
  class Eval
    def self.eval(exp, env)
      # 文字列とか数値とか
      if self_evaluating? exp
        exp
      # シンボル（変数名）
      elsif variable? exp
        env.lookup exp.value
      # クオートされた式（は (quote 3.14) となっているので cadr を返してあげる）
      elsif quoted? exp
        exp.cdr.car
      # 変数設定
      elsif assignment? exp
        Apply.assignment exp, env
      # 関数定義
      elsif definition? exp
        Apply.definition exp, env
      # if式
      elsif if? exp
        Apply.if exp, env
      # lambda式は現在のclosureを作ってそれを保持っておく
      elsif lambda? exp
        Apply.make_procedure exp, env
      # beginは順番に評価するだけ
      elsif begin? exp
        Apply.sequence exp.cdr, env
      # cond式はifに変換してそれを評価
      elsif cond? exp
        Eval.eval CondConverter.cond_to_if(exp), env
      # (x) みたいなものは関数とみなして実行する
      elsif application? exp
        Apply.apply Eval.eval(operator(exp), env),
                    list_of_values(operands(exp), env)
      else
        raise RschemeException, "unknown expression:#{exp.type}:#{exp.value}"
      end
    end
  end
end

Environment

変数とかを保持しておく環境が必要です。変数名とその値を格納するハッシュを持ったクラスです。変数を見つける場合は、まずは自分の環境、なかったら親の環境、それでもなかったら爺さん婆さんの環境、と探しに行きます。簡単です。

module Rscheme
  class Environment
    attr_reader :variables

    def initialize(parent)
      @parent = parent
      @variables = Hash.new
    end

    def set_variable(symbol, value)
      env = lookup_environment symbol
      if env
        env.store symbol, value
      else
        store symbol, value
      end
    end

    def lookup_environment(symbol)
      if @variables.has_key? symbol
        self
      else
        if @parent
          @parent.lookup_environment symbol
        else
          nil
        end
      end
    end

    def store(symbol, value)
      @variables.store symbol, value
    end

    # 変数名
    #
    # @param symbol [string] 
    def lookup(symbol)
      if @variables.has_key? symbol
        @variables[symbol]
      else
        if @parent
          @parent.lookup symbol
        else
          raise RschemeException, 'not found variable:' + symbol
        end
      end
    end

    # 現在の環境をもとに新しい環境を作成し、引数とその値を環境にセットする
    #
    # @param vars [pair] 引数のリスト(変数名のリスト)
    # @param vals [pair] 値のリスト
    # @returns 現在の環境を拡張し、引数と値がセットされた環境
    def extend_environment(vars, vals)
      env = Environment.new self
      vars_it = SchemeListIterator.new vars
      vals_it = SchemeListIterator.new vals

      while vars_it.has_next? && vals_it.has_next?
        var = vars_it.next.value
        val = vals_it.next
        env.store var, val
      end

      env
    end
  end
end

SchemeListIteratorはLispのListからiteratorを作成する便利なやつです。

Apply

Applyはちょっと長いので抜粋

変数の設定

    def self.assignment(exp, env)
      symbol = Assignment.variable exp
      value = Assignment.value exp, env

      env.set_variable symbol, value

      value
    end

(set! x 3) から x と 3 を取り出して環境に突っ込むだけです。もちろん (set! y (+ 1 2)) とかあったらちゃんと(+ 1 2)を評価した結果を突っ込みます。

関数の設定

    def self.definition(exp, env)
      symbol = Definition.variable exp
      value = Eval.eval (Definition.value exp), env

      env.set_variable symbol, value

      Atom.of_string "OK!"
    end

関数も基本構成は同じです。環境に対してPROCECUREを設定しています。

分岐

    def self.if(exp, env)
      if !Eval.eval(If.predicate(exp), env).nil?
        Eval.eval If.consequent(exp), env
      else
        Eval.eval If.alternative(exp), env
      end
    end

predicateが正ならconsequentを、それ以外ならalternativeを評価します。

primitiveな関数

    def self.apply(procedure, arguments)
      if Apply.primitive_procedure? procedure
        Apply.apply_primitive_procedure procedure, arguments
        ....

      def self.apply_primitive_procedure(procedure, arguments)
        cmd = procedure.cdr.car.value
        cmd.operate arguments
      end

初期の環境にprimitiveという印をつけているので、procedureを環境から引っ張って来て、primitiveという印が付いているならprimitiveとして実行します。

primitiveな関数はこんな感じで実装しています。

module Rscheme
  class PlusCommand
    def operate(exp)
      Atom.of_value exp.car.value + exp.cdr.car.value
    end
  end
end

で、こうやって初期の環境に突っ込んでいます。

env = Environment.create_global
env.set_variable "+", ListUtil.list(Atom.of_symbol("PRIMITIVE"), Atom.of_other(PlusCommand.new))

合成関数

(define (add2 x) (+ x 2)) みたいなやつを合成関数と読んでます。 defineで定義した関数はこんな感じで現在の環境にセットされます。

(define (add2 x) (+ x 2))
=> ; いったんlambda式に変換する
(define add2 (lambda (x) (+x 2)))
=> ; lambda式を評価する
(define add2 ("PROCEDURE" (X) (+ X 2) (その時点のEnvironment)))
=> ; 環境にセットする
(set! add2 ("PROCEDURE" (X) (+ X 2) (その時点のenvironment)))

で、実際に合成関数かどうかをチェックしている部分を確認します。

    def self.apply(procedure, arguments)
      if Apply.primitive_procedure? procedure
        Apply.apply_primitive_procedure procedure, arguments
      elsif Apply.compound_procedure? procedure
        sequence Apply.procedure_body(procedure), Apply.procedure_environment(procedure).extend_environment(Apply.procedure_parameters(procedure), arguments)
      end
    end

compound_procedure?はこんな感じで、リストの先頭が ‘PROCEDURE’ なら合成関数と判別します。

      def self.compound_procedure?(procedure)
        ListUtil.tagged_list(procedure, 'PROCEDURE')
      end

実行部分ですが、２つの部分に別れてます。

sequence Apply.procedure_body(procedure), Apply.procedure_environment(procedure).extend_environment(Apply.procedure_parameters(procedure), arguments)

Apply.procedure_bodyはprocedureから関数の本体を取得します。今回の例でいうと(+ X 2)の部分です。

Apply.procedure_environment(procedure).extend_environment(Apply.procedure_parameters(procedure), arguments)

は

Apply.procedure_environment(procedure)

でまずlambda式を評価した時の環境を取得し、 #extend_environment でその環境を元にした新しい環境を作成します。

Apply.procedure_parameters(procedure), arguments

引数に与えるこれらの値は (add2 3) の場合は、

(x) (3)

となります。で、この引数とそれに対応する値を拡張した環境にセットします。で、この環境を使って (+ X 2) を実行するので、 X が 3 となって(+ 2 3)が評価されることになります。（なのでこの実装はとても効率がわるい)

こういう環境の連鎖を持っているので、引数の値を変更しても呼び出し元の環境には影響を与えない、という当たり前のことが簡単に実装できます（効率悪いですが）