flisp, Stack Machine (2)
弱LisperがMITでSICP(シクピー)を受講した結果 なんてのを読んでいる。この教科書のコースは終了したと聞いていたけど
無理矢理復活している(コースのメールアドレスが6.001-zombies!)のを発見。
ゾンビが存在してて、短時間でLAMBDA教へ入信出来るようだ。そして、無事にコースを 終了すると、LAMBDA団のバッチを貰えるらしい。以後、死ぬまで、ラムダ、ラムダ、ラムダと 唱える人生が待っているとか。
こちらに、その教義が出ている。 6.037 - Structure and Interpretation of Computer Programs
SICPとは章だてが違うようで、SICPではやたら長かった４章があっさりしたものに変わって いるっぽい。その代わり、call/ccが入っていたり、やたら、自分schemeを書いてみようでって のが重視されてるようだ。
そうだよな、LAMDA団なら、evalとapplyを行ったりきたりして、上り詰めていく体験を 是非深く味わって欲しいとの親心だろう。
今、SICPを確認したら、レジスター計算機って説明してた。そうか、スタックマシンに 対して、あちらはレジスターマシンか。そんな事なら、もう一度該当章を読み直しても いいな。あるいは、手っ取り早く、codeを眺めるのもいいか。
まてまて、LAMDA教としては、写経せいと言われそうだな。 なんてのを無視して、Diskを漁ってみたら、楽しいのが出てきた。ch5-compiler.scm。 SICPが佳き解説書になるな。
;;;;Then you can compile Scheme programs as shown in section 5.5.5
;;**implementation-dependent loading of syntax procedures
(load "ch5-syntax.scm") ;section 4.1.2 syntax procedures
;;;SECTION 5.5.1
(define (compile exp target linkage)
(cond ((self-evaluating? exp)
(compile-self-evaluating exp target linkage))
((quoted? exp) (compile-quoted exp target linkage))
((variable? exp)
(compile-variable exp target linkage))
((assignment? exp)
(compile-assignment exp target linkage))
((definition? exp)
(compile-definition exp target linkage))
((if? exp) (compile-if exp target linkage))
((lambda? exp) (compile-lambda exp target linkage))
((begin? exp)
(compile-sequence (begin-actions exp)
target
linkage))
((cond? exp) (compile (cond->if exp) target linkage))
((application? exp)
(compile-application exp target linkage))
(else
(error "Unknown expression type -- COMPILE" exp))))
ほら、flispに付属のcompiler.scmとそっくりじゃん。flispの作者さんもやっぱり、LAMBDA団の 一員だな。
flispをNetBSDへ移植
gitからのflisp-dir内で、git log してたら、
commit 56b46ba923c2aa4d150bbb28de29fa57c3adbef6
Author: James Turner <james@calminferno.net>
Date: Mon Jun 3 21:40:51 2013 -0400
Allow the defining of an init file at build time
Since OpenBSD is unable to determine the pathname of a running process,
this allows us to specify the full path to flisp.boot. This will also
come in handy for system wide installs where you want flisp to live in
bin and flisp.boot to live in share or a similar location.
commit 19a835847c826572f6cff45852d496276b772056
Author: James Turner <james@calminferno.net>
Date: Mon Jun 3 21:40:14 2013 -0400
Add support for OpenBSD
こんなのに出くわした。OpenBSDもサポートしたよってさ。でもBSD界の本家である、NetBSD は、どうやら蚊帳の外らしい。で、見るに見かねて、NetBSDでも動くようにしたよ。
nb7$ egrep '(NetBSD|NETBSD)' -n *.[ch] llt/*.[ch] flisp.c:2312:#elif defined(NETBSD) llt/dirpath.c:92:#elif defined(OPENBSD) || defined(NETBSD) llt/dtypes.h:28:#elif defined(__NetBSD__) llt/dtypes.h:29:# define NETBSD llt/dtypes.h:36:#if defined(OPENBSD) || defined(FREEBSD) || defined(NETBSD) llt/dtypes.h:77:#elif defined(MACOSX) || defined(OPENBSD) || defined(FREEBSD) || defined(NETBSD) llt/timefuncs.c:109:#if defined(LINUX) || defined(NETBSD) || defined(OPENBSD) || defined(FREEBSD) llt/utf8.c:28:#if !defined(__FreeBSD__) && !defined(__OpenBSD__) && !defined(__NetBSD__)
gitで述べられていた、問題部分は、OpenBSDに習っておいた。だって、/usr/src/sysの 所で、
nb7$ find . -type f | xargs grep KERN_PROC_PATHNAME
したけど、応答が無かったからね。参考までに、FreeBSDで探してみると、
$ cd /usr/src/sys $ find . -type f | xargs grep KERN_PROC_PATHNAME ./sys/sysctl.h:#define KERN_PROC_PATHNAME 12 /* path to executable */ ./kern/kern_proc.c:static SYSCTL_NODE(_kern_proc, KERN_PROC_PATHNAME, pathname, CTLFLAG_RD |
うん、確かにあるね。FreeBSDは多方面に使われているから、色々な要求を取り入れているんだな。 正に、BSD界のLinuxか。とか言うと、FreeBSDの重鎮からLinuxと一緒にスナとまさかりが 飛んできそうですよ。
#elif defined(OPENBSD) || defined(NETBSD)
char *get_exename(char *buf, size_t size)
{
/* OpenBSD currently has no way of determining a processes pathname */
return NULL;
}
#elif defined(FREEBSD)
#include <sys/types.h>
#include <sys/sysctl.h>
char *get_exename(char *buf, size_t size)
{
int mib[4];
mib[0] = CTL_KERN;
mib[1] = KERN_PROC;
mib[2] = KERN_PROC_PATHNAME;
mib[3] = -1;
sysctl(mib, 4, buf, &size, NULL, 0);
return buf;
}
そのせいで、テスト部分で失敗する。
gmake test gmake[1]: Entering directory '/home/sakae/femtolisp' cd tests && ../flisp unittest.lsp fatal error: (io-error "file: could not open \"flisp.boot\"") Makefile:23: recipe for target 'test' failed gmake[1]: *** [test] Error 1
しょうがないので、テスト環境へVMとROMを持ち込み、そこで現地検査を実施。
nb7$ cp flisp flisp.boot tests/ nb7$ cd tests/ nb7$ ./flisp unittest.lsp all tests pass
git log に救われたな。以上、移植完了。
flispのhash, gensym
前回ちらっと書いたんだけど、hashの件。perlあたりからこの業界に入った人は(古さ満載、年代を暴露してる) ははん、キーに数値以外のものを取れる連想配列ねって思い当るだろう。最近のpython野郎 （若いって言う比喩で使ってます）にはピンとこないかも知れません。それって辞書じゃ ないですかって、聞き返されたりして。
flispにもhashがある。hashと言うよりhash関数です、って言うのが正解。誤解を受けない かな？ ちょっと心配。ものは試し、試してみる。
> (hash 1) -399682699 > (hash cons) -443745403 > (hash 'cons) 392354999
与えられた引数に対して一意の数値を返す。この手のやつでよく使われるのは、gitで有名に 成ったsha1とかだけど。flispのやつは、独特な実装をしてるっぽい。ソース嫁。
uptrint_t hash_lispvalue(value_t a)
{
int oob=0;
uptrint_t n = bounded_hash(a, BOUNDED_HASH_BOUND, &oob);
return n;
}
value_t fl_hash(value_t *args, u_int32_t nargs)
{
argcount("hash", nargs, 1);
return fixnum(hash_lispvalue(args[0]));
}
実行例から分かるように、控えめな大きさの数値を返しています。fixnumの範囲。 そしてbounded_hashが鍵になるんだけど、見てくと
// *oob: output argument, means we hit the limit specified by 'bound'
static uptrint_t bounded_hash(value_t a, int bound, int *oob)
{
:
int oob2, tg = tag(a);
switch(tg) {
case TAG_NUM :
case TAG_NUM1:
u.d = (double)numval(a);
return doublehash(u.i64);
case TAG_FUNCTION:
:
case TAG_SYM:
:
case TAG_VECTOR:
:
みたいに、引数の属性をtagを根拠にして、適当にばらけるように計算してました。 まあ、控えめなhashですから、これぐらい緩いものでもOKなんでしょう。
hash似たやつに、gensymってのがあります。アクセスする度にユニークな値を返す。 マクロ内で、変数名の衝突を避けるため、システムに登録されない名前が欲しい時に 必須になります。かのマクロ指南書 On Lispも、これ無しでは書けなかったでしょう。
これとhashを組み合わせると、出目が予測されるという、とても楽しい事が起きます。
> (define a (gensym)) #:g1 > (define b (gensym)) #:g2 > (hash a) 1 > (hash b) 2 > (gensym? a) #t > (typeof a) symbol
作者さんは、意図してこういうのを残してくれているのでしょうか？ 目下、この機能を 悪用出来ないか、検討中であります。
table
辞書です。作り方と引き方とか追加とか
> (define mine (table 'ichi 1 'ni 2 'san 3 'si 4)) #table(si 4 san 3 ni 2 ichi 1) > (get mine 'san) 3 > (put! mine 'go 5) #table(go 5 si 4 san 3 ni 2 ichi 1)
ちょいとソースを眺めてみた。
equalhash_put(h, (void*)args[1], (void*)args[2]);
こんなのが使われていて、いとも簡単にtableに登録してると思ったら、とんだ喰わせ者で、 マクロを通じて、llt/の裏社会に繋がっていた。 裏は、とっても複雑でオイラーには理解不能。ケツまくって逃げ出しますよ。 やっぱりhashは大変だって事です。
binary patch
前回積み残していた、パッチ当てをやってみる。untraceの不具合修正だね。
> (disassemble untrace)
maxstack 8
00000: argc 1
00002: loadv
maxstack 9
00000: argc 1
00002: loadg traced?
00004: loada0
00005: call 1
00007: brf @00018
0000a: loadv #fn(set-top-level-value!)
0000c: loadc00
0000d: loadv #fn(function:vals)
0000f: loada0
00010: call 1
00012: loadi8 3
00014: aref
00015: tcall 2
00017: ret
00018: loadt
00019: ret
00004: closure
00005: loadv #fn(top-level-value)
00007: loada0
00008: call 1
0000a: tcall 1
0000c: ret
#t
アドレス12にあるloadi8のオペランドが今は正しい3になってる。元の２に戻して比べて みると、正解だった。それはいいんだけど、flisp.boot上でどんな違いが有るかが分からないと patchする場所が特定出来ないな。
こんな事もあろうかと、正しいflisp.bootをgoodって名前で保存しておいて、悪いflisp.boot を作ったのさ。後は、場所の特定。
$ cmp -x good flisp.boot 0000994c 33 32
次はbviとかhexeditで開いてみる事になる。世間ではhexeditが良く使われているようなので、 hexeditの練習かたがた、pkgを使って入れた。
00009930 23 66 6E 28 22 39 30 30 30 72 31 65 30 7C 33 31 #fn("9000r1e0|31
00009940 36 40 30 63 31 7E 63 32 7C 33 31 62 32 5B 34 32 6@0c1~c2|31b2[42
00009950 3B 5D 3B 22 20 5B 74 72 61 63 65 64 3F 0A 20 20 ;];" [traced?.
00009960 23 66 6E 28 73 65 74 2D 74 6F 70 2D 6C 65 76 65 #fn(set-top-leve
これと、function:valsを比べてみる。
> (function:vals untrace)
[#fn("9000r1e0|316@0c1~c2|31b2[42;];" [traced? #fn(set-top-level-value!)
#fn(function:vals)])
#fn(top-level-value)]
見事に一致が取れている。後は、hexeditの分かり憎いマニュアルと格闘して、該当箇所を 書き換え、Ctl-Xして、yを押して更新。
調子こいて、juliaに実装されているuntraceも変更しておこうかと思ったら、ソースレベルで コメントされてた。調べてみると、方々で殺しが目立っていたよ。juliaからflispが 起動出来ると言っても、牙を削がれたlispに成り下がっていてつまらないぞ。
そうそう、もしjuliaのflisp相当にパッチを当てる必要が出たら、flisp.boot相当が 収納されてる、libjulia.soあたりに入っているので、そこを攻めるべき。julia本体には ないからね。
00DFB880 20 20 20 20 20 23 66 6E 28 22 35 30 30 30 72 31 #fn("5000r1
00DFB890 7C 43 3B 22 20 5B 5D 29 0A 09 09 20 20 20 20 20 |C;" [])...
00DFB8A0 20 23 66 6E 28 22 35 30 30 30 72 31 7C 44 3B 22 #fn("5000r1|D;"
--- libjulia-debug.so --0xDFB8A1/0x13B228C------------------------------
とまあ、ソフトにパッチを当てるなんて何年ぶりだろう？ Macを使ってた頃は、patch 道具のResEditがオイラーの御用達だったからね。
勿論、生業にしてたハード屋のパッチ道具と言えば、良く切れるナイフ。これは、プリント板の パターンカットに必要。それから、先の細いニッパ。基板に半田付けされたICの足を ニッパで切って、（俗に言う）足上げ実施。そこから空中配線。このための先の細い ニッパは、スウェーデン製のやつが最高だった。
ICを追加する時は、基板にパッチ用ICの追加穴があれば、それを使うんだけど、無い 場合は、ICの上にICを載せる亀の子作戦発動ですよ。電源とグランドピンだけを、親IC に半田付け。これで、追加ICが物理的に固定される。子のICは、ICの各ピンを曲げて、 空中を泳ぐようにする。そしてその足から、各所に細い線で配線。 昔は、こんな事を当たり前にやってた。
今は、ハードの配線もFPGAの中に隠れてしまったようで、ソフトにパッチを当てるな んて事もしないんでしょうな。つまらない世界になっちゃったな。これも時代か。
ふと、juliaから起動したlispから、system.lspをロードしたら、いいんでないかと 思って実行してみると
> (load "/home/sakae/femtolisp/system.lsp")
eval: variable string.encode has no value
in file /home/sakae/femtolisp/system.lsp
#0 (lambda)
#1 (load/lambda/lambda (define (string.trim s at-start at-end)
:
#2 (load "/home/sakae/femtolisp/system.lsp")
こんなエラーを吐いて、拒否されたぞ。juliaのlispでは、string.encodeって言う のが、疎外されてた。utf8がらみなんで、julia側で面倒は嫌ったんだろうね。 そこを旨くすり抜ければ、まともにflispを使えるだろうけど、そこまでするなら、 最初からflisp単体で使えよ、ってのが、最終結論だな。