femtolisp
前回は llvm ocaml bindingを試して失敗した。ならば、頑張ってllvmのバージョンを 上げたのを作ってやってみようとなった。
うんと新しいllvmって事で、3.9を選んでみたら、いろいろなtar玉が必要みたいで、 llvmの中でconfigureなんてするんじゃ無いと怒られた。噂によるとconfigureなんていう摩訶不思議な 魔怪と決別して、Makefileの作成には、清く正しいcmakeを使うらしい。調べる気力も無かったので、 llvm 3.6にレベルダウン。（こういうのはレベルダウンとはちと違うかな）
configureの所で、ocamlの色々な関係者が必要とぬかす。その度に調べて入れていった。 どう調べるか？ ググル様に聞くのもあれなんで汎用的なやつ。
sakae@uB:~$ camlp4of The program 'camlp4of' is currently not installed. You can install it by typing: sudo apt-get install camlp4-extra sakae@uB:~$ dpkg -S ocamlbuild libfindlib-ocaml: /usr/lib/ocaml/METAS/META.ocamlbuild
で、どうやっても解決出来なかったのが、ctypes。巷では、opamのモジュールになってるから、 opamをまず設置して、そこからインストールせよって事らしい。単独で使いたい人は どうしろと？ まあ、ghcがcabalに頼っているのと事情は同じか。と言うことで、単独行は あえなく中止と相成りました。
で、ocaml用のコードをちらちら見てるんだけど、どうもピンとこない。ocaml特有の 言い回しが鼻につくというか、目に余ると言うか。。。歳と供に注意力が散漫に なるのであろうか。常日頃触っていないと皮膚感覚が鈍るという事にしておこう。
最後に、 LLVMとコンパイラとVM とかを見ておきますかね。
lispでの言語処理系はどうよ？
で、忘れないようにlispと言うかschemeと言うか、いわゆる括弧系のリハビリと言うか、 頭脳メモリーのリフレッシュをしときましょ。
ええ、DRAMのリフレッシュは、バーストリフレッシュとかヒドンリフレッシュとか ディストリビューテッドリフレッシュの3種類有る事は承知してますよ。 今のパソコンに搭載してるメモリーは、どちらが 採用されているんでしょうか？ すっかり世間の事情から疎くなっていますよ。 そういう時は、SDRAMの解説を読めば いいんだな。
ああ、DRAMってのは、情報の記憶(１か０かの事)をコンデンサーに電荷が溜まっているかで対比 してる。コンデンサは放っておくとリークで電荷が無くなる。（痴呆症になる） そうなる前に、RAWアドレスをスキャンして、再記憶するリフレッシュって操作が 必要。オイラーが現役の頃のDRAMは、4msの間にリフレッシュせいと言う仕様だった。
バースト法は一気にリフレッシュする。ディストリ法は、各アドレスが4ms間隔で アクセスするように分散させてリフレッシュ。当然、リフレッシュ中は、ユーザー側 からメモリーアクセス出来ない。それじゃ困るって事で、メモリーサイクル中に RAWアドレスへのスキャンを隠してしまう方法がヒドン法。
こうしてみると、各リフレッシュってガベコレ(GC)に似てるな。GC中はユーザー側 からメモリーアクセス出来ませんって所が。まあ、両者共、メモリーアクセスに 共通する問題だから当然か。そういうオチかよ。そんじゃ解説します。
リフレッシュは３種類。GCも大きく分けるとやはり３種類になるかな。バーストに 相当するのが、一気にGCするマーク・スイープ法とかコピー法（SICPで解説されてる。 あれを東大では式年遷宮と言うとか。オイラーは焼畑農法と思う）。ディストリ法に相当するのは、 メジャー/マイナーGCになるか（ちょっと対比が強引だな）。ヒドンに相当するのは、 レファレンス・カウンター法。
そうしてみると、どちらかが、考え方を真似た可能性が有るな。記憶が鮮明に残って いるのは、インテル（ご存知、糞石メーカー）が、世界で初と言う大容量のDRAM、 型式（i1103)を発表したんだ。大容量と言っても、1024Address X 1Bitと言う 代物だけどね。
この石はPDP-11に採用されたそう。それよりも前にlispは有ったはずだから、年代的には GCの方が先に生まれていたはずだな。そして最近では、SSDでもガベコレ問題が有るのね。 ライトアンプリフィケーション いやー、メモリーとGCは永遠のテーマですよ。
わき道に逸れてしまったな。 オイラーの脳はヒドンリフレッシュを常に行っておく必要が有るな。バーストだと 脇目もふらずに無我夢中、その間は何も受け付けないじゃ困りますから。
久しぶりに、How To Become A Hacker さんの所を訪ねたら、面白い記事が出ていた。
面白いな。オイラーもfedoraにgaucheを入れて、試してみるかな。で、入れた。けど、 infoが作成されなかったぞ。どうしてってんで調べたら、makeinfoが入っていない為、 そんな事出来ませんって拒否されてたんだ。
makeinfoは何処？ fedoraでは、パッケージ名が分からなくても、配置先から検索して パッケージを見繕ってくれる機能があるってさ。どうせ、makeinfoは、収まる所へ収まるはずですから。 /usr/binって馬鹿の一つ覚えで十分です。
[sakae@fedora ~]$ sudo dnf install /usr/bin/makeinfo
================================================================================
Package アーキテクチャ
バージョン リポジトリ 容量
================================================================================
インストール:
perl-Text-Unidecode noarch 1.27-1.fc23 updates 145 k
perl-Unicode-EastAsianWidth noarch 1.33-6.fc23 fedora 15 k
perl-libintl i686 1.20-18.fc23 fedora 801 k
texinfo i686 6.0-2.fc23 updates 1.1 M
トランザクションの要約
================================================================================
インストール 4 パッケージ
総ダウンロード容量: 2.0 M
インストール済み容量: 9.1 M
アセンブリでSECD machine LISP 開発日誌 なんて人を見かけた。すごいものだなあ。
femtolisp
前回までのjuliaで何回かflispを取り上げた。debug環境も作っておいたので、そのまま 詳しい観光をしても良かったんだけど、何せjuliaの下支えという事で、再コンパイル等も 面倒。（ちょいと書き換えてとかやると、理解が深まる）
そんな訳で、flispだけを取り出してきて、ごにょごにょしたい。ソースは、 femtolispに有るので、git clone して持ってくる。
FreeBSDでもLinuxでもMacOSでもコンパイル出来るようにMakefileが用意されてるので、 容易に実験環境を作れるだろう。
makeって、一種の計算機。より正確にカッコよく言うと、チューリング完全ですから。 だから、Makefileはプログラミング言語として、読むのが正解。読んで理解するより、 実行して、ログを取るだけでもいいだろう。疎かにするなよ。作者の熱い心が秘められて いるからね。
ざっと見、debugオプションを付けると出来上がった成果物をgdbに渡せて便利な事に 気付いた。そして、flispを下支えしてるユーティリティにもgdbの魔力が及ぶよう、 先に、lit-dirの中に入って、コンパイルしておく。
cd llt gmake debug | tee LOG
それから、top-dirで、gmakeすれば良い。どんな風になったかと言うと
$ cat LOG : ar rs libflisp.da flisp.do builtins.do string.do equalhash.do table.do iostream.do clang -g -DDEBUG -falign-functions -Wall -Wno-strict-aliasing -Illt -DUSE_COMPUTED_GOTO -c flmain.c -o flmain.do clang -g -DDEBUG -falign-functions -Wall -Wno-strict-aliasing -Illt -DUSE_COMPUTED_GOTO flisp.do builtins.do string.do equalhash.do table.do iostream.do flmain.do -o flisp llt/libllt.a -lm libflisp.da :
サフックスに見慣れない、.do なんて付いているけど、作者さんの親切心で、debugオプション 付きでコンパイルしたから宜しくって印だ。
で、早速走らせてみたいんだけど、何やら tinyなんてdirに目が行った。femtoよりも 小さいって事？ そんな単位はオイラー知らねぇーぞ、とか言わないで覗いてみる。
実験用のlispでした。コメントも入れて、1034行しかありません。こちらを先に 見ておきます。
まずは実行例
$ ./runme file not found error loading file "system.lsp" > (set 'hoge (lambda (x) (+ x x))) (lambda (x) (+ x x)) > (hoge 1234) 2468 > (eval (hoge 321)) 642 > (apply hoge '(5678)) 11356
Scheme方言のlisp-1との事。とは言え、defineは有りません。何せ、定義されて いるものは、
enum {
// special forms
F_QUOTE=0, F_COND, F_IF, F_AND, F_OR, F_WHILE, F_LAMBDA, F_MACRO, F_LABEL,
F_PROGN,
// functions
F_EQ, F_ATOM, F_CONS, F_CAR, F_CDR, F_READ, F_EVAL, F_PRINT, F_SET, F_NOT,
F_LOAD, F_SYMBOLP, F_NUMBERP, F_ADD, F_SUB, F_MUL, F_DIV, F_LT, F_PROG1,
F_APPLY, F_RPLACA, F_RPLACD, F_BOUNDP, N_BUILTINS
};
とっても小さいけど、マクロを搭載。そしてびっくりする事に、 simple compacting copying garbage collector を実装していると言うのです。 これはもう、どんな実装になっているか、見ておくしかないな。
あたりが参考になるかな。
typedef struct {
value_t car;
value_t cdr;
} cons_t;
typedef struct _symbol_t {
value_t binding; // global value binding
value_t constant; // constant binding (used only for builtins)
struct _symbol_t *left;
struct _symbol_t *right;
char name[1];
} symbol_t;
lispに取って大事な々、ご本尊様。consの定義と、symbolと言うか昔気質だとatomの 定義。シンボルに右左が有るって事は、検索時間を稼ぐために、２進木を使って いるのでしょう。
(gdb) p symtab
$10 = (symbol_t *) 0x809e018
(gdb) p *symtab
$11 = {binding = 2, constant = 134864922, left = 0x809e058, right = 0x809e038, name = "n"}
(gdb) x/s (symtab)->name
0x809e028: "nil"
(gdb) x/s (symtab->left)->name
0x809e068: "lambda"
(gdb) x/s (symtab->left->right)->name
0x809e088: "macro"
こういうのをgdbでスマートに（幅優先で表示するとか）リターンキーを叩くだけで、 表示出来ないものだろうか？ 上記の構造体定義の関係上、構造体を表示させても、 name部分は先頭の１文字しか表示されない。（ああ、登録する時は、構造体のサイズと 登録名の文字列長を加算して、mallocにサイズを渡してるけど）
(gdb) x/s (symtab)->name 0x809e028: "nil" (gdb) x/s (symtab->left)->name 0x809e068: "lambda" (gdb) x/s (symtab->left->left)->name 0x809e0a8: "label" (gdb) x/s (symtab->left->left->left)->name 0x809e0e8: "cond" (gdb) x/s (symtab->left->left->left->left)->name 0x809e128: "and" (gdb) x/s (symtab->left->left->left->left->left)->name 0x809e348: "+" (gdb) x/s (symtab->left->left->left->left->left->left)->name 0x809e388: "*" (gdb) x/s (symtab->left->left->left->left->left->left->left)->name 0x10: <error: Cannot access memory at address 0x10>
car,cadr,caddr,cadddr ... の気分。人間Lispですよ。
そして、TAGの定義
#define TAG_NUM 0x0 #define TAG_BUILTIN 0x1 #define TAG_SYM 0x2 #define TAG_CONS 0x3 #define UNBOUND ((value_t)TAG_SYM) // an invalid symbol pointer
2Bitを使って、４種類のオブジェクトを表現してます。従って数値は30Bit分に なる事が推測出来る。
// functions ending in _ are unsafe, faster versions #define car_(v) (((cons_t*)ptr(v))->car) #define cdr_(v) (((cons_t*)ptr(v))->cdr) #define car(v) (tocons((v),"car")->car) #define cdr(v) (tocons((v),"cdr")->cdr) #define set(s, v) (((symbol_t*)ptr(s))->binding = (v)) #define setc(s, v) (((symbol_t*)ptr(s))->constant = (v))
car,cdrとかの便利なC語用のマクロ。中身を見ずに強引にcar,cdrする版と、安全版が 用意されてる。
// safe cast operators --------------------------------------------------------
#define SAFECAST_OP(type,ctype,cnvt) \
ctype to##type(value_t v, char *fname) \
{ \
if (is##type(v)) \
return (ctype)cnvt(v); \
type_error(fname, #type, v); \
return (ctype)0; \
}
SAFECAST_OP(cons, cons_t*, ptr)
SAFECAST_OP(symbol,symbol_t*,ptr)
SAFECAST_OP(number,number_t, numval)
こういうの初めてだ。
インタープリタの実行は、スタックマシンとして、値をスタックに積んで、それを 演算してく事になる。その為の定義。
#define N_STACK 49152 static value_t Stack[N_STACK]; static u_int32_t SP = 0; #define PUSH(v) (Stack[SP++] = (v)) #define POP() (Stack[--SP]) #define POPN(n) (SP-=(n))
49152の大きさの配列をスタックにしてるけど、この数字って作者のラッキーナンバー かな。
case F_CONS:
argcount("cons", nargs, 2);
v = mk_cons();
car_(v) = Stack[SP-2];
cdr_(v) = Stack[SP-1];
break;
:
case F_NUMBERP:
argcount("numberp", nargs, 1);
v = ((isnumber(Stack[SP-1])) ? T : NIL);
break;
case F_ADD:
s = 0;
for (i=saveSP+2; i < (int)SP; i++) {
n = tonumber(Stack[i], "+");
s += n;
}
v = number(s);
break;
アリティーが固定の場合は、SPの負の方向に引数が置かれる。不定個の場合は、値は、左側から右側への 順番で評価され、スタックのプラス方向へ配置されてる。（よって、引数の評価順は、 右から左になる）
tinyの中に有るsystem.lspを間違えたものを使っていた。正しいものにしたら、schemeっぽくなったので、gcの 動きを追ってみる。
> (define c '()) nil > (while t (set c (cons t c)))
ひたすらconsを消費してくやつ。gc()で待ち構えていると、gcが発動された。
(gdb) bt #0 gc () at lisp.c:273 #1 0x080491aa in mk_cons () at lisp.c:218 #2 0x0804ac2c in eval_sexpr (e=679602635, penv=0x804de6c <Stack>) at lisp.c:742 #3 0x08049d0b in eval_sexpr (e=679602611, penv=0x804de6c <Stack>) at lisp.c:579 #4 0x0804a854 in eval_sexpr (e=679602587, penv=0x804de6c <Stack>) at lisp.c:692 #5 0x0804bf98 in toplevel_eval (expr=679602587) at lisp.c:984 #6 0x0804c140 in main (argc=1, argv=0xbfbfe888) at lisp.c:1029
eval中にconsが欲しくなって実行したら、領域が無くなってた。それでgcが発動された。 gcが実行されて行くと、中でcons場所の移動が発生する。きっかけは、シンボルテーブルから 辿って、consエリアを指しているのを見つけ、新しい領域へ移動。
(gdb) bt
#0 relocate (v=679559547) at lisp.c:250
#1 0x08049412 in relocate (v=679559539) at lisp.c:253
#2 0x080493fc in relocate (v=679559531) at lisp.c:252
#3 0x08049412 in relocate (v=679559515) at lisp.c:253
#4 0x08049412 in relocate (v=679559507) at lisp.c:253
#5 0x08049456 in trace_globals (root=0x28823c40) at lisp.c:260
#6 0x08049469 in trace_globals (root=0x28823220) at lisp.c:261
#7 0x08049469 in trace_globals (root=0x288230e0) at lisp.c:261
#8 0x08049469 in trace_globals (root=0x288230a0) at lisp.c:261
#9 0x08049469 in trace_globals (root=0x28823060) at lisp.c:261
#10 0x08049469 in trace_globals (root=0x28823020) at lisp.c:261
#11 0x08049245 in gc () at lisp.c:277
#12 0x080491aa in mk_cons () at lisp.c:218
#13 0x0804ac2c in eval_sexpr (e=679602635, penv=0x804de6c <Stack>) at lisp.c:742
:
該当するソースは、VERBOSEGCをonにしておくと、五月蝿いぐらいに報告してくるの だろうね。
272 curheap = tospace;
273 lim = curheap+heapsize-sizeof(cons_t);
274
275 for (i=0; i < SP; i++)
276 Stack[i] = relocate(Stack[i]);
277=> trace_globals(symtab);
278#ifdef VERBOSEGC
279 printf("gc found %d/%d live conses\n", (curheap-tospace)/8, heapsize/8);
280#endif
281 temp = tospace;
282 tospace = fromspace;
283 fromspace = temp;
やっぱり五月蝿い。
gc found 2245/8192 live conses gc found 2245/8192 live conses gc found 2245/8192 live conses
ついでだから、system.lspの冒頭付近を見ておく。
(set 'list (lambda args args))
(set 'setq (macro (name val)
(list set (list quote name) val)))
オイラーが、define無いと思って、setを直接使って、関数を定義したけど、ここでも 同じ事をやってるね。setqも欲しいなと思ったら、早速macroを使って作ってた。 考える事は一緒だね。
そして、defineの定義
(defmacro defun (name args . body)
(list 'setq name (list 'lambda args (f-body body))))
(defmacro define (name . body)
(if (symbolp name)
(list 'setq name (car body))
(cons 'defun (cons (car name) (cons (cdr name) body)))))
CLスタイルを使うには、この前にf-bodyの定義が必要だ。
(setq f-body (lambda (e)
(cond ((atom e) e)
((eq (cdr e) ()) (car e))
(t (cons progn e)))))
なんだか、progn なんてのが出てきて、懐かしいな。
$ ./runme gc found 1607/8192 live conses Welcome to femtoLisp (modfy) ---------------------------------------------- > setq (macro (name val) (list set (list quote name) val)) > define (macro (name . body) (if (symbolp name) (list (quote setq) name (car body)) (cons (quote defun) (cons (car name) (cons (cdr name) body))))) > map (lambda (f lst) (if (atom lst) lst (cons (f (car lst)) (map f (cdr lst)))))
repl上から、定義が丸見えってlispに初めて出会った。これは貴重だな。
oblist
今度はflisp付属のsystem.lspをちらちらと眺めている。そしたら、make-system-image なんてのに出会った。これってjuliaのflispにも有ったな。 興味深い手続きを発見。
> (environment)
(zero? write wchar void vector.map vector->list vector.alloc vector? values
:
*banner* * *builtins* *print-length* *print-pretty* function)
> (length that)
367
これって、登録されてる手続きじゃないですか。昔風に言うと、oblist。昔風な名前で 呼んであげたいって事で、system.lspに登録したけど反映されず。 どうすれば良いかと言うと、
(define (oblist) (environment))
こんな定義を書いておいてから、
$ ./bootstrap.sh Creating stage 0 boot file... Creating stage 1 boot file... Testing... cd tests && ../flisp unittest.lsp all tests pass
bootstrapして、システムイメージを更新すれば良い。
$ cat bootstrap.sh #!/bin/sh cp flisp.boot flisp.boot.bak echo "Creating stage 0 boot file..." #../interpreter/flisp mkboot0.lsp system.lsp compiler.lsp > flisp.boot.new ./flisp mkboot0.lsp system.lsp compiler.lsp > flisp.boot.new mv flisp.boot.new flisp.boot echo "Creating stage 1 boot file..." ./flisp mkboot1.lsp echo "Testing..." make test
インタープリタ版のflispにsystemlispとコンパイラーを読み込ませて、それを コンパイルするコードが、mkboot0に書いてあった。mkboot1の方は、ダンプした内容の うち必要な部分だけを、make-system-imageを使ってダンプするようになってた。
そうか、コンパイルして実行スピードを稼いでいるんだな。
> car
#.car
> caar
#fn("6000r1|MM;" [] caar)
> environment
#fn(environment)
> (define (hoge x y) (* x y))
#fn("7000r2|}T2;" [] hoge)
#.で始まるのはプリミティブな手続き。#fnは合成関数と言うか、プリミティブ手続きを 使って組み立てた手続き。そのうち、コンパイル出来るものは、VMコードが併記されてる んだな。
その場で定義した関数もコンパイルされるとな。これってJITですよ。
etc
ブラウザで動く「Windows 1.01」と「Windows 98」で遊んでみた
サポートしてるOSの中に、昔懐かしい万次郎ことArchLinuxが有ったので試してみた。 そしたら、いきなりrootが起動してきて、ちょろっとdirの中が窺えた。 cpuidなんてコマンドが有ったので、実行してみると、
CPU 0:
vendor_id = "GenuineIntel"
version information (1/eax):
processor type = primary processor (0)
family = Intel Pentium 4/Pentium D/Pentium Extreme Edition/Celeron/Xeon/Xeon MP/Itanium2, AMD A
thlon 64/Athlon XP-M/Opteron/Sempron/Turion (15)
model = 0x6 (6)
stepping id = 0x3 (3)
extended family = 0x0 (0)
extended model = 0x0 (0)
(simple synth) = Intel Pentium 4 (Cedar Mill) / Pentium Extreme Edition (Presler) / Pentium D (Presler)
/ Xeon (Dempsey) / Xeon (Tulsa) / Celeron D (Cedar Mill), 65nm
miscellaneous (1/ebx):
process local APIC physical ID = 0x0 (0)
cpu count = 0x1 (1)
CLFLUSH line size = 0x8 (8)
brand index = 0x0 (0)
brand id = 0x00 (0): unknown
feature information (1/edx):
x87 FPU on chip = true
virtual-8086 mode enhancement = true
debugging extensions = false
:
へぇー、ってなものだ。
ピボットテーブルとは何か──「そもそも、何をする機能か」を理解する
こちらはRとかJuliaとかパンダのデータフレーム相当品でしょうか？ 昔Excelで ちらちらと使った覚えがあるな。懐かしい。