トップ «前の日記(2008-01-07) 最新 次の日記(2008-01-09)» 編集

Route 477



2008-01-08

[biwascheme] equal?

現実逃避にも熱が入る今日この頃ですが、皆様いかがお過ごしでしょうか。

write/ssができたので、これそのままequal?にも使えんかなーと思ったのだが…

(let* ((x (list 'a)) (y (list 'a)))
  (equal? (list x y) (list x x)))

というコードを考えると、(list x y)は "((a) (a))"で、 (list x x)は "(#0=(a) #0#)" になるから駄目なのであった。残念。

ちなみにwriteでなくwrite/ssなのは、R6RSのequal?は循環構造でも停止しないといけないから (参考)。

無いよりはマシかということで、writeを使った実装をコミットした。 あとで書き直す。

equal?の実装とかめんどいなーと思って今まで放置してたのだけど、write/ssに比べたら全然難しくないと思えるようになった (特に停止性を考えなければ)。なんとなく成長している感があって良い。

[biwascheme] 速度と可読性について悩む

例えばPrototype.jsのeachを使うか使わないか。

  • eachを使う
    • メリット
      • 書くのが楽
      • 読みやすい。あとからbiwaschemeのソースを読む人にとって優しい。
    • デメリット
      • 遅い。
  • for文手書き
    • メリット
      • 速い。
    • デメリット
      • eachより読みにくい。
      • 書くのがだるい(おれが)

まぁほんの少し速いことにどれくらい意味があるかは処理系のどの部分かによって違ってくるわけだけど、 いちいちこれはeachでいいかとか考えるのが面倒になってきたので全部eachにしちゃえという悪魔の囁きが。

自明な例:

インタプリタのコア部分(中間言語を実行していくところ)
ここはさすがにeachは避けたい。
write/ss
多分そんなに多用しないのでeachでいい。

いま、ソースコードのトップレベルの各式に対して繰り返す部分をeachにしようかforにしようか悩んでいるところ。

ていうか、個数がいくつから有意な差が出るのか一度ベンチマーク取らんとな。判断基準が。勘で決めている場合ではない。

あとfor文にしても、lengthをキャッシュするか否かとかー

別解

全てのeachをfor文に展開するプリプロセッサを書く。

[biwascheme] 全体をlambdaでくくるのを止めた

ソースコードに複数の式があった場合、それらを全部つなげてlambdaでくるむという手抜きをしてたのだが、それを止めた。

なんでかというと、以下のようなのがうまく実行できないからだ。

(define a "global var")
(set! a 1) ;unbound symbol 'a'

でどうしたかというと、とりあえずソースコードを全部パーズし、インタプリタが式の配列とどこまで実行したかを 状態として持つようにした。

まあPauseが絡まない限り状態変数とか要らないんで、Pauseオブジェクト側に持たせても良かったんだけど… というかそうした方が良いか?うーん。 でもスタックはインタプリタ側が持ってるんだよなー。

整理しよう。

状態変数:

  • stack
  • a,x,f,c,s
  • forms (パーズした式たち)
  • forms_ct (いま何番目の式を実行中か。Array#popで削っていけば不要なんだが、実行速度に配慮したとかなんとか)

今の実装だと、stack, forms, forms_ctはインタプリタが持ってて、x,f,c,sはPauseが持ってる。aはインタプリタを再開するときに外部から与えられる (例えばconfirmにおけるユーザの入力とか)。

とりあえずこのままにしとくか。

(define c 1)
(set! c (confirm "hoge"))
c

こんなプログラムも問題なく実行できるようになった。

[junk] ふと

もう一年修士やった方が全体として幸せかもなぁなんて考えが頭をよぎる。

卒業と留年を同時に行うことはできないので、どちらが幸せかなんて分からないわけだが。

[biwascheme] jsSchemeがCoreEnvとTopEnvを分けていた理由

jsSchemeのREPLにはユーザが定義した変数のインスペクタみたいのがあったので、そのためだったらしい。最近気付いた(遅いよ)。

[biwascheme] lambda式中でグローバル変数をset!できないバグ

以下のプログラムの結果が1になる。

(define a 1)
((lambda () (set! a 3)))
a

2番目の式のコンパイル結果はこう。

['frame', ['refer-global', 'a', ['argument', ['close', 1, ['constant', 3, ['assign-free', 0, ['return', 0]]], ['apply', 0]]]], ['halt']]

assign-globalになるべきところがassign-freeになってしまっている。 あとaの参照が自由変数と見なされてcollect_freeの対象になっているっぽい(→refer-global)。

ひげぽんさんが11月に遭遇したバグと同じか?

自由変数とかset!のあたりは、ちゃんと理解せずに適当に済ました感があるので、そのツケが来たともいえる(^^;

作業ログ

直すべきこと:

  • aが自由変数と判定されるのを直す。

どこを直すか:

  • find_freeを直せばいいはず

どう直すか:

  • 元の3impの実装にはグローバル変数がないので、「自由変数:ローカル変数でない変数」
  • これを、
    • 「ローカル変数:lambda式の仮引数」
    • 「自由変数:参照or代入されていて、ローカル変数ではなくて、外側のlambdaの仮引数になっているもの」
    • 「グローバル変数:それ以外」
    • のようにしたい。
  • 変数eの中身が上のような定義を満たすようになればOK

やること:

  • 変数fの内容が正しいかチェックする
    • てかいつのまにこんな変数増やしたんだっけ(汗
    • 変数fは「外側のlambdaの仮引数になっているもの」を表す。
    • fをいじるのはlambda式の本体をコンパイルするとき(スコープが深くなるとき)だけ。
      • このとき、fにlambda式の仮引数を加える。加えた情報は、さらに内側のlambda式をコンパイルするときに役に立つ。
  • 変数fの使い方が正しいかチェックする
    • 変数fを使うのはfind_freeだけ。
      • 案の定コメントに書いてあることがとんちんかんだw
      • あとローカル変数の集合に「b」とかいう名前付けるのやめてください(><)
      • もしかして、フランス語で'local'がbで始まる単語になる?
    • 参照時:
      • 変数がfに含まれていたら自由変数。これは正しい。
    • 代入時:
      • 変数がfに含まれていたら自由変数…ってf見てねえじゃん。これのせいか。
      • fを見るように直した。
(define a 1)
((lambda () (set! a 3)))
a

結果:3

やったね!!

困ったこと:

  • 「現在のローカル変数」と「外側のローカル変数」の区別がややこしい。
    • だって変数名が1文字なんだもん
    • そのうちリネームしたい。
  • sをsets.union(s.intersect(free))としてるのがよく分からない。
    • あ、setsはfind_setsの返り値、freeはfind_freeの返り値ね。
    • setsをそのまま渡すんじゃ駄目なん?
    • そもそもsは何に使われるのか
      • 変数参照のとき、その変数がsに含まれていたら、indirect命令を挟む
      • つまり、sはboxingされた変数の一覧。
    • とすれば、sets.union(s) まではよく分かる。現在のlambda中でset!される変数だけでなく、外側でset!されるものもboxingされた変数だからだ。
    • じゃああとは s.intersect(free) の意味を考えれば良い。
      • これは「sのうち、freeにも含まれるもの」という意味。
      • 逆に考えて、「sのうち、freeに含まれないもの」とは何か。これはつまり「sのうち、varsに含まれるもの」と、「sのうち、グローバル変数であるもの」。
      • これらがsとして渡るとなにがマズいか?
        • sに含まれる変数はindirect経由で参照されるのだった。
        • varsに含まれるもの(ローカル変数)はindirectしてはならない…のかな。どうだっけ。
        • グローバル変数であるものはindirectしてはならない。これは確か。
      • つまり、「indirectすべきなのは自由変数だけ」ということらしい。なるほど。
  • いきなりトップレベルで(set! a 1)とやってもエラーにならない。
    • TopEnvにエントリがないものをassign-globalしようとしたら例外を投げればいい?
    • いや、これじゃdefineもエラーになってしまうな。
      • define-global命令を追加する?
      • コンパイル時に、define対象のグローバル変数に仮の値を入れておく?
        • これで何か問題があるかな。
        • てか a["foo"] = undefined でも a.hasOwnProperty("foo") == true なのか
        • とりあえず現在のテストは通った。