#:g1: toadstoolの紹介

Posted 2014-01-09 15:00:00 GMT

(LISP Library 365参加エントリ)

 LISP Library 365 の10日目です。

toadstoolとはなにか

 toadstoolとはStanislaw Halik氏作のHaskellやOCaml風のパターンマッチのライブラリで高速性が特長のようです。

パッケージ情報

パッケージ名toadstool
Quicklisp
CLiKihttp://cliki.net/toadstool
Quickdocshttp://quickdocs.org/toadstool

インストール方法

(ql:quickload :toadstool)

試してみる

 どんな関数があるかは、Quickdocsで確認できます。

 内容は、toad-caseが基本で、あとはパターンにマッチしなかった場合にエラーにするtoad-ecaseと、継続的エラーにするtoad-ccaseの3つのみです。
パターン -> マッチした結果節
という記述になっています。

(toad-ecase 3
  4 -> :iv
  3 -> :iii)
;=>  :III
ガードは、whenで指定します。
(toad-case '(1 2 -42 3)
  (list (* t) x (* t)) -> (when (< x 0)) x)
;=>  -42
面白いのがpushで、LOOPのcollectのような働きをします。
(toad-case (list 1 2 'foo "bar" :baz)
  (list (* (or (and (satisfies #'numberp)
                    (push numbers))
               (and (satisfies #'symbolp)
                    (push symbols))
               (push others))))
    -> (values numbers symbols others))
;=>  (1 2)
;    (FOO :BAZ)
;    ("bar")

 速度ベンチについての記載があるので、Schemeで良く利用されているAndrew Wright氏のmatchをAlex Shinn氏がsyntax-rulesで記述したものを私がCommon Lispに移植したものと比較してみました。
元ネタは、comp.lang.lispでHarrop氏が提示した問題にQiのMark Tarver氏が興味を示したもの「Qi, Lisp and O'Caml compared」にさらにインスパイアされたもののようです。
速度的には、toadstoolはQiと大体同じとのこと。

toadstool
(defun harropify (x)
  (toad-case x
    (list Op A B) -> (h Op (harropify A) (harropify B))
    A -> A))

(defun h (op a b) (toad-case op a b '+ M N -> (when (and (numberp M) (numberp N))) (+ M N) '+ 0 F -> F '+ F 0 -> F '+ A (list '+ B C) -> (h '+ (h '+ A B) C) '* M N -> (when (and (numberp M) (numberp N))) (* M N) '* 0 F -> 0 '* F 0 -> 0 '* F 1 -> F '* 1 F -> F '* A (list '* B C) -> (h '* (h '* A B) C) Op A B -> (list Op A B)))

match
(defun harropifym (x)
  (snow-match:match x
    ((Op A B) (ho Op (harropifym A) (harropifym B)))
    (A A)))

(defun hm (op a b) (snow-match:match (list op a b) (('+ (:? numberp M) (:? numberp N)) (+ M N)) (('+ 0 F) F) (('+ F 0) F) (('+ A ('+ B C)) (hm '+ (hm '+ 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)) (hm '* (hm '* A B) C)) ((Op A B) (list Op A B))))

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

(harropifym '(* x (+ (+ (* 12 0) (+ 23 8)) y)))
;=>  (* X (+ 31 Y))
(dotimes (i (expt 10 7))
  (harropify '(* x (+ (+ (* 12 0) (+ 23 8)) y))))
;⇒ NIL
#|------------------------------------------------------------|
Evaluation took:
  3.124 seconds of real time
  3.128196 seconds of total run time (3.104194 user, 0.024002 system)
  [ Run times consist of 0.144 seconds GC time, and 2.985 seconds non-GC time. ]
  100.13% CPU
  7,479,361,944 processor cycles
  960,025,520 bytes consed

Intel(R) Core(TM)2 Duo CPU P8600 @ 2.40GHz |------------------------------------------------------------|#

(dotimes (i (expt 10 7)) (harropifym '(* x (+ (+ (* 12 0) (+ 23 8)) y)))) ;⇒ NIL #|------------------------------------------------------------| Evaluation took: 5.888 seconds of real time 5.892368 seconds of total run time (5.784362 user, 0.108006 system) [ Run times consist of 0.312 seconds GC time, and 5.581 seconds non-GC time. ] 100.07% CPU 14,097,064,158 processor cycles 3,359,992,304 bytes consed

Intel(R) Core(TM)2 Duo CPU P8600 @ 2.40GHz |------------------------------------------------------------|#

matchもそんなに遅くはありませんが、toadstoolは結構速いみたいです。

関連記事等

まとめ

 今回は、toadstoolを紹介してみました。
自分の手元では、5年前位からインストールしてありましたが、全然使ったことはありませんでした。
結構速いし便利そうなので利用してみたいところです。

comments powered by Disqus