Slash Boxes
NOTE: use Perl; is on undef hiatus. You can read content, but you can't post it. More info will be forthcoming forthcomingly.

All the Perl that's Practical to Extract and Report

use Perl Log In

Log In

[ Create a new account ]

Ovid (2709)

  (email not shown publicly)
AOL IM: ovidperl (Add Buddy, Send Message)

Stuff with the Perl Foundation. A couple of patches in the Perl core. A few CPAN modules. That about sums it up.

Journal of Ovid (2709)

Thursday July 24, 2008
07:28 AM

Warren Abstract Machine Tutorial

[ #37007 ]

If you've ever looked at the original paper for the Warren Abstract Machine (a fast, proven correct virtual machine for Prolog), your head probably hurts. That's why you probably want the WAM tutorial, by Hassan Aït-Kaci. It's still incredibly hard to work through and you have to read it carefully.

I initially tried to write a lexer/parser and then realized I was being stupid. Perl already includes its own lexer/parser for the Perl language itself! Thus, all I need to do is write Perl code which generates an abstract syntax tree. Easier said than done. My first pass looked like this:

p(   # example straight from the WAM tutorial
  h( $z, $w ),
  f( $w )

The problem with this our lack of lazy evaluation. The inner terms would get evaluated prior to the outer terms and I was losing some ordering information because I couldn't tell if various predicates were terms in another predicate. With a bit of trickery, I can make each predicate have an anonymous subroutine as an argument. They let me check to see if I'm in an anonymous sub and, if so, I know I'm contained in another predicate. (and yes, this is valid Perl code and those upper case letters really are variables).

p {
    h { Z, W },
    f { W }

That's the same thing, but the (&) prototype trick allowed me to capture just the extra bit of semantic information needed to proceed with parsing. Now my heap looks like this, just as in the WAM tutorial:

my @expected_heap = (
    [ 'STR' => 1 ],
    [ 'REF' => 2 ],
    [ 'REF' => 3 ],
    [ 'STR' => 5 ],
    [ 'REF' => 3 ],
    [ 'STR' => 8 ],
    [ 'REF' => 2 ],
    [ 'STR' => 1 ],
    [ 'STR' => 5 ],

eq_or_diff heap, \@expected_heap,
    '... and it should build our heap correctly';

I also have the registers correctly ordered, but there are some bits of the tutorial I need to read a bit more carefully to make sure I haven't done anything stupid. This is frickin' hard work!

The Fine Print: The following comments are owned by whoever posted them. We are not responsible for them in any way.
More | Login | Reply
Loading... please wait.