femtolisp, macro debug

独自CPU開発で学ぶ コンピュータのしくみ なんて本を買った。こういうのは、図書館に置いてないからね。たまにはいいよね。

FPAGを使って、オレオレCPUを作っちゃう話。ハードが出来てもソフトなければただの石って事で、 ハード半分、ソフト(C語開発環境)半分にページが割かれている。

手元に届いたばかりで通読も済んでいなけど、前半部分の感想を少し書いてみる。

ハード担当者1人とソフト担当者1人の2人体勢。それでも、打ち合わせ内容をそれぞれ 独自に解釈する所が有って、苦労したとか。仕様書はきちんと書こうって反省されてた。

そうだよね。ハードもプログラムを書く事でFPGAの中を構成する時代だから、ソースが 仕様書って強弁出来そうだけど、やっぱり仕様書大事、オイラーもそう思う。

ハード・ソフトと綺麗に分担が分かれていたようだけど、どうせキーボードを叩くだけ だから、二人プログラミングって出来なかったものでしょうか? そしたら、どちらも理解出来、意志疎通にうってつけだと思うのだけど、駄目?

虫が沸きだした時、ハードが悪い、動かんのはソフトのせいだと、醜いなすりつけを 経験した事がある。その時は、両者の境界線で自分の正当性を証明したものだ。 ソフトが出してくる命令をオシロで捉えて、ハード読み出しの順序が間違ってるとか 主張したり、そのうちに、ソフトが命令を出してくれないと、ハードの信号が追えなく なったり。

なんやかんやで、ハード/ソフトって垣根が段々と無くなっていった覚えがある。 いがみ合うんじゃなくて、協調体制が自然に出来上がって行ったんだろうね。

そんな経験してるから、ハードもソフトも一緒じゃんって、ある時から思えるように なった。著者の2人も同じような気持ちだろうね。

これから先の読書が、楽しみであります。

(environment)

前回からの続きでflispの観光をします。

environmentってので、登録されてる関数類を拾い出してダンプしてた。その選択基準が systemlisp.lspの中でmake-system-imageって関数ので定義されてた。

        (excludes '(*linefeed* *directory-separator* *argv* that
                               *print-pretty* *print-width* *print-readably*
                               *print-level* *print-length* *os-name*)))
           :
      (let ((syms
             (filter (lambda (s)
                       (and (bound? s)
                            (not (constant? s))
                            (or (not (builtin? (top-level-value s)))
                                (not (equal? (string s) ; alias of builtin
                                             (string (top-level-value s)))))
                            (not (memq s excludes))
                            (not (iostream? (top-level-value s)))))
                     (simple-sort (environment)))))

フィルターの条件がlambdaを使った無名関数としてまとめられている。値が設定されてて、 定数ではなくて、ビルトイン関数でないもの、もしくは、エイリアスじゃないもの。かつ 前に挙げたブラックリストや入出力じゃないもの。この論理説明で、東大の入試数学は、 突破できますかね?

こういうものを、environment関数が返す結果から拾い出せって事。environmentの元ネタは 大体想像付くけど、一応確認しておく。

static void global_env_list(symbol_t *root, value_t *pv)
{
    while (root != NULL) {
        if (root->name[0] != ':' && (root->binding != UNBOUND)) {
            *pv = fl_cons(tagptr(root,TAG_SYM), *pv);
        }
        global_env_list(root->left, pv);
        root = root->right;
    }
}

value_t fl_global_env(value_t *args, u_int32_t nargs)
{
    (void)args;
    argcount("environment", nargs, 0);
    value_t lst = FL_NIL;
    fl_gc_handle(&lst);
    global_env_list(symtab, &lst);
    fl_free_gc_handles(1);
    return lst;
}

builtins.c内に有った。やっぱりsymtabと言う名前の登録簿をスキャンしてる。スキャンは、 左側、次に右側というようにやってるな。fl_gc_handleも呼んで、gc中のstackも対象に 加えているように見受けられるんだけど、gcは、STOP the World じゃ無かったっけ?

macro debug

ああ、top_level_valueを忘れていた。gdbで追っている時、toxxxとかのマクロが よく出てくる。下記のように代入してくれていれば、結果がどうなったか簡単に 確認出来るんでいいんだけど、式中に埋め込まれたマクロの結果って、gdbで 確認する方法は有るのかな? macro expand xxx(n) で、行けるか、要実験。

DEBUGFLAGS = -O0 -gdwarf-2 -g3 

デバッグフラグを上記に設定して、gccでコンパイルする。FreeBSDのcc(clang)は、 十分にフラグの意味を理解してくれない。

(gdb) p e
$1 = 679602371
(gdb) info macro issymbol
Defined at /home/sakae/femtolisp/tiny/lisp.c:63
#define issymbol(x) (tag(x) == TAG_SYM)
(gdb) macro expand issymbol(e)
expands to: (((e)&0x3) == 0x2)
(gdb) p (((e)&0x3) == 0x2)
$2 = 0

こんな具合に、ちゃんと展開した。これで、lispみたいにTAGが埋め込まれたのも 追跡が楽になるな。とか言ってたら、穴が有ったぞ。

(gdb) macro expand eval(expr, &Stack[SP-1])
expands to: ((((expr)&0x3)<0x2) ? (expr) : eval_sexpr((expr),&Stack[SP-1]))
(gdb) macro expand-once eval(expr, &Stack[SP-1])
Expand-once not implemented yet.

lisp/schemeには、macro-expandで、展開したらまたマクロが出てきたって時に、それも 徹底的に展開しちゃうmacro-expandってのと、1回展開して終わりって、macro-expand-1 ってのが有る。gdbには後者相当が、名前まで決めてあるのに実装されていない。

これを実装しようとすると、Cコンパイラー系のCPPを持ってくる必要がありそうなんで、 多分難工事を予想して、予算が付かないんだろうね。

安倍ちゃん、ODAで予算を捻出してやれよ。世界の開発者達から感謝されるぞ。何?ODAは、 自国の企業に利益をもたらす隠れ蓑だって。そうさ、最近厳しい状況にあるTとかFへの隠れ支援で、 そちらに仕事が廻るように外務大臣をGNUに派遣して、話を付けてくればいいのさ。

それが出来ないようだと、アプルの旦那がスポンサーになってるLLVMがLLDBプロジェクトを支援して、 これを先に実装しちゃうぞ。多分きっとね。

#define eval(e, env) ((tag(e)<0x2) ? (e) : eval_sexpr((e),env))
#define tag(x) ((x)&0x3)

ソースの関連部分が上記。そして、gdb用の情報を付け足した実行ファイルから、stringsで、 関連部分を検索すると

eval(e,env) ((tag(e)<0x2) ? (e) : eval_sexpr((e),env))
tag(x) ((x)&0x3)

ってな具合に、情報を持ってるんで、直ぐに実現出来ると思うんだけどなー。 何なら、flisp付属のsystem.lspから関連部分を提供しようか?

(defun macrop (e) (and (consp e) (eq (car e) 'macro) e))
(defun macrocallp (e) (and (symbolp (car e))
                           (boundp (car e))
                           (macrop (eval (car e)))))
(defun macroapply (m args) (apply (cons 'lambda (cdr m)) args))

(defun macroexpand-1 (e)
  (if (atom e) e
    (let ((f (macrocallp e)))
      (if f (macroapply f (cdr e))
        e))))

macro-expandって、Lisp一族が発明した。便利なのでC語も取り入れた。ならば、C語の コンパイラーでは、展開したのを実行代わりにコンパイルって事をするんだな。展開した 所で結果を確認(表示)出来る。

gcc -E lisp.c
 :
value_t toplevel_eval(value_t expr)
{
    value_t v;
    u_int32_t saveSP = SP;
    (Stack[SP++] = (NIL));
    v = ((((expr)&0x3)<0x2) ? (expr) : eval_sexpr((expr),&Stack[SP-1]));
    SP = saveSP;
    return v;
}
  :

元ソースはこちら。

value_t toplevel_eval(value_t expr)
{
    value_t v;
    u_int32_t saveSP = SP;
    PUSH(NIL);
    v = eval(expr, &Stack[SP-1]);
    SP = saveSP;
    return v;
}

マクロは大文字にして目立つようにする、なんてのは単なる口約束。普通の関数のように (上の例ではeval(...)が相当)見えても、実体は、マクロって事が十分にあるからね。 C語も言語内DSLが十分に浸透してますよ。なお、C語のマクロについての使い方とかに ついては、C言語のマクロの詳細についてを 参照。他にも、C言語 マクロ 落とし穴とかで検索すると、いやという程引っかかってくる。みんな、 一度は穴に落ちた口だな。

ああ、関数ぽいのは、関数のようにgdb上で表示出来るね。DSLだから。

      apply_builtin:
          nargs = SP - saveSP - 2;
  =>      switch (intval(f)) {
          // special forms
          case F_QUOTE:

ここまでgdbで実行を進めてきて、さてと言う時、

(gdb) p f
$3 = 73
(gdb) p intval(f)
$4 = 18

こんな風に計算してくれるんだけど、この結果の18を、caseのラベルに戻す事って 出来ないの? まあ、走ってみれば分かるけど。。。走った先に何があるか、あらかじめ 知っておきたいって欲望もあるな。欲望は際限無いのであります。

pop

思わずmacro割り込みが遭ったのでpopしてcontinue です。

static value_t fl_top_level_value(value_t *args, u_int32_t nargs)
{
    argcount("top-level-value", nargs, 1);
    symbol_t *sym = tosymbol(args[0], "top-level-value");
    if (sym->binding == UNBOUND)
        fl_raise(fl_list2(UnboundError, args[0]));
    return sym->binding;
}

大きい方のflispは、登録簿も進化してた。構造体もメンバーが増えているけど、必要に なった時に参照する事にしよう。

typedef struct _symbol_t {
    uptrint_t flags;
    value_t binding;   // global value binding
    struct _fltype_t *type;
    uint32_t hash;
    void *dlcache;     // dlsym address
    // below fields are private
    struct _symbol_t *left;
    struct _symbol_t *right;
    union {
        char name[1];
        void *_pad;    // ensure field aligned to pointer size
    };
} symbol_t;

VM

system.lspを見てたら、function:code なんてのが出てきた。何じゃいこれ。例によって マニュアルの類は一切無いのでソース嫁の世界。手探り状態。で、手がかりをやっと 見つけた。コンパイルされた関数のVMのコードを表示してくれるっぽい。

> (typeof car)
builtin

> (typeof caar)
function

> car
#.car

> caar
#fn("6000r1|MM;" [] caar)

> (function:code caar)
"\x06\x00\x00\x00B\x01L\x1d\x1d\v"

鍵括弧の中が空だけど、本来は何が入るのだろう? もう少し試行錯誤してみる。

> (typeof environment)
builtin

> (typeof oblist)
function

> environment
#fn(environment)

> oblist
#fn("6000r0c040;" [#fn(environment)] oblist)

> (function:code oblist)
"\x06\x00\x00\x00B\x003\x00\x04\x00\v"

oblistはenvironmentと同義に定義したから、そっくりそのまま、元の定義を参照 しますよって事かな。

function:codeの方は、flisp.cの中の関数、fl_function_codeが担当。核心は、fn_bcodeに 委譲してる。定義を見ると、マクロだよ。マクロは、flisp.hに有り。

#define fn_bcode(f) (((value_t*)ptr(f))[0])
#define fn_vals(f) (((value_t*)ptr(f))[1])
#define fn_env(f) (((value_t*)ptr(f))[2])
#define fn_name(f) (((value_t*)ptr(f))[3])

対象にしてる構造体は、下記のようだ。

typedef struct {
    value_t bcode;
    value_t vals;
    value_t env;
    value_t name;
} function_t;

bcodeとかnameは、想像つくけど、valsって何を入れておく? envの方はクロージャ要。 苦労じゃなあ。さて、どうしてくれよう。

コンパイルとその逆で姿を変える

VMって事でflisp.cを見ると、長い々関数、apply_cl に、その手のオペコードが沢山出て来る。 VMの心臓部である実行機関に違いない。この関数の前に、APIの説明が置いてあった。

/*
  stack on entry: <func>  <nargs args...>
  caller's responsibility:
  - put the stack in this state
  - provide arg count
  - respect tail position
  - restore SP

  callee's responsibility:
  - check arg counts
  - allocate vararg array
  - push closed env, set up new environment
*/

ちゃんとコメントしてるって事は、重要だよって言ってるんだな。ああ、引数の配置に 関して、こんなのも

/*
  argument layout on stack is
  |--required args--|--opt args--|--kw args--|--rest args...
*/

ここまでは良いけど、膠着状態。一歩も先へ進まん。こういう時はトラックバックしましょ。 俗な言葉では、別の道を試してみましょだ。

付属のファイルに、compiler.lspが有ったな。きっと、VM用にソースのscheme語をコンパイルしてるに違いない。 ざっと見で、zappingしたら、750行ぐらいある。ちと頭から見てく根性無し。見る所を 絞り込めればいいな。で、あたりを見回すと、mkboot0.lspに、楽しい事が書かれていた。

(define (compile-file inf)
  (let ((in  (file inf :read)))
    (let next ((E (read in)))
      (if (not (io.eof? in))
          (begin (print (compile-thunk (expand E)))
                 (princ "\n")
                 (next (read in)))))
    (io.close in)))

(for-each (lambda (file)
            (compile-file file))
          (cdr *argv*))

引数で渡されるschemeファイルを、順次compile-fileでコンパイルしてね。結果は標準 出力に出てくるよって事。この核心は、S式を一つづつ読み込んで、compile-thunkに 渡す事の繰り返し。

ならば、自分で実験しろや。

> (compile-thunk (car '(hello world)))
#fn("6000r0e0;" [hello])

上でfunction:codeを実験したのと同じだ。そうか、で、希望としては、これを 人間が読めるように逆変換してくれないかな。探したら有った。作者さんもこれが コンパイラーを書くについて、最初に必要だったに違いありません。

> (disassemble (compile-thunk (car '(hello world))) )
maxstack 6
00000:  argc    0
00002:  loadg   hello
00004:  ret
#t

とか

> (disassemble oblist)
maxstack 6
00000:  argc    0
00002:  loadv   #fn(environment)
00004:  tcall   0
00006:  ret
#t

もう少し、発展させて

> (compile-thunk (define (hoge x y) (* x y)) )
#fn("6000r0c0;" [#fn("7000r2|}T2;" [] hoge)])

>  (disassemble (compile-thunk (define (hoge x y) (* x y)) ))
maxstack 6
00000:  argc    0
00002:  loadv
        maxstack 7
        00000:  argc    2
        00002:  loada0
        00003:  loada1
        00004:  *       2
        00006:  ret
00004:  ret
#t

入れ子になってるのは、defineが有るから? そんじゃ、関数実行は?

> (compile-thunk (hoge 123 456))
#fn("6000r0c0;" [56088])

> (disassemble (compile-thunk (hoge 123 456)))
maxstack 6
00000:  argc    0
00002:  loadv   56088
00004:  ret
#t

畳み込みが発動してますな。折角なので、コンパイルしたのを逆にするマクロを 書いておこう。

(define-macro (cd e)
    `(disassemble (compile-thunk ,e)))

ちょっと使ってみる。上で2つの引数を取ると指示した時に現れてきた数字の2は、個数を 表しているんだろうな。検証してみる。

> (cd (define (foo x y z)(+ x y z)))
maxstack 6
00000:  argc    0
00002:  loadv
        maxstack 8
        00000:  argc    3
        00002:  loada0
        00003:  loada1
        00004:  loada   2
        00006:  +       3
        00008:  ret
00004:  ret
#t

もう一丁

> (cd (define (foo x y z zz)(/ x y z zz)))
maxstack 6
00000:  argc    0
00002:  loadv
        maxstack 9
        00000:  argc    4
        00002:  loada0
        00003:  loada1
        00004:  loada   2
        00006:  loada   3
        00008:  /       4
        0000a:  ret
00004:  ret
#t

argcと算術オペレータには、個数が並置されるとな。引数をロードしてくる専用命令は、 2個までは、特別に1バイト命令が用意されてるけど、それ以上は汎用命令とな。

> (cd (define (hoge x y)(* (car x)(cadr y))))
maxstack 6
00000:  argc    0
00002:  loadv
        maxstack 7
        00000:  argc    2
        00002:  loada0
        00003:  car
        00004:  loada1
        00005:  cadr
        00006:  *       2
        00008:  ret
00004:  ret
#t

微妙にForthマシンとは違う動きをするけど、根は同じ。演算対象がStackで、面倒な アドレス演算とレジスターのアロケートを避けている。

(define-macro (cad e)
     `(let ((E (compile-thunk ,e)))
        (print E)
        (princ "\n")
        (disassemble E)))

先ほどのマクロ、こちらの方が、コンパイル結果と逆アセンブル結果を同時観察 出来て、より便利そう。

> (cad (define (fuga x y)(+ (cddr x) (caddr y))))
#fn("6000r0c0;" [#fn("8000r2e0|31e1}31w;" [cddr caddr] fuga)])
maxstack 6
00000:  argc    0
00002:  loadv
        maxstack 8
        00000:  argc    2
        00002:  loadg   cddr
        00004:  loada0
        00005:  call    1
        00007:  loadg   caddr
        00009:  loada1
        0000a:  call    1
        0000c:  add2
        0000d:  ret
00004:  ret
#t

etc

命令セット拡張に対するGCC及びGNU Tool Chainのリターゲッティング

Schemeコンパイラで、末尾再帰のクロージャをループに変更する

継続渡しスタイル

継続渡し形式(CPS)

継続と継続渡しスタイル