Why Perl 5 Needs an AST

When I wrote Features Perl 5 Needs in 2012, I promised to explain my thinking. I've explained Why Perl 5 Needs a Metaobject Protocol and previously Why Perl 5 Needs a Compiler-Free Extension Mechanism.

(If you don't follow the latter link, ask yourself this: would you use Perl 5 on another VM if you didn't have access to the CPAN? As long as any CPAN stack you need includes an XS dependency, you're stuck with the C implementation of Perl 5. Break that dependency and... you see where this is going.)

If you read a good book on compilers such as SICP or the Dragon book or even a good book on Lisp, which is half of the same thing, you'll eventually run into the idea that you can represent any program in a tree-like structure.

That is to say, any type of computation you wish to perform can be represented with the right data structure, and that data structure happens to be a tree. Even the venerable "Hello, world!" program from K&R is a tree:

STATEMENTS
    / \
print  exit
  |      |
"Hello,  0
 world!"

(You can represent this tree in a lot of ways, but you get the idea.) As SICP explains, the execution model governs how you traverse this tree. Obviously in this tree, you start at the topmost node, then evaluate leftmost depthfirst until you end.

Even though your processor likely doesn't execute programs by traversing trees and your language's favorite runtime doesn't either, tree structures are still very useful in compilers because they're simple data structures that are easy to traverse and produce and manipulate.

This is one reason that fans of Lisp think that Lisp is the ultimate programming language: you write it by writing this tree directly as source code and you can manipulate that tree with source code as if it were a tree, because it is.

Many of the rest of us don't want to spend the rest of our lives writing trees by hand, but sometimes we do want to do things with source code without having to write our own compilers, or at least our own parsers.

Do you know know people say "Parsing Perl is Hard?" That's because it is. It's not impossible, but the Perl 5 parser is a complicated program that mixes up the traditional roles of lexing and parsing such that replicating that parse completely is difficult, at best. This is why writing a syntax highlighter for Perl 5 is more difficult than writing one for Lisp.

Do you know how something like Devel::Declare works? I do, and I don't want to explain it to you. It's not particularly yucky magic, but it's not particularly lovely magic either.

Do you know how Perl 5's optimizer works? It's very limited.

Do you know how Perl 5 source filters work? Not that well! That's why the Switch module was deprecated in the commit after it became a core module.

Do you know how PPI works? Most of the time, very well, but with lots of magic and a few very well understood edge cases and not a lot of speed.

All of these problems have the same root cause: it's exceedingly difficult to manipulate a Perl 5 program as anything other than text, because the one thing that unambiguously understands that program won't share its understanding.

(That's not entirely true; a few years ago, Larry added a compile-time option to Perl 5 to produce an annotated tree from the parser/lexer/compiler, but no one's done much with it.)

A traditional compiler parses a document into a tree structure, then manipulates that tree into at least one and probably more trees and finally emits code in another language. It's very patriotic (from tree to shining tree). This pattern is no accident; it's the basis of many programs (everything is a compiler).

This process is so well understood that patterns exist for treating this process as a pipeline of tree transformations. As long as you know what kind of tree you're going to get and what kind of tree you need to produce, you can add your own transformation step. (If that sounds like Plack middleware, there's no coincidence there either.)

A formalized AST in Perl 5, representing an official separation between the lexing/parsing and execution phases of Perl 5, made available to any and all programs would let people write better syntax highlighters, sure, but also better IDEs (finding function declarations and associating them with source code would be easier) or debuggers (see again "finding things) or optimizers (a pipeline of tree transformations) or transliterations to other VMs or languages (still not entirely easy but much more possible) or serialization mechanisms (avoid parsing; dump an AST to the execution engine) or even little languages atop Perl with their own parsers which compile to the Perl 5 AST and run as if they had been Perl all along.

Think about that last point for a moment.

(Think about that last point in the context of syntax weirding mechanisms like MooseX::Declare, or anything which uses string eval.)

Are you sold yet?

Here's the bad news: this is a lot of work. It needs expertise and it needs research and planning. It needs at least one champion, and it probably needs funding. The first approach will probably fail. It will take longer than anyone wants. The only way it will happen is if someone stubborn appears and says "I'll do that!" or "I'll fund that!" and gets just enough support to keep going past the difficult parts.

Imagine how amazing it will be, though.