tail recursion hack in Emacs Lisp?

tail recursion hack in Emacs Lisp?

[Oliver Scholz]

I like tail recursion a lot, because I regard it as a means to specify
the flow of control that is IMO the right way for /some/ problems.
Thus tail call reduction is on the top of my personal wish list for
enhancements of Emacs Lisp---even before closures and greater speed.

I have been wondering for a while, whether it would be possible to
fake tail recursion without hacking the byte code compiler.  Say, if
we have an `iterate' macro like in CMU CL (which in turn is inspired
by Scheme's named let): would it be possible that the macroexpanded
code would be non-recursive Emacs Lisp code?

Today I got bored in my lunch break and came up with this.

(iterate fact ((n n)
	       (r 1))
  (if (= n 1)
      r
    (fact (1- n) (* n r))))

should expand to:

(let ((continue t)
      (result (list n 1)))
  (while continue
    (setq result
	  (catch 'repeat
	    (setq result
		  (apply
		   (lambda (n r)
		     (if (= n 1)
			 r
		       (throw 'repeat (list (1- n) (* n r)))))
		   result))
	    (setq continue nil)
	    result)))
  result)


(Of course, a code walker would be necessary.) I can't see any
problems with that approach right know. But lacking experience in
implementing Lisp, I might be missing something.

So my question is: Can anybody think of a case where this approach
would break?

While I am at it: I quickly hacked something together:

(defmacro iterate (name arglist &rest body)
  (let ((catch-symbol (make-symbol "--repeat"))
	(continue (make-symbol "--continue"))
	(result (make-symbol "--result"))
	(lambda-list (mapcar 'car arglist))
	(initial-args (mapcar 'cadr arglist)))
    (setq body (iterate-code-walk body name catch-symbol))
    `(let ((,continue t)
	   (,result (list ,@initial-args)))
       (while ,continue
	 (setq ,result
	       (catch ',catch-symbol
		 (setq ,result
		       (apply
			(lambda ,lambda-list
			  ,@body)
			,result))
		 (setq ,continue nil)
		 ,result)))
       ,result)))

(defun iterate-code-walk (exp sym catch-sym)
  (cond ((and (listp exp)
	      (eq (car exp) 'quote))
	 exp)
	((and (listp exp)
	      (eq (car exp) sym))
	 (list 'throw `(quote ,catch-sym)
	       (cons 'list (cdr exp))))
	((listp exp)
	 (iterate-code-walk-list exp sym catch-sym))
	(t exp)))

(defun iterate-code-walk-list (exp sym catch-sym)
  (mapcar (lambda (el)
	    (iterate-code-walk el sym catch-sym))
	  exp))       


    Oliver
-- 
29 Messidor an 212 de la Révolution
Liberté, Egalité, Fraternité!

Re: tail recursion hack in Emacs Lisp?

[Oliver Scholz]

Oliver Scholz <alkibiades@gmx.de> writes:

[`iterate' macro with code-walker]
>
> So my question is: Can anybody think of a case where this approach
> would break?

Silly me. The usual case for breaking such things would apply:

(iterate fact ((n 10)
	       (r 1))
  (if (= n 1)
      r
    (funcall (intern "fact") (1- n) (* n r))))

Not to mention `eval'.

:-(  :-(  :-(


    Oliver
-- 
29 Messidor an 212 de la Révolution
Liberté, Egalité, Fraternité!

Re: tail recursion hack in Emacs Lisp?

[Oliver Scholz]

[Sorry for talking to myself today.]

Oliver Scholz <alkibiades@gmx.de> writes:

> Oliver Scholz <alkibiades@gmx.de> writes:
>
> [`iterate' macro with code-walker]
>>
>> So my question is: Can anybody think of a case where this approach
>> would break?
>
> Silly me. The usual case for breaking such things would apply:
>
> (iterate fact ((n 10)
> 	       (r 1))
>   (if (= n 1)
>       r
>     (funcall (intern "fact") (1- n) (* n r))))
>
> Not to mention `eval'.

And of course that could be circumwented by `fset'ing NAME:

(defmacro iterate (name arglist &rest body)
  (let ((catch-symbol (make-symbol "--repeat"))
	(continue (make-symbol "--continue"))
	(result (make-symbol "--result"))
	(fdef (make-symbol "--fdef"))
	(lambda-list (mapcar 'car arglist))
	(initial-args (mapcar 'cadr arglist)))
    `(let ((,fdef (and (fboundp ',name)
			   (symbol-function ',name))))
       (unwind-protect
	   (let ((,continue t)
		 (,result (list ,@initial-args)))
	     (fset ',name (lambda (&rest args)
			    (throw ',catch-symbol args)))
	     (while ,continue
	       (setq ,result
		     (catch ',catch-symbol
		       (setq ,result
			     (apply
			      (lambda ,lambda-list
				,@body)
			      ,result))
		       (setq ,continue nil)
		       ,result)))
	     ,result)
	 (if (null ,fdef)
	     (fmakunbound ',name)
	   (fset ',name ,fdef))))))


Yet, I dislike it more and more.


    Oliver
-- 
29 Messidor an 212 de la Révolution
Liberté, Egalité, Fraternité!

Re: tail recursion hack in Emacs Lisp?

[Stefan Monnier]

> So my question is: Can anybody think of a case where this approach
> would break?

I have another question: why is it better than CL's `do' ?


        Stefan

Re: tail recursion hack in Emacs Lisp?

[Oliver Scholz]

Stefan Monnier <monnier@iro.umontreal.ca> writes:

>> So my question is: Can anybody think of a case where this approach
>> would break?
>
> I have another question: why is it better than CL's `do' ?

Huh?  You mean like:

(do ((n 10 (1- n))
     (r 1 (* n r)))
    ((= n 1) r))

I had no intention to suggest that it were better. iterate/named
let is just different. Personally I find `do' hard to read, but
that might be a matter of taste.

I used `fact' just because it is the classical example. I can't
think of a really good example right now, exept maybe this:

(defun my-flatten-list (lst)
  (iterate walk-list ((lst lst)
		      (acc nil)
		      (stk nil))
    (if (null lst)
	(if (null stk)
	    (nreverse acc)
	  (walk-list stk acc nil))
      (if (listp (car lst))
	  (walk-list (car lst)
		     acc
		     (if (null (cdr lst))
			 stk
		       (cons (cdr lst)
			     stk)))
	(walk-list (cdr lst)
		   (cons (car lst) acc)
		   stk)))))

There might be better examples. To quote the CMU CL manual: "The
main advantage of using iterate over do is that iterate naturally
allows stepping to be done differently depending on conditionals
in the body of the loop."

    Oliver
-- 
29 Messidor an 212 de la Révolution
Liberté, Egalité, Fraternité!