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.

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

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); } }

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):

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

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)

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"

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:

 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

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.