Hi,
First, sorry for the terminology that I made up in the subject line :).
I wonder if there is a straightforward and clean syntax to do the
following:
Assume I have a symbol, say "var1", which holds "var2", which holds
"var3", and so on, up until "varN". But, varN holds some value, not yet
another symbol. I there a form (function, operator, whatever) that I
call on "var1" and get the value at a given nesting level, say 3rd,
10th, and final level that holds a non-symbol value?
If not, what's the best way to do this in a flexible way?
Thank you for any advice in advance.
Regards.
new_to_lisp wrote:
> Hi,
> First, sorry for the terminology that I made up in the subject line :).
> I wonder if there is a straightforward and clean syntax to do the
> following:
>
> Assume I have a symbol, say "var1", which holds "var2", which holds
> "var3", and so on, up until "varN". But, varN holds some value, not yet
> another symbol. I there a form (function, operator, whatever) that I
> call on "var1" and get the value at a given nesting level, say 3rd,
> 10th, and final level that holds a non-symbol value?
>
> If not, what's the best way to do this in a flexible way?
Hope this helps:
Welcome to OpenMCL Version 1.0 (DarwinPPC32)!
? (defvar *foo* '*bar*)
*FOO*
? (defvar *bar* '*baz*)
*BAR*
? (defvar *baz* '*qux*)
*BAZ*
? (defvar *qux* 7)
*QUX*
? (symbol-value '*foo*)
*BAR*
? (symbol-value (symbol-value '*foo*))
*BAZ*
? (defun nth-symbol-value (n sym)
(if (= n 1)
(symbol-value sym)
(nth-symbol-value (1- n) (symbol-value sym))))
NTH-SYMBOL-VALUE
? (nth-symbol-value 1 '*foo*)
*BAR*
? (nth-symbol-value 4 '*foo*)
7
? (defun terminal-value (sym)
(let ((result (symbol-value sym)))
(if (symbolp result)
(terminal-value result)
result)))
TERMINAL-VALUE
? (terminal-value '*foo*)
7
Note that symbol-value doesn't work on lexical variables because
lexical variables names may have been optimized away before evaluation.
Justin Dubs
Sorry for replying to my own message, but just wanted to clarify: We
may not necessarily know how deep the nesting is. If so, is there an
automatic way to get the bottom of the stack, i.e. last non-symbol
value by a single form?
Again, probably ther is no cooked and packed way to achieve this. In
that case, what would be the most reasonable way to do this? Only thing
I can think of:
a) either there is an operator or form at least to get a specific
nesting level (like C pointer dereferencing)
or
b) looping
"new_to_lisp" <········@yahoo.com> writes:
> Sorry for replying to my own message, but just wanted to clarify: We
> may not necessarily know how deep the nesting is. If so, is there an
> automatic way to get the bottom of the stack, i.e. last non-symbol
> value by a single form?
>
> Again, probably ther is no cooked and packed way to achieve this. In
> that case, what would be the most reasonable way to do this? Only thing
> I can think of:
> a) either there is an operator or form at least to get a specific
> nesting level (like C pointer dereferencing)
> or
> b) looping
Here is the basic algorithm:
(defun deref (symbol)
(if (symbolp (symbol-value symbol))
(deref(symbol-value symbol))
(symbol-value symbol)))
But perhaps you'll want to check for cycles:
(defun deref (symbol)
(let ((seen (make-hash-table)))
(labels ((deref-loop (symbol)
(cond ((not (symbolp (symbol-value symbol)))
(symbol-value symbol))
((gethash (symbol-value symbol) seen)
(error "DEREF cycle"))
(t
(setf (gethash (symbol-value symbol) seen) t)
(deref-loop (symbol-value symbol))))))
(deref-loop symbol))))
[226]> (setf a 'b b 'c c 'd d '7)
A
[227]> (deref 'a)
7
[228]> (setf a 'b b 'c c 'd d 'a)
A
[229]> (deref 'a)
*** - DEREF cycle
--
__Pascal Bourguignon__ http://www.informatimago.com/
PLEASE NOTE: Some quantum physics theories suggest that when the
consumer is not directly observing this product, it may cease to
exist or will exist only in a vague and undetermined state.
> Assume I have a symbol, say "var1", which holds "var2", which holds
> "var3", and so on, up until "varN". But, varN holds some value, not yet
> another symbol. I there a form (function, operator, whatever) that I
> call on "var1" and get the value at a given nesting level, say 3rd,
> 10th, and final level that holds a non-symbol value?
Assuming var1, var2, etc are global variables (otherwise I don't have a
solution), you may find symbol-value to be useful. Search for it on
this page: http://www.lisp.org/HyperSpec/Body/syscla_symbol.html
Here are some queries and the result of each (query --> result)
'var1 --> var1
var1 --> var2
'var2 --> var2
var2 --> var3
(symbol-value var1) --> var3
(symbol-value 'var2) --> var3
symbol-value only gets you one level deeper, but you could of course
use it repeatedly:
(symbol-value (symbol-value 'var1)) --> var3
which leads to an idea for a recursive solution...
(defun deep-symbol-value (symbol &optional (depth 1))
(cond
((eql depth 0) symbol)
(t (deep-symbol-value (symbol-value symbol) (- depth 1)))))
I didn't compile this, and I matched parentheses by hand, so mistakes
are likely.
I am curious what sort of problem required a function like this. Or
maybe you just want to explore strange corners of Lisp?
<quote>
I am curious what sort of problem required a function like this. Or
maybe you just want to explore strange corners of Lisp?
</quote>
The last one. Kidding :). Just want to explore possibilities: it may be
of use, but I don't have a case as yet.
new_to_lisp wrote:
> The last one. Kidding :). Just want to explore possibilities: it may be
> of use, but I don't have a case as yet.
I don't think that it is useful, but you can do it like this:
> (defparameter *v1* '*v2*)
*V1*
> (defparameter *v2* '*v3*)
*V2*
> (defparameter *v3* '*v4*)
*V3*
> (defparameter *v4* 123)
*V4*
> (loop for v = *v1* then (symbol-value v) unless (symbolp v) return v)
123
--
Frank Buss, ··@frank-buss.de
http://www.frank-buss.de, http://www.it4-systems.de
<quote>I don't think that it is useful, but you can do it like this:
</quote>
Well, don't be too sure :). Just a simple thought, for example: one can
generate non-self-intersecting paths or partitioning sequences without
any extra lists or vectors for example. Of ourse you don't have to do
anything in any specific way, but just an idea...
"new_to_lisp" <········@yahoo.com> writes:
> Assume I have a symbol, say "var1", which holds "var2", which holds
> "var3", and so on, up until "varN". But, varN holds some value, not
> yet another symbol. I there a form (function, operator, whatever)
> that I call on "var1" and get the value at a given nesting level,
> say 3rd, 10th, and final level that holds a non-symbol value?
Don't succumb to the recursion madness! ;-)
(defun nth-symref (s n)
(loop repeat n do (setf s (symbol-value s)))
s)
or:
(defun repeated-symref (x)
(loop while (symbolp x) do (setf x (symbol-value x))
x))
--
Frode Vatvedt Fjeld
<quote>Don't succumb to the recursion madness! ;-) </quote>
Don't like recursion :)? I'm especially sold on the idea of "tail
recursion", it's a fascinating technique! Reminds me of the "principle
of inertia" in mechanics, i.e. it's natural, too :).
"new_to_lisp" <········@yahoo.com> writes:
> Don't like recursion :)? I'm especially sold on the idea of "tail
> recursion", it's a fascinating technique! Reminds me of the
> "principle of inertia" in mechanics, i.e. it's natural, too :).
Like so many things, it's fascinating and well worth learning and
understanding, then to be used with discretion. In CS, similar topics
are "Object Orientation", "Functional Programming", etc. When _not_ to
use it is essential.
--
Frode Vatvedt Fjeld
<quote>
Like so many things, it's fascinating and well worth learning and
understanding, then to be used with discretion. In CS, similar topics
are "Object Orientation", "Functional Programming", etc. When _not_ to
use it is essential.
</quote>
Agreed, everything in moderation :). As I am not a CS by profession,
I can say that it's not about hype, though: I just liked it :).
Regards.
Frode Vatvedt Fjeld <······@cs.uit.no> writes:
> "new_to_lisp" <········@yahoo.com> writes:
>
>> Don't like recursion :)? I'm especially sold on the idea of "tail
>> recursion", it's a fascinating technique! Reminds me of the
>> "principle of inertia" in mechanics, i.e. it's natural, too :).
>
> Like so many things, it's fascinating and well worth learning and
> understanding, then to be used with discretion. In CS, similar topics
> are "Object Orientation", "Functional Programming", etc. When _not_ to
> use it is essential.
Absolutely! Actually, I most often find first a recursive solution.
Consider it RAD prototype :-) Then if need be, (and considering
Common Lisp doesn't require TCO), optimize it out to a LOOP. But
only if it's needed! Perhaps I should write a TC -> LOOP macro...
--
__Pascal Bourguignon__ http://www.informatimago.com/
"Klingon function calls do not have "parameters" -- they have
"arguments" and they ALWAYS WIN THEM."
<quote>(and considering Common Lisp doesn't require TCO)</quote>
Is there a reason for a compiler not to implement TCO? I mean, is there
a side effect? Even so, a better solution would be to make available a
compiler directive or sorts rather than giving up on it.
<rant>
I personally like C very much, for example, but I'm also so clueless
why on earth they didn't introduce "restrict" keyword until C99: it may
be dangerous in wrong hands, but quite useful for numerical
optimization used cautiously.
</rant>
"new_to_lisp" <········@yahoo.com> writes:
> <quote>(and considering Common Lisp doesn't require TCO)</quote>
>
> Is there a reason for a compiler not to implement TCO? I mean, is there
> a side effect? Even so, a better solution would be to make available a
> compiler directive or sorts rather than giving up on it.
Well, the only reason I can see, is if you implement Common Lisp
(remember, a Common Lisp impementation must have CL:COMPILE) on a
washmashine^W GSM phone or some other memory deprived device. You can
easily save 1KB or two if you don't implement TCO I guess.
Ah, now I see another reason: it could be hard to implement it in an
interpreter, or with (optimize (debug 3)).
> <rant>
> I personally like C very much, for example, but I'm also so clueless
> why on earth they didn't introduce "restrict" keyword until C99: it may
> be dangerous in wrong hands, but quite useful for numerical
> optimization used cautiously.
> </rant>
--
__Pascal Bourguignon__ http://www.informatimago.com/
"Klingon function calls do not have "parameters" -- they have
"arguments" and they ALWAYS WIN THEM."
<quote>
Well, the only reason I can see, is if you implement Common Lisp
(remember, a Common Lisp impementation must have CL:COMPILE) on a
washmashine^W GSM phone or some other memory deprived device. You can
easily save 1KB or two if you don't implement TCO I guess.
</quote>
I don't know what CL:COMPILE is ;-).
"new_to_lisp" <········@yahoo.com> writes:
> Is there a reason for a compiler not to implement TCO?
I think that changing the semantics of a form based on it's position
in a function is antithetical to good programming language
design. Also, I believe TCO is ill-specified or counter-intuitive when
one introduces e.g. dynamically-scoped mechanisms such as dynamic
bindings, unwind-protect, etc.
--
Frode Vatvedt Fjeld
<quote>
I think that changing the semantics of a form based on it's position
in a function is antithetical to good programming language
design.
</quote>
I'm certainly not an expert on anything you mention. I agree in
principle with
your assessment. However, I tend to think that as long as we have to
live with
physical restrictions of CPU architectures available, there is no
escape route: on the other hand TCO seems to be a reasonably good thing
to do. Probably as long as
we have have a "stack", with such design decisions and trciks we are
stuck.
<quote>
I believe TCO is ill-specified or counter-intuitive when
one introduces e.g. dynamically-scoped mechanisms such as dynamic
bindings, unwind-protect, etc.
</quote>
I'll take a note of this, and think about it later. My current
knowledge is not enough to speculate about this. You may be right, I
don't know. Would you mind to clarify a little in the context of
dynamic binding though? I'll certainly bring this up in the future to
get your advice. As Lisp is the first language I've ever seen with
dynamic binding, I need more explanation. (I don't know yet about
unwind-protect).
"new_to_lisp" <········@yahoo.com> writes:
> <quote>
> I think that changing the semantics of a form based on it's position
> in a function is antithetical to good programming language
> design.
> </quote>
>
> I'm certainly not an expert on anything you mention. I agree in
> principle with your assessment. However, I tend to think that as
> long as we have to live with physical restrictions of CPU
> architectures available, there is no escape route: on the other hand
> TCO seems to be a reasonably good thing to do. Probably as long as
> we have have a "stack", with such design decisions and trciks we are
> stuck.
I don't see that there's any requirement anywhere that implies that
TCO is necessary. What are the boundaries that you need to escape
from?
BTW: Can I suggest that you adopt a more conventional style of quoting?
--
Frode Vatvedt Fjeld
<quote>
>>>BTW: Can I suggest that you adopt a more conventional style of quoting?
</quote>
Sorry for doing the same way, but like what? I use Google web
interface, and this seems the easiest way to me.
Do you mean >>>-thing?
<quote>
I don't see that there's any requirement anywhere that implies that
TCO is necessary. What are the boundaries that you need to escape
from?
</quote>
I've carefully read the page I linked above. Now, I agree with your
assessment about the article. Even worse, I've been trapped by the same
reasoning: you can write programs that may use unbounded stack space
:-). But I think, I would never use tail recursion with procedures that
modify dynamic globals. I always thought in the context of lexical
variables (as I've never seen dynamic binding before).
<quote> (from your next email)
To me this seems like sacrificing a lot of the
regularity and predictability that is very important in programming
language design on the altar of something of questionable real value.
</quote>
I agree after reading that webpage carefully, it doesn't offer anything
of practical value IMHO, too.
Regards.
> Sorry for doing the same way, but like what? I use Google web
> interface, and this seems the easiest way to me.
> Do you mean >>>-thing?
>
I also use Google Groups. Try clicking on "show options", then "reply".
You get a different result than if you click on "reply" at the bottom
of the post.
Thank you ;-).
Eric Lavigne wrote:
> > Sorry for doing the same way, but like what? I use Google web
> > interface, and this seems the easiest way to me.
> > Do you mean >>>-thing?
> >
>
> I also use Google Groups. Try clicking on "show options", then "reply".
> You get a different result than if you click on "reply" at the bottom
> of the post.
"new_to_lisp" <········@yahoo.com> writes:
> Thank you ;-).
Next up you can expect someone to tell you that you should avoid "top posting."
-Peter
> Eric Lavigne wrote:
>> > Sorry for doing the same way, but like what? I use Google web
>> > interface, and this seems the easiest way to me.
>> > Do you mean >>>-thing?
>> >
>>
>> I also use Google Groups. Try clicking on "show options", then "reply".
>> You get a different result than if you click on "reply" at the bottom
>> of the post.
>
--
Peter Seibel * ·····@gigamonkeys.com
Gigamonkeys Consulting * http://www.gigamonkeys.com/
Practical Common Lisp * http://www.gigamonkeys.com/book/
Peter Seibel wrote:
> "new_to_lisp" <········@yahoo.com> writes:
>
> > Thank you ;-).
>
> Next up you can expect someone to tell you that you should avoid "top posting."
>
> -Peter
You already did ;-). Anything to add about the subject?
Frode,
About dynamic tail recursion, I searched the web and found the
following:
http://www.accesscom.com/~darius/writings/dynatail.html
Maybe you've already seen this, but just in case.
It seems to be an interesting reading.
Regards.
"new_to_lisp" <········@yahoo.com> writes:
> http://www.accesscom.com/~darius/writings/dynatail.html
>
> Maybe you've already seen this, but just in case. It seems to be an
> interesting reading.
It seems to me that what it says is that you can make TCO work in the
presence of dynamic bindings if you change the semantics of dynamic
bindings. The same is probably true of all other mechanisms that don't
mesh to well with TCO: they can be changed in subtle ways so as to
make it "work". To me this seems like sacrificing a lot of the
regularity and predictability that is very important in programming
language design on the altar of something of questionable real value.
It also says that TCO is the Right Thing because it's possible to
write programs that uses unbounded amounts of stack without TCO. A
very silly argument, IMHO.
--
Frode Vatvedt Fjeld
Frode Vatvedt Fjeld wrote:
> "new_to_lisp" <········@yahoo.com> writes:
>
> > Is there a reason for a compiler not to implement TCO?
>
> I think that changing the semantics of a form based on it's position
> in a function is antithetical to good programming language
> design.
There is no *observable* change in semantics. Any program that runs to
completion and produces an answer in a non-tail-recursive
implementation will run to completion and produce the exact same answer
in a tail-recursive implementation. Alternatively, any program that
runs to completion and produces an answer in a tail-recursive
implementation will also run to completion and produce the exact same
answer in a non-tail recursive implementation provided it has
sufficient stack space.
Frode Vatvedt Fjeld wrote:
> > I think that changing the semantics of a form based on it's position
> > in a function is antithetical to good programming language
> > design.
"Joe Marshall" <··········@gmail.com> writes:
> There is no *observable* change in semantics. Any program that runs
> to completion and produces an answer in a non-tail-recursive
> implementation will run to completion and produce the exact same
> answer in a tail-recursive implementation. Alternatively, any
> program that runs to completion and produces an answer in a
> tail-recursive implementation will also run to completion and
> produce the exact same answer in a non-tail recursive implementation
> provided it has sufficient stack space.
Well sure, but what if, for the sake of argument and real-world
applicability, we take "semantics" to include "whether one can assume
that there is enough stack-space for reasonably-sized inputs"?
--
Frode Vatvedt Fjeld
I'd better not interfere with experts :-), but if the only problem is
"whether one can assume that there is enough stack-space for
reasonably-sized inputs", I'd go with TCO and a compiler that supports
it. But then, I'm now really confused: what's all the fuss is about?
Really sorry for the lame question, but, what's the main problem that
you see with dynamic binding + TCO (together)? Could you show me with a
small digestible example so that I could decide for myself what to do
(not to argue with anyone, everybody is entitled to their own choices)?
I would really appreciate a code snippet that represents the real
problems that makes TCO different than non-TCO? Remember, I'm
new_to_lisp ;-).
Yours.
In article <·······················@p10g2000cwp.googlegroups.com>,
"new_to_lisp" <········@yahoo.com> wrote:
> I would really appreciate a code snippet that represents the real
> problems that makes TCO different than non-TCO? Remember, I'm
> new_to_lisp ;-).
(defun web-server ()
(serve-one-request)
(unless (time-to-quit-p)
(web-server)))
rg
Ron Garret wrote:
> In article <·······················@p10g2000cwp.googlegroups.com>,
> "new_to_lisp" <········@yahoo.com> wrote:
>
> > I would really appreciate a code snippet that represents the real
> > problems that makes TCO different than non-TCO? Remember, I'm
> > new_to_lisp ;-).
>
> (defun web-server ()
> (serve-one-request)
> (unless (time-to-quit-p)
> (web-server)))
>
> rg
Hi Ron,
This example is basically the same as the one provided by Frode later,
right? Basically what made me confused was:
1) Frode agreed to Mr. Marshall's claim that there is no *observable*
difference between TCO and non-TCO version. But apparently they had
some assumptions in mind. Probably CL standard provides the necessary
specs to exclude such problematic cases from optimization effort. I
simply don't know. If so, there is no real world implication anyways.
I'm not sure about this last point, because the disassembly example
Pascal provided showed no symptom of side-effects: when side-effects
are possible, is standard specs wise enough to make sure TCO is not
performed in such situations, or should I worry about that? I simply
don't know yet. But I certainly understood what the problem is in
theory.
2) The computer I accessed then had no Lisp installation, so I couldn't
try simple examples, and in a hurry I identified the non-TCO one with
TCO version in my mind in a hurry. And as I couldn't try the example, I
didn't notice the problem in my thinking. I'm just getting used to all
this dynamic binding thing, as my previous experience with programming
is basically using C and C++, so no dynamic binding. In fact, even the
notion of binding is kinda new: it doesn't map directly to C scopes.
Kinda fascinating. I enjoyed it a lot, but it takes some effort to get
used to on my side.
When you provide examples, it really helps if you either summarize the
expected result in a sentence, or provide a directly executable simple
one (with print, variable assignments, etc.) to illustrate the point,
it's really helpful though. Because I have no good command of my
installed Lisp interpreters (I'm only focused on language constructs as
of now, not on the system specific properties of any particular Lisp
installation) I really have a hard time to reproduce disassembler
output, converting unexecutable things to executable pieces and so on.
I'm really, really new :-). I expect this to be the case at least for
one more month (until i finish the book I follow, the one by David
Lamkins, "Successful Lisp").
I appreciate all the help.
Regards.
In article <························@z34g2000cwc.googlegroups.com>,
"new_to_lisp" <········@yahoo.com> wrote:
> Ron Garret wrote:
> > In article <·······················@p10g2000cwp.googlegroups.com>,
> > "new_to_lisp" <········@yahoo.com> wrote:
> >
> > > I would really appreciate a code snippet that represents the real
> > > problems that makes TCO different than non-TCO? Remember, I'm
> > > new_to_lisp ;-).
> >
> > (defun web-server ()
> > (serve-one-request)
> > (unless (time-to-quit-p)
> > (web-server)))
> >
> > rg
>
> Hi Ron,
> This example is basically the same as the one provided by Frode later,
> right?
Could be. I haven't been following the whole thread (just enough to not
that people have been making this a lot more complicated than it needs
to be).
> Basically what made me confused was:
> 1) Frode agreed to Mr. Marshall's claim that there is no *observable*
> difference between TCO and non-TCO version.
They are both wrong.
> But apparently they had some assumptions in mind.
Just one false assumption: infinite stack space.
> Probably CL standard provides the necessary
> specs to exclude such problematic cases from optimization effort. I
> simply don't know.
Nope, the CL standard says nothing about TCO. In CL, TCO is a
vendor-specific extension.
> If so, there is no real world implication anyways.
Incorrect. The real-world implication is that some programs that will
run with TCO will fail with a stack overflow without it.
> I'm not sure about this last point, because the disassembly example
> Pascal provided showed no symptom of side-effects: when side-effects
> are possible, is standard specs wise enough to make sure TCO is not
> performed in such situations, or should I worry about that? I simply
> don't know yet. But I certainly understood what the problem is in
> theory.
Side-effects are a red herring. They have nothing to do with TCO. (I
think they may have been talking about dynamic binding, which is not the
same thing as a side-effect. But that has nothing to do with TCO
either, except for making it a little harder to implement.)
> 2) The computer I accessed then had no Lisp installation
That is the first thing you ought to fix.
> I'm just getting used to all
> this dynamic binding thing, as my previous experience with programming
> is basically using C and C++, so no dynamic binding. In fact, even the
> notion of binding is kinda new: it doesn't map directly to C scopes.
> Kinda fascinating. I enjoyed it a lot, but it takes some effort to get
> used to on my side.
You might want to take a look at:
http://www.flownet.com/ron/specials.pdf
> When you provide examples, it really helps if you either summarize the
> expected result in a sentence,
In an implementation with TCO, the above example with work (assuming
suitable definitions of serve-one-request and time-to-quit-p). In an
implementation without TCO, the above example will overflow the stack
sooner or later.
That's pretty much all there is to TCO.
(There is one more point, and that is the distinction between tail calls
and tail recursion. The above example is tail-recursive (the tail call
is to the function in which the tail-call resides), so you can rewrite
it using other constructs so that it will not overflow the stack even in
a non-TCO implementation, e.g. using DO or LOOP. Here's an example with
tail-calls that cannot be so transformed:
(defun f1 () (do-something) (f2))
(defun f2 () (do-something-else) (f1))
As before, this will run forever on an implementation with TCO. It will
overflow the stack otherwise. And unlike the tail-recursive example, it
cannot be rewritten to work in a non-TCO implementation. If you try
something like:
(defun f1 () (loop (do-something) (do-something-else))
it will fail if do-something or do-something-else redefine f1 or f2,
which in Lisp they could do.)
rg
> (defun f1 () (do-something) (f2))
> (defun f2 () (do-something-else) (f1))
>
Doesn't Lisp have something like "goto" in C? Couldn't we just do TCO
by hand? I mean to rewrite this so as not to overflow the stack?
"new_to_lisp" <········@yahoo.com> writes:
>> (defun f1 () (do-something) (f2))
>> (defun f2 () (do-something-else) (f1))
>>
>
> Doesn't Lisp have something like "goto" in C? Couldn't we just do TCO
> by hand? I mean to rewrite this so as not to overflow the stack?
Not cross lexical bound.
Read again the thread, there's an example of TAGBODY and GO.
But you can always transform them as:
(defun f1 () (do-something) (do-something-else) (f1))
(defun f2 () (do-something-else) (do-something) (f2))
as long as do-something, do-something-else, and no other thread don't
redefine f1 or f2 while f1 or f2 run.
--
__Pascal Bourguignon__ http://www.informatimago.com/
COMPONENT EQUIVALENCY NOTICE: The subatomic particles (electrons,
protons, etc.) comprising this product are exactly the same in every
measurable respect as those used in the products of other
manufacturers, and no claim to the contrary may legitimately be
expressed or implied.
Pascal Bourguignon wrote:
> "new_to_lisp" <········@yahoo.com> writes:
>
> >> (defun f1 () (do-something) (f2))
> >> (defun f2 () (do-something-else) (f1))
> >>
> >
> > Doesn't Lisp have something like "goto" in C? Couldn't we just do TCO
> > by hand? I mean to rewrite this so as not to overflow the stack?
>
> Not cross lexical bound.
> Read again the thread, there's an example of TAGBODY and GO.
>
>
>
> But you can always transform them as:
>
> (defun f1 () (do-something) (do-something-else) (f1))
> (defun f2 () (do-something-else) (do-something) (f2))
>
> as long as do-something, do-something-else, and no other thread don't
> redefine f1 or f2 while f1 or f2 run.
>
>
Not that it's necessarily a good thing or bad, but is the following
valid (any of the two go's); or should the tag and go be on exactly the
same lexical level (just to make sure that I understand what you say
correctly):
(tagbody A
...
(tagbody B
...
(go A))
...
(go B))
Note that they're unbalanced...
new_to_lisp wrote:
> Pascal Bourguignon wrote:
> > "new_to_lisp" <········@yahoo.com> writes:
> >
> > >> (defun f1 () (do-something) (f2))
> > >> (defun f2 () (do-something-else) (f1))
> > >>
> > >
> > > Doesn't Lisp have something like "goto" in C? Couldn't we just do TCO
> > > by hand? I mean to rewrite this so as not to overflow the stack?
> >
> > Not cross lexical bound.
> > Read again the thread, there's an example of TAGBODY and GO.
> >
> >
> >
> > But you can always transform them as:
> >
> > (defun f1 () (do-something) (do-something-else) (f1))
> > (defun f2 () (do-something-else) (do-something) (f2))
> >
> > as long as do-something, do-something-else, and no other thread don't
> > redefine f1 or f2 while f1 or f2 run.
> >
> >
>
> Not that it's necessarily a good thing or bad, but is the following
> valid (any of the two go's); or should the tag and go be on exactly the
> same lexical level (just to make sure that I understand what you say
> correctly):
>
> (tagbody A
> ...
> (tagbody B
> ...
> (go A))
> ...
> (go B))
>
>
> Note that they're unbalanced...
Of course assuming some conditionals etc. to circumvent the first (go
A) if that's valid at all...
new_to_lisp wrote:
> new_to_lisp wrote:
> > Pascal Bourguignon wrote:
> > > "new_to_lisp" <········@yahoo.com> writes:
> > >
> > > >> (defun f1 () (do-something) (f2))
> > > >> (defun f2 () (do-something-else) (f1))
> > > >>
> > > >
> > > > Doesn't Lisp have something like "goto" in C? Couldn't we just do TCO
> > > > by hand? I mean to rewrite this so as not to overflow the stack?
> > >
> > > Not cross lexical bound.
> > > Read again the thread, there's an example of TAGBODY and GO.
> > >
> > >
> > >
> > > But you can always transform them as:
> > >
> > > (defun f1 () (do-something) (do-something-else) (f1))
> > > (defun f2 () (do-something-else) (do-something) (f2))
> > >
> > > as long as do-something, do-something-else, and no other thread don't
> > > redefine f1 or f2 while f1 or f2 run.
> > >
> > >
> >
> > Not that it's necessarily a good thing or bad, but is the following
> > valid (any of the two go's); or should the tag and go be on exactly the
> > same lexical level (just to make sure that I understand what you say
> > correctly):
> >
> > (tagbody A
> > ...
> > (tagbody B
> > ...
> > (go A))
> > ...
> > (go B))
> >
> >
> > Note that they're unbalanced...
>
> Of course assuming some conditionals etc. to circumvent the first (go
> A) if that's valid at all...
Never mind, I asked, because I was not sure how tagbody was working
internally. I'm not sure simply putting parentheses and a special
symbol like tagbody (or defun, or whatever) correspond to {}'s in C in
terms of creating a new level of lexical scope. in fact I'm sure they
don't, thanks to defun :). If all this don't make sense, just ignore
;-).
I tried and saw for myself that (go A) is OK, but (go B) is not. It's a
pity though not to have a real goto ;-)
> > Basically what made me confused was:
> > 1) Frode agreed to Mr. Marshall's claim that there is no *observable*
> > difference between TCO and non-TCO version.
>
> They are both wrong.
>
> > But apparently they had some assumptions in mind.
>
> Just one false assumption: infinite stack space.
To be fair, I don't think neither had that assumption in mind. Both
clarified that in their posts. What I mean that the post in question
was confusing is evident in the example later provided by Frode: in a
hypothetical Lisp environment, the output is different in the presence
of TCO. Regardless of infinite stak space. In fact, I previously noted
that modifying a dynamic global may be problematic, but obviously my
mind was not clear and later i was confused. Yes, their agreement in
that post was wrong, but probably that was just a slip on Frode's half
as he is the one who provided the clarifying example later.
> > Probably CL standard provides the necessary
> > specs to exclude such problematic cases from optimization effort. I
> > simply don't know.
>
> Nope, the CL standard says nothing about TCO. In CL, TCO is a
> vendor-specific extension.
>
> > If so, there is no real world implication anyways.
>
> Incorrect. The real-world implication is that some programs that will
> run with TCO will fail with a stack overflow without it.
>
I meant, if CL standard prevented TCO in semantically (excluding stack
overflow semantics) different cases, both would overflow the stack as
it wouldn't be possible to TCO in such cases. In other cases, what you
said..
> > I'm not sure about this last point, because the disassembly example
> > Pascal provided showed no symptom of side-effects: when side-effects
> > are possible, is standard specs wise enough to make sure TCO is not
> > performed in such situations, or should I worry about that? I simply
> > don't know yet. But I certainly understood what the problem is in
> > theory.
>
> Side-effects are a red herring. They have nothing to do with TCO. (I
> think they may have been talking about dynamic binding, which is not the
> same thing as a side-effect. But that has nothing to do with TCO
> either, except for making it a little harder to implement.)
I meant something at the time, but i don't recall now ;-)
>
> > 2) The computer I accessed then had no Lisp installation
>
> That is the first thing you ought to fix.
>
Couldn't fix that, but no problem with my own PC ;-)
> > I'm just getting used to all
> > this dynamic binding thing, as my previous experience with programming
> > is basically using C and C++, so no dynamic binding. In fact, even the
> > notion of binding is kinda new: it doesn't map directly to C scopes.
> > Kinda fascinating. I enjoyed it a lot, but it takes some effort to get
> > used to on my side.
>
> You might want to take a look at:
>
> http://www.flownet.com/ron/specials.pdf
>
I'll have a look, although it's title make me feel like an idiot ;-).
It's just a matter of comfort, nothing conceptually difficult.
Thanks a lot for the post.
In article <·······················@i40g2000cwc.googlegroups.com>,
"new_to_lisp" <········@yahoo.com> wrote:
> > > Basically what made me confused was:
> > > 1) Frode agreed to Mr. Marshall's claim that there is no *observable*
> > > difference between TCO and non-TCO version.
> >
> > They are both wrong.
> >
> > > But apparently they had some assumptions in mind.
> >
> > Just one false assumption: infinite stack space.
>
> To be fair, I don't think neither had that assumption in mind. Both
> clarified that in their posts. What I mean that the post in question
> was confusing is evident in the example later provided by Frode: in a
> hypothetical Lisp environment, the output is different in the presence
> of TCO. Regardless of infinite stak space.
Not if it's done correctly. TCO is a semantics-preserving optimization.
If your program produces different output after TCO then you've done
something wrong.
I presume this is the example you're referring to:
> The point of TCO is to make code like
>
> (defun f (x)
> ... (return-from f (f y)) ...)
>
> [Note that the return-from operator here is just to make it explicit
> that the function-call is a tail-call.]
>
> behave exactly like
>
> (defun tco-f (x)
> (tagbody restart-f
> ... (setf x y) (go restart-f) ...))
but this is oversimplifying the situation. TCO in the presence of
dynamic binding is possible but very tricky. MCL, for example, just
punts:
? (defun foo (x) (foo x))
FOO
? (foo 1)
; This will run forever until we hit cmd-.
Aborted
? (defun foo (x) (let ((*print-base* 10)) (foo x)))
FOO
? (foo 1)
> Error: Stack overflow on control stack.
> To globally increase stack space,
> increase *MINIMUM-STACK-OVERFLOW-SIZE*
> While executing: "Unknown"
> Type Command-/ to continue, Command-. to abort.
> If continued: Continue with a larger stack
See the Restarts� menu item for further choices.
1 >
Aborted
?
> > You might want to take a look at:
> >
> > http://www.flownet.com/ron/specials.pdf
> >
>
> I'll have a look, although it's title make me feel like an idiot ;-).
Then tell yourself that the title refers to the author, not the audience.
rg
> but this is oversimplifying the situation. TCO in the presence of
> dynamic binding is possible but very tricky. MCL, for example, just
> punts:
>
> ? (defun foo (x) (foo x))
> FOO
> ? (foo 1)
> ; This will run forever until we hit cmd-.
> Aborted
> ? (defun foo (x) (let ((*print-base* 10)) (foo x)))
> FOO
> ? (foo 1)
> > Error: Stack overflow on control stack.
> > To globally increase stack space,
> > increase *MINIMUM-STACK-OVERFLOW-SIZE*
> > While executing: "Unknown"
> > Type Command-/ to continue, Command-. to abort.
> > If continued: Continue with a larger stack
> See the Restarts menu item for further choices.
> 1 >
> Aborted
> ?
That's why I said in a *hypothetical* Lisp environment. By change in
semantics,
of course I mean a straightforward and dumb TCO. I've seen some
articles on the web
trying to circumvent the perils of dynamic binding (yesterday, trying
to make sense
of people's talk) with TCO. I already know very well that it's
semantics preserving
if you don't have to deal with dynamic binding. Your output simply
shows that MCL is
not that dumb ;-).
> > > You might want to take a look at:
> > >
> > > http://www.flownet.com/ron/specials.pdf
> > >
> >
> > I'll have a look, although it's title make me feel like an idiot ;-).
>
> Then tell yourself that the title refers to the author, not the audience.
>
> rg
I was just kidding ;-). Thank you for the document, appreciate it.
Regards.
In article <························@e56g2000cwe.googlegroups.com>,
"new_to_lisp" <········@yahoo.com> wrote:
> > but this is oversimplifying the situation. TCO in the presence of
> > dynamic binding is possible but very tricky. MCL, for example, just
> > punts:
> >
> > ? (defun foo (x) (foo x))
> > FOO
> > ? (foo 1)
> > ; This will run forever until we hit cmd-.
> > Aborted
> > ? (defun foo (x) (let ((*print-base* 10)) (foo x)))
> > FOO
> > ? (foo 1)
> > > Error: Stack overflow on control stack.
> > > To globally increase stack space,
> > > increase *MINIMUM-STACK-OVERFLOW-SIZE*
> > > While executing: "Unknown"
> > > Type Command-/ to continue, Command-. to abort.
> > > If continued: Continue with a larger stack
> > See the Restarts� menu item for further choices.
> > 1 >
> > Aborted
> > ?
>
> That's why I said in a *hypothetical* Lisp environment. By change in
> semantics,
> of course I mean a straightforward and dumb TCO. I've seen some
> articles on the web
> trying to circumvent the perils of dynamic binding (yesterday, trying
> to make sense
> of people's talk) with TCO. I already know very well that it's
> semantics preserving
> if you don't have to deal with dynamic binding.
No, (correct) TCO is semantics-preserving, period, end of story. Any
transformation that does not preserve semantics is not (correct) TCO.
> Your output simply shows that MCL is not that dumb ;-).
Actually, my output shows that MCL is dumb. It only does the easy case
and punts on the hard one. This is of course much better than just
getting it wrong, but a really smart implementation would be able to do
the hard case correctly.
rg
Ron Garret <·········@flownet.com> writes:
> Actually, my output shows that MCL is dumb. It only does the easy
> case and punts on the hard one. This is of course much better than
> just getting it wrong, but a really smart implementation would be
> able to do the hard case correctly.
I'd be surprised if there aren't cases where you'd need to keep N
separate bindings active in order not to change the standard semantics
of dynamic bindings. In other words, I believe there are cases where
no amount of compiler smartness would suffice.
It's also a valid point I think that although it's perhaps /possible/
for the compiler to get it right, the implications (in terms of
speed/code-size/compiler-time/etc) might be severe, and perhaps not
just for the code in question but throughout the system (e.g. if the
protocol for dynamic binding lookup must be changed).
--
Frode Vatvedt Fjeld
In article <··············@vserver.cs.uit.no>,
Frode Vatvedt Fjeld <······@cs.uit.no> wrote:
> Ron Garret <·········@flownet.com> writes:
>
> > Actually, my output shows that MCL is dumb. It only does the easy
> > case and punts on the hard one. This is of course much better than
> > just getting it wrong, but a really smart implementation would be
> > able to do the hard case correctly.
>
> I'd be surprised if there aren't cases where you'd need to keep N
> separate bindings active in order not to change the standard semantics
> of dynamic bindings. In other words, I believe there are cases where
> no amount of compiler smartness would suffice.
Sometimes being dumb can be the smart thing. :-)
> It's also a valid point I think that although it's perhaps /possible/
> for the compiler to get it right, the implications (in terms of
> speed/code-size/compiler-time/etc) might be severe, and perhaps not
> just for the code in question but throughout the system (e.g. if the
> protocol for dynamic binding lookup must be changed).
Indeed.
rg
Ron Garret wrote:
> In article <························@z34g2000cwc.googlegroups.com>,
> "new_to_lisp" <········@yahoo.com> wrote:
>
> > Basically what made me confused was:
> > 1) Frode agreed to Mr. Marshall's claim that there is no *observable*
> > difference between TCO and non-TCO version.
>
> They are both wrong.
I was making an effort to be technically correct here. By an
`observable' difference, I mean the ability to write a program that
runs to completion and returns a distinguishably different answer
depending on whether the computer has tail-call optimization or not.
Although it is possible to write a program that would eventually
overflow any finite stack, until it overflows you cannot state
positively that the implementation is not tail recursive (you may
simply have a *lot* of stack and not yet hit the end).
>
> > But apparently they had some assumptions in mind.
>
> Just one false assumption: infinite stack space.
>
No, just *arbitrarily large*. Again, any program that runs to
completion on a tail-recursive implementation will run to completion on
a non-tail-recursive implementation provided it has sufficient (not
infinite) stack space. (In other words, if you specify a particular
tail-recursive program that returns an answer, I can in theory supply
enough stack to a non-tail recursive version and it will return the
same answer.)
> > Probably CL standard provides the necessary
> > specs to exclude such problematic cases from optimization effort. I
> > simply don't know.
>
> Nope, the CL standard says nothing about TCO. In CL, TCO is a
> vendor-specific extension.
>
> > If so, there is no real world implication anyways.
>
> Incorrect. The real-world implication is that some programs that will
> run with TCO will fail with a stack overflow without it.
Right.
"new_to_lisp" <········@yahoo.com> writes:
> I would really appreciate a code snippet that represents the real
> problems that makes TCO different than non-TCO? Remember, I'm
> new_to_lisp ;-).
The point of TCO is to make code like
(defun f (x)
... (return-from f (f y)) ...)
[Note that the return-from operator here is just to make it explicit
that the function-call is a tail-call.]
behave exactly like
(defun tco-f (x)
(tagbody restart-f
... (setf x y) (go restart-f) ...))
Now, if you ignore the fact that the stack (as observed from a
debugger) will look quite different, the two programs will behave
identically.. EXCEPT, if the code hidden in the dots installs a
dynamically scoped environment around the tail-call form, for example
like this:
(defun f (x)
.. (let ((*print-base* 16))
(return-from f (f y))) ..)
which would be TCO-translated to
(defun tco-f (x)
(tagbody restart-f
.. (let ((*print-base* 16))
(setf x y) (go restart-f)) ..))
which is a different program (do you see why? Hint: what could those
dots do?). With some effort it is possible to make tco-f behave
somewhat better (this is what the article you found discussed, I
believe), but I don't think you can (with reasonable effort) make it
behave truly identically.
--
Frode Vatvedt Fjeld
I'm trying to understand, but, obviously whatever you do in the first
dots would make possibly a difference only when you create a new local
binding declared special. But then that binding would be reexecuted in
both TCO and non-TCO cases over and over again, making whatever you did
before returns obsolete: so TCO and non-TCO cases would be the same?!.
I'm not sure why the result would be different.
And, sorry, maybe I'm getting lame, but I don't understand how you
could ever get to the second dots (the ones after the returns)?
Please could you clarify? i tried, but I don't think I get it. I would
really appreciate your explanation.
Thank you.
Frode Vatvedt Fjeld wrote:
> "new_to_lisp" <········@yahoo.com> writes:
>
> > I would really appreciate a code snippet that represents the real
> > problems that makes TCO different than non-TCO? Remember, I'm
> > new_to_lisp ;-).
>
> The point of TCO is to make code like
>
> (defun f (x)
> ... (return-from f (f y)) ...)
>
> [Note that the return-from operator here is just to make it explicit
> that the function-call is a tail-call.]
>
> behave exactly like
>
> (defun tco-f (x)
> (tagbody restart-f
> ... (setf x y) (go restart-f) ...))
>
>
> Now, if you ignore the fact that the stack (as observed from a
> debugger) will look quite different, the two programs will behave
> identically.. EXCEPT, if the code hidden in the dots installs a
> dynamically scoped environment around the tail-call form, for example
> like this:
>
> (defun f (x)
> .. (let ((*print-base* 16))
> (return-from f (f y))) ..)
>
> which would be TCO-translated to
>
> (defun tco-f (x)
> (tagbody restart-f
> .. (let ((*print-base* 16))
> (setf x y) (go restart-f)) ..))
>
> which is a different program (do you see why? Hint: what could those
> dots do?). With some effort it is possible to make tco-f behave
> somewhat better (this is what the article you found discussed, I
> believe), but I don't think you can (with reasonable effort) make it
> behave truly identically.
>
> --
> Frode Vatvedt Fjeld
"new_to_lisp" <········@yahoo.com> writes:
> I'm trying to understand, but, obviously whatever you do in the
> first dots would make possibly a difference only when you create a
> new local binding declared special. But then that binding would be
> reexecuted in both TCO and non-TCO cases over and over again, making
> whatever you did before returns obsolete: so TCO and non-TCO cases
> would be the same?!. I'm not sure why the result would be
> different.
Well, it's not all that difficult, if you just try to trace what
whould happen. Here's the code again:
> > (defun f (x)
> > .. (let ((*print-base* 16))
> > (return-from f (f y))) ..)
> >
> > which would be TCO-translated to
> >
> > (defun tco-f (x)
> > (tagbody restart-f
> > .. (let ((*print-base* 16))
> > (setf x y) (go restart-f)) ..))
Now, let's say the first two dots contain (print x).. and that we
ignore here the issue of recursion termination etc, so the programs
are:
(defun f (x)
(print x)
(let ((*print-base* 16))
(return-from f (f y))))
[ which is btw is identical to
(defun f (x)
(print x)
(let ((*print-base* 16))
(f y)))
]
which would be TCO-translated to
(defun tco-f (x)
(tagbody restart-f
(print x)
(let ((*print-base* 16))
(setf x y) (go restart-f))))
Now, in the first iteration, in both cases the print form would see
the previous binding of *print-base* (whatever value that happened to
be). However, in f all the subsequent (i.e. "inner") prints would see
the *print-base* (with value 16) that was established by the outer
invocation of f. In tco-f however, the binding to 16 will /never/ be
seen by any print, because the goto always exits the scope of the
binding before print can see it.
> And, sorry, maybe I'm getting lame, but I don't understand how you
> could ever get to the second dots (the ones after the returns)?
> Please could you clarify?
If the first dots included e.g. an if, the latter dots could hold the
else part. Or the dots could represent just the left-paren of a let
binding.
--
Frode Vatvedt Fjeld
Got it ;-). Previously I thought the function call as if it was goto.
Thank you very much.
Frode Vatvedt Fjeld wrote:
> "new_to_lisp" <········@yahoo.com> writes:
>
> > I'm trying to understand, but, obviously whatever you do in the
> > first dots would make possibly a difference only when you create a
> > new local binding declared special. But then that binding would be
> > reexecuted in both TCO and non-TCO cases over and over again, making
> > whatever you did before returns obsolete: so TCO and non-TCO cases
> > would be the same?!. I'm not sure why the result would be
> > different.
>
> Well, it's not all that difficult, if you just try to trace what
> whould happen. Here's the code again:
>
> > > (defun f (x)
> > > .. (let ((*print-base* 16))
> > > (return-from f (f y))) ..)
> > >
> > > which would be TCO-translated to
> > >
> > > (defun tco-f (x)
> > > (tagbody restart-f
> > > .. (let ((*print-base* 16))
> > > (setf x y) (go restart-f)) ..))
>
> Now, let's say the first two dots contain (print x).. and that we
> ignore here the issue of recursion termination etc, so the programs
> are:
>
> (defun f (x)
> (print x)
> (let ((*print-base* 16))
> (return-from f (f y))))
>
> [ which is btw is identical to
>
> (defun f (x)
> (print x)
> (let ((*print-base* 16))
> (f y)))
> ]
>
> which would be TCO-translated to
>
> (defun tco-f (x)
> (tagbody restart-f
> (print x)
> (let ((*print-base* 16))
> (setf x y) (go restart-f))))
>
> Now, in the first iteration, in both cases the print form would see
> the previous binding of *print-base* (whatever value that happened to
> be). However, in f all the subsequent (i.e. "inner") prints would see
> the *print-base* (with value 16) that was established by the outer
> invocation of f. In tco-f however, the binding to 16 will /never/ be
> seen by any print, because the goto always exits the scope of the
> binding before print can see it.
>
> > And, sorry, maybe I'm getting lame, but I don't understand how you
> > could ever get to the second dots (the ones after the returns)?
> > Please could you clarify?
>
> If the first dots included e.g. an if, the latter dots could hold the
> else part. Or the dots could represent just the left-paren of a let
> binding.
>
> --
> Frode Vatvedt Fjeld
From: Marcin 'Qrczak' Kowalczyk
Subject: Re: dereference (or eval ?) a "nested" symbol
Date:
Message-ID: <877j6rwxnz.fsf@qrnik.zagroda>
Frode Vatvedt Fjeld <······@cs.uit.no> writes:
> The point of TCO is to make code like
>
> (defun f (x)
> ... (return-from f (f y)) ...)
>
> [Note that the return-from operator here is just to make it explicit
> that the function-call is a tail-call.]
>
> behave exactly like
>
> (defun tco-f (x)
> (tagbody restart-f
> ... (setf x y) (go restart-f) ...))
This is a special case of a tail call: tail recursion.
TCO applies also when the called function is different than the one
we are in.
Tail recursion optimization is an easy local transformation even if
the runtime system has otherwise no special support for tail calls.
OTOH tail call optimization requires an appropriate function call
protocol.
--
__("< Marcin Kowalczyk
\__/ ······@knm.org.pl
^^ http://qrnik.knm.org.pl/~qrczak/
> OTOH tail call optimization requires an appropriate function call
> protocol.
>
> --
> __("< Marcin Kowalczyk
> \__/ ······@knm.org.pl
> ^^ http://qrnik.knm.org.pl/~qrczak/
Like what? Could you elaborate a little bit?
Regards.
new_to_lisp wrote:
>> OTOH tail call optimization requires an appropriate function call
>> protocol.
>>
>> --
>> __("< Marcin Kowalczyk
>> \__/ ······@knm.org.pl
>> ^^ http://qrnik.knm.org.pl/~qrczak/
>
> Like what? Could you elaborate a little bit?
> Regards.
I wrote up a good explanation of this, and then I found
<http://lambda-the-ultimate.org/classic/message1532.html> on Google.
Even though it's mainly talking about C and C++, it goes into much
better detail then I did.
-- MJF
From: Marcin 'Qrczak' Kowalczyk
Subject: Re: dereference (or eval ?) a "nested" symbol
Date:
Message-ID: <87bqw3pkij.fsf@qrnik.zagroda>
"new_to_lisp" <········@yahoo.com> writes:
>> OTOH tail call optimization requires an appropriate function call
>> protocol.
>
> Like what? Could you elaborate a little bit?
There are two basic ways to introduce TCO on a runtime system which
didn't support it before, where the abstraction level of the runtime
is so high that it has "function call" and "function return" primitives
(rather than separate primitives for pushing arguments on the stack,
pushing the return address, jumps to computed addresses, creating
and removing stack frames etc., where a tail call could be made by
assembling them in a different order):
1. Add primitives for tail calls, such that the semantics of a tail
call is like a non-tail call followed by function return, modulo
things like stack traces on uncaught exceptions etc. where changes
result from the fact that the caller's stack frame is removed
before the call instead of during function return.
This is almost always possible without changing the calling
convention, under reasonable assumptions about it (arguments
are passed in registers or on the stack etc.) and while certain
optimizations are not used (objects which must be live during
the call are not put directly in the stack frame, function
arguments can be moved to a different address).
The naive way which always works is to push arguments as in the
normal call, then shift them towards the base of the stack,
overwriting the previous stack frame; arguments passed in registers
are even easier. But it's often possible to do better, and put
arguments in their target positions directly, or at least put these
which don't clash with local variables still needed for computing
later arguments.
.NET offers such a primitive. It would be unimplementable if it
had not been provided, but providing it didn't interfere with the
already established calling convention. I've heard that in the
Microsoft implementation it's actually slower than a non-tail call
however; they didn't seem to care about its efficiency because C#
and VB don't use it.
JVM doesn't offer such primitive, even though probably it would be
technically straightforward to add it, so this way is not available
when targetting JVM.
2. Emulate tail calls with other mechanisms (trampoline style where
each function returns the address of the function it wishes to jump
to, or periodic exceptions which clear the stack, or not using
function calls at all but jumping within a single function).
This is portable, but it's a different calling convention. It's
generally less efficient than original calls. The return address is
passed as an extra argument instead of using the native mechanism,
and there is a central loop which implements the trampoline, or
repeatedly catches exceptions and restarts the computation from
the place indicated in the exception. Callbacks from the target
language to the language which uses tail calls require setting up
a local driver loop.
There is a modification of the trampoline style when the target
language is C, used by Glasgow Haskell and by my Kogut compiler on
some processor families. The C compiler generates something like the
trampoline style, and the assembler source it produces is postprocessed
by a program which converts trampoline returns into assembler jumps.
If all calls can be thus converted, the driver loop can be eliminated.
--
__("< Marcin Kowalczyk
\__/ ······@knm.org.pl
^^ http://qrnik.knm.org.pl/~qrczak/
Frode Vatvedt Fjeld <······@cs.uit.no> writes:
> > (defun tco-f (x)
> > (tagbody restart-f
> > ... (setf x y) (go restart-f) ...))
Marcin 'Qrczak' Kowalczyk <······@knm.org.pl> writes:
> This is a special case of a tail call: tail recursion. TCO applies
> also when the called function is different than the one we are in.
That's right. The point of the exercise remains precisely the same,
though (and it's quite a bit more difficult I think to illustrate the
point using general tail-calls).
> Tail recursion optimization is an easy local transformation even if
> the runtime system has otherwise no special support for tail calls.
> OTOH tail call optimization requires an appropriate function call
> protocol.
This seems like a rather peculiar statement to me, given the context
which is TCO in the presence of dynamic bindings..?
--
Frode Vatvedt Fjeld
From: Marcin 'Qrczak' Kowalczyk
Subject: Re: dereference (or eval ?) a "nested" symbol
Date:
Message-ID: <878xr7xxc4.fsf@qrnik.zagroda>
Frode Vatvedt Fjeld <······@cs.uit.no> writes:
>> Tail recursion optimization is an easy local transformation even if
>> the runtime system has otherwise no special support for tail calls.
>> OTOH tail call optimization requires an appropriate function call
>> protocol.
>
> This seems like a rather peculiar statement to me, given the context
> which is TCO in the presence of dynamic bindings..?
For me a call inside a LET which establishes dynamic bindings is not
a tail call wrt. the whole function body, so TCO doesn't apply there.
Same as when the call is in UNWIND-PROTECT. It's not a tail context.
The only problem with this is that a careless programmer might
overlook that this is not a tail context, and assume that TCO would
apply. These constructs for the first sight look as if they were tail
contexts because they don't contain an explicit intervening LAMBDA,
because actions to be performed after returning are implicit, and
because a similar LET with all lexical variables does provide a tail
context.
There might be implementations which realize that some cases of tail
recursion in LET with dynamic variables could be TCO'ed as well, but
programmers should not rely on that even if the language otherwise
promises TCO.
--
__("< Marcin Kowalczyk
\__/ ······@knm.org.pl
^^ http://qrnik.knm.org.pl/~qrczak/
Marcin 'Qrczak' Kowalczyk <······@knm.org.pl> writes:
> For me a call inside a LET which establishes dynamic bindings is not
> a tail call wrt. the whole function body, so TCO doesn't apply
> there.
> Same as when the call is in UNWIND-PROTECT. It's not a tail context.
>
> The only problem with this is that a careless programmer might
> overlook that this is not a tail context, and assume that TCO would
> apply. These constructs for the first sight look as if they were
> tail contexts because they don't contain an explicit intervening
> LAMBDA, because actions to be performed after returning are
> implicit, and because a similar LET with all lexical variables does
> provide a tail context.
Now what happens when we throw with-foo macros (whose implementation
may or may not set up a dynamic environment) into this stew?
Suddenly, an important aspect of every macro that takes &body
arguments is whether they preserve tail context. So (going back to the
debate of whether required TCO is the Right Thing [and I don't know
what your position is on this]) we have to destroy one of the very
nice principles of orthogonality in the language by requiring TCO,
i.e. that wrapping a form in a dynamic environment has no further
consequences for that form.
--
Frode Vatvedt Fjeld
Frode Vatvedt Fjeld <······@cs.uit.no> writes:
> Marcin 'Qrczak' Kowalczyk <······@knm.org.pl> writes:
>
>> For me a call inside a LET which establishes dynamic bindings is not
>> a tail call wrt. the whole function body, so TCO doesn't apply
>> there.
>
>> Same as when the call is in UNWIND-PROTECT. It's not a tail context.
>>
>> The only problem with this is that a careless programmer might
>> overlook that this is not a tail context, and assume that TCO would
>> apply. These constructs for the first sight look as if they were
>> tail contexts because they don't contain an explicit intervening
>> LAMBDA, because actions to be performed after returning are
>> implicit, and because a similar LET with all lexical variables does
>> provide a tail context.
>
> Now what happens when we throw with-foo macros (whose implementation
> may or may not set up a dynamic environment) into this stew?
> Suddenly, an important aspect of every macro that takes &body
> arguments is whether they preserve tail context. So (going back to the
> debate of whether required TCO is the Right Thing [and I don't know
> what your position is on this]) we have to destroy one of the very
> nice principles of orthogonality in the language by requiring TCO,
> i.e. that wrapping a form in a dynamic environment has no further
> consequences for that form.
Well, in a sense, tail call optimization and the question whether a
form is a tail call ARE orthogonal.
What I get is that the occasions for TCO in usual Common Lisp code are
so few that we don't lose a lot not having it mandatorily. It's nice
to use an implementation having TCO when you're running academic
exercises, but as soon as you write professionnal code, with all these
UNWIND-PROTECT, HANDLER-CASE, and WITH- macros, it doesn't make a
difference because TCO couldn't be applied in most cases anyway.
If anybody is interested, that'd make a good paper subject: a
statistical study of TCO-ability of actual CL sources.
--
__Pascal Bourguignon__ http://www.informatimago.com/
Small brave carnivores
Kill pine cones and mosquitoes
Fear vacuum cleaner
Pascal Bourguignon wrote:
> Frode Vatvedt Fjeld <······@cs.uit.no> writes:
>
> > Marcin 'Qrczak' Kowalczyk <······@knm.org.pl> writes:
> >
> >> For me a call inside a LET which establishes dynamic bindings is not
> >> a tail call wrt. the whole function body, so TCO doesn't apply
> >> there.
> >
> >> Same as when the call is in UNWIND-PROTECT. It's not a tail context.
> >>
> >> The only problem with this is that a careless programmer might
> >> overlook that this is not a tail context, and assume that TCO would
> >> apply. These constructs for the first sight look as if they were
> >> tail contexts because they don't contain an explicit intervening
> >> LAMBDA, because actions to be performed after returning are
> >> implicit, and because a similar LET with all lexical variables does
> >> provide a tail context.
> >
> > Now what happens when we throw with-foo macros (whose implementation
> > may or may not set up a dynamic environment) into this stew?
> > Suddenly, an important aspect of every macro that takes &body
> > arguments is whether they preserve tail context. So (going back to the
> > debate of whether required TCO is the Right Thing [and I don't know
> > what your position is on this]) we have to destroy one of the very
> > nice principles of orthogonality in the language by requiring TCO,
> > i.e. that wrapping a form in a dynamic environment has no further
> > consequences for that form.
>
> Well, in a sense, tail call optimization and the question whether a
> form is a tail call ARE orthogonal.
>
> What I get is that the occasions for TCO in usual Common Lisp code are
> so few that we don't lose a lot not having it mandatorily. It's nice
> to use an implementation having TCO when you're running academic
> exercises, but as soon as you write professionnal code, with all these
> UNWIND-PROTECT, HANDLER-CASE, and WITH- macros, it doesn't make a
> difference because TCO couldn't be applied in most cases anyway.
>
> If anybody is interested, that'd make a good paper subject: a
> statistical study of TCO-ability of actual CL sources.
>
>
> --
> __Pascal Bourguignon__ http://www.informatimago.com/
> Small brave carnivores
> Kill pine cones and mosquitoes
> Fear vacuum cleaner
I don't think my comment is worth anything among you seasoned Lispers
as a newbie, but I feel this is one of the best points made until now.
Insisting a TCO is always semantic preserving is on the other hand,
IMHO, is just giving a different definition of the concept than what I
had in mind. Therefore, that's a differerent issue now.
As long as TCO (definition: the thing that eliminates the function call
without changing any observable behavior, except it can save me some
stack spaceof course ;-)) buys me a considerable peformance gain, it
matters to me. I don't see this in tricky cases. One would be much
better off with a loop. Better safe than sorry... Otherwise, it's not
worth getting into trouble. I would personally just use some other
technique in such a situation. I would use C or fortran doing numerics
or GUI stuff anyway: call me traitor ;-). Just my 2 cents ;-).
But, it's very instructive to follow this discussion for me, and
probably a waste of time for you ;-). In any case, I profit more than
you do. Thank you very much, guys!
Regards.
new_to_lisp wrote:
>
> As long as TCO (definition: the thing that eliminates the function call
> without changing any observable behavior, except it can save me some
> stack spaceof course ;-)) buys me a considerable peformance gain, it
> matters to me.
Tail-call optimization does not usually enhance performance. It is a
space-saving
optimization.
From: Marcin 'Qrczak' Kowalczyk
Subject: Re: dereference (or eval ?) a "nested" symbol
Date:
Message-ID: <87r74xvspv.fsf@qrnik.zagroda>
"Joe Marshall" <··········@gmail.com> writes:
> Tail-call optimization does not usually enhance performance. It is a
> space-saving optimization.
It depends on the calling convention. Often it does enhance
performance directly, especially when arguments are passed in
registers. Even if the actual instruction sequence is not faster,
using less space means better cache effects.
--
__("< Marcin Kowalczyk
\__/ ······@knm.org.pl
^^ http://qrnik.knm.org.pl/~qrczak/
Pascal Bourguignon wrote:
>
> What I get is that the occasions for TCO in usual Common Lisp code are
> so few that we don't lose a lot not having it mandatorily. It's nice
> to use an implementation having TCO when you're running academic
> exercises, but as soon as you write professionnal code, with all these
> UNWIND-PROTECT, HANDLER-CASE, and WITH- macros, it doesn't make a
> difference because TCO couldn't be applied in most cases anyway.
>
> If anybody is interested, that'd make a good paper subject: a
> statistical study of TCO-ability of actual CL sources.
I bet that they would be used much more often than you think.
I, too, would like to see a statistical study.
"new_to_lisp" <········@yahoo.com> writes:
> I'd better not interfere with experts :-), but if the only problem is
> "whether one can assume that there is enough stack-space for
> reasonably-sized inputs", I'd go with TCO and a compiler that supports
> it. But then, I'm now really confused: what's all the fuss is about?
> Really sorry for the lame question, but, what's the main problem that
> you see with dynamic binding + TCO (together)? Could you show me with a
> small digestible example so that I could decide for myself what to do
> (not to argue with anyone, everybody is entitled to their own choices)?
>
> I would really appreciate a code snippet that represents the real
> problems that makes TCO different than non-TCO? Remember, I'm
> new_to_lisp ;-).
[238]> (defun recl (x) (let ((y (1- x))) (unless (zerop y) (recl y))))
RECL
[239]> (defvar *y*)
*Y*
[240]> (defun py () (print *u*))
PY
[241]> (defun recd (x) (let ((*y* (1- x))) (py) (unless (zerop y) (rec y))))
RECD
Nor RECL is TCO:
[242]> (disassemble (compile 'recl))
Disassembly of function RECL
1 required argument
0 optional arguments
No rest parameter
No keyword parameters
9 byte-code instructions:
0 L0
0 (LOAD&DEC&PUSH 1)
2 (LOAD&PUSH 0)
3 (CALLS2&JMPIF 146 L11) ; ZEROP
6 (LOAD&PUSH 0)
7 (JMPTAIL 1 4 L0)
11 L11
11 (NIL)
12 (SKIP&RET 3)
NIL
but RECD isn't because of the dynamic binding:
[243]> (disassemble (compile 'recd))
WARNING in RECD :
Y is neither declared nor bound,
it will be treated as if it were declared SPECIAL.
WARNING in RECD :
Y is neither declared nor bound,
it will be treated as if it were declared SPECIAL.
Disassembly of function RECD
(CONST 0) = *Y*
(CONST 1) = PY
(CONST 2) = Y
(CONST 3) = REC
1 required argument
0 optional arguments
No rest parameter
No keyword parameters
reads special variable: Y
14 byte-code instructions:
0 (LOAD&PUSH 1)
1 (CALLS2 152) ; 1-
3 (BIND 0) ; *Y*
5 (CALL0 1) ; PY
7 (GETVALUE&PUSH 2) ; Y
9 (CALLS2&JMPIF 146 L19) ; ZEROP
12 (GETVALUE&PUSH 2) ; Y
14 (CALL1 3) ; REC
16 L16
16 (UNBIND1)
17 (SKIP&RET 2)
19 L19
19 (NIL)
20 (JMP L16)
NIL
[244]>
And the question is: how many recursive functions use such dynamic
bindings vs. how many recursive functions only use lexical bindings in
your code?
--
__Pascal Bourguignon__ http://www.informatimago.com/
You're always typing.
Well, let's see you ignore my
sitting on your hands.
Could you explain the second example a little more? What happens if we
create tail recursion optimized and *not* tail recursion optimized
versions of the second example (i.e. two versions of the dynamic one)?
I appreciate the assembly listing, I really do; but please could you
tell me what difference in functionality would be observed then? Just
to be sure...
Thank you in advance.
Pascal Bourguignon wrote:
> "new_to_lisp" <········@yahoo.com> writes:
>
> > I'd better not interfere with experts :-), but if the only problem is
> > "whether one can assume that there is enough stack-space for
> > reasonably-sized inputs", I'd go with TCO and a compiler that supports
> > it. But then, I'm now really confused: what's all the fuss is about?
> > Really sorry for the lame question, but, what's the main problem that
> > you see with dynamic binding + TCO (together)? Could you show me with a
> > small digestible example so that I could decide for myself what to do
> > (not to argue with anyone, everybody is entitled to their own choices)?
> >
> > I would really appreciate a code snippet that represents the real
> > problems that makes TCO different than non-TCO? Remember, I'm
> > new_to_lisp ;-).
>
>
> [238]> (defun recl (x) (let ((y (1- x))) (unless (zerop y) (recl y))))
> RECL
> [239]> (defvar *y*)
> *Y*
> [240]> (defun py () (print *u*))
> PY
> [241]> (defun recd (x) (let ((*y* (1- x))) (py) (unless (zerop y) (rec y))))
> RECD
>
>
> Nor RECL is TCO:
>
> [242]> (disassemble (compile 'recl))
>
> Disassembly of function RECL
> 1 required argument
> 0 optional arguments
> No rest parameter
> No keyword parameters
> 9 byte-code instructions:
> 0 L0
> 0 (LOAD&DEC&PUSH 1)
> 2 (LOAD&PUSH 0)
> 3 (CALLS2&JMPIF 146 L11) ; ZEROP
> 6 (LOAD&PUSH 0)
> 7 (JMPTAIL 1 4 L0)
> 11 L11
> 11 (NIL)
> 12 (SKIP&RET 3)
> NIL
>
>
> but RECD isn't because of the dynamic binding:
>
> [243]> (disassemble (compile 'recd))
> WARNING in RECD :
> Y is neither declared nor bound,
> it will be treated as if it were declared SPECIAL.
> WARNING in RECD :
> Y is neither declared nor bound,
> it will be treated as if it were declared SPECIAL.
>
> Disassembly of function RECD
> (CONST 0) = *Y*
> (CONST 1) = PY
> (CONST 2) = Y
> (CONST 3) = REC
> 1 required argument
> 0 optional arguments
> No rest parameter
> No keyword parameters
> reads special variable: Y
> 14 byte-code instructions:
> 0 (LOAD&PUSH 1)
> 1 (CALLS2 152) ; 1-
> 3 (BIND 0) ; *Y*
> 5 (CALL0 1) ; PY
> 7 (GETVALUE&PUSH 2) ; Y
> 9 (CALLS2&JMPIF 146 L19) ; ZEROP
> 12 (GETVALUE&PUSH 2) ; Y
> 14 (CALL1 3) ; REC
> 16 L16
> 16 (UNBIND1)
> 17 (SKIP&RET 2)
> 19 L19
> 19 (NIL)
> 20 (JMP L16)
> NIL
> [244]>
>
>
> And the question is: how many recursive functions use such dynamic
> bindings vs. how many recursive functions only use lexical bindings in
> your code?
>
>
> --
> __Pascal Bourguignon__ http://www.informatimago.com/
> You're always typing.
> Well, let's see you ignore my
> sitting on your hands.
"new_to_lisp" <········@yahoo.com> writes:
> Could you explain the second example a little more? What happens if we
> create tail recursion optimized and *not* tail recursion optimized
> versions of the second example (i.e. two versions of the dynamic one)?
> I appreciate the assembly listing, I really do; but please could you
> tell me what difference in functionality would be observed then? Just
> to be sure...
Well the point is that you cannot TCO RECD.
(Ignore the RECD in my previous post, it wasn't even recursive).
While in the source:
(defun recd (x) (let ((*y* (1- x))) (py) (unless (zerop y) (recd y))))
it looks like (recd y) is a recursive tail call, it is not. You can
see it from the disassembled:
[249]> (disassemble (compile 'recd))
WARNING in RECD :
Y is neither declared nor bound,
it will be treated as if it were declared SPECIAL.
WARNING in RECD :
Y is neither declared nor bound,
it will be treated as if it were declared SPECIAL.
Disassembly of function RECD
(CONST 0) = *Y*
(CONST 1) = PY
(CONST 2) = Y
1 required argument
0 optional arguments
No rest parameter
No keyword parameters
reads special variable: Y
15 byte-code instructions:
0 L0
0 (LOAD&PUSH 1)
1 (CALLS2 152) ; 1-
3 (BIND 0) ; *Y*
5 (CALL0 1) ; PY
7 (GETVALUE&PUSH 2) ; Y
9 (CALLS2&JMPIF 146 L19) ; ZEROP
12 (GETVALUE&PUSH 2) ; Y
14 (JSR L0) ; THIS is the call (recd y)
16 L16 ; and after that call,
16 (UNBIND1) ; there is still this to do.
17 (SKIP&RET 2) ; finally we return.
19 L19
19 (NIL)
20 (JMP L16)
NIL
The dynamic bindings imply some post-processing that prevent the
apparant last call to be trully a tail call.
Otherwise, Frode gave an example of what would happen if we forced the
last call to be a tail call.
There are also other dynamic constructs in CL that will prevent TCO:
CATCH, UNWIND-PROTECT, HANDLER-BIND, etc...
--
__Pascal Bourguignon__ http://www.informatimago.com/
WARNING: This product warps space and time in its vicinity.
Pascal Bourguignon wrote:
> "new_to_lisp" <········@yahoo.com> writes:
>
> > Could you explain the second example a little more? What happens if we
> > create tail recursion optimized and *not* tail recursion optimized
> > versions of the second example (i.e. two versions of the dynamic one)?
> > I appreciate the assembly listing, I really do; but please could you
> > tell me what difference in functionality would be observed then? Just
> > to be sure...
>
> Well the point is that you cannot TCO RECD.
> (Ignore the RECD in my previous post, it wasn't even recursive).
>
>
> While in the source:
>
> (defun recd (x) (let ((*y* (1- x))) (py) (unless (zerop y) (recd y))))
>
> it looks like (recd y) is a recursive tail call, it is not. You can
> see it from the disassembled:
>
>
>
> [249]> (disassemble (compile 'recd))
> WARNING in RECD :
> Y is neither declared nor bound,
> it will be treated as if it were declared SPECIAL.
> WARNING in RECD :
> Y is neither declared nor bound,
> it will be treated as if it were declared SPECIAL.
>
> Disassembly of function RECD
> (CONST 0) = *Y*
> (CONST 1) = PY
> (CONST 2) = Y
> 1 required argument
> 0 optional arguments
> No rest parameter
> No keyword parameters
> reads special variable: Y
> 15 byte-code instructions:
> 0 L0
> 0 (LOAD&PUSH 1)
> 1 (CALLS2 152) ; 1-
> 3 (BIND 0) ; *Y*
> 5 (CALL0 1) ; PY
> 7 (GETVALUE&PUSH 2) ; Y
> 9 (CALLS2&JMPIF 146 L19) ; ZEROP
> 12 (GETVALUE&PUSH 2) ; Y
> 14 (JSR L0) ; THIS is the call (recd y)
> 16 L16 ; and after that call,
> 16 (UNBIND1) ; there is still this to do.
> 17 (SKIP&RET 2) ; finally we return.
> 19 L19
> 19 (NIL)
> 20 (JMP L16)
> NIL
>
> The dynamic bindings imply some post-processing that prevent the
> apparant last call to be trully a tail call.
>
> Otherwise, Frode gave an example of what would happen if we forced the
> last call to be a tail call.
>
>
> There are also other dynamic constructs in CL that will prevent TCO:
> CATCH, UNWIND-PROTECT, HANDLER-BIND, etc...
>
> --
> __Pascal Bourguignon__ http://www.informatimago.com/
>
> WARNING: This product warps space and time in its vicinity.
Your last explanation together with Frode's last post clarified things
a lot. Not that I didn't learn essentials of this dynamic binding
thing, but I guess it will take some time to get used to it. Your
explanations make perfect sense though. In a week of Lisp experience,
I've seen quite a bit of new stuff. As these points are not made
explicit in the book by Lamkins (successful Lisp -- I've read about
third of it yet though), believe me this and other Lisp lists help
quite a lot. I deeply appreciate your help and patience.
I'm really grateful to all who tried to help, and you really succeeded
;-): I really got it :).
Thanks again, I'll be back soon again!
Regards.
From: Pascal Costanza
Subject: Re: dereference (or eval ?) a "nested" symbol
Date:
Message-ID: <47vloaFhn206U1@individual.net>
new_to_lisp wrote:
> <quote>(and considering Common Lisp doesn't require TCO)</quote>
>
> Is there a reason for a compiler not to implement TCO?
There is a reason to make it optional. For example, it can be easier to
debug if your stack frames are not implicitly reused because you can
then inspect them all.
You may also want to be able to replace function bodies at runtime and
make sure that the new versions are called, including from tail calls of
already executing functions.
Pascal
--
3rd European Lisp Workshop
July 3-4 - Nantes, France - co-located with ECOOP 2006
http://lisp-ecoop06.bknr.net/
<quote>There is a reason to make it optional</quote>
Optional for the programmer, not for compiler writer though...
From: Pascal Costanza
Subject: Re: dereference (or eval ?) a "nested" symbol
Date:
Message-ID: <4809m5Fhmeq0U1@individual.net>
new_to_lisp wrote:
> <quote>There is a reason to make it optional</quote>
> Optional for the programmer, not for compiler writer though...
...depends on the specific goals of a language implementation.
Pascal
--
3rd European Lisp Workshop
July 3-4 - Nantes, France - co-located with ECOOP 2006
http://lisp-ecoop06.bknr.net/
<quote>
...depends on the specific goals of a language implementation.
</quote>
Given that TCO is not assumed to make any difference in the language
semantics (a point I've just came to realize), yes, I have to admit to
that. But especially for a commercial large-scale "compiler", it would
be a mistake not to, I guess :-).