なぜfor文は禁止なのか？関数型記述のススメ (Emacs Lisp 遅延評価版) 改訂版

改訂について (2018/10/12)

改定前は「stream.elを使う事でEmacs自体が落ちる」旨がそこかしこに書かれているので、やっぱりそれじゃ駄目だろ…と思い、この記事用に自前で落ちない遅延評価ライブラリを作成したので改訂しました。

はじめに

なぜfor文は禁止なのか？関数型記述のススメ
https://qiita.com/ukiuni@github/items/abad07524856c65a20ea

上記サイトのEmacs Lisp遅延評価版を掲載して、使われている遅延評価ライブラリのlazy.elの使い方を解説します。
なぜ関数プログラミングは重要かによると、関数プログラミング(Functional Programming)にとっては、高階関数と遅延評価が重要である旨が書かれています。

上記サイト(なぜfor〜)では、最終的に高階関数は使われていますが遅延評価は使われていません。
それによる弊害として1〜100までの数列を最初に全部作成してしまっています。
この場合は言うまでもなく、個数が多ければ多いほど最初に膨大なメモリを消費しかねません。
遅延評価を使えば、それを回避することが出来ます。

使っている遅延評価ライブラリは以下のサイトにあります。
https://github.com/chuntaro/lazy.el
これを適当なディレクトリにクローンしてlazy.elをバイトコンパイルしておいてください。
以下、カレントディレクトリにlazy.elcがある事を前提に進めます。
ちなみに、必要なのはlazy.elだけなので、以下の lisp を実行すればファイルの取得とバイトコンパイルとロードを行えます。

(cd "~/.emacs.d/elisp")
(url-copy-file "https://raw.githubusercontent.com/chuntaro/lazy.el/master/lazy.el" "lazy.el")
(byte-compile-file "lazy.el" t)

上記のように式だけ書いてある場合は*scratch*バッファにコピーして評価すると思いますが、以下の設定だけはしておいてください。(しなかった場合は、*scratch*バッファでdefunした関数を実行した際にエラーが発生する場合があります)

(setq lexical-binding t)

このlazy.elはSRFI 45で定義されているdelay, force, lazyを Emacs Lisp で実装し、ユーティリティ関数群にseq.elとstream.elで定義されているものを移植したものになります。
delay, forceの使い方は一番下の参考に書かれているサイト等を参照してください。
ユーティリティ関数群は、一先ずこの記事が書ける程度のものしか移植していません。
(基本的に無限リスト関連のみで、移植してないものは無限リストを通常のリストに変換した後seq.elを使えば済むものがほとんどです)

で、最初に書いた参照元サイトの命題**「0から100未満の偶数のみを累計する。」**を、lazy.elを使って書くと以下のようになります。

;; Emacs Lisp 遅延評価版
(require 'lazy) ;; or (load "/path/to/lazy.elc")

(lz-reduce #'+ (lz-filter #'cl-evenp (lz-range 1 100)) 0) ;; => 2450

ちなみに、Emacs に標準添付のseq.elを使って書くと以下のようになります。
number-sequenceが実行された時点で(1 2 ... 99)のリストが作成されてしまっている違いがあります。

;; Emacs Lisp 正格評価版
(require `seq)

(seq-reduce #'+ (seq-filter #'cl-evenp (number-sequence 1 99)) 0) ;; => 2450

lazy.el 入門

一番単純な例として

(lz-range)

これを*scratch*等で評価すると…

(lz-range) ;; => ((lz-lazy . #[0 "\300\242\204	^@\300\303\240\210\302\242\204^R^@\302\304\240\210\300\242\301\232\203^^^@\305\306BC\207\305\307\303\310\311\312\300\301\302#\313\"\314$BC\207" [(nil) nil (nil) 0 1 lz-lazy #[0 "\300\301^ABC\207" [nil lz-eager] 3] make-byte-code "\300\242\303\300\242\302\242\\\301\302\242#B\304^ABC\207" vconcat vector [lz-range lz-eager] 5] 9]))

何か変な値が表示されたと思いますが、これが整数の無限リスト(オブジェクト)を表しています。
概念的には(0 1 2 3 4 5 6 7 ...無限に続く)となります。

無限だと不便なので最初の 10 個を取得してみます。

(lz-take (lz-range) 10)

これでもまだ無限リスト(オブジェクト)の状態なので、通常のリストに変換します。

(lz-into-list (lz-take (lz-range) 10)) ;; => (0 1 2 3 4 5 6 7 8 9)

これでようやく見て分かる状態になりました。最終的にはリストに変換するはずなので、この形が基本になります。

次に**「整数を 0 から合計して行って 10,000 以上の最小値を表示する」**というタスクを実装してみます。
整数の合計なので、最初に例示したようにlz-rangeとlz-reduceを組み合わせれば良いように思いますが、
lz-findを使用して以下のようにしてみても、終了しません。C-gで終了させてください。

(lz-find (lambda (n) (>= n 10000)) (lz-reduce #'+ (lz-range) 0))

これは、lz-reduceが(lz-range)が生成した無限リストに対して実行されている為、途中で止まる事が無い為です。
(最初の例示では(lz-range 1 100)と有限の範囲でした)

そういう場合にはlz-reduce-whileを使います。
ちなみに、改訂前に使っていたstream.elにはstream-reduce-whileが無い為、自作する必要がありましたが、lazy.elには最初から追加されてます。ここでは、自分で実装した体で進めます。
lz-reduceやlz-findを参考にすると以下のようになります。

(defun lz-reduce-while (pred function stream initial-value)
  (if (lz-empty-p stream)
      initial-value
    (let ((acc initial-value))
      (catch 'lz--break
        (lz-dostream (elt stream)
          (setq acc (funcall function acc elt))
          (unless (funcall pred acc)
            (throw 'lz--break nil))))
      acc)))

これを使って

(lz-reduce-while (lambda (n) (< n 10000))
                 #'+
                 (lz-range)
                 0) ;; => 10011

と実装する事が出来ました。

次にフィボナッチ数列の最初の 20 個を表示する遅延評価版を作成します。

(defun lazy-fib ()
  (cl-labels ((rec (a b)
                   (lz-cons (+ a b)
                            (rec (+ a b) a))))
    (lz-cons 0 (lz-cons 1 (rec 1 0)))))

(lz-into-list (lz-take (lazy-fib) 20)) ;; => (0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181)

特徴としては終了判定が必要無くて、無限にコンスセルが繋って見えるところです。
もちろん実際は無限にコンスセルが作られてる訳ではなく、再帰呼び出しにすらなってないのです。

どうでしょうか？最終的なコードは for 文を使わずに、非常に綺麗なコードになってると思います。
望むオペレーターが無い場合は、一段階下りてオペレーター自身を実装する必要が出てきますが、出来たものは再利用出来るもので、関数プログラミングのモジュラー性というものを表してると思います。

最後に遅延評価のお約束とも言えるtaraiを実行してみます。
参考で挙げたサイトにも同じ内容がありますが、コードに少し違いがあります。
odd streamとeven streamの違いによるものです。

lazy-tarai.el

;;; -*- lexical-binding: t; -*-

(require 'lazy)

(eval-when-compile
  (defmacro time (&rest body)
    "Measure the time it takes to evaluate BODY."
    `(let ((time (current-time)))
       ,@body
       (print (float-time (time-since time))))))

(defun tarai (x y z)
  "正格評価版"
  (if (<= x y)
      y
    (tarai (tarai (1- x) y z)
           (tarai (1- y) z x)
           (tarai (1- z) x y))))

(defun lazy-tarai (x y z)
  "遅延評価版"
  (lz-lazy
   (if (<= (lz-force x) (lz-force y))
       y
     (lazy-tarai (lazy-tarai (lz-delay (1- (lz-force x))) y z)
                 (lazy-tarai (lz-delay (1- (lz-force y))) z x)
                 (lazy-tarai (lz-delay (1- (lz-force z))) x y)))))

(time (print (tarai 13 6 0)))
(time (print (lz-force (lazy-tarai (lz-delay 13) (lz-delay 6) (lz-delay 0)))))

このソースコードをバイトコンパイルしてから実行してみます。
-L .はカレントディレクトリをload-pathに追加するオプションです。

$ emacs --batch -L . -f batch-byte-compile lazy-tarai.el
$ emacs --batch -L . -l lazy-tarai.elc

13
4.530629 sec

13
0.000000 sec

なんと！遅延評価版は計測不能なほど高速に実行されています！
正格評価版はtaraiが76,527,789回も実行されているのに対して、遅延評価版はlazy-taraiが169回しか実行されていませんでした。
それが実行速度の差に出たようです。

ちなみにlz-forceは553回実行されていました。lz-forceは値の生成を文字通り強制する訳なのでlazy-taraiが553回実行されていてもいいものですが、lz-delayで生成されたpromiseは一度評価した値をキャッシュしている為、無駄なlazy-taraiの実行が抑制されています。

ちなみに、これは遅延評価が極端に有効に働くベンチマークなので、遅延評価が常に高速に実行される訳ではありません。
遅延評価にはオーバーヘッドが有る為、却って遅くなる可能性もあります。

まとめ

Emacs で無限リストを使う機会は中々無いのかも知れません…。ただ、遅延評価ひいては関数プログラミングをフル活用して書かれたコードは綺麗ですね。

コーディングしていて、(while tを書いてcatchとthrowで抜けるみたいなコードを書いていた場合は、遅延評価(無限リスト)を使うチャンスかもしれません！
上手く行けば、間違いなくモジュラー性に優れた綺麗なコードになっているでしょう！

Emacs にはseq.elとそれを無限リストが扱えるように拡張したstream.elという素晴らしいライブラリがありますが、簡単に Emacs 自体が落ちる問題があるので、lazy.elが遅延評価を Emacs でちょっと試してみようという場合の代替になればと思います。

参考

遅延リストの実装を知りたい場合は↓ここ
遅延リスト遊び - Emacsで学ぶLazyな世界(前編) - Code Aquarium

Scheme だけど参考になる (delay-forceはlazy.elのlz-lazyの事で、even stream,odd streamの違いの解説もある)
R7RSのdelay-forceとは何か

関数プログラミングする場合は必読
なぜ関数プログラミングは重要か