use Perl

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
  $z,
  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 {
    Z,
    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 ],
    'h/2',
    [ 'REF' => 2 ],
    [ 'REF' => 3 ],
    [ 'STR' => 5 ],
    'f/1',
    [ 'REF' => 3 ],
    [ 'STR' => 8 ],
    'p/3',
    [ '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!