In the Sinclair 8K ROM program of the ZX80/81 the “expression evaluator” is to be found at 0F55-111Bh (improved 8K ROM) and forms an essential part of the program. A study of the fundamental parts of the “expression evaluator” can be very useful as it enables Basic programmers to understand many of the limitations and quirks of the Sinclair Basic.
Some Definitions
First we must make some definitions:
Expression. An expression is any combination of numbers, variables, strings, functions, and operators that can be combined to form the operand of a command. For example:
1) 2—a simple number.
2) 2*A—a number and a variable linked by a binary operator.
3) CHR$ 32—a function and a number.
4) CHR$(T+A-26*INT ((T+A)+38)—my favorite complex expression.
Function. Function includes the expected keywords ABS, CHR$, INT, etc., but do not ignore the two special functions NOT and -. NOT is a function that gives an “opposite logical result,” i.e., NOT 3 gives 0 as the number 3 is logically “true.” When – is used as a “leading minus,” it gives an “opposite numeric result,” i.e., -3 should be taken as”+3″subjected to the function-.
Binary operators. In the 8K ROM program the following binary operators are allowed: **, *, /, +, -, =, <=, >=, <, >, AND, OR. In each case a binary operator is required to be between two operands, which may in turn be “subexpressions” in their own right.
Unary operators. There are three special operators in this group: RND, PI, and INKEY$. In one sense they are not operators at all and they can, if preferred, be considered as “fixed variables.”
Priority. All of the binary operators and functions have associated with them a “priority” that is used to determine the “order of the operations.” Hence, 2+4*3 is 14 rather than 18 since multiplication has the priority value of 8 and addition a value of 6.
Last value. Last value is, perhaps, a difficult point to understand but the Sinclair 8K ROM program evaluates expressions to produce a “last value” on the “calculator stack.” For a numeric result the “last value” is a 5 byte floating-point number and for a string result a set of 5 parameters that define the string.
The Actual “Expression Evaluator”
The object of the “evaluator” is to produce a single “last value” that corresponds to the expression that it has been given. For instance, if the expression is a simple one such as 2, then the “last value” produced will be the number 2 in binary floating-point form, and it will be the topmost number on the calculator stack. However, if the expression is 2+4*3, then the “last value” is to be 14 and this has to be “evaluated” by “scanning” the expression from left to right and saving the part-answers as they occur and the operations to be performed until the point is reached when the “saved” answers and operations have to be used.
A Simple Evaluation
A Basic line such as 10 PRINT 2 appears to be a very simple line but its interpretation by the 8K ROM program involves an almost unbelievable amount of work. Initially the interpreter has to locate line 10, then scan the line for its first command and jump to that command’s routine. In this example, the jump is to the PRINT COMMAND ROUTINE at 0ACFh. In this routine a call is made to the “expression evaluator” so as to create a “last value” from the operand of the PRINT command, i.e., the 2, and then a call is made to PRINT-STK, the routine that prints the correct representation of the “last value” on the TV display. A check is then made to see if the line is finished, which in this case it is, before the next line is considered.
It can be seen in the above description that the use of the “expression evaluator” is essential and an outline view of this routine will now be given.
1) Put a zero on the machine stack as a “starting priority marker.”
2) See if the first character of the expression is a “unary operator.” No.
3) Is the character alphanumeric? Yes. So jump accordingly.
4) Is it a digit? Yes. So jump accordingly.
5) Transfer the invisible binary representation of the number 2 to the calculator stack as a “last value” (remember the line 10 PRINT 2 has its binary representation in 6 bytes between the 2 and the NEWLINE).
6) Fetch the next character in the line. It is a NEWLINE.
7) Jump forward to the “evaluation loop” if it is not an operator. At this point the “last operation” code is zero.
8) In the “loop” an exit is made as the “last operation” code is the same as the “starting priority marker.” Both are zero.
Note the successful outcome! The “last value” on the calculator stack is the floating-point representation of 2 as was required.
The Next Stage
Let us go through this outline view of the work of the expression evaluator again, but this time the expression is 2+4*3—a seemingly innocent expression that is a great deal more complex than appears at first sight!
1) Put the “starting priority marker” of zero on the machine stack.
2) Perform the steps outlined above in 2-5 that result in a “last value” of “2” going onto the calculator stack.
3) Fetch the next character: a +.
4) This time it is an operator so prepare the “literal,” 0F, and the priority of 06 for the operation of addition.
5) Enter the “evaluation loop” and as the “present priority” is greater than the “last priority” (that zero) put the “present literal” and “present priority” onto the machine stack on top of the “last literal and priority” (that zero again).
6) Now fetch the next character, the 4, and go back to step 2 again with a different operand. This time a “last value” of 4 goes on the calculator stack on top of the 2. The “literal,” 04, and the corresponding priority of 08 for multiplication are prepared and the “evaluation loop” entered once again.
7) Here the “present priority” is greater than the “last priority,” i.e, 08 is greater than 06, so again the “present priority and literal” go onto the machine stack. (The evaluator has determined that 2 is not to be added to 4, as the 4 is followed by a “more binding” operator.)
8) Now fetch the next character, the 3, and loop back to create a “last value” of 3, above the 4, and the 2.
9) Alas, the end of the expression has been reached. The “present operator” is zero because the present character is a NEWLINE and the “evaluator loop” is entered for the final time.
10) At this point the priorities are 00, 06, 08 and 00 whilst the calculator stack holds 2, 4, and 3. These stacked values now have to be “unstacked” and this is done as follows: The “present priority”of 00 is less than the “last priority” of 08 so the operation of multiplication, associated with the “last priority,” is performed between the top two numbers of the calculator stack.
11) Now the priorities are 00, 06, and 00 and the stack holds 2 and 12. As the “present priority” 00 is less than the last priority 06, the operation of addition is performed.
12) Now the end has been reached. The priorities are 00 and 00 and, since there is but one value on the calculator stack, the required 14, the EXIT is taken.
Although the above examples have dealt only with simple decimal numbers and binary operators the other facilities of the expression evaluator are managed in a similar manner. A variable, such as A, is evaluated to a “last value” and used accordingly. A function such as COS is identified and its literal and priority prepared, and the “operation” of COSing the “last value” is performed when required. Note that it is part of the “calculator” which ensures that a unary operation replaces a “last value” with another, and a binary operation replaces two values with a “last value.”
The “expression evaluator” also handles the special operators RND, PI, and INKEY$. Indeed there are no subroutines for these operators but merely segments of the “expression evaluator” deal with them in a “straight programming” manner. The addresses of the segments are (all improved ROM):
RND—0F59h
PI—0F8Ch
INKEY$—0F9Dh
The Priorities
The last point we need to cover is to correct the ZX81 BASIC Programming manual with regard to the “priorities” of the various operations. They are:
Priority Operations and Functions Decimal All functions (except LEADING MINUS and NOT) 16 ** 10 LEADING MINUS 9 * 8 -, + 6 =, >=, <=, >, <, <> 5 NOT 4 AND 3 OR 2
Demonstration Program
Our program this time is an exercise in graphics. It is quite easy to get vehicles to go across the screen, but it is a little more complicated to get them appearing in stages from the left and disappearing slowly at the right!
Listing 1: A SYNC Delivery Van.
10 SLOW
20 LET A$="[32 spaces][inv SYNC][graphic on R][33 spaces][6 inverse spaces][32 spaces]O O[33 spaces]"
30 FOR L=1 TO 15
40 FOR A=37 TO 1 STEP -1
50 PRINT AT L,0;A$(A TO A+31);A$(A+38 TO A+69);A$(A+76 TO A+107)
60 NEXT A
70 CLS
80 NEXT LProgram notes
Line 20: After the ” enter 32 spaces, type in SYNC in reverse letters (hit shift and 9 to get the graphics mode and then type in the letters), enter the graphic on the R key, enter 33 spaces, enter 6 reverse spaces (get into graphics mode and hit the space key 6 times), enter 32 spaces, the letter O, 3 spaces, the letter O, and 33 spaces. Close with the “.
After entering the program, hit RUN and ENTER and watch the results.
Ed.—Note that Dr. Logan’s Sinclair ROM Disassembly Parts A and B will provide major assistance. They can be obtained from several advertisers or directly from Dr. Logan.