読者です 読者をやめる 読者になる 読者になる

レガシーコード生産ガイド

私に教えられることなら

遅延評価(遅延シーケンス)利点の1つに気づいたのでCommon Lispで確かめる

Clojureローグライク書いてるんだけど、そのために遅延シーケンスとイミュータブルなデータ構造を多用したことで、今まで気づいてなかった遅延評価(シーケンス)の利点がわかったのでメモしておく。

正格評価や遅延評価など、用語の使い方に間違いがあれば訂正してもらえると嬉しい。 もちろん考え方に間違いがあった場合も。

結論

遅延シーケンスを使うと、

  1. 評価回数を最適化できる
  2. 1によって内部が複雑なループをシンプルに書ける

今回は2に気づいたという話。

以下のようなリスト操作関数があるとする。

;; リストxsの各要素にfを適用した結果のリストを返す
(map f xs)

;; リストxsの各要素xについて、(pred x)が正を返す要素のみのリストを返す
(filter pred xs) 

;; リストxsの先頭からn個とったリストを返す
(take n xs) ; リストxsの先頭から

そこで以下のような擬似コードについて考える

(take 10
  (filter 心躍るものか?
    (map 魔法をかける
      (map 何か素敵な事をする 巨大なリスト))))

正格評価の場合は、例えば巨大なリストの要素数が10000だった場合

  • mapで何か素敵な事を10000個の要素に行う
  • mapで10000個の要素に魔法をかける
  • filterで10000個の要素を調べて、心躍るものだけ抜き出す
  • 先頭の10個を取りだす

という評価順になり、30000個の要素について処理を行うことになる。

一方遅延評価の場合は

  • takeでまず1個目を取ろうとする
  • filterで1個目が心躍るものか調べようとする
  • mapで1個とって魔法をかけようとする
  • mapで1個とって何か素敵なことをして、takeまで返していく
  • takeで2個目を取ろうとする
  • filterで2個目が心躍るものか調べようとする
  • ...
  • takeで10個目を取ろうとする...
  • ...
  • 10個とったので、返す

と、mapやfilterなどシーケンス全体に影響するものを使った場合でも、 10個の要素に処理をするだけで済む。

巨大なシーケンスの一つ一つに処理を行う場合、 例えば二次元配列で表された巨大なダンジョンの各マスに対して、 様々な処理を行いたいとする。必要があれば座標を記録したりもしたい。

正格評価だと

  1. mapやreduceなどを重ねてわかりやすく書く(計算量大)
  2. 1つのループの中に押しこめ、複数の変数を管理して処理を行う(複雑さ大)

のどちらかをトレードオフで選ばないといけなかったが、 遅延評価とイミュータブルなデータ構造を使うと、1のわかりやすい書き方で2を達成できる。

面倒な条件分岐をあまりずに書けるし、全体に対して動作するかのテストも簡単に書ける。

プログラムを書いていて特に混乱して嫌な気分になるのが、ループの中で複数の条件や変数を管理してるときなので、まさにこれが欲しかったものだ。

確かみてみる

実際に上に書いたような評価順、評価回数になるか確かめる。

別々の言語で比べると面倒なのと、楽しそうなので、正格評価なCommon Lispで遅延評価マクロを作って比べる。

遅延評価マクロの定義

前に作ったものを 見ながら、Common Lispで書いてみる。

(defun make-promise (f)
  (let ((flag nil) (value nil))
    (lambda ()
      (unless flag
        (setf value (funcall f))
        (setf flag t))
      value)))

(defmacro delay (expr)
  `(make-promise (lambda () ,expr)))

(defun force (promise) (funcall promise))

利点を活かせてないtakeと活かすtake

このときテスト用にrepeatとtakeも作ったんだけど、そこで完全に誤解してた。

(defun repeat (x) (cons x (delay (repeat x))))

(defun take-old (n ds)
  (cond 
    ((eq n 0) nil)
    (t
     (cons
      (car ds)
      (take-old (- n 1) (force (cdr ds)))))))

このtakeが返すのは遅延リストdsを全て評価した結果なんだけど、 そうじゃなくてtakeやreduceなど遅延リストを全て評価しそうな(だと思っていた)関数も含めて、 全て遅延リストを返すことで利点が生まれる。

というわけで書き直す。repeatも(値 promise)じゃなくて全体をdelayで囲みpromiseのみを返すようにする。さらに、遅延リストを全て評価するdoallも末尾再帰で定義しておく。

(defun repeat (x) (delay (cons x (repeat x))))

(defun take (n delayed-list)
  (delay
   (cond
     ((eq n 0) nil)
     (t
      (let ((ds (force delayed-list)))
        (if ds
            (cons (car ds)
                  (take (- n 1) (cdr ds)))
            nil))))))

(defun doall-body (delayed evaled)
  (let ((v (force delayed)))
    (cond
      ((null v) (reverse evaled))
      (t
       (doall-body (cdr v)
                   (cons (car v) evaled))))))

(defun doall (delayed)
(doall-body delayed (list)))

以下のコードで試せる。(3 3 3 3 3 3 3 3 3 3)が返ってくる。

(doall (take 10 (repeat 3)))

ちなみにここまでは少しだけClojure 5書いてるときに、 Clojureのソースでのlazy-seqの使われ方と プログラミング Clojure第2版のp105、「再帰を遅延評価で置き換える」を読んで気づいた。 単純な再帰を書き換えていって、最後に遅延シーケンスの威力がわかる、という構成のおかげだと思う。

正格評価版の準備

map(mapcar)、filterがどんな順番で何回呼ばれたか調べるために、 それぞれの回数を表示するmap-count、reduce-count、filter-countを作る。

(defun map-count (f xs)
  (let ((result nil) (count 0))
    (dolist (x xs (nreverse result))
      (incf count)
      (format t "~2d map~%" count)
      (push (funcall f x) result))))

(defun filter-count (pred xs)
  (let ((result nil) (count 0))
    (dolist (x xs (nreverse result))
      (incf count)
      (format t "~2d filter~%" count)
      (when (funcall pred x) (push x result)))))

試してみる。

(defun show-result (fname v)
  (format t "~S result: ~S~%" fname v))
(defvar xs (list 'a 'b 'c 'd))

(show-result "map" (map-count (lambda (x) x) xs))
(show-result "filter" (filter-count (lambda (x) (not (eq x 'a))) xs))
 1 map
 2 map
 3 map
 4 map
"map" result: (A B C D)
 1 filter
 2 filter
 3 filter
 4 filter
"filter" result: (B C D)

遅延評価版の準備

(defun lmap-count (f delayed &optional (count 1))
  (delay
   (let ((ds (force delayed)))
     (cond
       ((null ds) nil)
       (t
        (format t "~2d lmap ~%" count)
        (cons
         (funcall f (car ds))
         (lmap-count f (cdr ds) (1+ count))))))))

(defun lfilter-count (pred delayed &optional (count 1))
  (delay
   (let ((ds (force delayed)))
     (cond
       ((null ds) nil)
       (t
        (format t "~2d lfilter~%" count)
        (if (funcall pred (car ds))
            (cons (car ds)
                  (lfilter-count pred (cdr ds) (1+ count)))
            (lfilter-count pred (cdr ds) (1+ count))))))))

リストを遅延リストに作り変える関数も定義して、試してみる。

(defun list->delayed (ys)
  (delay
   (cond
     ((null ys) nil)
     (t
      (cons
       (car ys)
       (list->delayed (cdr ys)))))))

(show-result "lmap"
             (doall (lmap-count (lambda (x) x) (list->delayed xs))))

(show-result "lfilter"
             (doall (lfilter-count (lambda (x) x) (list->delayed xs))))
 1 lmap 
 2 lmap 
 3 lmap 
 4 lmap 
"lmap" result: (A B C D)
 1 lfilter
 2 lfilter
 3 lfilter
 4 lfilter
"lfilter" result: (A B C D)

確認

素数20のリストにmapとfilterを重ねて適用し、最後にtakeで先頭の2要素のみ取り出す。

takeの動きも見るためにカウント用のtakeを、それと使用する正格/遅延リストも定義しておく

(defun take-regular-count (n xs &optional (count 1))
  (cond
    ((eq n 0) nil)
    ((null xs) nil)
    (t
     (format t "~2d take~%" count)
     (cons (car xs)
           (take (- n 1) (cdr xs) (1+ count))))))

(defun take-count (n delayed-list &optional (count 1))
  (delay
   (cond
     ((eq n 0) nil)
     (t
      (let ((ds (force delayed-list)))
        (if ds
            (progn
              (format t "~2d take~%" count)
              (cons (car ds)
                    (take-count (- n 1) (cdr ds) (1+ count))))
            nil))))))

(defun ys ()
  (take 20 (repeat 'ya)))
(defvar regular-ys
  (doall (ys)))

まず正格版。(さすがに見難いので非標準インデントにする)

(show-result "regular "
  (take-regular-count 2
    (filter-count #'identity
      (map-count #'identity
        (filter-count #'identity
          (map-count #'identity regular-ys))))))

結果

 1 map
 2 map
    (省略)
20 map
 1 filter
 2 filter
    (省略)
20 filter
 1 map
 2 map
    (省略)
20 map
 1 filter
 2 filter
    (省略)
20 filter
 1 take
 2 take
"regular " result: (YA YA)

予想通り20回ずつ、順番に評価されている。mapとfilterでの評価回数は80回になる。

次に遅延版

(show-result "lazy "
  (doall
    (take-count 2
      (lfilter-count #'identity
        (lmap-count #'identity
          (lfilter-count #'identity
            (lmap-count #'identity (ys))))))))

結果

 1 lmap 
 1 lfilter
 1 lmap 
 1 lfilter
 1 take
 2 lmap 
 2 lfilter
 2 lmap 
 2 lfilter
 2 take
"lazy " result: (YA YA)

予想通り、1要素ずつ全て適用されている。lmapとlfilterでの評価回数は合計8回。

(どれも遅延リストの要素を取り出した後にカウントを表示しているので、深い方から表示されている)

試しにysのtakeを10000に変えても固定で8回になる。リストが大きければ大きいほど有利になる。素晴らしい。

感想

  • もう遅延シーケンス無しじゃ面倒すぎてプログラム組め無さそう
  • 検証作業楽しかったし、自信が持てるのでバンバンやっていいかも。バンバンやるための環境を整えたい
  • 書いたもの見返して確認するの鬼めんどうだった、そういう職業の人すごいなと改めて思った
広告を非表示にする