XIDEK
Extensible Interpreter Development Kit

Building Custom Interpreters

• Introduction
• Working Examples of Interpreter Extensions
• The Host Program Interface
• Adding New Data Types
• Adding New Operations
  • Built-in Functions
  • Adding New Statement Syntax
  • Adding New Expression Syntax
• Other Ways to Customize an Interpreter

Introduction

Many applications require additional features in the script language. These can be implemented by modifying or extending one of the interpreters in the kit. In this chapter we will discuss some of the changes a developer might wish to make and how he might handle these changes.

Script interpreters are a useful technique for bridging the gap between the computer specialist on the one hand and the problem domain specialist on the other. A well designed interpreter allows the computer specialist to provide the implementation of problem domain functionality while the actual application of the functionality to specific problems is left to a problem domain specialist. For an excellent exposition of this approach, see

Arie van Deursen and Paul Klint.
Little languages: little maintenance?
Proceedings of DSL '97 (First ACM SIGPLAN Workshop on Domain-Specific Languages)
(Paris, France, 18 Jan. 1997).
Published as University of Illinois Computer Science Report,
http://www-sal.cs.uiuc.edu/~kamin/dsl/papers/van-deursen.ps
Also available at:
http://www.cwi.nl/~arie/papers/domain.pdf

Another way of looking at this use of interpreters is as an extension of the concept of object oriented programming. From this point of view, the computer technologist can be seen as implementing classes which describe problem domain objects and operations on them. The script interpreter then allows a problem domain specialist to use these operations to specify and control the interactions among the problem domain objects, without the need for using a full-fledged programming language. The relationship between the software specialist and the problem domain specialist is then somewhat like the relationship between the computer architect who designs a cpu and the programmer.

For example, the computer architect defines various "objects", i.e., bytes, integers, floats, doubles, etc. and operations on them, i.e. machine instructions. The computer programmer, in turn, creatively combines these objects and operations to create a computer program. Just as a computer programmer uses assemblers and compilers to clarify and simplify his work, a problem domain specialist can use a set of well defined objects and an interpreter to create his own application without having to explain his specialized knowledge to a computer programmer.

The success of this approach depends strongly on making the script language congenial to and readily understandable by the problem domain specialist. This is more easily achieved with the support of a tool like XIDEK specifically designed to make modifications to the language as easy as possible.

Extensions to interpreters in the kit can be seen as falling into two categories: those which do and those which do not require modifications of or additions to the language syntax. In those cases where there are no modifications to the language, most developers will find themselves in familiar territory. For instance, modifying the host program interface, modifying error handling, adding new data types: all these are conventional programming exercises which require no prior experience with compiler construction technology.

Working Examples of Interpreter Extensions

To illustrate the techniques involved in adding additional features to an interpreter, a number of examples have been provided which implement particular familiar features. These examples have been implemented for both the CLL and the PLL language, and for all four interpreter architectures.

Except for the complex arithmetic example, the examples implement useful interpreter features that have not been implemented in the baseline interpreters. Generally these are features where no consensus has yet evolved on how they should be implemented.

The examples are as follows:

• Complex Arithmetic
  Link to Reference Documentation
  This example adds support for complex arithmetic to the baseline interpreters. No syntax modifications are required, but on the other hand, changes to the Value class are extensive.

• Arrays and Subscripts
  Link to Reference Documentation
  This example adds support for arrays and subscripts to the baseline interpreters. It adds arrayType and charPointerType objects to the Value class. It illustrates the use of built-in functions, statement syntax and expression syntax to support the new data types.

• Structures and Objects
  Link to Reference Documentation
  This example adds support for structures and objects to the baseline interpreters. It adds structureType and instanceType objects to the Value class. It illustrates the use of statement syntax and expression syntax to support the new data types.

• Local Function Definitions
  Link to Reference Documentation
  This example adds support for local function definitions to the baseline interpreters. It adds functionType objects to the Value class. It illustrates the use of statement syntax to support the new data type. Note that no new expression syntax is required, since function calls are already implemented in the baseline syntax.

• Combining Arrays, Structures and Functions
  This example simply combines the above three extensions into a single example containing array, structure and function functionality. Since these extensions are effectively independent, the modifications in this example are simply the sum of the modifications for the array, structure and function extensions.

  Note that the name list token is defined identically in both the structure example and the function example. Only one instance of name list is defined in the combination example. If it were desired to have separate name list tokens, they would have to be given different names, e.g., struct name list and function name list.

  For reference documentation, see the reference documentation for the component extensions.

The Host Program Interface

The host program interface provided by XIDEK is meant to be illustrative rather than definitive. This is particularly true for the dci, astci, and astxi architectures. An application that uses the dci or astci architecture might save the bytecode associated with a script and recompile only when a new or modified script is encountered. Similarly, an application that uses the astxi architecture might save the abstract syntax tree associated with a script and regenerate it only for new or modified scripts.

Error handling in XIDEK, similarly, is meant to be illustrative. The challenge in handling errors is to deliver all relevant information about the error to the appropriate party. From this point of view, error handling is essentially part of the interface to the host program and should be modified to suit your requirements.

Adding New Data Types

1. Add new type specifications to the Value class.
2. Add constructors as necessary.
3. Add new methods as necessary to wrap the methods for the new type.
4. Add cases to the relevant switch statements in the Value class methods. If a particular Value class method is not relevant to a new data type, nothing special need be done, since all such methods throw an exception by default for data types that are not explicitly handled.

In some cases, particularly where the target problem domain is mathematically oriented, user level operations can be handled by overloading conventional arithmetic operators. In these cases, adding new data types is all that is necessary to make a useful extension of one of the baseline interpreters. This special case is illustrated by the complex arithmetic example.

Adding New Operations

Depending on the nature of an operation on a new data type, there are several ways it might be implemented: as a built-in function, as a separate statement, or as an arithmetic operator. The choice of implementation depends on various circumstances, consistency with the rest of the language, and the requirements of the users of the language, among others.

Built-in Functions

Built-in functions are perhaps the implementation of choice when there is a single argument and the functional notation is not misleading.

Note that in the arrays and subscripts example, for consistency with the other examples, a new statement was defined to declare an array. It would have been easier, in fact, to simply create an array() function and add it to the function table. Then, instead of writing

  array x(size);

  x = array(size);

Adding New Statement Syntax

The baseline interpreters contain two instances of functionality provided by special statement syntax: the dump statement and the print statement. Note that these statements actually provide for comma delimited lists of arguments, a capability that is not available when using built-in functions.

The arrays and subscripts example uses a simple declaration statement to declare arrays. It should be noted that with very little effort, this statement syntax could be extended to allow any number of arrays to be defined in a single statement. Consider the following syntax for example:

  simple statement
   -> array statement, ';'

  array statement
   -> "array", name, '[', expression, ']'
   -> array statement, ',', name, '[', expression, ']', ';'

  array x[17], y[17], z[17];

The structures and objects example uses a noticeably more complicated declaration statement, based on the C struct declaration. Note that the statement has three key fields, the name of the struct, the body of the struct, and a list of instance names. Any one of these three fields may be omitted. The syntax is written by enumerating the allowable combinations.

The local function example uses two new statements: the local statement and the function definition statement. The local statement is not absolutely necessary, but it provides a means for assuring that global variables are not inadvertently modified by a function call.

The function definition statement is the only syntax modification in the set of examples where the changes to the PLL version is not identical to the CLL version. The difference is the treatment of delimiters for the function body: begin/end in the one case, braces in the other.

When operations on problem statement objects involve several parameters, it is often desirable to use statements that contain "unnecessary" keywords in order to improve readability. For example:

statement
 -> "set", name, "to", expression, "volts;"

  set controlVoltage to baselineLevel + 3 volts;

Adding New Expression Syntax

There are two primary alternatives to extending expression syntax: using built-in functions and overloading existing operators. The choice should generally be determined by conventional usage in the problem domain. For instance, in complex arithmetic, the extraction of the real and imaginary part is conventionally written using functional notation. The complex conjugate, however, is commonly denoted by a bar over a variable name or expression. Because of the limitations of editing programs, this is not possible to represent conveniently in a script. The choice then is one between a built-in function, conj(), and an overloaded operator. An argument could be made that in the complex arithmetic example one should overload the '~' operator, which would actually be easier to implement than the conj() function. On the other hand, the meaning of conj() will be readily apparent to anybody familiar with complex variables who reads a script. The same cannot be said for the use of '~'.

The baseline interpreters contain one example of extending expression syntax: the Fortran style exponentiation operator. This provides the use of familiar notation for those who would otherwise find it lacking.

Both the arrays and subscripts example and the structures and objects example use simple expression syntax extensions, implementing subscript notation in the one case, member field notation in the other. In both cases, the notation is familiar from C and Pascal.

Keywords can be used in extending expression syntax as well as in statement syntax. Instead of using built-in functions to implement methods with multiple parameters, it can sometimes be advantageous to use "syntactic sugar", as it is sometimes called, to identify particular arguments. For instance, to specify a circle, one might use the following syntax:

primary
 -> "circle", "of"?, "radius:", expression, "at", '(',
     assignment expression, ',', assignment expression, ')'

This syntax would allow a script to contain statements of the form:

  c = circle of radius z at (x+5, y-7);

  c = circle(z, x+5, y-7);

When making extensions of this sort, make sure that the rule is not right recursive. There must be some token, usually nonterminal, that delimits the expression on the right. Otherwise, the rule will generate conflicts in the grammar.

A more complex example of what can be done by extending expression syntax is illustrated in the file matrix.syn. This file adds rules to the expression syntax of the CLL language to allow more congenial representation of matrix and vector arithmetic. These extensions include:

• The use of a postfixed '~' character to represent the inverse of a matrix. x~ is far less cumbersome than x**-1.

• The use of a postfixed single quote character to represent the transpose of a matrix. Thus x' represents the transpose of x, in accordance with ordinary mathematical notation. Contrast the clarity of x'*y and x*y' with transpose(x)*y and x*transpose(y).

• The use of vertical bars to represent the norm of a vector or an absolute value. Thus |x| is more in line with traditional mathematical usage than abs(x).

• The use of square brackets to denote n-tuples. This allows specifying the components of a vector: V = [x, y, z]; The notation has been set up so that n-tuples can nest. Thus the elements of a matrix could be specified by writing:

  M = [[x, y, z],
       [u, v, w],
       [a, b, c]];
  

  Also, if X, Y, and Z are vectors, one could write:

  M = [X, Y, Z];
  

The changes to the syntax required to implement these extensions are as follows:

• Adding the postfix operators requires that the definition of factor be changed from:

  factor
   -> primary             // next higher precedence level
   -> primary, "**", unary expression
  

  to:

  factor
   -> postfix expression  // next higher precedence level
   -> postfix expression, "**", unary expression
  
  postfix expression
   -> primary
   -> postfix expression, '~'                // inverse
   -> postfix expression, '\''               // transpose
  

  Note that it is necessary to interpolate a new level in the operator precedence hierarchy. If one attempts to simply add the following rules:

  primary
   -> primary, '~'                // inverse
   -> primary, '\''               // transpose
  

  the grammar will be ambiguous because primary already has right recursion due to the cast operators. Thus an expression like (double) x' could be parsed either as ((double) x)' or as (double)(x'). Of course, this expression is meaningless, but that is, of course, irrelevant to the syntactic analysis.

• To implement the absolute value and tuple features, two new rules for primary are required:

  primary
   -> '[', arg list, ']'              // tuple
   -> '|', additive expression, '|'   // absolute value
  

  Since these rules are neither left nor right recursive, there is no problem with ambiguity and no new level in the precedence hierarchy needs to be added.

  Note the use of additive expression in the rule for absolute value. This allows the user to write |x+y| or |x*y|, but requires parentheses if a more loosely binding operator is to be used within the vertical lines. If the rule had been written:

  primary
   -> '|', expression, '|'   // absolute value
  

  the grammar would yield numerous conflicts, since given the complete expression syntax, it is possible to require the absolute value of an expression such as x|y. In this case, the absolute value would be written |x|y|. Although such a construct is not, properly speaking, ambiguous, it can't be parsed with an LALR-1 grammar. At the same time, no user is going to find it any easier to understand than the parser does.

Other Ways to Customize an Interpreter

To an extent, software specialists have become so accustomed to the peculiarities of conventional programming languages that they often do not recognize how inscrutable their programs can be.

There are two basic classes of end users: those who are comfortable with mathematical notation and those who find it confusing and hard to understand. The latter group, of course, are a much greater challenge to the language designer than the former. On the other hand, the mathematically sophisticated user may well appreciate the implementation of notation commonly used in his field, as in the matrix arithmetic syntax described above.

If the end users of an interpreter are not mathematically inclined, they should be spared any notation that cannot be effectively explained within the domain of their expertise.

Much of the syntax of C/C++ certainly falls within this category for people who are not professional programmers. As can be seen from the description of the Pascal-like language used in this kit, PLL, significant simplifications can be made without sacrificing functionality. Some operations simply become somewhat more longwinded and tedious, but certainly less obscure. More importantly, it will be noticed that, with the exception of the for statement, the support code in PLL is no different from that in CLL.

As an example of the visual difference between the two syntaxes, a script to make a table of sines and cosines would look like this in CLL:

  for (i = 0; i <= 90; i++) {
    angle = pi*i/360;
    print angle, "deg: ", sin(angle), "  ", cos(angle), "\n";
  }

  for i := 0 to 90 do begin
    angle := pi*i/360;
    print angle, "deg: ", sin(angle), "  ", cos(angle), "\n";
end

Other syntactic changes can be made with essentially no effort. In PLL, the rule for the assignment statement could be changed from:

  assignment statement
  -> lvalue, ":=", expression

  assignment statement
  -> "set", lvalue, "to", expression

Similarly, the C assignment operators, such as "+=", "-=", "*=", or "\=", can be represented by productions of the form:

  simple statement
  -> "add", expression, "to", lvalue
  -> "subtract", expression, "from", lvalue
  -> "multiply", lvalue, "by", expression
  -> "divide", lvalue, "by", expression

Another easy modification has to do with function calls. Consider the following function definition:

  function presentValue(interestRate, amount, elapsedTime) {
    ...
  }

  x = presentValue(7.85, 2734.23, 5);

It is quite easy to add syntax to a language to provide self-documenting function calls. Here is how this function call would look with a very simple syntax change:

  given
    amount = 2734.23;
    elapsedTime = 5;
    interestRate = 7.85;
  calculate x = presentValue;

Of course, it goes without saying that when implementing such a notation, the developer would include code to acheck the argument names and assure a one-to-one matchup between the arguments provided and the definition of the function.

Here is the syntax for the above statement:

  given statement
   -> "given", given parameters,
      "calculate", lvalue, '=', name, ';'

  given parameters
   ->
   -> given parameters, name, '=', expression, ';'

Although with respect to readability the above syntax is a clear improvement over the conventional function call, it is possible to improve it further. The problem, from the point of view of the problem domain specialist, is that the arguments are still simply numbers. In the real world, numbers are usually meaningless unless the corresponding units of measurement are also specified. The above example would be a good deal more reliable if the function call were written thus:

  given
    amount = 2734.23 (USD);
    elapsedTime = 5 (yrs);
    interestRate = 7.85 (percent/yr);
  calculate x = presentValue;

Adding support for units, then, is another modification that can provide significant utility and reliability at a rather low cost.

The file units.syn shows how to add support for units to the syntax. It is identical to cll.syn except for the addition of syntax sufficient to implement units. The changes are as follows:

1. Add a token to distinguish numeric constants from constants in general:

     numeric constant
      -> integer
      -> real
   

2. Define unit expression:

     unit expression
      -> name
      -> unit expression, '*', name
      -> unit expression, '/', name
   

3. Add a new production for primary:

     primary
      -> numeric constant, '(', unit expression, ')'
   

4. Modify print statement to allow an optional unit specification:

     print statement
      -> "print", print expression
      -> print statement, ',', print expression
   
     print expression
      -> assignment expression
      -> assignment expression,
         "units:", '(', unit expression, ')'
   

• Units may only be used with constants. The units associated with the values of variables must be computed as the value of the variable is computed.

• The parentheses around unit expression protect against ambiguity of the star and slash operators. A star or slash within the parentheses is part of the unit expression. A star or slash outside the parentheses is part of the overall expression of which the unit expression is only part.

• The "units" keyword in print expression serves to specify that these are the units in which the specified expression is to be printed. Note that the specified expression might itself have units:

    print 5280 (ft) units: (m);
  

  This statement might be used to print the length of a mile in meters.

The second step is to define a QuantityWithUnits class that would contain a real value and either a unit object or a reference to a unit object. The Value class would then be extended to wrap an instance of QuantityWithUnits, and the appropriate arithmetic operators would be implemented. Note that addition and subtraction can only occur if their operands have equivalent dimensions. The units of products and quotients can be generated from the units of the operands.

With this foundation, the reduction procedures neede to handle the units can readily be written for any of the interpreter architectures.