| ## AST Constructors

The heart of metaprogramming lies in the ability to construct and compose code fragments. This section presents the metaprogramming capabilities of creating and manipulating abstract syntax trees (ASTs) of the Jak language.

- What is a Code Constructor?
- What is a Code Escape?
- What are available Constructors and Escapes?
- How to convert a String or Integer to an AST?
- How to convert an AST into a String?
- How to print ASTs to files?
- Coding Techniques for writing Metaprograms

### What is a Code Constructor?

A code constructor converts a specification of a code fragment into an AST: the value of a constructor is a pointer to the AST's root. The expression constructor exp{...}exp, for example, encloses a syntactically correct Java expression. When the constructor is evaluated, an AST for that expression is created, and the root of that tree is the result. stm{...}stm is the corresponding constructor for statements.

>     Exp x = exp{ 7 + q*8 }exp;
>     AST_Stm y = stm{ foo(3); if (y<4) return r; }stm;

>     System.out.print(x);          // outputs "7 + q*8"
>     System.out.print(y);          // outputs "foo(c); if (y<4) return r;"

A code escape is a construct that allows previously defined code fragments to be substituted inside another code fragment. For example:

>     Exp x = exp{ 7 + x*8 }exp;
>     AST_Stm y = stm{ y = ($exp(x)) * 8; }stm;

>     System.out.println(y);        // outputs "y = ( 7 + q*8 ) * 8;"

That is, the $exp(e) escape substitutes the AST for variable e at the designated spot in the stm{...}stm code constructor. There are presently 17 different tree constructors.

> > We caution readers when using expression escapes. Consider the example below. When e is composed with s, the correct parse tree results. However, when printed, ambiguities arise. When escaping expressions, it is recommended that parentheses be used around the escape.

> > >     e = exp{ a + b }exp;
> > >     s = stm{ if (4 < $exp(e)) foo(); }stm;

> > >     s.print(props);   // outputs "if (4 < a + b) foo();" which is wrong

> > >     s = stm{ if (4 < ($exp(e))) foo(); }stm;

> > >     s.print(props);   // outputs "if (4 < (a + b)) foo();" which is correct

### What is a Code Escape?

ASTs are composed using escapes, the counterpart to the Lisp comma (unquote) construct. The example below shows a statement constructor with an escape $exp(body). When the constructor is evaluated, the AST of body is substituted in the position at which its escape clause appears.

>     AST_Stm body = stm{ if (i > 40) foo(i); }stm;
>     AST_Stm loop = stm{ for (i=1; i<10; i++) { $stm(body); } }stm;

>     System.out.print(loop);     // outputs "for (i=1; i<10; i++) {
>                           	    //            if (i > 40) foo(i); }"

Unlike Lisp and Scheme which have only a single constructor and escape operator (e.g., backquote and comma), multiple constructors in syntactically rich languages are common. The main reason has to do with the ease of parsing code fragments: each constructor produces a code fragment of particular type and each escape takes a code fragment of a particular type. In this way, code fragments that are created with tree constructors and composed with escapes should always be syntactically correct.

A complete program that shows a more complicated example illustrating several different tree constructors and escapes is shown below:

>     import jak2java.*;

>     class ex1 {
>        public static void main( String args[] ) {
>           AST_Modifiers m = mod{ public final }mod;
>           AST_Exp e = exp{ i+1 }exp;
>           AST_FieldDecl f = mth{ int i; int inc( int i ) { return $exp(e); } }mth;
>           AST_TypeNameList t= tlst{ empty }tlst;
>           AST_QualifiedName q = id{ foo }id;
>           AST_Class c = cls{ interface empty{};
>              $mod(m) class $name(q) implements $tlst(t) { $mth(f) } }cls;
>           System.out.print(c);
>        }
>     }

>     // prints:

>     interface empty{}; public final class foo implements empty { int i; int inc( int i ) { return ( i+1); } }

### Available Constructors and Escapes

The following table lists the syntax of each available AST constructor, its escape, the class/type of objects that a constructor returns (or that its escape requires):

#### Constructor | #### Escape | #### Class | #### AST Representation Of
exp{...}exp | $exp(...) | AST_Exp | expressions
stm{...}stm | $stm(...) | AST_Stmt | list of statements
mth{...}mth | $mth(...) | AST_FieldDecl | list of data member and method declarations
cls{...}cls | $cls(...) | AST_Class | list of class and interface declarations
case{...}case | $case(...) | AST_SwitchEntry | list of one or more switch cases
prg{...}prg |  | AST_Program | entire Java program (including package, import and class declarations)
typ{...}typ | $typ(...) | AST_TypeName | a type name
id{...}id | $id(...) | AST_QualifiedName | a qualified name (e.g., "a.b.c")
plst(...}plst | $plst(...) | AST_ParList | list of formal parameters of methods
xlst{...}xlst | $xlst(...) | AST_ArgList | list of arguments for method calls
tlst{...}tlst | $tlst(...) | AST_TypeNameList | list of type names
imp{...}imp | $imp(...) | AST_Imports | list of import declarations
mod{...}mod | $mod(...) | AST_Modifiers | list of modifiers
vlst{...}vlst | $vlst(...) | AST_VarDecl | list of variable declarations
vi{...}vi | $vi(...) | AST_VarInit | variable initialization code
ai{...}ai | $ai(...) | AST_ArrayInit | array initialization code
estm{...}estm | $estm(...) | AST_ExpStmt | list of comma-separated expressions
cat{...}cat | $cat(...) | AST_Catches | list of catch statements
| $str(...) | String | the argument of $str(...) is taken literally and converted into an AST of type Literal
| $name(...) |  | escape that converts an AST_QualifiedName parameter into an unqualified name -- basically returns first name "a" in a qualified name ("a.b.c"). see below for example.

Note that very few constructors are ever used in practice - constructors for expressions, statements, field declarations, classes, and programs.

### How to convert a String or Integer to an AST?

Besides tree constructors, there are several methods that return ASTs given string or integer inputs. First, there is the MakeAST methods. Every AST type in listed in the previous section has a static MakeAST method which converts a string into the corresponding AST by invoking a parser. Some examples:

>     AST_Exp       e = AST_Exp.MakeAST("3*4 + 5");
>     AST_FieldDecl m = AST_FieldDecl.MakeAST("int foo(int x) { return x; }");
>     AST_ArgList   a = AST_ArgList.MakeAST("3, 4, foo(4)");

There are other, more primitive methods that do not invoke parsers. These methods are:

>     in class Literal:
>       static Literal Make(String s);
>       static Literal Make(int i);

>     in class AST_QualifiedName:
>       static AST_QualifiedName Make(String s);  // for name 'foo'
>       static AST_QualifiedName Make(String[] s);// for name 'foo.bar'

Some examples:

>     String            qname[] = { "alpha", "beta", "gamma" };

>     AST_QualifiedName n1 = AST_QualifiedName.Make( "alpha" );
>     AST_QualifiedName n2 = AST_QualifiedName.Make( qname );

>     AST_Exp f1 = Literal.Make( 5 );
>     AST_Exp f2 = Literal.Make( "5" );

>     System.out.print(n1);        // outputs "alpha"
>     System.out.print(n2);        // outputs "alpha.beta.gamma"

>     System.out.print(f1);        // outputs "5"
>     System.out.print(f2);        // outputs "\"5\""  (i.e., a quoted string)

### How to Convert ASTs into Strings

ASTs are converted into strings using the toString() method:

>     AST_Stmt  s = stm{ x = 4+5; }stm;

>     System.out.println( s.toString() );     // prints "x = 4+5;"
>     System.out.print( s );			// same thing

Finally, another useful method is to convert AST_QualifiedNames into strings. The method is GetName() and it removes whitespace from AST_QualifiedNames.

>     AST_QualifiedName n = id{ a. /* comment */.b.c }id;
>     S = n.GetName();                        // s = "a.b.c"

### How to Print ASTs to Files?

ASTs are reduced (e.g., reduced to text) by invoking a method that takes an object of type AstProperties as input. This object specifies the file to which the text is to be sent. The methods of AstProperties are:

Object getProperty(String key) | get specified property
Object removeProperty(String key) | remove specified property
boolean containsProperty(String key) | is property present?
void setPw( PrintWriter p ) | set print writer
static AstProperties open( Writer out ) | create an output writer
static AstProperties open( String filename ) | create an output writer, given file name
static AstProperties open( String directory, String filename ) | same as above, except specify directory also. If both parameters null, stdout is assumed
String close() | close writer
void print( String arg ) | print to output
void println( String arg ) | println to output
void print( AstNode n ) | print to output
void println( AstNode n ) | println to output

For all text to be flushed, the AstProperties object should be closed, as shown below:

>     import jak2java.*;

>     class ex {
>        public static void main( String[] args ) {
>           AstProperties props = AstProperties.open(null,null);
>           AST_Exp e = exp{ 7 + x*8 }exp;
>           e.print(props);
>           props.close();
>        }
>     }

To convert this program into an executable, type:

>     > jak2java ex.jak		// converts ex.jak to ex.java
>     > javac ex.java			// compiles ex.java
>     > java ex			// runs ex.java

### Coding Techniques for Writing MetaPrograms

There are techniques and coding strategies that you should be aware of when using code constructors and escapes. The most important is the use once and discard policy for code variables. Remember, code fragments are parse trees. When a code fragment is inserted into another parse tree (either via escapes or programmatic "adds"), our tools don't copy the parse tree, but rather integrate it within the enclosing tree. The variable that points to the inserted code fragment now points to nothing, and should be discarded. Thus, the idiom:

> >     var = code{ ... }code; 		// create fragment

> >     var2 = code{ ... $code( var ) ... }code		// insert fragment

> >     // don't use var again, discard it

is common. If you wish to use the same code fragment multiple times, create a copy of it by cloning:

> >     var = stm{ ... }stm;

> >     copy = (AST_Stmt) var.clone();		// make copy -- casting important

The following program illustrates common ways in which code fragments can be composed.

>     import jak2java.*;

>     class test1 {

>        // This program illustrates ways in which code can be composed
>        // Note that there are "quirks" you should be aware of. Once a
>        // code fragment is substituted, the original variable that points
>        // to the code fragment is essentially nullified. So the rule is
>        // use once, throw away code variables.

>        public static void main( String args[] ) {
>           AST_FieldDecl first, firstc, second, secondc, third, thirda, thirdb;
>           AST_FieldDecl copy;

>           // First way is to compose using escapes.
>           first = mth{ int a, b, c; }mth;
>           firstc = mth{ float x,y; $mth( first ) }mth;
>           System.out.println( firstc );

>           // Second way is to use the add method

>           second = mth{ boolean i, j; }mth;
>           secondc = mth{ double y, z; }mth;
>           secondc.add( second );
>           System.out.println( secondc );

>           // note: once substituted, the original value is gone
>           System.out.println( first ); /// will print nothing
>           System.out.println( second ); // will print nothing;

>           // the reason is that parse trees are manipulated and sliced
>           // apart during addition/escapes. If you want to use a code
>           // fragment multiple times, you must replicate it using clone(),
>           // like below. The casting is important...

>           third = mth{ char r, q, s; }mth;
>           copy = ( AST_FieldDecl ) third.clone(); // make a copy
>           thirda = mth{ int foo() {} $mth( copy ) }mth;

>           thirdb = mth{ int bar() {} }mth;
>           copy = ( AST_FieldDecl ) third.clone(); // make another copy
>           thirdb.add( copy );

>           System.out.println( third ); // prints char r, q, s;
>           System.out.println( thirda ); // as expected
>           System.out.println( thirdb ); // as expected
>        }
>     }

The output of this program is:

>     float x,y; int a, b, c;
>     double y, z; boolean i, j;

>     char r, q, s;
>     int foo() {} char r, q, s;
>     int bar() {} char r, q, s;

Sometimes, using the normal constructors isn't quite what you want. For example, it so happens that mth{ }mth returns null. So code like:

>     AST_FieldDecl m = mth{ }mth;
>     m.add( mth{ ... }mth );

will generate a NullPointerException run-time error. Instead, you can do the following -- create a list node and then add onto it:

>     import jak2java.*;

>     class test {
>        public static void main( String args[] ) {
>           AST_FieldDecl f = new AST_FieldDecl();
>           f.add( mth{ void foo() {} }mth;
>           System.out.println( f );
>        }
>     }

Here's another thing you should keep in mind. An object of type Statement is NOT an object of type AST_Stmt. There is due to the fact that there is an oddity in our Java grammar where Block is defined by a sequence of BlockStatements, and a Statement is a BlockStatement. (So far, so good). However, many statement declarations, such as IfStmt are defined in terms of Statements, not AST_Stmt:

> IfStatement : "if" "(" Expression ")" Statement [LOOKAHEAD(1) ElseClause ] ::IfStmt
> ;
> ElseClause
> : "else" Statement ::ElseClauseC
> ;

The problem arises in metaprogramming when you want to access the Statement tree of the IfStatement; you can't use an AST_Stmt variable, because of type mismatch. Stated another way, Statement is a SINGLE statement; AST_Stmt is a LIST of Statements. So the following code will not compile:

> IfStmt s = (something);
> AST_Stmt e = s.arg[2]; // access the "then" part of the if statement
> // this will not compile!!

To circumvent this problem, a special method is available for converting a BlockStatement into an AST_Stmt. The corrected code is shown below:

>     IfStmt s = (something);
>     AST_Stmt e = ((Statement) s.arg[2]).toAST_Stmt();  // access the "then" part of the if statement
>     // this will compile!!

AHEAD Home Page

Copyright © Software Systems Generator Research Group. All rights reserved.
Revised: September 21, 2004.