[NEXT] [PREV]    HANDBOOK / GENTLE PRIMER / Optimal Rule Selection /

A Stack Computer

Gentle
Applications
Concepts
Examples
Handbook
Support
Download

Our target computer is a stack computer with the following instructions (the instructions are given as predicates, that, when invoked, emit the instruction):


   'action' PLUS
   'action' MINUS
   'action' PUSH(Variable)
   'action' POP(Variable)
The instructions modify the stack of the computer. If the stack has the form
  • ... X Y
then PLUS replaces the top two elements by their sum Z = X+Y, i.e. the stack becomes
  • ... Z
Similarly, MINUS replaces X and Y by Z = X-Y.

If K is the value of a variable V, then PUSH(V) puts K onto the stack.

If K is the value on top of the stack, then POP(V) removes it from the stack and stores it in V.

Let us write predicates Encode and StackCode that emit instructions for statements and expressions.

If we have to generate code for assign(V, X), we have to emit code for the expression X that computes its value on top of the stack. Then, we can use the POP instruction to store it in V.


   'rule' Encode(assign(V,X)):
      StackCode(X)
      POP(V)
The predicate StackCode processes the alternatives for Expr:

   'rule' StackCode(plus(X,Y)):
      StackCode(X)
      StackCode(Y)
      PLUS
   'rule' StackCode(minus(X,Y)):
      StackCode(X)
      StackCode(Y)
      MINUS
   'rule' StackCode(var(V)):
      PUSH(V)
For the Statement

   assign("Res", plus("A", minus("B", "C")))
the generated code is

   PUSH A
   PUSH B
   PUSH C
   MINUS
   PLUS
   POP Res
which, when executed, results in the following stack configurations
  • ... (A)
    ... (A) (B)
    ... (A) (B) (C)
    ... (A) (B-C)
    ... (A+(B-C))
    ...





[NEXT] [PREV]