SICP 読み (378) 5.5 翻訳系

SICP scheme

中締め、と言いつつ続けてしまう。休みに時間が取れたら EoPL がっとヤッてみたい方向で。(何

問題 5.51

これは次の問題 (C の手続きへの自動翻訳) に繋げる必要がありそげなので、ch5-compiler.scm が scheme な命令列をどう扱っているのか、を参考にした方が良さげ。
regsim な命令は

  • assign
  • test
  • branch
  • goto
  • save
  • restore
  • perform

な模様。うーん。リストをどう持つか、というあたりは 5.3.2 節を参考にすれば良いのかなぁ。これはきちんと検討しないと大変なコトになりそげ。
とりあえずリストが管理できれば初等的な実装ってのはさほどハードル高そうには感じないのですが、手元にある gauche-0.1 を見てみる必要あり??

データ構造

ええと、gauche.h を上から見ていきながらチェキ。guile のドキュメントやら RHG やら見てるんでとても分かりやすい。最初に出てくるマクロなんかはスルーで

  • ScmWord 型は unsigned long
  • ScmByte 型は unsigned char
  • ScmChar 型は long
  • ScmObj 型は ScmHeaderRec 構造体へのポインタ

ScmHeaderRec 構造体は何処??と言いつつ emacs のキーバインド忘れとる。検索用に GNU GLOBAL って書いとこ。以下がキーバインド。

  • M-t で掘る
  • M-s (Find symbol)
  • M-r (reference)
  • C-t でもどる

後天性記憶不全の身の上を呪いつつ gauche.h にあるのを発見。

typedef struct ScmHeaderRec {
    struct ScmClassRec *klass;
} ScmHeader;

あるいは ScmClassRec 構造体の定義が以下。(gauche.h)

/*---------------------------------------------------------
 * CLASS
 */

struct ScmClassRec {
    SCM_HEADER;
    char *name;
    int (*print)(ScmObj obj, ScmPort *sink, int level);
    struct ScmClassRec **cpl;
};

クラス、というものがあるみたい。微妙に ruby 的 (違)。いっちゃんケツのポインタがアレげ感満点だなぁ。メンバは一旦スルーで次にタグが出てくる。コメントを以下に引用。

/* TAG STRUCTURE
 *
 * [Pointer]
 *      -------- -------- -------- ------00
 *      Points to cell (4-byte aligned)
 *
 * [Fixnum]
 *      -------- -------- -------- ------01
 *      30-bit signed integer
 *
 * [Character]
 *      -------- -------- -------- -----010
 *      29-bit
 *
 * [Miscellaneous]
 *      -------- -------- -------- ----0110
 *      #f, #t, '(), eof-object, undefined
 *
 * [VM Instructions]
 *      -------- -------- -------- ----1110
 *      Only appears in a compiled code.
 */

ケツの 4 bit で制御している模様

  • 4 の倍数はセルへのポインタ
  • ケツが 01 なら 30bit 使って小さい整数 (signed とある)
  • ケツが 010 なら 29bit 使って文字を表現??
  • ケツが 0110 なら特別な値を表現
  • ケツが 1110 なら VM 云々 (これは多分今回はスルーしまくるはず

ruby はどうだったか、と思いつつどんどん見る。

  • SCM_OBJ は ScmObj 型にキャストするマクロ
  • SCM_WORD は ScmWord 型にキャストするマクロ
  • SCM_TAG はケツの 2bit (タグ) を取り出すマクロ
  • SCM_PTRP はポインタなら真を戻すマクロ

そういえば RHG にも出ていましたが、なんたらP っていうマクロは predicate な意味だとの事。これは guile もそうなっていたので scheme 式、なのでしょうか (てーか lisp 式、というのが本当なのかな
で、以降はカテゴリ毎でマクロが定義されている

  • IMMEDIATE OBJECTS (即値って言い方で良いのかな
    • SCM_IMMEDIATEP はケツの 4bit が 6 なら真、とあるから上記コメントの #f, #t, '(), eof-object, undefined にあたるのか
    • SCM_ITAG マクロは 4bit 右シフトしているから値の取り出し
    • SCM_MAKE_ITAG マクロは上記とは逆にタグ付け
    • 以降はそれぞれのオブジェクトの定義 (正確にはそうではないか) と述語の定義

次は BOOLEAN との事で述語なマクロ (SCM_BOOLP) と BOOLEAN なオブジェクトを戻すマクロが定義されている。

#define	SCM_MAKE_BOOL(obj)   ((obj)? SCM_TRUE:SCM_FALSE)

なんとなく格好いい。以降で

  • SCM_EQ マクロ
  • Scm_EqP 関数の extern 宣言
  • Scm_EqvP 関数の extern 宣言
  • Scm_EqualP 関数の extern 宣言

となっている。むむ、よく考えたら primitive な手続きもいくつか作らないと駄目なのか。何々が必要になるのか、は見といた方が良いな。ちなみに上記の関数は boolean.c にて定義されている模様。
引用は略しますが、Scm_EqualP() で取り扱っているオブジェクトは

のみな模様。問題 5.51 ではベクタはスルーな方向で。

続

ええと、BOOLEAN の次は FIXNUM です。

  • SCM_INTP マクロが小さい int か、な述語
  • SCM_INT_VALUE マクロは値の取り出し
  • SCM_MAKE_INT は小さい int なオブジェクトへの変換

次の CHAR についてはスルー (意味はない
で、その次が HEAP ALLOCATED OBJECTS とある。malloc されたオブジェクトが持ってる共通ヘッダ関連のマクロ達が定義されている模様。ちょっと気になったのでメモしておくと、ScmObj 型はここで出てくる struct ScmHeaderRec 構造体へのポインタとして定義されていますが、これは便宜上と言えばよいのかとりあえずと言えばよいのかは分かりませんが、実際に使う時にはそれぞれのオブジェクトの型にキャストして使うのでしょうか。
まだ実際にどうこう、というあたりが出てきてないので推測なんですが。
とりあえず最初に ScmHeaderRec 構造体と ScmHeader 型の定義。で SCM_HEADER マクロも定義。どのオブジェクトも hdr という ScmHeader 型のメンバを持っているものと思われる。以降で定義されているマクロはざっくり以下

  • SCM_CLASS_OF マクロは ScmHeader 型の klass メンバを戻す (この書き方微妙
  • SCM_XTYPEP マクロは型をチェックする述語な模様

む。この SCM_XTYPEP マクロの定義は以下

#define SCM_XTYPEP(obj, klass) (SCM_PTRP(obj)&&(SCM_CLASS_OF(obj) == (klass)))

なんですが、この定義を見るにクラスなオブジェクトは singleton なソレなのか。次でちょっとだけクラス関連なマクロも出てくる。

  • SCM_CLASS は ScmClass 型でキャストなマクロ
  • SCM_CLASSP は SCM_CLASS_CLASS を使って SCM_XTYPEP するマクロになっている。メタクラスというヤツかな (SCM_CLASS_CLASS)。クラスオブジェクトはヘッダの klass メンバは SCM_CLASS_CLASS がセットされるきまりだろうか。

で、次なんですが微妙に gc がカランでるっぽいので以下をスルー

  • SCM_MALLOC
  • SCM_MALLOC_ATOMIC
  • SCM_REALLOC
  • SCM_NEW
  • SCM_NEW2
  • SCM_NEW_ATOMIC
  • SCM_NEW_ATOMIC2

これはアレだな。オブジェクトを生成する時に使うんだろうな。次は klass メンバにクラスオブジェクトをセットする SCM_SET_CLASS マクロが定義。

#define SCM_SET_CLASS(obj, type)   (SCM_OBJ(obj)->klass = type)

これも RHG に出ていたような記憶があるんですが、上記のマクロにペアが渡される形でも klass メンバは基本的にオブジェクトの先頭に存在するから ScmObj でキャストして代入しても大丈夫、なカラクリなんだろうな。このあたりのテクは lisp/scheme 由来なのでしょうか。guile がどうなってたか、は記憶にない。多分ここまで見てないんだろうな。
で、以降はそれぞれのオブジェクトの構造体をデータ型として定義している。詳細は略。次の VM もスルーします。VM の次にあるのは CLASS になっている模様。
このクラスというもので様々なオブジェクトの種類を切り分けているものと思われるんですが、構造体の定義については上で引用してるんで略。cpl というメンバはポインタ配列があってそれを指してるのだろうか、と予想。後は

  • Scm_ClassOf
  • Scm_ClassCPL
  • Scm_SubtypeP
  • Scm_TypeP
  • Scm_MakeBuiltinClass

という関数が extern 宣言されている。これらの関数は class.c で定義されているものと思われる。ちょっとだけ中身見てみたんですが Scm_ClassCPL() 関数の定義で

    ScmObj start = SCM_NIL, last;

な命令があって一瞬 last って何だよ、とパニクってしまいました。カンマつなぎで代入されているように見えた。何と勘違いしていたのでしょうか。駄目です。
後は built-in なクラスのオブジェクトを参照するグルーバル変数の extern な宣言やら構造体のポインタを戻すマクロやらが定義されている。あと

  • Scm_DefaultCPL
  • Scm_CollectionCPL
  • Scm_SequenceCPL

というこれもポインタ配列のポインタなのか微妙ですが、extern 宣言されていたり参照するマクロが定義されていたり。最後に SCM_DEFCLASS というマクロが定義されておるのですが、これはグローバルなクラス定義の命令を書くのが微妙だったのでマクロを作ったものと思われます。

/* define built-in class statically */
#define SCM_DEFCLASS(cname, sname, printer, cpl)        \
    ScmClass cname = {                                  \
        SCM_CLASS_CLASS, sname, printer, cpl            \
    }

以下、実際に使われている例 (class.c)

SCM_DEFCLASS(Scm_TopClass,     "<top>",     NULL, SCM_CLASS_DEFAULT_CPL);

次でようやくリストが出てきますが一旦停止。