2012/02/09

simple-vector

simple-vectorがよく分からない - conjの日記

Clozure CL や Steel Bank Common Lisp で以下のような挙動になった．

(subtypep 'fixnum 'integer)
;=> t

(simple-vector-p (make-array 10 :element-type 'integer :initial-element 0))
;=> t

(simple-vector-p (make-array 10 :element-type 'fixnum :initial-element 0))
;=> nil

最後の式が nil を返す理由が分からない．

コメントを書こうと思ったら長くなったのでこちらで。

まず教科書的な答えを言うと、simple-vectorは「ジェネリックなLispオブジェクトを格納できるsimple-array」と決められているから。型表記で言えば (simple-array t (*)) ならsimple-vector。上の二つのarrayをdescribeしてみると、前者はジェネリックだけど後者はfixnumに特殊化されているだろうと思う。下はAllego CLでの実行結果。

cl-user(7): (describe (make-array 1 :element-type 'integer :initial-element 0))
#(0) is a new (simple-array t (1)).
 There are 1 elements
cl-user(8): (describe (make-array 1 :element-type 'fixnum :initial-element 0))
#(0) is a new (simple-array fixnum (1)).
 There are 1 elements

(simple-array fixnum (*)) はfixnumに特殊化されてるから、simple-vectorになれない。

でも、これだけだといくつか疑問が浮かぶんじゃないかと思う。

上のarrayも:element-type 'integerしてるのになぜintegerに特殊化されてないの?

Common Lispでの型情報はあくまで最適化のためのヒントにすぎないので、処理系は型情報を全て無視して全部ジェネリックなLispオブジェクトとして扱っても構わない。なので:element-type 'fixnumしてるarrayが(simple-array t (*))になる(したがってsimple-vectorにならない)可能性だってある。ただ、普通の処理系では要素がfixnumの配列は特別扱いすると有利なことが多い。数値を保存しておくのに型情報をつけなくてよいとか。

一方、要素がintegerの場合はbignumも格納しないとならないんで、そうすると特殊な配列を使うメリットがあまりない。bignumは普通ヒープに置かれて型タグもついたLispオブジェクトになるから。だから処理系はえいやっとジェネリックな配列を使っちゃうわけ。

そもそもsimple-vectorって何のためにあるの?

効率のため。Lispの配列は高機能で、要素の格納形式が指定できたり、動的に大きさが 変えられたり、他の配列の一部分を別の形の配列としてアクセスしたりできるんだけど、 その場合、アクセスの度にいろいろ確認したり変換したりというコードが必要になる。

でもsimple-vectorなら、それはC言語でいう配列 LispObj x[] と同じものと みなせる。(declare (optimize (safety 0))) すればインデックスの範囲チェックも 省かれるので svref はCで書いた配列アクセスと同等のコードになる。

というわけで高速なLispコードを書くときにはsimple-vectorとsvrefは強い味方。

(subtypep 'fixnum 'integer) => tなのに前者の配列が後者の配列のsubtypeにならないのはなぜ?

これはCommon Lispに限らずパラメタライズされた型に一般的な性質。 型Sが型Tのサブタイプでも、パラメタライズされた型X<T>は型X<S>のサブタイプになるとは限らない。

SがTのサブタイプである (S <: T) ということは、Tを期待してる文脈に実際はSであるオブジェクトを渡してもいいということ。例えば Fixnum <: Integer ということは、Integer のインスタンスを期待してるところに Fixnum のインスタンスを渡せる、ということ。

ここでもし Fixnum <: Integer だからといって Array<Fixnum> <: Array<Integer> であることを許すと、Array<Integer> を期待している文脈に Array<Fixnum> を渡せることになる。例えば次の式ではiarrayがintegerのarrayであることを期待して、bignumを代入しているが:

  (setf (aref iarray 0) 47874827583458281495927465923753928)

このiarrayにfixnumのarrayを渡したらまずいでしょ、という話。

もっときっちりした話はTAPLの15章あたり参照。

Tags: Programming, Lisp