[Armedbear-devel] Tail recursion
Hi all, ABCL does not seem to support tail call optimization right now. Are there any plans to provide this? Best regards, Ralf Moeller _______________________________________________ Armedbear-devel mailing list Armedbear-devel@common-lisp.net http://common-lisp.net/cgi-bin/mailman/listinfo/armedbear-devel
Hi Ralf, On Tue, Apr 1, 2014 at 3:52 PM, Ralf Moeller <moeller@tu-harburg.de> wrote:
Hi all,
ABCL does not seem to support tail call optimization right now.
That's right. Basically we've inherited that "property" from the JVM: The Java language disallows tail call optimization in the JVM because it interferes with security options which walk the stack to determine access rights of callers.
Are there any plans to provide this?
Not at this point, however, I know that there have been work-arounds for JVM based Scheme implementations, because it's part of the Scheme language to require TCO; I don't know about the performance consequences, though. If you want to write portable CL though, you can't depend on TCO: it's not part of the language definition that the underlying runtime/compiler should support it. If anybody has some insights on how to implement TCO efficiently, I don't see why we would not want to accept code to implement it and support it -- at this time I don't have any plans to implement it personally, though. Bye, Erik. -- http://efficito.com -- Hosted accounting and ERP. Robust and Flexible. No vendor lock-in. _______________________________________________ Armedbear-devel mailing list Armedbear-devel@common-lisp.net http://common-lisp.net/cgi-bin/mailman/listinfo/armedbear-devel
One idea I have is to use deftro (described below) instead of defun for tail recursive functions. On TCO Lisps define deftro to just be defun. On others define it to rewrite the body. It won't optimise all tail calls, just those are self-recursive. http://www.wispym.com/notes/tech/lisp/tco.txt I haven't used this myself. But I might start, because it's not ugly in the following sense. Writing a tail recursive function and depending implicitly on TCO is non-portable. deftro is a portability layer. _______________________________________________ Armedbear-devel mailing list Armedbear-devel@common-lisp.net http://mailman.common-lisp.net/cgi-bin/mailman/listinfo/armedbear-devel
Hi Vibhu, Thanks for sharing your thoughts. Indeed, rewriting function bodies in the case of tail recursion is an option. However, do we know which percentage of TCO calls can be optimized by using deftro? So far, I have not spent any energy on TCO because my idea is that the benefit is just too small -- in other words, I expect that the number of cases that would benefit from TCO without getting optimization is just too big... Do you have any idea/ numbers? Regards, Erik. On Thu, Nov 20, 2014 at 8:54 PM, Vibhu Mohindra <vibhu.mohindra@gmail.com> wrote:
One idea I have is to use deftro (described below) instead of defun for tail recursive functions. On TCO Lisps define deftro to just be defun. On others define it to rewrite the body. It won't optimise all tail calls, just those are self-recursive.
http://www.wispym.com/notes/tech/lisp/tco.txt
I haven't used this myself. But I might start, because it's not ugly in the following sense. Writing a tail recursive function and depending implicitly on TCO is non-portable. deftro is a portability layer.
_______________________________________________ Armedbear-devel mailing list Armedbear-devel@common-lisp.net http://mailman.common-lisp.net/cgi-bin/mailman/listinfo/armedbear-devel
-- Bye, Erik. http://efficito.com -- Hosted accounting and ERP. Robust and Flexible. No vendor lock-in. _______________________________________________ Armedbear-devel mailing list Armedbear-devel@common-lisp.net http://mailman.common-lisp.net/cgi-bin/mailman/listinfo/armedbear-devel
Hi Erik, No, no idea or numbers about the fraction that would benefit. The "optimisation" in TCO is different from its traditional sense, which is usually "just" to provide a constant factor improvement in speed/memory. TCO by contrast, allows or doesn't allow a programmer to use a certain programming technique: recursion. I use recursion a lot, and when I moved to ABCL, I found that a lot of code broke on lists as short as a few thousand elements. So I'm not referring so much to ABCL or its implementation as to a Lisp program. A portable Lisp programmer can't rely on TCO being available. So using defun/tro [1] lets them remain portable across Lisps. It's probably not too hard to also optimise mutual recursion (f->g->f) in a labels clause using a similar macro to defun/tro. When I say I'm not referring specifically to ABCL, it means that if ABCL implemented TCO, everything I wrote would just move over to another (present or future) non-TCO ANSI Common Lisp's discussion forum when someone enquired about it :-) . Sorry about the delay. I haven't yet mastered this newsgroup's (mailing-list's?) interface, and thought my last message hadn't even gone through. [1]: was deftro Vibhu _______________________________________________ Armedbear-devel mailing list Armedbear-devel@common-lisp.net http://mailman.common-lisp.net/cgi-bin/mailman/listinfo/armedbear-devel
Am 20.11.2014 um 20:54 schrieb Vibhu Mohindra:
One idea I have is to use deftro (described below) instead of defun for tail recursive functions. On TCO Lisps define deftro to just be defun. On others define it to rewrite the body. It won't optimise all tail calls, just those are self-recursive.
http://www.wispym.com/notes/tech/lisp/tco.txt
I haven't used this myself. But I might start, because it's not ugly in the following sense. Writing a tail recursive function and depending implicitly on TCO is non-portable. deftro is a portability layer.
How about something like scheme's named let, or clojure's loop? Furthermore, I wonder whether it is possible to do something similar to chicken scheme, and let the stack overflow, but then handle the overflow accordingly.
_______________________________________________ Armedbear-devel mailing list Armedbear-devel@common-lisp.net http://mailman.common-lisp.net/cgi-bin/mailman/listinfo/armedbear-devel
_______________________________________________ Armedbear-devel mailing list Armedbear-devel@common-lisp.net http://mailman.common-lisp.net/cgi-bin/mailman/listinfo/armedbear-devel
participants (4)
-
Christoph-Simon Senjak -
Erik Huelsmann -
Ralf Moeller -
Vibhu Mohindra