Beefy Boxes and Bandwidth Generously Provided by pair Networks
Your skill will accomplish
what the force of many cannot
 
PerlMonks  

comment on

( [id://3333]=superdoc: print w/replies, xml ) Need Help??
As you may know if you follow my use.perl journal or my posts to the perl6 language lists, I'm working on a Scheme implementation in Perl.

As it turns out, a basic interpreter for a schemelike language is surprisingly easy to implement. The problem is that, in order to be able to call it Scheme, you have to do 'tail call optimization'. "What's that then?" I hear you ask?

Well, here's a simple example. Consider the following piece of tail recursive perl:

sub tail_factorial { my($total, $n) = @_; if ($n == 0) { return $total; } else { return tail_factorial($total * $n, $n - 1) } }
notice that, in the 'else' branch of the code, we're simply returning the value of a further function call, we don't actually do anything with it in the current function. Wouldn't it be great if the 'if' branch of that conditional could just return directly to the 'original' caller of tail_factorial instead of having the result passed up a tower of intermediate callers.

Well, that's what tail call optimization is all about. A full implementation would do the optimization even in cases where the tail call isn't a straightforward recursive call (and that's what is needed for a 'proper' scheme implementation).

Note that you can sort of do tail call optimization in native Perl right now, but it's not exactly optimal. Here's here's that factorial function again:

sub tail_factorial { my $total = shift; my $n = shift; if ($n == 0) { return $total; } else { @_ = ($n * $total, $n - 1); goto &tail_factorial; } }
But it's scary, not desperately quick, and requires programmer intervention. Ideally this sort of thing should happen automatically. Larry has already said that simple tail recursion in Perl 6 will be optimized, but how do I make my scheme interpreter do the Right Thing in perl 5?

Well, frankly, it's scary. I've had to roll my own virtual machine, complete with registers and a stack (there's no call stack though, but eventually I'll implement a 'real' chain of partial continuations.) The driver loop for this machine looks something like:
sub run_ops { my $self = shift; EVAL_DISPATCH: while (1) { my $expr = $self->expr; if ($expr->is_self_evaluating) { $self->{value} = $expr; } else { $expr->evaluate($self); } while (1) { my $cont = $self->continuation; if (ref($cont) eq 'CODE') { $cont->($self); } elsif (!ref($cont)) { return $self->{value} if $cont eq 'return'; $self->$cont(); } else { die "Broken continuation: $cont" } } } }
Notice that labeled while loop. The idea is that, instead of calling $self->expr->evaluate($self) directly (doing a classic OO double dispatch trick), functions set up a continuation (the function that will 'carry on' once things have been evaluated), set 'expr' to an appropriate value and do redo EVAL_DISPATCH, which unwinds the call stack and jumps to the start of the loop again. This avoids recursing desperately deeply into multiple calls to evaluate (my naive, none tail recursive implementation could easily get 100s of levels deep).

The inner while loop is then responsible for handing control off to the current continuation, which will eventually, one hopes, get set to 'return' so the subroutine can exit.

It turns out that this simple loop combined with a small number of registers and a stack gives me enough that I can bootstrap scheme. My current problem is that my simpleminded scheme parser (implemented in perl) recurses far deeper than my interpreter, so I probably need to reimplement it on the virtual machine. (Something I'm going to have to do when I replace the virtual machine with Parrot anyway...). AFAICT it shouldn't be too hard to implement the full scheme call-with-current-continuation on this machine, as well as 'compiled' functions (but compiled functions are some way off for now).

I'm afraid the CPAN release is some way off too. At the very least I need to write a test suite and get a few more of the standard scheme things implemented and, who knows, maybe write some documentation.

And then there's the Parrot compiler to write. And something to compile to perl 5 as well. And the port to Perl 6 (I only started the perl 5 version to make sure that what I'd implemented in perl 6 would actually work), and then there's Inline::Scheme to write, and...


In reply to Pure Perl tail call optimization by pdcawley

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post; it's "PerlMonks-approved HTML":



  • Are you posting in the right place? Check out Where do I post X? to know for sure.
  • Posts may use any of the Perl Monks Approved HTML tags. Currently these include the following:
    <code> <a> <b> <big> <blockquote> <br /> <dd> <dl> <dt> <em> <font> <h1> <h2> <h3> <h4> <h5> <h6> <hr /> <i> <li> <nbsp> <ol> <p> <small> <strike> <strong> <sub> <sup> <table> <td> <th> <tr> <tt> <u> <ul>
  • Snippets of code should be wrapped in <code> tags not <pre> tags. In fact, <pre> tags should generally be avoided. If they must be used, extreme care should be taken to ensure that their contents do not have long lines (<70 chars), in order to prevent horizontal scrolling (and possible janitor intervention).
  • Want more info? How to link or How to display code and escape characters are good places to start.
Log In?
Username:
Password:

What's my password?
Create A New User
Domain Nodelet?
Chatterbox?
and the web crawler heard nothing...

How do I use this?Last hourOther CB clients
Other Users?
Others studying the Monastery: (6)
As of 2024-03-28 15:32 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found