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

ここに自分で書いたことも関連。

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

型変数

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

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

macro define-with-typevar

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

例:

(define-with-typevar (<s> <t>)
  (defstruct coordinate2
    (x 0 :type <s>)
    (y 0 :type <t>)
    (z 0 :type <s>))
  (ftype vector-+ (/ coordinate2 <s> <t>) (/ coordinate2 <s> <t>) (/ coordinate2 <s> <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>}* って名前がつきます。

(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と違って静的型付けなので, できる関数は速いです。ディスパッチも無し。

; 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されます。それぐらいのレベルの制約伝播なら出来ます。

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

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

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

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

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