Posts in this category
- Current State of Exceptions in Rakudo and Perl 6
- Meet DBIish, a Perl 6 Database Interface
- doc.perl6.org and p6doc
- Exceptions Grant Report for May 2012
- Exceptions Grant Report -- Final update
- Perl 6 Hackathon in Oslo: Be Prepared!
- Localization for Exception Messages
- News in the Rakudo 2012.05 release
- News in the Rakudo 2012.06 release
- Perl 6 Hackathon in Oslo: Report From The First Day
- Perl 6 Hackathon in Oslo: Report From The Second Day
- Quo Vadis Perl?
- Rakudo Hack: Dynamic Export Lists
- SQLite support for DBIish
- Stop The Rewrites!
- Upcoming Perl 6 Hackathon in Oslo, Norway
- A small regex optimization for NQP and Rakudo
- Pattern Matching and Unpacking
- Rakudo's Abstract Syntax Tree
- The REPL trick
- First day at YAPC::Europe 2013 in Kiev
- YAPC Europe 2013 Day 2
- YAPC Europe 2013 Day 3
- A shiny perl6.org site
- Creating an entry point for newcomers
- An offer for software developers: free IRC logging
- Announcing try.rakudo.org, an interactive Perl 6 shell in your browser
- Another perl6.org iteration
- Blackjack and Perl 6
- Why I commit Crud to the Perl 6 Test Suite
- This Week's Contribution to Perl 6 Week 5: Implement Str.trans
- This Week's Contribution to Perl 6
- This Week's Contribution to Perl 6 Week 8: Implement $*ARGFILES for Rakudo
- This Week's Contribution to Perl 6 Week 6: Improve Book markup
- This Week's Contribution to Perl 6 Week 2: Fix up a test
- This Week's Contribution to Perl 6 Week 9: Implement Hash.pick for Rakudo
- This Week's Contribution to Perl 6 Week 11: Improve an error message for Hyper Operators
- This Week's Contribution to Perl 6 - Lottery Intermission
- This Week's Contribution to Perl 6 Week 3: Write supporting code for the MAIN sub
- This Week's Contribution to Perl 6 Week 1: A website for proto
- This Week's Contribution to Perl 6 Week 4: Implement :samecase for .subst
- This Week's Contribution to Perl 6 Week 10: Implement samespace for Rakudo
- This Week's Contribution to Perl 6 Week 7: Implement try.rakudo.org
- What is the "Cool" class in Perl 6?
- Report from the Perl 6 Hackathon in Copenhagen
- Custom operators in Rakudo
- A Perl 6 Date Module
- Defined Behaviour with Undefined Values
- Dissecting the "Starry obfu"
- The case for distributed version control systems
- Perl 6: Failing Softly with Unthrown Exceptions
- Perl 6 Compiler Feature Matrix
- The first Perl 6 module on CPAN
- A Foray into Perl 5 land
- Gabor: Keep going
- First Grant Report: Structured Error Messages
- Second Grant Report: Structured Error Messages
- Third Grant Report: Structured Error Messages
- Fourth Grant Report: Structured Error Messages
- Google Summer of Code Mentor Recap
- How core is core?
- How fast is Rakudo's "nom" branch?
- Building a Huffman Tree With Rakudo
- Immutable Sigils and Context
- Is Perl 6 really Perl?
- Mini-Challenge: Write Your Prisoner's Dilemma Strategy
- Longest Palindrome by Regex
- Perl 6: Lost in Wonderland
- Lots of momentum in the Perl 6 community
- Monetize Perl 6?
- Musings on Rakudo's spectest chart
- My first executable from Perl 6
- My first YAPC - YAPC::EU 2010 in Pisa
- Trying to implement new operators - failed
- Programming Languages Are Not Zero Sum
- Perl 6 notes from February 2011
- Notes from the YAPC::EU 2010 Rakudo hackathon
- Let's build an object
- Perl 6 is optimized for fun
- How to get a parse tree for a Perl 6 Program
- Pascal's Triangle in Perl 6
- Perl 6 in 2009
- Perl 6 in 2010
- Perl 6 in 2011 - A Retrospection
- Perl 6 ticket life cycle
- The Perl Survey and Perl 6
- The Perl 6 Advent Calendar
- Perl 6 Questions on Perlmonks
- Physical modeling with Math::Model and Perl 6
- How to Plot a Segment of a Circle with SVG
- Results from the Prisoner's Dilemma Challenge
- Protected Attributes Make No Sense
- Publicity for Perl 6
- PVC - Perl 6 Vocabulary Coach
- Fixing Rakudo Memory Leaks
- Rakudo architectural overview
- Rakudo Rocks
- Rakudo "star" announced
- My personal "I want a PONIE" wish list for Rakudo Star
- Rakudo's rough edges
- Rats and other pets
- The Real World Strikes Back - or why you shouldn't forbid stuff just because you think it's wrong
- Releasing Rakudo made easy
- Set Phasers to Stun!
- Starry Perl 6 obfu
- Recent Perl 6 Developments August 2008
- The State of Regex Modifiers in Rakudo
- Strings and Buffers
- Subroutines vs. Methods - Differences and Commonalities
- A SVG plotting adventure
- A Syntax Highlighter for Perl 6
- Test Suite Reorganization: How to move tests
- The Happiness of Design Convergence
- Thoughts on masak's Perl 6 Coding Contest
- The Three-Fold Function of the Smart Match Operator
- Perl 6 Tidings from September and October 2008
- Perl 6 Tidings for November 2008
- Perl 6 Tidings from December 2008
- Perl 6 Tidings from January 2009
- Perl 6 Tidings from February 2009
- Perl 6 Tidings from March 2009
- Perl 6 Tidings from April 2009
- Perl 6 Tidings from May 2009
- Perl 6 Tidings from May 2009 (second iteration)
- Perl 6 Tidings from June 2009
- Perl 6 Tidings from August 2009
- Perl 6 Tidings from October 2009
- Timeline for a syntax change in Perl 6
- Visualizing match trees
- Want to write shiny SVG graphics with Perl 6? Port Scruffy!
- We write a Perl 6 book for you
- When we reach 100% we did something wrong
- Where Rakudo Lives Now
- Why Rakudo needs NQP
- Why was the Perl 6 Advent Calendar such a Success?
- What you can write in Perl 6 today
- Why you don't need the Y combinator in Perl 6
- You are good enough!
Sun, 31 Mar 2013
Rakudo's Abstract Syntax Tree
After or while a compiler parses a program, the compiler usually translates the source code into a tree format called Abstract Syntax Tree, or AST for short.
The optimizer works on this program representation, and then the code generation stage turns it into a format that the platform underneath it can understand. Actually I wanted to write about the optimizer, but noticed that understanding the AST is crucial to understanding the optimizer, so let's talk about the AST first.
The Rakudo Perl 6 Compiler uses an AST
format called QAST. QAST nodes derive from the common superclass
QAST::Node, which sets up the basic structure of all QAST
classes. Each QAST node has a list of child nodes, possibly a hash map for
unstructured annotations, an attribute (confusingly) named
for storing the lower-level parse tree (which is used to extract line numbers
and context), and a bit of extra infrastructure.
The most important node classes are the following:
- A list of statements. Each child of the node is considered a separate statement.
- A single operation that usually maps to a primitive operation of the underlying platform, like adding two integers, or calling a routine.
- QAST::IVal, QAST::NVal, QAST::SVal
- Those hold integer, float ("numeric") and string constants respectively.
- Holds a reference to a more complex object (for example a class) which is serialized separately.
- A list of statements that introduces a separate lexical scope.
- A variable
- A node that can evaluate to different child nodes, depending on the context it is compiled it.
To give you a bit of a feel of how those node types interact, I want to give a few examples of Perl 6 examples, and what AST they could produce. (It turns out that Perl 6 is quite a complex language under the hood, and usually produces a more complicated AST than the obvious one; I'll ignore that for now, in order to introduce you to the basics.)
Ops and Constants
23 + 42 could, in the simplest case, produce
QAST::Op.new( :op('add'), QAST::IVal.new(:value(23)), QAST::IVal.new(:value(42)), );
QAST::Op encodes a primitive operation, an addition of
two numbers. The
:op argument specifies which operation to use.
The child nodes are two constants, both of type
hold the operands of the low-level operation
Now the low-level
add operation is not polymorphic, it always
adds two floating-point values, and the result is a floating-point value
again. Since the arguments are integers and not floating point values, they
are automatically converted to float first. That's not the desired semantics for Perl 6; actually the operator
+ is implemented as a subroutine of name
&infix:<+>, so the real generated code is closer to
QAST::Op.new( :op('call'), :name('&infix:<+>'), # name of the subroutine to call QAST::IVal.new(:value(23)), QAST::IVal.new(:value(42)), );
Variables and Blocks
Using a variable is as simple as writing
QAST::Var.new(:name('name-of-the-variable')), but it must be declared
first. This is done with
But there is a slight caveat: in Perl 6 a variable is always scoped to a
block. So while you can't ordinarily mention a variable prior to its
declaration, there are indirect ways to achieve that (lookup by name, and
eval(), to name just two).
So in Rakudo there is a convention to create
QAST::Stmts children. The first holds all the
declarations, and the second all the actual code. That way all the declaration
always come before the rest of the code.
my $x = 42; say $x compiles to roughly this:
QAST::Block.new( QAST::Stmts.new( QAST::Var.new(:name('$x'), :decl('var'), :scope('lexical')), ), QAST::Stmts.new( QAST::Op.new( :op('p6store'), QAST::Var.new(:name('$x')), QAST::IVal.new(:value(42)), ), QAST::Op.new( :op('call'), :name('&say'), QAST::Var.new(:name('$x')), ), ), );
Polymorphism and QAST::Want
Perl 6 distinguishes between native types and reference types. Native types are closer to the machine, and their type name is always lower case in Perl 6.
Integer literals are polymorphic in that they can be either a native
int or a "boxed" reference type
To model this in the AST,
QAST::Want nodes can contain
multiple child nodes. The compile-time context decides which of those is
So the integer literal
42 actually produces not just a simple
QAST::IVal node but rather this:
QAST::Want.new( QAST::WVal(Int.new(42)), 'Ii', QAST::Ival(42), )
Int.new(42) is just a nice notation to indicate a
boxed integer object; it doesn't quite work like this in the code that
translate Perl 6 source code into ASTs).
The first child of a
QAST::Want node is the one used by
default, if no other alternative matches. The comes a list where the elements
with odd indexes are format specifications (here
integers) and the elements at even-side indexes are the AST to use in that
An interesting format specification is
'v' for void context,
which is always chosen when the return value from the current expression isn't
used at all. In Perl 6 this is used to eagerly evaluate lazy lists that are
used in void context, and for several optimizations.