lambdaの実装まで - みずぴー日記

mzp2005-12-14

前回のHaskellではうまく行かなかったので、こんどこそプログラムの道のりを書いてみよう。
お題は、LastEmpereへのlambda式の実装

速習:lambda式および仕様の把握

id:selvaggioも見ているだろうから、簡単に解説をしておく。
もちろん、実装するにあたって仕様を把握する意味もある。

lambda式とは、無名関数のこと。そして関数をまるでデータのように扱える。C言語で言うなら関数ポインタ、SMLで言うならfnで生成した関数。

((lambda (x) (+ x 1)) 3) => 4

(set! inc (lambda (x) (+ x 1))) => #undef
(inc 3) => 4

単体テストの作成

まずは、lambda式を自動でテストしてくれるコードを作る。

def test_lambda
   eval <<-EOF
   (assert-eqv 4 ((lambda (x) (+ x 1)) 3))

   (set! inc (lambda (x) (+ x 1)))
   (assert-eqv 4 (inc 3))
  EOF
end

assert-eqvは第１引数と第２引数が違う場合は、テストを失敗させる関数。
めっさ単純なテストだけど、さしあたりこんなもんでいい。

一応、実行させて失敗することを確認しておく。

$ ruby test/test_scheme.rb
Loaded suite test/test_scheme
Started
....E...
Finished in 0.047 seconds.

  1) Error:
test_lambda(SchemeTest):
Script::DebugInfo: in procedure call of assert-eqv
    ./scheme/error.rb:14:in `error'
    ./scheme/node.rb:23:in `error'
    ./scheme/procedure_call.rb:25:in `evalute'
    test/test_scheme.rb:27:in `eval'
    test/test_scheme.rb:154:in `test_lambda'

8 tests, 0 assertions, 0 failures, 1 errors

スキャナの拡張

lamda式を導入するには、"lambda"を予約語にして特別扱いしてやる必要がある。なので、文字列をトークンごとに区切るスキャナに変更を加える。

if ['lambda','if'].include?(ident)
  # 予約語
  add_token ident,ident
else
  # 変数
  add_token :VARIABLE,ident
end

パーサーの拡張

スキャナがトークンごとに区切ってくれたので、次はこれから構文木を作らないといけない。これの役割はパーサー。
でも、パーサーは自動生成されるので、設定ファイルをいじればよい。
単にBNF(CFG)を書けばよい。オートマトンの授業が役立つね。

lambda : '(' 'lambda' params body ')'
params : '(' variable_star ')' | variable | '(' variable_star variable '.' variable ')'
body : sequence

そして、一度パーサーを生成して、エラーがないかチェックする。

$ ruby -S racc -v -o scheme/parser.rb scheme/parser.y

エラーが無かったので、構文木を作るためのコードを追加する。

lambda : '(' 'lambda' params body ')'
         {
           result = Scheme::Lambda.new(get_info val[0],val[2][0],val[2][1],val[3])
         }

params : '(' variable_star ')'
         {
           result = [val[1],nil]
         }
         | variable 
         {
           result = [val[0],nil]
         }
         | '(' variable_star variable '.' variable ')'
         {
           result = [val[1].push(val[2]),val[4]]
         }

body : sequence

lambdaノードの作成

パーサーが拡張できたので、次は構文木。

ここまで来たら、コードを書く→テストする→クラスを修正する→テストする・・・の繰り返し。この時のテストを簡略化するために自動でテストできるようにしてある。

そして、いろいろいじくって完成。

require 'scheme/node'
require 'scheme/function'

module Scheme
  class Lambda < Node
    def initialize(info,params,rest,body)
       :
    end

    def call(env,*args)
       :
    end
    
    def evalute(env)
       :
    end
  end
end

テストの拡張

書いてみて、弱そうなところを重点的にテストする。

def test_lambda
    eval <<-EOF
    (set! x 100)
    
    (assert-eqv 4 ((lambda (x) (+ x 1)) 3))

    (set! inc (lambda (x) (+ x 1)))
    (assert-eqv 4 (inc 3))

    ; 仮引数がローカルなスコープを保っているかチェック
    (assert-eqv 100 x)

    ; 可長変引数のテスト
    (set! tail (lambda (x . xs) xs))
    (assert-eqv 10 (car (tail 0 10 11)))

    ; 一個だけ
    (assert-eqv 10 ((lambda x x) 10))
    EOF
end

すると、エラーがぞろぞろ見つかるのでそれを修正。

コミット

あとは、これをSubversionにコミットしておしまい。

速習:lambda式 および仕様の把握