In this article we present an easily extended, interactive interpreter, providing a stack oriented, dictionary based programming environment similar to FORTH. The interpreter is, thus, the basis for the more friendly, more interactive use of your computer. The ease with which INTERP can be coded is a dramatic demonstration of the power of the ZX81 string manipulation capabilities and the GOSUB and VAL commands.
Interaction
The essence of effective use of the personal computer is contained in the word, “interaction.” While more memory and languages are desirable to have, solving problems with a computer is essentially a function of how easy it is to control the machine. A computer is able to perform simple tasks like adding one and one, or recalling what the balance is in the checking account, or integrating a set of differential equations. What it has trouble with, and what humans excel at, is decision making and recognition of the significance of a result. (Computers are just as happy with a balance of -$1.00 as +$100,000.00) Thus, a proper man-machine dialogue might have the form:
Man: What would happen if ….?
Machine: !!!!!!! (a result unexpected or undesired by Man)
Man: Well then, do this first: …..
Man: And then, do this: ….
Machine: ….. Hmmm
Man: Given that, what would the further consequences be?
Machine: …….
Man: Thanks.
Any program which inputs data and permits decisions on the basis of the input is, of course, interactive. The operationally important point is that in normal programs, the control is quite limited. The flow of code is restricted. Control cannot be arbitrarily transferred from one place in a program to another. Humans do not normally suffer from this restriction. They can do their operations in whatever order is most convenient. The purpose of INTERP is to provide the basis of a “General Interactive System” of maximal flexibility.
The features required in an interactive system can be seen in the following simple example. Consider a program to keep track of where you are spending your money. Inputs to your program are the amount and the type of each expenditure. We leave the details of the coding as a problem for the reader, but a typical interactive session with a program based on INTERP could be
? 225.00 RENT 42.27 FOOD 9.25 CLOTHING 2*0.90 3*0.65 + 0.45 + , FOOD EXPENDITURES CLS ... more entries ... EXPENDITURES STOP
The general features and requirements demonstrated by this example are as follows:
1) The interactive system is composed of individual modules or “primitive operations.” In the above example, “EXPENDITURES”, lists the totals so far in each category, while “RENT” adds the amount indicated to the category rent. Each module has a well-defined input and output. They share data but their actions are accomplished by separate pieces of code.
2) Except for obvious dependencies like initialization, the order in which the modules may be invoked is arbitrary.
3) The simplest way to call up a module is by name. It is both more easily remembered and more reliable to use “RENT” than to choose this operation by number from a menu, which is the typical method employed.
4) There must be a general way of passing values or “arguments” to and from the modules. The result of an operation need not be printed, but it should be easily available. In other words, we want the equivalent of “named subroutines”.
5) Modules like “RENT” or “FOOD” are obviously problem specific, but some operations are of such general utility that they will be needed in most programs. The general purpose modules which are built into INTERP are:
? —Output the names of the modules defined in the dictionary.
, —Output the value at the top of the stack (see below for a
discussion of stacks).
. —Output the top element, then remove it from the stack.
Stop —Stop the program (SHIFT A), CONT will restart with no loss
of results.
CLS —Clear the screen; note this is the three letters C L S.
All Basic functions, e.g., RND or PI any variable used in the Basic code, e.g., S or D, or any arithmetic operator, e.g., ** or /, are legal and usable.
Basis of INTERP
The key element of our implementation of these ideas in INTERP will be the use of BASIC SUBROUTINES. A subroutine is simply a block of code which is called via the GOSUB command. Control is transferred to the line number given in the GOSUB call, as in a simple GOTO. The important difference is that subroutines remember from where they were called. When a RETURN command is encountered control returns to the line following the GOSUB which invoked the subroutine. Conceptually, a GOSUB command amounts to telling the program to “go perform a series of commands and then come back when you are done with them.” This is exactly what we want for a module.
For anyone accustomed to programming in languages such as Pascal or Fortran, the most fundamental deficiency in the ZX81 Basic is that subroutines are not named. While GOSUB 700, for example, can be executed interactively and may cause the data to be plotted, humans are more at ease with typing “PLOT” in order to accomplish that task. We clearly cannot change the definition of the Basic language, but what we can do is make it easier for a user to get at pieces of the code. That is, through INTERP we add another level of code which “interprets” the input. Via INTERP we expand the Basic vocabulary so it includes whatever operations we require.
The basis of the ability of INTERP to provide named subroutines is its dictionary, which consists of the names of the routines, stored in the string array, D$, and the definitions, which are nothing more than the line numbers with which the Basic subroutines start, stored in the array, D, in the same order as the words in D$. Because the order is the same, the elements of the two arrays are related when they have the same subscript. For example, D$(3) is the name of the third module, while D(3) is the line number where the third module starts. INTERP determines the meaning of an input word, W$, by scanning through the dictionary looking for the value of the subscript, J, for which W$=D$(J). Once the subscript is known, GOSUB D(J), executes the indicated subroutine. In other words, the dictionary gives a name to a line number. Of course, the block of code starting there must be a true subroutine, i.e., terminated by RETURN.
Central to the operation of INTERP is the concept of a “stack,” which is just the mathematical analogue of a pile of dishes on a spring-loaded dispenser at a cafeteria. Put a dish on the stack, and it “pushes” the stack of dishes down one level. Take a dish off, and it “pops” the stack up one level. The mathematical stack is just an array of numbers with a pointer to the location of the current “top of the stack.” The basic rule in “stack processing” is that an operator always works on the elements at the top of the stack. The stack provides the logical organization for performing a series of operations. Say we want to evaluate
ERFC (FUNC(PI+7))
In our stack system we would re-write this as
PI 7+FUNC ERFC
The PI and 7 are values placed on the stack. The + removes the two top stack elements, adds them, and puts the result back on the stack. FUNC and ERFC simply get their one argument from the stack and replace it with the appropriate result, ready for the next operation.
An operation always consists of removing the arguments used by the function from the top of the stack and leaving the result generated as the new top value. While the standard mathematical operators have either one or two arguments and return one value, user-defined functions may have as many arguments as needed and return an arbitrary number, up to the limit defined by the size of the stack.
Implementation of INTERP
Our interpreter consists of the following steps:
1) Get a word of input (GOSUB 200)
2) Is the word in the dictionary?
IF W$=D$(J) THEN GOSUB D(J)
3) If not found, then:
If the word is a Basic operator, apply it to the stack.
Otherwise apply VAL to it and put the result on the stack.
4) Go back to (1) for more words.
This is a fully general interpreter. As a side benefit, it is also a “Reverse Polish Computer” which can be used in the same way as an HP calculator.
While one could require that each word be terminated by NEWLINE, it is much more friendly to permit “type ahead,” that is, to allow the input to be as long a string as the user wishes. Words are then extracted from the input string by using internal spaces as delimiters. This is particularly convenient, since we permit arguments to be associated with subroutine calls. For example,
3 ERFC.
is easier to type and understand than the totally equivalent,
3
ERFC
When the input line has been completely processed, INTERP prompts for further input by printing, “OK”.
The division of the line into words is done in the code starting at line 240. Note that the code starting at line 300 “hashes'” the word being input. This hashing technique only affects words which are longer than four characters. It is done so that words of any length may be put in the dictionary without having to pay too high a storage cost. When strings are dimensioned, say DIM D$(20,4), the maximum number of characters in each D$(I) is the second value in the DIM statement. Thus, one could never store the string, “SOLVE”, in this array. LET D$(1) =”SOLVE” is legal, but results in D$(1) containing only “SOLV”. Thus, we hash the word by storing its first four characters, and then changing the fourth character to be the length of the word if it is longer than four characters. The effect is to reduce the length of all words to just four bytes, but to maintain distinction among them. For example, “SOLVE” becomes “SOL5”, while “SOLVENT” becomes “SOL7”. This hashing scheme must be recognized when extensions are made to the dictionary. The word, “SOLVE”, is made the seventh word on the dictionary by adding before line 90, LET D$(7)=”SOL5″ and changing the value of D, set in line 90, accordingly.
Note, how we use the CHR$ function in line 310 to generate the character corresponding to a numerical value. Since “O” is the 28th character in the ZX81 character set and the digits are stored in ascending order, CHR$(28+N) generates the symbol corresponding to the number N. If N=10, 11, …, the characters generated by this algorithm are “A”, “B”, …
The code starting at line 500 is used to evaluate expressions and is based on the extremely powerful ZX81 function, VAL. This operator, when applied to an arbitrary string, produces the numeric value defined by the string. For example, if the Basic variable X=O, the expression VAL “COS X” has the value 1. VAL permits the input to contain any BASIC expression which does not contain an explicit space. Expressions may also be entered in the “Reverse Polish Notation” natural to INTERP, although then each operator and term must be delimited by spaces. The point is that the type ahead feature uses spaces as delimiters. “2**3”, for example, which contains no spaces, is treated as a single expression. Since it is not found in the dictionary or recognized as an operator, it is evaluated by VAL and the result, 8, put on the stack. The input, “2 3 **”, where the symbols are separated by spaces, is split and each term treated separately. The “2” and “3” are individually evaluated by VAL and the corresponding numerical values put on the stack. Then INTERP recognizes “**” as a binary operator and, as described below, creates a string and then applies VAL to it the top two elements of the stack, replacing them with 8.
Strings containing operators are easily created. Almost every symbol appearing on the keyboard, with the exception of keywords like PLOT, UNPLOT, etc., which are white and above the keys, can be entered by a single keystroke. Thus, to enter the word STOP one needs only type SHIFT A; a call for the SIN operator is FUNCTION Q, and so on. Note, that even though the ZX81, when it prints these words, adds spaces of its own, they must be delimited by true spaces when being input to INTERP.
The hashed input word is compared with the dictionary in the loop starting at line 410. If it is found, the corresponding subroutine is executed. If not found, at line 500 it is checked to see whether the unknown word is actually a Basic operator. Finally, if still unrecognized, INTERP concludes that the word must actually be a Basic expression and goes to line 600 to evaluate it. The result produced by VAL is stored in the stack vector, S. If a typing error was made, the word entered will be meaningless to INTERP and an error will be signaled. If this happens, the user can continue without any loss of the computations already made by entering GOTO 100.
In order to apply W$ as a Basic operator, we must make one further judgment: is W$ a binary operator, like +, or a unary operator, like SIN? This is decided in line 510. The expression to be evaluated is constructed by string concatenation in lines 550 (binary operators) and 570 (unary operators). The values used are replaced on the stack by the value generated. We see here how by using VAL and string manipulation one can create at run time the equivalent of Basic program statements.
The stack in INTERP has been implemented using the array S(). The pointer to the top is the value of variable S. The top value on the stack is, therefore, S(S). Whenever the stack is manipulated, the value of S must be changed accordingly. For example, when one does a binary operation, as in lines 540-550, S is reduced by one. Any user subroutine which requires arguments should check that there actually are as many elements on the stack as will be needed. If S is less than the number that are needed, GOTO 9990 will generate an appropriate error response.
Simple Example: A Reverse Polish Calculator
As an example of how one adds new routines, let us produce a program which models a simple HP-like calculator. Because calculators are clearly interactive, INTERP is our natural starting point. We already have all the mathematical functions, so in order to create our calculator program, all we will need to add are a few operations for manipulating the stack:
DUP —Duplicate the tope element, i.e., push this value
again onto the stack.
SWAP —Interchange the top and next elements on the stack.
ROTATE —Rotate the order of the stack elements.
STACK —List the values on this stack, top first.
The code for including these four new words is given in the second listing. The important points to note are:
1) The new definitions in the dictionary must be made before line 100, the start of the interpreter.
2) If a name is longer than four letters, like ROTATE, it is stored in D$ by its first three letters followed by its length, “ROT6”.
3) Each subroutine must be terminated by a RETURN.
4) Routines should check that there are an adequate number of arguments on the stack. If there are not, the transfer GOTO 9990 will indicate the error.
If you are not familiar with the reverse Polish system used on HP calculators and in INTERP, it would pay you to enter the statements of the second listing and then to try it. One very important thing to note is INTERP DOES NOT AUTOMATICALLY OUTPUT ANY RESULTS. In order to see the result of a calculation you must use either the command, “,”, which will print the answer, or “.”, which prints and then discards the top of the stack. Typical calculations would be found in figure 1.
Figure 1.
3 DUP * 4 DUP * + = SQR. equivalent to PRINT SQR(3*3*=4*4) 1 2 / , 1 SWAP / . will print .5 and 2 1 2 3 4 * * * . equivalent to PRINT 1*2*3*4 STOP
Remember, the words and numbers can be entered using as many lines as you wish.
In passing, we should note that, while INTERP permits arbitrary length words, your fingers may not appreciate this. Thus, you will probably want to use “ROT” instead of “ROTATE”. To be entirely general, you can include both forms in the dictionary as there is no requirement that a given Basic module have a unique name.
General Use of INTERP
In itself, INTERP solves no problem; it only provides a framework which can be used to ensure that the code will be simple to use. The steps that should be taken in employing INTERP are:
1) Enter and save the basic INTERP program given in Listing 1.
2) Whenever you wish to create a program, LOAD INTERP.
3) Modify it, coding the various Basic routines you need. Terminate each by RETURN and make sure it properly adjusts S.
4) Extend the dictionary, by adding new values to D$() and defining D() accordingly. The variable D, defined in line 90, is the length of the dictionary.
5) SAVE your new program. The important point is that, although the code in Listing 1 is long, it need only be entered once. After it has been stored on tape, it can be loaded and the needed routines easily added.
We hope that you, too, find that INTERP is the best starting point for the creation of interactive programs. As it is a different approach from the typical one, at first, coding may feel strange, but the ease of its use will justify the learning experience.
Listing 1. INTERP.
1 REM INTERP
2 LET S=0
3 REM MAX STACK DEPTH IS 10
4 DIM S(10)
5 REM TO MAKE DICTIONARY SIZE >10 REDIMENSION D$ AND D
6 DIM D$(10,4)
7 DIM D(10)
10 LET D$(1)=","
11 LET D(1)=1530
12 LET D$(2)="."
13 LET D(2)=1505
14 LET D$(3)="CLS"
15 LET D(3)=1510
16 LET D$(4)="?"
17 LET D(4)=1525
20 REM INCLUDE USER DEFINITIONS HERE
89 REM D IS NUMBER OF WORDS IN DICT
90 LET D=5
91 LET D$(D)=" STOP "
92 LET D(D)=1500
98 LET L$=""
99 REM INTERPRETER
100 GOSUB 200
110 GOSUB 400
120 GOTO 100
199 REM WORD
200 IF L$<>"" THEN GOTO 240
210 PRINT "OK "
220 INPUT L$
230 PRINT L$
240 FOR L=1 TO LEN L$
250 IF L$(L)<>" " THEN NEXT L
260 LET W$=L$( TO L-1)
270 LET L$=L$(L+1 TO )
280 IF W$="" OR W$=" " THEN GOTO 200
290 RETURN
299 REM HASH
300 LET H$=(W$+" ")( TO 4)
310 IF LEN W$>4 THEN LET H$(4)=CHR$ (28+LEN W$)
320 RETURN
399 REM SEARCH DICTIONARY
400 GOSUB 300
410 FOR J=1 TO D
420 IF H$=D$(J) THEN GOTO 650
430 NEXT J
499 REM OPERATOR
500 IF LEN W$>1 OR W$<">" OR W$>"<>" OR W$<"SIN " AND W$>"/" THEN GOTO 600
510 IF W$>"/" AND W$<"**" THEN GOTO 570
520 REM BINARY OPERATOR
530 IF S<2 THEN GOTO 9990
540 LET S=S-1
550 LET S(S)=VAL ("S(S)"+W$+"S(S+1)")
560 RETURN
569 REM UNARY OPERATOR
570 LET S(S)=VAL (W$+"S(S)")
580 RETURN
599 REM VALUE
600 LET S=S+1
610 LET S(S)=VAL W$
620 RETURN
649 REM GOSUB BASIC SUBROUTINE
650 GOSUB D(J)
660 RETURN
1499 REM STOP . CLS ? ,
1500 STOP
1501 RETURN
1505 IF S<1 THEN GOTO 9990
1506 PRINT S(S)
1507 LET S=S-1
1508 RETURN
1510 CLS
1511 RETURN
1525 PRINT "COMMANDS"
1526 FOR I=1 TO D
1527 PRINT D$(I)
1528 NEXT I
1529 RETURN
1530 IF S>0 THEN PRINT S(S)
1531 RETURN
9989 REM ERROR DETECTED
9990 PRINT "? ";W$
9991 RETURNListing 2. RPN Calculator.
1 REM RPN CALCULATOR
50 REM DEFINITIONS
51 LET D$(5)="DUP"
52 LET D(5)=5000
53 LET D$(6)="SWAP"
54 LET D(6)=5100
55 LET D$(7)="ROT6"
56 LET D(7)=5200
57 LET D$(8)="STA5"
58 LET D(8)=5300
90 LET D=9
4999 REM DUP
5000 IF S<1 THEN GOTO 9990
5010 LET S=S+1
5020 LET S(S)=S(S-1)
5030 RETURN
5099 REM SWAP
5100 IF S<2 THEN GOTO 9990
5110 LET TMP=S(S)
5120 LET S(S)=S(S-1)
5130 LET S(S-1)=TMP
5140 RETURN
5199 REM ROTATE
5200 IF S<2 THEN RETURN
5210 LET TMP=S(S)
5220 FOR I=S TO 2 STEP -1
5230 LET S(I)=S(I-1)
5240 NEXT I
5250 LET S(1)=TMP
5260 RETURN
5299 REM STACK
5300 FOR I=S TO 1 STEP -1
5310 PRINT S(I);" ";
5320 NEXT I
5330 PRINT
5340 RETURNNote: Type-in program listings on this website use ZMAKEBAS notation for graphics characters.