CLでSRFI-45 — #:g1

Posted 2011-12-27 12:26:00 GMT

CLでSRFI、今回は、SRFI-45の「Primitives for Expressing Iterative Lazy Algorithms」です。

Schemeには遅延評価の仕組みとしてdelayとforceがありますが、これらの組み合わせでは末尾再帰的に書いてもメモリが消費されていってしまうそうで、その辺りをトランポリンの仕組みで問題を解決したのが、SRFI-45だそうです。 delayとforceにlazyとeagerが追加されています。
(defun stream-filter (p? s)
  (lazy
   (if (null (force s))
       (delay '())
       (let ((hd (car (force s)))
             (tl (cdr (force s))))
         (if (funcall p? hd)
             (delay (cons hd (stream-filter p? tl)))
             (stream-filter p? tl))))))

(defun from (n) (delay (cons n (from (+ n 1)))))

(defvar *large-number* 100000000)

(car (force (stream-filter (lambda (n) (= n *large-number*)) (from 0)))) ;=> 100000000

移植について

メモリの消費がどんどん消費されるようなことはないらしいのですが、参照実装そのままだとコンスしているところがあるので非常に大きなコンスストリームを作ったりするとSBCLではうまくないようです。 Gauche等ではこのあたりは上手く処理されているようなので、ちょっと探ってみたいと思っています。

comments powered by Disqus