Optional function argument with default value in Common Lisp

Question

Here's a function I was writing that will generate a number list based on a start value, end value and a next function.

(defun gen-nlist (start end &optional (next #'(lambda (x) (+ x 1))))
    (labels ((gen (val lst)
        (if (> val end) 
            lst
            (cons val (gen (next val) lst)))))
    (gen start '())))

However when entering it into the SBCL repl I get the following warnings:

; in: DEFUN GEN-NLIST
;     (SB-INT:NAMED-LAMBDA GEN-NLIST
;         (START END &OPTIONAL (NEXT #'(LAMBDA (X) (+ X 1))))
;       (BLOCK GEN-NLIST
;         (LABELS ((GEN #
;                    #))
;           (GEN START 'NIL))))
; 
; caught STYLE-WARNING:
;   The variable NEXT is defined but never used.

;     (NEXT VAL)
; 
; caught STYLE-WARNING:
;   undefined function: NEXT
; 
; compilation unit finished
;   Undefined function:
;     NEXT
;   caught 2 STYLE-WARNING conditions

Somehow it does see the variable next as defined, but not used. And where I do use it, as in (next val), it's an undefined function?!

Clearly I'm doing something wrong here. I just can't figure what or how. Is this the correct way of specifying optional function arguments with default values?

Goodsell

If you want to post a/the solution, you should post it as an answer. Not include it as an edit in the question. Questions are for questions. Answers are for answers. – Giffer

Makes sense. Changed. – Goodsell

Answer 1

You have defined the optional argument the correct way, but as Common Lisp is a Lisp-2, it distinguishes between functions and variable values. The optional function is available as a variable, and has to be called using funcall.

Replace

(cons val (gen (next val) lst))

with

(cons val (gen (funcall next val) lst))

and both the warning about the unused variable and the warning about the undefined function will disappear.

BTW: Your default function can be replaced with #'1+

Buine

Also it should be (gen (funcall ...) (cons ...)) for tail recursion to work. – Zita

@Zita Nope, that changes the order of things. That's an entirely different function and would have to be written that way. Although yes, the one I wrote isn't tail recursive. – Goodsell

@λ- You have to reverse the list too of course. As it is now, the LST parameter is unnecessary. – Zita

Answer 2

The simple recursive version has a main problem: stack overflow for long lists. It's useful as a learning exercise, but not for production code.

The typical efficient loop iteration would look like this:

(defun gen-nlist (start end &optional (next #'1+) (endp #'>))
  (loop for i = start then (funcall next i)
        until (funcall endp i end)
        collect i))

Embry

I ran the loop version (L) above, and a simple recursive version (SR), and a tail recursive version(TR) (the latter two as per my answer), and timed each for various ranges. SR fails at about 100,000 elements by running out of call stack. But L and TR both give up only at 100,000,000 by running out of heap space. L seems to be about 30% or so faster. Why is this? Both L and TR run out of heap, so they must both pattern down to some iterative process, right? What then is different about loop that it is faster than tail recursion? – Goodsell

Answer 3

In case if anyone ever does need to see the functioning code in full, thanks to the answer above and the comments, here's what I ended up with:

(defun gen-nlist (start end &optional (next #'1+) (endp #'>))
    (labels ((gen (val)
        (if (funcall endp val end) 
            '()
            (cons val (gen (funcall next val))))))
      (gen start)))

And here's the tail recursive version which doesn't suffer from a function call stack overflow, when attempting to create large lists:

(defun gen-nlist (start end &optional (next #'1+) (endp #'>))
    (labels ((gen (val lst)
        (if (funcall endp val end) 
            (reverse lst)
            (gen (funcall next val) (cons val lst)))))
      (gen start '())))

Usage examples:

> (gen-nlist 0 10)

(0 1 2 3 4 5 6 7 8 9 10)

> (gen-nlist 0 10 #'1+ #'equal)

(0 1 2 3 4 5 6 7 8 9)

> (gen-nlist 0 -10 #'1- #'<)

(0 -1 -2 -3 -4 -5 -6 -7 -8 -9 -10)

> (gen-nlist -10 0)

(-10 -9 -8 -7 -6 -5 -4 -3 -2 -1 0)

Goodsell

If you would use automatic indentation support by an editor, the code would be indented slightly different. The last call is inside the LABELS. Not on the same level. The body of the GEN function needs to be indented more to the right... – Embry

I thought so too, but my editor for some reason insists on indenting in this incorrect way. I'm going to check its auto indent bindings. – Goodsell