ここ2,3日、人のパターンマッチャ http://qiita.com/m2ym/items/a2e00c79984750958e8a を使いやすくするライブラリを整備していて、こんなものが出来ました。
ここに自分で書いたことも関連。
使いやすさをシェイプアップするため、これらをつかって、試験的に以下のライブラリをバババッとつくっていました。うち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が十分賢いのでこれで十分です。
例:
(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未登録)。
以上です。どしどしツッコミください。