1 # Copyright (C) 2008, Parrot Foundation.
6 PAST Building Blocks - A catalogue of PAST nodes and how to use them.
10 This document describes the PIR output for each type of Parrot Abstract Syntax
11 Tree (PAST) node, and all available attributes.
15 PAST::Node is the base class of all other PAST classes.
21 Sets this node's C<source> and C<pos> attributes. These indicate which part of
22 the source code generated this node. The C<node> attribute can be set using
23 another node or a Match object.
25 The C<:node> attribute is needed for annotating a source line. If a source line
26 is represented by several nodes, i.e. a subtree of the whole AST, then only the
27 root of that subtree needs to have the C<:node> attribute.
31 See L<docs/pdd26_ast.pod>.
39 Without any attributes, a PAST::Block translates to the following:
52 A block represents a lexical C<scope>. The most common use for a block
53 is subroutines (or functions or procedures or whatever name Your Language
54 gives to invokable objects). Usually, C<nested> blocks define a new scope
55 as well, which can also be represented by a block. A typical example is
56 the common C<if> statement (the example here uses Lua syntax):
64 A variable in C<block1> is (depending on the language) usually not visible
65 in C<block2>. If the statements in the body of the C<if> statement are not
66 in a different scope, use a PAST::Stmts node instead.
72 Sets the namespace of the block to the specified value.
76 will result in a directive:
80 {{XXX how to specify nested namespaces? what kind of string array?}}
90 Default value. The block is created, but not invoked. This is typically used
91 for creating functions.
95 The block is invoked immediately. When the :blocktype attribute is set to this
96 value, the generated PIR becomes:
102 get_global $P11, "_block10"
103 newclosure $P11, $P11
114 The sub C<anon> is the I<main> function, which is the entry point of the
115 whole program. It looks for the sub that we declared, creates a new closure
116 from that block (more on that later), and invokes that closure.
122 Gives a name to the block. The generated PIR subroutine is named by the
123 value of this attribute. Example:
125 PAST::Block.new( :name('foo') )
139 As a block defines a new scope, a PAST::Block object has a symbol table,
140 which can be used to store and look up symbols. See PDD26 for more details.
141 A PAST::Block node has a method C<symbol> used to both enter and find symbols.
143 The C<symbol> method takes the symbol name as an argument, and optional
144 attributes. If the symbol does not exist in the table, a new hash is created
145 for that symbol. Any additional attribute arguments are set into this new hash.
146 The C<symbol> method returns the current entry for the specified name. Checking
147 for a symbol in a symbol table is as easy as:
149 our $?BLOCK; # the current scope
151 if $?BLOCK.symbol('foo') {
152 # symbol 'foo' was found
155 # symbol 'foo' was not found
159 XXX Review this; this should refer to PAST compiler's symbol() method.
161 If a symbol is not found in a block's symbol table, any outer blocks
162 (outer scopes) will be inspected. The symbol table entry of the innermost
163 scope is returned. For instance, consider the following Perl 6 code:
174 In the subroutine C<baz>, the variable C<$i> is referenced. It is not
175 found in the symbol table of C<baz>, so it is looked for in baz' outer
176 scope, C<bar>. It's not found there either, so bar's outer scope, C<foo>
177 is inspected, where it is found.
190 The common use of a PAST::Stmts node is to group a set of statements. Most
191 programming languages have a grammar rule that similar to this:
198 In order to move around the PAST nodes representing these individual statements,
199 it is useful to group them and store them in one node. This can be done by
200 storing all PAST nodes in a PAST::Stmts node.
201 Note that PAST does not define a C<statement>; any PAST node can be considered
202 a statement, including a PAST node as simple as PAST::Val.
208 PAST::Var.new( :name('foo'), :scope('lexical') )
220 Nodes of type PAST::Var are used to represent variables and their declarations
221 (based on the C<:isdecl> flag, see below). Wherever a variable is used in the
222 source language, this can be represented by a PAST::Var node.
226 =head3 C<:name> (required)
228 Sets the name of the variable. This attribute is required.
232 Set the scope of this PAST::Var node. If the C<:scope> is not set, it is
233 inherited from the symbol table entry in a PAST::Block's symbol table.
234 If the scope is not set, the scope defaults to C<lexical>.
242 When the C<:scope> attribute is set to C<lexical>, then the identifier
243 specified in the C<:name> attribute is handled as a lexical:
253 Defines the variable as a C<package> variable. This is handled by the
254 C<get_global> and C<set_global> ops.
258 Defines the variable as a parameter (but is stored as a lexical).
269 my $idx := PAST::Var.new( :name('foo'), :scope('package') );
270 my $agg := PAST::Var.new( :name('bar'), :scope('package') );
271 make PAST::Var.new( $agg, $idx, :scope('keyed') );
277 get_global $P10, "foo" # get index, a package-scoped variable "foo"
278 get_global $P11, "bar" # get aggregate, a package-scoped variable "bar"
279 set $P12, $P11[$P10] # get the contents at bar[foo]
285 Defines the variable as an attribute of an object. The first child of
286 the PAST::Var node evaluates to the object from which the attribute is
287 requested. If there is no such child, the object defaults to C<self>,
288 meaning the current invocant.
290 make PAST::Var.new( PAST::Var.new( :name('foo'), :scope('package') ),
297 =begin PIR_FRAGMENT_INVALID
299 get_global $P10, "foo"
300 get_attribute $P11, $P10, "bar"
302 =end PIR_FRAGMENT_INVALID
304 Note: currently, no child nodes are evaluated, so you can only get
305 attributes on C<self> for now.
309 =head3 C<:isdecl(INT)>
311 If this flag is set, the variable represented by this PAST::Var node is
312 declared at this point. This flag is cleared by default.
322 When this attribute is set, the variable is initialized with the value
323 represented by the PAST subtree given as this attribute's argument.
324 Adding this attribute will result in the following generated code:
326 <code for PAST::Var, leaving the variable in $P10>
327 unless_null $P10, vivify_11
328 <evaluate the child PAST node, leaving result in $P12>
334 Similar to C<:viviself>, but the value of this attribute yields the
335 initialization code for an aggregate object. See L<pdd26_ast.pod> for
342 PAST::Val.new( :value(42) )
355 All literal values in your source language can be represented by
360 =head3 C<:value> (required)
362 Specifies the literal value that is represented by this PAST::Val node.
366 Specifies the type of the value. If this is not specified, then some
367 defaults are used. For integer values, this is C<Integer>, for quoted
368 strings this is C<String>; for floating point values, this is C<Float>.
378 Used to group a number of PAST::Var nodes.
385 PAST::Op.new( :pasttype('if') )
389 PAST::Op nodes are used to represent common operations, such as an
390 C<if> statement, a sub C<call>. They can also be used to generate
391 custom PIR instructions, using the C<:inline> attribute.
402 Requires at least 1 child node, which is evaluated as the conditional
405 <evaluate 1st child, result stored in $P11>
407 <else part (3rd child); optional>
410 <then part (2nd child); optional>
415 Same as C<if>, except that the C<if> op is replaced by the C<unless> op.
419 Requires 2 children; the first is the loop condition, the second is the
423 <evaluate 1st child, result stored in $P11>
424 unless $P11, while_10_end
431 Same as C<while>, except the loop is executed while the condition evaluates
434 =item C<call> (default)
436 PAST::Op.new( :name('foo'), :pasttype('call') );
448 my $fun := PAST::Var.new( :name('foo'), :scope('package'));
449 PAST::Op.new( $fun, :pasttype('call') );
455 get_global $P10, "foo"
460 Children of a :pasttype('call') node are evaluated and passed as arguments.
461 If the node does not receive a C<:name> attribute, then the first child
462 is evaluated as the subroutine to be invoked.
466 my $invocant := PAST::Var.new( :name('foo'), :scope('package') );
467 PAST::Op.new( $invocant,
469 :pasttype('callmethod')
476 get_global $P10, "foo"
483 Binds the variable represented by the first child to the value
484 represented by the second child.
486 my $lhs := PAST::Var.new( :name('foo'), :scope('package') );
487 my $rhs := PAST::Val.new( :value(42) );
488 make PAST::Op.new($lhs, $rhs, :pasttype('bind') );
494 new $P10, "Integer" # code for evaluating $rhs
496 set_global "foo", $P10 # code for the :pasttype('bind') op
500 when the scope is set to C<lexical>, the last line becomes:
504 store_lex "foo", $P10
512 If this attribute is specified, C<:pasttype> is implicitly set
513 to the value of C<inline>. The specified string is emitted in the
514 code generator. The string may contain special fields: %n where n
515 is an integer value between (0,9); %r, %t and %u. See the PDD for
520 my $var := PAST::Var.new( :name('foo'), :scope('lexical') );
521 PAST::Op.new( $var, :inline(' %r = %0') );
527 find_lex $P10, "foo" # generated for $var
528 $P11 = $P10 # inline '%r = %0'
532 =head1 TIPS AND TRICKS
534 Once you have experience in using PAST nodes, generating code for
535 Your Favorite Language becomes rather straightforward. However, it
536 is sometimes tricky to get started. Therefore, this section presents
537 some tips 'n' tricks to get you started.
539 =head2 Refactor Grammar Rules
543 Sometimes it is useful to refactor the grammar of your language in
544 order to make code generation somewhat easier or to make the action
545 method easier. Consider the following example.
548 [ <prefix> | <functioncall> ] <expression>
552 method primary_expr($/) {
555 $past := $( $<prefix> );
558 $past := $( $<functioncall> );
560 my $expr := $( $<expression> );
562 # do something with $past and $expr
566 while this solution is straightforward, the code in the action method
567 contains a conditional statement. The more branches you have in your
568 code, the more you need to think when you re-read this in 6 months time.
569 An alternative solution would be this:
572 <prefix_expr> <expression>
577 | <prefix> {*} #= prefix
578 | <functioncall> {*} #= functioncall
581 method primary_expr($/) {
582 my $past := $( $<prefix_expr> );
583 my $expr := $( $<expression> );
585 # do something with $past and $expr
589 method prefix_expr($/, $key) {
593 While you have to write a bit more code, this code is more straightforward.
594 While there might be a small cost in function call overhead, there is no
595 longer the conditional statement, which itself is more efficient.
599 Consider a language that uses an index notation to indicate fields (attributes),
604 this language also has some syntactic sugar for this, using a dot notation:
608 This can be expressed in the following grammar rules:
616 | '.' <ident> {*} #= ident
617 | '[' <quote> ']' {*} #= quote
620 A naive implementation could look like this:
623 my $name := $( $<ident> );
626 my $idx := $( $<index>[0] );
627 # do something with $idx
632 method index($/, $key) {
633 my $indexexpr := $( $/{$key} );
635 # if $indexexpr is an identifier, stringify it
637 $indexexpr := PAST::Val.new( :returns('String'), :value($indexexpr) );
642 Somewhere you have to check the type of index. Not only does this
643 result in more complex code (more conditional statements), it is
644 less efficient, as an extra PAST node must be created.
646 A more elegant solution is to refactor the grammar slightly, like so:
649 | <dot_field> {*} #= dot_field
650 | '[' <quote> ']' {*} #= quote
658 method index($/, $key) {
662 method dot_field($/) {
663 my $field := $( $<ident> );
664 make PAST.Val.new( :returns('String'), :value($field) );
667 There is no more conditional code, it's just a matter of computations;
668 based on the type of index, do the right thing automatically.
671 =head2 Create PAST nodes I<deep> in the parse tree
673 Consider a grammar fragment such as this:
676 'function' <ident> '(' <parameters>? ')' <block> 'end'
681 <ident> [',' <ident>]*
685 You could write the action methods for these rules as follows:
687 method function_def($/) {
688 my $past := PAST::Block.new( :node($/) );
691 # get the PAST::VarList that contains all parameters
692 my $params := $( $<parameters>[0] );
694 # put all of them into the PAST::Block node
700 $past.name( $( $<ident> ) );
701 $past.push( $( $<block> ) );
705 method parameters($/) {
706 my $past := PAST::VarList.new( :node($/) );
709 $param.scope('parameter');
710 $past.push( $param );
715 While this solution works well, this is suboptimal. In the
716 action method for <parameters>, a PAST::VarList node is created,
717 which is only used to move around the parameter identifiers, and
719 An alternative solution would be to create the PAST::Block node
720 that represents the function in the action method for <parameters>.
721 This makes perfect sense, as the only place where the parameters
722 should live is in that function block. Then, in the action method
723 for C<function_def>, this PAST::Block node is retrieved and
724 I<decorated> with other values (such as a function name, for instance)
725 and the PAST node for the function body. Only if there are no parameters
726 should the action method for C<function_def> create a PAST::Block node.
728 The result could look like this:
730 method function_def($/) {
733 $past := $( $<parameters>[0] );
735 else { # no parameters, create the function block here
736 $past := PAST::Block.new( :node($/) );
738 $past.name( $( $<ident> ).name() );
739 $past.push( $( $<block> ) );
742 method parameters($/) {
743 my $past := PAST::Block.new( :node($/) );
746 $param.scope('parameter');
747 $past.push( $param );
752 A further refactor could result in even simpler code:
755 'function' <ident> '(' <parameters> ')' <block> 'end'
760 [ <ident> [',' <ident>]* ]?
763 method function_def($/) {
764 my $past := $( $<parameters> );
765 $past.name( $( $<ident> ).name() );
766 $past.push( $( $<block> ) );
770 method parameters($/) {
771 my $past := PAST::Block.new( :node($/) );
773 my $param := $( $<ident> );
774 $param.scope('parameter');
780 Note that the rule C<parameters> is changed slightly. For indexing
781 the C<ident> nodes, this makes no difference, as they already lived
782 in an array. Making all of them optional doesn't change the way they
783 are stored in the parse tree.
785 The same principle can be applied in several scenarios.
786 More tips will be added later.
788 =head2 Steal from Perl 6
790 You are implementing a language and you want to find out which PAST nodes
791 you should generate for your language construct. Often Perl 6 has the same
792 language construct. This means that you can write a quick example script
793 in Perl 6 and look at the PAST generated by Rakudo (the Perl 6 implementation
796 ./perl6 --target=past t.pl
802 =item * docs/pdds/pdd26_ast.pod
806 =head1 BUGS AND IMPROVEMENTS
808 Bug reports and improvements on this document may be sent to
809 C<parrotbug@parrotcode.org>.