Monday, August 30, 2021

Tail recursion and fold-left

fold-left has this basic recursion:

(fold-left f init ())      = init
(fold-left f init (a . d)) = (fold-left f (f init a) d)
A straightforward implementation of this is
(defun fold-left (f init list)
  (if (null list)
      init
      (fold-left f (funcall f init (car list)) (cdr list))))
The straightforward implementation uses a slightly more space than necessary. The call to f occurs in a subproblem position, so there the stack frame for fold-left is preserved on each call and the result of the call is returned to that stack frame.

But the result of fold-left is the result of the last call to f, so we don't need to retain the stack frame for fold-left on the last call. We can end the iteration on a tail call to f on the final element by unrolling the loop once:

(defun fold-left (f init list)
  (if (null list)
      init
      (fold-left-1 f init (car list) (cdr list))))

(defun fold-left-1 (f init head tail)
  (if (null tail)
      (funcall f init head)
      (fold-left-1 f (funcall f init head) (car tail) (cdr tail))))

There aren't many problems where this would make a difference (a challenge to readers is to come up with a program that runs fine with the unrolled loop but causes a stack overflow with the straightforward implementation), but depending on how extreme your position on tail recursion is, this might be worthwhile.

4 comments:

A. V. said...

The straightforward implementation also allows to re-use single stack frame, instead allocating new one for every call.

The version compiler would generation, by replacing the recursive call with assignment to the parameters in the current stack frame and goto the beginning of the function body:


(defun fold-left (f init list)
(loop
(if (null list)
(return init)
(setf f f
init (funcall f init (car list))
list (cdr list))))))

A. V. said...

(sorry for the typos - "instead of", "would generate", I wanted to say)

Joe Marshall said...

Here is code that can test if your implementation of fold-left is tail-recursive on its last call:

(defun testit (n)
..(if (zerop n)
......t
......(fold-left #'cl:funcall #'testit (list (- n 1)))))

If fold-left is tail-recursive on its last call, then this function will be tail-recursive and (testit 1000000) will run to completion. If fold-left is not tail-recursive, (testit 1000000) will likely overflow the stack.

A. V. said...

Ah, you mean recursion through F, when F calls FOLD-LEFT...