読者です 読者をやめる 読者になる 読者になる

@uents blog

Code wins arguments.

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

いよいよ4章。

metacircular (超循環評価器) というものがいきなり登場しました。

被実装言語と実装言語が同じインタプリタのことをそう呼ぶらしく、冒頭からSchemeで実装したSchemeインタプリタが例として登場します。

ただ id:higepon さんが指摘されていますように、

どうも読んでいるだけでは解決しないモヤモヤがあって、それは被実装言語と実装言語の境界に関する問題のように思えてきました。metacircularだと、どこまでが被実装言語の機能で、どこからが実装言語の機能なのか分からなくなってきてしまうのです。

という点もありますし、SICPを読む前に以下のページでRubyによるSchemeインタプリタの実装をかじっていたので、

ここはRubyで挑戦することにしました。本当は普段使っているJavaScriptやCの方が得意なんですが、「1年に1つ新しい言語を覚える」という達人の教えもあるので、あえてRubyで実装することにします。

達人プログラマー―システム開発の職人から名匠への道

達人プログラマー―システム開発の職人から名匠への道

  • 作者: アンドリューハント,デビッドトーマス,Andrew Hunt,David Thomas,村上雅章
  • 出版社/メーカー: ピアソンエデュケーション
  • 発売日: 2000/11
  • メディア: 単行本
  • 購入: 42人 クリック: 1,099回
  • この商品を含むブログ (349件) を見る

評価器の中核

評価器の評価プロセスはevalとapplyの相互作用で記述できる。

  • eval : 式(expression)を評価し(evaluate)、値や手続きおよびその引数を取得
  • apply : 手続きと引数を適用

まずはテキストのevalRubyで実装し直す。ほぼ写経ですけど。

def _eval(exp, env)
  if self_evaluating?(exp)
    exp
  elsif variable?(exp)
    lookup_variable_value(exp, env)
  elsif quoted?(exp)
    text_of_quotation(exp)
  elsif assignment?(exp)
    eval_assignment(exp, env)
  elsif definition?(exp)
    eval_definition(exp, env)
  elsif if?(exp)
    eval_if(exp, env)
  elsif lambda?(exp)
    params = lambda_parameters(exp)
    body = lambda_body(exp)
    make_procedure(params, body, env)
  elsif begin?(exp)
    exps = begin_actions(exp)
    eval_sequence(exps, env)
  elsif cond?(exp)
    exp_if = cond_to_if(exp)
    eval_if(exp_if, env)
  elsif application?(exp)
    procedure = _eval(operator(exp) env)
    arguments = list_of_values(operands(exp) env)
    _apply(procedure, arguments)
  else
    raise "eval: unknown expression type: " + exp
  end
end

特殊形式の式から順に確認しヒットすれば評価します。どれにもヒットしなければ手続きと引数を取り出しapplyで適用させます。

次にapplyを実装。

def _apply(procedure, arguments)
  if primitive_procedure?(procedure)
    apply_primitive_prodecure(procedure, arguments)
  elsif compound_procedure?(procedure)
    body = procedure_body(procedure)
    params = procedure_parameter(procedure)
    env = procedure_environment(procedure)
    eval_sequence(body, extend_environment(params, arguments, env))
  else
    raise "apply: unknown procedure type: " + procedure
  end
end

ここでprimitive_procedurecompound_procedureという見慣れないワードが出てきました。

  • primitive_procedureであれば、primitive_procedureとして適用
  • compound_procedureであれば、新しく拡張した環境に対し、手続きの本体bodyから式を取り出し順に評価する

evalからapply、applyからevalと循環しながら手続きが評価されていく様子がわかる。

あとprimitive_procedureに何があるのか気になる。

まだ全然動いていないけどワクワクしてきました!


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