#:g1: select-matchの紹介

Posted 2014-03-25 15:00:00 GMT

(LISP Library 365参加エントリ)

 LISP Library 365 の85日目です。

select-matchとはなにか

 select-matchは、Stephen Adams氏が1990年に作ったパタンマッチのマクロです。

パッケージ情報

パッケージ名select-match
参考サイトPackage: lang/lisp/code/match/miranda/

インストール方法

 上記のCMUのAIレポジトリから拾ってきても良いのですが、SWANKにSWANK-MATCHとして同梱されているので、SWANKをロードすれば使えたりします。

(ql:quickload :swank)

試してみる

 恒例のharropifyで速度はどんなものかをみてみます。

(defun h (op a b)
  (match (list op a b)
    (('+ (#'numberp M) (#'numberp N)) (+ M N))
    (('+ 0 F)  F)
    (('+ F 0)  F)
    (('+ A ('+ B C))  (h '+ (h '+ A B) C))
    (('* (#'numberp M) (#'numberp N)) (* M N))
    (('* 0 F) f 0)
    (('* F 0) f 0)
    (('* F 1)  F)
    (('* 1 F)  F)
    (('* A ('* B C))  (h '* (h '* A B) C))
    ((Op A B)  (list Op A B))))

(defun harropify (x) (match x ((Op A B) (h Op (harropify A) (harropify B))) (A A)))

(harropify '(* x (+ (+ (* 12 0) (+ 23 8)) y))) ;=> (* X (+ 31 Y))

(time (dotimes (i 1000000) (harropify '(* x (+ (+ (* 12 0) (+ 23 8)) y))))) ;=> #| ================================================================ Evaluation took: 0.480 seconds of real time 0.472029 seconds of total run time (0.472029 user, 0.000000 system) [ Run times consist of 0.040 seconds GC time, and 0.433 seconds non-GC time. ] 98.33% CPU 1,147,606,731 processor cycles 336,014,880 bytes consed |#

 同じものがoptimaだと0.563secなのでselect-matchも結構速いようです。

 ちなみに、=>を使って括弧を少なめで書くことも可能です。

(defun h (op a b)
  (match (list op a b)
    ('+ (#'numberp M) (#'numberp N)) => (+ M N)
    ('+ 0 F) => F
    ('+ F 0) => F
    ('+ A ('+ B C)) =>  (h '+ (h '+ A B) C)
    ('* (#'numberp M) (#'numberp N)) => (* M N)
    ('* 0 F) => 0
    ('* F 0) => 0
    ('* F 1) => F
    ('* 1 F) => F
    ('* A ('* B C)) => (h '* (h '* A B) C)
    (Op A B) => (list Op A B)))

まとめ

 今回は、select-matchを紹介してみました。
コンパクトでありつつツボは押えている感じでソースコードも短かいのでSWANKでのように同梱するには良さそうなライブラリです。

comments powered by Disqus