lazy eval vs tail recursion 遅延評価と末尾再帰はそりがあわない？

実は知ってる人は知っているみたいですね。自分は初めて気が付きました。
I found this fact is broadly shared in Haskell community.

[this post](http://jinvii.blogspot.jp/2012/05/notes-on-lazy-evaluation-tail-recursion.html) says "when lazy evaluation is available, tail recursion is meaningless". Especially in Haskell. In this post I'd like to show it in CL.

以下は、permutationの計算のコードです。末尾再帰。
Below is the tail-recursive version of code that produces a permutation of a sequence(list). The algorithm is based on Steinhaus–Johnson–Trotter algorithm + Even's speedup.

```cl
(defun %permutations-of-cons (seq)
  (match seq
    ((list _)
     (list seq))
    ((list* head rest-seq)
     (let* ((len (length seq))
            (n (1- len))) ; n -- 2, length -- 3
       (labels 
           ((insert (subperm pos)
              (let (acc (%subperm subperm))
                (dotimes (i pos)        ; i = 0
                  (push (car %subperm) acc)
                  (setf %subperm (cdr %subperm)))
                (push head acc); pos = 1
                (dotimes (i (- n pos))  ; 2 - 1 = 1
                  (push (car %subperm) acc)
                  (setf %subperm (cdr %subperm)))
                (nreverse acc)))
                                        ;
            (forward (subperms pos acc) ; pos -- 0,1,2
              (ematch subperms
                ((cons subperm rest)
                 (if (< pos n)
                     (forward subperms (1+ pos)
                              (cons (insert subperm pos) acc))
                     (backward rest pos
                               (cons (insert subperm pos) acc))))
                (_ acc)))
            (backward (subperms pos acc)
              (ematch subperms
                ((cons subperm rest)
                 (if (< 0 pos)
                     (backward subperms (1- pos)
                               (cons (insert subperm pos) acc))
                     (forward rest pos
                              (cons (insert subperm pos) acc))))
                (_ acc))))
         (forward (%permutations-of-cons rest-seq) 0 nil))))))
```

Here, in order to avoid consuming the stack frame, all `label`led functions are defined in a tail-recursive manner. `cons` is evaluated first, then the result of either continuations, `backward` and `forward`, is returned unmodified.

Contrary, below is the same code but assuming the lazy-evaluation. This is **not** tail-recursive. Since the evaluations of the tails are delayed, we do not have to care about the stack exhaust. In the first call, it uses only O(1) stacks. Moreover, that stack will be released immediately -- because the function returns at the same time.

```cl
(defun %lpermutations-of-cons (seq length)
  (match seq
    ((list _)
     (llist seq))
    ((list* head rest-seq)
     (let* ((n (1- length))) ; n -- 2, length -- 3
       (labels 
           ((insert (subperm pos)
              (let (acc (%subperm subperm))
                (dotimes (i pos)        ; i = 0
                  (push (car %subperm) acc)
                  (setf %subperm (cdr %subperm)))
                (push head acc); pos = 1
                (dotimes (i (- n pos))  ; 2 - 1 = 1
                  (push (car %subperm) acc)
                  (setf %subperm (cdr %subperm)))
                (nreverse acc)))
            (forward (subperms pos)
              (match subperms
                ((lcons subperm rest)
                 (if (< pos n)
                     (lcons (insert subperm pos) (forward subperms (1+ pos)))
                     (lcons (insert subperm pos) (backward rest pos))))))
            (backward (subperms pos)
              (match subperms
                ((lcons subperm rest)
                 (if (< 0 pos)
                     (lcons (insert subperm pos) (backward subperms (1- pos)))
                     (lcons (insert subperm pos) (forward rest pos)))))))
         (forward (%lpermutations-of-cons rest-seq (1- length)) 0))))))
```

Also, if I implement the lazy version in a tail-recursive manner, it diminishes the advantages of lazy evaluation. In this case, the resulting list of permutations are constructed `from the tail`, `once at the first call`, `entirely`. Even though each element is delayed.

```cl
(backward subperms (1- pos)
          (lcons (insert subperm pos) acc))
```

じゃあ末尾再帰と遅延評価どちらがいいかというと、自分の方針としては

+ メモリが爆発するとき（全部の結果をメモリに置いておくことができない)だけは遅延評価

という感じですね。
書き捨て御免!