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.