← •   HOME  • UP  •   →
Top/Interpreter/Kinds  

5.1. Kinds of Interpreters

There are two major kinds of interpreters.


Interpreters based on abstract machine language

One kind, exemplified by implementations of Java, relies on a compiler to translate a source program to an abstract machine language. The interpreter performs the steps of the compiled program one by one.

The instructions are coded in binary, typically with one byte telling what kind of instruction is represented and zero or more additional bytes providing additional information for the instruction. But it is easiest to think of the instructions in symbolic form.

It tends to be easiest for abstract machine languages to use a stack to hold temporary results. Statement 

  K = J*K + 1
could look as follows in an abstract machine language. 

  FETCH J     // Push(J)
  FETCH K     // Push(K)
  MULT        // Push(pop() * pop()).
  CONST 1     // Push(1)
  ADD         // Push(pop() + pop()).
  STORE K     // K = pop().

Conditionals and loops are handled by jump instructions and labels. For example, 

  N = 0;
  while(N < 5) {
   print(N);
   N = N + 1;
  }
would look something like this: 

  CONST 0
  STORE N
  LABEL 1
  FETCH N
  CONST 5
  COMPARE   // Pop 5 and N and push indicator
            // of the relationship between
            // N and 5.
  JUMPGE 2  // Pops indicator and jumps to
            // label 2 if indicator is ≥.
  FETCH N
  PRINT
  FETCH N
  CONST 1
  ADD
  STORE N
  JUMP  1

Interpreters based on trees

A second major kind of interpreter, exemplified by some implementations of Lisp, uses a compiler to convert a program into a collection of trees.

Each tree represents an expression that has a value, and the interpreter finds that value by performing simplifications on the tree.

For example, expression K * J + 1 would be represented by a tree something like this: 

          +
         / \
        *   1
       / \
      K   J
The interpreter follows a set of rules for performing simplifications. For example, to simplify a tree of the form 
          +
         / \
        A   B
where A and B are subtrees, the interpreter would:

  1. Simplify tree A, yielding tree A';

  2. Simplify tree B, yielding tree B';

  3. Check that A' and B' are numbers. If so, add the two and yield their sum (as a tree).

When drawing trees, it is convenient to write K for a node holding identifier K and 1 for a node holding number 1. In reality, each node has a tag telling what kind of node it is and some additional information providing specifics. So, in more detail, a tree representing expression K * J + 1 might be as follows. 
           OP(PLUS)
          /        \
      OP(TIMES)   NUM(1)
     /         \
   ID("K")   ID("J")

 

← •   HOME  • UP  •   →
Top/Interpreter/Kinds