只今記号操作中

 | 

2008-02-11

[][][][] ステップ実行eval開発中(5) 12:58

WiLiKiに書いた。

しかし……これって、ものすごくR5RS外だよなあ、あんまり突き詰めるような部分じゃないよなあ、移植性ないよなあ、とも、書きながら思ってしまった。

mzschemeで追試したら、mzschemeではそもそも、special formやmacroの実体に、(即値風に)アクセスする事自体がエラー扱いになってたのも、裏付けのなさの一因だ。


ただ、ステップ実行evalを実装するには、このeval拡張があれば楽かつ安全に実装できるので、できれば欲しいところ……。

無かったら、自分でSchemeScheme処理系を書くか、ランダム生成した隠し束縛でインチキするかのどっちかというのはちょっと厳しい。


とりあえず、gauche.gongには動く物を持っていかなくてはいけないので、隠し束縛のインチキで実装して、ステップ実行eval作成の続きを続行しよう。

[][][][] ステップ実行eval開発中(4) 07:48

できた。eval拡張パッチが。

さっきのコメントは、((lambda () ...) ...)のような、car部分がlistになってるものについてだった。気にしなくてよかった。

R5RSのevalの項目も確認した。

expression は,データとして表現された一つの妥当な Scheme 式でなければならず,(以下略)

実装は eval を,第1引数として式以外のプログラム (定義) を許したり,環境として他の値を許すように拡張してもよい(以下略)

  • 最初の引用の「データとして表現された一つの妥当な Scheme 式」が、純粋なS式だけじゃなく「内部表現」も含んでれば、大丈夫。
    • でも、これは微妙そうな気はする。
  • 或いは、二番目の引用の「式以外のプログラム (定義)」にあてはまればok。
    • とりあえず手続きはこの定義にあてはまりそうだけど、マクロとspecial formはちょっと微妙かも……。

おそらく大丈夫だと思われるが、ちょっと微妙かも知れない。


もう少し、細かいパターンの条件分岐のチェックと動作確認が終わったらWiLiKiに提出してみる。

[][][][] ステップ実行eval開発中(3) 06:19

回り道したが、これを発見した。凄い有難い。


で、問題のコードはcompile.scmのpass1のところにあった。

evalの第一引数のlistの先頭が何なのかをpass1/lookup-headで調べているが、ここが既に実体のマクロやspecial formだった場合にスルーされてしまうのが原因のようだ。

;; Check if the head of the list is a variable, and if so, lookup it.
;; Note that we need to detect the case ((with-module foo bar) arg ...)
;; NB: This isn't a proper fix, for we cannot deal with the situation
;; like nested or aliased with-modules.  The Right Thing is to run
;; `pass1 for syntax' on (car PROGRAM) and check the result to see if
;; we need to treat PROGRAM as a special form or an ordinary procedure.
;; It would be a large change, so this is a compromise...

というコメントがあるのが気になるが、とりあえず試してみる。

[][][][] ステップ実行eval開発中(2) 04:04

要は、

((eval `(,lambda (arg) arg) (interaction-environment)) 123)
=> 123

のように、evalに対して、マクロやspecial formの「実体」を渡した時にも、evalがそれをマクロやspecial formとして扱ってくれれば問題は解決するのだが、とりあえずGaucheはそう扱ってはくれなかった。

(そもそも、evalにシンボルでない実体を渡した時の挙動自体がR5RS外のような気はする。しかし未確認。)

ので、自前で展開する必要があると思ったのだが、どうにも大変そうだ。

evalがマクロ類の実体を扱ってくれれば楽なのに……と思い、Gauche本体の方に手を入れる方向もある事に気付いた。

とりあえず、guileは前述の式を与えたところ、自分の望んでいる通りに機能しているので、そういう挙動にしてもいい裏付けは無くはないようだ。

とりあえず今からパッチ書いてみる事にする。

採用されるかは謎。そもそも楽にパッチ書けるのかも謎。

[][][][] ステップ実行eval開発中(1) 03:18

とりあえず手続き類は問題無く動くようになった。

しかし、マクロとspecial formの評価時に割り込み処理を入れるのが難しい。

マクロとspecial formには割り込み処理を入れない事にすると、当初に想定していた利用方法の大半が駄目になってしまう為、この部分は実装しておきたい。

  • 具体的には、マクロ展開やspecial formが(手続きの実行を含まずに)無限ループする場合があると問題になるので、割り込み処理を入れて、特定ステップ以上かかったらevalを中断できるようにしたい、という事。

実装方法は色々と考えた。

  1. 真面目に、evalにかける前に自前でマクロとspecial formを展開/実行する。
    • マクロの方はmacroexpand-1があるのでそれなりに簡単そうだが、special formも同時に考慮する事を考えると頭が痛くなる。quasiquoteのunquoteとか。
      • 自前でScheme処理系Schemeで書くのに近い作業になる……SICPの後半の方でこんな問題があった気がする(自力で解いてない)。
        • ちょっとSICP読み直したかったが、会社のはどっかいってしまったらしく、見付からなかった。amazon注文は今「通常3〜5週間以内に発送」。7&Yは今「品切れ」。英語版ならオンラインで読める、が……。
        • 来週に紀伊国屋辺りで探そう。
      • とりあえず、この方法で実装するとしても、今回のgauche.nightが終わってからにする(他人のコードを見て参考にする気マンマン)。
  2. 無限ループする可能性のある特定special formは、ステップ実行eval用モジュール(環境)に束縛する段階で、こっそり割り込み処理を実行するマクロとして束縛する。マクロはmacroexpand-1を使って自前で展開する。
    • マクロという事は、実行前に「本物のspecial form」と「割り込み処理を行うproc」に展開される事になる。つまり、ステップ実行eval用モジュール空間内に「本物のspecial form」を(束縛として)持ち込む必要がある。しかし、この「本物のspecial form」の方の束縛が悪用者にバレるとセキュリティホールになり、DoS(無限ループ)可能になってしまう。
      • あまりいい解決方法ではないが、束縛の名前をランダムに生成して隠す事にする。
      • この時に問題になるのは、Gaucheが提供する、束縛テーブルを参照する系の手続きの存在と、エラーメッセージ。対策は今は考えない事にする。

「最終的には、真面目にspecial formを実装する」という約束で、とりあえずspecial formは隠し束縛で実装する事にする。

マクロは自前で展開する。

shiroshiro 2008/02/11 08:54 マクロやsyntaxの実体がcar部に来た時にそれをマクロや構文キーワードが来たかのように扱うのはfirst class macroとか呼ばれたりしますが、一貫性のある意味づけが難しいんですよ。
例えばそれを許すと
(for-each (lambda (z) (z #t ’ok (destroy-the-world))) if)
みたいな書き方をされた時にどうするの、とか。

ranekovranekov 2008/02/11 11:26 ちょっと長くなったので、返事はWiLiKiの方に書きます。
(修正にcompile.scmのpass1/lookup-headを修正したら、これがpass1/bodyからも呼ばれてたので、そっちに影響を与えないかの検証が終わってから……)

ranekovranekov 2008/02/11 18:54 あれから色々考えて、確かに、実は奥が深くて、難しい事に気付きました……。
WiLiKiの方に、もう少し追記します。

 |