flisp in julia
前回の枕に、Haskellは絶滅危惧言語のひとつに挙げられているなんて記事を引用した。 そんな中、 『プログラミングHaskell 第2版』 が目出度く出版された。一版は持っているんで、記念に購入してdiffを取ってみますかね。
この種本は、 Programming in Haskell 2nd Edition になる。あっ、目次が出てた。
そして、スライドとコードが提供されてた。眺めてみるかな。復習の意味を込めて。
ざっとスライディングしたら、昔はhugsを使っていたけど、今回はghc(i)に切り替わっていた。問題の種をまき散らす（であろう）パッケージは、ありきたりのものばかりを採用。上手に地獄を避けている。で、いざまともな事をしようとすると、地獄行。こういう事はHaskellに限った事では無いんだけど、過去にすごくいじめられた記憶が有るので、トラウマになってるのさ。
ビデオも有るな。ググルさん、頑張ってリアルタイム翻訳をお願い致しますだ。オリンピックも近い事だし、需要が増大しますよ。
flisp app
前回ちょびっとやった、juliaに組み込まれているlispに注目してみる。ソースをざっと見したら、Cフラフラ語とかのものに並置して、xxx.scmが散見された。その親分はいかにもって名前に なってたぞ。
(base) cent:src$ ls *.scm ast.scm julia-parser.scm match.scm bin2hex.scm julia-syntax.scm mk_julia_flisp_boot.scm jlfrontend.scm macroexpand.scm utils.scm
親分のjlfrontend.scmを呼び出して、これはと言う関数に、julia語を喰わせてみる。起動直後に、jlfrontend.scmをロードしてみたけど、試してみただけです。既に組み込まれているので、改めてロードする必要はありません。
debian:src$ julia --lisp
; _
; |_ _ _ |_ _ | . _ _
; | (-||||_(_)|__|_)|_)
;-------------------|----------------------------------------------------------
> (load "jlfrontend.scm")
#fn("<000r3e0g7a=6J0c1c2c3c4c5}g23231}g2|46;g7b2=680e6|41;^;" [*depwarn-opt* #fn(julia-logmsg)
1000 depwarn #fn(symbol)
#fn(string)
error] frontend-depwarn)
> (jl-parse-string "a = 123" "hoge.jl")
(= a 123)
> (jl-parse-string "foo(x) = x + 1234" "hoge.jl")
(= (call foo x) (block (line 1 hoge.jl) (call + x 1234)))
いきなりhoge.jlが出てきたけど、この場では、ダミー？なソース名だ。なんとなく、コンパイルして結果をS式で返している事が分かる。
今度は、こんな手続きに注目。julia語のソースファイルを与えると、それをまとめてコンパイル（と言うか、抽象表現に）してくれるっぽい。
(define (jl-parse-file filename) (trycatch (jl-parse-all (open-input-file filename) filename) (lambda (e) #f)))
実験材料を、前回やったスペクトラグラムを表示しるやつにしてみる。一応、行番号付きで再掲しとくね。
[ham@cent SND]$ cat -n snd.jl
1 using WAV
2 using DSP
3 using Gnuplot
4
5 x, fs = wavread("S.wav", format="native");
6 x, fs = convert(Vector{Float64}, vec(x)), convert(Int, fs);
7 winsize = 512;
8 hopsize = 256;
9 S = spectrogram(x, winsize, winsize-hopsize, fs=fs, window=hanning);
10
11 p = power(S);
12 q = log10.(p');
13 t = time(S);
14 f = freq(S);
15 @gp( "set nokey", "set grid", xlabel="Time [S]", ylabel="Freq [Hz]",
16 # "unset xtics", "unset ytics",
17 # "set xtics('3' 100, '6' 200, '9' 300)",
18 q, "with image")
19
20 # save(term="png", output="DSPspect.png")
変身ーー、じゃなくて、変換ーー。
> (jl-parse-file "snd.jl")
(toplevel (line 1) (using (|.| WAV)) (line 2)
(using (|.| DSP)) (line 3) (using (|.| Gnuplot)) (line 5)
(toplevel (= (tuple x fs) (call wavread "S.wav"
(kw format "native"))))
(line 6) (toplevel (= (tuple x fs)
(tuple (call convert (curly Vector Float64)
(call vec x))
(call convert Int fs))))
(line 7) (toplevel (= winsize 512)) (line 8)
(toplevel (= hopsize 256)) (line 9)
(toplevel (= S (call spectrogram x winsize
(call - winsize hopsize)
(kw fs fs)
(kw window hanning))))
(line 11) (toplevel (= p (call power S))) (line 12)
(toplevel (= q (|.| log10 (tuple (|'| p))))) (line 13)
(toplevel (= t (call time S))) (line 14)
(toplevel (= f (call freq S))) (line 15)
(macrocall @gp (line 15 snd.jl) "set nokey" "set grid"
(= xlabel "Time [S]")
(= ylabel "Freq [Hz]") q "with image"))
行儀悪く、toplevelに各行を置いているんで、それぞれにtoplevelで定義されましたって注釈が入っているな。
今度は、関数定義が有るやつ。
(base) cent:tmp$ cat -n pjs.jl
1 using PlotlyJS
2
3 function heatmap2(q)
4 trace = heatmap(
5 x=1:size(q)[1],
6 y=1:size(q)[2],
7 z=q
8 )
9 plot(trace)
10 end
11
12 heatmap2(q)
変換ーーー。
> (jl-parse-file "pjs.jl")
(toplevel (line 1) (using (|.| PlotlyJS)) (line 3)
(function (call heatmap2 q) (block (line 4 pjs.jl)
(= trace (call heatmap (kw x (call : 1 (ref (call size q) 1)))
(kw y (call : 1 (ref (call size q) 2)))
(kw z q)))
(line 9 pjs.jl)
(call plot trace)))
(line 12) (call heatmap2 q))
トップレベルでの定義は、１行目と３行目と12行目から始まるやつが３つあるよとな。そのうちの3行目からのやつは、関数定義ですよ。この関数の中で使われてる関数heatmapの引数は、キーワード引数ですよって具合に解析してくれた。
今度はforやwhileの元締めであるifが、どうコンパイルされるか確かめてみる。lisp的にはcondに翻訳されるのだろうか？ プチ興味が有るぞ。それから、翻訳系の元締めであるjulia-parseを使ってみよう。
> (julia-parse "aa(n) = if (n>12) n+34 else n-56 end")
(= (call aa n) (block (line 1 none) (if (call > n 12)
(block (line 1 none)
(call + n 34))
(block (line 1 none)
(call - n 56)))))
ふむ、普段lisp屋さんが書くコードと一致するやつが出てきた。lisp屋さんは、人間パーサーなんだなあ。
このjulia-parseは何処にあるかと探してみたら、julia-parser.scmで定義されてた。これが、lisp脳の入り口になってるとな。
;; --- main entry point ---
;; can optionally specify which grammar production to parse.
;; default is parse-stmts.
(define (julia-parse s . production)
(cond ((string? s)
(apply julia-parse (make-token-stream (open-input-string s))
production))
((port? s)
(apply julia-parse (make-token-stream s) production))
((eof-object? s)
s)
(else
;; as a special case, allow early end of input if there is
;; nothing left but whitespace
(skip-ws-and-comments (ts:port s))
(let skip-loop ((tok (peek-token s)))
(if (or (eqv? tok #\newline) )
(begin (take-token s) (skip-loop (peek-token s)))))
(if (eof-object? (peek-token s))
(eof-object)
((if (null? production) parse-stmts (car production))
s)))))
lisp屋さんなら、ifの連鎖を避けてcondを使うのは当たり前。condが姿を変えてcase文とかswitch文になってるんだな。lispは正に、コンピューター言語の母語ですなあ。
beginはscheme系の方言だけど、その元はlisp語のprogn。これらがC語では、{...}と言うフレーズに姿を変えて生き残っているとな。
兎も角、このjulia-parser.scmが、脳味噌の中身になるんだな。自分の脳を解剖してくみたいで、こわいな。（こわいってのは、北海道言葉ってか方言で、大変だーって意味だったよな。うろ覚えスマソ）
正面きって、解剖していかなくても、怒らせて反応を見るって方法で内部を推測出来る（かな）。最後のendを省略して、様子を見て見る。
> (julia-parse "aa(n) = if (n>12) n+34 else n-56")
error: incomplete: "if" at none:1 requires end
#0 (error ("incomplete: \"if\" at none:1 requires end"))
#1 (parse-resword/lambda/lambda)
#2 (parse-resword/lambda)
#3 (parse-resword [#<eof> #<io stream> #f #f #f] if)
#4 (parse-factor-with-initial-ex
[#<eof> #<io stream> #f #f #f] if)
:
#23 (parse-docstring [#<eof> #<io stream> #f #f #f]
#fn("7000r1e0|e142;" [parse-assignment parse-comma] parse-eq))
#24 (parse-Nary [#<eof> #<io stream> #f #f #f]
#fn("7000r1e0|e142;" [parse-docstring parse-eq])
(#\;) toplevel #fn("6000r1|c0=;" [#\linefeed]) #f)
#25 (parse-stmts [#<eof> #<io stream> #f #f #f])
分かり易い奴。どういう風に考えたかって思考の筋道が出てきた。こういう手がかりがあるのが嬉しい。(但し、lispはスタックトレースを最後に死んじゃうみたいだけど）
その点、今流行りのML（マシンラーニング）は、全く面白みが無いな。幾ら将棋でプロに勝てるようになったって、どういう思考方法をしたか、説明出来ないもの。 人間が既に、人工知能の下僕になっちまって、あーでもないこうでもないと一生懸命に推測してる。人間の尊厳は何処へ行った！
julia> aa(n) = if (n>12) n+34 else n-56
juliaレベルで最後のendを省略すると、まだ式が完成してないって認識で、入力を促されました。lispのつっけんどんな所を補ってくれてるのね。
juliaとflispの橋渡し
そんじゃ、このflispの関数群とjuliaシステムの橋渡しに注目してみる。ast.cっていういかにもってファイルがsrcの中に有った。冒頭を覗き見。
/* AST interface to front-end, obtains and translates syntax trees */ #include "julia.h" #include "julia_internal.h" #include "flisp.h" #include "julia_assert.h"
juliaとflispのヘッダーファイルを取り込んでる。やっぱり、架け橋なんだな。ならば、上で使ったflispの関数を呼び出しているはず。
なお、flisp側では、flisp.cの中で、platform.hをインクルードしてる。これは、juliaをコンパイルする際に自動作成される（はず）もので、juliaとflispを結ぶ、flisp側の参照ファイルだ。
(base) cent:src$ grep jl-parse-file ast.c
ast = fl_applyn(fl_ctx, 1, symbol_value(symbol(fl_ctx, "jl-parse-file")), f);
どうやら、fl_applynが元締めみたいだ。今度は、それで引いてみる。
(base) cent:src$ grep fl_applyn ast.c
fl_applyn(fl_ctx, 0, symbol_value(symbol(fl_ctx, "__init_globals")));
fl_applyn(fl_ctx, 1, symbol_value(symbol(fl_ctx, "__start")), fl_cons(fl_ctx, fl_ctx->NIL,fl_ctx->NIL));
:
このfl_applynを介してflisp側の関数を呼んでいるとな。勿論呼び出すflisp側には相当の手続が備わっていなければならない。juliaのシステムを作る時、flispを作り、そこにjfrontend.scm等を組み込み。それをダンプ。そのダンプされたものを、juliaに取り込んでいるんだな。
inside flisp
そんじゃ、src/flispの中に潜ってみるか。聞く所によると、初期のjuliaの時、lispとしてはguileを使っていたとか。バグを見つけても、さっぱり対応してもらなかったので、業を煮やして、自作のlispを使う事にしたそうだ。とても小さいlispなんで、頭にfemtoって接頭語をつけた。フェムトってピコの 1/1000 ね。10^-15 と、とてつもなく小さいって意味。
flisp.cの冒頭部分
a compact interpreter for a minimal lisp/scheme dialect
characteristics:
* lexical scope, lisp-1
* unrestricted macros
* data types: 30-bit integer, symbol, pair, vector, char, string, table
iostream, procedure, low-level data types
* case-sensitive
* simple compacting copying garbage collector
* Scheme-style varargs (dotted formal argument lists)
* "human-readable" bytecode with self-hosted compiler
extra features:
:
by Jeff Bezanson (C) 2009
Distributed under the BSD License
flispのreplには便利な機能が全くついていないので、下記のようにrlwrapをかませて起動する。履歴を辿って編集実行が出来るようになる。 2016年の春にもjuliaがらみで、随分femtolispを探っていた。そして、environmentって言う、登録されてるシンボルを列挙する関数を見つけたものだから、補完用のデータを作ったのであった。
(base) cent:femtolisp$ cat >z.lsp
(let ((aa (environment)))
(while (not (null? aa))
(princ (car aa) "\n")
(set! aa (cdr aa))))
(base) cent:femtolisp$ ./flisp z.lsp | sort > ~/.flisp_completions
z.lspでシンボルを列挙。それを並び変えて、補完データにする。rlwaapは、所定のドットファイルが有ると、補完機能が働く。
(base) cent:femtolisp$ rlwrap -pGreen ./flisp > (m ;; mTAB すると、mで始まるシンボルを列挙してくれる。 macrocall? map max memv mod0 macroexpand map! member min make mark memq mod
注意深い人は、julia --lispで起動する場合はどうすんねん？と思うでしょう。上記のような事は出来ないので、何とかして補完データを採取してください。（投げ槍スマソ）
ソースをちら見したら、直近の実行結果が that に残っている事を発見。
[ham@cent ~]$ julia --lisp > (car '(a b c)) a > that a > (cdr '(a b c)) (b c) > that (b c)
rlwrapが有れば、大して嬉しくはないか。では、これはどうよ？
femtolisp
lisp単体として遊ぶなら、 juliaに内蔵のflispを離れて、その元になったfemtolispを頂いてくるのが得策。
(base) cent:~$ git clone https://github.com/JeffBezanson/femtolisp.git
lltってdirの中で、make debug。続いてtopでも make debug すれば、gdbから操れる特製のlispが出来上がる。
makeする時には使われないんだけど、いかにもってのが有ったんで実行してみた。
(base) cent:femtolisp$ ./bootstrap.sh Creating stage 0 boot file... Creating stage 1 boot file... Testing... cd tests && ../flisp unittest.lsp all tests pass
ソース見ろ。
./flisp mkboot0.lsp system.lsp compiler.lsp > flisp.boot.new mv flisp.boot.new flisp.boot ./flisp mkboot1.lsp
mkboot0.lspでは、引数のファイル(system.lsp,compiler.lsp)を読み込んで、小刻みにコンパイルして吐き出す。mkboot1.lspでは、スクリプト内部から読み込んで、全体をダンプするって事をやってる。これで、初期はインタープリタで動いていたのが、コンパイルされたイメージに置き換わるとな。なかなか巧妙な仕組みだ。
なお、このflisp.bootは、flispが起動した時に使われる。
tiny
このfemtolispソース群には、その元となったtinyと言うlispが付属してる。わずか1000行で、実装されてるので、読むのも楽しい。
檻から、盆休み中に読まなくなった昔の本を整理したよなんていう人がいた。そうかと思うと、母が亡くなった時、遺品整理で、必要な物以外は全部ゴミって方針で棄てた人もいた。断捨離って言うんですかね。
Lisp界では、そういうのガーベッジコレクション略してGCと言うんですよって、話を振った。 丁度良い機会なので、tinyLispに実装されてる compacting copying garbage collectorを、読み解いてみる。
その前に簡単にLispの紹介。 C語の教科書に出て来る、単方向リンクリストで、データもプログラムも表現する。データの入れ物が、チェーン状に並んでるんだ。
その定義
typedef struct {
value_t car;
value_t cdr;
} cons_t;
構造体のメンバー名に、carとかcdrって意味不な名前が付いてるけど、これはlisp界の由緒ある名前。car部にはデータとかプログラム（のポインター）が通常入る。cdr部は次のcons部へのポインターが入る。
これだけじゃ、データや関数に名前さえ付ける事が出来ないので、シンボルと呼ばれる構造体を用意する。
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;
メンバーのbindingには、データを表すポインター（cons_t構造体へのリンク）と、もう一つは内部関数へのポインターがある。（用途によって使い分ける事にしてる） それと、ユーザーが認識出来る名前だ。なお、left/rightってメンバーも要るけど、これは名前を高速で検索出来るように２分木を実現するのに使うだけで、本質ではない。
hoge -> (1 -> 2 -> 3 -> 4 -> 5 -> nil) ;; nilは終了記号 symbol領域 cons領域
リスト(1 2 3 4 5)は、cons領域に格納され、それをシンボル領域にあるhogeって名前で参照出来るようになる。
symbol/cons共、構造体なので作る時はmallocで領域をOSから貰ってくる。使い終わったらfreeして返却。これではメモリー管理をユーザーに押し付ける事になり負担が大きすぎる。そこで、使い終わったらそのエリアを自動回収したい。これがGCの主目的だ。
使い終わるってのは、hoge -> (6 7 8) みたいな場合だ。今までの(1 2 3 4 5)は、何処からもポインティングされていない（アクセス不能と言い換えられる）不用品。
どうするか？ cons構造体を入れる大きな領域を２つ用意して、片方から使っていく。一杯になったら、新しい方に切り替えて、古い方に残ってる大事なデータを新しい方にコピーする。 また、新しい方が一杯になったら、古い方に切り替えて、アクセス出来るデータを古い方にコピーする。この繰り返し。
じゃsymbol領域はどうする？ 名前なんて、めちゃくちゃ生まれるわけではないので、回収はせずに放置する。（同じ名前は再利用する）
下記は、GCの状況をモニター出来るようにして起動した図。
> (base) cent:tiny$ ./lisp gc found 2944/8192 live conses gc found 3134/8192 live conses gc found 3492/8192 live conses gc found 4226/8192 live conses Welcome to femtoLisp ---------------------------------------------------------- >
プロンプトが出て使えるようになるまで、４回GCが実行されてるって事が分かる。8192個のcons領域(cell領域とも言う）が用意されてて、それを使い果たしたので、１回目のGCを実行。そしたら、有効なcellが2944個でした。プログラムの実行が進むにつれて、何回かGCされ、最後はcell領域の約半分が使われましたって事を表している。
なお、起動時には、lisp語で書かれたライブラリィーが自動読み込みされるんで、上記のようになるんだ。実用的にはcell領域が絶対的に不足してるんで、最初から広大な領域を用意する事が多い。
そんじゃ、コードを追ってみる。
static u_int32_t heapsize = 64*1024; //bytes
void lisp_init(void)
{
int i;
fromspace = malloc(heapsize);
tospace = malloc(heapsize);
curheap = fromspace;
lim = curheap+heapsize-sizeof(cons_t);
NIL = symbol("nil"); setc(NIL, NIL);
:
プログラムが起動して真っ先に呼ばれる部分。fromspaceと言うのとtospaceと言う２つのエリアをOSから貰ってきて、最初は、fromspaceを使うって設定。同時に使えるリミットを設定。 これは、cons領域の事ね。
このconsエリアから、領域を切り取って使う部分は、下記
static value_t mk_cons(void){
cons_t *c;
if (curheap > lim)
gc();
c = (cons_t*)curheap;
curheap += sizeof(cons_t);
return tagptr(c, TAG_CONS);
}
static value_t cons_(value_t *pcar, value_t *pcdr){
value_t c = mk_cons();
car_(c) = *pcar; cdr_(c) = *pcdr;
return c;
}
切り出し元がリミットを越えていたらgcを発動して場所を作る。そうでなかったら、現在の空き地をｃに得ておいて、cons一個分、切り出し元を進める。得た空き領域はcons用途なので、それ用にマークを付けておく。こうして得たエリアにconsとか言う内部関数でcar値、cdr値をセットしていく。
一方、symbolの登録の大本は
static symbol_t *mk_symbol(char *str){
symbol_t *sym;
sym = (symbol_t*)malloc(sizeof(symbol_t) + strlen(str));
sym->left = sym->right = NULL;
sym->constant = sym->binding = UNBOUND;
strcpy(&sym->name[0], str);
return sym;
}
登録したい名前strを受け取ってから、symbol構造体とサイズ+strの長さ文のエリアをOSから貰ってきて、初期化（この名前にはまだデータが代入されてません）をしてる。ここのmallocに対するfreeでのエリア解放は行われない。
それじゃ、いよいよ本命のgc。長くなるので、主要部分のみ
void gc(void){
static int grew = 0;
unsigned char *temp;
u_int32_t i;
curheap = tospace;
lim = curheap+heapsize-sizeof(cons_t);
for (i=0; i < SP; i++)
Stack[i] = relocate(Stack[i]);
trace_globals(symtab);
#define VERBOSEGC
#ifdef VERBOSEGC
printf("gc found %d/%d live conses\n", (curheap-tospace)/8, heapsize/8);
#endif
temp = tospace;
tospace = fromspace;
fromspace = temp;
:
consを取り出すエリアをtospaceって新しいのに切り替える。そして、新しい方に対してリミットを設定。自前で用意したStackと言う配列（計算用エリア）内にあるデータをrelocateって関数で、引っ越し。続いて、trace_grobalsで、symbolエリアをスキャンして、引っ越し。
この時点での、cons領域の利用状況を報告。最後に、エリアの名前交換して次回に備える。 これが主要部分だ。後非常に重要な引っ越し手続が残ってたな。
static value_t relocate(value_t v){
value_t a, d, nc;
if (!iscons(v))
return v;
if (car_(v) == UNBOUND)
return cdr_(v);
nc = mk_cons();
a = car_(v); d = cdr_(v);
car_(v) = UNBOUND; cdr_(v) = nc;
car_(nc) = relocate(a);
cdr_(nc) = relocate(d);
return nc;
}
引っ越しする時には、住所変更するでしょ。それと同じ事を行う。cons領域内でリンクしてる先は、旧エリアだ。それをそのまま移してしまうと、新しいエリアに切り替えても古い方に行っちゃう。その対策。
対象はconsだけね。mk_consで、新しい方のcellを一つ用意。古い方のcar値とcdr値を取り出す。古い方のcar値を無効に設定。cdr値を新しい方に張り替え。 リストは再帰的なので、再帰呼び出しして、徹底的に書き換え。 これで、consエリアの引っ越し完了。
残るは、symbol領域からconsエリアを指している場合の対処。
static void trace_globals(symbol_t *root){
while (root != NULL) {
root->binding = relocate(root->binding);
trace_globals(root->left);
root = root->right;
}
}
これを呼び出す時の引数は、シンボル領域の総本山を示す、systabだった。これを起点に、cons領域を指すポインターをrelocateを使って更新。２分木なんで、左側を再帰的に辿り、今度は右側に切り替えてから、更新。
こうして、長いgcが行われるのさ。
pythonは、こういう方法を取っていない。gcに長大な時間がかかるのを嫌ってね。 それぞれのオブジェクト（上の例だと、(1 2 3 4 5)みたいなデータ）を使った時にカウンタを増やす。使わなくなったらカウンターを減らす。カウンターがZEROなら、何処からも利用されていないので、即回収。こういう方法をリファレンスカウンター方式のGCと言う。GCが一極集中しないので使っててGCの為に一瞬ハングしたようにはならない。ユーザーからは使い心地が良いと評判。
でも、この方式があだになって、pythonの高速化を難しくしてる面もある。銀の玉は無いんだよって事です。
copy方式のGCを、伊勢神宮の式年GCとSICPの訳者である和田先生はおっしゃった。オイラーはこの方法を焼畑農業と思った。そして、もう一つ比喩を思い付いた。
cons領域の事をcell領域とも言うってのからの連想。cellって細胞の意味。細胞ってDNAと言う大事な物を抱えこんでいる。で、DNA遺伝方式ってどうよ。
上で出てきたfromspaceとかは、細胞の集まり、要は生命体。これが肥大して寿命が尽きたら、大事な物を持って別の個体に移動。ああ、これってウィルスとも言うな。
こういう馬鹿話はいい加減にして、由緒正しくSICPの該当箇所を読んでみるか。