Re: tail recursion

[kanderso@DINO.BBN.COM]

  Date: Tue, 27 Feb 90 11:25:29 CST
  From: Larry Smith <lsmith@cli.com>
  To: slug@warbucks.ai.sri.com
  Subject: tail recursion
  
  
  A function like the following keeps blowing the control stack. 
  
  (defun doit-list (list collector)
    (if (atom list) collector
        (doit-list (cdr list)
                   (cons (doit (car list))
                         collector))))
  
  Is there a way to tell the lispm compiler that it's OK to turn the
  tail recursion into iteration? [Let's assume I don't want to recode it
  into a LOOP or MAPCAR or anything else.]
  
  Ah. I have just found a mention of compiler:add-optimizer in Volume 4,
  page 135 of the genera 7.2 manual. I can do what I
  need with this, painfully. The following turns 
  (doit-list x nil) into a LOOP.
  
  (compiler:add-optimizer doit-list turn-doit-list-into-loop)
  (defun turn-doit-list-into-loop (form)
     ;; form is a call to doit-list.
     (let ((arg1 (cadr form))
           (arg2 (caddr form)))
       (if (null arg2) `(loop for xyzzy in ,arg1 collect (doit xyzzy))
           form)))
  
  I realize there are at least three bugs in that transformation. That's
  one reason why I'd rather not use this feature if there's a more
  reasonable way. Another is that I write a lot of functions similar to
  doit-list, and don't want to recode the optimizer every time.
  
Unfortunately, the current compiler does not do tail recursion.  Many
people wish it did, but i seems harder than it looks.

You could try using a macro like this to generate loops for you:

(defmacro deftail (name args &body body)
  `(defun ,name ,args
     (macrolet
       ((tail-call ((call-name &rest call-args))
	  (if (not (eq call-name ',name))
	      (error "can only tail-call ~a" ',name)
	  `(progn
	     ,@(map 'list #'(lambda (a v) `(setq ,a ,v)) ',args call-args)
	     (go :start)))))
       (prog ()
	 :start
	 (return (progn ,@body))))))

So your example would look like:

  (deftail doit-list (list collector)
    (if (atom list) collector
        (tail-call (doit-list (cdr list)
                              (cons (doit (car list))
                                     collector)))))


Using TAIL-CALL lets you separate out tail recursive calls to
DOIT-LIST from those that aren't.  Though i guess you could flag
norecursive calls instead, which might be more natural.

k