Strangely Consistent

Theory, practice, and languages, braided together

Macros progress report: quantum yak shaving

Ah, the busy life. I knew April was going to be filled with $work, but it still pulled me away from blogging more than I expected. But things have been moving along with the macros grant work. This post is about that.

As you might remember from my last macros grant status update, I expected to take a yak shaving detour:

Looking ahead a bit, what's up next is D2. Informally, D2 consists of "getting those little {{{$stuff}}} thingies to work". We need a way to represent "there's a placeholder here" in the AST, because that's how the ASTs look during the static part of their lifetime (before macro application). It will require a new AST type. As it happens, PAST in nqp/Rakudo is just about to be replaced by the next generation of AST technology, and jnthn++ is just about to start working on that. So it makes sense for me to assist him, since I'm now blocking on the new AST technology landing in Rakudo for my macros work. Aside from blocking, I expect D2 to be quite easy to implement.

This "next generation of AST technology" is called QAST; that's what you get if you "increment" our current AST format PAST. Of course, as all geeks, we on the #perl6 channel love backformations.

<felher> What does the 'Q' in QAST stand for?
<PerlJam> P++
<felher> Okay, what did the P stand for? :D
<tadzik> Parrot, Perl
<masak> felher: the "P" always stands for "Patrick Michaud" :P
<masak> felher: the gradual spread of the letter "Q" in the entire toolchain
        is a reflection on the fact that Patrick Michaud is upgrading from his
        ordinary, impressive self to a superhuman cyborg with capabilities
        that defy physics as we know it.
<masak> or so I've heard.
<felher> Of course! I should have known that! :)
* [Coke] backscrolls, and suggests: Quantum Michaud.
<masak> that does sound like a superhero. a bit like Dr Manhattan.
<masak> Quantum Abstract Syntax Tree works quite well, too. practically a
        necessity if your language supports junctions :P

Let's talk about how QAST actually looks, and what I'm aiming to do here.

So, you have an expression like my $area := 50. During compilation, it parses into a QAST tree looking like this:

Op :op<bind>
+-- Var :name<$area>, :decl<var>
+-- IVal :value(50)

Yeah, I know, that's almost too simple. (I'm simplifying, but only a little bit. The remaining details are not important here.)

Now, for macros to work, as I said in the last post, we need a way to represent "there's a placeholder here". Think about a very similar expression, my $area := {{{$input}}}. Eventually, the {{{$input}}} bit will be executed, the $input will be evaluated, it better be found to be an AST fragment, and it will be spliced into the AST of the quasi, which then gets spliced into the program somewhere. But there are two phases here:

  1. The macro is parsed.
  2. A macro call is parsed, and...
    • the macro is called,
    • the quasi quote has its unquasi placeholders evaluated,
    • the resulting AST is returned from the macro, and
    • the AST gets spliced into the program code where the macro call was.

Between these two times, we need a form of storage for the yet-unevaluated {{{$input}}}. It's like an ingested pill whose water-soluble shell allows it to be transported into the stomach before it triggers.

We're making this shell a new QAST node, affectionately referred to as QAST::Unquote.

So the QAST tree in the case of my $area := {{{$input}}} would look like this:

Op :op<bind>
+-- Var :name<$area>, :decl<var>
+-- Unquote
    +-- Var :name<$input>

That's where I'm heading right now.

But what I've been working on so far has been all of the more basic bits of QAST. QAST isn't ready for prime time yet, and getting it there means working on the QAST compiler. It's great fun, and it gives me an introduction to QAST that I would probably have needed anyway.

Here's what I've done so far. You can sort of see how jnthn++ lets me have a go at bigger and bigger bits.

There's a bit left to go with building QAST. I don't know exactly how much. When it looks like our kit is relatively complete, I'll turn to implementing QAST::Unquote. I expect to blog again when this has happened.