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