I'm trying to solve something akin to the following problem:
(defun test-fn ()
(handler-case
(random-fn)
(error (e)
(handler-fn))))
(defun random-fn ()
(loop as rand = (random 10)
do
(if (> rand 8)
(error "im too big ~d~%" rand)
(format t "no problem with me ~d~%" rand))))
(defun handler-fn ()
(format t "WHOOPS, found an error~%")
(test-fn))
Basically, I'd like to run test-fn, and every time random-fn returns
an error, I'd like to report the error and just restart from scratch
with test-fn. As written, these 3 functions very quickly return a
stack overflow, because we're just getting deeper and deeper into new
instances of test-fn. I'm obviously misusing the lisp conditional
system, but I'm a bit confused as to how to use it correctly. Any
help?
Thanks!
On Apr 30, 1:55 pm, Q <······@gmail.com> wrote:
> Basically, I'd like to run test-fn, and every time random-fn returns
> an error, I'd like to report the error and just restart from scratch
> with test-fn.
I.e. you'd benefit from learning about restarts.
On Apr 30, 9:55 pm, Q <······@gmail.com> wrote:
> I'm trying to solve something akin to the following problem:
>
> (defun test-fn ()
> (handler-case
> (random-fn)
> (error (e)
> (handler-fn))))
There are other ways, and this will horrify the wimps but:
(defun test-fn ()
(tagbody
try
(handler-case
(random-fn)
(error (e) (report-error) (go try)))))
is what you want. You can do this in lots of other ways as well. The
real issue is that you need to restart the call to the function from
inside the function, or by throwing out of it altogether and then
retrying - recursing into it is not safe.
Q <······@gmail.com> writes:
> I'm trying to solve something akin to the following problem:
>
> (defun test-fn ()
> (handler-case
> (random-fn)
> (error (e)
> (handler-fn))))
>
> (defun random-fn ()
> (loop as rand = (random 10)
> do
> (if (> rand 8)
> (error "im too big ~d~%" rand)
> (format t "no problem with me ~d~%" rand))))
>
> (defun handler-fn ()
> (format t "WHOOPS, found an error~%")
> (test-fn))
>
>
> Basically, I'd like to run test-fn, and every time random-fn returns
> an error, I'd like to report the error and just restart from scratch
> with test-fn. As written, these 3 functions very quickly return a
> stack overflow, because we're just getting deeper and deeper into new
> instances of test-fn. I'm obviously misusing the lisp conditional
> system, but I'm a bit confused as to how to use it correctly. Any
> help?
To a close approximation, stack is increased by calling functions and
decreased by returning from functions. When you call test-fn, it
sometimes calls handler-fn, increasing stack depth. But handler-fn
doesn't return. It calls test-fn, which you might think is a tail
call, but it's not. So you increase stack depth. test-fn doesn't
return. It calls random-fn, which either loops happily, or eventually
catches an error, in which case test-fn doesn't return, it calls
handler-fn. And the whole mess goes around and around.
This problem would happen with mutual recursion as well. Your problem
is not condition handling. It's tail calls. Nothing in CL encourages
you to assume recursion, even tail recursion, can be done without
increasing stack depth.
One reason for this, so you don't think it's an utter bug, is that
many errors are mysterious to debug if you don't have the ability to
look up the stack and see who called you. Languages that eliminate
tail calls do so as a conscious choice, opting to make some amount of
debugging harder. Also, it's complicated (not impossible, just
subtle) to spec exactly what constitutes a tail call--there are some
odd cases. Historically, it was not something Lisp had traditionally
done, so when we standardized Lisp, we didn't make all existing
implementation strategies illegal by standardizing on it.
While I am quite comfortable working in a language that hasn't got
this required, I'm sympathetic to the desire of implementations to
play with this. There are a number of ways in which we differ from
Scheme and other languages for "good principled reason" but this
particular one is somewhat more arbitrary and obviously in some cases
constraining to people.
There are many days on which I suspect we should have gone to more
trouble to allow declarational ways for users to say they wanted this.
The complexity of that was that it would have meant that such programs
would have not run in implementations that didn't support such
declarations. If memory serves (someone will undoubtedly correct me
if I'm wrong on this, but I haven't looked at the spec on this in
qutie some time), we already have that situation with SAFETY... we
allow implementations to not implement high SAFETY, and we allow
programs to request it, forcing some conforming programs to not be
accepted by some conforming implementations. That sort of compromise
would likely have worked with tail calls.
(I also don't know that much of anyone would object to an
implementation describing itself as being "mostly like CL but with
good support for tail calls" if someone wanted to try implementing it.
See another post I wrote in the last day or so about good labeling
being the most important thing. Conformance criteria are not about
keeping people from experimenting, they are just about how to properly
name the things you experiment with. People should know they are
playing with something that is not conforming, but that's not the same
as saying people should feel horrible guilt for straying.)
So, there's no simple way, if a function errors, to just unwind
everything and call the function again?
On Apr 30, 4:09 pm, Kent M Pitman <······@nhplace.com> wrote:
> Q <······@gmail.com> writes:
> > I'm trying to solve something akin to the following problem:
>
> > (defun test-fn ()
> > (handler-case
> > (random-fn)
> > (error (e)
> > (handler-fn))))
>
> > (defun random-fn ()
> > (loop as rand = (random 10)
> > do
> > (if (> rand 8)
> > (error "im too big ~d~%" rand)
> > (format t "no problem with me ~d~%" rand))))
>
> > (defun handler-fn ()
> > (format t "WHOOPS, found an error~%")
> > (test-fn))
>
> > Basically, I'd like to run test-fn, and every time random-fn returns
> > an error, I'd like to report the error and just restart from scratch
> > with test-fn. As written, these 3 functions very quickly return a
> > stack overflow, because we're just getting deeper and deeper into new
> > instances of test-fn. I'm obviously misusing the lisp conditional
> > system, but I'm a bit confused as to how to use it correctly. Any
> > help?
>
> To a close approximation, stack is increased by calling functions and
> decreased by returning from functions. When you call test-fn, it
> sometimes calls handler-fn, increasing stack depth. But handler-fn
> doesn't return. It calls test-fn, which you might think is a tail
> call, but it's not. So you increase stack depth. test-fn doesn't
> return. It calls random-fn, which either loops happily, or eventually
> catches an error, in which case test-fn doesn't return, it calls
> handler-fn. And the whole mess goes around and around.
>
> This problem would happen with mutual recursion as well. Your problem
> is not condition handling. It's tail calls. Nothing in CL encourages
> you to assume recursion, even tail recursion, can be done without
> increasing stack depth.
>
> One reason for this, so you don't think it's an utter bug, is that
> many errors are mysterious to debug if you don't have the ability to
> look up the stack and see who called you. Languages that eliminate
> tail calls do so as a conscious choice, opting to make some amount of
> debugging harder. Also, it's complicated (not impossible, just
> subtle) to spec exactly what constitutes a tail call--there are some
> odd cases. Historically, it was not something Lisp had traditionally
> done, so when we standardized Lisp, we didn't make all existing
> implementation strategies illegal by standardizing on it.
>
> While I am quite comfortable working in a language that hasn't got
> this required, I'm sympathetic to the desire of implementations to
> play with this. There are a number of ways in which we differ from
> Scheme and other languages for "good principled reason" but this
> particular one is somewhat more arbitrary and obviously in some cases
> constraining to people.
>
> There are many days on which I suspect we should have gone to more
> trouble to allow declarational ways for users to say they wanted this.
> The complexity of that was that it would have meant that such programs
> would have not run in implementations that didn't support such
> declarations. If memory serves (someone will undoubtedly correct me
> if I'm wrong on this, but I haven't looked at the spec on this in
> qutie some time), we already have that situation with SAFETY... we
> allow implementations to not implement high SAFETY, and we allow
> programs to request it, forcing some conforming programs to not be
> accepted by some conforming implementations. That sort of compromise
> would likely have worked with tail calls.
>
> (I also don't know that much of anyone would object to an
> implementation describing itself as being "mostly like CL but with
> good support for tail calls" if someone wanted to try implementing it.
> See another post I wrote in the last day or so about good labeling
> being the most important thing. Conformance criteria are not about
> keeping people from experimenting, they are just about how to properly
> name the things you experiment with. People should know they are
> playing with something that is not conforming, but that's not the same
> as saying people should feel horrible guilt for straying.)
Q wrote:
> So, there's no simple way, if a function errors, to just unwind
> everything and call the function again?
Sure, there's a few. You just can't recurse indefinitely. Here's a
simple example (assuming you just want to log the error and move on) :
(defun retry (thunk)
(loop
(handler-case
(return-from retry (funcall thunk))
(error (e)
(typecase e
(simple-condition
(apply 'warn
(simple-condition-format-control e)
(simple-condition-format-arguments e)))
(t (warn "Got an error : ~A" e)))))))
CL-USER> (retry 'random-fn)
no problem with me 3
no problem with me 4
no problem with me 0
no problem with me 2
WARNING: im too big 9
no problem with me 1
; Evaluation aborted
hth,
drewc
>
>
> On Apr 30, 4:09 pm, Kent M Pitman <······@nhplace.com> wrote:
>> Q <······@gmail.com> writes:
>>> I'm trying to solve something akin to the following problem:
>>> (defun test-fn ()
>>> (handler-case
>>> (random-fn)
>>> (error (e)
>>> (handler-fn))))
>>> (defun random-fn ()
>>> (loop as rand = (random 10)
>>> do
>>> (if (> rand 8)
>>> (error "im too big ~d~%" rand)
>>> (format t "no problem with me ~d~%" rand))))
>>> (defun handler-fn ()
>>> (format t "WHOOPS, found an error~%")
>>> (test-fn))
>>> Basically, I'd like to run test-fn, and every time random-fn returns
>>> an error, I'd like to report the error and just restart from scratch
>>> with test-fn. As written, these 3 functions very quickly return a
>>> stack overflow, because we're just getting deeper and deeper into new
>>> instances of test-fn. I'm obviously misusing the lisp conditional
>>> system, but I'm a bit confused as to how to use it correctly. Any
>>> help?
>> To a close approximation, stack is increased by calling functions and
>> decreased by returning from functions. When you call test-fn, it
>> sometimes calls handler-fn, increasing stack depth. But handler-fn
>> doesn't return. It calls test-fn, which you might think is a tail
>> call, but it's not. So you increase stack depth. test-fn doesn't
>> return. It calls random-fn, which either loops happily, or eventually
>> catches an error, in which case test-fn doesn't return, it calls
>> handler-fn. And the whole mess goes around and around.
>>
>> This problem would happen with mutual recursion as well. Your problem
>> is not condition handling. It's tail calls. Nothing in CL encourages
>> you to assume recursion, even tail recursion, can be done without
>> increasing stack depth.
>>
>> One reason for this, so you don't think it's an utter bug, is that
>> many errors are mysterious to debug if you don't have the ability to
>> look up the stack and see who called you. Languages that eliminate
>> tail calls do so as a conscious choice, opting to make some amount of
>> debugging harder. Also, it's complicated (not impossible, just
>> subtle) to spec exactly what constitutes a tail call--there are some
>> odd cases. Historically, it was not something Lisp had traditionally
>> done, so when we standardized Lisp, we didn't make all existing
>> implementation strategies illegal by standardizing on it.
>>
>> While I am quite comfortable working in a language that hasn't got
>> this required, I'm sympathetic to the desire of implementations to
>> play with this. There are a number of ways in which we differ from
>> Scheme and other languages for "good principled reason" but this
>> particular one is somewhat more arbitrary and obviously in some cases
>> constraining to people.
>>
>> There are many days on which I suspect we should have gone to more
>> trouble to allow declarational ways for users to say they wanted this.
>> The complexity of that was that it would have meant that such programs
>> would have not run in implementations that didn't support such
>> declarations. If memory serves (someone will undoubtedly correct me
>> if I'm wrong on this, but I haven't looked at the spec on this in
>> qutie some time), we already have that situation with SAFETY... we
>> allow implementations to not implement high SAFETY, and we allow
>> programs to request it, forcing some conforming programs to not be
>> accepted by some conforming implementations. That sort of compromise
>> would likely have worked with tail calls.
>>
>> (I also don't know that much of anyone would object to an
>> implementation describing itself as being "mostly like CL but with
>> good support for tail calls" if someone wanted to try implementing it.
>> See another post I wrote in the last day or so about good labeling
>> being the most important thing. Conformance criteria are not about
>> keeping people from experimenting, they are just about how to properly
>> name the things you experiment with. People should know they are
>> playing with something that is not conforming, but that's not the same
>> as saying people should feel horrible guilt for straying.)
>
>
--
Posted via a free Usenet account from http://www.teranews.com
Q <······@gmail.com> writes:
> So, there's no simple way, if a function errors, to just unwind
> everything and call the function again?
I didn't say that at all. There are many ways to do that. You just
didn't write any of them. I was explaining why your function did not
do what you wanted, not telling you how to do what you wanted. You
seemed not to understand that you had pushed stack each time, and I
considered fixing that confusion to be the first thing to fix.
Subsequent to my reply, there's another reply already (from Tim
Bradshaw) that explains one of several ways to do what you want. But,
IMO, you should not just pick up that and use it without also taking
the time to learn why what you did did not work.
I could be misreading, of course, but, to me, your program in the
original post suggests a basic misunderstanding of how things work.
As such, I think that merely leaping to a cookbook thing someone else
gives you won't fix that misunderstanding... I do recommend doing
something akin to what Tim suggests, but I also think you're likely to
have that same misunderstanding I think is exhibited in your original
post, even absent error handling, if you just expect the use of
recursion notation to have no stack consequences in CL.
Hope all this is helpful. Good luck to you.
On Apr 30, 11:49 pm, Kent M Pitman <······@nhplace.com> wrote:
>
> Subsequent to my reply, there's another reply already (from Tim
> Bradshaw) that explains one of several ways to do what you want. But,
> IMO, you should not just pick up that and use it without also taking
> the time to learn why what you did did not work.
I agree with this. In particular my solution gratuitously used GO, at
least partly to put you off the scent. There are better ways of doing
it than this: CL's condition system and its control constructs are
very powerful, and use of GO is not often needed (most of the times
I've used it have been in the expansion of macros).
I also agree with what I think is Kent's point about recursion. In
fact I think my view may be stronger than his: code which makes
extensive use of tail-calls to do what is actually iteration can be
approximately as hard to read as code which makes extensive use of GO
to do what is actually iteration, despite the hype (I have written
fairly significant amounts of such code, so am talking from first-hand
experience here). So I'm actually completely happy that CL does not
mandate tail-call optimisation.
--tim
Actually, I THINK I did understand why I was getting the stack
overflow due to infinite recursion as evidenced in my initial post:
"As written, these 3 functions very quickly return a
stack overflow, because we're just getting deeper and deeper into new
instances of test-fn. I'm obviously misusing the lisp conditional
system, but I'm a bit confused as to how to use it correctly."
test-fn never exits, it just calls another instance of test-fn. I
knew it was working that way, but I couldn't think of how to get it to
do what I wanted to do. If there's some further subtlety I'm missing,
I'd love to hear about it. On a relative basis, I'm still pretty new
to lisp.
On spending some time away from the problem, before I even came back
to see the posts, I was thinking, "I wonder if a (catch) in the
function and a (throw) in the handler would work here. Then your post
said to use (go). Is (go) a better idea than (throw) because of scope
issues, or are they both valid?
Thanks to all who replied. You guys are awesome.
On May 1, 3:47 am, Tim Bradshaw <··········@tfeb.org> wrote:
> On Apr 30, 11:49 pm, Kent M Pitman <······@nhplace.com> wrote:
>
>
>
> > Subsequent to my reply, there's another reply already (from Tim
> > Bradshaw) that explains one of several ways to do what you want. But,
> > IMO, you should not just pick up that and use it without also taking
> > the time to learn why what you did did not work.
>
> I agree with this. In particular my solution gratuitously used GO, at
> least partly to put you off the scent. There are better ways of doing
> it than this: CL's condition system and its control constructs are
> very powerful, and use of GO is not often needed (most of the times
> I've used it have been in the expansion of macros).
Q <······@gmail.com> writes:
> On spending some time away from the problem, before I even came back
> to see the posts, I was thinking, "I wonder if a (catch) in the
> function and a (throw) in the handler would work here. Then your post
> said to use (go). Is (go) a better idea than (throw) because of scope
> issues, or are they both valid?
Catch/throw, Block/return, and tagbody/Go all provide essentially
equivalent functionality. I'm nearly certain I could implement any of
these given only any of the others [plus other operators in the language
which don't do control transfer, but do other things essential to
binding environments if you want to paper over the dynamic/static difference
between block/return]. But, in general, you should assume that anything
that does non-local control [and that includes error restarts as well],
will suffice. So you're on the right track.
Incidentally, you can probably ALSO do this without non-local transfer
of control, you just have to return extra values to indicate the reason
for which you're returning. It's just easier with non-local transfer.
I strongly suggest you read my special forms paper:
http://www.nhplace.com/kent/Papers/Special-Forms.html
and my two conditions papers:
http://www.nhplace.com/kent/Papers/Exceptional-Situations-1990.html
http://www.nhplace.com/kent/Papers/Condition-Handling-2001.html
This will, among other things, save me from repeating a lot of things
you could learn there in pre-packaged form. :)
Good luck!
On 01 May 2007 11:02:39 -0400, Kent M Pitman <······@nhplace.com> wrote:
> Catch/throw, Block/return, and tagbody/Go all provide essentially
> equivalent functionality. I'm nearly certain I could implement any
> of these given only any of the others
http://home.pipeline.com/~hbaker1/MetaCircular.html
--
Lisp is not dead, it just smells funny.
Real email: (replace (subseq ·········@agharta.de" 5) "edi")
Tim Bradshaw <··········@tfeb.org> writes:
> I also agree with what I think is Kent's point about recursion. In
> fact I think my view may be stronger than his: code which makes
> extensive use of tail-calls to do what is actually iteration can be
> approximately as hard to read as code which makes extensive use of GO
> to do what is actually iteration,
And, in fact, in a language such as Scheme where tail calling is allowed,
you can trivially implement GO using letrec, in such a way that a supposed
"bad" program using GO can be turned into a supposed "good" program using
tail calls, without changing the fundamental shape of the program. This
suggests strongly to me that it's just so much dogma that GO is bad.
I actually had an exam question in college that asked:
Gotos are (a) good (b) bad.
It was at this point that my eyes opened and I realized I was studying
not Computer Science but Computer Religion. There's a lot more that's been
done in the field since then, but one of them is not to beat that confusion
out of the system. It still rears its ugly head on a routine basis.
Use of GO is a matter of aesthetic. And while the vendors/priests of
aethetics would often say there is only one True Way, the truth is
often that they're not being scientific. Rarely do they either
proceed from clear definitions, nor do controlled measurements. It
becomes more an issue of definition, and mere Definition (while it has
that "crisp" sound) is not Science either.
Personally, I think the GO usage you [Tim] used is just fine. I also
approve of GO for implementing finite state machines; yes, you can use
tail calls, but for reasons outlined above I don't see that it adds
anything. The use of GO seems to me more perspicuous, in the same sense
as I like to write #' in front of LAMBDA in CL... just as a visual cue,
not because it adds something functional.
On May 1, 7:57 am, Kent M Pitman <······@nhplace.com> wrote:
>
> And, in fact, in a language such as Scheme where tail calling is allowed,
> you can trivially implement GO using letrec, in such a way that a supposed
> "bad" program using GO can be turned into a supposed "good" program using
> tail calls, without changing the fundamental shape of the program. This
> suggests strongly to me that it's just so much dogma that GO is bad.
>
> I actually had an exam question in college that asked:
> Gotos are (a) good (b) bad.
> It was at this point that my eyes opened and I realized I was studying
> not Computer Science but Computer Religion. There's a lot more that's been
> done in the field since then, but one of them is not to beat that confusion
> out of the system. It still rears its ugly head on a routine basis.
The problem with goto is that it is too weak a construct: You can't
pass
arguments along with it, so you have to stick the arguments in some
shared location so the code at the destination can find them again.
Once
you add in the ability to pass arguments (with function calls), you
can
map all control transfer to GOTO.
Personally, I think GOTO (in its more powerful form) is one of the
best
concepts in computer science. The weak form where you just pass
control is a bit nasty, though.
Joe Marshall <··········@gmail.com> wrote:
+---------------
| The problem with goto is that it is too weak a construct: You can't
| pass arguments along with it, so you have to stick the arguments in some
| shared location so the code at the destination can find them again.
| Once you add in the ability to pass arguments (with function calls),
| you can map all control transfer to GOTO.
+---------------
Exactly this point was made by Steele & Sussman in a number of
the early "Lambda Papers" -- "Lambda: The Ultimate Imperative",
perhaps, or maybe "Debunking the 'Expensive Procedure Call'
Myth, or, Procedure Call Implementations Considered Harmful,
or, Lambda: The Ultimate GOTO", and certainly in "Compiler
Optimization Based on Viewing LAMBDA as RENAME + GOTO" -- in
which it was observed [that in a tail-call-optimizing environment]
that a [tail] procedure call is "just" a GOTO that binds its
arguments to variables at the destination [the target of the GOTO].
+---------------
| Personally, I think GOTO (in its more powerful form) is one
| of the best concepts in computer science.
+---------------
Heady stuff indeed.
+---------------
| The weak form where you just pass control is a bit nasty, though.
+---------------
(*Boo!*) (*Hiss!*) ;-}
-Rob
-----
Rob Warnock <····@rpw3.org>
627 26th Avenue <URL:http://rpw3.org/>
San Mateo, CA 94403 (650)572-2607
On May 1, 3:57 pm, Kent M Pitman <······@nhplace.com> wrote:
>
> And, in fact, in a language such as Scheme where tail calling is allowed,
> you can trivially implement GO using letrec, in such a way that a supposed
> "bad" program using GO can be turned into a supposed "good" program using
> tail calls, without changing the fundamental shape of the program. This
> suggests strongly to me that it's just so much dogma that GO is bad.
Well. I agree with this, but I disagree with it too, but (cue Little
Britain quote).
I suppose I really think[*] that crap programs are crap, and replacing
so-called bad constructs (GO) with so-called good ones (tail calls)
doesn't help very much. Tail calls are just GO with a little bit of
exra niceness in the way of argument passing, and that extra niceness
doesn't fix crap code.
I've had that exact experience (well, not starting with GO), where I
wrote some thing which made heavy use of local functions tail-calling
each other and the result was just incomprehensible spaghetti: even
though I could pass it off as this principled thing that was just
bullshit, and it needed a lot more than someone wearing the right kind
of robes to fix it.
The flip side of that is that sometimes there is stuff which is just
hard, and trying to make it not complicated is equally futile. When I
did physics (half my life ago now, sigh), there were bits of maths
which you had to do where you *just needed to look at it for a long
time* to work out what was going on, and there are bits (usually small
bits) of programs which are like that as well.
I suspect the trick is making the bits of programs which do hard stuff
be hard and the other bits easy.
> I actually had an exam question in college that asked:
> Gotos are (a) good (b) bad.
> It was at this point that my eyes opened and I realized I was studying
> not Computer Science but Computer Religion.
There is computer science? Science is what those people in Geneva do,
I think. What computer people do is either engineering, maths or
(mostly,and tragically) some kind of cult practice involving curious
and unpleasant body modifications and burying people from different
cults in pits.
--tim
[*] (not that anyone cares what I think other than possibly the cat,
and she only cares in so far as it concerns the state of the food
supply (never adequate) and whether the Rayburn is going to be left
on).
On May 2, 4:16 am, Tim Bradshaw <··········@tfeb.org> wrote:
>
> I suppose I really think[*] that crap programs are crap, and replacing
> so-called bad constructs (GO) with so-called good ones (tail calls)
> doesn't help very much. Tail calls are just GO with a little bit of
> exra niceness in the way of argument passing, and that extra niceness
> doesn't fix crap code.
True.
But the advantage of tail calls is that they are more general than
a plain GOTO. You can trivially emulate a GOTO by tail calls that
don't pass any arguments, but you have to come up with some
sort of ad-hoc convention for passing arguments if you want to
emulate tail-calls with GOTO. It is possible to create non-crap
programs with GOTO if you are disciplined and document things
well, but it is easier if you don't have to resort to workarounds.
Of course, if tail-calls make writing code easier, they probably
make writing crap easier as well.
Joe Marshall wrote:
> On May 2, 4:16 am, Tim Bradshaw <··········@tfeb.org> wrote:
>
>> I suppose I really think[*] that crap programs are crap, and replacing
>> so-called bad constructs (GO) with so-called good ones (tail calls)
>> doesn't help very much. Tail calls are just GO with a little bit of
>> exra niceness in the way of argument passing, and that extra niceness
>> doesn't fix crap code.
>
> True.
>
> But the advantage of tail calls is that they are more general than
> a plain GOTO. You can trivially emulate a GOTO by tail calls that
> don't pass any arguments, but you have to come up with some
> sort of ad-hoc convention for passing arguments if you want to
> emulate tail-calls with GOTO. It is possible to create non-crap
> programs with GOTO if you are disciplined and document things
> well, but it is easier if you don't have to resort to workarounds.
>
> Of course, if tail-calls make writing code easier, they probably
> make writing crap easier as well.
I am not convinced that GO doesn't have any advantages over tail calls.
One thing that's good about GO is that you can both have invocation of
GO and go tags in arbitrary places within a tagbody. So you can write
code like this:
(tagbody
:tag1 ...
(when foo (go :tag3))
... ;; fall
:tag2 ... ;; through
(unless bar (go :tag1))
...
:tag3 ...
(when baz (go :tag1)))
The following observations are interesting:
- Code "covered" by a label can just continue to execute into the next
part (see the part marked as "fall through").
- We can conditional jumps anywhere in the code. These jumps don't have
to be in tail position, but nevertheless don't grow the stack. (!) You
don't have to rearrange you code such that such jumps are in tail
position. (Whenever a language forces me to program in a certain style,
that's a bad idea because the language's preferred style may not suit my
needs.)
Of course, one could try to come up with some extension of such a GO
mechanism where the labels "receive" arguments and GO can pass arguments:
(tagbody
(tag :tag1 x y z) ...
...
:tag2 ...
(when foo (go :tag1 5 6 7))
...)
...but this raises the question what the scope of such tag parameters
are. I don't think that's easy to solve.
Pascal
--
My website: http://p-cos.net
Common Lisp Document Repository: http://cdr.eurolisp.org
Closer to MOP & ContextL: http://common-lisp.net/project/closer/
On May 2, 12:35 pm, Pascal Costanza <····@p-cos.net> wrote:
>
> One thing that's good about GO is that you can both have invocation of
> GO and go tags in arbitrary places within a tagbody.
>
> - We can conditional jumps anywhere in the code. These jumps don't have
> to be in tail position, but nevertheless don't grow the stack. (!)
Because you can place them *anywhere*, they can in fact shrink the
stack.
GO in Common Lisp isn't exactly the same as a goto in some other
languages.
> You
> don't have to rearrange you code such that such jumps are in tail
> position.
On the other hand, it is the caller that makes the distinction, not
the
callee. In other words, the target code might be invoked as a goto
or a gosub depending on the context of the caller.
> (Whenever a language forces me to program in a certain style,
> that's a bad idea because the language's preferred style may not suit my
> needs.)
Agreed.
On May 2, 9:35 pm, Pascal Costanza <····@p-cos.net> wrote:
> Of course, one could try to come up with some extension of such a GO
> mechanism where the labels "receive" arguments and GO can pass arguments:
>
> (tagbody
> (tag :tag1 x y z) ...
> ...
> :tag2 ...
> (when foo (go :tag1 5 6 7))
> ...)
>
> ...but this raises the question what the scope of such tag parameters
> are. I don't think that's easy to solve.
I think PROG does a nice job of addressing this. When implementing a
state machine like thing with prog, I'll often wrap it with a macrolet
that provides easy ways of advancing through the input, backing up,
whatever. These really just expand into calls to SETQ and utility
functions. Of course you could do this all with tail calls, but
especially if you have quite a few state variables, if your code only
mentions them when you explicitly modify them, it's a lower cognitive
burden than the functional approach (which a GO-with-arguments is just
a variation on).
And functional zealots can always write a PROG-replacement that
expands into a LABELS, so they can be sure their bodily fluids stay
pure. (Actually, I've seen SBCL produce better code for a PROG that
was machine-converted into a LABELS than for the PROG itself, so there
can be some value in ultimately expanding into the functional code,
regardless of the surface syntax).
Pascal Costanza <··@p-cos.net> wrote:
+---------------
| Joe Marshall wrote:
| > But the advantage of tail calls is that they are more general than
| > a plain GOTO. You can trivially emulate a GOTO by tail calls that
| > don't pass any arguments, but you have to come up with some
| > sort of ad-hoc convention for passing arguments if you want to
| > emulate tail-calls with GOTO. ...
|
| I am not convinced that GO doesn't have any advantages over tail calls.
| One thing that's good about GO is that you can both have invocation of
| GO and go tags in arbitrary places within a tagbody. So you can write
| code like this:
|
| (tagbody
| :tag1 ...
| (when foo (go :tag3))
| ... ;; fall
| :tag2 ... ;; through
| (unless bar (go :tag1))
| ...
| :tag3 ...
| (when baz (go :tag1)))
|
| The following observations are interesting:
|
| - Code "covered" by a label can just continue to execute
| into the next part (see the part marked as "fall through").
+---------------
You can do exactly the same thing with tail calls [at least in
those CLs providing them] by using LABELS instead of TAGBODY, though
you sometimes need to wrap the "GO"s in (RETURN-FROM here (there))
to convert them into true tail calls:
(labels (
(tag1 ()
...
(when foo (return-from tag1 (tag3)))
...
(tag2)) ; "fall through"
(tag2 ()
...
(unless bar (return-from tag2 (tag1)))
...
(tag3)) ; "fall through"
(tag3 ()
...
(unless bar (return-from tag2 (tag1)))
...
(when baz (tag1)))))
+---------------
| - We can conditional jumps anywhere in the code. These jumps don't
| have to be in tail position, but nevertheless don't grow the stack.(!
| You don't have to rearrange you code such that such jumps are in
| tail position.
+---------------
As demonstrated above, provided your LABELS routine don't do their
"jumps" from inside some binding form that *precludes* tail calls
[such as binding a dynamic variable or a CATCH or HANDLER-{CASE,BIND}
or UNWIND-PROTECT], you can turn any call into a tail-call by simply
wrapping it in (RETURN-FROM here (there)) -- no need to "rearrange"
your code more than that very-local amount.
+---------------
| Of course, one could try to come up with some extension of such a
| GO mechanism where the labels "receive" arguments and GO can pass
| arguments:
+---------------
As demonstrated above, CL already has such: LABELS.
-Rob
-----
Rob Warnock <····@rpw3.org>
627 26th Avenue <URL:http://rpw3.org/>
San Mateo, CA 94403 (650)572-2607
····@rpw3.org (Rob Warnock) writes:
> Pascal Costanza <··@p-cos.net> wrote:
> +---------------
> | Joe Marshall wrote:
> | > But the advantage of tail calls is that they are more general than
> | > a plain GOTO. You can trivially emulate a GOTO by tail calls that
> | > don't pass any arguments, but you have to come up with some
> | > sort of ad-hoc convention for passing arguments if you want to
> | > emulate tail-calls with GOTO. ...
> |
> | I am not convinced that GO doesn't have any advantages over tail calls.
> | One thing that's good about GO is that you can both have invocation of
> | GO and go tags in arbitrary places within a tagbody. So you can write
> | code like this:
> |
> | (tagbody
> | :tag1 ...
> | (when foo (go :tag3))
> | ... ;; fall
> | :tag2 ... ;; through
> | (unless bar (go :tag1))
> | ...
> | :tag3 ...
> | (when baz (go :tag1)))
> |
> | The following observations are interesting:
> |
> | - Code "covered" by a label can just continue to execute
> | into the next part (see the part marked as "fall through").
> +---------------
>
> You can do exactly the same thing with tail calls [at least in
> those CLs providing them] by using LABELS instead of TAGBODY, though
> you sometimes need to wrap the "GO"s in (RETURN-FROM here (there))
> to convert them into true tail calls:
>
> (labels (
> (tag1 ()
> ...
> (when foo (return-from tag1 (tag3)))
> ...
> (tag2)) ; "fall through"
> (tag2 ()
> ...
> (unless bar (return-from tag2 (tag1)))
> ...
> (tag3)) ; "fall through"
> (tag3 ()
> ...
> (unless bar (return-from tag2 (tag1)))
> ...
> (when baz (tag1)))))
And... drum roll please ... if you want it to be truly elegant, you
can use Scheme. (That _does_ automatically make everything elegant,
doesn't it? ... No slight on Scheme itself intended. It's an ok
language, just not my preferred language. What I tire of, though, is
the reverence paid to it by some, as if it holds a lock on aesthetics.
I think this example illustrates why I don't agree.)
I'll use the early syntax, which had labels and catch/throw rather
than letrec and call/cc. I've never liked call/cc. And I haven't
done this for a long time, nor used Scheme for any reason particularly
recently, so apologies in advance if I got this wrong--I'm sure some
helpful soul will chime in with corrections.
((catch go
(labels ((tag1 ()
...
(when foo (go tag3))
...
(go tag2))
(tag2 ()
...
(unless bar (go tag1))
...
(tag3))
(tag3 ()
...
(when baz (go tag1))))
(go tag1))))
So we're back where Pascal started in his code at the top.
Whether I got the syntax exactly right or not, I think this is close
enough to make my point, which is that it's not the choice of GO
that makes it ugly, nor the choice of Scheme that makes it pretty.
Since ANY program involving GO can be just about transliterated this
way, you have to either say that all programs with GO are elegant
or else admit that the whole notion of judging goodness based on the
presence of, rather than the style of use of, a given operator is
silly.
> As demonstrated above, provided your LABELS routine don't do their
> "jumps" from inside some binding form that *precludes* tail calls
> [such as binding a dynamic variable or a CATCH or HANDLER-{CASE,BIND}
> or UNWIND-PROTECT], you can turn any call into a tail-call by simply
> wrapping it in (RETURN-FROM here (there)) -- no need to "rearrange"
> your code more than that very-local amount.
And that's the irony of my approach. The only thing it makes easier
is hiding what you're really doing. All of this hair is hidden in the
((catch ...)), which is a remarkably subtle construct in Scheme. It
doesn't suit my personal taste to have such an important program
aspect be nearly invisible. If one had CL's syntax and Scheme's
capability, it would be written (funcall (catch ...)) and at least
people would more readily get the joke. But even then, you have to
know it's Scheme's catch, which can return more than once, so it
functions not just as a funcall but also as a provisional loop... Too
much clever, too little perspicuity for my taste.
As something to be thought-provokingly concise, it's got a certain
grace. But as an example of good programming style that I would
recommend anyone ever repeat, I'm afraid I can't endorse anyone
repeating the style except as low-level implementational boilerplate,
just the same way as I might endorse pretty much any implementation of
TAGBODY and GO in order to support code already written in that style.
If you were going to use these things on a regular basis, I think
having a well-known macro [at least for the TAGBODY part] is visually
clearer and therefore better.
Btw, as an aside, I think the whole biz of using LABELS this way is
due to Steele (or maybe Sussman, but for some reason I think it was
Steele). Jonathan Rees was the one who taught me the above technique,
and I think he said he'd embellished what Steele had done. It might
be Rees who added the ((catch ...)) cleverness. But in any case, it
as all a couple of decades ago, so I might be misremembering--I mostly
just wanted to cite a source so someone didn't think I was claiming
this as my own creation.
Rob Warnock wrote:
> Pascal Costanza <··@p-cos.net> wrote:
> +---------------
> | Joe Marshall wrote:
> | > But the advantage of tail calls is that they are more general than
> | > a plain GOTO. You can trivially emulate a GOTO by tail calls that
> | > don't pass any arguments, but you have to come up with some
> | > sort of ad-hoc convention for passing arguments if you want to
> | > emulate tail-calls with GOTO. ...
> |
> | I am not convinced that GO doesn't have any advantages over tail calls.
> | One thing that's good about GO is that you can both have invocation of
> | GO and go tags in arbitrary places within a tagbody. So you can write
> | code like this:
> |
> | (tagbody
> | :tag1 ...
> | (when foo (go :tag3))
> | ... ;; fall
> | :tag2 ... ;; through
> | (unless bar (go :tag1))
> | ...
> | :tag3 ...
> | (when baz (go :tag1)))
> |
> | The following observations are interesting:
> |
> | - Code "covered" by a label can just continue to execute
> | into the next part (see the part marked as "fall through").
> +---------------
>
> You can do exactly the same thing with tail calls [at least in
> those CLs providing them] by using LABELS instead of TAGBODY, though
> you sometimes need to wrap the "GO"s in (RETURN-FROM here (there))
> to convert them into true tail calls:
>
> (labels (
> (tag1 ()
> ...
> (when foo (return-from tag1 (tag3)))
> ...
> (tag2)) ; "fall through"
> (tag2 ()
> ...
> (unless bar (return-from tag2 (tag1)))
> ...
> (tag3)) ; "fall through"
> (tag3 ()
> ...
> (unless bar (return-from tag2 (tag1)))
> ...
> (when baz (tag1)))))
>
> +---------------
> | - We can conditional jumps anywhere in the code. These jumps don't
> | have to be in tail position, but nevertheless don't grow the stack.(!
> | You don't have to rearrange you code such that such jumps are in
> | tail position.
> +---------------
>
> As demonstrated above, provided your LABELS routine don't do their
> "jumps" from inside some binding form that *precludes* tail calls
> [such as binding a dynamic variable or a CATCH or HANDLER-{CASE,BIND}
> or UNWIND-PROTECT], you can turn any call into a tail-call by simply
> wrapping it in (RETURN-FROM here (there)) -- no need to "rearrange"
> your code more than that very-local amount.
I think that's the part that Kent has just commented on.
> +---------------
> | Of course, one could try to come up with some extension of such a
> | GO mechanism where the labels "receive" arguments and GO can pass
> | arguments:
> +---------------
>
> As demonstrated above, CL already has such: LABELS.
Not quite: I would expect the scope of variables introduced at a go tag
to extend to the rest of the tagbody, not just to the next go tag. In
your version of the code, the scope ends in each local function.
Thanks for the illustration anyway, that was interesting.
Pascal
--
My website: http://p-cos.net
Common Lisp Document Repository: http://cdr.eurolisp.org
Closer to MOP & ContextL: http://common-lisp.net/project/closer/
Kent M Pitman wrote:
> I actually had an exam question in college that asked:
> Gotos are (a) good (b) bad.
> It was at this point that my eyes opened and I realized I was studying
> not Computer Science but Computer Religion. There's a lot more that's been
> done in the field since then, but one of them is not to beat that confusion
> out of the system. It still rears its ugly head on a routine basis.
I add my name to the roll of those taught In School that goto is (b)
bad. I've never read the entire essay, but I love the following from
the preface of Knuth's "Structured Programming with Goto Statements."
I'm sure that many have already read this essay and probably know it
better than I do but Kent's above statements just reminded me of it.
(I'm cutting and pasting from a multi-column PDF, so I had to do some
editing. Any errors are mine.)
| Before beginning a more technical discussion. I should confess that
| the title of this article was chosen primarily to generate
| attention. There are doubtless some readers who are convinced that
| abolition of go to statements is merely a fad and they may see this
| title and think, "Aha! Knuth is rehabilitating the goto statement,
| and we can go back to our old ways of programming again." Another
| class of readers will see the heretical title and think, "When are
| die-hards like Knuth going to get with it?" I hope that both classes
| of people will read on and discover that what I am really doing is
| striving for a reasonably well balanced viewpoint about the proper
| role of goto statements. I argue for the elimination of goto's in
| certain cases, and for their introduction in others.
|
| I believe that by presenting such a view I am not in fact disagreeing
| sharply with Dijkstra's ideas, since he recently wrote the following:
| "Please don't fall into the trap of believing that I am terribly
| dogmatical about [the goto statement]. I have the uncomfortable
| feeling that others are making a religion out of it, as if the
| conceptual problems of programming could be solved by a single trick,
| by a simple form of coding discipline!" [29]. In other words, it,
| seems that fanatical advocates of the New Programming are going
| overboard in their strict enforcement of morality and purity in
| programs. Sooner or later people are going to find that their
| beautifully-structured programs are running at only half the speed--or
| worse--of the dirty old programs they used to write, and they will
| mistakenly blame the structure instead of recognizing what is probably
| the real culprit--the system overhead caused by typical compiler
| implementation of Boolean variables and procedure calls. Then we'll
| have an unfortunate counter-revolution, something like the current
| rejection of the "New Mathematics" in reaction to its over-zealous
| reforms.
I realize that the state of the "typical compiler implementation" has
probably changed quite a bit from when Knuth wrote this in 1974 but I
really like the way he seems to keep both of the issues of aesthetics
and practicalities in mind at the same time. I think the executive
summary is almost beautifully succinct:
The discussion brings out opposing points of view about whether or not
goto statements should be abolished; some merit is found on both sides
of this question.
Q wrote:
> (defun random-fn ()
> (loop as rand = (random 10)
Why do you have a nonterminating loop here?
Combined with the call to test-fn, you're
continuing no matter what, which you can do
with a simple loop around handler-case.
--
Dan
www.prairienet.org/~dsb/
(message (Hello 'Q)
(you :wrote :on '(30 Apr 2007 13:55:25 -0700))
(
Q> Basically, I'd like to run test-fn, and every time random-fn returns
Q> an error, I'd like to report the error and just restart from scratch
Q> with test-fn.
you've already got few replies, but they haven't yet demonstrated restarts
yet. here's a code using restarts:
;;random-fn as before
(defun random-fn ()
(loop
as rand = (random 10)
do
(if (> rand 8)
(error "im too big ~d~%" rand)
(format t "no problem with me ~d~%" rand))))
if you'll run it, you'll get an error in REPL with only option to abort.
we'd like to be able to restart this computation. with-simple-restart macro
will do this. we can wrap it in a function (or a macro):
(defun call-retryable (fun)
(loop
(with-simple-restart (retry "Retry")
(return-from call-retryable (funcall fun)))))
you can see here, that when function completes, it will escape, but if it
signals error, and restart RETRY is invoked, it will be restarted as many
times as needed. you can run in REPL:
(call-retryable #'random-fn)
now you can see that you have an option RETRY in debugger, and if you hit
it, it will indeed restart random-fn. you can also ABORT it.
but it's no fun restarting manually in repl, can we make it restartable
automatically? sure we can:
(defun retry-always (fun)
(handler-bind ((error #'(lambda (c)
(format *error-output* "~&~A~&" c)
(invoke-restart 'retry))))
(funcall fun)))
now you can run it in repl:
(retry-always (lambda () (call-retryable #'random-fn)))
and see that it automatically restarts random-fn (now without blowing
stack).
certainly, if you need only a simple case, you can do it with simple THROW
or GO, without using condition system at all.
you need a condition system when you need to separate error handling policy
from error itself. in this example, you can see that function that can
signal errors, policy making that function retryable and error handling
policy are totally separated. you can add abort restart and make error
handling policy a bit more complex -- for example, restart first 3 times,
and then abort. you can also control error logging policy etc. and you can
do this changes without changing original random-fn function. it's very
flexible.
)
(With-best-regards '(Alex Mizrahi) :aka 'killer_storm)
"I am everything you want and I am everything you need")
From: Jock Cooper
Subject: Re: new to the condition system
Date:
Message-ID: <87y7k8fj6a.fsf@mail.com>
"Alex Mizrahi" <········@users.sourceforge.net> writes:
> (message (Hello 'Q)
> (you :wrote :on '(30 Apr 2007 13:55:25 -0700))
> (
>
> Q> Basically, I'd like to run test-fn, and every time random-fn returns
> Q> an error, I'd like to report the error and just restart from scratch
> Q> with test-fn.
>
> you've already got few replies, but they haven't yet demonstrated restarts
> yet. here's a code using restarts:
>
>[snip]
Here's another example of code using restarts and condition:
(define-condition rand-too-big (simple-error)
((value :initarg :value))
(:report (lambda (cond stream)
(with-slots (value) cond
(format stream "im too big ~a" value)))))
(defun test-fn ()
(loop with continue = t
while continue
do
(restart-case
(handler-bind ((rand-too-big #'(lambda (cond)
(format t "error, continuing~%")
(princ cond)
(terpri)
(invoke-restart 'continue)))
(error #'(lambda (cond)
(format t "error, exiting~%")
(princ cond)
(terpri)
(invoke-restart 'exit)
)))
(random-fn))
(continue ())
(exit () (setq continue nil))
)))
(defun random-fn ()
(loop as rand = (random 10)
do
(if (> rand 8)
(error 'rand-too-big :value rand)
(format t "no problem with me ~d~%" rand))
; occasionally gen a different error
(/ 10 rand)))