From: John Thingstad
Subject: Was not making tail recursion elmination a mistake?
Date:
Message-ID: <opr9fvortjpqzri1@mjolner.upc.no>
I have recently been annoyeed by the fact that tail recursion elimination
is
not part of the standard. Any ansi compliant program can now not rely on
recurive tail
elimination and must use loops or some simular structue. For mutual
recurion things get even uglier.
Wouldn't it have been better to make a commentary on the implementation
and require it?
Most implementations do anyhow.
What is the historic reason for this omission?
--
Using M2, Opera's revolutionary e-mail client: http://www.opera.com/m2/
In article <················@mjolner.upc.no>,
"John Thingstad" <··············@chello.no> wrote:
> I have recently been annoyeed by the fact that tail recursion elimination
> is
> not part of the standard. Any ansi compliant program can now not rely on
> recurive tail
> elimination and must use loops or some simular structue. For mutual
> recurion things get even uglier.
> Wouldn't it have been better to make a commentary on the implementation
> and require it?
> Most implementations do anyhow.
> What is the historic reason for this omission?
I think it's because most of the programmers who designed Common Lisp
were used to dialects that didn't have tail-call elimination. So they
were comfortable with using looping constructs like DO, LOOP, and
MAPxxx. Scheme's use of recursion to implement looping was viewed as a
nice pedagogical feature, but not something needed for everyday
programming.
Although some algorithms are naturally recursive, they don't tend to get
so deep that they exhaust the stack -- almost all stack overflows are
due to infinite recursion bugs. And many recursive algorithms aren't
naturally tail-recursive -- it's often necessary to contort the code to
turn a recursive implementation into a tail-recursive one; e.g.:
(defun fact (n)
(if (< n 2)
1
(* n (fact (1- n))))
(defun tail-recursive-fact (n &optional (accumulator 1))
(if (< n 2)
accumulator
(tail-recursive-fact (1- n) (* n accumulator))))
This particular example may not be very compelling, but it's one of the
simplest recursive functions there is.
--
Barry Margolin, ······@alum.mit.edu
Arlington, MA
*** PLEASE post questions in newsgroups, not directly to me ***
From: Dominique Boucher
Subject: Re: Was not making tail recursion elmination a mistake?
Date:
Message-ID: <81u0xht1dq.fsf@sympatico.ca>
Barry Margolin <······@alum.mit.edu> writes:
> I think it's because most of the programmers who designed Common Lisp
> were used to dialects that didn't have tail-call elimination. So they
> were comfortable with using looping constructs like DO, LOOP, and
> MAPxxx. Scheme's use of recursion to implement looping was viewed as a
> nice pedagogical feature, but not something needed for everyday
> programming.
>
> Although some algorithms are naturally recursive, they don't tend to get
> so deep that they exhaust the stack -- almost all stack overflows are
> due to infinite recursion bugs. And many recursive algorithms aren't
> naturally tail-recursive -- it's often necessary to contort the code to
> turn a recursive implementation into a tail-recursive one; e.g.:
But what if your algorithm is best expressed using
continuation-passing style (CPS)? In CPS, most calls are tail calls
and you never really return from your functions. I once wrote a
grammar parsing/phrase generation algorithm this way. Without
tail-call elimination, it exhausted the stack even on small samples.
Also, the code fit on one page and was pretty elegant, which would not
have been the case if I had to implement my own search stack.
Dominique Boucher
John Thingstad wrote:
> I have recently been annoyeed by the fact that tail recursion
> elimination is
> not part of the standard. Any ansi compliant program can now not rely
> on recurive tail
> elimination and must use loops or some simular structue. For mutual
> recurion things get even uglier.
> Wouldn't it have been better to make a commentary on the implementation
> and require it?
> Most implementations do anyhow.
> What is the historic reason for this omission?
There are situations in which it is better not to eliminate tail
recursions (better debuggability, more restart options), so it would
have been an optional feature. The ANSI standard generally doesn't cover
optional features (or so it seems to me).
I think 1.6 and 1.7 of the HyperSpec are relevant here.
Pascal
--
1st European Lisp and Scheme Workshop
June 13 - Oslo, Norway - co-located with ECOOP 2004
http://www.cs.uni-bonn.de/~costanza/lisp-ecoop/
From: Svein Ove Aas
Subject: Re: Was not making tail recursion elmination a mistake?
Date:
Message-ID: <cacvrb$ltd$1@services.kq.no>
Pascal Costanza wrote:
>
> John Thingstad wrote:
>
>> I have recently been annoyeed by the fact that tail recursion
>> elimination is
>> not part of the standard. Any ansi compliant program can now not rely
>> on recurive tail
>> elimination and must use loops or some simular structue. For mutual
>> recurion things get even uglier.
>> Wouldn't it have been better to make a commentary on the implementation
>> and require it?
>> Most implementations do anyhow.
>> What is the historic reason for this omission?
>
> There are situations in which it is better not to eliminate tail
> recursions (better debuggability, more restart options), so it would
> have been an optional feature. The ANSI standard generally doesn't cover
> optional features (or so it seems to me).
>
It seems to me that you could make it an obligatory feature that has an
option to be turned off by the programmer.
Tail-call elimination isn't exactly hard to do, is it?
Svein Ove Aas wrote:
> It seems to me that you could make it an obligatory feature that has an
> option to be turned off by the programmer.
>
> Tail-call elimination isn't exactly hard to do, is it?
This depends on how far you want to go in this regard. Google for
"proper tail recursion", there was a discussion here some time ago about it.
Pascal
--
1st European Lisp and Scheme Workshop
June 13 - Oslo, Norway - co-located with ECOOP 2004
http://www.cs.uni-bonn.de/~costanza/lisp-ecoop/
Svein Ove Aas <··············@brage.info> wrote:
+---------------
| Pascal Costanza wrote:
| > John Thingstad wrote:
| >> I have recently been annoyeed by the fact that tail recursion
| >> elimination is not part of the standard. ...
| >> What is the historic reason for this omission?
| >
| > There are situations in which it is better not to eliminate tail
| > recursions (better debuggability, more restart options), so it would
| > have been an optional feature. The ANSI standard generally doesn't cover
| > optional features (or so it seems to me).
|
| It seems to me that you could make it an obligatory feature that has an
| option to be turned off by the programmer.
| Tail-call elimination isn't exactly hard to do, is it?
+---------------
When you *can* do it, no. But compared to Scheme, in CL it's a lot harder
to specify exactly when you can and can't do it -- and there are a *lot*
more places in CL where you *can't* than in Scheme.
Take a look at R5RS Scheme's section "3.5 Proper tail recursion", and
look at how very particular they had to be to define "tail calls", "active
tail calls" and "tail contexts", especially the recursive/inductive
definition of the latter. You basically need a full code-walker to
decide whether a given form is is is not a tail call (or in a tail
context).
Now consider writing the same section for Common Lisp, being sure
to "do the right thing" with regard to dynamically-bound variables,
UNWIND-PROTECT contexts (and other exception contexts, both HANDLER-
CASE-style *and* HANDLER-BIND-style), ill-specified things such as
TRACE, and non-standard but universally-desired things such as ADVISE
and threads.[1] Be sure that your document specifies "the right thing"
in all of these cases, *and* that the Common Lisp community *agrees*
that it's "the right thing" in each case.
Isn't exactly easy to do, is it?
-Rob
[1] Oh, and FFIs: Is a tail call to a foreign function that then
makes what looks like a tail call back into Lisp that then makes
a tail call *really* a "tail call"? Or is there junk on the stack
waiting to blow your never-terminating state-machine-implememnted-
as-tail-calls out of the water, hmmm?
List the answer for each of the possible FFI suites anybody might
want to use, with each Common Lisp implememntation anybody might
ever want to use.
-----
Rob Warnock <····@rpw3.org>
627 26th Avenue <URL:http://rpw3.org/>
San Mateo, CA 94403 (650)572-2607
"Rob Warnock" <····@rpw3.org> wrote in message
···························@speakeasy.net...
> You basically need a full code-walker to
> decide whether a given form is is is not a tail call
Well this really depends apon what the meanings of the words "is" are!
--
Coby Beck
(remove #\Space "coby 101 @ big pond . com")
Coby Beck <·····@mercury.bc.ca> wrote:
+---------------
| "Rob Warnock" <····@rpw3.org> wrote in message
| > You basically need a full code-walker to
| > decide whether a given form is is is not a tail call
|
| Well this really depends apon what the meanings of the words "is" are!
+---------------
(*sigh*) My bad. It's *way* too easy to typo when editing across
high-latency links.[1] What I meant, of course, was:
You basically need a full code-walker to
decide whether a given form is or is not a tail call
**
-Rob
[1] AT&T Wireless's GSM/GPRS/EDGE cellular data service, which,
while it has pretty good bandwidth [3-7 times dialup modem],
has *terrible* round-trip latency:
PING google.com (216.239.37.99): 56 data bytes
64 bytes from 216.239.37.99: icmp_seq=0 ttl=53 time=1145.788 ms
64 bytes from 216.239.37.99: icmp_seq=1 ttl=53 time=860.237 ms
64 bytes from 216.239.37.99: icmp_seq=2 ttl=53 time=570.285 ms
64 bytes from 216.239.37.99: icmp_seq=3 ttl=53 time=540.267 ms
64 bytes from 216.239.37.99: icmp_seq=4 ttl=53 time=670.334 ms
...
-----
Rob Warnock <····@rpw3.org>
627 26th Avenue <URL:http://rpw3.org/>
San Mateo, CA 94403 (650)572-2607
From: Svein Ove Aas
Subject: Re: Was not making tail recursion elmination a mistake?
Date:
Message-ID: <cak01j$jmj$1@services.kq.no>
Rob Warnock wrote:
> [1] AT&T Wireless's GSM/GPRS/EDGE cellular data service, which,
> while it has pretty good bandwidth [3-7 times dialup modem],
> has *terrible* round-trip latency:
>
> [high latency ping]
Hang on, isn't that the same link you use to talk with?
Where's the latency, then?
I'd be most interested in a traceroute.
[This is *way* off-topic, but since he asked...]
Svein Ove Aas <··············@brage.info> wrote:
+---------------
| Rob Warnock wrote:
| > [1] AT&T Wireless's GSM/GPRS/EDGE cellular data service, which,
| > while it has pretty good bandwidth [3-7 times dialup modem],
| > has *terrible* round-trip latency:
| > [high latency ping]
|
| Hang on, isn't that the same link you use to talk with?
+---------------
Yes. But voice calls pay the call-setup delay [see below] only once
per call, then they are billed continuously for the minutes that the
call stays connected.
+---------------
| Where's the latency, then?
| I'd be most interested in a traceroute.
+---------------
Almost all of the latency is between the cellular modem and the first
"service processor" [which is still behind the NAT gateway, before the
data even gets to the Internet]. It appears that, being a "best-efforts"
service, data is carried on an "as-available" basis, which in practice
seems to mean that they're using "fast circuit-switching" -- that is,
a circuit-switched call from the modem to the first IP service processor
is set up and torn down for *each* burst of IP packets. That means that
once-a-second things like "ping" (ICMP ECHO_REQUEST) and "traceroute"
(UDP to a random port) suffer a full call-setup delay per packet.
Traceroute from the cellular modem side [first few only]:
traceroute to fast.rpw3.org (66.93.131.53), 64 hops max, 44 byte packets
1 10.251.1.26 (10.251.1.26) 974.123 ms 609.204 ms 629.911 ms
2 10.251.0.1 (10.251.0.1) 599.648 ms 609.683 ms 629.716 ms
3 10.250.1.2 (10.250.1.2) 619.403 ms 609.467 ms 629.447 ms
4 allntxgdmzrt01-f4-0-0.network.attwireless.net (209.183.48.2) 599.935 ms 618.991 ms 599.909 ms
5 allntxgisprt01-f1-1-0.network.attwireless.net (172.16.1.102) 599.503 ms 769.224 ms 639.480 ms
6 allntxgisprt02-f4-1-0.network.attwireless.net (172.16.1.226) 409.877 ms 619.285 ms 599.623 ms
7 se-2-0-1.hsa1.Dallas1.Level3.net (209.245.240.21) 499.499 ms 619.134 ms 599.913 ms
...
Ping from the other side (my server) back to the host listed in #7 above:
PING se-2-0-1.hsa1.Dallas1.Level3.net (209.245.240.21): 56 data bytes
64 bytes from 209.245.240.21: icmp_seq=0 ttl=250 time=54.419 ms
64 bytes from 209.245.240.21: icmp_seq=1 ttl=250 time=52.418 ms
64 bytes from 209.245.240.21: icmp_seq=2 ttl=250 time=53.107 ms
...
As I said, almost *all* of the delay is between the cellular modem
and the first ATTWS-internal IP service processor...
-Rob
-----
Rob Warnock <····@rpw3.org>
627 26th Avenue <URL:http://rpw3.org/>
San Mateo, CA 94403 (650)572-2607
Svein Ove Aas <··············@brage.info> writes:
> Rob Warnock wrote:
>
>> [1] AT&T Wireless's GSM/GPRS/EDGE cellular data service, which,
>> while it has pretty good bandwidth [3-7 times dialup modem],
>> has *terrible* round-trip latency:
>>
>> [high latency ping]
>
> Hang on, isn't that the same link you use to talk with?
Kinda. GPRS is packet-based and does some funky signalling to get the
use of the voice radio channels when it needs to send packets.
Some particularly funky things about GPRS:
Any time you want to send data you must negotiate for use of the
"uplink". This takes several hundred milliseconds and is where the
observable fixed delay comes from. Aside from this the link is
actually low-latency: you can see this if you try pinging at
intervals of (say) 50ms. The first ping asks for the uplink, and
then they keep getting queued while it's established and then sent
in a batch, after which the uplink is immediately released. Earlier
pings will spend more time queued waiting for the link and thus
report longer round-trips.
Unfortunately most types of traffic hit these bad cases in the
uplink: you lose a lot of speed on small TCP transfers due to
delayed ACKs during "slow start", and when typing into telnet/ssh
most of your keystrokes get delayed.
The link-layer transparently does retransmission to prevent packet
loss. If the radio is bad you're supposed to see delay (while it
tries resends) rather than loss of packets. This is a "damned if you
do, damned if you don't" situation: packet loss would make TCP think
the network is congested and sharply slow down, but variance in
delay pushes the retransmission timers up way too high
(e.g. minutes). Since you're still going to be losing packets out on
the internet it's really bad to have inflated timers -- this is why
connections often get "stuck" in GPRS, particularly if you're
e.g. on a train.
There's more discussion of these issues in the IETF PILC (Performance
Implications of Link Characteristics) group's website [1].
There are also some good recommendations called "Wireless Profiled
TCP" [1] about how to tune your TCP settings to get better
performance. If your network operator doesn't do this transparently it
can be worth setting up a proxy (e.g. SOCKS) on the internet so that
you're always talking to its TCP rather than the ones of random
internet hosts. Having a good TCP on the sender-side is most
important.
Linux 2.4+ has a particularly nice base TCP to tune. Great features
are the Forward Acknowledgement ("FACK") [2] packet-loss recovery
algorithm that it uses and its ability to undo faulty
congestion-control decisions when timed-out packets (that were assumed
lost) turn up.
A couple of years ago me and some friends at work did a bunch of
hacking and built a box for GPRS networks to transparently optimize
TCP algorithms. (Tremendous fun!) Alas, the prototype was never
product'ified and the only information about our work that I can find
on the web are these slides (mostly in french):
http://dept-info.labri.fr/algotel03/CameraReady/Eisenmann-slides.pdf
Cheers,
Luke
[1]: http://www.ietf.org/html.charters/pilc-charter.html
[2]: http://www.wmlclub.com/docs/especwap2.0/WAP-225-TCP-20010331-a.pdf
[3]: http://www.psc.edu/networking/papers/fack_abstract.html
From: John Thingstad
Subject: Re: Was not making tail recursion elmination a mistake?
Date:
Message-ID: <opr9hb5usnpqzri1@mjolner.upc.no>
Perhaps I should elaborate. I am working on a chess algorithm that will!
run out of stack space
if elimination is not done. It uses mutual recursion of two funtions. Now
I have to resort to
someting like tagbody to make it work. This looses much of the elegance of
the original algorithm.
On Fri, 11 Jun 2004 18:49:29 +0200, John Thingstad
<··············@chello.no> wrote:
> I have recently been annoyeed by the fact that tail recursion
> elimination is
> not part of the standard. Any ansi compliant program can now not rely on
> recurive tail
> elimination and must use loops or some simular structue. For mutual
> recurion things get even uglier.
> Wouldn't it have been better to make a commentary on the implementation
> and require it?
> Most implementations do anyhow.
> What is the historic reason for this omission?
>
--
Using M2, Opera's revolutionary e-mail client: http://www.opera.com/m2/
From: Marco Baringer
Subject: Re: Was not making tail recursion elmination a mistake?
Date:
Message-ID: <m2oenpdlsm.fsf@convey.it>
"John Thingstad" <··············@chello.no> writes:
> Perhaps I should elaborate. I am working on a chess algorithm that
> will! run out of stack space if elimination is not done. It uses
> mutual recursion of two funtions. Now I have to resort to someting
> like tagbody to make it work. This looses much of the elegance of
> the original algorithm.
look into a technique called "trampolining". basically you'd rewrite
this:
(defun func1 ()
(func2))
(defun func2 ()
(func1))
as:
(defun func1 ()
(lambda ()
(func2)
(throw 'done t)))
(defun func2 ()
(lambda ()
(func1)
(throw 'done t)))
(defun run-trampolined (func)
(catch 'done
(loop for f = func then (funcall f))))
When you call this example:
(run-trampolined #'func1)
It will loop forever, but it won't run out of stack space. now all you
have to do is pick the best macros to hide the plumbing with.
--
-Marco
Ring the bells that still can ring.
Forget your perfect offering.
There is a crack in everything.
That's how the light gets in.
-Leonard Cohen
> look into a technique called "trampolining". basically you'd rewrite
I'm not familiar with this technique, but I couldn't get your example
to work. With some minor additional instrumentation, that does not
seem to affect the running:
CL-USER> (defun func1 ()
(lambda ()
(format t "Calling func2.~%")
(func2)
(throw 'done t)))
FUNC1
CL-USER> (defun func2 ()
(lambda ()
(format t "Calling func1.~%")
(func1)
(throw 'done t)))
FUNC2
CL-USER> (defun run-trampolined (func)
(catch 'done
(loop for f = func then (funcall f))))
RUN-TRAMPOLINED
CL-USER> (run-trampolined #'func1)
Calling func2.
T
CL-USER>
Cheers,
rif
From: Simon Katz
Subject: Re: Was not making tail recursion elmination a mistake?
Date:
Message-ID: <2j0glpFrmipaU1@uni-berlin.de>
"rif" <···@mit.edu> wrote in message
····················@five-percent-nation.mit.edu...
>
> I'm not familiar with this technique, but I couldn't get your
> example to work. With some minor additional instrumentation,
> that does not seem to affect the running:
>
> CL-USER> (defun func1 ()
> (lambda ()
> (format t "Calling func2.~%")
> (func2)
> (throw 'done t)))
> FUNC1
> CL-USER> (defun func2 ()
> (lambda ()
> (format t "Calling func1.~%")
> (func1)
> (throw 'done t)))
> FUNC2
> CL-USER> (defun run-trampolined (func)
> (catch 'done
> (loop for f = func then (funcall f))))
> RUN-TRAMPOLINED
> CL-USER> (run-trampolined #'func1)
> Calling func2.
> T
> CL-USER>
>
> Cheers,
>
> rif
The THROWs cause the loop to exit. Try this:
(defun func1 ()
(princ "1 ")
(sleep 1)
(lambda ()
(func2)))
(defun func2 ()
(princ "2 ")
(sleep 1)
(lambda ()
(func1)))
(defun run-trampolined (func)
(loop for f = func then (funcall f)))
(run-trampolined #'func1)
Simon Katz <······@nomistech.com> wrote:
+---------------
| The THROWs cause the loop to exit. Try this:
|
| (defun func1 ()
| (princ "1 ")
| (sleep 1)
| (lambda ()
| (func2)))
+---------------
Even simpler:
(defun func1 ()
(princ "1 ")
(sleep 1)
#'func2)
You only need to use LAMBDA here if you want to pass some closed-over
arguments to the next function in the chain.
+---------------
| (defun func2 ()
| (princ "2 ")
| (sleep 1)
| #'func1)
|
| (defun run-trampolined (func)
| (loop for f = func then (funcall f)))
|
| (run-trampolined #'func1)
+---------------
Yup! This is the standard "CPS by returning to trampoline" hack
used in so many C-based implementations of Scheme! ;-}
Although one typically wants to permit the state machine to exit
without having to throw an exception, e.g., returning NIL stops it:
(defun run-trampolined (func)
(loop for f = func then (funcall f)
while f))
-Rob
p.s. Note: On any system which buffers *STANDARD-OUTPUT* by default,
you'll need a FORCE-OUTPUT after each PRINC to see anything... ;-} ;-}
-----
Rob Warnock <····@rpw3.org>
627 26th Avenue <URL:http://rpw3.org/>
San Mateo, CA 94403 (650)572-2607
From: Marco Baringer
Subject: Re: Was not making tail recursion elmination a mistake?
Date:
Message-ID: <m2659wc16t.fsf@convey.it>
rif <···@mit.edu> writes:
>> look into a technique called "trampolining". basically you'd rewrite
>
> I'm not familiar with this technique, but I couldn't get your example
> to work. With some minor additional instrumentation, that does not
> seem to affect the running:
my bad. this technique is used when CPS transforming code, since my
example wasn't written in a CPS style (mainly it wasn't written such
that every form was in a tail position) it failed to prove my point.
here's an example which actually works. it's a recursive function for
calculating the length of a list. just so it's clear what i'm doing
i've started with the "normal" recursive version and re-written it
until it's in trampolined CPS form (this also serves to show the
similarities between the various transformations).
;; without this openmcl will optimize many of the tail calls away
CL-USER> (declaim (optimize debug safety))
NIL
CL-USER> (defun len (list)
(if (null list)
0
(1+ (len (cdr list)))))
LEN
CL-USER> (trace len)
NIL
CL-USER> (len (make-list 5))
Calling (LEN (NIL NIL NIL NIL NIL))
Calling (LEN (NIL NIL NIL NIL))
Calling (LEN (NIL NIL NIL))
Calling (LEN (NIL NIL))
Calling (LEN (NIL))
Calling (LEN NIL)
LEN returned 0
LEN returned 1
LEN returned 2
LEN returned 3
LEN returned 4
LEN returned 5
5
CL-USER> (defun len-cps (list k)
(if (null list)
(funcall k 0)
(len-cps (cdr list) (lambda (v)
(funcall k (1+ v))))))
LEN-CPS
CL-USER> (len-cps (make-list 5) #'identity)
5
CL-USER> (trace len-cps)
NIL
CL-USER> (len-cps (make-list 5) #'identity)
Calling (LEN-CPS (NIL NIL NIL NIL NIL) #<Compiled-function IDENTITY #x6061B86>)
Calling (LEN-CPS (NIL NIL NIL NIL) #<COMPILED-LEXICAL-CLOSURE #x649AB26>)
Calling (LEN-CPS (NIL NIL NIL) #<COMPILED-LEXICAL-CLOSURE #x649AAF6>)
Calling (LEN-CPS (NIL NIL) #<COMPILED-LEXICAL-CLOSURE #x649AADE>)
Calling (LEN-CPS (NIL) #<COMPILED-LEXICAL-CLOSURE #x649AAC6>)
Calling (LEN-CPS NIL #<COMPILED-LEXICAL-CLOSURE #x649AAAE>)
LEN-CPS returned 5
LEN-CPS returned 5
LEN-CPS returned 5
LEN-CPS returned 5
LEN-CPS returned 5
LEN-CPS returned 5
5
CL-USER> (defun len-tramp (list k)
(lambda ()
(if (null list)
(funcall k 0)
(len-tramp (cdr list) (lambda (v)
(funcall k (1+ v)))))))
LEN-TRAMP
CL-USER> (trace len-tramp)
NIL
CL-USER> (defun run-tramp (func)
(catch 'done
(loop for f = func
then (funcall f))))
RUN-TRAMP
CL-USER> (defun toplevel-k (value)
(throw 'done value))
TOPLEVEL-K
CL-USER> (run-tramp (len-tramp (make-list 5) #'toplevel-k))
Calling (LEN-TRAMP (NIL NIL NIL NIL NIL) #<Compiled-function TOPLEVEL-K #x64028D6>)
LEN-TRAMP returned #<COMPILED-LEXICAL-CLOSURE #x643646E>
Calling (LEN-TRAMP (NIL NIL NIL NIL) #<COMPILED-LEXICAL-CLOSURE #x6436446>)
LEN-TRAMP returned #<COMPILED-LEXICAL-CLOSURE #x6436426>
Calling (LEN-TRAMP (NIL NIL NIL) #<COMPILED-LEXICAL-CLOSURE #x6436406>)
LEN-TRAMP returned #<COMPILED-LEXICAL-CLOSURE #x64363E6>
Calling (LEN-TRAMP (NIL NIL) #<COMPILED-LEXICAL-CLOSURE #x64363C6>)
LEN-TRAMP returned #<COMPILED-LEXICAL-CLOSURE #x64363A6>
Calling (LEN-TRAMP (NIL) #<COMPILED-LEXICAL-CLOSURE #x6436386>)
LEN-TRAMP returned #<COMPILED-LEXICAL-CLOSURE #x6436366>
Calling (LEN-TRAMP NIL #<COMPILED-LEXICAL-CLOSURE #x6436346>)
LEN-TRAMP returned #<COMPILED-LEXICAL-CLOSURE #x6436326>
5
CL-USER>
hth.
--
-Marco
Ring the bells that still can ring.
Forget your perfect offering.
There is a crack in everything.
That's how the light gets in.
-Leonard Cohen
Marco Baringer <··@bese.it> wrote:
+---------------
| >> look into a technique called "trampolining". basically you'd rewrite
|
| my bad. this technique is used when CPS transforming code, since my
| example wasn't written in a CPS style ... it failed to prove my point.
|
| here's an example which actually works. it's a recursive function for
| calculating the length of a list. just so it's clear what i'm doing
| i've started with the "normal" recursive version and re-written it
| until it's in trampolined CPS form..
+---------------
But note that even in trampolined CPS form it is not necessary to use
THROW (which, when deeply nested, might be quite slow) to achieve the
desired result. Consider this slight rewrite [which, with no THROW,
allows replacing #'TOPLEVEL-K with #'IDENTITY]:
> (defun len-tramp (list k)
(if (null list)
(lambda () (funcall k 0))
(lambda ()
(len-tramp (cdr list) (lambda (v) (funcall k (1+ v)))))))
LEN-TRAMP
> (trace len-tramp)
NIL
> (defun run-tramp (func)
(loop for f = func then (funcall f)
while (functionp f)
finally (return f)))
RUN-TRAMP
> (run-tramp (lambda () (len-tramp '(a b c d e) #'identity)))
0: (LEN-TRAMP (A B C D E) #<Function IDENTITY {1019F481}>)
0: LEN-TRAMP returned #<Closure Over Function "LAMBDA (LIST K)" {48519951}>
0: (LEN-TRAMP (B C D E) #<Closure Over Function "LAMBDA (LIST K)" {4851A2F9}>)
0: LEN-TRAMP returned #<Closure Over Function "LAMBDA (LIST K)" {4851B9D1}>
0: (LEN-TRAMP (C D E) #<Closure Over Function "LAMBDA (LIST K)" {4851C379}>)
0: LEN-TRAMP returned #<Closure Over Function "LAMBDA (LIST K)" {4851DA19}>
0: (LEN-TRAMP (D E) #<Closure Over Function "LAMBDA (LIST K)" {4851E3C1}>)
0: LEN-TRAMP returned #<Closure Over Function "LAMBDA (LIST K)" {4851FA29}>
0: (LEN-TRAMP (E) #<Closure Over Function "LAMBDA (LIST K)" {485203D1}>)
0: LEN-TRAMP returned #<Closure Over Function "LAMBDA (LIST K)" {485219E9}>
0: (LEN-TRAMP NIL #<Closure Over Function "LAMBDA (LIST K)" {48522391}>)
0: LEN-TRAMP returned #<Closure Over Function "LAMBDA (LIST K)" {48523921}>
5
>
-Rob
-----
Rob Warnock <····@rpw3.org>
627 26th Avenue <URL:http://rpw3.org/>
San Mateo, CA 94403 (650)572-2607
From: Marco Baringer
Subject: Re: Was not making tail recursion elmination a mistake?
Date:
Message-ID: <m2smcz3n68.fsf@convey.it>
····@rpw3.org (Rob Warnock) writes:
> But note that even in trampolined CPS form it is not necessary to use
> THROW (which, when deeply nested, might be quite slow) to achieve the
> desired result. Consider this slight rewrite [which, with no THROW,
> allows replacing #'TOPLEVEL-K with #'IDENTITY]:
1) this means that the trampolined function can never return a
function.
2) the throw will never have to search more than two stack frames
(shortening the stack is the whole point of trampolining).
afaict. am i missing something?
--
-Marco
Ring the bells that still can ring.
Forget your perfect offering.
There is a crack in everything.
That's how the light gets in.
-Leonard Cohen
Marco Baringer <··@bese.it> wrote:
+---------------
| ····@rpw3.org (Rob Warnock) writes:
| > But note that even in trampolined CPS form it is not necessary to use
| > THROW (which, when deeply nested, might be quite slow) to achieve the
| > desired result. Consider this slight rewrite [which, with no THROW,
| > allows replacing #'TOPLEVEL-K with #'IDENTITY]:
|
| 1) this means that the trampolined function can never return a function.
+---------------
Well, you *can*, but it takes a small hack to the loop and the
reintroduction of a top-level value function to use instead of
#'IDENTITY, and it also helps to change the API for RUN-TRAMP
slightly, something like this, perhaps:
;;; RUN-TRAMP takes a function of one argument which calls the
;;; desired target function with the given argument as a continuation,
;;; e.g., (lambda (k) (foo arg1 arg2 ... k))
(defun run-tramp (func)
(let ((cookie nil))
(flet ((top-k (v) (setf cookie v) nil))
(loop for f = (funcall func #'top-k) then (funcall f)
while (functionp f)
finally (return (or cookie f))))))
[Note: The (RETURN (OR COOKIE F)) is unnecessary; it could just be
(RETURN COOKIE). I used the overly-defensive OR in case some called
function directly returned a non-function value instead of a trampoline
continuation.]
The function LEN-TRAMP remains the same as in my last reply, but
instead of starting it like this:
(run-tramp (lambda () (len-tramp '(a b c d e) #'identity)))
now you call it like this:
> (run-tramp (lambda (k) (len-tramp '(a b c d e) k)))
0: (LEN-TRAMP (A B C D E) #<Interpreted Function TOP-K {48536249}>)
0: LEN-TRAMP returned #<Interpreted Function "LAMBDA (LIST K)" {4853AF89}>
0: (LEN-TRAMP (B C D E) #<Interpreted Function "LAMBDA (LIST K)" {4853B571}>)
0: LEN-TRAMP returned #<Interpreted Function "LAMBDA (LIST K)" {4853BEE9}>
0: (LEN-TRAMP (C D E) #<Interpreted Function "LAMBDA (LIST K)" {4853C4B1}>)
0: LEN-TRAMP returned #<Interpreted Function "LAMBDA (LIST K)" {4853CE09}>
0: (LEN-TRAMP (D E) #<Interpreted Function "LAMBDA (LIST K)" {4853D3F1}>)
0: LEN-TRAMP returned #<Interpreted Function "LAMBDA (LIST K)" {4853DD29}>
0: (LEN-TRAMP (E) #<Interpreted Function "LAMBDA (LIST K)" {4853E2F1}>)
0: LEN-TRAMP returned #<Interpreted Function "LAMBDA (LIST K)" {4853EC09}>
0: (LEN-TRAMP NIL #<Interpreted Function "LAMBDA (LIST K)" {4853F1D1}>)
0: LEN-TRAMP returned #<Interpreted Function "LAMBDA (LIST K)" {4853FAA1}>
5
>
Now if you want to return a function, you can do like this [with apologies
for the continual wrapping & unwrapping of CONSTANTLY forms, just to get
a function result, but it does let the code resemble LEN-TRAMP's]:
> (defun func-val-tramp (count k)
(if (zerop count)
(lambda () (funcall k (constantly 0)))
(lambda ()
(func-val-tramp (1- count)
(lambda (v)
(funcall k (constantly (1+ (funcall v)))))))))
> (trace func-val-tramp)
> (run-tramp (lambda (k) (func-val-tramp 3 k)))
0: (FUNC-VAL-TRAMP 3 #<Interpreted Function TOP-K {485E5B41}>)
0: FUNC-VAL-TRAMP returned
#<Interpreted Function "LAMBDA (COUNT K)" {485EA751}>
0: (FUNC-VAL-TRAMP 2 #<Interpreted Function "LAMBDA (COUNT K)" {485EAD51}>)
0: FUNC-VAL-TRAMP returned
#<Interpreted Function "LAMBDA (COUNT K)" {485EB631}>
0: (FUNC-VAL-TRAMP 1 #<Interpreted Function "LAMBDA (COUNT K)" {485EBC31}>)
0: FUNC-VAL-TRAMP returned
#<Interpreted Function "LAMBDA (COUNT K)" {485EC501}>
0: (FUNC-VAL-TRAMP 0 #<Interpreted Function "LAMBDA (COUNT K)" {485ECB01}>)
0: FUNC-VAL-TRAMP returned
#<Interpreted Function "LAMBDA (COUNT K)" {485ED3F1}>
#<Closure Over Function "DEFUN CONSTANTLY" {485EDB49}>
>
So we got a function as a result, o.k.? Now let's call it and see what
the real result is:
> (funcall *)
3
>
+---------------
| 2) the throw will never have to search more than two stack frames
| (shortening the stack is the whole point of trampolining).
|
| afaict. am i missing something?
+---------------
Not really. It's just a difference of perception in the cost of THROW
(which I assume to be high, even across a small number of stack frames)
versus an extra FUNCALL or two.
-Rob
-----
Rob Warnock <····@rpw3.org>
627 26th Avenue <URL:http://rpw3.org/>
San Mateo, CA 94403 (650)572-2607
From: Svein Ove Aas
Subject: Re: Was not making tail recursion elmination a mistake?
Date:
Message-ID: <cak03t$jmj$2@services.kq.no>
Rob Warnock wrote:
> Not really. It's just a difference of perception in the cost of THROW
> (which I assume to be high, even across a small number of stack frames)
> versus an extra FUNCALL or two.
Is it?
I seem to remember a comparison on norvig.com that shows Lisp exceptions
to be 1% of the cost of C++ exceptions; that's pretty good.
Doesn't that include throw/catch?
Svein Ove Aas <··············@brage.info> wrote:
+---------------
| Rob Warnock wrote:
| > Not really. It's just a difference of perception in the cost of THROW
| > (which I assume to be high, even across a small number of stack frames)
| > versus an extra FUNCALL or two.
|
| Is it?
| I seem to remember a comparison on norvig.com that shows Lisp exceptions
| to be 1% of the cost of C++ exceptions; that's pretty good.
| Doesn't that include throw/catch?
+---------------
You're changing the subject: I did *NOT* compare Lisp THROW/CATCH to
C++ exceptions. I compared Lisp THROW/CATCH to Lisp FUNCALL/returns.
-Rob
-----
Rob Warnock <····@rpw3.org>
627 26th Avenue <URL:http://rpw3.org/>
San Mateo, CA 94403 (650)572-2607
From: Rahul Jain
Subject: Re: Was not making tail recursion elmination a mistake?
Date:
Message-ID: <87llilsjoi.fsf@nyct.net>
Svein Ove Aas <··············@brage.info> writes:
> Rob Warnock wrote:
>
>> Not really. It's just a difference of perception in the cost of THROW
>> (which I assume to be high, even across a small number of stack frames)
>> versus an extra FUNCALL or two.
>
> Is it?
> I seem to remember a comparison on norvig.com that shows Lisp exceptions
> to be 1% of the cost of C++ exceptions; that's pretty good.
> Doesn't that include throw/catch?
It shouldn't, since in Lisp, exceptional situations aren't necessarily
handled by unwinding the stack. However, THROW/CATCH in Lisp
implementations is usually very fast compared to throw/catch in C++ or
Java. But why does it matter? We're talking about Lisp here, not C++.
--
Rahul Jain
·····@nyct.net
Professional Software Developer, Amateur Quantum Mechanicist
Le Thu, 17 Jun 2004 22:07:25 -0400, Rahul Jain a �crit�:
> However, THROW/CATCH in Lisp
> implementations is usually very fast compared to throw/catch in C++ or
> Java.
Just curious, but what makes it so fast in Lisp (implementations) ? Is
there something special about the language that helps
implementors write fast throw/catches ?
Is the handler-bind/signal pair equally fast ?
> But why does it matter? We're talking about Lisp here, not C++.
Sure. Nevertheless, there is a myth out there saying "don't use exception
handling, for it's dog slow". Norvig's site shows EH speed of Java roughly
equivalent to its C++ couterpart : so both languages have slow exception
signalment.
Now, I like the idea of abusing the EH system to escape from deep
contexts, or to set up some protocol between two parts of the same
non-threaded program. (... getting even more off-topic ...) I may try to
build coroutines on top of the CL exception handling mecanism... just to
see if it makes sense ...
Aur�lien.
From: Duane Rettig
Subject: Re: Was not making tail recursion elmination a mistake?
Date:
Message-ID: <43c4s7pls.fsf@franz.com>
Aur�lien Camp�as <···········@wanadoo.fr> writes:
> Le Thu, 17 Jun 2004 22:07:25 -0400, Rahul Jain a �crit�:
>
> > However, THROW/CATCH in Lisp
> > implementations is usually very fast compared to throw/catch in C++ or
> > Java.
>
> Just curious, but what makes it so fast in Lisp (implementations) ? Is
> there something special about the language that helps
> implementors write fast throw/catches ?
Not the language; the implementation techniques. Many systems are
written with C and C calling conventions in mind, and the exception
handling and nonlocal-jumping are sometimes implemented in C in terms
of setjmp/longjump, which might not suit the requirements of the
language. CL implementations can also do this. I suspect, however,
that most CL implementations go directly to the machine level, defining
their own context saving and restoring structures and mechanisms that are
best suited to the CL problem sets. Some lisps do this via assembler
language. A disadvantage of this is that the implementation must be
ported to each architecture, but once this is done, the speed advantage
is fairly good.
Note that a throw must make stops at all unwind-protect markers on the
way out, so this is definitely a YMMV thing; you can slow down a throw
to a catch far away to arbitrary lengths of time simply by loading up
your code with large numbers of cleanup forms that do a lot of work.
> Is the handler-bind/signal pair equally fast ?
Don't forget handler-case as well as restart-case/restart-bind.
These are all built with catch/throw as building blocks, but they are not
the only building blocks used, and throws may not necessarily be involved.
When they are, they would tend to be longer, since handlers and restarts
need to be looked up in order to find out where to perform the throw.
If a throw isn't done, though, it might be faster, depending on the
speed of the lookups vs the throw itself. But such throws usually
involve unwind-protect cleanups to remove intermediate restarts and
handlers, so I wold guess that on average it is slower.
> > But why does it matter? We're talking about Lisp here, not C++.
>
> Sure. Nevertheless, there is a myth out there saying "don't use exception
> handling, for it's dog slow".
Whenever you hear or read something that you can recognize as hyperbole,
it is always a good idea to discount the statement and find out what
is _really_ meant, precisely (and I think that that is what you're
doing by asking these questions). But what is "Dog Slow" to one
person is "Blindingly Fast" to another. What would you say if I told
you that an operation took 100 cpu cycles to complete? If we were
talking about a single floating-point operation, it would be "dog slow",
and if we were talking about an interrupt-handling round-trip, it would
be "reasonably fast". If you were talking about a database transaction,
I might disbelieve you, but if you were to convince me that it really
occurs, I would call it "blazingly fast".
> Norvig's site shows EH speed of Java roughly
> equivalent to its C++ couterpart : so both languages have slow exception
> signalment.
>
> Now, I like the idea of abusing the EH system to escape from deep
> contexts, or to set up some protocol between two parts of the same
> non-threaded program. (... getting even more off-topic ...) I may try to
> build coroutines on top of the CL exception handling mecanism... just to
> see if it makes sense ...
That would be an informative experiment for you to try. It would
give you a feel for exactly what kinds of scaling you are dealing with.
--
Duane Rettig ·····@franz.com Franz Inc. http://www.franz.com/
555 12th St., Suite 1450 http://www.555citycenter.com/
Oakland, Ca. 94607 Phone: (510) 452-2000; Fax: (510) 452-0182
Le Fri, 18 Jun 2004 10:17:19 -0700, Duane Rettig a �crit�:
>> Just curious, but what makes it so fast in Lisp (implementations) ? Is
>> there something special about the language that helps implementors
>> write fast throw/catches ?
>
> Not the language; the implementation techniques. Many systems are
> written with C and C calling conventions in mind, and the exception
> handling and nonlocal-jumping are sometimes implemented in C in terms
> of setjmp/longjump, which might not suit the requirements of the
> language.
Possibly the requirements of C++ ? (note that I don't hold my breath
waiting for an answer about this...)
> CL implementations can also do this. I suspect, however,
> that most CL implementations go directly to the machine level, defining
> their own context saving and restoring structures and mechanisms that are
> best suited to the CL problem sets. Some lisps do this via assembler
> language. A disadvantage of this is that the implementation must be
> ported to each architecture, but once this is done, the speed advantage
> is fairly good.
That's quite interesting.
> Note that a throw must make stops at all unwind-protect markers on the
> way out, so this is definitely a YMMV thing; you can slow down a throw
> to a catch far away to arbitrary lengths of time simply by loading up
> your code with large numbers of cleanup forms that do a lot of work.
hmm, ok, I'm beginning to see all those hidden unwind-protect in the
dynamic path ... more importantly, who set them and why.
> >> Is the handler-bind/signal pair equally fast ?
>
> Don't forget handler-case as well as restart-case/restart-bind.
I have yet to understand what they are for... Next step :)
> These are all built with catch/throw as building blocks, but they are not
> the only building blocks used, and throws may not necessarily be involved.
Throw would be involved only if we had to unwind the stack after exiting
terminally the condition handler, that's it ?
> When they are, they would tend to be longer,
> since handlers and restarts
> need to be looked up in order to find out where to perform the throw.
> If a throw isn't done, though, it might be faster, depending on the
> speed of the lookups vs the throw itself. But such throws usually
> involve unwind-protect cleanups to remove intermediate restarts and
> handlers, so I wold guess that on average it is slower.
hmmm, I don't get it. Clearly I don't have a complete model of what may or
may not happen.
If we restart, no need to throw, but we had to collect some info about
the restarts before tranfering control to the handler ... and that would
be what we get back when applying the condition object to
(compute-restarts ...) ...
If we ultimately throw, we have to go through the cleanup forms of all
those explicit and implicit unwind-protect's ...
I know there are holes there, but is it a correct starting point ?
>
>> > But why does it matter? We're talking about Lisp here, not C++.
>>
>> Sure. Nevertheless, there is a myth out there saying "don't use exception
>> handling, for it's dog slow".
>
> Whenever you hear or read something that you can recognize as hyperbole,
[...]
> "blazingly fast".
... I question it...
>> Norvig's site shows EH speed of Java roughly
>> equivalent to its C++ couterpart : so both languages have slow exception
>> signalment.
>>
>> Now, I like the idea of abusing the EH system to escape from deep
>> contexts, or to set up some protocol between two parts of the same
>> non-threaded program. (... getting even more off-topic ...) I may try to
>> build coroutines on top of the CL exception handling mecanism... just to
>> see if it makes sense ...
>
> That would be an informative experiment for you to try. It would
> give you a feel for exactly what kinds of scaling you are dealing with.
I'm glad you think this may be a worthwhile exercise. Thank you, M Rettig !
Aur�lien.
From: Duane Rettig
Subject: Re: Was not making tail recursion elmination a mistake?
Date:
Message-ID: <4k6y4h554.fsf@franz.com>
Aur�lien Camp�as <···········@wanadoo.fr> writes:
> Le Fri, 18 Jun 2004 10:17:19 -0700, Duane Rettig a �crit�:
>
> >> Just curious, but what makes it so fast in Lisp (implementations) ? Is
> >> there something special about the language that helps implementors
> >> write fast throw/catches ?
> >
> > Not the language; the implementation techniques. Many systems are
> > written with C and C calling conventions in mind, and the exception
> > handling and nonlocal-jumping are sometimes implemented in C in terms
> > of setjmp/longjump, which might not suit the requirements of the
> > language.
>
> Possibly the requirements of C++ ? (note that I don't hold my breath
> waiting for an answer about this...)
The TRY/EXCEPT style constructs in C++ are definitely part of this whole
C calling conventions thing; some of these standards are more robust than
others and take C++ into consideration explicitly. I haven't looked too
closely at the code they generate; they may possibly generate fairly
efficient code, now that C++ has moved away from being a glorified
precompiler to C...
> > Note that a throw must make stops at all unwind-protect markers on the
> > way out, so this is definitely a YMMV thing; you can slow down a throw
> > to a catch far away to arbitrary lengths of time simply by loading up
> > your code with large numbers of cleanup forms that do a lot of work.
>
> hmm, ok, I'm beginning to see all those hidden unwind-protect in the
> dynamic path ... more importantly, who set them and why.
Yes. On the one hand, you don't want to create unwind-protects
willy-nilly in your code if they aren't really needed. On the other
hand, it's nice to knwo that they are there and are guaranteed to run
under normal and non-local return situations.
> > >> Is the handler-bind/signal pair equally fast ?
> >
> > Don't forget handler-case as well as restart-case/restart-bind.
>
> I have yet to understand what they are for... Next step :)
:-)
> > These are all built with catch/throw as building blocks, but they are not
> > the only building blocks used, and throws may not necessarily be involved.
>
> Throw would be involved only if we had to unwind the stack after exiting
> terminally the condition handler, that's it ?
Yes. Catch sets up a catchframe context (similar to a jmpbuf in the
setjmp() analogy) and if the return is normal, it just pops the catchframe
and goes on. Very fast, but probably no faster than the first-return
from a setjmp().
> > When they are, they would tend to be longer,
> > since handlers and restarts
> > need to be looked up in order to find out where to perform the throw.
> > If a throw isn't done, though, it might be faster, depending on the
> > speed of the lookups vs the throw itself. But such throws usually
> > involve unwind-protect cleanups to remove intermediate restarts and
> > handlers, so I wold guess that on average it is slower.
>
> hmmm, I don't get it. Clearly I don't have a complete model of what may or
> may not happen.
>
> If we restart, no need to throw, but we had to collect some info about
> the restarts before tranfering control to the handler ... and that would
> be what we get back when applying the condition object to
> (compute-restarts ...) ...
Computing restarts doesn't require a throw, but invoking a restart
will, probably.
> If we ultimately throw, we have to go through the cleanup forms of all
> those explicit and implicit unwind-protect's ...
>
> I know there are holes there, but is it a correct starting point ?
Yes.
> >> > But why does it matter? We're talking about Lisp here, not C++.
> >>
> >> Sure. Nevertheless, there is a myth out there saying "don't use exception
> >> handling, for it's dog slow".
> >
> > Whenever you hear or read something that you can recognize as hyperbole,
> [...]
> > "blazingly fast".
>
> ... I question it...
Good.
> >> Norvig's site shows EH speed of Java roughly
> >> equivalent to its C++ couterpart : so both languages have slow exception
> >> signalment.
> >>
> >> Now, I like the idea of abusing the EH system to escape from deep
> >> contexts, or to set up some protocol between two parts of the same
> >> non-threaded program. (... getting even more off-topic ...) I may try to
> >> build coroutines on top of the CL exception handling mecanism... just to
> >> see if it makes sense ...
> >
> > That would be an informative experiment for you to try. It would
> > give you a feel for exactly what kinds of scaling you are dealing with.
>
> I'm glad you think this may be a worthwhile exercise. Thank you, M Rettig !
No problem. Good luck.
--
Duane Rettig ·····@franz.com Franz Inc. http://www.franz.com/
555 12th St., Suite 1450 http://www.555citycenter.com/
Oakland, Ca. 94607 Phone: (510) 452-2000; Fax: (510) 452-0182
Le Fri, 18 Jun 2004 15:29:11 -0700, Duane Rettig a �crit�:
>> I have yet to understand what they are for... Next step :)
>
> :-)
I'm getting there ...
> > Computing restarts doesn't require a throw, but invoking a restart
> will, probably.
By "probably" you mean "iff the restart established with restart-bind just
returns normally" ? (Brian suggested this, are there other cases ?)
>> >> Now, I like the idea of abusing the EH system to escape from deep
>> >> contexts, or to set up some protocol between two parts of the same
>> >> non-threaded program. (... getting even more off-topic ...) I may try to
>> >> build coroutines on top of the CL exception handling mecanism... just to
>> >> see if it makes sense ...
>> >
>> > That would be an informative experiment for you to try. It would
>> > give you a feel for exactly what kinds of scaling you are dealing with.
>>
>> I'm glad you think this may be a worthwhile exercise. Thank you, M Rettig !
>
> No problem. Good luck.
hmmm, since real coroutines (not just thunks) need their own call stack,
that might be well an impossible thing ...
Aur�lien.
>
>> Norvig's site shows EH speed of Java roughly
>> equivalent to its C++ couterpart : so both languages have slow exception
>> signalment.
>>
Hi,
don't know about C++, but exceptions in Java are slow because
they capture a lot of stack info (for debugging I suppose).
You can define your own much faster exceptions like so:
public class LightWeightException extends Exception {
public LightWeightException(String message) {
super(message);
}
public LightWeightException() {
super();
}
public Throwable fillInStackTrace() {
return this;
}
}
The constructor in class Exception calls fillInStackTrace,
which is overridden to do nothing.
Please excuse the Java code in this newsgroup, but for a
relation to CL see the PS :-)
Bernhard
PS: Actually the way this works is interesting, as it shows
potential pitfalls in constructing objects, something CLOS
solves with a convention: use after methods on shared-initialize
for adding specific (constructor-like) code.
--
---------------------------------------------------------------------
Bernhard Pfahringer, Dept. of Computer Science, University of Waikato
http://www.cs.waikato.ac.nz/~bernhard +64 7 838 4041
From: Brian Downing
Subject: Re: Was not making tail recursion elmination a mistake?
Date:
Message-ID: <r_DAc.50707$Hg2.30009@attbi_s04>
In article <······························@wanadoo.fr>,
Aur�lien Camp�as <···········@wanadoo.fr> wrote:
> Just curious, but what makes it so fast in Lisp (implementations) ? Is
> there something special about the language that helps
> implementors write fast throw/catches ?
>
> Is the handler-bind/signal pair equally fast ?
Once you've spent the cost of the protocol layer that the condition
system provides, it's probably the same thing.
The HANDLER-BIND/RESTART-BIND pair don't actually transfer control
anywhere. Even ERROR doesn't, it just starts the debugger if the
condition was unhandled. The only way to actually unroll the stack is
to do one of the other non-local jumps; either THROW/CATCH, or a
non-local TAGBODY/GO, which I believe is more typical for handlers and
restarts, since they tend to be defined in one nice lexical chunk.
So at its root level, the basic condition system (HANDLER-BIND,
RESTART-BIND, SIGNAL, and ERROR) can't actually transfer control
anywhere - it's just a protocol layer. I was very impressed at the
thought and design involved when I figured this out. Some of the
convenience macros (the -CASE family) do transfer control, but they do
it with the same basic CL non-local jumps. I definitely recommend
playing around with just the raw RESTART-BIND and HANDLER-BIND for a
deeper understanding of just what's going on in the condition system.
(I'm pretty sure that Kent's paper:
http://www.nhplace.com/kent/Papers/Condition-Handling-2001.html
talks about this, but I had to play around with raw HANDLER-BIND and
RESTART-BIND before I "got" it.)
> Now, I like the idea of abusing the EH system to escape from deep
> contexts, or to set up some protocol between two parts of the same
> non-threaded program. (... getting even more off-topic ...) I may try to
> build coroutines on top of the CL exception handling mecanism... just to
> see if it makes sense ...
Fortunately you don't have to worry about "abusing" exception handling
in CL, since they (very carefully I imagine) don't call anything
exception handling. You just have the condition system (a protocol
layer), and lexical and dynamic non-local gotos. If you don't need the
extra protocol provided by the condition system, there's no reason to
use it in favor of the more simple non-local gotos. This point is
well-made in Kent's paper, see "Condition Handling Is Primarily a
Protocol Matter" for instance.
(Another interesting thing I discovered while playing with this is that
it's easy to implement THROW/CATCH in terms of TAGBODY, GO, closures,
and a dynamic variable.)
-bcd
Le Fri, 18 Jun 2004 15:36:56 +0000, Brian Downing a �crit�:
> In article <······························@wanadoo.fr>,
> Aur�lien Camp�as <···········@wanadoo.fr> wrote:
>> Just curious, but what makes it so fast in Lisp (implementations) ? Is
>> there something special about the language that helps
>> implementors write fast throw/catches ?
>>
>> Is the handler-bind/signal pair equally fast ?
>
> Once you've spent the cost of the protocol layer that the condition
> system provides, it's probably the same thing.
>
> The HANDLER-BIND/RESTART-BIND pair don't actually transfer control
> anywhere. Even ERROR doesn't,
Yes. I'm getting the importance of this. We execute some recovery action
in the dynamic environment of the signalling context, maybe choose a
restart and bail out (unwind) only if nothing else can be done.
Yet I read (CLHS) about HANDLER-CASE, the RESTART-* and barely grok what
role those primitives play. hmmm, work for tomorrow :)
> it just starts the debugger if the
> condition was unhandled. The only way to actually unroll the stack is
> to do one of the other non-local jumps; either THROW/CATCH, or a
> non-local TAGBODY/GO, which I believe is more typical for handlers and
> restarts, since they tend to be defined in one nice lexical chunk.
>
> So at its root
level, the basic condition system (HANDLER-BIND,
> RESTART-BIND, SIGNAL, and ERROR) can't actually transfer control
> anywhere - it's just a protocol layer.
Seems like a broad statement for me. Certainly, signal/cerror/error and
invoke-restart transfer control, no ?
> I was very impressed at the
> thought and design involved when I figured this out. Some of the
> convenience macros (the -CASE family) do transfer control, but they do
> it with the same basic CL non-local jumps. I definitely recommend
> playing around with just the raw RESTART-BIND and HANDLER-BIND for a
> deeper understanding of just what's going on in the condition system.
I am impressed, too. Also I read Kent Pitman's papers and they help a lot
to grok the condition system, hmm, at a philosophical level (or maybe I'm
dense)...
Ah, and Peter Seibel's chapter on the same topic helped, too, at a more
pragmatic level.
> Fortunately you don't have to worry about "abusing" exception handling
> in CL, since they (very carefully I imagine) don't call anything
> exception handling.
Indeed. I really meant "abusing the condition system".
> You just have the condition system (a protocol
> layer), and lexical and dynamic non-local gotos. If you don't need the
> extra protocol provided by the condition system, there's no reason to
> use it in favor of the more simple non-local gotos. This point is
> well-made in Kent's paper, see "Condition Handling Is Primarily a
> Protocol Matter" for instance.
>
> (Another interesting thing I discovered while playing with this is that
> it's easy to implement THROW/CATCH in terms of TAGBODY, GO, closures,
> and a dynamic variable.)
>
> -bcd
Thanks a lot,
Aur�lien.
From: Brian Downing
Subject: Re: Was not making tail recursion elmination a mistake?
Date:
Message-ID: <lGIAc.135158$Ly.79971@attbi_s01>
In article <······························@wanadoo.fr>,
Aur�lien Camp�as <···········@wanadoo.fr> wrote:
> Seems like a broad statement for me. Certainly, signal/cerror/error and
> invoke-restart transfer control, no ?
Not without the control transfer happening either in a handler, a
restart, or a strange *DEBUGGER-HOOK*. All of the functions you
mentioned conceptually behave as normal function calls. They certainly
don't unwind the stack on their own. ERROR is basically
(progn (signal ...) (invoke-debugger)). CERROR is the same except that
it sets up a restart (which will do a non-local control transfer if
called, but CERROR itself doesn't.) Entering the debugger is obviously
not going to unwind the stack - it wouldn't be much of a debugger if it
did!
(signal condition) basically finds the first handler in the dynamic
environment that matches the condition, and funcalls its handler
function (the one you write directly with HANDLER-BIND). If that
function does not do a non-local transfer of control, it chose not to
handle the condition, and the search goes deeper.
(invoke-restart restart) basically finds the first restart in the
dynamic environment that matches restart, and funcalls its restart
function (the one you write directly with RESTART-BIND). That function
can (and most likely should) perform some form of non-local jump, but it
doesn't have to.
This confused me at first too when I was playing with this. I had a
handler 'handler that did (invoke-restart 'foo) where the 'foo restart
just printed something out. However, an (error 'handler) went into the
debugger after calling my restart - my handler had declined! This
confused me until I realized that INVOKE-RESTART is /NOT/ a non-local
jump! It just called my restart, my restart didn't go anywhere,
INVOKE-RESTART returned normally, my handler returned normally, which
means it declined to handle the condition! The next step was for ERROR
to call INVOKE-DEBUGGER.
I think this is why generally it's recommended to use RESTART-CASE for
most situations. The condition system seems much more normal if calling
a restart always results in a transfer of control (which RESTART-CASE
guarantees - try macroexpanding it!)
-bcd
Le Fri, 18 Jun 2004 20:56:49 +0000, Brian Downing a �crit�:
> In article <······························@wanadoo.fr>,
> Aur�lien Camp�as <···········@wanadoo.fr> wrote:
>> Seems like a broad statement for me. Certainly, signal/cerror/error and
>> invoke-restart transfer control, no ?
>
> Not without the control transfer happening either in a handler, a
> restart, or a strange *DEBUGGER-HOOK*. All of the functions you
> mentioned conceptually behave as normal function calls.
[...]
Sorry, I should have read "non local transfer of control" ...
> (signal condition) basically finds the first handler in the dynamic
> environment that matches the condition, and funcalls its handler
> function (the one you write directly with HANDLER-BIND). If that
> function does not do a non-local transfer of control, it chose not to
> handle the condition, and the search goes deeper.
Yes, I just read about that in the CLHS. I was troubled at first that "not
handling" the condition and resignalling were two different things.
In fact, choosing not to handle is equivalent to resignalling the same
condition (and doing nothing further), isn't it ?
> (invoke-restart restart) basically finds the first restart in the
> dynamic environment that matches restart, and funcalls its restart
> function (the one you write directly with RESTART-BIND). That function
> can (and most likely should) perform some form of non-local jump, but it
> doesn't have to.
>
> This confused me at first too when I was playing with this. I had a
> handler 'handler that did (invoke-restart 'foo) where the 'foo restart
> just printed something out. However, an (error 'handler) went into the
> debugger after calling my restart - my handler had declined! This
> confused me until I realized that INVOKE-RESTART is /NOT/ a non-local
> jump! It just called my restart, my restart didn't go anywhere,
> INVOKE-RESTART returned normally, my handler returned normally, which
> means it declined to handle the condition! The next step was for ERROR
> to call INVOKE-DEBUGGER.
Thanks for this, I just tested those forms and I'm beginning to understand
what restarts are. I checked your point about restart-bind's not
automatically unwinding, too.
Now I see what it means to "repair" the signalling context ... and how
braindamaged most (so-called) exception handling systems are ...
> I think this is why generally it's recommended to use RESTART-CASE for
> most situations. The condition system seems much more normal if calling
> a restart always results in a transfer of control (which RESTART-CASE
> guarantees - try macroexpanding it!)
>
> -bcd
Aur�lien.
From: Brian Downing
Subject: Re: Was not making tail recursion elmination a mistake?
Date:
Message-ID: <b82Bc.71355$eu.20892@attbi_s02>
In article <······························@wanadoo.fr>,
Aur�lien Camp�as <···········@wanadoo.fr> wrote:
> Yes, I just read about that in the CLHS. I was troubled at first that "not
> handling" the condition and resignalling were two different things.
>
> In fact, choosing not to handle is equivalent to resignalling the same
> condition (and doing nothing further), isn't it ?
I'm not sure. I think the end result would be the same, but you may
build up frames of SIGNAL calls in the interim since it's possible that
no stack unwinding is occurring. In a language where the stack unwound
immediately it would be exactly equivalent I think.
Since the language defines a protocol for declining to handle a
condition, bypassing that protocol by resignalling would seem to be in
extremely bad style if nothing else.
(Anybody care to check my logic on this?)
-bcd
--
*** Brian Downing <bdowning at lavos dot net>
From: John Thingstad
Subject: Re: Was not making tail recursion elmination a mistake?
Date:
Message-ID: <opr9he3dpmpqzri1@mjolner.upc.no>
Thanks. That seems like a plan!
On Sat, 12 Jun 2004 14:04:57 +0200, Marco Baringer <··@bese.it> wrote:
> "John Thingstad" <··············@chello.no> writes:
>
>> Perhaps I should elaborate. I am working on a chess algorithm that
>> will! run out of stack space if elimination is not done. It uses
>> mutual recursion of two funtions. Now I have to resort to someting
>> like tagbody to make it work. This looses much of the elegance of
>> the original algorithm.
>
> look into a technique called "trampolining". basically you'd rewrite
> this:
>
> (defun func1 ()
> (func2))
>
> (defun func2 ()
> (func1))
>
> as:
>
> (defun func1 ()
> (lambda ()
> (func2)
> (throw 'done t)))
>
> (defun func2 ()
> (lambda ()
> (func1)
> (throw 'done t)))
>
> (defun run-trampolined (func)
> (catch 'done
> (loop for f = func then (funcall f))))
>
> When you call this example:
>
> (run-trampolined #'func1)
>
> It will loop forever, but it won't run out of stack space. now all you
> have to do is pick the best macros to hide the plumbing with.
>
--
Using M2, Opera's revolutionary e-mail client: http://www.opera.com/m2/
Marco Baringer <··@bese.it> writes:
> "John Thingstad" <··············@chello.no> writes:
>
> > Perhaps I should elaborate. I am working on a chess algorithm that
> > will! run out of stack space if elimination is not done. It uses
> > mutual recursion of two funtions. Now I have to resort to someting
> > like tagbody to make it work. This looses much of the elegance of
> > the original algorithm.
>
> look into a technique called "trampolining". basically you'd rewrite
> this:
>
> (defun func1 ()
> (func2))
>
> (defun func2 ()
> (func1))
>
> as:
>
> (defun func1 ()
> (lambda ()
> (func2)
> (throw 'done t)))
>
> (defun func2 ()
> (lambda ()
> (func1)
> (throw 'done t)))
>
> (defun run-trampolined (func)
> (catch 'done
> (loop for f = func then (funcall f))))
That doesn't look right to me, and someone else has tried it
and found that it didn't work. I think what you want is, with
the definition of RUN-TRAMPOLINED above,
(defun func1 () #'func2)
(defun func2 () #'func1)
or, if you need to be able to pass arguments around,
(defun run-trampolined (func args)
(catch 'done
(loop
(let ((new-func-and-args (multiple-value-list (apply func args))))
(setf func (first new-func-and-args)
args (rest new-func-and-args))))))
(defun func1 (n)
(values #'func2 n))
(defun func2 (n)
(if (zerop n)
(throw 'done 'i-am-the-walrus)
(values #'func1 (1- n))))
--
Gareth McCaughan
.sig under construc
····@rpw3.org (Rob Warnock) writes:
> Gareth McCaughan <················@pobox.com> wrote:
> +---------------
> | Marco Baringer <··@bese.it> writes:
> | > ...
> |
> | I think what you want is, with the definition of RUN-TRAMPOLINED above,
> | (defun func1 () #'func2)
> | (defun func2 () #'func1)
> | or, if you need to be able to pass arguments around,
> | (defun run-trampolined (func args)
> | (catch 'done
> | (loop ... )))
> +---------------
>
> Actually, you don't even need the THROW to pass arguments around:
> just use closures over the args:
I wasn't using the THROW to pass arguments around, but
you're correct that THROW is in fact not needed at all. :-)
--
Gareth McCaughan
.sig under construc
Marco Baringer <··@bese.it> writes:
> "John Thingstad" <··············@chello.no> writes:
>
> > Perhaps I should elaborate. I am working on a chess algorithm that
> > will! run out of stack space if elimination is not done. It uses
> > mutual recursion of two funtions. Now I have to resort to someting
> > like tagbody to make it work. This looses much of the elegance of
> > the original algorithm.
>
> look into a technique called "trampolining".
A few years ago, I hacked up a portable tail-call merging utility that
did this. I added docstrings, and packaged it up with asdf; you can
get it from here:
http://www.cliki.net/org-no-carrier-tail-funcall
It's probably most useful for doing merging of lexically visible
tail-calls, but it handles any tail-funcall form within the dynamic
extent of a WITH-TAIL-CALL-UNIT form (which is where the trampolining
is done). Eg:
CL-USER> (defun count-to (goal &optional (start 0))
(with-tail-call-unit ()
(labels ((worker (count)
(format t "count is ~D~%" count)
(if (>= count goal)
(values count goal)
(tail-funcall #'worker (1+ count)))))
(worker start))))
COUNT-TO
CL-USER> (count-to 10)
count is 0
count is 1
count is 2
count is 3
count is 4
count is 5
count is 6
count is 7
count is 8
count is 9
count is 10
10
10
You can see it trampolining if you use tail-funcall in a non-tail position:
CL-USER> (defun count-to (goal &optional (start 0))
(with-tail-call-unit ()
(labels ((worker (count)
(unwind-protect
(progn (format t "count is ~D~%" count)
(if (>= count goal)
(values count goal)
(tail-funcall #'worker (1+ count))))
(format t "... unwinding ...~%"))))
(worker start))))
STYLE-WARNING: redefining COUNT-TO in DEFUN
COUNT-TO
CL-USER> (count-to 10)
count is 0
... unwinding ...
count is 1
... unwinding ...
count is 2
... unwinding ...
count is 3
... unwinding ...
count is 4
... unwinding ...
count is 5
... unwinding ...
count is 6
... unwinding ...
count is 7
... unwinding ...
count is 8
... unwinding ...
count is 9
... unwinding ...
count is 10
... unwinding ...
10
10
Finally, for those curious:
ORG.NO-CARRIER.TAIL-FUNCALL>
(swank-backend:macroexpand-all
'(with-tail-call-unit ()
(labels ((worker (count)
(format t "count is ~D~%" count)
(if (>= count goal)
(values count goal)
(tail-funcall #'worker (1+ count)))))
(worker start))))
(block .block.
(let* ((.thunk. (constantly nil))
(*tail-funcall-function* *tail-funcall-function*))
(declare (type function .thunk.))
(tagbody
.start.
(macrolet ((tail-funcall (&rest args)
`(local-tail-funcall ,@args)))
(setq .thunk.
(lambda ()
(labels ((worker (count)
(format t "count is ~D~%" count)
(if (>= count goal)
(values count goal)
(progn
(setq .thunk.
(lambda ()
(funcall #'worker (1+ count))))
(go .loop.)))))
(worker start))))
(setq *tail-funcall-function*
(lambda (fn &rest args)
(declare (type function fn))
(let ((thunk (lambda () (apply fn args))))
(progn
(setq .thunk. (lambda () (funcall thunk)))
(go .loop.))))))
.loop.
(return-from .block. (funcall .thunk.)))))
From: Edi Weitz
Subject: Re: Was not making tail recursion elmination a mistake?
Date:
Message-ID: <87fz91c741.fsf@bird.agharta.de>
On Sat, 12 Jun 2004 13:42:56 +0200, "John Thingstad" <··············@chello.no> wrote:
> Perhaps I should elaborate. I am working on a chess algorithm that
> will! run out of stack space if elimination is not done. It uses
> mutual recursion of two funtions. Now I have to resort to someting
> like tagbody to make it work. This looses much of the elegance of
> the original algorithm.
Why? Is someone forcing you to make your program work with every
available Common Lisp implementation? Pick one that does tail call
elimination given sufficient declarations and go with it.
Edi Weitz wrote:
> On Sat, 12 Jun 2004 13:42:56 +0200, "John Thingstad"
> <··············@chello.no> wrote:
>
>> Perhaps I should elaborate. I am working on a chess algorithm that
>> will! run out of stack space if elimination is not done. It uses
>> mutual recursion of two funtions. Now I have to resort to someting
>> like tagbody to make it work. This looses much of the elegance of
>> the original algorithm.
>
> Why? Is someone forcing you to make your program work with every
> available Common Lisp implementation? Pick one that does tail call
> elimination given sufficient declarations and go with it.
But it would be nice to at least have a community-standard feature and
declaration where if the specific feature was present you'd know the
implementation did tail call elimination in at least the [INSERT SENSIBLE
MINIMAL SET HERE] situations if you did a declaration for it (rather than
having to just know that certain optimise settings trigger it in CMUCL,
say)
See old google thread linked from here:
http://www.cliki.net/Tail Recursion
David Golden <············@oceanfree.net> wrote in message news:<···················@news.indigo.ie>...
>
> But it would be nice to at least have a community-standard feature and
> declaration where if the specific feature was present you'd know the
> implementation did tail call elimination in at least the [INSERT SENSIBLE
> MINIMAL SET HERE] situations if you did a declaration for it (rather than
> having to just know that certain optimise settings trigger it in CMUCL,
> say)
I think the issue is that <SENSIBLE MINIMAL SET> is kind of
non-trivial to specify for CL. Of course, it's easy to argue for it
on usenet...
From: John Thingstad
Subject: Re: Was not making tail recursion elmination a mistake?
Date:
Message-ID: <opr9hf4up2pqzri1@mjolner.upc.no>
perhaps not. But this was the only feature that could not be implemented i
standard lisp.
I use winboard (or the unix equivalent) for graphics.
It seems a shame (particularly since I am writing a book on Lisp games)
to be limited by an implementation.
On Sat, 12 Jun 2004 14:07:26 +0200, Edi Weitz <···@agharta.de> wrote:
> On Sat, 12 Jun 2004 13:42:56 +0200, "John Thingstad"
> <··············@chello.no> wrote:
>
>> Perhaps I should elaborate. I am working on a chess algorithm that
>> will! run out of stack space if elimination is not done. It uses
>> mutual recursion of two funtions. Now I have to resort to someting
>> like tagbody to make it work. This looses much of the elegance of
>> the original algorithm.
>
> Why? Is someone forcing you to make your program work with every
> available Common Lisp implementation? Pick one that does tail call
> elimination given sufficient declarations and go with it.
--
Using M2, Opera's revolutionary e-mail client: http://www.opera.com/m2/
From: Rahul Jain
Subject: Re: Was not making tail recursion elmination a mistake?
Date:
Message-ID: <87hdtglip5.fsf@nyct.net>
"John Thingstad" <··············@chello.no> writes:
> perhaps not. But this was the only feature that could not be implemented
> i standard lisp.
> I use winboard (or the unix equivalent) for graphics.
> It seems a shame (particularly since I am writing a book on Lisp games)
> to be limited by an implementation.
Only if that implementation is limiting in the first place. :)
One could complain that using fortran is bad for a book because one
could use f2cl, which doesn't always get desirable performance.
--
Rahul Jain
·····@nyct.net
Professional Software Developer, Amateur Quantum Mechanicist
From: Rahul Jain
Subject: Re: Was not making tail recursion elmination a mistake?
Date:
Message-ID: <87llislitg.fsf@nyct.net>
"John Thingstad" <··············@chello.no> writes:
> Perhaps I should elaborate. I am working on a chess algorithm that
> will! run out of stack space if elimination is not done. It uses
> mutual recursion of two funtions. Now I have to resort to someting
> like tagbody to make it work. This looses much of the elegance of the
> original algorithm.
Why don't you use a mature compiler and tell it to optimize for speed
and against debugging?
--
Rahul Jain
·····@nyct.net
Professional Software Developer, Amateur Quantum Mechanicist
From: Joe Marshall
Subject: Re: Was not making tail recursion elmination a mistake?
Date:
Message-ID: <wu2cu8v5.fsf@comcast.net>
"John Thingstad" <··············@chello.no> writes:
> Perhaps I should elaborate. I am working on a chess algorithm that
> will! run out of stack space
> if elimination is not done. It uses mutual recursion of two
> funtions. Now I have to resort to
> someting like tagbody to make it work. This looses much of the
> elegance of the original algorithm.
I posted this before, but you might find this relevant.
In Allegro, if you (declare (optimize (speed 1))) you should get tail recursion.
Alternatively you can just turn it on like this:
(setq compiler:tail-call-self-merge-switch t)
(setq compiler:tail-call-non-self-merge-switch t)
In Lispworks, (declare (optimize (debug 2))) should do it.
Alternatively, this just turns it on unconditionally everywhere in
lispworks:
(setq compiler::*debug-do-tail-merge-policy* 'true
compiler::*eliminate-tail-recursion-policy* 'true)
(compiler::update-policy-switches)
--
~jrm
From: Marco Antoniotti
Subject: Re: Was not making tail recursion elmination a mistake?
Date:
Message-ID: <fBLyc.15$2i5.8688@typhoon.nyu.edu>
Different CL implementations treat tail-x-{elimination|merging}
differently. You can check your implementation about how it handles it.
Having said that, having some way in ANSI to control the use of the
trick would have been good.
Cheers
Marco
John Thingstad wrote:
> Perhaps I should elaborate. I am working on a chess algorithm that
> will! run out of stack space
> if elimination is not done. It uses mutual recursion of two funtions.
> Now I have to resort to
> someting like tagbody to make it work. This looses much of the elegance
> of the original algorithm.
>
> On Fri, 11 Jun 2004 18:49:29 +0200, John Thingstad
> <··············@chello.no> wrote:
>
>> I have recently been annoyeed by the fact that tail recursion
>> elimination is
>> not part of the standard. Any ansi compliant program can now not rely
>> on recurive tail
>> elimination and must use loops or some simular structue. For mutual
>> recurion things get even uglier.
>> Wouldn't it have been better to make a commentary on the
>> implementation and require it?
>> Most implementations do anyhow.
>> What is the historic reason for this omission?
>>
>
>
>
One good reason for not having tail-call optimizations in the standard
is the presence of subsets of CL. This makes writing and porting code
for implementations like Linj and ThinLisp, that translate into
languages that may not have tail-call optimizations, that much
easier. I do agree with David Golden that some mechanism for checking
for the presence of certain tail-call optimizations would be
desirable.
Vladimir
From: Rahul Jain
Subject: Re: Was not making tail recursion elmination a mistake?
Date:
Message-ID: <87llisjuud.fsf@nyct.net>
Vladimir Sedach <(string-downcase (concatenate 'string (subseq first-name 0 1) last-name))@cpsc.ucalgary.ca> writes:
> One good reason for not having tail-call optimizations in the standard
> is the presence of subsets of CL. This makes writing and porting code
> for implementations like Linj and ThinLisp, that translate into
> languages that may not have tail-call optimizations, that much
> easier. I do agree with David Golden that some mechanism for checking
> for the presence of certain tail-call optimizations would be
> desirable.
You'd have to define all possible nestings of dynamic contexts that
could occur in lisp code. And you may miss something that could
otherwise be implemented using a dynamic context.
What would you do if the optimization were missing? Switch to a
hopefully equivalent, portably efficient implementation of that code
instead? At that point, you might as well use that code as the only
implementation and save yourself headache.
If you just error out, that's about as logical as erroring out when
most-positive-fixnum isn't big enough to hold all the numbers your
program could use.
If someone wants the code to be fast and efficient, they'll use a
compiler and CPU and OS that allow the performance and space semantics
they desire. If they just want to code to run as best as it can and fail
at _run-time_ when the data becomes too large, then why should you
forbid them?
If you want bondage and discipline in your language, feel free to use
Java or Scheme. Lisp lets you code what you want the program to do and
worry about performance only as much as you actually care about it.
Sometimes your implementation can't give you the performance you desire.
If that's the case, (help) improve it or switch to a new one. There are
plenty of compilers that are good at optimizing.
--
Rahul Jain
·····@nyct.net
Professional Software Developer, Amateur Quantum Mechanicist