Lisp実装のための型情報のポインタへの埋め込み

[lisp implementer]

LispインタプリタをC言語で実装しようとしています。

データの型情報を何処かに保存しなければならないのですが、構造体を作って型番号int typeとデータそのものを構造体のなかに保存する方法のほかに、ポインタにデータを埋め込むという方法があるようなのですが、これがあまりよく理解できません。

http://bis83gb.hatenadiary.jp/entry/2014/01/02/094840

> Lispは動的型付言語なのでポインタに型を持たせる必要があります。
> 現在の計算機だと物理アドレスやOSの仮想アドレスに型が無いのは仕方ないですが、
> 残念ながらC言語のポインタにも実行時型情報は付きません。

> Lispオブジェクトの組み込み型は多くても数十程度なので、
> アドレス値の一部を利用して型情報を埋め込みましょう。

http://blog.bugyo.tk/lyrical/archives/1537

> Lispを作る際にはどこかに型の情報を入れておく必要がありますが、どこにいれるかは、2つのやり方があります。
> ひとつは先程のようにデータと一緒に格納する方法。そしてもうひとつはポインタに格納するという方法です。

どうやらポインタ変数をbitsとして扱い、その一部に型データを埋め込んでいるようなのですが、この方法でポインタのbitsを操作するとポインタの指し示すアドレスが変わってしまうのではないのですか？　どのような方法論なのかお教えいただけると幸いです。よろしくお願いします。

[びす]

アドレスの上位bitを無視してよい環境なのかもしれません。
例として64bit windowsであれば、ユーザーモードプログラム内で確保したメモリに割り当てられるアドレス範囲は 0x00000000'00000000 ~ 0x000007FF'FFFFFFFF であり、上位21bitは必ず0です。

参考 :
仮想アドレス領域 (Windows Drivers)
実行時のデータ型の表現手法

[lisp implementer]

ああ、なるほど、そういうことなのですね。特にリンク2番目のスライドは非常に助かります。ありがとうございます。

使われていない上位ビットを利用する場合、使われていないアドレス空間をアーキテクチャごとに調べる必要があるわけですが、これはC言語にアドレス空間について調べる機能があるわけではなく、各アーキテクチャのマニュアル等を読んで手動で場合分けする必要があるのですよね？

いずれにせよ非常に助かりました。ありがとうございます。

[餃子]

下位ビットをタグにする場合もあります。 というよりおそらくその場合の方が多いです。
大抵の場合、 malloc は 8 の倍数のアドレスにアラインされたポインタを返しますから、3ビットはタグに使えます。
実際にポインタとして使う場合は3ビット分はマスクしてから使うわけです。

更に文字や真偽値や小さな数値は情報量が小さいのでヒープに場所を確保せずそのままワードに詰込んでしまうということも行われます。
Lisp 族の言語の比較関数でそういったオブジェクトのいくつかが特別扱いになっていることがあるのはポインタが指す先を辿らずに直接比較できるからです。

[lisp implementer]

ありがとうございます。リンク先のスライドにも下位バイトにデータを埋め込む方法が書いてありました。調べたのですが、8の倍数にアラインするかどうかも厳密にはCPUのアーキテクチャによって決まるようなので、厳密にやろうと思えばそちらも調べなければなりませんね。

いずれにせよお陰様で大体分かってきたので、投稿を〆させていただきます。お二人とも本当にありがとうございました。