A comparison between using labels vs helper-and-main at the top level vs nested defun's in Common Lisp. Which is the best?

Question

I am trying to learn Common Lisp with the book Common Lisp: A gentle introduction to Symbolic Computation. In addition, I am using SBCL, Emacs, and Slime.

In the advanced section of chapter 8, the author presents the labels special function. Actually, he draws a contrast between defining things on top-level (main and helper functions) versus using label expression inside a function.

For instance, this would be a reverse list function with tail call using the top-level approach:

(defun reverse-top-level-helper (xs-left accu)
  (cond ((null xs-left) accu)
        (t (reverse-top-level-helper (cdr xs-left)
                                     (cons (car xs-left)
                                           accu)))))
(defun reverse-top-level-main (xs)
  (reverse-top-level-helper xs nil))

On the other hand, the code below would do the same using labels:

(defun reverse-labels (xs)
  (labels ((aux-label (xs-left accu)
           (cond ((null xs-left) accu)
                 (t (aux-label (cdr xs-left)
                         (cons (car xs-left) accu))))))
    (aux-label xs nil)))

So, the label approach avoids the chance that people will mess-up with the helper function on the top-level. Differently from the top level approach, the label way gives access to the local variables of the main function.

Unfortunately, according to the author, there is no way to trace functions inside label expressions in most lisp implementations. This seems to be my case since I get this from the REPL:

CL-USER> (trace aux-label)
WARNING: COMMON-LISP-USER::AUX-LABEL is undefined, not tracing.
NIL

The point that intrigues me is the fact that the author does not show a third approach that is quite common in Racket. I will call it nested defuns.

The same problem would be solved as:

(defun reverse-racket-style (xs)
  (defun aux (xs-left accu)
    (cond ((null xs-left) accu)
          (t (aux (cdr xs-left) (cons (car xs-left) accu)))))
  (aux xs nil))

In this approach the helper function can access the local variables from the main function. It can also be traced by the REPL.

I have been using it all day. So I know it works in a file with many functions using it. Actually, I do not even know how trace works so well considering that I am using a bunch of different helper functions and all of them have the same name being called aux under the racket style. The trace knows which aux I wanna see.

Above all, this omission really intrigues me. Specially because I am really enjoying the book. I guess I am probably missing something.

1 - Why this approach was not mentioned? Is this "racket style" with nested defuns considered bad style in Common Lisp?

2 - Did I miss some important detail (e.g. this approach could be the source of hard to find bugs or generate performance issues)?

3 - Is there some historical reason for this omission?

Answer 1

Yes, there are good reasons. In Racket, we have define

In an internal-definition context, a define form introduces a local binding; see Internal Definitions. A the top level, the top-level binding for id is created after evaluating expr

So, as you said, a define in a local context (such as a function body) defines a local function, with access to the enclosing variables and which only exists during that function.

Now compare that to Common Lisp's defun

Defines a new function named function-name in the global environment.

So, regardless of where a defun appears, it always defines a name at the global scope, with no access to local variables and with a name that becomes globally available. So your suggestion for a nested defun is really equivalent to defining the defun at the top-level (in the sense that the name is available at the top-level and in the sense that local variables are inaccessible), except that the name doesn't exist until you've called the original function at least once, which is, frankly, fairly unintuitive behavior.

Incidentally, the labels approach is the thing you want. In Common Lisp, if we want local helper functions, we use flet (for non-recursive functions) or labels (for recursive functions).

As to why this is, Common Lisp tries to enforce a very clear variable scope at all times. In any function, local variables are introduced with (let ...) and only exist inside of the block, and local functions are introduced with (flet ...) and (labels ...). Racket has similar constructs but also allows the more Scheme-like paradigm (Racket is a Scheme dialect, after all) of using define to define local variables for the rest of the current scope, similar to how you'd do it in more imperative languages.

Answer 2

Don't write nested defuns.

Writing nested defuns is usually a mistake. defun (and most other defsomething operators) are thought to be used at top-level. Top-level usually means as a top-most expression or nested only in prognor eval-when. Then a file compiler will recognize these macros.

As a nested function, the compiler does not recognize a defun. Calling the outer function will define the inner function on each call and globally.

Example:

(defun foo ()
 (defun bar ()
   20))

(defun baz ()
  (defun bar ()
    30))

Now do:

(bar)  ;  -> error undefined function BAR

(foo)
(bar)    ;   -> 20
(baz)
(bar)    ;   -> 30
(foo)
(bar)    ;   -> 20
(baz)
(bar)    ;   -> 30
...

Oops! The global function BAR gets overwritten on each call of FOO and of BAZ.

Nested functions

Use FLET and LABELS for defining local functions.

DEFUN does not define local lexical functions. It defines global functions with symbols as their names.

CL-USER 77 > (defun one ()
               (defun two ()
                 40))
ONE

CL-USER 78 > (fboundp 'two)
NIL

CL-USER 79 > (one)
TWO

CL-USER 80 > (fboundp 'two)
T

Tracing local functions

(trace aux-label)

Above is typically not how one traces local functions. That syntax traces global functions.

To trace local functions consult the manual of your Lisp implementation for the documentation of the trace macro. It may support tracing local functions, but then has a special syntax for doing so.

Answer 3

If you need to trace, labels can be annoying to use. Here is a little helper macro that defines labels*, a variant of labels that traces the execution of the functions being called.

Here is the function printing the trace:

(defun depth-trace (io depth name args)
  (let ((*standard-output* *trace-output*))
    (fresh-line)
    (dotimes (i depth) (princ (case io (:in "| ") (:out ": "))))
    (format t "~a. ~a ~s~%" depth name args)))

The macro uses alexandria:with-gensyms, defines a local special depth variable that keep tracks of recursion levels, and add side-effects to the defined functions to print the trace.

(defmacro labels* ((&rest bindings) &body body)
  (alexandria:with-gensyms ($depth $result $args)
    (loop
      with special = `(declare (special ,$depth))
      for (name args . fn-body) in bindings
      collect `(,name (&rest ,$args)
                      ,special
                      (depth-trace :in ,$depth ',name ,$args)
                      (let ((,$result
                              (multiple-value-list
                               (let ((,$depth (1+ ,$depth)))
                                 ,special
                                 (apply (lambda (,@args) ,@fn-body) ,$args)))))
                        (depth-trace :out ,$depth ',name ,$result)
                        (values-list ,$result)))
      into labels-bindings
      finally
         (return
           `(let ((,$depth 0))
              ,special
              (labels ,labels-bindings ,@body))))))

For example:

(labels* ((a (b) (if (> b 0) (* 2 (a (- b 2))) (- b))))
  (a 11))

This prints:

0. A (11)
| 1. A (9)
| | 2. A (7)
| | | 3. A (5)
| | | | 4. A (3)
| | | | | 5. A (1)
| | | | | | 6. A (-1)
: : : : : : 6. A (1)
: : : : : 5. A (2)
: : : : 4. A (4)
: : : 3. A (8)
: : 2. A (16)
: 1. A (32)
0. A (64)

It also works with mutually recursive functions:

(labels* ((a (x) (* x (b x)))
          (b (y) (+ y (c y)))
          (c (z) (if (> z 0) (* 2 z) (a (- z)))))
  (a -5))

The trace is:

0. A (-5)
| 1. B (-5)
| | 2. C (-5)
| | | 3. A (5)
| | | | 4. B (5)
| | | | | 5. C (5)
: : : : : 5. C (10)
: : : : 4. B (15)
: : : 3. A (75)
: : 2. C (75)
: 1. B (70)
0. A (-350)