Introduction to gmIL

The primary words of gmIL are called Opcodes. Each Opcode defines a basic operation or value reference performed within the intermediate language. There are a total of 206 opcodes. Each opcode has a type and a role which combine to define the actual type of the binary emission used by the operation and the semantic role that operation performs. Most opcodes also have subcodes associated with them. These subcodes can be a simple member of a fixed enumeration, or they can be a value, or an address into the symbol storage area. The opcode and subcode identifiers are then organized into a reverse-polish language like the pseudo-code produced by the first pass of contemporary compilers. The gmIL is this language. It is needed to organize every phase of the translation process.

What is a Translator?

The techniques used to produce the target language are based on the work done in the area of recreation of source code. In particular, P.J. Brown -- "More on the Recreation of Source Code from Reverse Polish." Software Practice and Experience, Vol. 7, p545-551 (1977) -- discusses the recreation of source code from reverse polish notation. This discussion reviews that work and shows how it can be easily extended via a "surface-form description language" and via "external library descriptions" to allow not only for the surface form variation needed to accommodate different target languages, but also to give the final user of the translator the ability to manipulate the translation to his own needs.

If the references upon which this approach is based seem old, they are. The original coding of this approach was done in Fortran for a 1972 Linguistics Masters thesis "SPELL, Systematic Procedures for Equating Logic and Language." For SPELL, the term "Logic" referred to a formal notation used to express meaning and "Language" referred to English. It then quickly became FTSQR, Formula Translation Squared, A Fortran program that converted programs written in nonstandard Fortran into machine independent Fortran. Then, in the early 80's, it branched into PROMULA, Processor of Multiple Languages, and PFC, Portable Fortran Compiler. These are both implemented in C on desk top desktop computers and use C as the target language. The primary difference between PROMULA and PFC is that PROMULA can both directly execute and translate its source code; while PFC translates and then compiles the C along with a runtime library to do the execution. Both PFC and PROMULA have been actively in use since the 80's.

Description of Approach

The problem with the standard theories of compiler design is that though there is ample discussion of how to do the conversion from the source language to the intermediate language, there is little discussion of how to move from an intermediate language back to a higher level target language. For compilers, the target language is always a low-level machine code. Fortunately, there has been some work done in the area of the re-creation of source code from intermediate code. Many BASIC interpreters need to be able to execute BASIC statements efficiently; while still giving the user access to the source code. The re-creationists solve this problem by compiling the source statements into a reverse polish notation and then rewriting the source code from that internal notation.

The technique of source code recreation from reverse polish notation hinges on the observation that executing such notation via a stack-oriented pseudo-machine is identical to writing and combining the character sequences that perform those operations in some target language via a stack-oriented string manipulation machine. The above can best be understood via a simple example.

Consider the following statement which we wish to both execute via a p-machine and re-create

   A = B * C + D.

   PUSHADR       A
   PUSHADR       B
   GETVAL
   PUSHADR       C
   GETVAL
   MULT
   PUSHADR       D
   GETVAL
   ADD
   PUTVAL
   EOS

   OpCode  Meaning
   ------  -------
   PUSHADR means push the address of the variable onto the stack.
   GETVAL  means pop the address from the stack, obtain the value at that
           address, and push it onto the stack.
   MULT    means pop the top two values from the stack, multiply them
           together, and push the result onto the stack.
   ADD     means pop the top two values from the stack, add them together,
           and push the result onto the stack.
   PUTVAL  means pop the value and address from the stack and then store the
           value at the address.
   EOS     means end the current statement.

   OpCode  Meaning
   ------  -------
   PUSHADR means enter the notation for a pointer to the variable onto the
           stack.
   GETVAL  means pop the top string from the stack, convert it to the notation
           for a value at the indicated address, and push that string back
           onto the stack.
   MULT    means pop the top two strings from the  stack, concatenate them
           with the symbol '*' in the middle, and push that string back onto
           the stack.
   ADD     means pop the top two strings from the stack, concatenate them
           with the symbol '+' in the middle, and push that string back onto
           the stack.
   PUTVAL  means pop the top two strings from the stack, convert the lower
           one to a value string, concatenate the two strings with the symbol
           '=' in the middle, and push the resultant string onto the stack.
   EOS     means write the current string.

   Instruction  Execution stack  String-manipulation stack
   -----------  ---------------  -------------------------
   PUSHADR A    45               "&A"
   PUSHADR B    45, 50           "&A", "&B"
   GETVAL       45, 2.0          "&A", "B"
   PUSHADR C    45, 2.0, 55      "&A", "B", "&C"
   GETVAL       45, 2.0, 3.0     "&A", "B", "C"
   MULT         45, 6.0          "&A", "B*C"
   PUSHADR D    45, 6.0, 60      "&A", "B*C", "&D"
   GETVAL       45, 6.0, 4.0     "&A", "B*C", "D"
   ADD          45, 10.0         "&A", "B*C+D"
   PUTVAL                        "A=B*C+D"
   EOS

A serious problem faced by the re-creationists, is that the production of the output string is completely independent of the original input made by the user. Though the original and the result mean the same thing, they might look very different. Fortunately, in this application this is not a problem. The user wants semantic and not syntactic identity.

The other important point is that the string machine need not operate against the reverse polish notation as originally formed by the compiler. The string machine can operate on any well-formed representation. This fact is key for the deep-refactoring operations which manipulate the low level notation directly.

The Problem with Parentheses

A = B * (C + D)

  PUSHADR   A
  PUSHADR   B
  GETVAL
  PUSHADR   C
  GETVAL
  PUSHADR   D
  GETVAL
  ADD
  MULT
  PUTVAL
  EOS

Note that the effect of the parentheses in intermediate form was simply to reorder the operations.

Now, using the same execution and string-manipulation rules as before, the following would result.

 Instruction  Execution stack   String-manipulation stack
 -----------  ---------------   --------------------------
 PUSHADR A    45                "&A"
 PUSHADR B    45, 50            "&A", "&B"
 GETVAL       45, 2.0           "&A", "B"
 PUSHADR C    45, 2.0, 55       "&A", "B", "&C"
 GETVAL       45, 2.0, 3.0      "&A", "B", "C"
 PUSHADR D    45, 2.0, 3.0, 60  "&A", "B", "C", "&D"
 GETVAL       45, 2.0, 3.0, 4.0 "&A", "B", "C", "D"
 ADD          45, 2.0, 7.0      "&A", "B", "C+D"
 MULT         45, 14.0          "&A", "B*C+D"
 PUTVAL                         "A=B*C+D"
 EOS

The solution taken is quite simple and general. Each rule in the string manipulation machine has associated with it a precedence code. Whenever the output of an operation is written to the string-stack, the precedence code of the rule that produced the output is also written. Whenever an element is combined within a rule, if its precedence code is nonzero and lower than the code of the rule, then that element is enclosed in parentheses as it is concatenated into the new output.

Applying this extension to the example above, the precedence codes for the various operations are as follows:

 Instruction    String-manipulation stack
 -----------    -------------------------
 (0) PUSHADR   A    (0) "&A"
 (0) PUSHADR   B    (0) "&A", (0) "&B"
 (0) GETVAL         (0) "&A", (0) "B"
 (0) PUSHADR   C    (0) "&A", (0) "B", (0) "&C"
 (0) GETVAL         (0) "&A", (0) "B", (0) "C"
 (0) PUSHADR   D    (0) "&A", (0) "B", (0) "C", (0) "&D"
 (0) GETVAL         (0) "&A", (0) "B", (0) "C", (0) "D"
 (1) ADD            (0) "&A", (0) "B", (1) "C+D"
 (2) MULT           (0) "&A", (2) "B*(C+D)"
 (0) PUTVAL         (0) "A=B*(C+D)"
     EOS

The critical point in the above occurs when the output of the ADD operation, which has a precedence code of 1, is combined via the MULT operation which has a precedence of 2. Since 1 is nonzero and less than 2, the string "C+D" is enclosed in parentheses as it is entered into the output string of the MULT instruction.

The Translation Process

1. The source language must be translatable into an intermediate language all of whose operators are expressed in reverse polish notation and be they unary, binary, ternary, etc. produce either a single result or no result.
2. In the target language every n-ary operator can be expressed as an arbitrary but fixed concatenation of its operands and of other fixed character sequences.
3. It must be possible to gain access to all operations performed in the source language via the target language.

The Surface-Form Description Notation

1. A specification of the number of operands associated with the operation -- i.e., whether the operation is null, or unary, or binary, etc. -- for the particular language. Remember that all operations are reverse polish; therefore, when a given operation is encountered, its operand strings have already been placed on the string-machine stack. The operands are numbered starting with the oldest first. In other words, the operand deepest on the stack is argument 1 and the operand at the top of the stack is argument n, for an n-ary operator.
2. A specification of the precedence of the operator relative to others. As the output production proceeds, it is necessary to enclose certain operations in parentheses to achieve the proper order of evaluation. The current precedence of each operand is maintained. When two operators of lower precedence are combined via an operator of higher precedence, then they are enclosed in parentheses.
3. A pattern string which specifies an arbitrary but fixed concatenation of the operands and of other character sequences which can be described via a linear pattern string. This pattern string is, of course, the actual implementation of our translation process requirement number (2) as presented earlier. The pattern string describes not only how the operands are combined but also how the various constants, symbol table entries, and miscellaneous special-purpose conversion routines combine to form the final output.

The Example Revisited

<pattern id="PUSHADR" >
   <all narg="0" level="0" code="\v"/>
</pattern>
<pattern id="GETVAL" >
   <all narg="1" level="0" code="%1i"/>
</pattern>
<pattern id="MULT" >
   <all narg="2" level="2" code="%1d * %2d"/>
</pattern>
<pattern id="ADD" >
   <all narg="2" level="1" code="%1d + %2d"/>
</pattern>
<pattern id="PUTVAL" >
   <all narg="2" level="1" code="%1i = %2d"/>
</pattern>
<pattern id="EOS" >
   <all narg="1" level="0" code="%1d\c"/>
</pattern>

Within the pattern strings there are three types of specifications:

1. Special operation parameters which consist of a backslash followed by a letter. These parameters trigger special conversions. Thus, in the above rule for PUSHADR the \v specifies that a pointer to a variable whose symbol number is specified following the opcode is to be entered into the output string at the indicated location. The \c notation in the EOS string specifies that the current string stack is to be cleared and thus written to the output file.
    
2. Operand conversion parameters which consist of a percent sign, followed by a numeric digit, followed by a conversion code. The numeric digit specifies which operand is to be entered at this point in the string, and the conversion code specifies any special operation to be performed. In the above, the %1d which occurs in the MULT, ADD, and EOS strings says "Enter the first operand without any additional editing (other that any precedence editing which may be needed) into the output string." The %2d says the same thing for operand 2. The %1i specification in GETVAL and PUTVAL says "Enter the string in instantiated form -- i.e., change it from a pointer representation to the representation of the value pointed to."
    
3. Simple character specifications are any characters not forming one of the two specifications above. Simple characters are entered into result strings exactly as entered.

Thec Opcode Functional Grouping

The Opcode Types

The Opcode Roles