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

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

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

# はじめに

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

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

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

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

```emacs-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`した関数を実行した際にエラーが発生する場合があります)

```emacs-lisp
(setq lexical-binding t)
```

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

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

```emacs-lisp
;; 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
;; Emacs Lisp 正格評価版
(require `seq)

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

# lazy.el 入門

一番単純な例として

```emacs-lisp
(lz-range)
```

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

```emacs-lisp
(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 個を取得してみます。

```emacs-lisp
(lz-take (lz-range) 10)
```

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

```emacs-lisp
(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`で終了させてください。

```emacs-lisp
(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`を参考にすると以下のようになります。

```emacs-lisp
(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)))
```

これを使って

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

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

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

```emacs-lisp
(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`の違いによるものです。

```emacs-lisp: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`に追加するオプションです。

```shell
$ 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](http://mnzk.hatenablog.com/entry/2012/12/20/020244)

Scheme だけど参考になる (`delay-force`は`lazy.el`の`lz-lazy`の事で、`even stream`,`odd stream`の違いの解説もある)
[R7RSのdelay-forceとは何か](https://nacl-ltd.github.io/2016/05/31/delay-force.html)

関数プログラミングする場合は必読
[なぜ関数プログラミングは重要か](http://www.sampou.org/haskell/article/whyfp.html)