SICP 読書ノート#44 - RubyでSchemeインタプリタをつくろう(3)

久しぶりの更新。行ったり来たり試行錯誤だけど毎日少しづつ進めてます…

式の表現

引き続きSchemeインタプリタの実装。今回は式の評価処理について。

self-evaluating items (自己評価式)

数か文字列の時にtrueを返す。number?()とstring?()は後で実装。

  def eval(exp, env)
    if self_evaluating?(exp)
      exp
    elsif
    #...
  end
      
  def self_evaluating?(exp)
    if number?(exp)
      true
    elsif string?(exp)
      true
    else
      false
    end
  end

variables (変数)

変数はシンボルで表す。symbol?()も後で実装。

  def eval(exp, env)
    # ...
    elsif variable?(exp)
      lookup_variable_value(exp, env)
    elsif
    # ...
  end

  def variable?(exp)
    symbol?(exp)
  end

環境から変数を探し出すと思われるlookup_variable_value()はここでは登場せず。

quotations (クォート式)

クォートは式が:quoteというタグを持つと定義する。

  def eval(exp, env)
    # ...
    elsif quoted?(exp)
      text_of_quotation(exp)
    elsif
    # ...
  end

  def quoted?(exp)
    tagged_list?(exp, :quote)
  end

  def text_of_quotation(exp)
    cadr(exp)
  end

式のタグチェックは共通でtagged_list?()を使う。

def tagged_list?(exp, tag)
  pair?(exp) && car(exp) == tag
end

assignments (代入)

式から変数と値を取り出すアクセサを用意。

  def eval(exp, env)
    # ...
    elsif assignment?(exp)
      eval_assignment(exp, env)
    elsif
    # ...
  end
    
  def assignment?(exp)
    tagged_list?(exp, :set!)
  end

  def assignment_variable(exp)
    cadr(exp)
  end

  def assignment_value(exp)
    caddr(exp)
  end

前回登場したeval_assignment()とこれで繋がる。

  def eval_assignment(exp, env)
    var = assignment_variable(exp)
    value = eval(assignment_value(exp), env)
    set_variable_value!(var, value, env)
    :ok
  end

definitions (定義)

• 新たに変数を束縛する場合
• 引数付きの手続きを定義する場合

があるのでそれぞれに対応する。

  def eval(exp, env)
    # ...
    elsif definition?(exp)
      eval_definition(exp, env)
    elsif
    # ...
  end
    
  def definition?(exp)
    tagged_list?(exp, :define)
  end

  def definition_variable(exp)
    if symbol?(cadr(exp)) # 変数の束縛
      cadr(exp)
    else                  # 手続きの定義
      caddr(exp)
    end
  end

  def definition_value(exp)
    if symbol?(cadr(exp)) # 変数の束縛
      caddr(exp)
    else                  # 手続きの定義
      params = cdadr(exp)
      body = cddr(exp)
      make_lambda(params, body)
    end
  end

make_lambda()がアツい！

これも前回登場したeval_definition()と繋がる。

  def eval_definition(exp, env)
    var = definition_variable(exp)
    value = _eval(definition_value(exp), env)
    define_variable!(var, value, env)
    :ok
  end

lambda expressions (lambda式)

lambda式は仮パラメタ(params)と本体(body)を組み合わせるだけ。

  def eval(exp, env)
    # ...
    elsif lambda?(exp)
      params = lambda_parameters(exp)
      body = lambda_body(exp)
      make_procedure(params, body, env)
    elsif
    # ...
  end

  def lambda?(exp)
    tagged_list?(exp, :lambda)
  end

  def lambda_parameters(exp)
    cadr(exp)
  end

  def lambda_body(exp)
    cddr(exp)
  end

  def make_lambda(params, body)
    cons(:lambda, cons(params, body))
  end

肝心のmake_procedure()はまだ出てこない。

conditionals (条件式)

ここでの本質じゃないけどcadddrとcdddrの実装が面倒くさそう…

  def eval(exp, env)
    # ...
    elsif if?(exp)
      eval_if(exp, env)
    elsif
    # ...
  end

  def if?(exp)
    tagged_list?(exp, :if)
  end

  def if_predicate(exp)
    cadr(exp)
  end

  def if_consequent(exp)
    caddr(exp)
  end

  def if_alternative(exp)
    unless null?(cdddr(exp))
      cadddr(exp)
    else
      :false
    end
  end

  def make_if(predicate, consequent, alternative)
    list(:if, predicate, consequent, alternative)
  end

begin

beginは一連の式をひとつにまとめる。評価では前回登場したeval_sequence()を使う。

  def eval(exp, env)
    # ...
    elsif begin?(exp)
      exps = begin_actions(exp)
      eval_sequence(exps, env)
    elsif
    # ...
  end

  def begin?(exp)
    tagged_list?(exp, :begin)
  end

  def begin_actions(exp)
    cdr(exp)
  end

begin式を生成する手続き。まだ使う場面が出てきていないのでよくわからない。

  def last_exp?(seq)
    null?(cdr(seq))
  end

  def first_exp(seq)
    car(seq)
  end

  def rest_exps(seq)
    cdr(seq)
  end

  def sequence_to_exp(seq)
    if null?(seq)
      seq
    elsif last_exp?(seq)
      first_exp(seq)
    else
      make_begin(seq)
    end
  end

  def make_begin(seq)
    cons(:begin, seq)
  end

procedure application (手続きの適用)

手続きのオペレータと被オペレータを定義。apply()の中身は次回に持ち越し。

  def eval(exp, env)
    # ...
    elsif application?(exp)
      procedure = eval(operator(exp), env)
      arguments = list_of_values(operands(exp), env)
      apply(procedure, arguments)
    else
    # ...
  end

  def application?(exp)
    pair?(exp)
  end

  def operator(exp)
    car(exp)
  end

  def operands(exp)
    cdr(exp)
  end

  def no_operands?(ops)
    null?(ops)
  end

  def first_operand(ops)
    car(ops)
  end

  def rest_operands(ops)
    cdr(ops)
  end

derived expressions (派生式)

condはifにより簡略することができる。この簡略された式をderived expressionsと呼ぶらしい。

まずeval()によるcond式の評価。cond_to_if()でif式に変換する。

  def eval(exp, env)
    # ...
    elsif cond?(exp)
      eval(cond_to_if(exp), env)
    elsif
    # ...
  end

次にcond_to_if()の実装。単純にcondの式を順次展開してmake_if()でif式へと組み替えていく。

  def cond?(exp)
    tagged_list?(exp, :cond)
  end

  def cond_clauses(exp)
    cdr(exp)
  end

  def cond_else_clause?(clause)
    eq?(cond_predicate(clause), :else)
  end

  def cond_predicate(clause)
    car(clause)
  end

  def cond_actions(clause)
    cdr(clause)
  end

  def cond_to_if(exp)
    expand_clauses(cond_clauses(exp))
  end

  def expand_clauses(clauses)
    if null?(clauses)
      :false                # no else clause
    else
      first = car(clauses)
      rest = cdr(clauses)
      if cond_else_clause?(first)
        if null?(rest)
          sequence_to_exp(cond_actions(first))
        else
          raise "else clauses isn't last: cond_to_if " + clauses.to_s
        end

        predicate = cond_predicate(first)
        consequent = sequence_to_exp(cond_actions(first))
        alternative = expand_clauses(rest)
        make_if(predicate, consequent, alternative)
      end
    end
  end

その他

Evaluatorクラスを新たに定義した。Baseはcons()などの基本手続きを集めたモジュール。

class Evaluator
  include Base

  def eval(exp, env)
    # ...
  end

  def apply(procedure, arguments)
    # ...
  end
end

こんな感じで実行できるはず。まだ全然動かないけどね。

> e = Evaluator.new()
> exp = list(:define, :x, 1)
> env = {}
> e.eval(exp, env)

ここから先は練習問題が続くので今日はここまで。次回はBaseの実装をやっていく。

---

※「SICP読書ノート」の目次はこちら