# Copyright (C) 2007-2010, Parrot Foundation =head1 PDD 26: Compiler Tools - Abstract Syntax Tree =head2 Abstract This PDD describes the node types and semantics of the Parrot Abstract Syntax Tree representation. =head2 Description The Parrot Abstract Syntax Tree (PAST) is a set of Parrot classes useful for generating an abstract semantic representation of a program written in a high level language such as Perl or Python. Once a program has been translated into its equivalent PAST representation, the Parrot Compiler Toolkit can be used to generate executable PIR or bytecode from the abstract syntax tree representation. PAST is designed to provide the common operations and semantics needed by many of the high level languages targeted by Parrot, while also being extensible to support the unique needs of specific languages. =head2 Implementation =head3 PAST::Node C<PAST::Node> is the base class for all nodes in an abstract syntax tree. Each C<PAST::Node> element has an array of children nodes (which may be empty), as well as a number of attributes and accessor methods for the node. Every PAST node has C<name>, C<source>, and C<pos> attributes. The C<name> attribute is the node's name, if any, while C<source> and C<pos> are used to identify the location of the node in the original source code. =over 4 =item init([child1, child2, ..., ] [attr1=>val1, attr2=>val2, ...]) Initialize a PAST node with the given children and attributes. Adds each child to the node (using the C<push> method, below) and calls the appropriate accessor method for each attribute. =item new([child1, child2, ..., ] [attr1=>val1, attr2=>val2, ...]) Create a new PAST node with the same type as the invocant and initialized with the given children and attributes. Returns the newly created node. =item push(child) Add C<child> to the end of the node's array of children. =item pop() Remove the last child from the node's array of children. Returns the child. =item unshift(child) Add C<child> to the beginning of the node's array of children. =item shift() Remove the first child from the node's array of children. Returns the child. =item iterator( ) Return a newly initialized C<Iterator> for the node's list of children. =item node(val) Set the invocant's C<source> and C<pos> attributes to be the same as C<val>. If C<val> is another PAST node, then C<source> and C<pos> are simply copied from that node. Otherwise, C<val> is assumed to be a C<Match> object (e.g., from PGE) and the source and position information are obtained from that. =item name([value]) Accessor method -- sets/returns the C<name> attribute of the node. =item named([value]) Accessor method -- for nodes that are being used as named arguments, sets/returns the name to be associated with the argument. =item flat([value]) Accessor method -- sets/returns the "flatten" flag on nodes being used as arguments. =item attr(STR attrname, PMC value, INT has_value) Helper method for writing accessors -- if C<has_value> is true then set the node's value of C<attrname> to C<value>. Returns the (resulting) value of C<attrname> for the invocant. =back =head3 PAST::Stmts C<PAST::Stmts> is simply a C<PAST::Node> used to contain a sequence of other PAST nodes to be evaluated. It has no specific methods or attributes. =head3 PAST::Val C<PAST::Val> nodes represent constant values in the abstract syntax tree. The C<value> attribute represents the value of the node itself. =over 4 =item value([value]) Accessor method to get/set the constant value for this node. =item returns([typename]) Get/set the type of value to be generated by this node. If not specified, the type is taken from the type of the value attribute given above. =back =head3 PAST::Var C<PAST::Var> nodes represent variable-like items within the abstract syntax tree. The C<name> attribute (inherited from C<PAST::Node>) identifies the name of the variable as given by the high level language program. The other attributes for C<PAST::Var> nodes provide the details of how the variable is defined and accessed. =over 4 =item scope([value]) A variable node's "scope" indicates how the variable is to be defined or accessed within the program. The available scopes include: =over 4 =item "lexical" Lexical variables are scoped to the C<PAST::Block> in which they are declared, including any nested blocks. If the node's C<isdecl> attribute is true, then this node defines a new lexical variable within the current block. Otherwise, the node refers to a lexical variable already declared in the current or outer block. =item "package" Package variables represent global or namespace-managed variables in the program. The node's C<namespace> attribute may be used to explicitly identify the namespace of the variable, otherwise it is assumed to be within the namespace of the C<PAST::Block> containing the node. =item "parameter" Parameter variables are the formal arguments to subroutine and methods, typically represented as C<PAST::Block> nodes. The parameter's lexical name is given by the node's C<name> attribute. Positional parameters are defined by the order in which they appear in the C<PAST::Block> node, named parameters have values for the C<named> attribute. Optional parameters are identified via the C<viviself> attribute (see below) indicating how the parameter is to be initialized if not supplied by the caller. Slurpy parameters are indicated via the node's C<slurpy> attribute. =item "keyed" Keyed variables represent the elements of aggregates such as arrays and hashes. Nodes representing keyed elements have two children; the first child is the PAST representation of the aggregate, and the second child is the PAST representation of the key or index. The C<vivibase> attribute below may be used to specify how to generate the aggregate if it doesn't already exist. =item "attribute" Attribute variables represent object attributes (in some languages they're called "member variables"). The attribute's name is given by the node's C<name> attribute. Nodes representing attribute variables have an optional child, representing the object to which the attribute belongs. If this child is not present, the attribute is assumed to belong to the current invocant, indicated by the special variable C<self> (which is implicitly passed to all subs that are flagged as a C<:method> or C<:vtable>). =item "register" Register variables are limited in scope to the C<PAST::Block> node in which they are declared. This is different from the C<lexical> scope, which I<includes> any nested C<PAST::Block> nodes. If the node's C<isdecl> attribute is true, then this node defines a new register variable within the current block. Register variables are mapped to Parrot registers, and are useful for handling the PIR pseudo-variable C<self> and storing intermediate results. Names given to the C<name> attribute must conform to rules for PIR identifiers. If no C<name> attribute is set, Parrot registers are used. In this case, setting the C<isdecl> does not have any effect. =back If C<scope> is not explicitly provided in the node, then PAST will look at the local symbol tables of any outer C<PAST::Block> nodes to try to determine the scope of the named variable. If this still does not result in a scope, then 'lexical' is assumed. =item viviself([value]) Accessor method for the C<viviself> attribute, which specifies how uninitialized variables are to be initialized when first used. The C<viviself> attribute may be either a string or array representing a type (e.g., C<Integer>), or it may be a PAST representation for generating the variable's initial value. =item vivibase([value]) Accessor method for the C<vivibase> attribute, which specifies how the base portion of aggregate variables (see "keyed scope" above) is to be created if it doesn't already exist. C<Vivibase> may either be a string or array representing the type of the newly created aggregate, or it may be a PAST representation for generating the aggregate. =item isdecl([flag]) Accessor method for the C<isdecl> attribute. A true value of C<isdecl> indicates that the variable given by this node is being created at this point within the current lexical scope. Otherwise, the node refers to a pre-existing variable (possibly from an outer scope). =item lvalue([flag]) Accessor method for the C<lvalue> attribute, which indicates whether this variable is being used in an lvalue context. =item slurpy([flag]) Accessor method for the C<slurpy> attribute of parameter variables. A true value of C<slurpy> indicates that the parameter variable given by this node is to be created as a slurpy parameter (consuming all remaining arguments passed in). Named slurpy parameters are indicated by having a non-empty C<named> attribute and a true value of C<slurpy>. =back =head3 PAST::Op C<PAST::Op> nodes represent the operations in an abstract syntax tree. The primary function of the node is given by its C<pasttype> attribute, secondary functions may be indicated by the node's C<name>, C<pirop>, or other attributes as given below. =over 4 =item pasttype([value]) Accessor method for the node's C<pasttype> attribute. The C<pasttype> is the primary indicator of the type of operation to be performed, the operands are typically given as the children of the node. Defined values of C<pasttype> are: =over 4 =item chain A short-circuiting chain of operations. In a sequence of nodes with pasttype 'chain', the right operand of a node serves as the left operand of its parent. Each node is evaluated only once, and the first false result short-circuits the chain. In other words, C<< $x < $y < $z >> is true only if $x < $y and $y < $z, but $y only gets evaluated once. =item copy Copy the value of the node's second child into the variable expression given by its first child. =item bind Bind the variable given by the node's first child to the value given by its second child. =item if The first, second, and third children represent the "condition", "then", and "else" parts of a conditional expression. The first child is evaluated; if the result is true then the second child is evaluated and returned as the result of the C<PAST::Op> node, otherwise the third child is evaluated and returned as the result. This implements the standard if-then-else logic needed by most higher level languages, and can also be used for implementing the ternary operator. If the node is missing its second ("then") or third ("else") child, then the result of the condition is used as the corresponding result of the operation. This makes it easy to implement the "short-circuit and" operator commonly used in many high level languages. For example, the standard C<&&> operator may be implemented using an "if" node, where the left operand is the first (condition) child, the right operand is the second (then) child, and the third child is left as null or uninitialized. It's also possible to build a "short-circuit or" (C<||>) operator using this pasttype, by setting the left operand to C<||> as the first child and the right operand as the I<third> child (leaving the second child as null). However, it's probably simpler to use the "unless" type as described below. =item unless Same as C<if> above, except that the second child is evaluated if the first child evaluates to false and the third child is evaluated if the first child evaluates to true. The C<unless> type can be used to implement "short-circuit or" semantics; simply set the first child to the left operand and the second child to the right operand, leaving the third child empty or uninitialized. If the first child evaluates to true it is returned as the result of the operation, otherwise the second child is evaluated and returned as the result. =item while Evaluate the first child (condition), if the result is true then evaluate the second child (body) and repeat. =item until Evaluate the first child (condition), if the result is false then evaluate the second child (body) and repeat. =item repeat_while, repeat_until Same as C<while> and C<until> above, except the second child is evaluated before the conditional first child is evaluated for continuation of the loop. =item for Iterate over the first child in groups of elements given by C<arity> (default 1). For each iteration, invoke the second child, passing the elements as parameters. =item call Call the subroutine given by the C<name> attribute, passing the results of any child nodes as arguments. If the node has no C<name> attribute, then the first child is assumed to evaluate to a callable subroutine, and any remaining children are used as arguments. =item callmethod Invoke the method given by C<name> on the first child, passing the results of any child nodes as arguments. If the node has no C<name> attribute, then the first child is evaluated as a method to be called, the second child is the invocant, and any remaining children are arguments to the method call. =item pirop Execute the PIR opcode given by the C<pirop> attribute. See the C<pirop> method below for details. This is also the default behavior when a C<pirop> attribute is set and C<pasttype> is not. =item inline Execute the sequence of PIR statements given by the node's C<inline> attribute (a string). See the C<inline> method below for details. =item return Generate a return exception, using the first child (if any) as a return value. =item try Evaluates the first child, if any exceptions occur then they are handled by the code given by the second child (if any). =item xor Evaluate the child nodes looking for exactly one true result to be returned. If two true results are encountered, the operation immediately short-circuits and returns false. Otherwise, after all children have been evaluated the result of any true child is used as the result of the operation, or the result of the last child if none of the children evaluated to true. =back =item pirop([opcode]) Get/set the PIR opcode to be executed for this node. Internally the PAST and POST (Parrot Opcode Syntax Tree) implementations understand the register types available for common PIR operations and will handle any needed register or constant conversion of operands automatically. Note that except for the C<assign> opcode, any destination is typically generated automatically and should not be explicitly given as a child operand to the node. The table of PIR opcodes that PAST "knows" about is given in F<compilers/pct/src/PAST/Compiler.pir> . =item lvalue([flag]) Get/set whether this node is an lvalue, or treats its first child as an lvalue (e.g., for assignment). =item inline([STRING code]) Get/set the code to be used for inline PIR when C<pasttype> is set to "inline". The C<code> argument is PIR text to be inserted in the final generated code sequence. Sequences of "%0", "%1", "%2", ... "%9" in C<code> are replaced with the evaluated results of the first, second, third, ..., tenth children nodes. (If you need more than ten arguments to your inline PIR, consider making it a subroutine call instead.) The register to hold the result of the inline PIR operation is given by "%r", "%t", or "%u" in the C<code> string: %r - Generate a unique PMC register for the result. %t - Generate a unique PMC register for the result, and initialize it with an object of type C<returns> {{Pm: or possibly C<viviself> }} before the execution of the inline PIR. %u - Re-use the first child's PMC (%0) if it's a temporary result, otherwise same as %t above. If none of %r, %t, or %u appear in C<code>, then the first child's (%0) is used as the result of this operation. =back =head3 PAST::Block C<PAST::Block> nodes represent lexical scopes within an abstract syntax tree, and roughly translate to individual Parrot subroutines. A C<PAST::Block> node nested within another C<PAST::Block> node acts like a nested lexical scope. If the block has a C<name> attribute, that becomes the name of the resulting Parrot sub. Otherwise, a unique name is automatically generated for the block. Each PAST::Block node can maintain its own local symbol table, see the C<symbol> method below. =over 4 =item blocktype([type]) Get/set the type of the block to C<type>. The currently understood values are 'declaration', 'immediate', and 'method'. 'Declaration' indicates that a block is simply being defined at this point, the result of the node is a reference to the block. A C<blocktype> of 'immediate' indicates a block that is to be immediately executed when it is evaluated in the AST, and the result of the last operation is used as the return value for the block. =item closure([value]) Get/set the closure flag for the block to C<value>. If the closure flag on a (non-immediate) block is true, then the node returns a reference to a clone of the block that has captured the current lexical context. =item namespace([value]) Get/set the namespace for this particular block (and any nested blocks that do not explicitly provide a namespace). C<Value> may either be a simple string or an array of strings representing a nested namespace. =item hll([value]) Get/set the HLL namespace for this block (and any nested blocks that do not explicitly provide a C<hll>). =item symbol(name, [attr1 => val1, attr2 => val2, ...]) Each PAST::Block node can use the C<symbol> method to maintain its own compile-time notion of a local symbol table. Each value of C<name> is given its own hash to hold information about that symbol for the block (i.e., the symbol table acts like a hash of hashes indexed by symbol name). If the C<symbol> method is called with named arguments, then the method sets the entries in the hash corresponding to C<name> in the block's symbol table. If C<symbol> is called with just a single C<name> argument, then the current hash for local symbol C<name> is returned. HLLs are free to place any values in the symbol hashes that may be useful. However, the C<scope> entry for a symbol is typically used to provide the C<scope> attribute for any nested C<PAST::Var> nodes that do not provide an explicit C<scope> attribute. =item symbol_defaults([attr1 => val1, attr2 => val2, ...]) Sets default attributes for symbols that aren't explicitly given by the C<symbol> method above. For example, an abstract syntax tree can use this method on a top-level C<PAST::Block> to specify the C<scope> attribute to be used for all variable nodes that don't otherwise provide one. =item subid([value]) Get/set the unique subid to be used for this block. If no subid is explicitly set, a unique subid is randomly generated for the block. =item pirflags([value]) Get/set any PIR flags to be used when generating the block. =item compiler([compiler_name]) Specify that the children nodes of this block are to be compiled using C<compiler_name> instead of being treated as standard PAST nodes. This is useful when a program may contain components of code written in other HLLs. For example, the C<perl6> compiler uses this feature to use PGE to compile pre-parsed Perl 6 regular expressions, rather than trying to represent the semantics of those expressions in PAST itself. When code is generated from a C<PAST::Block> node having a C<compiler> attribute, the compiler is invoked with C<name> and C<outer> arguments so that any generated subs can have names and lexical scoping appropriate to the block (it's the responsibility of the external compiler to support this). =back =head3 PAST::CompUnit C<PAST::CompUnit> nodes are used for the abstract representation of compilation units. Specific attributes and semantics are yet to be determined. =head2 References None. =cut __END__ Local Variables: fill-column:78 End: vim: expandtab shiftwidth=4: