Is there a style convention for Common Lisp recursive helper functions?

Question

I would like to know if there is a style guideline, published by ANSI or implementation authors or another influential authority, for Lisp functions which are implemented using recursive helper functions which take additional parameters that the person calling the function doesn't need to think about. Here is the simplest example I can think of. Which of these three, if any, is preferred in a standardized style guide for common lisp (if there is one)?

(defun factorial (n)
   (defun tail-factorial (n m)
      (if (= n 1)
          m
          (tail-factorial (- n 1) (* n m))))
   (tail-factorial n 1))

This seems unpleasant because of the function declaration within the function declaration. I would use a lambda to avoid naming the helper function and convoluting things, but I am not clear how to recurse within a lambda expression by having it call itself. Even if there is a way to have an anonymous function call itself, it seems like it would get messy, especially if the helper needs a helper needs a helper ...

Another alternative is to declare the tail guy first (or after, but that makes sbcl complain):

(defun tail-factorial (n m)
   (if (= n 1)
      n
      (tail-factorial (- n 1) (* n m))))
(defun factorial (n)
   (tail-factorial n 1))

This seems unpleasant because somebody reading my code would see tail-factorial and might feel the need to understand it, even though it's just a helper function for factorial and won't be used elsewhere. In my own code, I keep writing functions analogous to this and I really struggle to come up with comments that will make me re-understand what I did months or years from now. Again, the situation gets really bad here when the helper needs a helper needs a ...

Another alternative uses optionals:

(defun factorial (n &optional (m 1))
   (if (= n 1)
      m
      (factorial (- n 1) (* n m))))

This seems unpleasant because we expect only one argument for a factorial. Nobody outside this function would have a reason to call this with that second argument. I find it annoying to try to understand code with optional arguments I will never use.

Now, I'm clear that asking what you think is best is the kind of subjective conversation stackoverflow dislikes, so my objective question is whether or not there is some kind of standardized style guideline about which of these alternatives is preferred. I use SBCL and have not found a guideline for this sort of thing on their site, and I am not aware of such a guide published by ANSI or any other standardizing body, including other implementors.

Perhaps there is another alternative altogether, and I welcome your suggestions. I keep running into this situation of needing a little helper function (who needs a helper function, etc) and I want to get used to writing in the way most people will find clear. Somebody asked a similar question at Recursing in a lambda function , and several people recommended some favorite pet projects but nobody mentioned a style guideline.

Thanks in advance!

Digitize

Answer 1

defun only makes global functions. If you use defun inside defun you are actually making a new global function at each time you call it. To make a local lexical function to only be used inside factorial the standard way is with labels

(defun factorial (n)
   (labels ((tail-factorial (n m)
              (if (= n 1)
                  m
                  (tail-factorial (- n 1) (* n m)))))
     (tail-factorial n 1)))

Common Lisp has no guarantee to do tail call optimization so this might blow the stack. For serious work you would have used the loop macro to do this.

Optional arguments works, but you really shouldn't make internals optional if it's not the intention that the user would ever want to supply it. Then it's just leaking abstraction and making confusing documentation.

Midrib

Good to know! I'm obviously new to common lisp, but I experimented with scheme in college and I'm revisiting. It is true that common lisp, unlike scheme, does not guarantee tail call optimization. A useful investigation I found before I got started on my current project is 0branch.com/notes/tco-cl.html . Isn't using a loop construct in functional programming considered bad form, kind of reverting to imperative habits? – Digitize

@flagrant2 "Isn't using a loop construct in functional programming considered bad form, kind of reverting to imperative habits?" Some (most?)people probably consider it to be bad form to use imperative loops in functional programming, but that's not really relevant here, since no one's making the claim that Common Lisp is for functional programming (though it can be a nice environment if you chose to use that idiom). – Rech

@flagrant2 Lots of constructs in Common Lisp are explicitly in support of non-functional implementation. One pattern that you will often see, though, is a functional interface with imperative implementations. E.g., you might choose to modify local data, but not arguments passed in to you. – Rech

@flagrant2 It depends. Puritans would call something functional only if there are no mutation involved. You can draw it in the other extreme and say that linear updates doesn't remove the fact that the function is functional as long as it doesn't leak this fact. In the middle I'd say you can use linear update forms where it's safe and the chances of introducing a bug is low. Eg. using loop with collect isn't functional but the dirty stuff doesn't really happen in your code but in the loop implementation. eg. (loop :for n :from 1 :upto n :for m := n :then (* n m) :finally (return m)) . – Midrib

You can get tail recursion if you use my tlet macro instead of labels. Available here: kylheku.com/cgit/lisp-snippets/tree/tail-recursion.lisp. – Seraphim

Answer 2

I think that some of the answers provide more general answers, but I do want to point out that some of the most common uses of tail-recursive helper functions are often very cleanly expressed using a do loop. With a do loop, you declare the variables, their initial values, a step form (the value for the next iteration), a termination condition, and a result form. (Some of those are optional, but we'll use all of them here.) In that sense, a do is more like Scheme's named let, except that you don't end up putting a recursive call in the body. In fact, many times, you end up not needing a body at all. For the factorial function, your code could be expressed as:

(defun factorial (n)
  (do ((n n (1- n))    ; n starts as n, and is (1- n) on next iteration
       (m 1 (* n m)))  ; m starts at 1, and is (* m n) on next iteration
      ((= 1 n) m)))    ; if (= 1 n), then return m, else go to next iteration

CL-USER> (factorial 11)
39916800

Speaking of named let, you can implement it pretty easily in terms of labels in Common Lisp:

(defmacro nlet (name bindings &body body)
  `(labels ((,name ,(mapcar 'first bindings)
              ,@body))
     (,name ,@(mapcar 'second bindings))))

CL-USER> (macroexpand-1 '(nlet factorial ((n n) (m 1))
                          (if (= n 1) m
                              (factorial (1- n) (* m n)))))
(LABELS ((FACTORIAL (N M)
           (IF (= N 1)
               M
               (FACTORIAL (1- N) (* M N)))))
  (FACTORIAL N 1))

That still has the issue that Common Lisp implementations don't have to support tail recursion, though, but it can be a useful utility if you're coming from a Scheme background. You could implement a nlet type macro that makes the recursive call go to the next iteration, but that wouldn't be quite the same, since you only want the "reuse stack frame" behavior in a tail position; in a non-tail position, you'd still want the proper return.

A very subtle bug in the implementation above

As Sylwester pointed out in the comments, there's a very subtle bug in the implementation of nlet above. Because the call to the local function happens within the lexical scope where it's defined, doing something like

(nlet frob ((f #'frob))
   ...)

makes the initializer #'foo a reference to the new local function. That's probably not what you'd want, and it's not what Scheme's named let does. You can get around this by returning the local function from the labels form and calling it outside of that scope:

(defmacro nlet (name bindings &body body)
  `(funcall (labels ((,name ,(mapcar 'first bindings)
                       ,@body))
              #',name)
            ,@(mapcar 'second bindings)))

CL-USER> (macroexpand-1 '(nlet factorial ((n n) (m 1))
                          (if (= n 1) m
                              (factorial (1- n) (* m n)))))
(FUNCALL
 (LABELS ((FACTORIAL (N M)
            (IF (= N 1)
                M
                (FACTORIAL (1- N) (* M N)))))
   #'FACTORIAL)
 N 1)

(defmacro nlet (name bindings &body body)
  `(funcall (labels ((,name ,(mapcar 'first bindings)
                       ,@body))
              #',name)
            ,@(mapcar 'second bindings)))

Rech

my impression is that named-lets (and related) are looking okay for small examples. For more complex code its readability often is worse than a loop construct. YMMV – Mehalek

@RainerJoswig They seem to be pretty popular in Scheme, but I think they get used much more in Scheme because it's the typical way to write a loop. I think it's much more idiomatic to use a proper iteration construct in Common Lisp. – Rech

Wouldn't `(funcall (labels ((,name ,(mapcar #'first bindings) ,@body))#',name) ,@(mapcar #'second bindings)) be better? eg (nlet + ((old #'+)) ...) – Midrib

Answer 3

Good style is:

• useful function name
• documentation string
• argument type checking
• no sources of control stack overflows in portable code -> mostly avoid tail-recursive code

Example:

(defun factorial (n &aux (result 1))
  "Calculates the factorial N! for N >= 0"
  (check-type n (integer 0 *))
  (loop for i from 1 to n
        do (setf result (* result i)))
  result)

Using:

CL-USER 94 > (apropos "factorial")
FACTORIAL (defined)

CL-USER 95 > (documentation 'factorial 'function)
"Calculates the factorial N! for N >= 0"

CL-USER 96 > (factorial 7)
5040

Mehalek