3
: Building a Tree-Based Interpreter

The first step to comparing the efficiency of a tree-based interpreter to that of the traditional Java instruction-based interpreter is to create the tree-based interpreter. This chapter explores the design choices taken in the building of the Picojava Tree Interpreter (pJTI), and attempts to provide a description of its operation and rationale for its chosen implementation.

The design and implementation choices made here reflect the weight placed on elegance and simplicity over efficiency and complexity. The reason for this is to achieve the following ends:

• The interpreter should be extensible in the sense that it can be expanded to implement a broader language definition.
• The interpreter should be flexible enough to allow for it to be easily mutated into an instruction-based interpreter, so that the resulting instruction interpreter may is readily comparable to the tree interpreter.

3.1 Design Requirements

Just as the Java VM does not know the details the Java source language, a tree-based interpreter also need have no knowledge of the syntax of the source language. However, the instructions given to a tree-based interpreter are structurally equivalent to the source language tree, while the instructions used by the Java VM are a linearized version of their Java source.

Therefore, the first requirement of a tree-based interpreter is a program tree. The abstract grammar of the Picojava source language, discussed in Chapter 2 and included in its entirety in Appendix A, gives the structure of this tree. Each component, from the root CompilationUnit node down to the terminals of Identifier, Algebraic_SignedInteger5 and Algebraic_Boolean, must therefore be representable in any tree-based interpreter implementation we select.

The program tree itself merely encompasses the static state of the program. Alongside the program tree we also need some mechanism for keeping track of the dynamic state of a program. Typically such information is either embedded in processor registers (particularly the program counter), on various stacks and as heap blocks. Considering this information at a higher level, we can see that the purpose of many of these implementation devices is to provide a way of linking the identifiers within a program with the structures they reference. This function can be consilidated into one large structure.

At compile-time, such a structure is referred to as a symbol table. At run-time, it is typical for the information of the symbol table to be reduced into a more efficient form, normally by embedding its meaning within the compiled code. For example, a reference to a variable identifier is reduced to a pointer to the location where the value of the variable is stored.

In an interpreter, the distinction between compile-time and run-time is lost. Effectively, it is always run-time within an interpreter, for otherwise it is, by definition, a compiler. Therefore, for an interpreter which deals with program trees which contain identifiers, as a Picojava tree interpreter would, it is natural that this system would also have a symbol table. Of course, we note that it is possible to eliminate the need for a symbol table in a tree interpreter, but it greatly simplifies the implementation and analysis tasks to use one.

One final ingredient required in an interpreter is information about where in the program up to which execution has currently progressed. Typically this is achieved through a stack of method invocation frames, an operand stack and a program counter of some sort. We will refer to such structures collectively as interpreter state.

Together, a symbol table, some method of recording interpreter state, and a program tree are all the ingredients required to implement a fully functional tree interpreter.

3.1.1 Symbol Table Requirements

At its simplest, a symbol table is a dictionary of entries of the form (identifier, entity). New entries can be made by specifying both identifier and entity, and the existing entity corresponding to a supplied identifier can be looked up.

For a compiler, a symbol table is a means of translating program identifiers to the entity they identify. Typically, for a compiler-writer, this means that the symbol table has to provide for tasks like mapping variable identifiers to the addresses used for their run-time storage.

There are two distinct classes of meaning which can be ascribed to an identifier at each point in a source program. Either it is defining a new meaning for an identifier in the current scope (a defining instance), or it is referring to the existing meaning of the identifier (a referring instance), according to the scoping rules of the Picojava language.

For example, consider the Java clause:

class MyClass
{
	...
}

Here the instance of the identifier MyClass is a defining instance, because the compiler will now understand that the identifier MyClass refers to the class entity specified in this clause. Therefore the action of the compiler will be to insert an entry in the symbol table linking this identifier to some description of the new class.

An identifier may have more than one defining instance, according to the scope rules of the language. In Java. the scope of a class definition is confined to the package which contains it, and other packages which import it. In Picojava, class identifiers must be unique within the entire program.

Now consider the clause:

MyClass myObject;

This is a referring instance of the MyClass identifier. Upon encountering a referring instance of an identifier in the program source, the identifier can be looked up in the symbol table to determine if the reference is valid and what semantics it gives to the surrounding code.

For most languages, when compilation is complete, the symbol table is typically discarded. However, in Java, identifiers for classes, public instance variables and methods are kept within class files so that they can be used independently of their source code to build other classes. Identifiers for protected instance variables and local variables are sometimes kept as well, when optional debugging attributes are included in the compiled class file. However, such information is not used in the execution of the compiled program, only to perform debugging.

Taking this to its extreme, a tree-based interpreter must retain the symbol table from compilation (or some optimized form of it) in order to resolve run-time references. On close inspection, one finds the Java VM also uses a symbol table, albeit almost too complicated and optimized to recognise. For example, in the Java VM, variable identifiers become pointers, encoded within the parameters of VM instructions. There is no reason why a pure tree interpreter could not perform similar optimizations. We choose not to in this interpreter for the sake of simplicity.

3.1.2 Interpreter State Requirements

While traversing the program tree, the interpreter needs to have some way of recognising which item in a computation it is currently executing and what results have been obtained in surrounding computations in order to compute subsequent steps.

The Java VM keeps a set of method invocation frames in order to keep track of the stack of methods which are currently executing, with the most recently invoked method being on top of the stack. Likewise, any tree interpreter will need to keep track of these method invocations, and aditionally it will need to keep track of block and statement invocations.

In the Java VM, there is no such thing as a statement, and each method invocation frame has associated with it a program counter which indicates the current instruction executing in that method and an operand stack which keeps track of computations within each method.

A tree based interpreter needs only to know the stack of method, block and statement invocations in order to determine state. The method and statement invocation frames carry some of the information that would be provided by operand stacks in the Java VM, while the block invocation frames must carry a program counter which indexes the currently executing statement within a Block.

3.1.3 Program Tree Requirements

Essentially, the program tree is a bare bones representation of the abstract grammar defining the language to be tree interpreted. In the Java VM, at the level of a method, the tree becomes a linearized structure where instructions are bytecoded. This is not the case in a tree interpreter, where the tree continues down to the level of Blocks and Statements.

The program tree is a structure which at its root has a single CompilationUnit node. Each node is in turn composed of further nodes, as given by the rules Picojava source language grammar of Appendix A. Obviously a tree interpreter needs some way of representing such program trees.

3.2 Design Choices

The class-based design paradigm has been chosen for the design of the interpreter to provide for its elegance and extensibility. The language being interpreted is itself class-based, so it provides for an aesthetically pleasing duality for the interpreter to also be class-based. Practically, many of the constructs required by such a language will be readily supportable under a like paradigm.

3.2.1 Symbol Table Design

The symbol table will be a class, one instance associated with each program tree. It will not be allowable to have multiple symbol tables for a single program tree. This would allow for multiple instantiation of the same program, but is not required for the type of benchmarking analysis to which the tree interpreter will be subjected. It is sufficient to regenerate new program trees and associated symbol tables as required.

The symbol table will act as a dictionary matching qualified identifiers with variables (of primitive types or class instances), classes and methods. Each entry in this dictionary will provide access to the current entity (data or code structure) associated with an identifier, if one currently exists.

In order to provide access to the object this, the symbol table must be aware of the interpreter state in terms of the current stack of method invocations.

The following class of entities used by the symbol table doesn't form part of the program tree:

• The class AlgebraicOrStructured is used to represent a data entity. Of its subclasses, Structured_Object stores values of reference type, while the subclasses of Algebraic store values of primitive type.

3.2.2 Interpreter State Design

Each statement in the program tree will be represented by an instance of the appropriate subclass of Statement. The variables associated with the method named run in each of these classes will provide for keeping track of partial results during computations. The invocation of further run methods for statements and blocks within executing statements will thereby lead to implicit stack of statement and block invocation frames.

Each block in the program tree will be represented by an instance of a Block class. The only explicit information a block needs about interpreter state is a program counter indicating which statement it is currently executing.

For the sake of simplicity, we will augment the symbol table class with some of the non-implicit interpreter state elements:

• The method invocation stack will be known, updatable and readable through the symbol table class.
• The current return value for each currently invoked method will be known, updatable and readable through the symbol table class.

3.2.3 Program Tree Design

There is a one-to-one mapping between productions in the source language grammar (Appendix A) and the classes which will be used to construct the program tree in the design of the pJTI. The following classes will be used to construct the program tree:

• The class Identifier will be instantiated once for each unique identifier used within a program. Identifiers will be associated with a symbol table, and will contain a String representation that can be used in concrete listings. There is a special Identifier referring to the object containing the currently executing method, and its String representation is this.
• The class QualifiedIdentifier will be instantiated wherever appropriate according to the grammar in Appendix A. A QualifiedIdentifier is composed of a list of Identifiers, only the first of which may be the special identifier this.
• The subclasses of Algebraic, when instantiated, will store values of primitive type. These may be embedded as constants within programs.
• The subclasses of Statement will represent statements in the program tree. Each Statement will be constructed, executed via its run method, and be forced to output a concrete form of itself using its list method. Execution and output of a concrete form will both recursively call the appropriate methods of any substatements which compose the statement.
• The subclasses of Declaration will represent variable declarations in the program tree. They will have a list method which is used in order to create a listing of blocks which contain them. There will be a Declaration subclass for each class of types in Picojava.
• The class Block will be used to build methods and as a component within some forms of Statement. Like Statements, a Block will have a run method which executes it (creating all the declared variables and executing statements in order) and a list method that outputs a concrete representation, including all Declarations and Statements.
• The class Parameter will represent formal parameter specifications as used in methods. As for Declarations, there will be a list method, and there will be a Parameter subclass for each class of types in Picojava.
• The class Method will be instantiated for each method and constructor appearing in the program tree. The list method will produce a concrete representation for the method in line with Java syntax, including the Parameters and the Block. The run method will create the variables for the formal parameters, assign the actual parameters as evaluated from those in the method call, and then execute the block.
• The class ClassBased_Class will define classes in the Picojava program tree. A class is composed of Declarations and Methods, and the class may be listed using the list method.
• The class CompilationUnit will collect together the ClassBased_Classes needed to form a complete program tree. The CompilaionUnit will have a run method which runs the main method of the main class, and a list method which will produce a listing of all the component classes in turn.

3.3 Implementation Overview

The Java language was chosen to implement the interpreter, because it directly supports much of the functionality and behaviour required by the Picojava language. This reduces the amount of implementation effort required substantially. It is also convenient for a programmer to use a similar language to write an interpreter as is being interpreted, as she need only consider one set of syntax rules.

The downside of using the Java language is that the resulting code will be less efficient than that written to run real Java VMs. This is obviously the case if a Java VM is used to run the tree interpreter, but could foreseeably also be the case in a physical machine compilation of the program. However, if one was to use her own comparable interpreter for emulating the behaviour of a Java VM, necessarily also written in Java, then the extra overhead need not be of concern, as both interpreters will be subject to it.

3.3.1 Symbol Table Implementation

An instance of the SymbolTable class will be the entity containing interpreter state passed between the run and list methods of the components of the program tree (§3.2.3). It will also be used as a repository for identifiers as a program tree is created.

To fulfil the requirements as a repository for identifiers, it is necessary to have methods for:

• Symbol creation
• Symbol look-up

To store interpreter execution state, it is necessary to have methods for:

• Maintaining a stack of the objects containing the currently invoked methods, so that we implement the this identifier.
• Maintaining stacks for each variable identifier used in the program tree, so that we may determine what meaning may be ascribed to that identifier in the current scope.
• Providing a storage space for communicating the return value from the most recently invoked method.

To store interpreter listing state, it is necessary to have methods for:

• Manipulating the indentation of a listing.
• Starting a new line of a listing with the correct indentation.
• Keeping track of whether we have started a new line or not.

To make accessing components of the symbol table more convenient during execution, it is helpful to define the following:

• A method for converting an Identifier to its concrete name.
• A method for converting a QualifiedIdentifier to its concrete representation.
• A method for discovering the parent object of an entity referred to by a QualifiedIdentifier.
• A method for obtaining the Method identified by a QualifiedIdentifier.

3.3.2 Interpreter State Implementation

The implementation of interpreter state is shared between the SymbolTable class and the Java language itself. Some interpreter state is implicit in the nested method invocations and associated frames of variables within the Java environment, while the remainder is explicitly given, either in the variables used by executing methods, or within explicit repositories provided by the SymbolTable.

3.3.3 Program Tree Implementation

All but the terminal components of the program tree have a list method. This list method takes one parameter, the SymbolTable which is associated with that program tree. The SymbolTable contains all the information required to produce a concrete listing for a program tree: all that is necessary is to call the list method for the root CompilationUnit object of that tree with the appropriate SymbolTable object as parameter.

Some components of the program tree are executable, and therefore also have a run method. Again, the run method only takes one parameter, the SymbolTable. The SymbolTable is passed from method to method as the program tree is traversed, and is dynamically updated with program state information, particularly with values of variables.

A run method may have a return type, where one is appropriate. The run method of CompilationUnit returns the Structured_Object (prototyped on the main class) that was instantiated in executing the program. The run methods of Method and Statement_Action return AlgebraicOrStructured objects corresponding to the Picojava values they are defined to give as results (see Chapter 2).

The executable components of a program tree (i.e. those with a run method) are:

• CompilationUnit: the main class is instantiated, the first constructor is called, and the main method is executed.
• Method: the actual parameters are evaluated, they are assigned to the newly created formal parameter variables, and the block is executed. The result value assigned within the block is returned as required.
• Block: the declared local variables are created and assigned default values before the statements are executed in turn.
• Statement_Iteration: so long as the conditional statement has condition true, it is executed repeatedly.
• Statement_Conditional: the condition expression statement is evaluated, and if it is true, the block is executed.
• Statement_Action_Evaluate_Constant: the associated data value is returned directly to the enclosing statement. If the statement is enclosed by a block, then the value will be discarded by the block.
• Statement_Action_Evaluate_UnaryOp: the expression statement is evaluated, and the unary operation defined by the subclass is performed upon the return value. The value is returned to the enclosing statement as required.
• Statement_Action_Evaluate_BinaryOp: the two expressions are evaluated one after the other (the right-hand one only if required, see §2.17.3), and the binary operation defined by the subclass is performed to generate a return value. The value is returned to the enclosing statement as required.
• Statement_Action_Evaluate_Reference: the referenced variable is looked up in the symbol table and its value is returned as required.
• Statement_Action_Assign: the reference is used to identify the variable to assign, and the expression is then evaluated to determine how that variable should be changed. The value returned (if required) is the value of the expression.
• Statement_Action_Evaluate_Method: the actual parameters are passed to the method to be called and it is then executed. The result value of the method is returned.
• Statement_Action_Create_Object: the class specified is instantiated and the matching constructor method is called with the specified actual parameters. The value returned is the newly created object.

3.4 Implementation Details

3.4.1 Implementation Of Identifiers

Identifiers are implemented by the classes Identifier and QualifiedIdentifier. QualifiedIdentifiers are used in referring instances to variables and methods within the program tree. Identifiers are used in defining instances and in referring instances to classes (which have no hierarchial name structure in Picojava).

The class Identifer has three constructors:

• Identifier(): used to create the special this identifier which refers to the current object. Current object is a component of interpreter state recognised by the SymbolTable.
• Identifier(int): used by a SymbolTable to create a new identfier with a code decided upon by the SymbolTable. This code uniquely identifies the identifier, so that if two Identifier objects were to exist with the same code they would be considered to be the same identifier. The identifier is given a name derived from this code, and this name is used in concrete listings where the identifier appears. e.g. an Identifier object with code 13 would be called "Identifier13".
• Identifier(int, String): is the same as Identifier(int) except that the name used is as given by the String parameter.

The class has four destructors:

• getIdentifier(): returns the code associated with the identifier.
• getName(): returns the name used in concrete representations of this identifier.
• isThis(): returns true if the identifier is the special this identifier.
• hashCode(): returns the code associated with the identifier. This is used as the hashing table for the HashTable implementation of the Dictionary chosen to implement SymbolTable.

There is also a method to perform an equivalence test, equals(Identifier), which returns true if two identifiers have the same code, false otherwise.

The class QualifiedIdentifer has two constructors:

• QualifiedIdentifier(Identifier): used to create a qualified identifier for an entity with the given identifier.
• qualify(Identifier): used to modify an existing qualified identifier by specifying a further qualification to be applied to it. e.g. if a Qualifieddentifier has one component, referring to some field with a class, then qualify(Identifier) might be used to specify the Identifier of the object in which the field appears

The class has three destructors:

• getIdentifier(): returns the final Identifier object composing the Qualified Identifier. i.e. the one specified in the first constructor.
• getNumberQualifications(): returns the number of times this Qualified Identifier is qualified, excluding the identifier of the final entity specified in the first constructor.
• getQualification(int): returns the indexed qualification of this Qualified Identifier. Indices are zero-based.

3.4.2 Implementation Of Types And Values

AlgebraicOrStructured is the parent class of the classes Algebraic and Structured. All values in Picojava are instances of these classes.

s Table 3.1 Summary Of Methods In AlgebraicOrStructured Subclasses

In addition, the subclasses of Algebraic have an additional destructor, toString(), which returns a String representing the value embedded within an object.

The action of the Structured_Object's run method is to call the default (first) constructor for the class of which the object is an instance and then to call the main method for that class.

The Structured_Object class has additional methods to allow the instance variables composing the object to be modified and read:

• setValue(Identifier, AlgebraicOrStructured): changes the value of an instance variable.
• getValue(Identifier): reads the AlgebraicOrStructured value of an instance variable.

Note that instance variables are actually independent of the dictionary in the symbol table, and it is only the objects containing the instance variables which may have entries in the symbol dictionary. An instance of java.util.HashTable is used within Structured_Object to store the dictionary of instance variable identifiers and values.

3.4.3 Implementation Of Symbol Dictionaries

There are two symbol dictionaries implemented by the SymbolTable class: one for classes and the other for variables. Each of these dictionaries is implemented by java.util.HashTable, with the key being the identifier of the class or variable and the entities being references to the classes or variables themselves. This is why the Identifier class has a hashCode method.

The class dictionary has only two methods associated with it:

• setClass(Identifier, ClassBased_Class): associates a class with an identifier.
• getClass(Identifier): returns the ClassBased_Class object associated with an identifier.

The variable dictionary is more complicated, as each entity in the variable dictionary is actually a stack of values. See the next section for an explanation.

3.4.4 Implementation Of Symbol Stacks

The variable dictionary consists of variable identifiers which are associated with stacks of values. This arises from the fact that during the course of execution of a Picojava program, a single variable identifier may have many meanings ascribed to it. Only one of these meanings (or perhaps none) is relevant at any one time, according to the scoping rules of the Picojava language. It is the case that these rules lend themselves to a stack implementation.

A simple stack implementation is not sufficient, as method call under the pJTI assigns formal parameters with new values one at a time as it evaluates the expressions forming their actual parameters. If one of these formal parameters' identifier was to appear in the expression for one of the actual parameters, it is possible that a newly assigned value would be looked up instead of the correct value at the point of method call.

For this reason, a special form of stack is used, called IcyStack. IcyStack extends java.util.Stack in the following way:

class IcyStack extends Stack
{
  boolean isFrozen=false;

  Object frozenItem=null;
  // Sets the frozen stack to reflect the current 
  // unfrozen stack. IcyStack is then said to be 
  // 'frozen' & remains frozen until thawed using 
  // thaw().
  public void freeze()  {
    if (super.isEmpty()) {

      frozenItem=null;

    } else {

      frozenItem=super.peek();
    }
    isFrozen=true;
  }

  // Destroys the frozen stack. IcyStack is then no 
  // longer said to be 'frozen'.
  public void thaw()  {
    isFrozen=false;

    frozenItem=null;
  }

  // When 'frozen', returns if the frozen stack is 
  // empty. Otherwise as for Stack.
  public boolean empty()  {
    if (isFrozen) {

      return frozenItem==null;

    } else {

      return super.empty();
    }
  }

  // When frozen, returns the top of the frozen stack.
  // Otherwise as for Stack.
  public Object peek()  {
    if (isFrozen) {
      return frozenItem;
    } else {
      return super.peek();
    }
  }

  // When frozen, thaws the stack and pops top item 
  // off the unfrozen stack. Otherwise as for Stack.
  public Object pop()  {
    if (isFrozen) thaw();

    return super.pop();
  }

  // When frozen, puts a new top item on the unfrozen 
  // stack. The top of the frozen stack is maintained.
  // i.e. As for Stack.
  // public Object push(Object item)
  // When frozen, finds location of an object in 
  // unfrozen stack. i.e. As for Stack.
  // public int search(Object item)}

class Statement_Conditional extends Statement
{
  private Statement_Action condition;

  private Block block;
  ...
  
  public AlgebraicOrStructured run
      (SymbolTable symbolTable)
  {
    if (((Algebraic_Boolean)condition.run
         (symbolTable)).getValue())
    {
      block.run(symbolTable);
    }
    return null;
  }

  ...
}

class Statement_Iteration extends Statement{
  private Statement_Conditional loop;
  ...

  public AlgebraicOrStructured run
      (SymbolTable symbolTable)
  {
    Statement_Action condition;
    Block block;

    condition=loop.getCondition();
    block=loop.getBlock();

    while (((Algebraic_Boolean)condition.run
            (symbolTable)).getValue())
    {
      block.run(symbolTable);
    }

    return null;  }

  ...
}

abstract class Statement_Action_Evaluate_Constant_
    Algebraic extends Statement_Action_Evaluate_
    Constant
{
  protected Algebraic value;
  public Statement_Action_Evaluate_Constant_
      Algebraic(Algebraic newValue)
  {
    value=newValue;
  }

  public AlgebraicOrStructured run
      (SymbolTable symbolTable)
  {
    return (AlgebraicOrStructured)value;
  }
}

class Statement_Action_Evaluate_Constant_Algebraic_
     SignedInteger5 extends Statement_Action_Evaluate_
     Constant_Algebraic
{
  public Statement_Action_Evaluate_Constant_Algebraic_
      SignedInteger5(Algebraic newValue)
  {
    super(newValue);
  }

  public void list(SymbolTable symbolTable)  {
    System.out.print("("+((Algebraic_SignedInteger5)
                          value).getValue()+")");
  }
}

  public AlgebraicOrStructured run
      (SymbolTable symbolTable)
  {
    return (AlgebraicOrStructured)new Algebraic_
       SignedInteger5(((Algebraic_SignedInteger5)
                      operand1.run(symbolTable))
                     .getValue()+   
                     ((Algebraic_SignedInteger5)
                      operand2.run(symbolTable))
                     .getValue());
  }

class Statement_Action_Reference extends
     Statement_Action
{
  private QualifiedIdentifier identifier;
  ...

  public AlgebraicOrStructured run
      (SymbolTable symbolTable)
  {
    return symbolTable.getQualifiedValue(identifier);
  }

  ...
}

class Statement_Action_Assign extends Statement_Action
{
  private Statement_Action_Reference reference;
  private Statement_Action value;
  ...

  public AlgebraicOrStructured run
      (SymbolTable symbolTable)
  {
    if (reference==null) {
      return symbolTable.setReturnValue
               (value.run(symbolTable));
    } else {
      return symbolTable.setQualifiedValue
               (reference.getIdentifier(),
                value.run(symbolTable));
    }
  }
  
  ...
}

class Statement_Action_Evaluate_Method extends
     Statement_Action_Evaluate
{
  private QualifiedIdentifier identifier;
  private Statement_Action[] actualParameter;

  // Constructor to create an action statement which 
  // calls a specified method from a specified symbol 
  // table
  public Statement_Action_Evaluate_Method
    (QualifiedIdentifier newIdentifier, Method 
     newMethod)
  {
    identifier=newIdentifier;
    actualParameter=new Statement_Action
      [newMethod.getNumberParameters()];
  }

  // Modifier to specify the actual parameter to be 
  // substituted for the nth formal parameter of the 
  // method when invoked
  public void setParameter(int index, Statement_Action
      value)
  {
    actualParameter[index]=value;
  }

  // Destructor which returns the result of invoking a
  // method
  public AlgebraicOrStructured run
      (SymbolTable symbolTable)
  {
    AlgebraicOrStructured result;
    ObjectInterface object;
    Method method;

    // Obtain reference to object and make current
    object=symbolTable.setCurrentObject
             (symbolTable.getParentObject
              (identifier));

    // Obtain reference to method
    method=(object.getParentClass()).getMethod
             (identifier.getIdentifier());

    // Set formal parameters for method
    for (int i=0; i<actualParameter.length; i++)
      method.setParameter(symbolTable,i,
                          actualParameter[i]);

    // Execute method
    result=method.run(symbolTable);

    // Pop current object
    symbolTable.popCurrentObject();

    return result;
  }

  // Destructor which writes a method call to the 
  // output stream
  public void list(SymbolTable symbolTable)  {
    // Write identifier
    System.out.print("("+symbolTable.
      getQualifiedSymbolName(identifier)+"(");

    // Write parameter list
    for (int i=0; i<actualParameter.length; i++)    {
      actualParameter[i].list(symbolTable);
      if (i<(actualParameter.length-1))
         System.out.print(",");
    }
    System.out.print("))");
  }
}

class Statement_Action_Create_Object extends
     Statement_Action_Create
{
  private Identifier prototypeClass;
  private int constructorSignature;
  private Statement_Action[] constructionParameter;

  // Constructor to create an object
  public Statement_Action_Create_Object(SymbolTable
       symbolTable, Identifier newPrototypeClass,
      int newConstructorSignature)  {
    prototypeClass=newPrototypeClass;
    constructorSignature=newConstructorSignature;
    constructionParameter=new Statement_Action
      [((symbolTable.getClass(prototypeClass))
        .getMethodAt(constructorSignature))
       .getNumberParameters()];
  }

  // Modifier to specify the actual parameter to be 
  // substituted for the nth formal parameter of the 
  // method when invoked
  public void setParameter(int index,
      Statement_Action value)
  {
    constructionParameter[index]=value;
  }

  // Destructor which returns the result of invoking a
  // method
  public AlgebraicOrStructured run
      (SymbolTable symbolTable)
  {
    ClassInterface prototype;
    ObjectInterface object;
    Method method;

    // Obtain reference to prototype class
    prototype=symbolTable.getClass(prototypeClass);

    // Create object
    object=symbolTable.setCurrentObject
             (new Structured_Object(prototype));
    // Obtain reference to method
    method=prototype.getMethodAt
             (constructorSignature);

    // Set formal parameters for method
    for (int i=0; i<constructionParameter.length; i++)
      method.setParameter(symbolTable,i,
                          constructionParameter[i]);

    // Execute method
    method.run(symbolTable);

    // Return created object
    return (AlgebraicOrStructured)
             symbolTable.popCurrentObject();
  }

  // Destructor which writes a method call to the 
  // output stream
  public void list(SymbolTable symbolTable)  {
    // Write identifier of prototype class
    System.out.print("(new "+symbolTable.getSymbolName
                               (prototypeClass)+"(");

    // Write parameter list
    for (int i=0; i<constructionParameter.length; i++)
    {
      constructionParameter[i].list(symbolTable);
      if (i<(constructionParameter.length-1)) 
        System.out.print(",");
    }
    System.out.print("))");
  }
}