An efficient collect function in Common Lisp

Question

I'm learning Lisp and have written the following function to collect a list of results.

(defun collect (func args num)
  (if (= 0 num)
      ()
      (cons (apply func args)
        (collect func args (- num 1)))))

It produced similar output to the built in loop function.

CL-USER> (collect #'random '(5) 10)
(4 0 3 0 1 4 2 1 0 0)
CL-USER> (loop repeat 10 collect (random 5))
(3 3 4 0 3 2 4 0 0 0)

However my collect function blows the stack when I try to generate a list 100,000 elements long

CL-USER> (length (collect #'random '(5) 100000))
Control stack guard page temporarily disabled: proceed with caution

Whereas the loop version doesn't

CL-USER> (length (loop repeat 100000 collect (random 5)))
100000

How can I make my version more space efficient, are there alternatives to consing? I think it's tail recursive. I'm using sbcl. Any help would be great.

Answer 1

No, it is not tail recursive. Neither ANSI Common Lisp says anything about it nor your code:

(defun collect (func args num)
  (if (= 0 num)
      ()
      (cons (apply func args)
            (collect func args (- num 1)))))

If you look at your code, there is a CONS around your call to COLLECT. This CONS receives the value of the recursive call to COLLECT. So COLLECT can't be tail recursive. It's relatively simple to rewrite your function to something that looks tail recursive by introducing an accumulator variable. The various Lisp or Scheme literature should describe that.

In Common Lisp the default way to program an iterative computation is by using one of the several iterative constructs: DO, DOTIMES, DOLIST, LOOP, MAP, MAPCAR, ...

The Common Lisp standard does not provide tail call optimization (TCO). It would have to be specified what TCO should do in the presence of several other language features. For example dynamic binding and special variables have an effect on TCO. But the Common Lisp standard says simply nothing about TCO in general and about possible effects of TCO. TCO is not a part of the ANSI Common Lisp standard.

Several Common Lisp implementations have a way to enable various tail call optimizations with compiler switches. Note that both the way to enable those and the limitations are implementation specific.

Summary: In Common Lisp use iteration constructs and not recursion.

(defun collect (func args num)
  (loop repeat num
        collect (apply #'func args)))

Added bonus: it is easier to read.

Answer 2

Common Lisp implementations are not required by the ANSI standard to do tail call optimization; however, most that worth their salt (including SBCL) do optimize.

Your function, on the other hand, is not tail recursive. It can be turned into one by using the common trick of introducing an extra parameter for accumulating the intermediate result:

    (defun collect (func args num)
      (labels ((frob (n acc)
                 (if (= 0 n)
                     acc
                     (frob (1- n) (cons (apply func args) acc)))))
        (frob num nil)))

(The original parameters FUNC and ARGS are eliminated in the local function since they are constant with recpect to it).