C<caller> and Continuations

[Luke Palmer]

=head1 C<caller> and Continuations

Here's another "blend known paradigms" document from Luke. The idea
is to rethink C<caller> to provide even more information than it
already does, in an elegant way. To get us started:

As in Perl 5, the C<caller> function will return information about
the dynamic context of the current subroutine. Rather than always
returning a list, it will return an object that represents the
selected caller's context. (Apocalypse 6)

In brief, the semantics of C<caller> are to look up the stack until an
appropriate frame is found and return an object representing the
context at that point. In briefer, C<caller> gives information about
the stack.

It would make more sense, from an Object Oriented point of view, for
C<caller> just to give an object that knew about the stack, and query
it with methods. That way you could make more versatile queries (not
functionally, but more easily), and, for instance, pass it back inside
an exception object for a stack backtrace.

The magical C<caller()> function could return a handle by which
you can access the caller's C<my> variables. And in general, there
will be such a facility under the hood, because we have to be able
to construct the caller's lexical scope while it's being
compiled. (A6)

So now it needs access to each frame's lexical variables. That seems
reasonable, and because of object lifetime guarantees (complemented
with garbage collection), it poses no dangling reference problems.

You're probably way ahead of me, given the title of this paper.
That's right, throw in an execution point and we have ourselves all
the information that we need to go right back to where this object
refers. Yes, it's the makin's of a continuation.

If this object has a C<call> method (aliased by the funciton-call
operator) which replaces the current execution stack with the one it
represents, we now have a new way to return from a function:

sub one_plus($x) {
caller.call($x);
reformat_hard_drive; # Will never get here
}

Presumably, the argument to C<call> will be shoved in place of what
the return value was supposed to be.

So we have a way to get the caller's continuation, but a lot of
continuation-passing style is about I<current> continuations. Do we
have to have another function in the family of C<caller>, namely
C<here>? Sure, but it can be implemented in terms of C<caller>.

sub *here() {
return caller;
}

Snazzy, no?

Unfortunately, this is not particularly easy to work with. It's, in
fact, particularly hard to work with. Here's an implementation of a
simple coroutine given just these tools:

sub fact(Int $x, Continuation $caller) {
if $x == 0 {
return 1;
}
else {
my $result = $x * fact($x-1, $caller);
given here {
when defined { $caller.($result => $_) }
default { return $result }
}
}
}

given here {
when Continuation { fact(4, $_); }
when Pair { print .key; .value.(); }
}

The way Scheme (and various other languages) gets around this is with
a C<call-with-current-continuation> function, which resumes right
after the call. I'm going to call it C<branch>, for lack of a better
name that's less than 30 (!) characters long.

sub *here(?$id is rw) {
$id = \my $anon;
return caller but branched $id;
}

sub *branch( &code(Continuation) ) {
given here my $id {
when .branched == $id { undef .branched; code($_) }
default { $_ }
}
}

(Get it? This is fraud-proof, too, as long as you stay in the realm
of the Perl externals.)

Our factorial program now looks like:

sub fact(Int $x, Continuation $caller) {
if $x == 0 { return 1; }
else { branch { $caller.($x * fact($x-1, $caller) => $_) } }
}

my $rv = branch { fact(4, $_) };
print $rv.key;
while branch $rv.value -> $_ {
last when not Pair;
print $rv.key;
}

It's better, but as long as we're on the topic of adding layers of
continuation support to Perl, why not do coroutines as well? :)

sub *yield(*@_) { die "Yield while not in coroutine" }

class CoroutineIterator is Iterator {
submethod BUILD(&.code, @.args) { }

method next($self:) {
my @ret;
($.cc, @ret) := branch -> &back($,@) {
local &*yield(*@) = sub (*@_) {
branch { back $_, @_ }
}

if $.cc { $cc.call }
else { $self.code.(*@.args) }

undef; # When the coroutine returns
}
return *@ret;
}

has $.cc;
has &.code;
has @.args;
}

And now our factorial example closes as:

sub fact(Int $x) {
if $x == 0 { 1; }
else {
my $ret = $x * fact($x-1);
yield $ret;
return $ret;
}
}

my CoroutineIterator $i = new CoroutineIterator: &fact, 4;
print for <$i>;

Luke