helper nested functions in CL

Question

I used to write nested helper functions (which, btw, ocasionally used parameters of outer functions and are recursive) in Haskell like this (loop):

sum a b = let
  loop s i = if i > b then s else loop (s + i) (i + 1)
  in loop 0 a

What is the clearest analog for this in Common Lisp?

I searched around here and found some discussions focused on returning functions from functions (and the problems which may arise when trying to call such “returned” functions) which is not quite the same situation, as far as I can see.

Cootch

While helper functions are common in Lisp, iterating in this way is discouraged. Google coding standards tell you to prefer iteration over recursion. This is of course not an answer to your question, but I thought it might be useful regardless. – Occupational

@wvxvw, the use of Haskell's recursion in this case seems to be in a tail position, much like Scheme's named let when the name is invoked in a tail position. It ends up being a go-to or a tail call, e.g. iteration in disguise. What should be noted is that Common Lisp doesn't guarantee tail calls, so one needs to excplicitly use iterative approaches to avoiding stack overflow. – Emmettemmey

@PauloMadeira well, OP writes in Common Lisp. And that's definitely not how you'd iterate in CL. On the side note, and I think that Lisp code in the answers subconsciously fixed it: OP probably meant ... then s else loop ... instead of ... then sum else loop .... OP's version wouldn't compile in Haskell. GHC would have this understood as infinite type. – Occupational

@wvxvw thank you for your comments! As a CL noob I appreciate them very much. My explanation for the choice of tail recursion… Well, that's long story. We actually studing principles of functional prog. on Lisp at my University. I'm serving as TA and the Lisp is chosen by the lecturer. (I would prefer Haskell.) I use Touretzky's book on Lisp, he gave examples of recursion prior to DO-stuff as well. – Cootch

Yup, for some reason it is common (well, in some sense of "common") to insist that CL is a functional language, or that it is a good candidate for learning FP. I'm not a great fan of FP, especially not of Haskell :) but CL is just not a good choice / very not idiomatic for FP. There are libraries that make functional programming more tolerable in CL (functional containers, helper functions for common idioms such as composition, currying etc.) But they owe their existence to the fact of the aforementioned confusion. CL is about programming comfort, meta-programming and research. – Occupational

The rigidity of functional programming is foreign to it. It never pretended nor intended to adhere to arbitrary chosen mathematical formalisms, whereas functional programming languages are all about that. – Occupational

@wvxvw I'd like to emphasize: we teach functional programming and use CL as a possible (maybe not the best) tool for it. May FP be just “wrong”? Yes may be, but we consider it's ideas valuable for modern developer. So there is no big deal about Lisp (or particulary CL) in our classes. You may consider this as fallacy though: I can understand this and agree to some extent. As I mentioned earlier, I'd prefer to take Haskell. – Cootch

Answer 1

Labels is used to define local functions.

CL-USER> (defun thing (x)
           (labels ((helper (y) (loop for i from x to y collect i)))
             (helper 5)))
THING
CL-USER> (thing 1)
(1 2 3 4 5)

It is kind of like a let* statement for functions as you can define multiple local functions. So here we have helper and double-it being defined.

(defun thing (x)
   (labels ((helper (y) (loop for i from x to y collect i))
            (double-it (num) (* 2 num)))
     (helper (double-it 10))))

Also you could use lambdas. Which in this instance is fairly tidy, though I still prefer labels for readability in this case.

CL-USER> (defun another-test (x)
           (funcall #'(lambda (y) (loop for i from x to y collect i)) 10))
ANOTHER-TEST

CL-USER> (another-test 2)
(2 3 4 5 6 7 8 9 10)

Labels can also be used recursively:

CL-USER> (defun test-recurse (x)
           (labels ((rec-list (count) 
                      (when (< count x) 
                        (cons count (rec-list (+ 1 count))))))
             (rec-list 0)))
TEST-RECURSE
CL-USER> (TEST-RECURSE 10)
(0 1 2 3 4 5 6 7 8 9)

Hope it helps!

Chartism

I tried to use recursion in function defined by labels: clisp complains: EVAL: function IMPL is not defined (my translation of localized message I have). Here impl is the function defined with labels recursively. – Cootch

@ArtemPelenitsyn Haskell doesn't have the concept of non-recusrive binding (but it exists in similar languages, such as OCaml), where this would be a distinction between let rec and let. In Common Lisp there is this difference too, it uses labels analogously to let rec and flet analogously to let. – Occupational

@wvxvw: Cheers for the clarification, I'm looking forward to learning haskell but haven’t done so yet – Chartism

Artem, probably the most likely mistake to cause your error would be to have the call to impl placed outside of the labels form rather than inside of it. Check your syntax, look for typos. – Lung

@Lung yes, I placed call to impl outside of the labels! Thank very much! – Cootch

Answer 2

Labels and named lets if your Lisp optimizes tail calls

Just as a matter of playing "stupid Lisp tricks", I'd point out that in Scheme, the analog to

sum a b = let
  loop s i = if i > b then sum else loop (s + i) (i + 1)
  in loop 0 a

is letrec or a named let:

(define (sum a b)
  (letrec ((loop (lambda (s i)
                   (if (> i b)
                       s
                       (loop (+ s i) (+ i 1))))))
    (loop 0 a)))

(define (sum a b)
  (let loop ((s 0) (i a))
    (if (> i b)
        s
        (loop (+ s i) (+ i 1)))))

Letrec, because Scheme is a Lisp-1, gives you the functionality of labels, which Baggers described. The named let can be done in Common Lisp with a macro around labels:

(defmacro named-let (name bindings &body body)
  `(labels ((,name ,(mapcar 'first bindings)
              ,@body))
     (,name ,@(mapcar 'second bindings))))

(pprint (macroexpand
 '(named-let loop ((s 0) (i a))
   (if (> i b)
       s
       (loop (+ s i) (+ i 1))))))

;; (LABELS ((LOOP (S I)
;;            (IF (> I B)
;;                S
;;                (LOOP (+ S I)
;;                      (+ I 1)))))
;;   (LOOP 0 A))

Do and Do* should be efficient everywhere

However, tail calls aren't necessarily optimized away in Common Lisp, so this kind of recursion for iteration isn't all that common. The iterative analog is do:

(defun sum (a b)
  (do ((s 0 (+ s i))
       (i a (+ i 1)))
      ((> i b) s)))

Loop works too

You can use loop too, but it's a bit more verbose (but also probably more readable if you're familiar with do:

(defun sum (a b)
  (loop
     for s = 0 then (+ s i)
     for i = a then (+ i 1)
     when (> i b) return s))

Showily

thank you for your list of alternatives, I appreciate it an +1'd your answer. – Cootch