trace(1)
毎週火曜日はファミブのレディースディ。まあ、おいらには関係無い事だが、たまたま女房の アッシー君を務めた時。DVDのコーナーに足を踏み入れてみた。
韓国に占領されてましたねぇ。日本発のアニメはあちこち（の国）を占領しちゃってるから、 余り目くじら立てる事はないけど。で、コーナーをうろうろしてたら、「天使と悪魔」なんて のが陳列されてたので、女房のレンタルリストに追加して貰った。
確かこのシリーズは、ダン・ブラウンという作者によるものだ。初作は「モナリザの暗号」 だか、「ダビンチ･コード」 たったけかな。友人に借りて全てのシリーズを読んだ記憶がある。懐かしくなって、今度は DVDで見るかとなったのだ。
CERNが出てきて、そこで開発された「反物質」が盗まれて、、、って事で、話は進んで行く 訳だが、CERN == Web(HTML)と連想してしまうおいらは、職業病だろうか？ ハードカバーで ２冊分がDVDだと２時間と言うのはあっけないな。やはり、おいらには本が向いていると 思った次第。面白くなって、寝食を忘れて見るのは、本に限る。
暗号解読
本の虫で、「プログラミング Haskell」を読んでいる訳だが、その中にシーザー暗号の作り方と 解読方法の例が出てくる。作り方はともかく、解読方法は、いろいろ試して、文字の出現頻度の 検定を行うとの事だった。これって、ポーの「黄金虫」にもあったような。
この解読方法は理解出来るんだけど、平文がプレーンテキストじゃ無かった場合はどうするんだろう？ たとえば、平文を圧縮しちゃうとか、Paintソフトあたりを使ってキャンパスに描いた文字をBITMAPに変換しちゃうとか いわゆるバイナリー化を施してしまう。そして、そのバイナリーデータを暗号にしちゃうのだ。 そうすると、解読には、正しいバイナリーに戻す必要がある。だけど、バイナリーの状態では 出現頻度の検定とか辞書のマッチング等の手は使えない。
バイナリーの解読には、どういう方法が有効なのだろう？ 勿論、平文をバイナリーにした時の 解読に必要になりそうな情報（たとえば、ヘッダー情報）は、削除しておくとか、目くらましの 偽情報を混ぜておくとかは、普通にやるだろうから。 こういう事は、 サイモン･シンの本に載っているのだろうか？ あるいは、実践ウィルスの 作り方講座あたりが参考になるのだろうか？
debugの友 @oreore_lisp
先ほどから、暗号だとか虫だとかヤバ目な言葉が出てきている。暗号なんて言葉はCIAに傍受 されてそうなんで、もうしない。虫の話なら、ま、問題ないだろう。oreore_lispでdebugした い時、evalなりapplyにBPを置いて調べると思う。受け取った引数がリストだった場合、どんな リストか簡単に見られれば便利だ。
ん？、リストを表示する関数って、oreoreが自前で持ってるよね。そう、print_e だ。こやつを gdbの中で使えればいいんだ。それには、.gdbinit に、登録しておく必要がある。実際に 登録する関数は、sprint_e にした。
define z print sprint_e( $arg0 ) end
ちょっと使い心地を検証してみる。
(gdb) b eval Breakpoint 1 at 0x8049fc6: file oreore_lisp.c, line 549. (gdb) run Starting program: /usr/home/sakae/oreore_lisp/tl lisp> :l base Breakpoint 1, eval (e=0x804c0e8, env=0x0) at oreore_lisp.c:549 warning: Source file is more recent than executable. 549 if (e == NIL || IS_INT(e)) return e; (gdb) z e $1 = 0xc4fdd40 "(setq def (macro (name arg body) (list (quote setq) name (list (quote lambda) arg body))))" (gdb) z top_env $2 = 0xc4fdd40 "((cond *sform*.134517280) (setq *sform*.134517024) (macro *sform*.134517456) (lambda *sform*.134517392) (quote *sform*.134517008) (eval *func* 134520768.000101) (list *func* 134516992.-00001) (acons *"...
よく使うコマンドなので、コマンド名が一文字と言うのは正解だな。でも、人間は欲の塊なので breakしたら、自動的に、"z e"をやって欲しいなあ。gdbには、dispが用意されてて、breakしたら dispで登録しておいた変数を自動表示してくれるけど、コマンドの自動実行はdispに登録できない。
そんな時は、そのものずばりの commandと言うのが用意されている。
(gdb) command
Type commands for when breakpoint 1 is hit, one per line.
End with a line saying just "end".
>z e
>end
(gdb) c
Continuing.
Breakpoint 1, eval (e=0x804c1e8, env=0x804c350) at oreore_lisp.c:549
549 if (e == NIL || IS_INT(e)) return e;
$5 = 0xc4fdd40 "(list (quote setq) name (list (quote macro) arg body))"
(gdb) info breakpoints
Num Type Disp Enb Address What
1 breakpoint keep y 0x08049fc6 in eval at oreore_lisp.c:549
breakpoint already hit 11 times
z e
(gdb) b apply
Breakpoint 2 at 0x8049aa8: file oreore_lisp.c, line 499.
(gdb) command
Type commands for when breakpoint 2 is hit, one per line.
End with a line saying just "end".
>z func
>z args
>end
(gdb) c
Continuing.
Breakpoint 2, apply (func=0xc4f62c0, args=0x804c1f0, env=0x804c350)
at oreore_lisp.c:499
499 cell fbody = eval(func, env);
$8 = 0xc4fdd40 "quote"
$9 = 0xc4fdd40 "(setq)"
これで、随分と虫を駆除出来るかな？
さてと、前回、Schemeなら当たり前にtraceが備わっていると書いた。けど、このoreoreは 最小セットなので、traceなんてのは、勿論無い。無いなら作ろうと思うけど、どうやって 作ればいいんだい？ そんな時は、先輩はどうやったか調べて技を盗むのがよかろう。
gaucheでtrace
最近、１年ぶりにVerUPされて、0.9になった。 関係者の皆様お疲れ様でした。今回から、Windows版 も、インストーラー付きとなったので、導入はWindowsでも容易なはずだ。
で、traceだが、gaucheには標準で提供されていない。（とまあ、RWHに習って、卓袱台を ひっくり返してみました）でも、世の中には、いろいろなschemeの過不足を補ってくれる ポータブルなコードを提供してくれているありがたいお方がいる。
通称 slib というのがそれだ。 落としてきて、/usr/local/ 以下に展開。rootになって、goshを起動して (use slib)(require 'logical) を 一度行っておくと、普通に使えるようになる。(これは、カタログを作る作業です。） 早速使ってみる。
gosh> (use slib)
#<undef>
gosh> (require 'trace)
#t
gosh> (trace fact)
#<closure (debug:trace-procedure debug:trace-procedure)>
gosh> (fact 5)
CALL fact 5
CALL fact 4
CALL fact 3
CALL fact 2
CALL fact 1
RETN fact 1
RETN fact 2
RETN fact 6
RETN fact 24
RETN fact 120
120
gosh> (untrace fact)
#<closure fact>
gosh> (fact 5)
120
こういうありがたいコードがサーと読めればいいんだけど、汎用的に作ってあるせいか、難読 （勿論、私には、、であるが）である。もっと、簡易なのがないかと探してみる。
と、ggcというパッケージに、traceが含まれている 事が判明。早速、解剖してみる。(trace.scm と trace2.scmの２つが提供されてますが、原理の 勉強という理由で、trace2.scmをちと改変して実験台とします。)
(define-macro (trace proc)
`(let ((proc-under-trace ,proc))
(set! ,proc
(let ((level 0)
(retval #f))
(lambda x
(format #t "~a:~a~a~%"
level
(make-string level #\space)
(cons ',proc x))
(set! level (+ level 1))
(set! retval (apply proc-under-trace x))
(format #t "~a->~a~%"
(make-string level #\space)
retval)
(set! level (- level 1))
(when (= level 0)
(set! ,proc proc-under-trace))
retval)))))
これがtraceを実現するマクロです。以下、このマクロを使って、factをトレースしてみます。
gosh> fact #<closure fact> gosh> (fact 3) 6 gosh> (trace fact) #<closure #f> gosh> fact #<closure #f>
traceをセットする前は、#<closure fact>となっていましたが、セットした後は#<closure #f> に変化してる事に注目。それでは、実行します。
gosh> (fact 3)
0:(fact 3)
1: (fact 2)
2: (fact 1)
3: (fact 0)
->1
->1
->2
->6
6
gosh> (fact 3)
6
一度実行すると、trace機能はリセットされました。 では次に、マクロの実行でどのように展開されるか見てみます。
gosh> (%macroexpand (trace fact)) (let ((proc-under-trace fact)) (set! fact (let ((level 0) (retval #f)) (lambda x (format #t "~a:~a~a~%" level (make-string level #\space) (cons 'fact x)) (set! level (+ level 1)) (set! retval (apply proc-under-trace x)) (format #t "~a->~a~%" (make-string level #\space) retval) (set! level (- level 1)) (when (= level 0) (set! fact proc-under-trace)) retval))))
これでは、醜いのでemacsに持って行って、整形してみます。
(let ((proc-under-trace fact))
(set! fact
(let ((level 0)
(retval #f))
(lambda x
(format #t "~a:~a~a~%"
level
(make-string level #\space)
(cons 'fact x))
(set! level (+ level 1))
(set! retval (apply proc-under-trace x))
(format #t "~a->~a~%"
(make-string level #\space)
retval)
(set! level (- level 1))
(when (= level 0)
(set! fact proc-under-trace))
retval))))
これが、traceを可能にするためのコードです。全体が大きなletになっています。 proc-under-traceと言う変数に、trace前(オリジナルの)fact手続きを保存してます。
次のset!で、新たに(trace機能付きの)factを定義し直しています。で、letで 局所変数を２つ定義。levelは、再帰の深さを。retvalは、trace対象の手続きの戻り値の保存に 使われています。
次のlambdaで、実際のtrace機能付きfactの再定義をしています。factを呼ぶ前の状況を表示。 一回呼ぶと言う事でレベルを増やし、applyで元のfactを呼び出し、結果を保存。そして、結果を 表示。呼ばれた後なので、レベルを減らす。なお、(lambda x ... となっているが、この x は、 再定義した手続きに渡ってくる引数を、リストとして受け取る意味になる。
そして、レベルがゼロだったら、終了なので、保存しておいた本来のfactに挿げ替え。最後の retvalは、再定義したfactからの戻り値。うーん、なかなか巧妙ですねえ。
標準でtraceをサポートしてるscheme
すぐに思いつくのはDrSchemeだ。stepperまで付いてて、 面白いんだけど、独自拡張が過ぎて、slibの作者さんからも見放されている。 私も重すぎるので見放した。RnRSの委員会の人も、どうかねぇと言っている。
しっかりしたマニュアル(Webに公開されてる）と共に使えると言う事で (chez (chez scheme))が出している、無償版のpetiteが お勧め。有償版はコンパイラー付きだけど、無償版はインタープリタのみの提供。軽くて 速いのが嬉しい。また、SWLという repl は、カッコの対応や自動インデントをしてくれる ので、非常に手軽。
Petite Chez Scheme Version 7.4
Copyright (c) 1985-2007 Cadence Research Systems
> (define (fact n)
(if (= n 1)
1
(* n (fact (- n 1)))))
> (fact 3)
6
> (trace fact)
(fact)
> (fact 3)
|(fact 3)
| (fact 2)
| |(fact 1)
| |1
| 2
|6
6
あれ？ SICP用に作られたMIT Schemeには 、traceって有ったけかな？ 説明書を調べてみたら、有ったよ。debug機能も充実している。
procedure+: trace-both procedure
procedure+: trace procedure
Equivalent to calling both trace-entry と trace-exit on procedure. trace is
the same as trace-both.
(trace-both fib)
(fib 3)
-| [Entering #[compound-procedure 19 fib]
-| Args: 3]
-| [Entering #[compound-procedure 19 fib]
-| Args: 1]
-| [1
-| <== #[compound-procedure 19 fib]
-| Args: 1]
-| [Entering #[compound-procedure 19 fib]
-| Args: 2]
-| [2
-| <== #[compound-procedure 19 fib]
-| Args: 2]
-| [3
-| <== #[compound-procedure 19 fib]
-| Args: 3]
=> 3
procedure+: untrace-entry [procedure]
Stops tracing the entry of procedure. If procedure is not given, the
default is to stop tracing the entry of all entry-traced procedures.
それにしても、traceの有る/無しで、お勧めschemeを上げてみるってのは、作者様に 失礼だぞ！！
gaucheを便利に使うために
とまあ、traceに注目して、超偏見でお勧めschemeを上げた訳だが、traceが備わっているか どうかなんてのは、まあネタと言う事で。（ああ、またちゃぶ台ヒックリ返しちゃったよ。）
実用的には、コードを書く時にサーと書けるかが問題になってくる。先ほど gaucheな人達が集う場所に 行ってみたらgauche用の補完ファイルが紹介されてた。 私は普段gauche(gosh)を使う時はemacsの上から使っているので、補完も普通に使えるから 問題ないんだけど、ちょっとreplを動かしたい時は、shellから素のgoshを起動しちゃう事が ある。そんな時、補完が出来るとマンモスウレp :-) (関係ないけど、あの人もタレント再開で、 マンモスウレp、、最後にｐを付けるって、ひょっとしてLisper?)
この補完用辞書に4000余りが登録されてました。巨大なnamespace だなあ。びっくりですよ。 R5RSのScheme仕様書はわずか50ページ程しかないのに、随分と便利な関数が作られたものです。 今後もどんどん成長して行くのだろうか？