Chapter Seven

Execute Expression

The Execute Expression routine is entered when the Program Executor needs to evaluate a BASIC expression within a statement. It is also the executor for the LET and implied LET statements. Expression operators have an order of precedence; some must be simulated before others. To properly evaluate an expression, Execute Expression rearranges it during the evaluation. Expression Rearrangement Concepts Operator precedence rules in algebraic expressions are so simple and so unconscious that most people aren't aware of following them. When you evaluate a simple expression like Y=AX2+BX+C, you don't think: "Exponentiation has a higher precedence than multiplication, which has a higher precedence than addition; therefore, I will first square the X, then perform the multiplication." You just do it. Computers don't develop habits or common sense - they have to be specifically commanded. It would be nice if we could just type Y = AX2+BX+C into our machine and have the computer understand, but instead we must separate all our variables with operators. We also have to learn a few new operators, such as * for multiply and ^ for exponentiation. Given that we are willing to adjust our thinking this much, we enter Y=A*X^2+B*X+C. The new form of expression does not quite have the same feel as Y AX2+BX+C; we have translated normal human patterns halfway into a form the computer can use. Even the operation X^2 causes another problem for the computer. It would really prefer that we give it the two values first, then tell it what to do with them. Since the computer still needs separators between items, we should write X^2 as X,2,^. Now we have something the computer can work with. It can obtain the two values X,2, apply the operator ^, and get a result without having to look ahead. 55


Chapter Seven If we were to transcribe X^2*A in the same manner, we would have X,2,^,A,*. The value returned by X,2,^ is the first value to multiply, so the value pair for multiplication is (X,2,^) and A. Again we have two values followed by an operator, and the computer can understand. If we continue to transcribe the expression by pairing values and operators, we find that we don't want to add the value X^2*A to B; we want to add the value X^2*A to B*X. Therefore, we need to tell the computer X,2,^,A,*,B,X,*, +. The value pair for the operator + is (X,2,^,A,*) and (B,X,*). The value pair for the final operation, =, is (X,2,^,A,*,B,X, *,+,C,+) and Y. So the complete translation of Y=AX2+BX+ C is X,2,^,A,*,B,X,*,+,C,+,Y,=. Very few people other than Forth programmers put up with this form of expression transcription. Therefore, Atari BASIC was designed to perform this translation for us, provided we use the correct symbols, like * and ^. The Expression Rearrangement Algorithm The algorithm for expression rearrangement requires two LIFO stacks for temporary storage of the rearranged terms. The Operator Stack is used for temporarily saving operators; the Argument Stack is used for saving arguments. Arguments are values consisting of variables, constants, and the constant-like values resulting from previous expression operations. Operator Precedence Table The Atari BASIC User's Manual lists the operators by precedence. The highest-precedence operators, like <, >, and = <, are at the top of the list; the lowest-precedence operator, OR, is at the bottom. The operators at the top of the list get executed before the operators at the bottom of the list. The operators in the precedence table are arranged in the same order as the Operator Name Table. Thus the token values can be used as direct indices to obtain an operator precedence value. The entry for each operator in the Operator Precedence Table contains two precedence values, the go-onto-stack precedence and the come-off-stack precedence. When a new operator has been plucked from an expression, its go-onto- stack precedence is tested in relation to the top-of-stack operator's come-off-stack precedence. 56
Chapter Seven Expression Rearrangement Procedure The symbols of the expression (the arguments and the operators) are accessed sequentially from left to right, then rearranged into their correct order of precedence by the following procedure: 1. Initialize the Operator Stack with the Start Of Expression (SOE) operator. 2. Get the next symbol from the expression. 3. If the symbol is an argument (variable or constant), place the argument on the top of the Argument Stack. Go to step 2. 4. If the symbol is an operator, save the operator in the temporary save cell, SAVEOP. 5. Compare the go-onto-stack precedence of the operator in SAVEOP to the come-off stack precedence of the operator on the top of the Operator Stack. 6. If the top-of-stack operator's precedence is less than the precedence of the SAVEOP operator, then the SAVEOP operator is pushed onto the Operator Stack. When the push is done, go back to step 2. 7. If the top-of-stack operator's precedence is equal to or greater than the precedence of the SAVEOP operator, then pop the top-of-stack operator and execute it. When the execution is done, go back to step 5 and continue. The Expression Rearrangement Procedure has one apparent problem. It seems that there is no way to stop it. There are no exits for the "evaluation done" condition. This problem is handled by enclosing the expression with two special operators: the Start Of Expression (S0E) operator, and the End Of Expression (EOE) operator. Remember that SOE was the first operator placed on the Operator Stack, in step 1. Execution code for the SOE operator will cause the procedure to be exited in step 7, when SOE is popped and executed. The EOE operator is never executed. EOF's function is to force the execution of SOF. The precedence values of SOE and EOE are set to insure that SOE is executed only when the expression evaluation is finished The SOE come-off-stack precedence is set so that its value is always less than all the other operators' go-onto-stack precedence values. The EOE go-onto-stack precedence is set so that its value is always equal to or less than all the other 57
Chapter Seven operators' (including SOE's) corae-off-stack precedence values. Because SOE and EOE precedence are set this way, no operator other than EOE can cause SOE to be popped and executed. Second, EOE will cause all stacked operators, including SOE, to be popped and executed. Since SOE is always at the start of the expression and EOE is always at the end of the expression, SOE will not be executed until the expression is fully evaluated. In actual practice, the SOE operator is not physically part of the expression in the Statement Table. The Expression Rearrangement Procedure initializes the Operator Stack with the SOE operator before it begins to examine the expression. There is no single operator defined as the End Of Expression (EOE) operator. Every BASIC expression is followed by a symbol like :, THEN, or the EOL character. All of these symbols function as operators with precedence equivalent to the precedence of our phantom EOE operator. The THEN token, for example, serves a dual purpose. It not only indicates the THEN action, but also acts as the EOE operator when it follows an expression. Expression Rearrangement Example To illustrate how the expression evaluation procedure works, including expression rearrangement, we will evaluate our Y = A*X^2 + B*X + C example and see how the expression is rearranged to X,2,^,A,*,B,X,*,+,C,+,Y,= with a correct result. To work our example, we need to establish a precedence table for the operators. The values in Figure 7-1 are similar to the actual values of these operators in Atari BASIC. The lowest precedence value is zero; the highest precedence value is $0F. Figure 7-1. Example precedence Table operator go-on-stack come-off-stack symbol precedence precedence SOE NA $00 + $09 $09 * $0A $0A ^ s0C $0C = $0F $01 !(EOE) $00 NA 58
Chapter Seven Symbol values and notations. In the example steps, the term PSn refers to step n in the Expression Rearrangement Procedure (page 57). Step 5, for instance, will be called P55. In the actual expression, the current symbol will be underlined. If B is the current symbol, then the actual expression will appear as Y=A*X 2+B*X+C . In the rearranged expression, the symbols which have been evaluated up to that point will also be underlined. The values of the variables are: A=2 C=6 B=4 X=3 The variable values are assumed to be accessed when the variable arguments are popped for operator execution. The end-of-expression operator is represented by!. Example step 1. Actual Expression: Y=A*X^2 + B*X + C! Rearranged Expression: X,2,^,A,*,B,X,*,+,C,+,Y,=,! Argument Stack: Operator Stack: SOE SAVEOP: PS1 has been executed. The Operator Stack has been initialized with the SOE operator. We are ready to start processing the expression symbols. Example step 2. Actual Expression: Y= A*X^2+B*X+C! RearrangedExpression: X,2,^,A,*,B,X,*,+,C,+,Y,=,! Argument Stack: Y Operator Stack: SOE SAVEOP: The first symbol, Y, has been obtained and stacked in the Argument Stack according to PS2 and P53. Example step 3. Actual Expression: Y=A*X^2+B*X+C! Rearranged Expression: X,2,^,A,*,B,X,*,+,C,+,Y,=,! Argument Stack: Y Operator Stack: SOE,= SAVEOP: = 59
Chapter Seven Operator = has been obtained via PS2. The relative precedences of SOE ($00) and = ($0F) dictate that the = be placed on the Operator Stack via PS6. Example step 4. Actual Expression: Y=A*X^2+B*X+C! Rearranged Expression: X,2,^,A,*,B,X,*,+,C,+,Y,=,! Argument Stack: Y,A Operator Stack: SOE, = SAVEOP: The next symbol is A. This symbol is pushed onto the Argument Stack via PS3. Example step 5. Actual Expression: Y=A*X^2+B*X+C! Rearranged Expression: X,2,^,A,*,B,X,*,+,C,+,Y,=,! Argument Stack: Y,A Operator Stack: SOE, = , * SAVEOP: * The next symbol is the operator *. The relative precedence of * and = dictates that * be pushed onto the Operator Stack. Example step 6. Actual Expression: Y = A*X^2+B*X+C! Rearranged Expression: X,2,^,A,*,B,X,*,+,C,+,Y,=,! Argument Stack: Y,A,X Operator Stack: SOE, = , * SAVEOP: The next symbol is the variable X. This symbol is stacked on the Argument Stack according to PS3. Example step 7. Actual Expression: Y=A*X^2+B*X+C! Rearranged Expression: X,2,^,A,*,B,X,*,+C,+,Y,=,! Argument Stack: Y,A,X Operator Stack: SOE, = ,~, A U;' SAVEOP: A The next symbol is ^ The relative precedence of the and the * dictate that ^ be stacked via PS6. 60
Chapter Seven Example step 8. Actual Expression: Y=A*X^2+B*X+C! Rearranged Expression X,2,^,A,*,B,X,*,+,C,+,Y,=,! Argument Stack: Y,A,X,2 Operator Stack: SOE,=,*,^ SAVEOP: The next symbol is 2. This symbol is stacked on the Argument Stack via PS3. Example step 9. Actual Expression: Y=A*X^2+B*X+C! Rearranged Expression X,2,^,A,*,B,X,*,+,C,+,Y,=! Argument Stack: Y,A,9 Operator Stack: SOE,=,*, SAVEOP:+ The next symbol is the operator +. The precedence of the operator that was at the top of the stack, ^ , is greater than the precedence of +. PS7 dictates that the top-of-stack operator be popped and executed. The ^ operator is popped. Its execution causes arguments X and 2 to be popped from the Argument Stack, replacing the variable with the value that it represents and operating on the two values yielded: X^2=3^2=9. The resulting value, 9, is pushed onto the Argument Stack. The + operator remains in SAVEOP. We continue at PS5. Note that in the rearranged expression the first symbols, X,2,^, have been evaluated according to plan. Example step 10. Actual Expression: Y=A*X^2+B*X+C! Rearranged Expression: X,2,^,A,*,B,X,*,+,C,+,Y,=,! Argument Stack: Y,18 Operator Stack: SOE,= SAVEOP: + This step originates at PS5. The SAVEOP operator, +, has a precedence that is less than the operator which was at the top of the stack, *. Therefore, according to P57, the is popped and executed. The execution of * results in A*9=2*9=18. The resulting value is pushed onto the Argument Stack. 61
Chapter Seven Example step 11. Actual Expression: Y = A*X^2+B*X+C! Rearranged Expression: X,2,^,A,*,B,X,*,+,C,+,Y,=,! Argument Stack: Y,18 Operator Stack: SOE, =, + SAVEOP: When step 10 finished, we went to P55. The operator in SAVEOP was +. Since + has a higher precedence than the top- of-stack operator, =, the + operator was pushed onto the Operator Stack via PS6. Example step 12. Actual Expression: Y=A*X^2+B*X+C! Rearranged Expression: X,2,^,A,*,B,X,*,+,C,+,Y,=,! Argument Stack: Y,18,B Operator Stack: SOE, =, + SAVEOP: The next symbol is the variable B, which is pushed onto the Argument Stack via P53. Example step 13. Actual Expression: Y = A*X^2+B*X+C! Rearranged Expression: X,2,^,A,*,B,X,*,+,C,+,Y,=,! Argument Stack: Y,18,B Operator Stack: SOE, =,+,* SAVEOP: * The next symbol is the operator *. Since * has a higher precedence than the top-of-stack +, * is pushed onto the stack via PS6. Example step 14. Actual Expression: Y = A*X^2+B*X+C! Rearranged Expression: X,2,^,A,*,B,X,*,+,C,+,Y,=,! Argument Stack: Y,18,B,X Operator Stack: SOE, =, + * SAVEOP: The variable X is pushed onto the Argument Stack via PS3. Example step 15. Actual Expression: Y=A*X^2+B*X+C! Rearranged Expression: X,2,^,A,*,+,C,+,Y, =,! 62
Chapter Seven Argument Stack: Y,18,12 Operator Stack: SOE, =,+ SAVEOP: + The operator + is retneved from the expression. Since + has a lower precedence than which is at the top of the stack, * is popped and executed. The execution of * causes B*X=4*3=12. The resulting value of 12 is pushed onto the Argument Stack. We will continue at PS5 via the P57 exit rule. Example step 16. Actual Expression: Y=A*X^2+B*X+C! Rearranged Expression: X,2,^,A,*,B,X,*,+,C,+,Y,=,! Argument Stack: Y,30 Operator Stack: SOE,= SAVEOP: + This step starts at PS5. The SAVEOP operator, +, has precedence that is equal to the precedence of the top-of-stack operator, also +. Therefore, + is popped from the operator stack and executed. The results of the execution cause 18+12, or 30, to be pushed onto the Argument Stack. PS5 is called. Example step 17. Actual Expression: Y=A*X^2+B*X+C! Rearranged Expression: X,2,^,A,*,B,X,*,+,C,+,Y,=,! Argument Stack: Y,30 Operator Stack: SOE, =,+ SAVEOP: This step starts at PS5. The SAVEOP is +. The top-of-stack operator, =, has a lower precedence than +; therefore, + is pushed onto the stack via PS6. Example step 18. Actual Expression: Y=A*X^2+B*X+C! Rearranged Expression: X,2,^,A,*,B,X,*,+,C,+,Y,=,! Argument Stack: Y,30,C Operator Stack: SOE, =,+ SAVEOP: The variable C is pushed onto the Argument Stack via PS3. 63
Chapter Seven Example step 19. Actual Expression: Y=A*X^2+B*X+C! Rearranged Expression: X,2,^,A,*,B,X,*,+,C,+,Y,=,! Argument Stack: Y,36 Operator Stack: SOE, SAVFOP: The EOE operator is plucked from the expression. The EOE has a lower precedence than the top-of-stack + operator. Therefore, + is popped and executed. The resulting value of 30+6, 36, is pushed onto the Argument Stack. PS5 will execute next. Example step 20. Actual Expression: Y=A*X^2+B*X+C! Rearranged Expression: X,2,^,A,*,B,X,*,+,C,+,Y,=,! Argument Stack: Operator Stack: SOE SAVEOP: ! This step starts at P55. The ! operator has a lower precedence than the top-of-stack = operator, which is popped and executed. The execution of = causes the value 36 to be assigned to Y. This leaves the Argument Stack empty. PS5 will be executed next. Example step 21. Actual Expression: Y=A*X^2+B*X+C! Rearranged Expression: X,2,^,A,*,B,X,*,+,C+,Y,=,! Argument Stack: Operator Stack: SAVEOP: ! The operator in SAVEOP causes the SOE operator to be popped and executed. The execution of SOF terminates the expression evaluation. Note that the rearranged expression was executed exactly as predicted. Mainline Code The Execute Expression code implements the Expression Rearrangement Procedure. The mainline code starts at the EXEXPR label at $AAE0. The input to EXEXPR starts at the current token in the current statement. STMCUR points to the 64
Chapter Seven current statement. STINDEX contains the displacement to the current token in the STMCUR statement. The output of EXEXPR is whatever values remain on the top of the argument stack when the expression evaluation is finished. In the following discussion, PSn refers to the procedure step n in the Expression Rearrangement Procedure. PS1, initialization, occurs when EXEXPR is entered. EXPINT is called to initialize the operator and argument stacks. EXPINT places the SOF operator on the operator stack. PS2, which obtains the next token, directly follows initialization at EXNXT ($AAE3). The code calls EGTOKEN to get the next expression symbol and classify it. If the token is an argument, the carry will be set. If the token is an operator, the carry will be clear. If the token is an argument, P53 is implemented via a call to ARGPUSH. After the argument is pushed onto the argument stack, EXNXT (PS2) will receive control. If the token was an operator, then the code at EXOT ($AAEE) will be executed This code implements P54 by saving the token in EXSVOP. PS5, which compares the precedents of the EXSVOP token and the top-of-stack token, follows EXOT at EXPTST ($AAFA). This code also executes the SOE operator If SOE is popped, then Execute Expression finishes via RTS. If the top-of-stack operator precedence is less than the EXSVOP operator precedence1 PS6 is implemented at EOPUSH ($AB15). EOPUSH pushes EXSVOP onto the operator stack and then goes to EXNXT (PS2). If the top-of-stack operator precedence is greater than or equal to the EXSVOP operator precedence, then PS7 is implemented at EXOPOP ($AB0B). EXOPOP will pop the top- of-stack operator and execute it by calling EXOP. When EXOP is done, control passes to EXPTST (PS5). Expression Evaluation Stacks The two expression evaluation stacks, the Argument Stack and the Operator Stack, share a single 256-byte memory area. The Argument Stack grows upward from the lower end of the 256- byte area. The Operator Stack grows downward from the upper end of the 256-byte area. The 256-byte stack area is the multipurpose buffer at the start of the RAM tables. The buffer is pointed to by the 65
Chapter Seven ARGSTK (also ARGOPS) zero-page pointer at $80. The current index into the Argument Stack is maintained by ARSLVL ($AA). When the Argument Stack is empty, ARSLVL is zero. The OPSTKX cell maintains the current index into the Operator Stack. When the Operator Stack is initialized with the SOE operator, OPSTKX is inihalized to $FF. As operators are added to the Operator Stack, OPSTKX is decremented. As arguments are added to the Argument Stack, ARSLVL is incremented. Since the two stacks share a single 256-byte memory area, there is a possibility that the stacks will run into each other. The code at $ABC1 is used to detect a stack collision. It does this by comparing the values in ARSLVL and OPSTKX. If ARSLVL is greater than or equal to OPSTKX, then a stack collision occurs, sending the STACK OVERFLOW error to the user. Operator Stack Each entry on the Operator Stack is a single-byte operator-type token. Operators are pushed onto the stack at EXOPUSH (SAB15) and are popped from the stack at EXOPOP ($ABOB). Argument Stack Each entry on the Argument Stack is eight bytes long. The format of these entries is described in Figures 7-2, 7-3, and 7-4, and are the same as the formats for entries in the Variable Value Table. Unlike the Variable Value Table, the Argument Stack must deal with both variables and constants. In Figure 7-2, we see that VNUM is used to distinguish variable entries from constant entries. The SADR and AADR fields in the entries for strings and arrays are of special interest. (See Figures 7-3 and 7-4.) When a string or array variable is dimensioned, space for the variable is created in the string/array space. The displacement to the start of the variable's area within the string/array space is placed in the SADR/AADR fields at that time. A displacement is used rather than an absolute address because the absolute address can change if any program changes are made after the DIM statement is executed. Execute Expression needs these values to be absolute address values within the 6502 address space. When a string/array variable is retrieved from the Variable Value Table, 66
Chapter Seven the displacement is transformed to an absolute address. When (and if) the variable is put back into the Variable Value Table, the absolute address is converted back to a displacement. The entries for string constants also deserve some special attention. String constants are the quoted strings within the user program. These strings become part of the tokenized statements in the Statement Table. When Execute Expression gets a string token, it will create a string constant Argument Stack entry. This entry's SADR is an absolute address pointer to the string in the Statement Table. SLEN and SDIM are set to the actual length of the quoted string. Argument Work Area An argument which is currently being examined by Execute Expression is kept in a special zero-page Argument Work Area (AWA). The AWA starts at the label VTYPE at $D2. Figure 7-2. Argument Stack Entry 0 1 2 8 +-------+------+----------+ | VTYPE | VNUM | DATA | +-------+------+----------+ | | | | | | | | Data Field. Format depends on VTYPE. | | | +---- If VNUM =0, the entry is a constant. | If VNUM >0, the entry is a variable. In this case, | the VNUM value is the entry number in the Variable | Value Table. The token representing this variable is | VNUM+$80. | +---- $00=Data is a six-byte floating point constant. $80=Data represents an undimensioned string. $81=Data represents a dimensioned string with a relative address pointer. $83=Data represents a dimensioned string with an absolute address pointer. $40=Data represents an undimensioned array. $41=Data represents a dimensioned array with a relative address pointer. $43=Data represents a dimensioned array with an absolute address pointer. 67
Chapter Seven Figure 7-3. Argument Stack String Entry 0 1 2 4 6 8 +-------+------+------+------+------+ | VTYPE | VNUM | SADR | SLEN | SDIM | +-------+------+------+------+------+ | | | +---------------------+ | | | +--------------------------+ | | | +-------------------------------+ | | | Dimensioned length of the string. Valid only if | | +- VTYPE=$81 or $83. | | | +--- Current length of the string. Valid only if VTYPE | =$81 or $83. | +----| String address. Valid only if VTYPE=$81 or $83. | If VTYPE=$81, then SADR is the displacement | of the start of the string from the start of the | string/array space. | | If VTYPE=$83, then SADR is the absolute address | of the start of the string. Figure 7-4. Argument Stack Array Entry 0 1 2 4 6 8 +-------+------+------+------+------+ | VTYPE | VNUM | SADR | DIM1 | DIM2 | +-------+------+------+------+------+ | | | +---------------------+ | | | +--------------------------+ | | | +-------------------------------+ | | | When an array has been dimensioned as A(DI,D2), | | +- this field contains the D2 value. If an array | | was dimensioned as A(DI), then this field is | | zero. The field is valid only if VTYPE=$41 or | | $43. | | | | When an array has been dimensioned, as A(D1,D2) | |--- or as A(D1), this field contains the D1 value. | The field is valid only if VTYPE=$41 or $43. | | | Array Address. Valid only if VTYPE=$41 or $43. +----| | If VTYPE=$41, the AADR is the displacement to | the start of the array in the string/array space. | | If VTYPE=$43, the AADR is the absolute address | of the start of the string. 68
Chapter Seven Operator Executions An operaror is executed when it is popped from the Operator Stack. Execute Expression calls EXOP at $AB20 to start this execution. The EXOP routine uses the operator token value as an index into the Operator Execution Table ($AA70). The operator execution address from this table, minus 1, is placed on the 6502 CPU stack. An RTS is then executed to begin executing the operator's code. The names of the operator execution routines all begin with the characters XP. All the Atari BASIC functions, such as PEEK, RND, and ABS, are executed as operators. Most routines for the execution of the operators are very simple and straightforward. For example, the * operator routine, XPMUL ($AC96), pops two arguments, multiplies them via the floating point package, pushes the result onto the argument stack, and returns. String, Array, DIM, and Function Operations Any array reference in an expression may be found in one of two forms: A(x) or A(x,y). The indices x andy may be any valid expression. The intent of the indices is to reference a specific array element. Before the specific element reference can take place, the x and/or y index expressions must be fully evaluated. To do this, the characters '(' ',' and ')' are made operators. The precedence of these operators forces things to happen in the correct sequence. Figure 7-5 shows the relative precedence of these operators for an array. Figure 7-5. Array Operator Precedence operator go-on-stack come-off-stack symbol precedence precedence ( $0F $02 ,(comma) $04 $03 ) $04 $0E As a result of these precedence values, ( has a high enough precedence to go onto the stack, no matter what other operator is on the top of the stack. 69
Chapter Seven The comma's go-on-stack precedence will force all operators except ( to be popped and executed. As a result, the x index sub-expression in the expression A(x,y), will be fully evaluated and the final x index value will be pushed onto the Argument Stack. The comma will then be placed onto the Operator Stack. Its come-off-stack precedence is such that no other operator, except ), will pop it off. The ) operator precedence will force any y index expression to be fully evaluated and the y index result value to be placed onto the Argument Stack. It will then force the comma operator to be popped and executed. This action results in a comma counter being incremented. The ) will then force the ( to be popped and executed. The execution of ( results in the proper array element being referenced. The ( operator will pop the indices from the Argument Stack. The number of indices (either zero or one) to be popped is governed by the comma counter, which was incremented by one for each comma that was popped and executed. Atari BASIC has numerous ( tokens, and each causes a different ( routine to be executed. These ( operators are array (CALPRN), string (CSLPRN) array DIM (CDLPRN) string DIM (CDSLPR), function (CFLPRN), and the expression grouping CLPRN operator. The Syntax Table pseudo-instruction CHNG is used to change the CLPRN token to the other ( tokens in accordance with the context of the grammar. The expression operations for each of these various ( operators in relation to commas and ( is exactly the same. When ( is executed, the comma count will show how many arguments the operator's code must pop from the argument stack. Each of these arguments will have been evaluated down to a single value in the form of a constant. 70

<-Chapter 06Chapter 08->