<< 前 ホーム 次 >>

bakaid: 20130120

sl3.cという非常にシンプルなLisp処理系があります:

http://www.sonoma.edu/users/l/luvisi/sl3.c

GCを持たないくらいシンプルです。でも、ちょっとした
トリックが使われていて、それを理解したとき、思わず
「アタマイイ!」と声に出てしまいました。

Lispであるからには、まずセルの定義が来ます:

enum otype { INT, SYM, CONS, PROC, PRIMOP };
typedef struct obj {
  enum otype type;
  struct obj *p[1];
} obj;

ここでおかしいと気づくべきでした。いや、おかしいこと
には気づきました。「要素が1つしかない配列なんて定義
してどういうつもり?」と。

次にcarとcdrの定義を見て混乱に拍車がかかりました:

#define car(X) ((X)->p[0])
#define cdr(X) ((X)->p[1])

特にcdr。定義では存在しないはずの2番めの要素にアクセス
してます。

混乱しながらコードを見てると、consの実体である関数に
ミソがありそうだと分かりました:

#define cons(X, Y) omake(CONS, 2, (X), (Y))

obj *omake(enum otype type, int count, ...) {
  obj *ret;
  va_list ap;
  int i;
  va_start(ap, count);
  ret = (obj *) malloc(sizeof(obj) + (count - 1)*sizeof(obj *));
  ret->type = type;
  for(i = 0; i < count; i++) ret->p[i] = va_arg(ap, obj *);
  va_end(ap);
  return ret;
}

consすると、objの2つ分のサイズのメモリがmallocされる
わけです。その2つは、当然メモリ上に隣接して配置される
わけです。それがどういうことかというと、cdr部への
ポインタを使わずにコンスセルを実現できるということなん
です。

コンスセルの素朴な実装をRubyなんかでやるとすると:

class Cell; end

class Intejer < Cell
  def initialize(n)
    @value = n
  end
end

class Cons < Cell
  def initialize(kar, kdr)
    @kar = kar
    @kdr = kdr
  end
end

みたいに、明示的にcdr部のフィールドを用意しないと
いけない。C言語でやるとしても、コンスセルのために
unionを使うわけにはいかないので、たとえば:

struct Cell {
  int type;
};

struct Integer {
  int type;
  int value;
};

struct Cons {
  int type;
  Cell* kar;
  Cell* kdr;
};

みたいにするでしょう。でも、sl3.cだと構造体はobj
ひとつしかありません。

ただ、sl3.cのやり方だと、メモリ上に隣接しいていること
がコンスセルの必須条件になってしまうので、malloc
みたいなメモリ割り当てがない言語だとダメなんですね。

--

と、長々と書いてみたけど、すべてのセルを配列で用意した
昔のLispの実装を知っていれば、こういうやり方は自然
なのかもなぁ。

--

ああ、ある種、Forthに近いんだな、こういうやり方は。

--

あ、GC関係ないんだな。GCやらないからできる実装かと
思ったけど。mallocがポイントなわけか。

本家Permlink

<< 前 ホーム 次 >>


Copyright © 1905 tko at jitu.org

バカが征く on Rails