proper tail calls

classic Classic list List threaded Threaded
86 messages Options
12345
Reply | Threaded
Open this post in threaded view
|

proper tail calls

Peter Michaux
Will proper tail calls be implicit in ES4 or will there be a need for
special syntax? I hope it is just a required optimization but then I
read this ticket

http://bugs.ecmascript.org/ticket/323

and it seems there is a suggestion that the spec will only require
proper tail calls with a "goto" statement. Is it not reasonable for
the spec to simply require implementations to have proper tail calls?
Is it not acceptable for the spec to require certain implementation
internal optimizations?

Peter
_______________________________________________
Es4-discuss mailing list
[hidden email]
https://mail.mozilla.org/listinfo/es4-discuss
Reply | Threaded
Open this post in threaded view
|

Re: proper tail calls

Brendan Eich-2
On Jan 18, 2008, at 9:36 PM, Peter Michaux wrote:

Will proper tail calls be implicit in ES4 or will there be a need for
special syntax? I hope it is just a required optimization but then I
read this ticket


and it seems there is a suggestion that the spec will only require
proper tail calls with a "goto" statement.

That's the ticket's initial proposal, but as you can see opinions vary. I see two major axes of division:

E/I: explicit or implicit
S/X: statement or expression form

with the valid combinations being:

I,X: implicit, expression form, the original wiki'd proposal;
E,X: lth's proposal in the initial comment of the ticket;
E,S: graydon's proposal in comment 10.

I,S does not make sense. You can read the arguments for and against in the ticket. Graydon's recent comment includes this text:

"If, in order make the presence of an explicit form convenient, we have to add sugar for it as an additional form of expression-closure -- "goto call-expr()" means "{goto call-expr();} -- I don't think it's the end of the world. I do think, at present, we're meandering aimlessly towards a system that claims to provide a way to make tail calls, but in which nobody can ever figure out where or when they're actually getting tail calls. I don't think it'll be useful to ship such a language."

I think this nicely summarizes the problem with I, while not finishing off the case for X instead of just S or a slight extension to S (allowing the body of an expression closure to be a godo statement: function state1(a,b) goto state2(a*2, b-1); -- saving braces and using goto instead of return, four chars better). After a brief lapse into E,S, I'm in favor of E,X: goto as an operator required to get PTC and throwing an error if stack space must be consumed, as lth proposed in the original ticket.

Is it not reasonable for
the spec to simply require implementations to have proper tail calls?

The I,X original proposal from the wiki required this. It's "reasonable", maybe, if we can agree on the rules and they are not too complicated, but the crucial question is about usability, human factors, avoiding silent bad surprises: will programmers wanting proper tail calls be surprised when they nest an implicit (built-in among the primitive types) conversion in a big state machine, and silently defeat proper tail calls from that particular call site, leading to explosive stack growth in the worst case?

This concern of course led to the ticket; the principle familiar to Python folks is EIBTI (E Is Better Than I). Not just for readers (clarity of intent) but for writers (I want PTC or error here).

Is it not acceptable for the spec to require certain implementation
internal optimizations?

PTC is not an optimization, it's a storage rule. Schemers know to count on it, and do. For ~12 years, JS hackers have lacked it, on the other hand. And JS hackers have standard looping statement forms. But PTC is helpful for state machines, which you do see on the web; you even see setTimeout(fun, 0) flows to empty the JS stack in order to avoid overflow. PTC is worthwhile, and we have included it among approved proposals for a long time. The question remains: explicit or implicit syntax; if explicit, statement only or operator form?

/be


_______________________________________________
Es4-discuss mailing list
[hidden email]
https://mail.mozilla.org/listinfo/es4-discuss
Reply | Threaded
Open this post in threaded view
|

Re: proper tail calls

Peter Michaux
On Jan 18, 2008 10:49 PM, Brendan Eich <[hidden email]> wrote:
>
> On Jan 18, 2008, at 9:36 PM, Peter Michaux wrote:

[snip]

Some of the shorthand terminology that has developed in the
conversations is a bit unfamiliar to me. Hopefully my questions below
are not ridiculous.

>  Is it not reasonable for
> the spec to simply require implementations to have proper tail calls?
>
> The I,X original proposal from the wiki required this. It's "reasonable",
> maybe, if we can agree on the rules and they are not too complicated, but
> the crucial question is about usability, human factors, avoiding silent bad
> surprises: will programmers wanting proper tail calls be surprised when they
> nest an implicit (built-in among the primitive types) conversion in a big
> state machine, and silently defeat proper tail calls from that particular
> call site, leading to explosive stack growth in the worst case?

I'm thinking in terms of Scheme and tail calls. If a Scheme programmer
puts a recursive call in a non tail position they get explosive stack
growth. If the programmer was required to explicitly state they wanted
a tail call then the explicit system you are suggesting would throw an
error, correct?

It seems like having types in ES4 is adding quite a bit of difficulty
to when a proper tail call can occur. The Scheme folks don't have to
deal with that, I suppose.

> This concern of course led to the ticket; the principle familiar to Python
> folks is EIBTI (E Is Better Than I). Not just for readers (clarity of
> intent) but for writers (I want PTC or error here).
>
> Is it not acceptable for the spec to require certain implementation
> internal optimizations?
> PTC is not an optimization, it's a storage rule. Schemers know to count on
> it, and do. For ~12 years, JS hackers have lacked it, on the other hand. And
> JS hackers have standard looping statement forms. But PTC is helpful for
> state machines, which you do see on the web; you even see setTimeout(fun, 0)
> flows to empty the JS stack in order to avoid overflow. PTC is worthwhile,
> and we have included it among approved proposals for a long time. The
> question remains: explicit or implicit syntax; if explicit, statement only
> or operator form?

I think implicit tail calls are one of the most exciting proposals for
ES4. Can it be implicit with the option of making it explicit so that
it throws an error if the call is not in tail position and will
produce the explosive stack growth? This would have the same feel that
the language is "unsafe" but has optional "safety" features like
optional types. ES3 doesn't have any mandatory safety syntax and to me
it would be best to keep all safety syntax optional.

Peter
_______________________________________________
Es4-discuss mailing list
[hidden email]
https://mail.mozilla.org/listinfo/es4-discuss
Reply | Threaded
Open this post in threaded view
|

Re: proper tail calls

Brendan Eich-2
On Jan 19, 2008, at 12:31 AM, Peter Michaux wrote:

> It seems like having types in ES4 is adding quite a bit of difficulty
> to when a proper tail call can occur. The Scheme folks don't have to
> deal with that, I suppose.

Contract systems in Scheme may use space, so this is a problem that  
has been studied.

ES4 has no user-defined implicit conversions, but the built-in ones  
could require stack space so that's the hazard, as I understand things.

The C syntax makes it harder to see tail positions compared to  
Scheme, so types are not the only issue. Really, the question is a  
human factors one.

> I think implicit tail calls are one of the most exciting proposals for
> ES4. Can it be implicit with the option of making it explicit so that
> it throws an error if the call is not in tail position and will
> produce the explosive stack growth? This would have the same feel that
> the language is "unsafe" but has optional "safety" features like
> optional types. ES3 doesn't have any mandatory safety syntax and to me
> it would be best to keep all safety syntax optional.

This is an interesting way of looking at it, and indeed jaz (Jon  
Zeppieri) in comments 23 and 25 in

http://bugs.ecmascript.org/ticket/323

brought up the idea of an assertion "I want a PTC here:" that could  
be attached to a call, with implicit proper tail calls. I should have  
represented this as an option; thanks for bringing it to light on the  
list. Call it I,X (Implicit, eXpression tail calls) + A (Assert-PTC-
here).

Even with the explicit syntax for guaranteed PTCs, most of us can't  
see ruling out as non-conforming an implementation that uses PTC  
implicitly too. Given that allowance for further PTC without explicit  
"opt-in" syntax, the assertion jaz proposed makes a lot of sense.

My concern that people won't know to use it is weak. Either lack of  
it will burn people and they'll learn of it and use it, or it won't  
be needed anyway. Sort of like optional type annotations, as you  
note. The important point is that leaving out such an assertion, with  
explicit or implicit PTC (where the explicit case still allows  
further PTC to be done implicitly), enters the programmer in a  
guessing game.

I,X (no way to assert PTC here or error)
I,X+A (original wiki'd proposal + Jon Zeppieri's assertion idea)
E,X (+A anyway in case of further PTC at implementation's discretion?)
E,S (+A for the same reason?)

Looking at it this way, there's a case for A. And given A plus  
implementation freedom to optimize more PTC than required by the  
spec, is E really necessary?

/be

_______________________________________________
Es4-discuss mailing list
[hidden email]
https://mail.mozilla.org/listinfo/es4-discuss
Reply | Threaded
Open this post in threaded view
|

Re: proper tail calls

Erik Arvidsson
My concern with E (or A for that matter) is that it requires
additional syntax.  I'd prefer if we could keep the syntax small.  I
don't think implicit PTC is an issue.  It is an optimization that the
interpreter/compiler should do.  What are the problems with I?  It
does not change the semantics of the language.


--
erik
_______________________________________________
Es4-discuss mailing list
[hidden email]
https://mail.mozilla.org/listinfo/es4-discuss
Reply | Threaded
Open this post in threaded view
|

Re: proper tail calls

Brendan Eich-2
On Jan 20, 2008, at 5:22 PM, Erik Arvidsson wrote:

> My concern with E (or A for that matter) is that it requires
> additional syntax.  I'd prefer if we could keep the syntax small.  I
> don't think implicit PTC is an issue.  It is an optimization that the
> interpreter/compiler should do.  What are the problems with I?  It
> does not change the semantics of the language.

Proper tails calls are not an optimization; they certainly do change  
semantics, insofar as you can't write certain programs without them  
being guaranteed. I'll defer to Dave's 2005 LtU comment (he may have  
newer ones he prefers),

http://lambda-the-ultimate.org/node/472#comment-3511

which has useful links.

/be
_______________________________________________
Es4-discuss mailing list
[hidden email]
https://mail.mozilla.org/listinfo/es4-discuss
Reply | Threaded
Open this post in threaded view
|

Re: proper tail calls

Igor Bukanov-2
In reply to this post by Erik Arvidsson
On 21/01/2008, Erik Arvidsson <[hidden email]> wrote:
> My concern with E (or A for that matter) is that it requires
> additional syntax.  I'd prefer if we could keep the syntax small.

The explicit syntax has one extra flow. Since the type checker is
optional, even with explicit syntax the program may still compile just
to throw an
exception 100% when it reaches the tail call due to the runtime type checks.

I would bye the arguments about the explicit syntax if its semantics
would guarantee the tail call as long as the code compiles without
relining on optional parts of E4X. But since this is not possible,
then I would prefer to make the tail calls an optional optimization in
the same way as the type checker is optional.

Regards, Igor
_______________________________________________
Es4-discuss mailing list
[hidden email]
https://mail.mozilla.org/listinfo/es4-discuss
Reply | Threaded
Open this post in threaded view
|

Re: proper tail calls

Igor Bukanov-2
On 21/01/2008, Igor Bukanov <[hidden email]> wrote:
> then I would prefer to make the tail calls an optional optimization in
> the same way as the type checker is optional.

And if Haskell language specs can leave the issue of tail call
optimization up to implementations, then I do not see why ES4 can not
do the same.

>From http://www.haskell.org/onlinereport/intro.html :

> This report defines the syntax for Haskell programs and an informal abstract semantics for the meaning of such programs. We leave as implementation dependent the ways in which Haskell programs are to be manipulated, interpreted, compiled, etc. This includes such issues as the nature of programming environments and the error messages returned for undefined programs (i.e. programs that formally evaluate to _|_).

Regards, Igor
_______________________________________________
Es4-discuss mailing list
[hidden email]
https://mail.mozilla.org/listinfo/es4-discuss
Reply | Threaded
Open this post in threaded view
|

Re: proper tail calls

Peter Michaux
On Jan 21, 2008 5:34 AM, Igor Bukanov <[hidden email]> wrote:
> On 21/01/2008, Igor Bukanov <[hidden email]> wrote:
> > then I would prefer to make the tail calls an optional optimization in
> > the same way as the type checker is optional.
>
> And if Haskell language specs can leave the issue of tail call
> optimization up to implementations, then I do not see why ES4 can not
> do the same.

I think Haskell and ES are in different situations as a developer
chooses a Haskel implementation for execution. ES4 code for the web is
almost certainly going to run on multiple ES4 implementations. If
there are no requirements for proper tail calls then they cannot be
depended upon and are useless.

Peter
_______________________________________________
Es4-discuss mailing list
[hidden email]
https://mail.mozilla.org/listinfo/es4-discuss
Reply | Threaded
Open this post in threaded view
|

Re: proper tail calls

Peter Michaux
In reply to this post by Brendan Eich-2
On Jan 20, 2008 8:01 PM, Brendan Eich <[hidden email]> wrote:

>
> On Jan 20, 2008, at 5:22 PM, Erik Arvidsson wrote:
>
> > My concern with E (or A for that matter) is that it requires
> > additional syntax.  I'd prefer if we could keep the syntax small.  I
> > don't think implicit PTC is an issue.  It is an optimization that the
> > interpreter/compiler should do.  What are the problems with I?  It
> > does not change the semantics of the language.
>
> Proper tails calls are not an optimization; they certainly do change
> semantics, insofar as you can't write certain programs without them
> being guaranteed.

I've been trying to find out how they are not an optimization. I
haven't read anyone else that thinks they are not an optimization but
I have read other people refer to them as an optimization. I think
that from an application programmers point of view they are an
optimization since the same program will run without proper tail calls
if the computer has infinite resources.

> I'll defer to Dave's 2005 LtU comment (he may have
> newer ones he prefers),
>
> http://lambda-the-ultimate.org/node/472#comment-3511

He only mentions that transforming non tail-call application code into
tail-call application code is "a standard optimization technique" in a
language that has proper tail calls. He doesn't mention whether or not
proper tail calls in the language are to be considered a optimization.

> which has useful links.

Following one of those links leads to a wiki and the wiki has the
following page which discusses proper tail calls as an optimization in
the language

http://c2.com/cgi/wiki?TailCallOptimization

Peter
_______________________________________________
Es4-discuss mailing list
[hidden email]
https://mail.mozilla.org/listinfo/es4-discuss
Reply | Threaded
Open this post in threaded view
|

Re: proper tail calls

Erik Arvidsson
In reply to this post by Peter Michaux
On Mon, Jan 21, 2008 at 8:57 AM, Peter Michaux <[hidden email]> wrote:
>  I think Haskell and ES are in different situations as a developer
>  chooses a Haskel implementation for execution. ES4 code for the web is
>  almost certainly going to run on multiple ES4 implementations. If
>  there are no requirements for proper tail calls then they cannot be
>  depended upon and are useless.

As long as all the implementations have the exact same call stack
limitation then that holds true.  However, I think it is unreasonable
to enforce one call stack size fits all.

I think we can all agree on that having explicit tail calls at compile
time enforces all runtimes to have proper tail calls?

--
erik
_______________________________________________
Es4-discuss mailing list
[hidden email]
https://mail.mozilla.org/listinfo/es4-discuss
Reply | Threaded
Open this post in threaded view
|

Re: proper tail calls

Brendan Eich-2
In reply to this post by Peter Michaux
On Jan 21, 2008, at 9:08 AM, Peter Michaux wrote:

>> Proper tails calls are not an optimization; they certainly do change
>> semantics, insofar as you can't write certain programs without them
>> being guaranteed.
>
> I've been trying to find out how they are not an optimization. I
> haven't read anyone else that thinks they are not an optimization but
> I have read other people refer to them as an optimization.

Read more, then :-/. The Scheme and Pre-Scheme histories are  
interesting (in Pre-Scheme you used GOTO for a tail call -- explicit  
syntax I favor for ES4).

See, for instance, Anton van Straaten's fine comment in the same LtU  
post I cited:

http://lambda-the-ultimate.org/node/472#comment-3568

and especially:

http://lambda-the-ultimate.org/node/472#comment-3549

Quote:

"The ironic thing is that we're talking about a bug whose presence in  
the language implementation, and in people's minds, makes it  
difficult to detect that it is a bug. They don't think it's a bug,  
because they "know" recursion is unnatural and even dangerous — but  
the only reason they "know" that, is because their language  
implementation has a bug which makes it so. It's a recursive bug,  
which is particularly difficult to detect when one makes a habit of  
avoiding recursion..."

> I think
> that from an application programmers point of view they are an
> optimization since the same program will run without proper tail calls
> if the computer has infinite resources.

And if my mother had wheels, she'd be a trolley-car. Meanwhile, back  
in reality, no computer has infinite resources, and as you pointed  
out to Igor, making "TCO" an option makes it useless on the web --  
browsers have different, or no, stack quotas or redzoning. Semantics  
are not about the meanings of programs assuming infinite resources.

> Following one of those links leads to a wiki and the wiki has the
> following page which discusses proper tail calls as an optimization in
> the language
>
> http://c2.com/cgi/wiki?TailCallOptimization

Yes, it' s a common TLA but citing one use of it doesn't settle the  
debate. Please read more.

/be

_______________________________________________
Es4-discuss mailing list
[hidden email]
https://mail.mozilla.org/listinfo/es4-discuss
Reply | Threaded
Open this post in threaded view
|

Re: proper tail calls

Igor Bukanov-2
In reply to this post by Peter Michaux
On 21/01/2008, Peter Michaux <[hidden email]> wrote:
> On Jan 20, 2008 8:01 PM, Brendan Eich <[hidden email]> wrote:
...
> > Proper tails calls are not an optimization; they certainly do change
> > semantics, insofar as you can't write certain programs without them
> > being guaranteed.
>
> I've been trying to find out how they are not an optimization.

I second that. Consider the following case:

let f2;

function f(a)
{
    f2 = function() { return a; }
    goto return g();
}

function g() {f2 = null; ... }

Here in f "return g()" is in tail position yet the frame of f can not
be eliminated completely since it is referenced through a global
variable. On the other hand a smart implementation may figure out
that, given the structure of g, there is no leak of the frame and it
can be eliminated completely.

So in reality due to this closure leakage there is no guarantees about
the space complexity unless one restricts the code that can present in
a function with a tail call. As such a tail call can be treated only
as an optimization hint as in general it is not possible to ensure
O(1) in space behavior for calls in the tail positions.

Regards, Igor
_______________________________________________
Es4-discuss mailing list
[hidden email]
https://mail.mozilla.org/listinfo/es4-discuss
Reply | Threaded
Open this post in threaded view
|

Re: proper tail calls

Jon Zeppieri-2
On 1/21/08, Igor Bukanov <[hidden email]> wrote:

>
> let f2;
>
> function f(a)
> {
>     f2 = function() { return a; }
>     goto return g();
> }
>
> function g() {f2 = null; ... }
>
> Here in f "return g()" is in tail position yet the frame of f can not
> be eliminated completely since it is referenced through a global
> variable.

I don't understand your claim.  You're saying that the "frame of f"
is "referenced through a global variable"?  Clearly, f2 is the global
variable, you're referring to.  f2 may be bound to a function value
that closes over a, which is part of f's activation frame -- or, more
specifically, part of f's closure environment.  But how would this
prevent the call to g from being a tail call?  Are you assuming that a
must be on the stack?
_______________________________________________
Es4-discuss mailing list
[hidden email]
https://mail.mozilla.org/listinfo/es4-discuss
Reply | Threaded
Open this post in threaded view
|

Re: proper tail calls

Jon Zeppieri-2
On 1/21/08, Jon Zeppieri <[hidden email]> wrote:

> On 1/21/08, Igor Bukanov <[hidden email]> wrote:
> >
> > let f2;
> >
> > function f(a)
> > {
> >     f2 = function() { return a; }
> >     goto return g();
> > }
> >
> > function g() {f2 = null; ... }

To clarify,  space is consumed by the evaluation of:

   f2 = function() { return a; }

...which constructs (and binds) a closure.

   goto return g();

...on the other hand, does not consume space.  a is still live, but
it's live as part of f2's closure, not as part of f's activation
frame.
_______________________________________________
Es4-discuss mailing list
[hidden email]
https://mail.mozilla.org/listinfo/es4-discuss
Reply | Threaded
Open this post in threaded view
|

Re: proper tail calls

Igor Bukanov-2
In reply to this post by Igor Bukanov-2
On 21/01/2008, Jon Zeppieri <[hidden email]> wrote:

> On 1/21/08, Igor Bukanov <[hidden email]> wrote:
> > let f2;
> >
> > function f(a)
> > {
> >     f2 = function() { return a; }
> >     goto return g();
> > }
> >
> > function g() {f2 = null; ... }
...
>
> I don't understand your claim.  You're claiming that the "frame of f"
> is "referenced through a global variable"?  Clearly, f2 is the global
> variable, you're referring to.  f2 may be bound to a function value
> that closes over a, which is part of f's activation frame -- or, more
> specifically, part of f's closure environment.  But how would this
> prevent the call to g from being a tail call?  Are you assuming that a
> would be on the stack?  That is not a warranted assumption.

I am saying that even for calls in the tail position an implementation
may not eliminate the parent frame completely as it still may be
exposed via closures. As such the tail call optimization cannot
guarantee that the space complexity of the tail recursion is O(1).

>
_______________________________________________
Es4-discuss mailing list
[hidden email]
https://mail.mozilla.org/listinfo/es4-discuss
Reply | Threaded
Open this post in threaded view
|

Re: proper tail calls

P T Withington
In reply to this post by Peter Michaux
I think talking about stacks and stack overflows might be muddying  
this discussion.  The language is a garbage-collected language and a  
function context (stack frame) should be subject to garbage collection  
just like any other object.  A stack frame that is no longer  
'reachable' (because it will be returned through) should be  
collected.  A clever implementation trick is to notice this at compile  
time and simply reuse the frame.

The use of `goto` is darn cute, and a nice way to make that assertion  
to the compiler and give a clue to the reader.  It's a lot like  
`delete` though.  `delete` doesn't mean that the referenced object  
will actually be collected, it just drops that reference.  You may  
intend that by deleting a reference an object will be collected, but  
the language has no way for you to assert that.

You could still argue that in strict mode the compiler should complain  
if a frame you `goto` out of is not going to be unreachable (and hence  
collected) after all (either because you don't really have a tail  
call, or because a closure or type error may capture the frame).  But  
by the same token, I might like the compiler to warn me if I am  
allocating closures in a loop (easy to overlook).

What I wonder is, why are we obsessing about this particular garbage  
collection problem?  Because there is a clever implementation trick  
that solves it?  Do we have other requirements on implementation's of  
garbage collection?  Or just a general assumption that the garbage  
collector has to work?

If I re-write my recursive tail-call algorithm as a loop that  
allocates a state object each time around the loop (and drops the  
reference to the previous state), do we require all implementations to  
not run out of space because I have a 'proper' bounded resource  
algorithm?
_______________________________________________
Es4-discuss mailing list
[hidden email]
https://mail.mozilla.org/listinfo/es4-discuss
Reply | Threaded
Open this post in threaded view
|

Re: proper tail calls

Graydon Hoare-3
In reply to this post by Igor Bukanov-2
Igor Bukanov wrote:

> I am saying that even for calls in the tail position an implementation
> may not eliminate the parent frame completely as it still may be
> exposed via closures. As such the tail call optimization cannot
> guarantee that the space complexity of the tail recursion is O(1).

This is much like saying "if the function in the tail call appends a
value to an array, it is not O(1)". We're talking about stack growth,
not side-effects on escaped heap objects. They have indefinite lifetime
anyways. Who's to say the storage is even freed when g() runs and nulls
out f2?

-Graydon

_______________________________________________
Es4-discuss mailing list
[hidden email]
https://mail.mozilla.org/listinfo/es4-discuss
Reply | Threaded
Open this post in threaded view
|

Re: proper tail calls

Igor Bukanov-2
On 21/01/2008, Graydon Hoare <[hidden email]> wrote:

> Igor Bukanov wrote:
>
> > I am saying that even for calls in the tail position an implementation
> > may not eliminate the parent frame completely as it still may be
> > exposed via closures. As such the tail call optimization cannot
> > guarantee that the space complexity of the tail recursion is O(1).
>
> This is much like saying "if the function in the tail call appends a
> value to an array, it is not O(1)". We're talking about stack growth,
> not side-effects on escaped heap objects. They have indefinite lifetime
> anyways. Who's to say the storage is even freed when g() runs and nulls
> out f2?

Consider another example:

function f(a) {
   function f2 { return a * 2; }
   if (a == 0) return 0;
   goto return f(a - 1);
}

f(1 << 20);

One may expect that this would require O(1) space. But this is not the
case as the implementation may not eliminate f2. Moreover, even for a
case like:

function f(a) {
   if (a == 0) return 0;
   goto return f(a - 1);
}

f(1 << 20);

the implementation is still allowed to use heap for integers.  So even
in this example the space complexity may be O(N). Hence the questions:
how useful to specify the details of tail call optimizations without
putting restrictions on the rest of the runtime?

Regards, Igor
_______________________________________________
Es4-discuss mailing list
[hidden email]
https://mail.mozilla.org/listinfo/es4-discuss
Reply | Threaded
Open this post in threaded view
|

Re: proper tail calls

Anton van Straaten
In reply to this post by Peter Michaux
Peter Michaux wrote:
> I've been trying to find out how [proper tail calls] are not an
> optimization. I haven't read anyone else that thinks they are not an
> optimization but I have read other people refer to them as an
> optimization. I think that from an application programmers point of
> view they are an optimization since the same program will run without
> proper tail calls if the computer has infinite resources.
...
> Following one of those links leads to a wiki and the wiki has the
> following page which discusses proper tail calls as an optimization in
> the language
>
> http://c2.com/cgi/wiki?TailCallOptimization

There's a distinction between the space efficiency property known as
"proper tail recursion" and the implementation technique called "tail
call optimization".  For some discussion of this, see:

http://groups.google.com/group/comp.lang.lisp/msg/0b8eb4a54bff7857

In that post, Will Clinger makes the point that there's a distinction
between:

"* a syntactic concept (tail calls, aka tail recursion)
  * implementation techniques (tail call optimization, tail merging)
  * space efficiency property (proper tail recursion)"

The abstract of Clinger's original paper[*] about proper tail recursion
mentions this point:

"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."

Proper tail calls are a property that programmers can rely on in
languages which offer it.  How that is implemented is not that important
to an application programmer.  The fact that one can implement proper
tail recursion, in part, with a technique known as tail-call
optimization, doesn't make proper tail calls an optimization, any more
than optimizations in a garbage collector make garbage collection an
optimization.

Anton

[*] http://citeseer.ist.psu.edu/clinger98proper.html

_______________________________________________
Es4-discuss mailing list
[hidden email]
https://mail.mozilla.org/listinfo/es4-discuss
12345