Jon Harrop wrote:
> André Thieme wrote:
>> Jon Harrop schrieb:
>>> André Thieme wrote:
>>>> Also keep in mind that Sun is working on Fortress, which will most
>>>> likely lead to built in TC support in the JVM.
>>>
>>> Sun have been "working on" many things for many years and produced
>>> nothing worth having. I for one am not pinning my hopes on anything done
>>> by Sun, not least because they are going bankrupt and just laid off many
>>> thousands of employees (again).
>>
>> They are in the lead though.
>
> The CLR has had tail calls, value types and real parametric polymorphism
> for the best part of a decade. The JVM still does not have them.
Having said that:
http://mail.openjdk.java.net/pipermail/mlvm-dev/2009-January/000331.html
--
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
http://www.ffconsultancy.com/?u
Jon Harrop schrieb:
> Jon Harrop wrote:
>> André Thieme wrote:
>>> Jon Harrop schrieb:
>>>> André Thieme wrote:
>>>>> Also keep in mind that Sun is working on Fortress, which will most
>>>>> likely lead to built in TC support in the JVM.
>>>> Sun have been "working on" many things for many years and produced
>>>> nothing worth having. I for one am not pinning my hopes on anything done
>>>> by Sun, not least because they are going bankrupt and just laid off many
>>>> thousands of employees (again).
>>> They are in the lead though.
>> The CLR has had tail calls, value types and real parametric polymorphism
>> for the best part of a decade. The JVM still does not have them.
>
> Having said that:
>
> http://mail.openjdk.java.net/pipermail/mlvm-dev/2009-January/000331.html
Support in the official JDK (that from Sun) would be even nicer though.
Anyway, Clojure has tail calls, via recur and trampolines.
It is true that trampolines require you to code slightly different, but
that is just a design pattern. Tail recursion itself already is a design
pattern in functional programming. Trampolines are nothing complicated:
when you already understand the principle recursion it will require just
a few minutes to learn, and from then on you can use them.
They will not reduce productivity and are not a mentional disadvantage
over proper TCs. Strictly speaking they are a disadvantage, as tail
recursion is a disadvantage compared to non-TC-recursion, which can
still result in stack overflows with todays compiler technology.
André
--
Lisp is not dead. It’s just the URL that has changed:
http://clojure.org/
André Thieme wrote:
> Support in the official JDK (that from Sun) would be even nicer though.
Perhaps. I suspect users will migrate to OpenJDK as it acquires more
features and Sun go bankrupt.
> Anyway, Clojure has tail calls, via recur and trampolines.
Clojure does *not* have tail calls. Trampolines degrade performance and
obfuscate stack traces but, most importantly, they only handle a few
special cases of tail calls. Trampolines are not a substitute for real tail
calls.
--
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
http://www.ffconsultancy.com/?u
Jon Harrop schrieb:
> Trampolines [...] only handle a few special cases of tail calls.
> Trampolines are not a substitute for real tail calls.
Ah okay, thanks for the info.
This is what I suspected some days ago, when I said that I am not sure
if they can handle all cases of mutually recursive functions.
Do you maybe have one or two simple examples at hand where they won’t
work?
André Thieme wrote:
> Jon Harrop schrieb:
>> Trampolines [...] only handle a few special cases of tail calls.
> > Trampolines are not a substitute for real tail calls.
>
> Ah okay, thanks for the info.
> This is what I suspected some days ago, when I said that I am not sure
> if they can handle all cases of mutually recursive functions.
> Do you maybe have one or two simple examples at hand where they won’t
> work?
Yes. I gave an example when Kaz asked for one in the other thread. In fact,
this is essentially the same discussion: trampolines give you goto with
parameter passing and it is not sufficient as an alternative to real tail
calls. Essentially, trampolines only work locally whereas tail calls can
jump to any other function, including functions that have not yet been
defined (e.g. will be dynamically loaded).
A major advantage of first-class functions in functional languages is that
you can build closures and pass them around at will. Two common examples of
this are continuation passing style (where you pass the function
representing the remainder of the work) and monadic style (where
computations are broken into pieces that can subsequently be bound together
again). Both of these techniques require the ability to tail call a
function that was passed in as an argument. Consider the following:
# let succ k n = k (n+1);;
val succ : (int -> 'a) -> int -> 'a = <fun>
This function "succ" takes a continuation function "k" that was going to be
applied to an int and applies it to the next int instead. We have no idea
where "k" has been or will be defined so we cannot wrap the whole mutual
recursion in a trampoline. In fact, we may well want to expose "succ" as
part of our API to the outside world and we really don't want to have to
expose trampolines.
Perhaps the most obvious real example where we would want to do this is a
parser combinator library. For example, a parser combinator to read a list
of values (e.g. CSV) would be passed itself in order to read a nested list.
If you don't have tail calls then this is highly likely to cause a stack
overflow on big inputs, e.g. in Scala or Clojure.
This deficiency is so severe that it is arguably wrong to call Scala and
Clojure functional languages. In historical terms, you could say that
Clojure has failed to learn valuable lessons from Scheme. In practice, of
course, Clojure is only being limited by its target VM. I am sure Rich
Hickey wants real tail calls as much as the next guy.
--
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
http://www.ffconsultancy.com/?u
On 2009-01-23, Jon Harrop <···@ffconsultancy.com> wrote:
> André Thieme wrote:
>> Jon Harrop schrieb:
>>> Trampolines [...] only handle a few special cases of tail calls.
>> > Trampolines are not a substitute for real tail calls.
>>
>> Ah okay, thanks for the info.
>> This is what I suspected some days ago, when I said that I am not sure
>> if they can handle all cases of mutually recursive functions.
>> Do you maybe have one or two simple examples at hand where they won’t
>> work?
>
> Yes. I gave an example when Kaz asked for one in the other thread.
I have not dropped this.
> In fact,
> this is essentially the same discussion: trampolines give you goto with
> parameter passing and it is not sufficient as an alternative to real tail
> calls. Essentially, trampolines only work locally whereas tail calls can
> jump to any other function, including functions that have not yet been
> defined (e.g. will be dynamically loaded).
I have working prototype of a portable cross-module tail calling mechanism for
Common Lisp, which is based on functions, but still has the obvious goto
semantics. I will be presenting that in a separate thread.
> A major advantage of first-class functions in functional languages is that
> you can build closures and pass them around at will.
This tail calling module nicely supports higher order tail calls. A TAILCALL
function is provided which works like FUNCALL, except that it has special
semantics when a tail block directly calls another tail block.
> This deficiency is so severe that it is arguably wrong to call Scala and
> Clojure functional languages.
ROFL!
It's arguably wrong to call Clojure (and Common Lisp) functional languages, but
for reasons you have not clued into, not because of tail calls.
> In historical terms, you could say that
> Clojure has failed to learn valuable lessons from Scheme. In practice, of
> course, Clojure is only being limited by its target VM. I am sure Rich
> Hickey wants real tail calls as much as the next guy.
Maybe the portable Common Lisp technique I will shortly present can be ported
to Closure.
Kaz Kylheku wrote:
> This tail calling module nicely supports higher order tail calls. A
> TAILCALL function is provided which works like FUNCALL, except that it has
> special semantics when a tail block directly calls another tail block.
Why only when a tail block calls another tail block?
--
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
http://www.ffconsultancy.com/?u
On 2009-01-23, Jon Harrop <···@ffconsultancy.com> wrote:
> Kaz Kylheku wrote:
>> This tail calling module nicely supports higher order tail calls. A
>> TAILCALL function is provided which works like FUNCALL, except that it has
>> special semantics when a tail block directly calls another tail block.
>
> Why only when a tail block calls another tail block?
Pardon me, that is actually incorrect. If a tail block calls a function via
TAILCALL, then the special semantics also applies: TAILCALL terminates the
activation of the invoking tail block before passing control (and arguments) to
the target function, which is dispatched using the same mechanism.
I want to leave certain behaviors undefined; they are artifacts of the current
prototype implementation. In particular, regular functions should not use the
global TAILCALL; it ought to be hidden. If a regular function is invoked
through TAILCALL, and then uses TAILCALL, then the semantics can actually
apply; that function will be terminated. But if it does the same thing when not
invoked through TAILCALL, it will not be terminated. I don't want any of this
to be defined behaviors. So let the behavior of TAILCALL be undefined outside
of tail blocks.
Kaz Kylheku wrote:
> Pardon me, that is actually incorrect. If a tail block calls a function
> via TAILCALL, then the special semantics also applies: TAILCALL terminates
> the activation of the invoking tail block before passing control (and
> arguments) to the target function, which is dispatched using the same
> mechanism.
>
> I want to leave certain behaviors undefined; they are artifacts of the
> current prototype implementation. In particular, regular functions should
> not use the
> global TAILCALL; it ought to be hidden. If a regular function is invoked
> through TAILCALL, and then uses TAILCALL, then the semantics can actually
> apply; that function will be terminated. But if it does the same thing
> when not
> invoked through TAILCALL, it will not be terminated. I don't want any of
> this to be defined behaviors. So let the behavior of TAILCALL be undefined
> outside of tail blocks.
So you have a closed world assumption and external code cannot benefit from
or even use your tail calls? How does it interact with interop (i.e. the
FFI)?
--
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
http://www.ffconsultancy.com/?u
Jon Harrop wrote:
> Clojure does *not* have tail calls. Trampolines degrade performance and
> obfuscate stack traces but, most importantly, they only handle a few
> special cases of tail calls.
Sir Harrop's definition of a trampoline may be quite
different from mine, but trampolines are certainly
one of the most widely used standard techniques that
implementors of Scheme and functional languages use
to implement fully general tail recursion, i.e. real
tail calls.
Will
William D Clinger wrote:
> Jon Harrop wrote:
>> Clojure does *not* have tail calls. Trampolines degrade performance and
>> obfuscate stack traces but, most importantly, they only handle a few
>> special cases of tail calls.
>
> Sir Harrop's definition of a trampoline may be quite
> different from mine, but trampolines are certainly
> one of the most widely used standard techniques that
> implementors of Scheme and functional languages use
> to implement fully general tail recursion, i.e. real
> tail calls.
Indeed. Look at what Chicken Scheme's use of trampolines does to the stack
and how it breaks in the presence of interop. Now look at something like
Microsoft's CLR and observe how tail calls in the VM provide full stack
traces and seamless interop.
--
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
http://www.ffconsultancy.com/?u
Jan Harrop wrote:
> Indeed. Look at what Chicken Scheme's use of trampolines does to the stack
> and how it breaks in the presence of interop.
Chicken uses Cheney-on-the-MTA, not trampolines [1].
> Now look at something like Microsoft's CLR and observe
> how tail calls in the VM provide full stack traces and
> seamless interop.
It isn't that easy for Scheme or for Common Lisp, because
the CLR gets in the way of first class continuations and
restartable exceptions. By the time you've worked around
that limitation of the CLR, you've probably had to resort
to something like trampolines anyway [2].
Which do not have to break in the presence of interop,
and did not break in the presence of interop when we
used them for Common Larceny.
Will
[1] Henry G Baker. CONS Should Not CONS Its Arguments,
Part II: Cheney on the M.T.A. ACM SIGPLAN Notices 30, 9
(Sept 1995), pages 17-20. Online at
http://home.pipeline.com/~hbaker1/CheneyMTA.html
[2] William D Clinger. Common Larceny. Proceedings of
the 2005 International Lisp Conference, June 2005, pages
101-107. See http://www.ccs.neu.edu/home/will/papers.html
William D Clinger wrote:
> Jan Harrop wrote:
>> Indeed. Look at what Chicken Scheme's use of trampolines does to the
>> stack and how it breaks in the presence of interop.
>
> Chicken uses Cheney-on-the-MTA, not trampolines [1].
What they describe as "Appel's unpublished method" is what I had understood
to be conventional trampolines but the techniques are all quite similar.
However, I noticed that a recent discussion on the Scala list uses a much
simpler local (and correspondingly less useful) form of "trampoline".
>> Now look at something like Microsoft's CLR and observe
>> how tail calls in the VM provide full stack traces and
>> seamless interop.
>
> It isn't that easy for Scheme or for Common Lisp, because
> the CLR gets in the way of first class continuations and
> restartable exceptions.
Right.
> By the time you've worked around
> that limitation of the CLR, you've probably had to resort
> to something like trampolines anyway [2].
>
> Which do not have to break in the presence of interop,
> and did not break in the presence of interop when we
> used them for Common Larceny.
How do you handle callbacks?
> [1] Henry G Baker. CONS Should Not CONS Its Arguments,
> Part II: Cheney on the M.T.A. ACM SIGPLAN Notices 30, 9
> (Sept 1995), pages 17-20. Online at
> http://home.pipeline.com/~hbaker1/CheneyMTA.html
For example, they apparently prohibited callbacks into Scheme from C. That
is the kind of interop problem I was referring to.
--
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
http://www.ffconsultancy.com/?u
Jon Harrop wrote:
> What they describe as "Appel's unpublished method" is what
> I had understood to be conventional trampolines but the
> techniques are all quite similar.
No.
> How do you handle callbacks?
Straightforwardly. It's okay to have multiple trampolines
on the CLR control stack, and that doesn't interfere with
proper tail recursion.
> For example, they apparently prohibited callbacks into
> Scheme from C. That is the kind of interop problem I was
> referring to.
It must be possible to implement trampolines poorly, but
I don't have any experience with that.
Will
William D Clinger wrote:
> Jon Harrop wrote:
>> How do you handle callbacks?
>
> Straightforwardly. It's okay to have multiple trampolines
> on the CLR control stack, and that doesn't interfere with
> proper tail recursion.
Tail recursion or tail calls?
--
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
http://www.ffconsultancy.com/?u
Jon Harrop quoting me:
> > Straightforwardly. It's okay to have multiple trampolines
> > on the CLR control stack, and that doesn't interfere with
> > proper tail recursion.
>
> Tail recursion or tail calls?
The "LAMBDA: the ultimate" series of papers by Steele and
Sussman would be a good place for you to start [1,2,3].
After reading them, you would have a better understanding
of what "proper tail recursion" means in languages such
as Scheme and ML.
Will
[1] normally online at http://library.readscheme.org/, but
that web site is down temporarily.
[2] Guy Lewis Steele, Jr. Debunking the "expensive procedure
call" myth or, procedure call implementations considered
harmful or, LAMBDA: The Ultimate GOTO. Proceedings of the
ACM Annual Conference, 1977, pages 153-162. Online at
http://portal.acm.org/citation.cfm?id=800179.810196
[3] Guy Lewis Steele, Jr. and Gerald Jay Sussman. Lambda:
the ultimate imperative. MIT AI Memo 353, March 1976.
Online at http://hdl.handle.net/1721.1/5790
William D Clinger wrote:
> Jon Harrop quoting me:
>> > Straightforwardly. It's okay to have multiple trampolines
>> > on the CLR control stack, and that doesn't interfere with
>> > proper tail recursion.
>>
>> Tail recursion or tail calls?
>
> The "LAMBDA: the ultimate" series of papers by Steele and
> Sussman would be a good place for you to start [1,2,3].
> After reading them, you would have a better understanding
> of what "proper tail recursion" means in languages such
> as Scheme and ML.
Ok, you mean "tail calls".
--
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
http://www.ffconsultancy.com/?u
On Sat, 31 Jan 2009 01:10:20 +0000, Jon Harrop <···@ffconsultancy.com>
wrote:
>William D Clinger wrote:
>> Jon Harrop quoting me:
>>> > Straightforwardly. It's okay to have multiple trampolines
>>> > on the CLR control stack, and that doesn't interfere with
>>> > proper tail recursion.
>>>
>>> Tail recursion or tail calls?
>>
>> The "LAMBDA: the ultimate" series of papers by Steele and
>> Sussman would be a good place for you to start [1,2,3].
>> After reading them, you would have a better understanding
>> of what "proper tail recursion" means in languages such
>> as Scheme and ML.
>
>Ok, you mean "tail calls".
"Tail call" is more generic - it can refer to any function call
occurring in tail position.
Scheme uses the term "proper tail recursion" to refer to a self
recursive call in tail position.
George
Jon Harrop wrote:
> Ok, you mean "tail calls".
No. I meant proper tail recursion.
George Neuner corrected Harrop:
> "Tail call" is more generic - it can refer to any function call
> occurring in tail position.
Neuner is correct. "Tail call" is a syntactic concept,
having nothing to do with how tail calls are implemented.
For Scheme, tail calls are defined formally by R5RS 3.5
and R6RS 11.20 [1,2].
> Scheme uses the term "proper tail recursion" to refer to a self
> recursive call in tail position.
No. Proper tail recursion is not limited to self tail
calls, but is about the asymptotic space efficiency
achieved by implementing general tail calls without
creating new continuations unnecessarily. R5RS 3.5
and R6RS 5.11 define proper tail recursion by
reference to the formal definition in my PLDI 1998
paper [3].
Will
[1] Richard Kelsey, William Clinger, and Jonathan Rees
[editors]. Revised^5 Report on the Algorithmic Language
Scheme. Higher-Order and Symbolic Computation, 11(1),
August 1998, pages 7-105. Also in ACM SIGPLAN Notices
33(9), September 1998. Online at
http://www.schemers.org/Documents/Standards/R5RS/
[2] http://www.r6rs.org/final/html/r6rs/r6rs.html
[3] William D Clinger. Proper tail recursion and
space efficiency. Proceedings of the 1998 ACM
Conference on Programming Language Design and
Implementation, June 1998, pages 174-185. Online at
ftp://ftp.ccs.neu.edu/pub/people/will/tail.ps.gz
William D Clinger <········@yahoo.com> wrote:
+---------------
| George Neuner corrected Harrop:
| > "Tail call" is more generic - it can refer to any function call
| > occurring in tail position.
|
| Neuner is correct. "Tail call" is a syntactic concept,
| having nothing to do with how tail calls are implemented.
|
| For Scheme, tail calls are defined formally by R5RS 3.5
| and R6RS 11.20 [1,2].
|
| > Scheme uses the term "proper tail recursion" to refer to a self
| > recursive call in tail position.
|
| No. Proper tail recursion is not limited to self tail
| calls, but is about the asymptotic space efficiency
| achieved by implementing general tail calls without
| creating new continuations unnecessarily. R5RS 3.5
| and R6RS 5.11 define proper tail recursion by
| reference to the formal definition in my PLDI 1998
| paper [3].
+---------------
It is this sort of terminological confusion that makes me
really, *really* wish that RxRS had instead used the term
"proper tail call optimization", since the latter encompasses
both the general case and the specific case of "tail recursion".
(*sigh*)
-Rob
-----
Rob Warnock <····@rpw3.org>
627 26th Avenue <URL:http://rpw3.org/>
San Mateo, CA 94403 (650)572-2607
On Jan 31, 5:56 pm, ····@rpw3.org (Rob Warnock) wrote:
> William D Clinger <········@yahoo.com> wrote:
> +---------------
> | George Neuner corrected Harrop:
> | > "Tail call" is more generic - it can refer to any function call
> | > occurring in tail position.
> |
> | Neuner is correct. "Tail call" is a syntactic concept,
> | having nothing to do with how tail calls are implemented.
> |
> | For Scheme, tail calls are defined formally by R5RS 3.5
> | and R6RS 11.20 [1,2].
> |
> | > Scheme uses the term "proper tail recursion" to refer to a self
> | > recursive call in tail position.
> |
> | No. Proper tail recursion is not limited to self tail
> | calls, but is about the asymptotic space efficiency
> | achieved by implementing general tail calls without
> | creating new continuations unnecessarily. R5RS 3.5
> | and R6RS 5.11 define proper tail recursion by
> | reference to the formal definition in my PLDI 1998
> | paper [3].
> +---------------
>
> It is this sort of terminological confusion that makes me
> really, *really* wish that RxRS had instead used the term
> "proper tail call optimization", since the latter encompasses
> both the general case and the specific case of "tail recursion".
> (*sigh*)
Several years ago Will Clinger and I had the terminology discussion on
this newsgroup and concluded that a better phrase than "proper tail
recursion" would be "space efficient tail recursion". It removes the
incendiary term "proper" (implying that other forms of tail calls or
recursion are improper), and instead of "optimization", which usually
implies speed, the "space-efficient" term describes what Scheme is
really after. Unfortunately, nobody seems to remember that
conversation, since I've heard the term used very seldom after that.
Perhaps if Will were to concede too use that term, he wouldn't get
into arguments with non-lispers who have become confused by the term.
Duane
<·····@franz.com> wrote:
+---------------
| ····@rpw3.org (Rob Warnock) wrote:
| > It is this sort of terminological confusion that makes me
| > really, *really* wish that RxRS had instead used the term
| > "proper tail call optimization", since the latter encompasses
| > both the general case and the specific case of "tail recursion".
| > (*sigh*)
|
| Several years ago Will Clinger and I had the terminology discussion on
| this newsgroup and concluded that a better phrase than "proper tail
| recursion" would be "space efficient tail recursion". It removes the
| incendiary term "proper" (implying that other forms of tail calls or
| recursion are improper), and instead of "optimization", which usually
| implies speed, the "space-efficient" term describes what Scheme is
| really after.
+---------------
And I strongly prefer "optimization" to "recursion", since "recursion"
carries a bunch of baggage about computability and "iteration versus
recursion" that gets in the way. It also suggests self-recursion *way*
too strongly. I'm more concerned about the case where the program has
to run "forever" [such as an operating system or a server daemon] and
the program is a huge state machine that eats input events and "tail calls"
the next state. Whatever you call it -- maybe just the acronym TCO,
I dunno -- it has to cover this case.
How about "proper tail call conversion" or "proper tail call elimination",
meaning that the "call" gets "properly" (safe-for-space, if that's your
favorite form of "proper") converted to a "jump" [and that the "return"
gets eliminated] and that any local environment (including incoming args)
gets abandoned?
+---------------
| Unfortunately, nobody seems to remember that conversation, since
| I've heard the term used very seldom after that. Perhaps if Will
| were to concede too use that term, he wouldn't get into arguments
| with non-lispers who have become confused by the term.
+---------------
I myself have no trouble with "proper", since I think that any TCO that
*isn't* safe-for-space *is* "improper"! ;-} And I really, really think
that "recursion" has to go [see reasons above]. Whereas "tail call" has to
stay, since that's the basic conceptual "hook". But I'm flexible; I could
stand to replace "proper" with "safe", but not "space-efficient" -- it's
both too long and "efficiency" has the same problem as "optimization",
it's not an absolute... but needs to be!! ["Safe" is sufficiently close
to an absolute, with "safe-for-space" assumed as one of the kinds of
"safety" that must be provided.]
So maybe "safe tail call conversion" or "safe tail call elimination"?
-Rob
-----
Rob Warnock <····@rpw3.org>
627 26th Avenue <URL:http://rpw3.org/>
San Mateo, CA 94403 (650)572-2607
On Feb 1, 3:01 am, ····@rpw3.org (Rob Warnock) wrote:
> <·····@franz.com> wrote:
>
> +---------------
> | ····@rpw3.org (Rob Warnock) wrote:
> | > It is this sort of terminological confusion that makes me
> | > really, *really* wish that RxRS had instead used the term
> | > "proper tail call optimization", since the latter encompasses
> | > both the general case and the specific case of "tail recursion".
> | > (*sigh*)
> |
> | Several years ago Will Clinger and I had the terminology discussion on
> | this newsgroup and concluded that a better phrase than "proper tail
> | recursion" would be "space efficient tail recursion". It removes the
> | incendiary term "proper" (implying that other forms of tail calls or
> | recursion are improper), and instead of "optimization", which usually
> | implies speed, the "space-efficient" term describes what Scheme is
> | really after.
> +---------------
>
> And I strongly prefer "optimization" to "recursion", since "recursion"
> carries a bunch of baggage about computability and "iteration versus
> recursion" that gets in the way. It also suggests self-recursion *way*
> too strongly. I'm more concerned about the case where the program has
> to run "forever" [such as an operating system or a server daemon] and
> the program is a huge state machine that eats input events and "tail calls"
> the next state. Whatever you call it -- maybe just the acronym TCO,
> I dunno -- it has to cover this case.
Yes, see below.
> How about "proper tail call conversion" or "proper tail call elimination",
> meaning that the "call" gets "properly" (safe-for-space, if that's your
> favorite form of "proper") converted to a "jump" [and that the "return"
> gets eliminated] and that any local environment (including incoming args)
> gets abandoned?
There it is again: "proper". See below.
> +---------------
> | Unfortunately, nobody seems to remember that conversation, since
> | I've heard the term used very seldom after that. Perhaps if Will
> | were to concede too use that term, he wouldn't get into arguments
> | with non-lispers who have become confused by the term.
> +---------------
>
> I myself have no trouble with "proper", since I think that any TCO that
> *isn't* safe-for-space *is* "improper"! ;-}
Of course, when absolutely keeping the stack from blowing out is the
primary goal. But when the goal is debugging, and in particular not
losing any stack frames due to elimination of the caller's frame by
reuse by the callee, then the it's the tail-call-conversion which is
improper.
And I really, really think
> that "recursion" has to go [see reasons above].
That's fine; I don't recall if we discussed alternate forms of the
phrase, but "space-efficient tail calls" says all that needs to be
said as well; it may have even been the one we had decided on. The
main part of the phrase lodged in my memory is "space-efficient" and I
notice that Will has even used that description in his text, though
not as a label.
Whereas "tail call" has to
> stay, since that's the basic conceptual "hook". But I'm flexible; I could
> stand to replace "proper" with "safe", but not "space-efficient" -- it's
> both too long and "efficiency" has the same problem as "optimization",
> it's not an absolute... but needs to be!! ["Safe" is sufficiently close
> to an absolute, with "safe-for-space" assumed as one of the kinds of
> "safety" that must be provided.]
Yes, that's fine as well - space-safe, safe-for-space, space-
efficient. I just wish Schemers would start using those terms instead
of "proper".
> So maybe "safe tail call conversion" or "safe tail call elimination"?
Absolutely. Now the question is: can we get Schemers to use an of
them and abandon "proper tail recusrion"?
Duane
·····@franz.com wrote:
> I don't recall if we discussed alternate forms of the
> phrase, but "space-efficient tail calls" says all that needs to be
> said as well; it may have even been the one we had decided on. �The
> main part of the phrase lodged in my memory is "space-efficient" and I
> notice that Will has even used that description in his text, though
> not as a label.
I think "space-efficient" is not as clear as it could be, if you take
into account that polynomial time-bounded algorithms are considered
efficient. Why not "constant-space tail calls"?
Michael
--
Michael Schuerig
··············@schuerig.de
http://www.schuerig.de/michael/
On Feb 1, 11:11 am, Michael Schuerig <·······@schuerig.de> wrote:
> ·····@franz.com wrote:
> > I don't recall if we discussed alternate forms of the
> > phrase, but "space-efficient tail calls" says all that needs to be
> > said as well; it may have even been the one we had decided on. The
> > main part of the phrase lodged in my memory is "space-efficient" and I
> > notice that Will has even used that description in his text, though
> > not as a label.
>
> I think "space-efficient" is not as clear as it could be, if you take
> into account that polynomial time-bounded algorithms are considered
> efficient. Why not "constant-space tail calls"?
That would be fine, too. In case you haven't noticed by my responses,
I don't care as much what it's called, as long as it doesn't include
the word "proper" and thus hijack a qualitative descriptor for
something that should be descriptive, and not pejorative by contrast.
CLers have various terms for "the thing we do", and I rail when they
call it "tail call optimization", because it's not necessarily
optimization (though it can sometimes lead to faster code). I just
call it "tail-call merging" or "tail-merging".
Duane
·····@franz.com wrote:
> That would be fine, too. In case you haven't noticed by my responses,
> I don't care as much what it's called, as long as it doesn't include
> the word "proper" and thus hijack a qualitative descriptor for
> something that should be descriptive, and not pejorative by contrast.
> CLers have various terms for "the thing we do", and I rail when they
> call it "tail call optimization", because it's not necessarily
> optimization (though it can sometimes lead to faster code). I just
> call it "tail-call merging" or "tail-merging".
That depends how you interpret "optimization". I think it is fair for an
optimization to reduce space and not time.
--
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
http://www.ffconsultancy.com/?u
Michael Schuerig wrote:
> ·····@franz.com wrote:
>> I don't recall if we discussed alternate forms of the
>> phrase, but "space-efficient tail calls" says all that needs to be
>> said as well; it may have even been the one we had decided on. The
>> main part of the phrase lodged in my memory is "space-efficient" and I
>> notice that Will has even used that description in his text, though
>> not as a label.
>
> I think "space-efficient" is not as clear as it could be, if you take
> into account that polynomial time-bounded algorithms are considered
> efficient. Why not "constant-space tail calls"?
I fail to see the point when everyone else is already using tail calls and
TCO and its not as if improper tail recursion or variable-space tail calls
or space-inefficient tail calls exist in any usable sense. Everything that
has been described here is just ordinary TCO...
--
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
http://www.ffconsultancy.com/?u
Jon Harrop wrote:
> Michael Schuerig wrote:
>> ·····@franz.com wrote:
>>> I don't recall if we discussed alternate forms of the
>>> phrase, but "space-efficient tail calls" says all that needs to be
>>> said as well; it may have even been the one we had decided on. The
>>> main part of the phrase lodged in my memory is "space-efficient" and I
>>> notice that Will has even used that description in his text, though
>>> not as a label.
>> I think "space-efficient" is not as clear as it could be, if you take
>> into account that polynomial time-bounded algorithms are considered
>> efficient. Why not "constant-space tail calls"?
>
> I fail to see the point when everyone else is already using tail calls and
> TCO and its not as if improper tail recursion or variable-space tail calls
> or space-inefficient tail calls exist in any usable sense. Everything that
> has been described here is just ordinary TCO...
>
A frog by any other name would smell as bad?
The terminological adjustments you fear so much arose to address
repeated confusions arisng precisely from a literal reading of the
standard terminology.
Your argument is like saying "free" is a good name for software that
comes with a stranglehold license because everyone knows it does so that
is what free means now.
I need a quotation from "1984"....
kth
On Sun, 01 Feb 2009 20:11:53 +0100, Michael Schuerig
<·······@schuerig.de> wrote:
>·····@franz.com wrote:
>
>> I don't recall if we discussed alternate forms of the
>> phrase, but "space-efficient tail calls" says all that needs to be
>> said as well; it may have even been the one we had decided on. �The
>> main part of the phrase lodged in my memory is "space-efficient" and I
>> notice that Will has even used that description in his text, though
>> not as a label.
>
>I think "space-efficient" is not as clear as it could be, if you take
>into account that polynomial time-bounded algorithms are considered
>efficient. Why not "constant-space tail calls"?
>
>Michael
Because 'constant-space' is technically incorrect. For example, the
stack can fluctuate due to calls to non-recursing functions made from
within the recursive path.
A better phrase would be 'constant-bounded-space' or something similar
which conveys that the stack may fluctuate during execution but that
the recursive call in question does not continually add to it.
George
On Sun, 01 Feb 2009 08:02:06 -0800, duane wrote:
> But when the goal is debugging, and in particular not losing any stack
> frames due to elimination of the caller's frame by reuse by the callee,
> then the it's the tail-call-conversion which is improper.
Is it? I supppose that there could be a POLA issue for the uninitiated,
but I've never seen anyone complaining about losing history of loop
iterations, and it's effectively the same situation. If you want history
for debugging purposes, there are plenty of logging tools and techniques
that'll help.
Just me putting in a vote for "proper" being proper, in this context :-)
Cheers,
--
Andrew
Andrew Reilly wrote:
> On Sun, 01 Feb 2009 08:02:06 -0800, duane wrote:
>> But when the goal is debugging, and in particular not losing any stack
>> frames due to elimination of the caller's frame by reuse by the callee,
>> then the it's the tail-call-conversion which is improper.
>
> Is it? I supppose that there could be a POLA issue for the uninitiated,
> but I've never seen anyone complaining about losing history of loop
> iterations, and it's effectively the same situation...
I believe the maintainers of the JVM strongly disagree with you.
--
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
http://www.ffconsultancy.com/?u
On Mon, 02 Feb 2009 01:13:31 +0000, Jon Harrop wrote:
> I believe the maintainers of the JVM strongly disagree with you.
That's OK: they've been wrong before ;-)
Cheers,
--
Andrew
Andrew Reilly wrote:
> On Mon, 02 Feb 2009 01:13:31 +0000, Jon Harrop wrote:
>
>> I believe the maintainers of the JVM strongly disagree with you.
>
> That's OK: they've been wrong before ;-)
Amen. :-)
--
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
http://www.ffconsultancy.com/?u
Rob Warnock wrote:
> William D Clinger <········@yahoo.com> wrote:
> +---------------
> | George Neuner corrected Harrop:
> | > "Tail call" is more generic - it can refer to any function call
> | > occurring in tail position.
> |
> | Neuner is correct. "Tail call" is a syntactic concept,
> | having nothing to do with how tail calls are implemented.
> |
> | For Scheme, tail calls are defined formally by R5RS 3.5
> | and R6RS 11.20 [1,2].
> |
> | > Scheme uses the term "proper tail recursion" to refer to a self
> | > recursive call in tail position.
> |
> | No. Proper tail recursion is not limited to self tail
> | calls, but is about the asymptotic space efficiency
> | achieved by implementing general tail calls without
> | creating new continuations unnecessarily. R5RS 3.5
> | and R6RS 5.11 define proper tail recursion by
> | reference to the formal definition in my PLDI 1998
> | paper [3].
> +---------------
>
> It is this sort of terminological confusion that makes me
> really, *really* wish that RxRS had instead used the term
> "proper tail call optimization", since the latter encompasses
> both the general case and the specific case of "tail recursion".
> (*sigh*)
Indeed. Surely that nomenclature (which is what I had understood to be
conventional) was around long before William's 1998 paper?
--
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
http://www.ffconsultancy.com/?u
Jon Harrop <···@ffconsultancy.com> wrote:
+---------------
| Rob Warnock wrote:
| > William D Clinger <········@yahoo.com> wrote:
| > +---------------
| > | Proper tail recursion is not limited to self tail
| > | calls, but is about the asymptotic space efficiency
| > | achieved by implementing general tail calls without
| > | creating new continuations unnecessarily. R5RS 3.5
| > | and R6RS 5.11 define proper tail recursion by
| > | reference to the formal definition in my PLDI 1998
| > | paper [3].
| > +---------------
| >
| > It is this sort of terminological confusion that makes me
| > really, *really* wish that RxRS had instead used the term
| > "proper tail call optimization", since the latter encompasses
| > both the general case and the specific case of "tail recursion".
| > (*sigh*)
|
| Indeed. Surely that nomenclature (which is what I had understood
| to be conventional) was around long before William's 1998 paper?
+---------------
It was around, and the extensive references in Clinger's paper
document that, but it was seldom (if ever) defined as to precisely
what it *meant*, especially in terms of the formal semantics.
That was the contribution of Clinger's PLDI 1998 paper, especially
defining it in terms of the "safe for space" criterion (which, as he
freely notes, is essentially the same definition as that proposed by
Morrisett & Harper, reference [MH97] in Clinger's paper). You should
actually read it before dismissing it so cavalierly.
-Rob
-----
Rob Warnock <····@rpw3.org>
627 26th Avenue <URL:http://rpw3.org/>
San Mateo, CA 94403 (650)572-2607
Rob Warnock wrote:
> It was around, and the extensive references in Clinger's paper
> document that, but it was seldom (if ever) defined as to precisely
> what it *meant*, especially in terms of the formal semantics.
As I understand it, SML existed long before Will's paper, had a formal
semantics published before Will's paper and required what Will
calls "proper tail recursion" and everyone else calls TCO. Moreover, I
doubt SML was the first.
> That was the contribution of Clinger's PLDI 1998 paper, especially
> defining it in terms of the "safe for space" criterion (which, as he
> freely notes, is essentially the same definition as that proposed by
> Morrisett & Harper, reference [MH97] in Clinger's paper). You should
> actually read it before dismissing it so cavalierly.
I have read the paper. The sole purpose of Will's paper seems to be to
define his own nomenclature but, AFAICT, that nomenclature was never
adopted, presumably because others already had conventional nomenclature
(tail recursion, tail calls and tail call optimization).
The only question in my mind is whether Scheme introduces some ambiguity
that would not have been present with other languages like MLs.
--
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
http://www.ffconsultancy.com/?u
Jon Harrop wrote:
> As I understand it, SML existed long before Will's paper, had a formal
> semantics published before Will's paper and required what Will
> calls "proper tail recursion"
No. The formal semantics of Standard ML did not require
space-efficient tail calls. SFAIR, the formal semantics
says practically nothing about the core efficiency of
implementations, and space-efficient tail calls are all
about asymptotic space efficiency.
Furthermore the formal semantics of Standard ML was not
even published until 1990, long after the Scheme standards
had begun to state that requirement.
Scheme was apparently the first language to require proper
tail recursion. IEEE Standard 1178-1990, section 1.1, says
Implementations of Scheme are required to be
properly tail recursive [4].
where [4] is a reference to the RRRS of 1985.
Steele and Sussman's papers, and SICP, had already stated
the requirement for space-efficient tail calls in papers
dating back to 1975 (which, IIRC, is also the year in which
Cardelli and others first described ML; Standard ML came
later). Sussman seems to have invented the phrase "proper
tail recursion", to which he resorted after his earlier
term, "tail recursion", had become hopelessly corrupted by
people who didn't understand its full generality.
> and everyone else calls TCO.
As explained in my PLDI 1998 paper you claim to have read,
proper tail recursion is a much stronger property than most
of the things people call tail call optimization.
> Moreover, I doubt SML was the first.
Now there's a convincing citation!
Will
William D Clinger wrote:
> Steele and Sussman's papers, and SICP, had already stated
> the requirement for space-efficient tail calls in papers
> dating back to 1975...
Then why did you republish the definition under a different name 23 years
later?
>> and everyone else calls TCO.
>
> As explained in my PLDI 1998 paper you claim to have read,
> proper tail recursion is a much stronger property than most
> of the things people call tail call optimization.
Your paper did not define "most of the things people call tail call
optimization" and the sources to compilers (e.g. Moscow ML 1.03 from 1994,
CAML Light 0.74 from 1997 and OCaml 1.07 from 1997) that predate your paper
and discussions from before then make it quite clear that people were
already using today's conventional nomenclature to refer to what you later
tried to redefine as "proper tail recursion" but your terminology never
caught on and everyone is still using the same definitions they were before
1998 without issue.
So if Sussman managed to confuse his students about tail calls then that
confusion did not leak out into the wider functional programming community.
--
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
http://www.ffconsultancy.com/?u
This all started when Jon Harrop incorrectly stated that
"Trampolines...only handle a few special cases of tail
calls."
I corrected his misstatement, but he appears determined
to achieve some kind of revenge by imposing his favorite
terminology upon the Lisp world and especially the Scheme
community, which is where most of these concepts were
popularized in the first place.
Jon Harrop quoting me:
> > Steele and Sussman's papers, and SICP, had already stated
> > the requirement for space-efficient tail calls in papers
> > dating back to 1975...
>
> Then why did you republish the definition under a different name 23 years
> later?
Sussman was already using the phrase "proper tail recursion"
by 1980. By 1985, the de facto Scheme standard used that
phrase to state its requirements. In 1990, IEEE Standard
1178 used exactly that same phrase, citing the 1985 document.
In my PLDI 1998 paper, I was careful to use the terminology
that had become established within the Scheme community and
had been used in the relevant standards.
> > As explained in my PLDI 1998 paper you claim to have read,
> > proper tail recursion is a much stronger property than most
> > of the things people call tail call optimization.
>
> Your paper did not define "most of the things people call tail call
> optimization"
I see you never finished reading the first paragraph of my
abstract. Its second paragraph draws a clear distinction
between proper tail recursion and tail call optimization:
Proper tail recursion is not the same as ad hoc tail
call optimization in stack-based languages. Proper
tail recursion often precludes stack allocation of
variables, but yields a well-defined asymptotic space
complexity that can be relied upon by portable programs.
Note also that, prior to my paper, most compiler writers
hadn't yet figured out that proper tail recursion was not
always compatible with stack allocation of variables.
Some had, of course.
> and the sources to compilers (e.g. Moscow ML 1.03 from 1994,
> CAML Light 0.74 from 1997 and OCaml 1.07 from 1997) that predate your paper
If priority is such a concern for you, then why aren't you
mentioning the Scheme compilers I wrote in 1983 and 1991?
Look, I have never claimed to have invented this concept or
to have been one of the first to implement space-efficient
tail recursion. My only claim to fame in this is that my
PLDI 1998 gave the first implementation-independent formal
definition of the concept.
I wasn't the first because I'm brilliant. I was the first
because most researchers understood that a formal definition
would be fairly trivial but tedious, and didn't want to take
the time to do it. The main reason I did it was I got tired
of arguing with people who alleged that the concept had no
implementation-independent meaning.
As was explicitly acknowledged in my paper, and has already
been noted within this thread, my definition of proper tail
recursion "is essentially the same as the definition proposed
by Morrissett and Harper", but Morrissett and Harper had
never formalized their informal definition. Formalization
was the main contribution of my paper; I did not introduce
new terminology for the main concepts.
Morrissett and Harper are as firmly planted within the ML
community as anyone. Although "proper tail recursion" was
the established phrase within the Scheme community, and
was certainly understood throughout the ML community as
well, Morrissett and Harper's paper happened to use the
phrase "tail call elimination", which is similar to the
phrase upon which you are now insisting: "tail call
optimization".
I did not use "tail call optimization" to refer to this
concept in my PLDI paper because, in the wider programming
languages community served by PLDI, the word "optimization"
implies that the optimization is optional. In Scheme,
proper tail recursion is not optional; it is required.
Let it be noted that you had not used the phrase "tail
call optimization" early in this thread, when you insisted
that my choice of terms was between "tail recursion" and
"tail calls". I did not pick either, because both of
those terms are widely used to refer to concepts that
are much weaker than "proper tail recursion", and I had
no way of knowing what you happened to mean by those
terms.
> and discussions from before then make it quite clear that people were
> already using today's conventional nomenclature to refer to what you later
> tried to redefine as "proper tail recursion" but your terminology never
> caught on and everyone is still using the same definitions they were before
> 1998 without issue.
You don't seem to realize that the history of this concept
has been rife with terminological confusion. The very first
sentence of my introduction explicitly refers to the variety
of things that have been called "tail recursion".
The second second of my introduction defines "tail calls" in
the syntactic sense that has become standard within the FP
community. That standard meaning is *not* the meaning upon
which you have been insisting, which just goes to show how
confusing the terminology remains to this day.
Will
William D Clinger wrote:
> This all started when Jon Harrop incorrectly stated that
> "Trampolines...only handle a few special cases of tail
> calls."
I wrote that specifically in the context of Clojure, where it is true.
> I corrected his misstatement...
You addressed a strawman argument.
> but he appears determined to achieve some kind of revenge
I am just trying to get straight answers but you keep monologuing about
irrelevancies.
> by imposing his favorite
> terminology upon the Lisp world and especially the Scheme
> community, which is where most of these concepts were
> popularized in the first place.
Popular among a dozen people, perhaps.
> Jon Harrop quoting me:
>> > Steele and Sussman's papers, and SICP, had already stated
>> > the requirement for space-efficient tail calls in papers
>> > dating back to 1975...
>>
>> Then why did you republish the definition under a different name 23 years
>> later?
>
> Sussman was already using the phrase "proper tail recursion"
> by 1980.
Then why did you just use the different phrase "space-efficient tail calls"
in your last paragraph? A phrase that gets only 2 Google hits (excluding
you talking about it here).
> By 1985, the de facto Scheme standard used that
> phrase to state its requirements. In 1990, IEEE Standard
> 1178 used exactly that same phrase, citing the 1985 document.
>
> In my PLDI 1998 paper, I was careful to use the terminology
> that had become established within the Scheme community and
> had been used in the relevant standards.
You said:
After reading them, you would have a better understanding
of what "proper tail recursion" means in languages such
as Scheme and ML.
but "proper tail recursion" is not the conventional terminology in ML and,
consequently, the references are only confusing in that context.
>> > As explained in my PLDI 1998 paper you claim to have read,
>> > proper tail recursion is a much stronger property than most
>> > of the things people call tail call optimization.
>>
>> Your paper did not define "most of the things people call tail call
>> optimization"
>
> I see you never finished reading the first paragraph of my
> abstract. Its second paragraph draws a clear distinction
> between proper tail recursion and tail call optimization:
>
> Proper tail recursion is not the same as ad hoc tail
> call optimization in stack-based languages. Proper
> tail recursion often precludes stack allocation of
> variables, but yields a well-defined asymptotic space
> complexity that can be relied upon by portable programs.
As I said, your paper did not define "most of the things people call tail
call optimization".
>> and the sources to compilers (e.g. Moscow ML 1.03 from 1994,
>> CAML Light 0.74 from 1997 and OCaml 1.07 from 1997) that predate your
>> paper
>
> If priority is such a concern for you, then why aren't you
> mentioning the Scheme compilers I wrote in 1983 and 1991?
I cited those compilers because of the terminology used in their sources,
not because they are old.
> Look, I have never claimed to have invented this concept or
> to have been one of the first to implement space-efficient
> tail recursion. My only claim to fame in this is that my
> PLDI 1998 gave the first implementation-independent formal
> definition of the concept.
Sure.
> I wasn't the first because I'm brilliant.
So now you're "brilliant". ;-)
> I was the first
> because most researchers understood that a formal definition
> would be fairly trivial but tedious, and didn't want to take
> the time to do it. The main reason I did it was I got tired
> of arguing with people who alleged that the concept had no
> implementation-independent meaning.
How could anyone justify that the concept had no implementation-independent
meaning?
> As was explicitly acknowledged in my paper, and has already
> been noted within this thread, my definition of proper tail
> recursion "is essentially the same as the definition proposed
> by Morrissett and Harper", but Morrissett and Harper had
> never formalized their informal definition. Formalization
> was the main contribution of my paper; I did not introduce
> new terminology for the main concepts.
But you did not mention that alternative terminology existing outside
Scheme, which would have been helpful.
> Morrissett and Harper are as firmly planted within the ML
> community as anyone. Although "proper tail recursion" was
> the established phrase within the Scheme community, and
> was certainly understood throughout the ML community as
> well, Morrissett and Harper's paper happened to use the
> phrase "tail call elimination", which is similar to the
> phrase upon which you are now insisting: "tail call
> optimization".
Right.
> I did not use "tail call optimization" to refer to this
> concept in my PLDI paper because, in the wider programming
> languages community served by PLDI, the word "optimization"
> implies that the optimization is optional. In Scheme,
> proper tail recursion is not optional; it is required.
Ok.
> Let it be noted that you had not used the phrase "tail
> call optimization" early in this thread, when you insisted
> that my choice of terms was between "tail recursion" and
> "tail calls". I did not pick either, because both of
> those terms are widely used to refer to concepts that
> are much weaker than "proper tail recursion", and I had
> no way of knowing what you happened to mean by those
> terms.
Tail recursion can certainly be interpreted more weakly but how can tail
calls be?
>> and discussions from before then make it quite clear that people were
>> already using today's conventional nomenclature to refer to what you
>> later tried to redefine as "proper tail recursion" but your terminology
>> never caught on and everyone is still using the same definitions they
>> were before 1998 without issue.
>
> You don't seem to realize that the history of this concept
> has been rife with terminological confusion.
That confusion seems to be almost entirely confined to the Scheme and Lisp
communities though.
> The very first sentence of my introduction explicitly refers to the
> variety of things that have been called "tail recursion".
I don't contest that but tail calls and TCO (or TCE) seem well defined.
> The second second of my introduction defines "tail calls" in
> the syntactic sense that has become standard within the FP
> community. That standard meaning is *not* the meaning upon
> which you have been insisting, which just goes to show how
> confusing the terminology remains to this day.
Can you explain exactly what the difference is?
--
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
http://www.ffconsultancy.com/?u
Jon Harrop wrote:
> but "proper tail recursion" is not the conventional terminology in ML and,
> consequently, the references are only confusing in that context.
This is not comp.lang.ml.
The ML programmers I know---people like Bob Harper, Greg
Morrissett, David McQueen, Andrew Appel, Matthias Blume,
Olivia Danvy---are quite familiar with the phrase "proper
tail recursion". They are also quite prominent within
the ML community; it could be that the ML programmers you
hang out with are not as knowledgeable.
> As I said, your paper did not define "most of the things people call tail
> call optimization".
My paper made a clear distinction between proper tail
recursion and tail call optimization, beginning with the
second paragraph of its abstract.
> So now you're "brilliant". ;-)
If you say so. I didn't.
> How could anyone justify that the concept had no implementation-independent
> meaning?
People can say whatever they want, no matter how foolish.
In the mid-1990s, however, several leading researchers
correctly noted that no one had ever actually written
down a formal, implementation-dependent definition of
proper tail recursion, and expressed doubt concerning
whether it could be done. It most certainly could not
have been done by trying to formalize the notion as it
was being explained by the majority of posters to Usenet
newsgroups.
> But you did not mention that alternative terminology existing outside
> Scheme, which would have been helpful.
As noted by my previous post, the very first sentence of
my introduction explicitly referred to various meanings
that were being given to exactly the same phrases. You
have not yet been able to give a single example of a
specific name for the concept that was in widespread use
but does not appear somewhere within my paper. (I gave
an example, but you did not.) In particular, my paper
specifically mentions "tail calls" and "tail call
optimization", drawing a constrast between widespread
meanings of those phrases and proper tail recursion.
> Tail recursion can certainly be interpreted more weakly but how can tail
> calls be?
Tail calls are unambiguously syntactic, but you yourself,
in this very thread, have used "tail calls" as though it
were something other than a syntactic concept.
> I don't contest that but tail calls and TCO (or TCE) seem well defined.
You are mistaken.
> > The second second of my introduction defines "tail calls" in
> > the syntactic sense that has become standard within the FP
> > community. That standard meaning is *not* the meaning upon
> > which you have been insisting, which just goes to show how
> > confusing the terminology remains to this day.
>
> Can you explain exactly what the difference is?
Yes. In fact, George Neuner and I have already done so
earlier in this thread. I have also cited the formal
definitions of "tail call" that appear in R5RS 3.5, R6RS
11.20, and in my PLDI 1998 paper. If you were sincerely
interested in learning the difference between tail calls
and proper tail recursion, you would have actually read
one of those references by now.
Will
William D Clinger wrote:
> Jon Harrop wrote:
>> but "proper tail recursion" is not the conventional terminology in ML
>> and, consequently, the references are only confusing in that context.
>
> This is not comp.lang.ml.
You explicitly stated "ML".
>> As I said, your paper did not define "most of the things people call tail
>> call optimization".
>
> My paper made a clear distinction between proper tail
> recursion and tail call optimization, beginning with the
> second paragraph of its abstract.
Your paper did not define TCO so its claim that they are distinct is
meaningless.
>> But you did not mention that alternative terminology existing outside
>> Scheme, which would have been helpful.
>
> As noted by my previous post, the very first sentence of
> my introduction explicitly referred to various meanings
> that were being given to exactly the same phrases. You
> have not yet been able to give a single example of a
> specific name for the concept that was in widespread use
> but does not appear somewhere within my paper. (I gave
> an example, but you did not.) In particular, my paper
> specifically mentions "tail calls" and "tail call
> optimization", drawing a constrast between widespread
> meanings of those phrases and proper tail recursion.
Your paper made the claim without justification. Where is the evidence of
these "widespread meanings"?
>> Tail recursion can certainly be interpreted more weakly but how can tail
>> calls be?
>
> Tail calls are unambiguously syntactic, but you yourself,
> in this very thread, have used "tail calls" as though it
> were something other than a syntactic concept.
Can you be more specific?
>> I don't contest that but tail calls and TCO (or TCE) seem well defined.
>
> You are mistaken.
Can you substantiate that?
>> > The second second of my introduction defines "tail calls" in
>> > the syntactic sense that has become standard within the FP
>> > community. That standard meaning is *not* the meaning upon
>> > which you have been insisting, which just goes to show how
>> > confusing the terminology remains to this day.
>>
>> Can you explain exactly what the difference is?
>
> Yes.
Wonderful.
> In fact, George Neuner and I have already done so
> earlier in this thread. I have also cited the formal
> definitions of "tail call" that appear in R5RS 3.5, R6RS
> 11.20, and in my PLDI 1998 paper. If you were sincerely
> interested in learning the difference between tail calls
> and proper tail recursion, you would have actually read
> one of those references by now.
They only describe half of your inequality. What *exactly* does your own
phrase "the meaning upon which you have been insisting" mean?
--
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
http://www.ffconsultancy.com/?u
Jon Harrop wrote:
> Your paper did not define TCO so its claim that they
> are distinct is meaningless.
If that were so, then your claim that TCO is the same
as proper tail recursion would also be meaningless,
because you have not defined TCO within this thread.
BTW, did you notice that the second reply to your
inquiry over in comp.lang.functional referred to
"proper tail recursion"? If functional programmers
aren't familiar with that phrase, then why are they
using it in comp.lang.functional?
> Where is the evidence of these "widespread meanings"?
> Can you be more specific?
> Can you substantiate that?
Yes.
Since your argument has degenerated into a dispute
concerning the relative popularity of various phrases
with various meanings, we might as well use Google
and Wikipedia to sample current usage.
Googling "proper tail recursion"+"Standard ML" turns
up over 350 hits. A Google search on
"proper tail recursion"+("Javascript"OR"ECMAScript")
turns up 750 hits. As it happens, the committee
that's drafting ECMAScript Edition 4 gave serious
consideration to requiring proper tail recursion,
although some members of that committee prefer to
refer to it as "proper tail calls" (e.g. [1]).
On the other hand, a Google search on "tail call
optimization" turns up about 12,000 hits. The top
hit is a Wikipedia article that contains two occurrences
of the phrase "properly tail recursive implementation"
and refers to "proper tail recursion optimization" in
connection with Scheme, which is evidently a Wikipedian
corruption of "proper tail recursion" [2]. That same
Wikipedia article also defines "tail call" exactly as
it was defined within my PLDI 1998 paper, and also
links to a separate Wikipedia article on "tail call"
that gives an equivalent but less formal definition [3].
Those two Wikipedia articles define "tail call" as a
syntactic concept; a tail call is a tail call even if
it is not optimized. That differs from the meaning
you had attached to "tail calls" earlier in this thread.
That proves that "tail call" means different things to
different people.
Looking at the other 9 hits on the first page returned
by a Google search on "tail call optimization", I find
that at least 3 use the phrase to mean something less
general than proper tail recursion [4,5,6]. A fourth
says TCO is a generalization of "tail recursion" [7].
Another talks about "proper tail calls", and doesn't
even mention TCO or the word "optimization" [8].
That proves that different meanings are being attached
to those phrases by web pages that Google's search
algorithm regards as the most relevant pages for those
phrases.
> They only describe half of your inequality. What *exactly*
> does your own phrase "the meaning upon which you have been
> insisting" mean?
It means this: If you don't know what you meant by
your own phrase, then I can't help you.
Will
[1] http://blogs.adobe.com/fcheng/2008/01/proper_tail_calls_a_definition.html
[2] http://en.wikipedia.org/wiki/Tail_recursion
[3] http://en.wikipedia.org/wiki/Tail_call
[4] http://www.lispworks.com/documentation/lcl50/aug/aug-51.html
[5] http://code.activestate.com/recipes/474088/
[6] http://wiki.tcl.tk/1348
[7] http://c2.com/cgi/wiki?TailCallOptimization
[8] http://www.lua.org/pil/6.3.html
William D Clinger <········@yahoo.com> writes:
> Jon Harrop wrote:
>
>> [...some reply with spammer's homepage as signature...]
>
> [some reply which probably has cost him some time]
FYI: Since JH is a well-known spammer, he will probably continue replying
to your posts as long as he is allowed to add the signature with his
company's webpage to his posts - that is, forever.
Nicolas
Nicolas Neuss wrote:
> FYI: Since JH is a well-known spammer, he will probably continue replying
> to your posts as long as he is allowed to add the signature with his
> company's webpage to his posts - that is, forever.
Yes. Just talking to you earns me huge sums of money. That is certainly not
a paranoid delusion. You should probably never substantiate anything for
that reason.
--
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
http://www.ffconsultancy.com/?u
On Feb 4, 2:11 pm, Jon Harrop <····@ffconsultancy.com> wrote:
> Nicolas Neuss wrote:
> > FYI: Since JH is a well-known spammer, he will probably continue replying
> > to your posts as long as he is allowed to add the signature with his
> > company's webpage to his posts - that is, forever.
>
> Yes. Just talking to you earns me huge sums of money. That is certainly not
> a paranoid delusion. You should probably never substantiate anything for
> that reason.
>
> --
> Dr Jon D Harrop, Flying Frog Consultancy Ltd. [URL OMITTED]
Your response would have more credibility if you had omitted the URL
in your signature.
As it is, you have contributed yet another instance of that URL to
comp.lang.lisp without contributing any useful discussion.
···············@gmail.com wrote:
> On Feb 4, 2:11 pm, Jon Harrop <····@ffconsultancy.com> wrote:
>> Dr Jon D Harrop, Flying Frog Consultancy Ltd. [URL OMITTED]
>
> Your response would have more credibility if you had omitted the URL
> in your signature.
You should be able to estimate the monetary value to me of my posts here by
yourself without depending upon anything I have said or done. You only have
to get within two orders of magnitude of my own estimate to see that
Nicolas' argument is absurd.
This is a great exercise for all academics with no industrial experience who
ride on the unjustified assumption that everything they say or do is of
tremendous worth whilst living off taxes.
--
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
http://www.ffconsultancy.com/?u
On 4 Feb., 22:09, Jon Harrop <····@ffconsultancy.com> wrote:
> ···············@gmail.com wrote:
> > On Feb 4, 2:11 pm, Jon Harrop <····@ffconsultancy.com> wrote:
> >> Dr Jon D Harrop, Flying Frog Consultancy Ltd. [URL OMITTED]
>
> > Your response would have more credibility if you had omitted the URL
> > in your signature.
>
> You should be able to estimate the monetary value to me of my posts here by
> yourself without depending upon anything I have said or done. You only have
> to get within two orders of magnitude of my own estimate to see that
> Nicolas' argument is absurd.
>
> This is a great exercise for all academics with no industrial experience who
> ride on the unjustified assumption that everything they say or do is of
> tremendous worth whilst living off taxes.
I have no idea what the monetary value of your spamming of
comp.lang.lisp is.
Speaking for me, I bought lots of books and software over the years,
but none
from your business. Given your current offerings and your marketing
approach
by spamming, I expect this not to change anytime soon.
······@corporate-world.lisp.de wrote:
> I have no idea what the monetary value of your spamming of
> comp.lang.lisp is.
Estimate it and you will see that the remainder of your post was
ill-founded.
--
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
http://www.ffconsultancy.com/?u
On Feb 4, 4:36 pm, Jon Harrop <····@ffconsultancy.com> wrote:
> ······@corporate-world.lisp.de wrote:
> > I have no idea what the monetary value of your spamming of
> > comp.lang.lisp is.
>
> Estimate it and you will see that the remainder of your post was
> ill-founded.
>
> --
> Dr Jon D Harrop, Flying Frog Consultancy Ltd. [URL OMITTED]
You are the one who brought monetary concerns into the discussion.
The plain fact is that you seem to spend an awful lot of time posting
articles to comp.lang.lisp that contain little or no Lisp-relevant
content, except to disparage it, and include even long discussions
with obvious nutcases such as Xah Lee.
Whether monetary or not, it is only logical to assume you that you
have *some* motivation.
Your history of posting indicates your motivations do not include Lisp
or even useful discussion. The one common element to your posts,
however, is that they *all*, without fail, contain a URL pointing to
your consultancy.
By process of elimination, the inclusion of that URL into the
comp.lang.lisp archives seems to be the only possible motivation for
your efforts. That deduction is independent of the actual profits you
realize from those efforts.
···············@gmail.com wrote:
> On Feb 4, 4:36 pm, Jon Harrop <····@ffconsultancy.com> wrote:
>> ······@corporate-world.lisp.de wrote:
>> > I have no idea what the monetary value of your spamming of
>> > comp.lang.lisp is.
>>
>> Estimate it and you will see that the remainder of your post was
>> ill-founded.
>>
>> --
>> Dr Jon D Harrop, Flying Frog Consultancy Ltd. [URL OMITTED]
>
> You are the one who brought monetary concerns into the discussion.
>
> The plain fact is that you seem to spend an awful lot of time posting
> articles to comp.lang.lisp that contain little or no Lisp-relevant
> content, except to disparage it, and include even long discussions
> with obvious nutcases such as Xah Lee.
>
> Whether monetary or not, it is only logical to assume you that you
> have *some* motivation.
>
> Your history of posting indicates your motivations do not include Lisp
> or even useful discussion. The one common element to your posts,
> however, is that they *all*, without fail, contain a URL pointing to
> your consultancy.
>
> By process of elimination, the inclusion of that URL into the
> comp.lang.lisp archives seems to be the only possible motivation for
> your efforts. That deduction is independent of the actual profits you
> realize from those efforts.
Can you really not see that there is no logic to what you are saying? For
example, my posts also contain my name but you silently "eliminated" that
during your "deduction".
--
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
http://www.ffconsultancy.com/?u
On 2009-02-04, ···············@gmail.com <············@gmail.com> wrote:
> On Feb 4, 2:11 pm, Jon Harrop <····@ffconsultancy.com> wrote:
>> Nicolas Neuss wrote:
>> > FYI: Since JH is a well-known spammer, he will probably continue replying
>> > to your posts as long as he is allowed to add the signature with his
>> > company's webpage to his posts - that is, forever.
>>
>> Yes. Just talking to you earns me huge sums of money. That is certainly not
>> a paranoid delusion. You should probably never substantiate anything for
>> that reason.
>>
>> --
>> Dr Jon D Harrop, Flying Frog Consultancy Ltd. [URL OMITTED]
>
> Your response would have more credibility if you had omitted the URL
> in your signature.
What does someone's perfectly netiquette-conforming signature have to do
with their credibility?
If that's a fair attack, than how about this: you would have more credibility
if you used an actual newsreader to post news, instead of a bad
browser-built-in mail client with bolted-on NNTP support.
A proper newsreading program can hide the signatures from your eyes,
and avoids quoting signatures when generating the followup.
Jon's signature is correctly delimited by the characters "-- ", and is not
longer than four lines.
You have no case.
On Feb 4, 4:53 pm, Kaz Kylheku <········@gmail.com> wrote:
> On 2009-02-04, ···············@gmail.com <············@gmail.com> wrote:
>
> > On Feb 4, 2:11 pm, Jon Harrop <····@ffconsultancy.com> wrote:
> >> Nicolas Neuss wrote:
> >> > FYI: Since JH is a well-known spammer, he will probably continue replying
> >> > to your posts as long as he is allowed to add the signature with his
> >> > company's webpage to his posts - that is, forever.
>
> >> Yes. Just talking to you earns me huge sums of money. That is certainly not
> >> a paranoid delusion. You should probably never substantiate anything for
> >> that reason.
>
> >> --
> >> Dr Jon D Harrop, Flying Frog Consultancy Ltd. [URL OMITTED]
>
> > Your response would have more credibility if you had omitted the URL
> > in your signature.
>
> What does someone's perfectly netiquette-conforming signature have to do
> with their credibility?
>
> If that's a fair attack, than how about this: you would have more credibility
> if you used an actual newsreader to post news, instead of a bad
> browser-built-in mail client with bolted-on NNTP support.
>
> A proper newsreading program can hide the signatures from your eyes,
> and avoids quoting signatures when generating the followup.
>
> Jon's signature is correctly delimited by the characters "-- ", and is not
> longer than four lines.
>
> You have no case.
My point was the evidence we have for Dr. Harrop's motivations from
his posts. These posts do not contain useful discussions about Lisp,
and, sometimes, contain no useful discussion at all.
However, all of them contain his URL. Regardless of how *I* read news,
search engines presumably include the signature in their archives, and
perhaps use it to increase the weight given to the Flying Amphibian's
consultancy in Lisp-related searches. (In fact, his name shows up in
the top 20 results of "Lisp programming consultancy" for me on Google)
His inclusion of the URL in otherwise useless discussions is what
offers evidence that he wishes to increase the frequency of that URL
without much regard for any other contribution. That is characteristic
of a spammer.
If he wished to rebut the conclusion that the URL is important to him,
he could have written a post that either contained useful information
or omitted his URL. Instead, he produced yet another content-free post
with the URL, adding evidence for the spammer hypothesis, instead of
rebutting it.
It doesn't bother me, because I can use my experience reading his
posts to know that his consultancy services will be useless, no matter
how high in my search results he appears.
···············@gmail.com wrote:
> If he wished to rebut the conclusion...
The onus is on you to prove my guilt, not on me to prove my innocence.
--
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
http://www.ffconsultancy.com/?u
Jon Harrop wrote:
> ···············@gmail.com wrote:
>> If he wished to rebut the conclusion...
>
> The onus is on you to prove my guilt, not on me to prove my innocence.
>
Jon, it's about etiquette, not judgement. Off course no one would put
you in prison for posting non-lisp stuff to comp.lang.lisp
Please, continue to do so, as it seems there is nothing stopping you
from doing it!
Please, continue, and let us pray that you get bored or tired.
From all your readings - I've got only one thing: you would like ML
system with the capabilities of Lisp - where you can develop iteratively
and have restartable exceptions. Why don't state it upfront, and then
say something along the lines - I would like to see this in ML, or even
say - ML's weak points are here and there (you obviously state such weak
points in ML related groups, but you are not doing that in comp.lang.lisp)
Cheers!
Honestly I might buy a book from you, because I know you from here...
But please...
Dimiter "malkia" Stanev wrote:
> From all your readings - I've got only one thing: you would like ML
> system with the capabilities of Lisp - where you can develop iteratively
> and have restartable exceptions. Why don't state it upfront, and then
> say something along the lines - I would like to see this in ML, or even
> say - ML's weak points are here and there (you obviously state such weak
> points in ML related groups, but you are not doing that in comp.lang.lisp)
You would get combinatorial complaint explosion. :-)
I have documented problems with other languages elsewhere though, as you
say. Here are some problems with the current release of F# that I have
enumerated:
http://stackoverflow.com/questions/161125/whats-wrong-with-f
OCaml also has some deficiencies that have been addressed in F#:
http://groups.google.com/group/fa.caml/msg/a3fb09157a21be6a
--
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
http://www.ffconsultancy.com/?u
On 2009-02-04, Kaz Kylheku <········@gmail.com> wrote:
> If that's a fair attack, than how about this: you would have more credibility
> if you used an actual newsreader to post news, instead of a bad
> browser-built-in mail client with bolted-on NNTP support.
Oops, pardon the mistake, even worse: Google Groups. :) My condolences.
How can anyone complain about spam, yet use Google Groups? LOL!
Here is what the current list of topics looks like, when viewed through Google
Groups:
programming by evolution?
..SELL NIKE SHOES AIR MAX 90 NEW 35$
packages revisited
International Lisp Conference - website up and registrations open
London Office Administration and Bulk Trade System
& 1 Samuel 25v42
Movado SL Watch, Best Wristwatch
Baume & Mercier Hampton City Watch, Best Wristwatch
Cartier Roadster Watch, Best Wristwatch
Cartier Hard to Find Cartier Watch, Best Wristwatch
Technomarine Redsquare Watch, Best Wristwatch
TAG Heuer Formula One F1 & Indy 500 Watch, Best Wristwatch
Movado Sapphire Watch, Best Wristwatch
Jaeger LeCoultre Reverso Grande Date Watch, Best Wristwatch
www.stefsclothes.com cheap sell air max shoes, nike shoes,ugg shoes, ...
about pushnew
Safe to get address of va_list function parameter?
project emacs2010
random_shuffle
Bitwise 2009 ($5000 prize money)
free hardcore fuck movie, extreme hardcore fucking, blonde lesbian orgasm
free old sex movie, drunk teen video, free anime cartoon porn video
nude teen virgins, latina lesbian sexy, free adult classic movie
help with NLP library
++ Hilary Clinton Sex Scandal
cl-user google map
COMPILE-FILE
C-Graph
ICFP09 Final CFP
Baby Spice Naked Photo Shoot
Here is what it looks like on my news server when I thread the most recent 500
articles:
& 1 Samuel 25v42
about pushnew
amusing read
ANN: a system browser for Emacs
cl-user google map
COMPILE-FILE without a file...
emacs lisp programming help
Emacs vs VI, the final solution
Fexprs more flexible, powerful, easier to
Function Application is not Currying
help with NLP library
How do I shorten or split this function
how to tokenize a string in Lisp
International Lisp Conference - website up
Is Javascript a Lisp?
JOB: Postdoc in bioinformatics
JVM vs CLR
Kent Pitman's essay on why lisp doesn't ha
Learning Lisp the hard way
Lisp as an *external* DSL for a J2EE app?
making a virtual file system
Mathematica 7 compares to other languages
packages revisited
Please Help!!! Lisp Newbie.
programatically constructing the #'(setf acces
programming by evolution?
project emacs2010
random_shuffle
Safe to get address of va_list function pa
Seeking computer-programming job (Sunnyval
Tokyo Japan LOCAL: Satuday 28 February 200
What gives you power in CL, that you don't
why don't people make the ultimate browser
Writing a Windows Service in Common Lisp
Where is the porn, wristwatches, shoes, Hilary Clinton Sex Scandal?
Pretty damn stupid to be complaining about Jon Harrop's signature being spam,
while willingly subjecting yourself to Google Groups.
On 4 Feb, 00:11, Jon Harrop <····@ffconsultancy.com> wrote:
> William D Clinger wrote:
> > Jon Harrop wrote:
> >> but "proper tail recursion" is not the conventional terminology in ML
> >> and, consequently, the references are only confusing in that context.
>
> > This is not comp.lang.ml.
>
> You explicitly stated "ML".
>
> >> As I said, your paper did not define "most of the things people call tail
> >> call optimization".
>
> > My paper made a clear distinction between proper tail
> > recursion and tail call optimization, beginning with the
> > second paragraph of its abstract.
>
> Your paper did not define TCO so its claim that they are distinct is
> meaningless.
>
> >> But you did not mention that alternative terminology existing outside
> >> Scheme, which would have been helpful.
>
> > As noted by my previous post, the very first sentence of
> > my introduction explicitly referred to various meanings
> > that were being given to exactly the same phrases. You
> > have not yet been able to give a single example of a
> > specific name for the concept that was in widespread use
> > but does not appear somewhere within my paper. (I gave
> > an example, but you did not.) In particular, my paper
> > specifically mentions "tail calls" and "tail call
> > optimization", drawing a constrast between widespread
> > meanings of those phrases and proper tail recursion.
>
> Your paper made the claim without justification. Where is the evidence of
> these "widespread meanings"?
>
> >> Tail recursion can certainly be interpreted more weakly but how can tail
> >> calls be?
>
> > Tail calls are unambiguously syntactic, but you yourself,
> > in this very thread, have used "tail calls" as though it
> > were something other than a syntactic concept.
>
> Can you be more specific?
A Tail call is a procedure invocation that appear as the last
operation of a procedure. They either never return or return a value
that becomes the return value of the caller procedure.
Proper tail recursion, or bounded-space tail recursion, is a semantic
property of some languages, notably Scheme, which guarantees that if a
procedure tail calls itself either directly or trough other tail-
called procedures, and if each procedure in the tail-call chain
evaluates in bounded space, then the whole chain evaluates in bounded
space.
Tail call optimization is an implementation technique of tail calls on
stack-based architectures that removes the stack frame of the caller
procedure when the callee is invoked.
Taill call optimization can be used to implement proper tail
recursion, but it isn't required.
Chicken Scheme, for instance, provides proper tail recursion without
implementing it as tail call optimization.
<snip>
Vend <······@virgilio.it> wrote:
+---------------
| Tail call optimization is an implementation technique of tail calls on
| stack-based architectures that removes the stack frame of the caller
| procedure when the callee is invoked.
|
| Taill call optimization can be used to implement proper tail
| recursion, but it isn't required.
| Chicken Scheme, for instance, provides proper tail recursion without
| implementing it as tail call optimization.
+---------------
Small quibble: Chicken Scheme *does* "remove the stack frame of the
caller procedure when the callee is invoked", just not at the time
of the call. Instead, all of the outstanding stack frames of calling
procedures are removed "en masse" in one shot when a garbage collection
is triggered by the C stack growing too large... which (after moving
live data out of the stack into the heap) finishes with a "longjmp()"
far up the stack [which is what actually removes the caller frames].
But you are correct in principle that TCO at the call site per se
is not required for unbounded safe-for-space tail-call chains, e.g.,
a trampoline loop can provide the latter without the former.
-Rob
-----
Rob Warnock <····@rpw3.org>
627 26th Avenue <URL:http://rpw3.org/>
San Mateo, CA 94403 (650)572-2607
On 5 Feb, 01:23, ····@rpw3.org (Rob Warnock) wrote:
> Vend <······@virgilio.it> wrote:
>
> +---------------
> | Tail call optimization is an implementation technique of tail calls on
> | stack-based architectures that removes the stack frame of the caller
> | procedure when the callee is invoked.
> |
> | Taill call optimization can be used to implement proper tail
> | recursion, but it isn't required.
> | Chicken Scheme, for instance, provides proper tail recursion without
> | implementing it as tail call optimization.
> +---------------
>
> Small quibble: Chicken Scheme *does* "remove the stack frame of the
> caller procedure when the callee is invoked", just not at the time
> of the call.
I wrote "when" to mean "at the same time".
> Instead, all of the outstanding stack frames of calling
> procedures are removed "en masse" in one shot when a garbage collection
> is triggered by the C stack growing too large... which (after moving
> live data out of the stack into the heap) finishes with a "longjmp()"
> far up the stack [which is what actually removes the caller frames].
>
> But you are correct in principle that TCO at the call site per se
> is not required for unbounded safe-for-space tail-call chains, e.g.,
> a trampoline loop can provide the latter without the former.
>
> -Rob
>
> -----
> Rob Warnock <····@rpw3.org>
> 627 26th Avenue <URL:http://rpw3.org/>
> San Mateo, CA 94403 (650)572-2607
Jon Harrop schrieb:
> William D Clinger wrote:
>> This all started when Jon Harrop incorrectly stated that
>> "Trampolines...only handle a few special cases of tail
>> calls."
>
> I wrote that specifically in the context of Clojure, where it is true.
It�s very possible that you are right with this.
I would really like to see an example, so that I can try to avoide these
issues. If it is true that only some few special cases of tail calls
can be done in a stack-safe way with trampolines it means that the great
majority of the cases will run into problems with the stack.
And if that is the case it should be easy to post one (or two) small
examples, as a proof-of-concept.
Could you please post some code, be it in Clojure or some other lang,
that demonstrates this?
I would need a concrete example.
This can help me to be much more aware of problematic issues until the
JVM gets support for tail recursion.
Andr�
--
Lisp is not dead. It�s just the URL that has changed:
http://clojure.org/
André Thieme wrote:
> Could you please post some code, be it in Clojure or some other lang,
> that demonstrates this?
> I would need a concrete example.
In Scheme, the simplest example is also the simplest
way to write an infinite loop:
((lambda (x) (x x))
(lambda (x) (x x)))
That should run forever in constant space.
Simple examples are susceptible to optimizations that
work only for simple cases.
To make it harder for the compiler to recognize that
as a special case, you can write an obfuscated procedure
that acts like the identity function but is too complex
for the compiler to figure that out. Here is one
possible example, written in Scheme:
(define (hide x)
(let* ((y (list x (lambda (y) y)))
(z (reverse y)))
(if (odd? (random 2341234))
(car y)
((cadr y) (cadr z)))))
Some compilers might be able to figure that out, but
I'd be surprised if Clojure's compiler does.
Having defined hide, you can then see whether
((hide (lambda (x) ((hide x) (hide x))))
(hide (lambda (x) ((hide x) (hide x)))))
runs forever in constant space.
Will
William D Clinger <········@yahoo.com> writes:
> Andr� Thieme wrote:
>> Could you please post some code, be it in Clojure or some other lang,
>> that demonstrates this?
>> I would need a concrete example.
>
> In Scheme, the simplest example is also the simplest
> way to write an infinite loop:
>
> ((lambda (x) (x x))
> (lambda (x) (x x)))
>
> That should run forever in constant space.
>
> Simple examples are susceptible to optimizations that
> work only for simple cases.
>
> To make it harder for the compiler to recognize that
> as a special case, you can write an obfuscated procedure
> that acts like the identity function but is too complex
> for the compiler to figure that out. Here is one
> possible example, written in Scheme:
>
> (define (hide x)
> (let* ((y (list x (lambda (y) y)))
> (z (reverse y)))
> (if (odd? (random 2341234))
> (car y)
> ((cadr y) (cadr z)))))
>
> Some compilers might be able to figure that out, but
> I'd be surprised if Clojure's compiler does.
>
> Having defined hide, you can then see whether
>
> ((hide (lambda (x) ((hide x) (hide x))))
> (hide (lambda (x) ((hide x) (hide x)))))
>
> runs forever in constant space.
>
> Will
sbcl seems to run this in constant space.
clisp doesn't:
C/USER[5]> (defun hide ( x)
(let* ((y (list x (lambda (y) y)))
(z (reverse y)))
(if (oddp (random 2341234))
(car y)
(funcall (cadr y) (cadr z)))))
HIDE
C/USER[6]> (compile 'hide)
HIDE ;
NIL ;
NIL
C/USER[7]> (funcall (compile nil (lambda ()
(funcall (hide (lambda (x) (funcall (hide x) (hide x))))
(hide (lambda (x) (funcall (hide x) (hide x))))))))
*** - Program stack overflow. RESET
C/USER[8]>
--
__Pascal Bourguignon__
Andr� Thieme <······························@justmail.de> wrote:
+---------------
| Jon Harrop schrieb:
| > William D Clinger wrote:
| >> This all started when Jon Harrop incorrectly stated that
| >> "Trampolines...only handle a few special cases of tail
| >> calls."
| >
| > I wrote that specifically in the context of Clojure, where it is true.
|
| It�s very possible that you are right with this.
| I would really like to see an example, so that I can try to avoide these
| issues. If it is true that only some few special cases of tail calls
| can be done in a stack-safe way with trampolines it means that the great
| majority of the cases will run into problems with the stack.
| And if that is the case it should be easy to post one (or two) small
| examples, as a proof-of-concept.
| Could you please post some code, be it in Clojure or some other lang,
| that demonstrates this?
| I would need a concrete example.
+---------------
I don't have an example at hand that will definitely fail for you
[I use CMUCL, which agressively optimizes tail calls even between
functions across separately-compiled files], but if Clojure *does*
have a problem with proper TCO you might be able to construct an
example by, say, defining three identical functions which tail call
each other in a circle, or, if necessary to defeat some optimization,
call one of the other two pseudo-randomly, something like this:
(defun f1 (x y)
(let ((x1 (1- x))
(y1 (1+ y)))
(if (zerop x)
y
(if (zerop (random 2))
(f2 x1 y1)
(f3 x1 y1)))))
and the same, mutatis mutandis, for F2 & F3.
I was unable to get this to fail with CMUCL even with
(F1 MOST-POSITIVE-FIXNUM 0) [M-P-F is 536870911 there,
*way* larger than any reasonable stack size], even when
compiling each function separately in its own file.
But Clojure's MMV...
-Rob
p.s. You might also try explicitly allocating something in
each function, e.g.:
(defun f1 (x y z)
(declare (ignorable z))
(let ((x1 (1- x))
(y1 (1+ y))
(z1 (make-array 10)))
(if (zerop x)
y
(if (zerop (random 2))
(f2 x1 y1 z1)
(f3 x1 y1 z1)))))
Though, again, this *didn't* cause CMUCL to break, but it *did*
slow things down a lot and force me to (SETF *GC-VERBOSE* NIL)!! ;-}
-----
Rob Warnock <····@rpw3.org>
627 26th Avenue <URL:http://rpw3.org/>
San Mateo, CA 94403 (650)572-2607
Rob Warnock schrieb:
> André Thieme <······························@justmail.de> wrote:
> +---------------
> | Jon Harrop schrieb:
> | > William D Clinger wrote:
> | >> This all started when Jon Harrop incorrectly stated that
> | >> "Trampolines...only handle a few special cases of tail
> | >> calls."
> | >
> | > I wrote that specifically in the context of Clojure, where it is true.
> |
> | It’s very possible that you are right with this.
> | I would really like to see an example, so that I can try to avoide these
> | issues. If it is true that only some few special cases of tail calls
> | can be done in a stack-safe way with trampolines it means that the great
> | majority of the cases will run into problems with the stack.
> | And if that is the case it should be easy to post one (or two) small
> | examples, as a proof-of-concept.
> | Could you please post some code, be it in Clojure or some other lang,
> | that demonstrates this?
> | I would need a concrete example.
> +---------------
>
> I don't have an example at hand that will definitely fail for you
> [I use CMUCL, which agressively optimizes tail calls even between
> functions across separately-compiled files], but if Clojure *does*
> have a problem with proper TCO you might be able to construct an
> example by, say, defining three identical functions which tail call
> each other in a circle, or, if necessary to defeat some optimization,
> call one of the other two pseudo-randomly, something like this:
>
> (defun f1 (x y)
> (let ((x1 (1- x))
> (y1 (1+ y)))
> (if (zerop x)
> y
> (if (zerop (random 2))
> (f2 x1 y1)
> (f3 x1 y1)))))
>
> and the same, mutatis mutandis, for F2 & F3.
Thanks for the example.
If I do this in Clojure it indeed is not stack-safe and ends with an
Exception:
user> (defn f1 [x y]
(let [x1 (dec x)
y1 (inc y)]
(if (zero? x)
y
(if (zero? (rand-int 2))
(f2 x1 y1)
(f3 x1 y1)))))
..f2..
..f3..
user> (f1 10000 80) ==>
At around 10k calls the Exception is thrown.
However, if I would want to make such a function I would do it with a
trampoline:
user> (defn f1 [x y]
(let [x1 (dec x)
y1 (inc y)]
(if (zero? x)
y
(if (zero? (rand-int 2))
#(f2 x1 y1)
#(f3 x1 y1)))))
I added only two “#”. And now the call:
user> (trampoline f1 10000 50000) ==> 60000
Does not break anymore.
I think as long as I am writing the code myself I can’t run into stack
problems with trampolines.
The only chance I see is to have some lib function which I have to pass
my function and at the same time call it recursively. And the author of
that function must also have forgotten to write a # before his recursive
call.
André
--
On Mon, 02 Feb 2009 22:15:00 +0100, André Thieme wrote:
> If I do this in Clojure it indeed is not stack-safe and ends with an
> Exception:
> user> (defn f1 [x y]
> (let [x1 (dec x)
> y1 (inc y)]
> (if (zero? x)
> y
> (if (zero? (rand-int 2))
> (f2 x1 y1)
> (f3 x1 y1)))))
>
> ..f2..
> ..f3..
>
> user> (f1 10000 80) ==>
>
> At around 10k calls the Exception is thrown. However, if I would want to
> make such a function I would do it with a trampoline:
...
Not that this is practical for all situations, but for mutual recursion
in clojure you can also fold the functions into a single function and
dispatch on the name:
;(typed, not tested)
(defn entry [name x y]
(case [:f1
(let [x1 (dec x)
y1 (inc y)]
(if (zero? x)
y
(if (zero? (rand-int 2))
;;note the recur
(recur :f2 x1 y1)
(recur :f3 x1 y1))))]
[:f2 ...]
[:f3 ...]))
...
(entry :f1 10000 80)
--
Work consists of whatever a body is obliged to do.
Play consists of whatever a body is not obliged to do.
-- Mark Twain
On Tue, 03 Feb 2009 03:09:21 +0000, Matthew D Swank wrote:
> On Mon, 02 Feb 2009 22:15:00 +0100, André Thieme wrote:
>
>
>> If I do this in Clojure it indeed is not stack-safe and ends with an
>> Exception:
>> user> (defn f1 [x y]
>> (let [x1 (dec x)
>> y1 (inc y)]
>> (if (zero? x)
>> y
>> (if (zero? (rand-int 2))
>> (f2 x1 y1)
>> (f3 x1 y1)))))
>>
>> ..f2..
>> ..f3..
>>
>> user> (f1 10000 80) ==>
>>
>> At around 10k calls the Exception is thrown. However, if I would want
>> to make such a function I would do it with a trampoline:
>
> ...
>
> Not that this is practical for all situations, but for mutual recursion
> in clojure you can also fold the functions into a single function and
> dispatch on the name:
>
> ;(typed, not tested)
>
> (defn entry [name x y]
> (case [:f1
> (let [x1 (dec x)
> y1 (inc y)]
> (if (zero? x)
> y
> (if (zero? (rand-int 2))
> ;;note the recur
> (recur :f2 x1 y1)
> (recur :f3 x1 y1))))]
> [:f2 ...]
> [:f3 ...]))
> ...
>
> (entry :f1 10000 80)
This might work better:
(defn entry [name x y]
(case name
:f1
(let [x1 (dec x)
y1 (inc y)]
(if (zero? x)
y
(if (zero? (rand-int 2))
;;note the recur
(recur :f2 x1 y1)
(recur :f3 x1 y1))))
:f2 ...
:f3 ...))
--
You will be the last person to buy a Chrysler.
On Sat, 31 Jan 2009 09:06:09 -0800 (PST), William D Clinger
<········@yahoo.com> wrote:
>George Neuner wrote:
>> Scheme uses the term "proper tail recursion" to refer to a self
>> recursive call in tail position.
>
>No. Proper tail recursion is not limited to self tail
>calls, but is about the asymptotic space efficiency
>achieved by implementing general tail calls without
>creating new continuations unnecessarily ...
Thanks for the correction.
George
George Neuner wrote:
> On Sat, 31 Jan 2009 01:10:20 +0000, Jon Harrop <···@ffconsultancy.com>
> wrote:
>>William D Clinger wrote:
>>> Jon Harrop quoting me:
>>>> > Straightforwardly. It's okay to have multiple trampolines
>>>> > on the CLR control stack, and that doesn't interfere with
>>>> > proper tail recursion.
>>>>
>>>> Tail recursion or tail calls?
>>>
>>> The "LAMBDA: the ultimate" series of papers by Steele and
>>> Sussman would be a good place for you to start [1,2,3].
>>> After reading them, you would have a better understanding
>>> of what "proper tail recursion" means in languages such
>>> as Scheme and ML.
>>
>>Ok, you mean "tail calls".
>
> "Tail call" is more generic - it can refer to any function call
> occurring in tail position.
>
> Scheme uses the term "proper tail recursion" to refer to a self
> recursive call in tail position.
Yes. So William's proposed solution does not solve the problem.
--
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
http://www.ffconsultancy.com/?u
Jon Harrop wrote:
> Yes. So William's proposed solution does not solve the problem.
Wrong again.
Harrop apparently understands neither the generality of
proper tail recursion nor the meaning of tail calls as
defined by the relevant standards and research literature.
He also does not understand that trampolines are a fully
general technique for achieving proper tail recursion.
Will
William D Clinger wrote:
> Jon Harrop wrote:
>> Yes. So William's proposed solution does not solve the problem.
>
> Wrong again.
>
> Harrop apparently understands neither the generality of
> proper tail recursion nor the meaning of tail calls as
> defined by the relevant standards and research literature.
>
> He also does not understand that trampolines are a fully
> general technique for achieving proper tail recursion.
The only thing I understand here is the irony of you repeatedly citing
yourself in a discussion about recursion.
--
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
http://www.ffconsultancy.com/?u
Jon Harrop schrieb:
> William D Clinger wrote:
>> Jon Harrop wrote:
>>> Yes. So William's proposed solution does not solve the problem.
>> Wrong again.
>>
>> Harrop apparently understands neither the generality of
>> proper tail recursion nor the meaning of tail calls as
>> defined by the relevant standards and research literature.
>>
>> He also does not understand that trampolines are a fully
>> general technique for achieving proper tail recursion.
>
> The only thing I understand here is the irony of you repeatedly citing
> yourself in a discussion about recursion.
Okay, let�s assume that trampolines in Clojure can�t always provide
the security of not exploding the stack.
Can you please give a concrete example (possibly a short one) where
you make recursive calls that will result in a stack overflow when we
try to translate your example into Clojure?
Andr�
--
Lisp is not dead. It�s just the URL that has changed:
http://clojure.org/
André Thieme wrote:
> Can you please give a concrete example (possibly a short one) where
> you make recursive calls that will result in a stack overflow when we
> try to translate your example into Clojure?
Any combinator library. The combinators rely upon tail calls to continue
into their function arguments. As a library, this code is expected to be
arbitrarily extensible with user-defined combinators. So there is
no "closed world" for the trampoline to encompass unless it encompasses the
entire language implementation:
http://groups.google.com/group/clojure/msg/3addf875319c5c10
Interestingly, it sounds as though MLVM/OpenJDK will get working tail calls
(at least on x86) any day now but I recently discovered that Mono, which
has claimed to have tail calls for many years, does not actually support
them properly:
http://flyingfrogblog.blogspot.com/2009/01/mono-does-not-support-tail-calls.html
--
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
http://www.ffconsultancy.com/?u
Jon Harrop wrote:
> Any combinator library. The combinators rely upon tail calls to continue
> into their function arguments. As a library, this code is expected to be
> arbitrarily extensible with user-defined combinators. So there is
> no "closed world" for the trampoline to encompass unless it encompasses the
> entire language implementation:
When trampolines are used by the implementor of the
language to implement space-efficient tail recursion,
they do indeed encompass the entire implementation of
the language, even though users of the language may
be completely unaware of that fact.
That is why trampolines are a completely general
technique for implementing space-efficient tail
calls.
Will
Jon Harrop schrieb:
> André Thieme wrote:
>> Can you please give a concrete example (possibly a short one) where
>> you make recursive calls that will result in a stack overflow when we
>> try to translate your example into Clojure?
>
> Any combinator library. The combinators rely upon tail calls to continue
> into their function arguments. As a library, this code is expected to be
> arbitrarily extensible with user-defined combinators. So there is
> no "closed world" for the trampoline to encompass unless it encompasses the
> entire language implementation:
>
> http://groups.google.com/group/clojure/msg/3addf875319c5c10
Unfortunately I am not an expert for that.
What I would need is a concrete (and possibly short) program that
demonstrates the effect. The shortest proof-of-concept program, dunno
a 10-liner or whatever.
You could show me the ML version (Haskell, F#, Python, Common Lisp, ..)
and I will see if I can translate the program into Clojure and experience
a stack overflow.
Besides from the existance of such proof-of-concept, I would be
interested to know how many (for humans) interesting programs will have
this problem. At the moment I am under the impression that trampolines
cover many cases, if not all.
> Interestingly, it sounds as though MLVM/OpenJDK will get working tail calls
> (at least on x86) any day now but I recently discovered that Mono, which
> has claimed to have tail calls for many years, does not actually support
> them properly:
>
> http://flyingfrogblog.blogspot.com/2009/01/mono-does-not-support-tail-calls.html
Oh, I see. Well, I have a Windows box at home anyway, so when I learn
and play with F# I would most likely use Microsofts official .NET
implementation anyway. I guess Mono does not offer many advantages over
that one.
André
--
Lisp is not dead. It’s just the URL that has changed:
http://clojure.org/
William D Clinger wrote:
> It isn't that easy for Scheme or for Common Lisp, because
> the CLR gets in the way of first class continuations and
> restartable exceptions. By the time you've worked around
> that limitation of the CLR, you've probably had to resort
> to something like trampolines anyway [2].
Actually, can you not just translate into CPS to get callcc and use an
approach like this for restartable exceptions:
http://okmij.org/ftp/ML/resumable.ml
--
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
http://www.ffconsultancy.com/?u
Jon Harrop wrote:
> Actually, can you not just translate into CPS to get callcc
> and use an approach like this for restartable exceptions:
Sure, there are lots of things you can do, especially if
you're willing to transform into CPS. You can learn about
some of the alternatives by reading the ICFP 2005 paper by
Pettyjohn et al and the MS thesis by Lorelli [1,2].
It looks like Joe Marshall, who was a co-author of the ICFP
paper, will be presenting yet another paper about this at
the International Lisp Conference in Boston from 22 through
25 March 2009 [3]. Hope to see you there!
Will
[1] Greg Pettyjohn, John Clements, Joe Marshall, Shriram
Krishnamurthi, and Matthias Felleisen. Continuations from
generalized stack inspection. Proceedings of ICFP 2005,
ACM SIGPLAN Notices 40(9), September 2005, pages 216-227.
Online at http://portal.acm.org/citation.cfm?id=1086393 and
http://www.cs.brown.edu/~sk/Publications/Papers/Published/pcmkf-cont-from-gen-stack-insp/paper.pdf
[2] Anthony J Lorelli. Implementing continuations for
a virtual machine environment. MS thesis, 2006.
Online at http://synrc.com/io/project_lorelli.pdf
[3] http://www.international-lisp-conference.org/
On 24 Gen, 01:21, Jon Harrop <····@ffconsultancy.com> wrote:
> William D Clinger wrote:
> > Jon Harrop wrote:
> >> Clojure does *not* have tail calls. Trampolines degrade performance and
> >> obfuscate stack traces but, most importantly, they only handle a few
> >> special cases of tail calls.
>
> > Sir Harrop's definition of a trampoline may be quite
> > different from mine, but trampolines are certainly
> > one of the most widely used standard techniques that
> > implementors of Scheme and functional languages use
> > to implement fully general tail recursion, i.e. real
> > tail calls.
>
> Indeed. Look at what Chicken Scheme's use of trampolines does to the stack
> and how it breaks in the presence of interop. Now look at something like
> Microsoft's CLR and observe how tail calls in the VM provide full stack
> traces and seamless interop.
Does CLR provide seamless interop when calling native code?
Vend wrote:
> On 24 Gen, 01:21, Jon Harrop <····@ffconsultancy.com> wrote:
>> Indeed. Look at what Chicken Scheme's use of trampolines does to the
>> stack and how it breaks in the presence of interop. Now look at something
>> like Microsoft's CLR and observe how tail calls in the VM provide full
>> stack traces and seamless interop.
>
> Does CLR provide seamless interop when calling native code?
Yes.
--
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
http://www.ffconsultancy.com/?u
On 23 Gen, 22:48, William D Clinger <········@yahoo.com> wrote:
> Jon Harrop wrote:
> > Clojure does *not* have tail calls. Trampolines degrade performance and
> > obfuscate stack traces but, most importantly, they only handle a few
> > special cases of tail calls.
>
> Sir Harrop's definition of a trampoline may be quite
> different from mine, but trampolines are certainly
> one of the most widely used standard techniques that
> implementors of Scheme and functional languages use
> to implement fully general tail recursion, i.e. real
> tail calls.
Do you need to transform everything into continuation passing form in
order to use trampolines to implement general tail calls?
Vend asked:
> Do you need to transform everything into continuation passing form in
> order to use trampolines to implement general tail calls?
No.
The basic idea is that every procedure call (and also every
return) is implemented by a return (never a call) to the
trampoline, communicating these items of information:
* whether this is a return or a call
* the continuation (if a return) or the procedure (if a
call) to be invoked
* the return values (if a return) or arguments (if a call)
The trampoline then performs the return or call by
performing a call (never a return, unless this is a
return to code that uses the native calling convention)
to the continuation or procedure, passing the return
values or arguments.
(The need to distinguish native continuations from
non-native continuations explains why trampolines,
if that detail is omitted or implemented badly, can
screw up interoperability. The solution is to get
that detail right.)
Using trampolines as above does not, by itself, buy you
anything. To achieve space-efficient tail calls (aka
proper tail recursion, etc), the implementation must
allocate new continuations only for non-tail calls.
That means the implementation must recognize the difference
between tail calls and non-tail calls. Hence any formal
specification of proper tail recursion (by whatever name)
will include a formal (syntactic) definition of the calls
that are to be regarded as tail calls.
CPS has some advantages, but is orthogonal to the above.
Some alternatives to trampolines require transformation
to something like CPS or A-normal form, but trampolines
do not.
Will
On 2 Feb, 17:30, William D Clinger <········@yahoo.com> wrote:
> Vend asked:
>
> > Do you need to transform everything into continuation passing form in
> > order to use trampolines to implement general tail calls?
>
> No.
>
> The basic idea is that every procedure call (and also every
> return) is implemented by a return (never a call) to the
> trampoline, communicating these items of information:
>
> * whether this is a return or a call
> * the continuation (if a return) or the procedure (if a
> call) to be invoked
> * the return values (if a return) or arguments (if a call)
>
> The trampoline then performs the return or call by
> performing a call (never a return, unless this is a
> return to code that uses the native calling convention)
> to the continuation or procedure, passing the return
> values or arguments.
>
> (The need to distinguish native continuations from
> non-native continuations explains why trampolines,
> if that detail is omitted or implemented badly, can
> screw up interoperability. The solution is to get
> that detail right.)
>
> Using trampolines as above does not, by itself, buy you
> anything. To achieve space-efficient tail calls (aka
> proper tail recursion, etc), the implementation must
> allocate new continuations only for non-tail calls.
Maybe I miss something, but isn't the above actually CPS?
> That means the implementation must recognize the difference
> between tail calls and non-tail calls. Hence any formal
> specification of proper tail recursion (by whatever name)
> will include a formal (syntactic) definition of the calls
> that are to be regarded as tail calls.
>
> CPS has some advantages, but is orthogonal to the above.
> Some alternatives to trampolines require transformation
> to something like CPS or A-normal form, but trampolines
> do not.
Can you explain the difference, please?
Vend wrote:
> Maybe I miss something, but isn't the above actually CPS?
No.
In CPS, every call is a tail call, and there are no
returns at all.
In direct style, not all calls are tail calls, and
there are returns as well as calls.
In my description of trampolines, I assumed there
were both returns and calls, and that not all calls
were tail calls. I was therefore assuming direct
style.
With CPS, all returns to the trampoline would represent
calls. That would work, of course, but you wouldn't
need all of the complexity of trampolines; jumps would
work just as well, if your target machine allows them.
Will
On 3 Feb, 00:57, William D Clinger <········@yahoo.com> wrote:
> Vend wrote:
> > Maybe I miss something, but isn't the above actually CPS?
>
> No.
>
> In CPS, every call is a tail call, and there are no
> returns at all.
>
> In direct style, not all calls are tail calls, and
> there are returns as well as calls.
>
> In my description of trampolines, I assumed there
> were both returns and calls, and that not all calls
> were tail calls. I was therefore assuming direct
> style.
Ok, so you distinguish between procedures and return continuations,
while in a CPS-transformed program all return continuations are
transformed into procedures.
Right?
> With CPS, all returns to the trampoline would represent
> calls. That would work, of course, but you wouldn't
> need all of the complexity of trampolines; jumps would
> work just as well, if your target machine allows them.
>
> Will
Vend wrote:
> Ok, so you distinguish between procedures and return continuations,
> while in a CPS-transformed program all return continuations are
> transformed into procedures.
> Right?
Right. So trampolines work with both direct and CPS
style, but are simpler with CPS because there are
fewer cases for the trampoline to implement.
Will
In article
<····································@w1g2000prm.googlegroups.com>,
········@gmail.com wrote:
> On 22 Gen, 01:50, Jon Harrop <·@ff> wrote:
>
> Jon Harrop is already seriously preoccupied that Clojure soon could
> take over the hacking world?
>
> Wow!!
Why was I thinking of frogs when I saw
Michelle Obama's green gloves?
http://images.huffingtonpost.com/gen/59192/thumbs/s-MICHELLE-large.jpg
--
http://lispm.dyndns.org/