I was thinking: Implementing tail calls seems easy; the normal calling
sequence of "do some setup, then jump" just turns into "don't bother
with (most of) the setup, just jump". That is, don't move a new
register base-pointer into place, etc.

But there's one wiggle: If you've created a continuation previously
(and it still exists), then any call has to preserve the frame--you
basically can't do a tail call, with its key implication of the
"current frame" vaporizing, or being re-used (depending on how you want
to describe it).

But that's not too much of a problem, with the following:

1) Consider a tailcall op a recommendation--but have the VM do a
regular call, if necessary.
2) Regular calls create continuations, so you can't do a tail call out
of a function, if you've already done a regular call inside that
function, _unless_ we have an (efficient) way to tell if any such
continuation was "saved". You can figure some of that out at
compile-time (whether a regular call could have been already made), but
you'd need runtime checks for other cases, unless you just forego a
tail call any time you _could_ have already done a regular call (which
avoids the runtime checks, but allows less actual tail calls).

Do any existing languages have both tail calls and continuations?
Scheme mandates that anything which looks like a tail call, must be
optimized as expected (other languages like Lisp merely permit it), but
I don't know of Scheme having continuations. Scheme cares, of course,
so that you can have ostensibly unlimited recursion, without running
out of stack space (or really, memory). Tail calls and continuations
seem a bit like opposites--one preserves state, the other destroys it.

Just thought I'd send out these thoughts, since the topic was mentioned
recently.

JEff

Scheme is a counterexample, it supports both mandatory tail calls &
continuations.

I've no idea how stuff is implemented in Parrot, but an obvious idea
would be to have some kind of lazy copying scheme (i.e. maintain a
reference count for the stack frames & copy the respective one before
mutating it in a tail call, if necessary).

Cheers,
Michael

Jeff~

I find thinking in terms of continuations directly make this a little
easier to envision.  consider the following code

sub bar() {
  return foo();

in the normal case this will be

sub bar( parentContinuation) {
  myContinuationForCC;
  temp = foo(myContinuationForCC);
CC:
  parentContinuation(temp);

in the tailcall case, this will be

sub bar( parentContinuation) {
  foo(parentContinuation);

In the case that your current frame has already had a continuation of
it taken, then the created continuation would already be doing the
work of ensuring that the frame does not evaporate (after all the
created continuation IS the frame).  Thus, you should still be able to
just pass your parent continuation to whatever you are calling without
any reservations.

At least that is how I understand it,
Matt
--
"Computer Science is merely the post-Turing Decline of Formal Systems Theory."
-???

Well, that's what continuations are doing. They do preserve the frame,
which they have taken a snapshot of. And they preserve any frames up the
call chain. This is needed and implemented and working.

The concept of a return continuation (which recycles itself and the
frame it returned from) doesn't have an influence on tail calls.
Whenever you see a continuation "on the surface", it's one that is
preserving the frames and the context. Eventually there isn't even a
RetContinuation object but just a pointer to the calling frame. But
whenever you can see a continuations it's a real one - at least then,
when the big cheese doesn't see this change (returncc opcode) as a change
to calling conventions anymore "not now" ;)

So a tailcall can even silently reuse the return continuation and return
to the caller's caller.
AFAIK the only problem with tailcalls and tail-recursive functions is to
prperly detect them in some optimizer, or to convert to such tailcalls.

leo

Is it sufficient to provide a mechanism for the compiler writers to indicate that tail call should be used? For example, I have a few cases in tcl where I have something like:

  ($I0,$P0) = interpret($P1)
  .return($I0,$P0)

Where I'd be happy to have to write:

  .return_tailcall(interpret($P1))

or somesuch.

On Nov 10, 2004, at 3:08 PM, Leopold Toetsch wrote:

But here's the part I'm thinking about:

Continuations only copy the interpreter context, which contains the
register bp, but of course the actual contents of the register frame
are not duplicated. (This is as it should be.) The contents of the
register frame are effectively preserved because in sub->invoke() we
allocate a new register frame, and change the bp to point there.
(That's fine too.)

But, in a tail-call-optimization case, we don't need to call
new_register_frame() and copy_regs()--ex hypothesi, we can re-use the
register frame already in-place. That's a big savings--that's the
optimization I'm after. But of course, we can only do that if we know
that a "real" continuation hasn't also captured the context.

But in light of what you say here...

...it sounds like we have an easy way to tell if a "real" continuation
has a claim on the register frame, because creating such a real
continuation can mark the frame, and we can check for the mark in our
tail-call implementation, and if it's marked then fall back to
new_register_frame/copy_regs. (In fact that mark should be a reference
count, keeping track of how many continuations "have a claim" on the
register frame. That way, if a real continuation is created, but GC
claims it before our tail-call attempt, we can still use our
optimization.)

But maybe we're already doing something like that, and I missed it.

Seems like that shouldn't be too bad--we only need to know that there's
effectively no code between the function call and subsequent return.
(Though maybe telling call from return will be tricky.)

JEff

In that case it's easily detectable. The relevant logic is even
implemented (imcc/pcc.c /TAIL_CALLS). Just the calling needs changes.

leo

Yes. As the return and the calling conventions are the same WRT register
setup, we've function arguments already in place. We still have to copy
the context, though.

There is no such mark. If ctx->current_cont isa(RetContinuation), then
it's save to do the tail call. This OTOH is meaning that we can do the
check only at runtime. Thus the C<tailcall> or C<tailcallmethod> opcodes
have to do plain calls if they detect such a situation.

That's really not needed. If you return from the function and you call
it next time, you've again a RetContinuation. If the continuation was
created somewhere deeper in the call chain, it's gone or not after the
GC cycle. And you know - starting with refcounting one objects ends up
with refcounting containers holding that item ...

leo

On Nov 10, 2004, at 11:53 PM, Leopold Toetsch wrote:

Good--implicit mark then.

Yep, although there will be some situations where we can know for sure
at compile time--for instance if all function calls within a function
are tail calls. (We could have a special sort of C<tailcalldontcheck>,
but that depends on our philosophy--if it's okay for the VM to trust
the compiler. Or possibly the VM could detect this, and cache this
information as a sort of dynamic optimization; or a bytecode verifier
could ensure that C<tailcalldontcheck> is valid in a given context.
Multiple options here.)

And also, even when C<tailcall> has to fall back to a plain call, it
doesn't have to fall all the way back--it can still pass along the
return continuation from its caller, and get some benefit.

But if ctx->current_cont has been promoted to a real continuation (as a
result of something that happened deeper in the stack), it will never
be turned back to a RetContinuation, even if it could have been (ie, if
GC reclaimed the things that caused the promotion), so we might forego
a tail call that we could have made.

Not really. In this case, the only things which are allowed to point to
a register frame (via a ctx) are the interpreter itself, and
continuations. There are just a couple of specific points where the ref
count would need to be incremented/decremented (including the destroy()
of continuations). But that's the clear place to stop--you don't need
to ref count the continuations themselves, since that wouldn't be
practical (you'd need write barriers to always check if you're
referencing or un-referencing a continuation, etc.). We wouldn't have
to go off the deep end with it.

JEff

[ refcounting continuations ]

In the current scheme. I was a bit further ;) Given big frame chunks
and the watermark holding the highest continuation frame. Now during GC
(and when the Continuation is dead) all frames the call chain up can be
compacted and if they had return continuations earlier, these can be
restored.

Ok. That should work too.

leo

I thought that too. So I did it ;)

$ time parrot  -j fact.imc 10000                  # [1]
maximum recursion depth exceeded

$ time parrot -Oc -j fact.imc 10000 >2            # [2]

real    0m0.635s

$ time ruby $(locate fact.rb) 10000 >1            # [3]

real    0m5.237s

$ diff 1 2
$ ls -l 1
-rw-r--r--   1 lt       users       35661 Nov 11 18:01 1

I've to clean it up a bit, though.

leo

[1] default recursion limit is 1000
[2] -Oc turns on tailcall optimizations, unoptimized Parrot build
[3] this is an iterative version of factorial

leo

Fully agreed. Even further, it's necessary for some languages
(Scheme)/paradigms (loop by recursion) that a "tailcall" is not just a
hint but mandatory.

Cheers,
Michael

At 1:24 AM -0800 11/11/04, Jeff Clites wrote:

Tail calls should be explicit, compile-time things. Otherwise we're
going to run afoul of traceback requirements and suchlike things, and
I think that's just not worth the risk and hassle. Besides, it's a
lot easier in general for a language compiler to decide when a tail
call's in order than it is for us.
--
                                Dan

--------------------------------------it's like this-------------------
Dan Sugalski                          even samurai
d...@sidhe.org                         have teddy bears and even
                                       teddy bears get drunk

On Nov 11, 2004, at 9:44 AM, Michael Walter wrote:

Nah, that's just the difference between running optimized and
unoptimized. Actually, with a tailcall op that's effectively a hint, it
would be ideal to have 3 run modes: a "just obey the hints" mode (for
those that trust their compiler), a "never do a tail call" mode (for
debugging purposes), and a "do tail calls whenever possible" mode
(independent of whether the tailcall op was used). Not sure if those
are run modes or assembler (optimizer) modes, though.

I think it's pretty straightforward to tell, at least at the PIR level.
Even at the pasm level, the only requirement is that there's
effectively no code between a call from foo to bar, and a return from
foo. It's a pure optimization--good fodder for an optimizer.

I think that actually doesn't matter. Even in the case where we think
we can't do a full tail call optimization (because of a continuation
that's been taken), we can still actually remove the calling frame from
the call stack--we just can't immediately re-use the register frame.
That satisfies the Scheme requirement, I would think. You can still do
unbounded recursion, just that GC may need to run to clean up call
frames.

Leo said:

I'd think that long-term our max recursion depth limit should only
apply to net frame depth--tail calls shouldn't increase the count.
(Probably we'd need 2 counts--net depth and logical depth.)

JEff

Yep. So is it implemented:
* tailcall / tailcallmethod opcodes
* the former is currently created by imcc with "parrot -Oc" only

Patch is probably ready tomorrow.

leo

At 11:16 AM -0800 11/11/04, Jeff Clites wrote:

Still, the only way we know they're valid to do is if we're told so.
If the compilers allow it then they can do it themselves.

I only skimmed the earlier parts of this, but continuations shouldn't
affect tail calls at all. There's certainly no reason they ought to.
All a tail call does is use the current return continuation as the
return continuation for the call you're making. That's not affected
by taking a continuation.

If this is from some side effect of call speed optimization (I
remember seeing some discussion of stack allocation of call frames or
something, but I don't recall if it was before or after I said we
weren't optimizing this stuff right now) then we need to rip out
those optimizations. If there's some other reason then it needs to
get fixed, as we've got something else broken.
--
                                Dan

--------------------------------------it's like this-------------------
Dan Sugalski                          even samurai
d...@sidhe.org                         have teddy bears and even
                                       teddy bears get drunk

At 7:26 PM +0100 11/11/04, Leopold Toetsch wrote:

Cool. I think I'd like to skip having to specify the -Oc flag,
though, and add explicit syntax to PIR.

For the long form sub call, .pcc_tail_call instead of .pcc_call. For
the short form... I dunno, something explicit. Double-colons before
the opening parenthesis or something. Foo::(). Or something else.
Whatever works OK in the grammar. (Leaving out short-form tail
calling is fine too)

Method calls should look about the same. Foo.methodname::() or
something like that.
--
                                Dan

--------------------------------------it's like this-------------------
Dan Sugalski                          even samurai
d...@sidhe.org                         have teddy bears and even
                                       teddy bears get drunk

On Nov 11, 2004, at 11:24 AM, Dan Sugalski wrote:

You should read the thread then.

Tail call optimization *is* and optimization.... That's what the whole
feature is.

And there's a difference between a pure optimization (which increases
speed at the cost of design), and an architectural feature which
improves speed.

JEff

At 11:54 AM -0800 11/11/04, Jeff Clites wrote:

Joy. That means continuations are broken still.

Yeah, and in environments with call stack inspection, it's a
*language level* optimization.

For us, whether or not a call is a tail call is something the
compiler must make explicit.

We're deferring those too.
--
                                Dan

--------------------------------------it's like this-------------------
Dan Sugalski                          even samurai
d...@sidhe.org                         have teddy bears and even
                                       teddy bears get drunk

No. It was a wrong conclusion I had earlier in this thread. I thought
that the presence of any captured frame could have an influence on
tailcalls. I argue the converse now.

leo

No. It's an opcode doing tailcalls. The optimization is coming from the
language. In case of imcc it's turned on with -Oc (optimize calls)
currently.
And when the language compiler emits a tailcall sequence, however that
construct might look like, then it'll be translated as one.

As Dan already has outlined a Continuation doesn't have any impact on
tail calls (my argument WRT that was wrong) A tail call just uses the
current continuation of sub A and passes it on to the called sub B, so
that the called sub B returns to the caller of A.

Above is *without* tail calls. The next one was with tail calls, and it
obviously did succeed, because tail calls do not contribute to any kind
of stack depth. So there is for sure no limit. It's the same as an
iteration loop for the recursive tail call case - no limits.

leo

Do we really need it? Are there wicked cases, where we could misdetect a
tail call?

As far as I know is any sequence looking like:

    ...
    (a,b) = foo(...)
    .return (a,b)
  .end

a tail call. That is the call to a function immediately followed by a
return, which is the last operation of that function,  has the same
return value(s) as the actual return.
At least that's what the code with -Oc is checking now.

That's looking too much like some kind of perlish class thingy.

Why not just:

  .return->  foo(args)        # "return trough" token

leo

At 10:26 PM +0100 11/11/04, Leopold Toetsch wrote:

Cool.
--
                                Dan

--------------------------------------it's like this-------------------
Dan Sugalski                          even samurai
d...@sidhe.org                         have teddy bears and even
                                       teddy bears get drunk

That's great to hear (this is the point I was trying to make before).

Michael

At 10:13 PM +0100 11/11/04, Leopold Toetsch wrote:

Nope. The issue is one where the language guarantees the existence of
full traceback information. In that case optimizing a call and return
pair into a tail call's violating language guarantees, and we
shouldn't be doing that.

That works too. I'm easy.
--
                                Dan

--------------------------------------it's like this-------------------
Dan Sugalski                          even samurai
d...@sidhe.org                         have teddy bears and even
                                       teddy bears get drunk