The S2 calculator engine

The main engine of S2 calculator is S2 simulator.  The calculator engine is the simulator supplement to read the input line and perform dynamic load of S2 executable object.  The main engine works like this loop.

main             written in HLL
  loop
    getline
    interpret

The main loop is written in HLL (C).  The "interpret" function and the rest can be written in S2 assembly language!  (as you will see).

interpret
  t = read()
  while t != end_of_line
    eval t
    t = read()

Reading a token

read()  is a special routine to scan tokens from the input line.  It is implemented as "trap x" in S2 assembly language. read() returns one value and change one global variable, VALUE.

As the input line composed of the following token:

number + - * / f0..f9 = ld end_of_line

read() return the following integers indicate the token:

1     2  3 4 5  6..15 16 17 18
number + - * / f0..f9 = ld end_of_line

in case of number, the value of number is stored in a global variable, VALUE.

The main function of interpret() is eval() written in S2 assembly language. eval() uses an evaluation stack to store the result (so that it can be readily used by next operation).  It is defined recursively (hence must be a recursive program, the eval() function calls the eval() function itself).

Evaluation

The "heart" of calculator engine is this eval function.  Here is the description how it works.  Given an input line and read() to read one token at a time.  We do recursive eval() until the end of line.  (and the main loop of the calculator will get the next input line)

eval
  read one token
  if it is a number   push its value to the evaluation stack
  if it is basic function (+ - * /)  doInfix
  if it is special function (f0..f9) doPrefix
  if it is "="  display the value on top of the evaluation stack

for infix operator, one value is already in the ev-stack, read next token eval it, which will deposit the next value in the ev-stack, then we can perform the operator.

doInfix
  read next token and eval it then execute the operator

for prefix operator, all arguments will be next tokens, read and eval all next tokens.  The number of arguments depends on the arity of the operator.  f0 has no argument. f1..f3 has one argument.  f4..f7 has two argument.  f8, f9 has variable argument.

doPrefix
  read and eval next token according to arity of the function
  then apply the function
  for f8,f9 they will also consume the token "=" so do display.
 
The eval function can be written as follows.

eval(t)
  switch t
  case 1   push VALUE          number
  case 2   evalnext doAdd      +
  case 3   evalnext doSub      infix binary op
  ...
  case 6   doF0                prefix op, no arg
  case 7   evalnext doF1       prefix op, one arg
  ...
  case 10  evaln2 doF4         prefix op, two arg
  ...
  case 14  getarg doF8 display   prefix op, variable arg
  case 15  getarg doF9 display   ...
  case 16  display
  case 18  break               end of line

evalnext      get next token and eval() it
  t = read()
  eval t

evaln2        get next two tokens and eval() them
  evalnext
  evalnext

getarg        evaluate variable argument until found =
  t = read()
  while t != 7        =
    eval t

Example

The following example shows how the eval work.  Let the input line be " 22 + 33 - 1 = ".  The picture of the right hand side is the evaluation stack, the top of stack is on the right most.

read "22",  it is a number push it    [22 ]
read "+",   it is an infix op,  eval read next
read "33", it is a number push it     [22 33 ]
then perform "+"                           [55 ]
read "-", it is an infix op, eval read next
read "1", it is a number push it       [55 1 ]
then perform "-"                            [54 ]
read "=",  do display, print top of stack to a screen.  [ ]

Implementation

The easiest way to do "switch" in S2 assembly language is to use a sequence of "if..then...else if .."

  if t == 1 then do ..
  else if t == 2 then do ..
  else if t == 3 then do ..

But it is slow, it takes in average the time of n/2 where n is the number of case.  To make it faster, you can use "computed goto", using the instruction "ret r1". It can compute the address in the "jump table".   This method will reduce the time from n/2 to a constant time (fastest possible).  I will show how to do it in the class.

Work in progress

I am working on "loading a special function" into the calculator.  It is like loading an executable object into the simulator.  However, we need to link the address with the "switch" statement in the eval function properly (the routines doF0...doF9).

7 Feb 2007