From: Jonathan H. <vo...@vo...> - 2002-05-13 09:39:08
|
SBCL doesn't seem to optimize tail-recursion. It seems like such an important optimization for lisps... is there a good reason why? CMUCL, in contrast, handles tail-recursion well. If there's not a good reason why SBCL shouldn't include it, perhaps I can begin helping the project by adding it :) -- Jonathan Hseu <vo...@vo..., vo...@de..., jh...@ce...> GPG ID: 5228D713 GPG fingerprint: 220B A4EF 70FE B884 CB38 F93F EA8A 1024 5228 D713 |
From: Christophe R. <cs...@ca...> - 2002-05-13 10:52:44
|
On Mon, May 13, 2002 at 04:36:12AM -0500, Jonathan Hseu wrote: > SBCL doesn't seem to optimize tail-recursion. It seems like such an > important optimization for lisps... is there a good reason why? > > CMUCL, in contrast, handles tail-recursion well. Starting with sbcl-0.7.2, there were two changes which cause what you're seeing: * incompatible change: The compiler is now less aggressive about tail call optimization, doing it only when (> SPACE DEBUG) or (> SPEED DEBUG). (This is an incompatible change because there are programs which relied on the old CMU-CL-style behavior to optimize away their unbounded recursion which will now die of stack overflow.) and ** The system now detects stack overflow and handles it gracefully, at least for (OR (> SAFETY (MAX SPEED SPACE)) (= SAFETY 3)) optimization settings. (This is a good thing in general, and its introduction in this version should be particularly timely for anyone whose code fails because of suppression of tail recursion!) So in other words, the support for tail-call elimination is still there; it happens to be suppressed in the default compilation mode, where all optimization policies are set to 1. Um. That's odd -- does that mean that stack overflow detection is suppressed by default? > If there's not a good reason why SBCL shouldn't include it, perhaps I > can begin helping the project by adding it :) Maybe better would be to put the above in the documentation somewhere :-) Cheers, Christophe -- Jesus College, Cambridge, CB5 8BL +44 1223 510 299 http://www-jcsu.jesus.cam.ac.uk/~csr21/ (defun pling-dollar (str schar arg) (first (last +))) (make-dispatch-macro-character #\! t) (set-dispatch-macro-character #\! #\$ #'pling-dollar) |
From: William H. N. <wil...@ai...> - 2002-05-13 22:35:17
|
On Mon, May 13, 2002 at 04:36:12AM -0500, Jonathan Hseu wrote: > SBCL doesn't seem to optimize tail-recursion. It seems like such an > important optimization for lisps... is there a good reason why? If I were on the ANSI CL committee 15 years ago, I'd be agitating for tail recursion support. But instead, it's not part of the standard, and so writing code which depends on it is arguably a bad idea. I'm one of the people who would argue that it is in fact a bad idea. I've been through numerous changes of computer and o/s in my checkered career. It's ever so nice to have code that just keeps on working no matter where it goes; and definitely nice enough that I prefer just to bite the bullet and write the code iteratively if the tail recursive code would go more than a few thousand levels deep. > CMUCL, in contrast, handles tail-recursion well. > > If there's not a good reason why SBCL shouldn't include it, perhaps I > can begin helping the project by adding it :) To the extent that tail recursion can be supported with no compromises of anything else, it's still good. But since in practice it tends to complicate other things (especially debugging), and since code which depends on it is unportable, I'm not very enthusiastic about it. To the extent that you want to work on tail recursion specifically, you might do better to write a portable package which provides it on top of stock common Lisp. (See Screamer for a package which ports another Schemely feature into CL, providing portable continuation-like functionality.) To the extent that you want to work on unportable extensions, I'd suggest something that increases the expressiveness of the language more than tail recursion does, e.g. weak pointers or multithreading. (Both of these seem as though they'd be unreasonably difficult to implement as a portable layer atop ANSI CL.) Or if you still really want to work on tail recursion specifically in SBCL, I'd suggest that early on you write up (or find, if perhaps someone has done this already) a description how it's to be done cleanly as an extension to Common Lisp. If you can put together something that's can become a good de facto standard, so that code using it has a decent chance of being de facto portable, I'll be more receptive to making the kinds of compromises on overall simplicity that will be required to support tail recursion. (Some stuff like this already exists for extensions like Grey streams and, if I understand correctly, multithreading as well; and weak pointers are sufficiently self-explanatory that they almost get a bye here.) -- William Harold Newman <wil...@ai...> "Palantir great. Better than cable." -- <http://home.nyu.edu/~amw243/diaries/saruman.html> PGP key fingerprint 85 CE 1C BA 79 8D 51 8C B9 25 FB EE E0 C3 E5 7C |
From: Marco A. <ma...@cs...> - 2002-05-14 13:50:03
|
> From: William Harold Newman <wil...@ai...> > Content-Disposition: inline > Sender: sbc...@li... > X-Original-Date: Mon, 13 May 2002 17:33:39 -0500 > Date: Mon, 13 May 2002 17:33:39 -0500 > X-Filter-Version: 1.8 (cat) > > On Mon, May 13, 2002 at 04:36:12AM -0500, Jonathan Hseu wrote: > > SBCL doesn't seem to optimize tail-recursion. It seems like such an > > important optimization for lisps... is there a good reason why? > > If I were on the ANSI CL committee 15 years ago, I'd be agitating for > tail recursion support. But instead, it's not part of the standard, > and so writing code which depends on it is arguably a bad idea. > > I'm one of the people who would argue that it is in fact a bad idea. > I've been through numerous changes of computer and o/s in my checkered > career. It's ever so nice to have code that just keeps on working no > matter where it goes; and definitely nice enough that I prefer just to > bite the bullet and write the code iteratively if the tail recursive > code would go more than a few thousand levels deep. > > > CMUCL, in contrast, handles tail-recursion well. > > > > If there's not a good reason why SBCL shouldn't include it, perhaps I > > can begin helping the project by adding it :) Well, you get lazy and happily confident that your quality CL implementation "DTRT". I have code written in a full tail recursive manner (it is Schemeish! :) ). It is a beauty to look at and easy to maintain. It works flawlessly under CMUCL for very large data sets (very "deep" graphs). I ported it to LW (and I did some preliminary tests on ACL), where it bombs (stack overflows) extremely easily. So now I have to rewrite a lot of code (that has worked for years under CMUCL) with an explicit heap allocated stack handling component. This is *not* nice. > > To the extent that tail recursion can be supported with no compromises > of anything else, it's still good. But since in practice it tends to > complicate other things (especially debugging), and since code which > depends on it is unportable, I'm not very enthusiastic about it. > > To the extent that you want to work on tail recursion specifically, > you might do better to write a portable package which provides it on > top of stock common Lisp. (See Screamer for a package which ports > another Schemely feature into CL, providing portable continuation-like > functionality.) From what you say here, it seems to me that you have departed quite a way from the CMUCL code base. I am not privy to the guts of SBCL, but I did not think that you had to go so far. It is you choice to dump full tail recursion. But in this case I think you are throwing the baby with the bathwater. > To the extent that you want to work on unportable extensions, I'd > suggest something that increases the expressiveness of the language > more than tail recursion does, e.g. weak pointers or multithreading. > (Both of these seem as though they'd be unreasonably difficult to > implement as a portable layer atop ANSI CL.) Why is CMUCL full tail recursion not portable? AFAIK, there is nothing in the standard that prevents it. Your suggestion that it should be implemented as a "portable layer" implies that it is something that should not be transparent to the user. IMO this is not the case. Cheers -- Marco Antoniotti ======================================================== NYU Courant Bioinformatics Group tel. +1 - 212 - 998 3488 719 Broadway 12th Floor fax +1 - 212 - 995 4122 New York, NY 10003, USA http://bioinformatics.cat.nyu.edu "Hello New York! We'll do what we can!" Bill Murray in `Ghostbusters'. |
From: Arthur L. <ale...@xs...> - 2002-05-14 17:26:51
|
Marco Antoniotti wrote: > I have code written in a full tail recursive manner (it is Schemeish! > :) ). It is a beauty to look at and easy to maintain. > > It works flawlessly under CMUCL for very large data sets (very "deep" > graphs). > > I ported it to LW (and I did some preliminary tests on ACL), where it > bombs (stack overflows) extremely easily. The Lispworks User Guide says that the compiler will 'eliminate tail recursion' when you use a DEBUG level of less than 3. I never tested this though. You could also try increasing the default stack size by setting the variable SYSTEM:*SG-DEFAULT-SIZE*. Arthur Lemmens |
From: Christophe R. <cs...@ca...> - 2002-05-14 14:12:49
|
On Tue, May 14, 2002 at 09:50:17AM -0400, Marco Antoniotti wrote: > Well, you get lazy and happily confident that your quality CL > implementation "DTRT". Why do you think that tail call optimization is the right thing in all circumstances? Surely you can enviseage a time when the ability to locate explicitly some offending code is more important? > I have code written in a full tail recursive manner (it is Schemeish! > :) ). It is a beauty to look at and easy to maintain. > > It works flawlessly under CMUCL for very large data sets (very "deep" > graphs). > > I ported it to LW (and I did some preliminary tests on ACL), where it > bombs (stack overflows) extremely easily. > > So now I have to rewrite a lot of code (that has worked for years under CMUCL) > with an explicit heap allocated stack handling component. This is > *not* nice. This is not true. You simply have to use the documented interface to controlling compiler optimization policy. From the NEWS file: changes in sbcl-0.7.2 relative to sbcl-0.7.1: * incompatible change: The compiler is now less aggressive about tail call optimization, doing it only when (> SPACE DEBUG) or (> SPEED DEBUG). (This is an incompatible change because there are programs which relied on the old CMU-CL-style behavior to optimize away their unbounded recursion which will now die of stack overflow.) So to get your tail call optimization back, you need to tell SBCL that you are more interested in SPACE than in DEBUGability, or that you are more interested in SPEED than in DEBUGability. You can do that with, for instance: (declaim (optimize (space 2) (debug 1))) to get this behaviour at file level, or (locally (declare (optimize (space 2) (debug 1))) ...) at block level. Note also that cmucl also doesn't elide tail calls for debug values greater than 2; it just so happens that cmucl's default debug optimization policy is not greater than 2. Hope that helps, Cheers, Christophe -- Jesus College, Cambridge, CB5 8BL +44 1223 510 299 http://www-jcsu.jesus.cam.ac.uk/~csr21/ (defun pling-dollar (str schar arg) (first (last +))) (make-dispatch-macro-character #\! t) (set-dispatch-macro-character #\! #\$ #'pling-dollar) |
From: Marco A. <ma...@cs...> - 2002-05-14 15:46:31
|
> Date: Tue, 14 May 2002 15:12:18 +0100 > Cc: sbc...@li... > Content-Disposition: inline > From: Christophe Rhodes <cs...@ca...> > X-Filter-Version: 1.8 (cat) > > On Tue, May 14, 2002 at 09:50:17AM -0400, Marco Antoniotti wrote: > > Well, you get lazy and happily confident that your quality CL > > implementation "DTRT". > > Why do you think that tail call optimization is the right thing in all > circumstances? Surely you can enviseage a time when the ability to > locate explicitly some offending code is more important? I think it is important. However, I think that having t-c-e by default is nicer. I regard debugging inherently less portable, hence I expect to do different things in different implementations when debugging. In some ways you do answer me later on. > > I have code written in a full tail recursive manner (it is Schemeish! > > :) ). It is a beauty to look at and easy to maintain. > > > > It works flawlessly under CMUCL for very large data sets (very "deep" > > graphs). > > > > I ported it to LW (and I did some preliminary tests on ACL), where it > > bombs (stack overflows) extremely easily. > > > > So now I have to rewrite a lot of code (that has worked for years under CMUCL) > > with an explicit heap allocated stack handling component. This is > > *not* nice. > > This is not true. > > You simply have to use the documented interface to controlling compiler > optimization policy. From the NEWS file: > > changes in sbcl-0.7.2 relative to sbcl-0.7.1: > * incompatible change: The compiler is now less aggressive about > tail call optimization, doing it only when (> SPACE DEBUG) or > (> SPEED DEBUG). (This is an incompatible change because there are > programs which relied on the old CMU-CL-style behavior to optimize > away their unbounded recursion which will now die of stack overflow.) > > So to get your tail call optimization back, you need to tell SBCL that > you are more interested in SPACE than in DEBUGability, or that you are > more interested in SPEED than in DEBUGability. You can do that with, for > instance: > > (declaim (optimize (space 2) (debug 1))) > > to get this behaviour at file level, or > > (locally > (declare (optimize (space 2) (debug 1))) > ...) > > at block level. > > Note also that cmucl also doesn't elide tail calls for debug values > greater than 2; it just so happens that cmucl's default debug > optimization policy is not greater than 2. > > Hope that helps, Yes, it does. Thanks. I must have misunderstood what William said. I interpreted it as a way of saying that SBCL would not support t-c-e in the future. Cheers -- Marco Antoniotti ======================================================== NYU Courant Bioinformatics Group tel. +1 - 212 - 998 3488 719 Broadway 12th Floor fax +1 - 212 - 995 4122 New York, NY 10003, USA http://bioinformatics.cat.nyu.edu "Hello New York! We'll do what we can!" Bill Murray in `Ghostbusters'. |
From: William H. N. <wil...@ai...> - 2002-05-14 17:03:17
|
On Tue, May 14, 2002 at 11:46:46AM -0400, Marco Antoniotti wrote: > I must have misunderstood what William said. I interpreted it as a way > of saying that SBCL would not support t-c-e in the future. Alas, I think it was fairly reasonable to interpret what I wrote that way. Sorry, I wasn't writing or thinking particularly clearly. I'm not planning to get rid of tail call optimization. If nothing else, it's a useful optimization in ordinary code, in the same way that it's useful to optimize away code whose value is never used, or to collapse constant lists with identical contents into the same physical CONS. But I do think you shouldn't rely on t.c.e., any more than you rely on unused code being optimized away or constant lists being collapsed to the same physical CONS. (For any of these optimizations, I think I can construct code which works with them but fails without them, and in all cases I think it's unwise.) -- William Harold Newman <wil...@ai...> "Palantir great. Better than cable." -- <http://home.nyu.edu/~amw243/diaries/saruman.html> PGP key fingerprint 85 CE 1C BA 79 8D 51 8C B9 25 FB EE E0 C3 E5 7C |
From: Pierre R\. M. <pm...@pm...> - 2002-05-15 02:11:34
|
Christophe Rhodes <cs...@ca...> writes: > So to get your tail call optimization back, you need to tell SBCL that > you are more interested in SPACE than in DEBUGability, or that you are > more interested in SPEED than in DEBUGability. You can do that with, for > instance: > > (declaim (optimize (space 2) (debug 1))) > > to get this behaviour at file level, or > > (locally > (declare (optimize (space 2) (debug 1))) > ...) > > at block level. > > Note also that cmucl also doesn't elide tail calls for debug values > greater than 2; it just so happens that cmucl's default debug > optimization policy is not greater than 2. FWIW, when we added the option of disabling TCE (people where screaming and jumping up and down that that was very important for debugability, and CMUCL until 18d didn't have a way of turning TCE off!), people actually wanted the default to be disabled TCE (something that I have great sympathy for, and think is the right thing, for SBCL). Since I'm such a dull stickler for stability, and not changing documented (see CMUCL user-manual on TCE) behaviour, I was adamant that the default behaviour should not change. I prevailed (so Marco can thank me now ;), which is why TCE is only disabled for debug > 2 (debug = 2 is the default in CMUCL). [ The test is debug > 2 and not debug = 3, because other people screamed that they wanted disabled TCE, but not the heavy-duty stuff that debug = 3 entails ] So why am I posting this? a) It didn't just so happen, but took quite a bit of effort ;) b) It illustrates quite nicely that depending on TCE being done is quite dangerous, even when only porting between releases of a fairly conservative implementation, that actually documented when it does TCE. c) It also illustrates why I personally think that having both SBCL and CMUCL alive and kicking is the best thing since sliced bread, even if it entails a bit more work overall. The existence of SBCL makes it easier for CMUCL maintainers to be conservative, without thwarting the development of the CMU/SBCL code base, and the existence of CMUCL allows SBCL maintainers to be more progressive, without alienating all those conservative users. At least that's the theory, which practice tends to screw up on occasion... Regs, Pierre. -- Pierre R. Mai <pm...@pm...> http://www.pmsf.de/pmai/ The most likely way for the world to be destroyed, most experts agree, is by accident. That's where we come in; we're computer professionals. We cause accidents. -- Nathaniel Borenstein |
From: Marco A. <ma...@cs...> - 2002-05-15 13:49:24
|
> X-Authentication-Warning: dent.bln.pmsf.de: Host no...@or... [192.168.42.10] claimed to be orion > Sender: de...@pm... > Cc: Marco Antoniotti <ma...@cs...>, sbc...@li... > From: "Pierre R\. Mai" <pm...@pm...> > Date: 15 May 2002 02:58:05 +0200 > X-Sender: 320...@t-... > X-Filter-Version: 1.8 (cat) > ... > > FWIW, when we added the option of disabling TCE (people where > screaming and jumping up and down that that was very important for > debugability, and CMUCL until 18d didn't have a way of turning TCE > off!), people actually wanted the default to be disabled TCE > (something that I have great sympathy for, and think is the right > thing, for SBCL). Since I'm such a dull stickler for stability, and > not changing documented (see CMUCL user-manual on TCE) behaviour, I > was adamant that the default behaviour should not change. I prevailed > (so Marco can thank me now ;), Thanks :) > which is why TCE is only disabled for > debug > 2 (debug = 2 is the default in CMUCL). ... > b) It illustrates quite nicely that depending on TCE being done is > quite dangerous, even when only porting between releases of a > fairly conservative implementation, that actually documented when > it does TCE. Yep. In some sense I was naive and didn't RTFM of LW. Somehow I just expected that a commercial implementation should be as good as CMUCL. Then I coincidentally read William's note here... you know the rest. ... Cheers -- Marco Antoniotti ======================================================== NYU Courant Bioinformatics Group tel. +1 - 212 - 998 3488 719 Broadway 12th Floor fax +1 - 212 - 995 4122 New York, NY 10003, USA http://bioinformatics.cat.nyu.edu "Hello New York! We'll do what we can!" Bill Murray in `Ghostbusters'. |