Beefy Boxes and Bandwidth Generously Provided by pair Networks
Perl: the Markov chain saw

Comment on

( #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

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

  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Titles consisting of a single word are discouraged, and in most cases are disallowed outright.
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.
  • Log In?

    What's my password?
    Create A New User
    and all is quiet...

    How do I use this? | Other CB clients
    Other Users?
    Others avoiding work at the Monastery: (6)
    As of 2018-06-19 18:45 GMT
    Find Nodes?
      Voting Booth?
      Should cpanminus be part of the standard Perl release?

      Results (114 votes). Check out past polls.