Common Lisp に型変数を導入してみる

ここ2,3日、人のパターンマッチャ http://qiita.com/m2ym/items/a2e00c79984750958e8a を使いやすくするライブラリを整備していて、こんなものが出来ました。

https://github.com/guicho271828/optima-immutable-struct

[ここに自分で書いたこと](http://ja.stackoverflow.com/questions/1703/common-lisp%E3%81%AEdefstruct%E3%81%AE%E3%82%B9%E3%83%AD%E3%83%83%E3%83%88%E3%81%AEread-only%E3%82%AA%E3%83%97%E3%82%B7%E3%83%A7%E3%83%B3%E3%81%AB%E3%81%A4%E3%81%84%E3%81%A6)も関連。

使いやすさをシェイプアップするため、これらをつかって、試験的に以下のライブラリをバババッとつくっていました。うち1つはm2ymさんのソースを核にしたもの。

* https://github.com/guicho271828/optima-binary-heap
* https://github.com/guicho271828/optima-red-black-tree
* https://github.com/guicho271828/optima-bdd --- bdd と zdd
* https://github.com/guicho271828/optima-priority-queue-rb

# 型変数

しかし、こうML的にアルゴリズムを書いていると欲しくなるのが型変数。
なんか伝播したり、unifyできたり、あれば嬉しい感じですよね。
こういうときに、思い立ったらパパっと機能を言語に追加できちゃうのがlispのいいところです。
コミットログを見ればわかりますが、半日ぐらいで実装できました。

実際にテスト以外で使ってはいないので、完成度は微妙です。
API上の意見、docの書き方上の意見、「てめ~それ本物の型変数じゃなくてハックだろ」みたいなツッコミをお待ちしています。

# macro *define-with-typevar*

body中だけで有効な型変数を宣言します。body中では defstruct,ftype,defun らが特別扱いされます。一応自明な型伝播は有効にしたつもり。推論だのなんだのについてはsbclが十分賢いのでこれで十分です。

例:

```lisp
(define-with-typevar (
 <t>)
  (defstruct coordinate2
    (x 0 :type 
)
    (y 0 :type <t>)
    (z 0 :type 
))
  (ftype vector-+ (/ coordinate2 
 <t>) (/ coordinate2 
 <t>) (/ coordinate2 
 <t>))
  (defun vector-+ (v1 v2)
    (declare (optimize (speed 3) (space 0) (safety 0) (debug 0)))
    (coordinate2
     (+ (coordinate2-x v1)
        (coordinate2-x v2))
     (+ (coordinate2-y v1)
        (coordinate2-y v2))
     (+ (coordinate2-z v1)
        (coordinate2-z v2)))))
```

ここの時点では、まだ特定化された structure/functions は定義してません。型が特定化された構造体/関数は `instantiate-structure` と `instantiate-ftype` を使えば作ることが出来ます。なお、新しい構造体や関数には `<original name>{/<type>}*` って名前がつきます。

```lisp
(instantiate-ftype 'vector-+ 'fixnum 'fixnum)

;-->
; Instantiating a function VECTOR-+ with typevars (FIXNUM FIXNUM)
; (FTYPE VECTOR-+/FIXNUM/FIXNUM (/ COORDINATE2 FIXNUM FIXNUM) (/ COORDINATE2 FIXNUM FIXNUM)...)
; Instantiating a structure COORDINATE2 with typevars (FIXNUM FIXNUM)..
```

CLOSと違って静的型付けなので, できる関数は速いです。ディスパッチも無し。

```lisp
; disassembly for VECTOR-+/FIXNUM/FIXNUM
; Size: 84 bytes. Origin: #x100C2CD232
; 32:       4C8B410D         MOV R8, [RCX+13]                 ; no-arg-parsing entry point
; 36:       488B470D         MOV RAX, [RDI+13]
; 3A:       49D1F8           SAR R8, 1
; 3D:       48D1F8           SAR RAX, 1
; 40:       4901C0           ADD R8, RAX
; 43:       4C8B4915         MOV R9, [RCX+21]
; 47:       488B4715         MOV RAX, [RDI+21]
; 4B:       49D1F9           SAR R9, 1
; 4E:       48D1F8           SAR RAX, 1
; 51:       4901C1           ADD R9, RAX
; 54:       488B711D         MOV RSI, [RCX+29]
; 58:       488B471D         MOV RAX, [RDI+29]
; 5C:       48D1FE           SAR RSI, 1
; 5F:       48D1F8           SAR RAX, 1
; 62:       4801C6           ADD RSI, RAX
; 65:       49D1E0           SHL R8, 1
; 68:       49D1E1           SHL R9, 1
; 6B:       48D1E6           SHL RSI, 1
; 6E:       498BD0           MOV RDX, R8
; 71:       498BF9           MOV RDI, R9
; 74:       488B0565FFFFFF   MOV RAX, [RIP-155]               ; #<FDEFINITION for COORDINATE2/FIXNUM/FIXNUM>
; 7B:       B906000000       MOV ECX, 6
; 80:       FF7508           PUSH QWORD PTR [RBP+8]
; 83:       FF6009           JMP QWORD PTR [RAX+9]
```

わざわざ自分で `instantiate-ftype/structure` を呼ばずとも、それらを使う関数定義のところで `(/ lifted-struct types...)` という型を宣言すれば、 deftype 展開の時点で自動的にそれらの特定化構造体/関数がinstantiateされます。それぐらいのレベルの制約伝播なら出来ます。

```lisp
(defun abababa (x y)
   (declare (type (/ coordinate2 'ratio 'float) x y))
   ;; ^^^ たぶんこの部分のコンパイル時点で型が instantiate されるハズ。
   ....)
```

でも、本当に賢い(ってどんな?)伝播は出来ません。(いい例が思いつかない.)

また、残念なことに、common lisp では型がいつ展開されるかというのは制御できないので、いつ特定化構造体/関数が定義されるのかわからず、困りものです。上の例で「たぶん」って書いたのはそのため。

処理系独自の `typeexpand` 的な関数ならあります。それ用の compatibility ライブラリもあります(quicklisp未登録)。

https://github.com/Bike/compiler-macro

以上です。どしどしツッコミください。