This website does readability filtering of other pages. All styles, scripts, forms and ads are stripped. If you want your website excluded or have other feedback, use this form.

Design Notes

DESIGN NOTES FOR TINY BASIC


by Dennis Allison, happy Lady, & friends
(reprinted from People's Computer Company Vol. 4, No. 2)

SOME MOTIVATIONS

A lot of people have just gotten into having their own computer. Often they don't know too much about software and particularly systems software, but would like to be able to program in something other than machine language. The TINY BASIC project is aimed at you if you are one of these people. Our goals are very limited -- to provide a minimal BASIC-like language for writing simple programs. Later we may make it more complicated, but now the name of the game is keep it simple. That translates to a limited language (no floating point, no sines and cosines, no arrays, etc.) and even this is a pretty difficult undertaking.

Originally we had planned to limit ourselves to the 8080, but with a variety of new machines appearing at very low prices, we have decided to try to make a portable TINY BASIC system even at the cost of some efficiency. Most of the language processor will be written in a pseudo language which is good for writing interpreters like TINY BASIC. This pseudo language (which interprets TINY BASIC) will then itself be implemented interpretively. To implement TINY BASIC on a new machine, one simply writes a simple interpreter for this pseudo language and not a whole interpreter for TINY BASIC.

We'd like this to be a participatory design project. This sequence of design notes follows the project which we are doing here at PCC. There may well be errors in content and concept. If you're making a BASIC along with us, we'd appreciate your help and your corrections.

Incidentally, were we building a production interpreter or compiler, we would probably structure the whole system quite differently. We chose this scheme because it is easy for people to change without access to specialized tools like parser generator programs

THE TINY BASIC LANGUAGE

There isn't much to it. TINY BASIC looks like BASIC but all variables are integers. There are no functions yet (we plan to add RND, TAB, and some others later) - Statement numbers must be between 1 and 256 so we can store them in a single byte. LIST only works on the whole program. There is no FOR-NEXT statement. We've tried to simplify the language to the point where it will I fit into a very small memory so impecunious, tyros can use the system.

The boxes shown define the language. The guide gives a quick reference to what we will include. The formal grammar defines exactly what is a legal TINY BASIC statement. The grammar is important because our interpreter design will be based upon it

IT'S ALL DONE WITH MIRRORS---OR HOW TINY BASIC WORKS

All the variables in TINY BASIC: the control information as to which statement is presently being executed and how the next statement is to be found, the return addresses of active GOSUBS -- all this information constitutes the state of the TINY BASIC interpreter.

There are several procedures which act upon this state. One procedure knows how to execute any TINY BASIC statement. Given the starting point in memory of a TINY BASIC statement, it will execute it changing the state of the machine as required. For example,

100 LET S = A+6
would change the value of S to the sum of the contents of the variable A and the integer 6, and sets the next line counter to whatever line follows 100, if the line exists.

A second procedure really controls the interpretation process by telling the line interpreter what to do. When TINY BASIC is loaded, this control routine performs some initialization, and then attempts to read a line of information from the console. The characters typed in are saved in a buffer, LBUF. It first checks to see if there is a leading line number. If there is, it incorporates the line into the program by first deleting the line with the same line number (if it is present) then inserting the new line if it is of nonzero length. If there is no line number present, it attempts to execute the line directly. With this strategy, all possible Commands, even LIST and CLEAR and RUN are possible inside programs. Suicidal programs are also certainly possible.


TINY BASIC GRAMMAR

The things in bold face stand for themselves. The names in lower case represent classes of things. '::=' is read 'is defined as'. The asterisk denotes zero or more occurances of the object to its immediate left. Parenthesis group objects. e is the empty set. | denotes the alternative (the exclusive-or).
line::= number statement   | statement  statement::=  PRINT expr-list IF expression relop expression THEN statement GOTO expression INPUT var-list LET var = expression GOSUB expression RETURN CLEAR LIST RUN END expr-list::= (string | expression) (, (string | expression) )*
var-list::= var (, var)*
expression::= (+ | - | e) term ((+ | -) term)*
term::= factor ((* | /) factor)*
factor::= var | number | (expression)
var::= A | B | C ..., | Y | Z
number::= digit digit*
digit::= 0 | 1 | 2  | ...  | 8 | 9
relop::= < (> | = | e) | > (< | = | e) | =

A BREAK from the console will interrupt execution of the program.


IMPLEMENTATION STRATEGIES AND ONIONS

When you write a program in TINY BASIC there is an abethect machine Which is necessary to execute it. If you had a compiler it would make in the machine language of your computer a program which emulates that abstract machine for your program. An interpreter implements the abstract machine for the entire language and rather than translating the program once to machine code it translates it dynamically as needed. Interpreters are programs and as such have their's as abstract machines. One can find a better instruction set than that of any general purpose computer for writing a particular interpreter. Then one can write an interpreter to interpret the instructions of the interpreter which is interpreting the TINY BASIC program. And if your machine is micro-programmed (like PACE), the machine which is interpreting the interpreter interpreting the interpreter interpreting BASIC is in fact interpreted.

This multilayered, onion-like approach gains two things: the interpreter for the interpreter is smaller and simpler to write then an interpreter for all of TINY BASIC, so the resultant system is fairly portable. Secondly, since the main part of the TINY BASIC is programmed in a highly memory efficient, tailored instruction set, the interpreted TINY BASIC will be smaller than direct coding would allow. The cost is in execution speed, but there is not such a thing as a free lunch.


QUICK REFERENCE GUIDE FOR TINY BASIC

LINE FORMAT AND EDITING

* Lines without numbers executed immediately
* Lines with numbers appended to program
* Line numbers must be 1 to 255
* Line number alone (empty line) deletes line
* Blanks are not significant, but key words must contain no unneeded blanks
* '¨' deletes last character
* Xc deletes the entire line

EXECUTION CONTROL

CLEAR delete all lines and data
RUN run program
LIST list program

EXPRESSIONS

Operators Arithmetic + - * / Relational > >= < <= = <>, >< Variables
A...Z (26 only) All arithmetic is modulo 215
(+/- 32767)

INPUT / OUTPUT

PRINT X,Y,Z
PRINT 'A STRING'
PRINT 'THE ANSWER IS'
INPUT X
INPUT X,Y,Z

ASSIGNMENT STATEMENTS

LET X=3
LET X= -3+5*Y

CONTROL STATEMENTS

GOTO X+10
GOTO 35
GOSUB X+35
GOSUB 50
RETURN

IF X > Y THEN GOTO 30


LINE STORAGE

The TINY BASIC program is stored, except for line numbers, just as it is entered from the console. In some BASIC interpreters, the program is translated into an intermediate form which speeds execution and saves space. In the TINY BASIC environment, the code necessary to provide the transformation would easily exceed the space saved.

When a line is read in from the console device, it is saved in a 72-byte array called LBUF (Line BUFfer). At the same time, a pointer, CP, is maintained to indicate the next available space in LBUF. Indexing is, of course, from zero.

Delete the leading blanks. If the string matches the BASIC line, advance the cursor over the matched string and execute the next IL instruction. If the match fails, continue at the IL instruction labeled lbl.

The TINY BASIC program is stored as an array called PGM in order of increasing line numbers. A pointer, PGP, indicates the first free place, in the array. PGP=0 indicates an empty program; PGP must be less than the dimenstion of the array PGM. The PGM array must be reorganized when new lines are added, lines replaced, or lines we deleted.

Insertion and deletion are carried on simultaneously. When a new line is to be entered, the PGM array searches for a line with a line number greater than or equal to that of the new line. Notice that lines begin at PGM (0) and at PGM (j+1) for every j such that PGM (j)=[carriage return]. If the line numbers are equal, then the length of the existing line is computed. A space equal to the length of the new line is created by moving all lines with line numbers greater than that of the line being inserted up or down as appropriate. The empty line is handled as a special case in that no insertion is made.

TINY BASIC AS STORED IN MEMORY

byte in memory treated as an integer
                           byte treated as a character

a carriage return symbol                        free space
 

ERRORS AND ERROR RECOVERY

There are two places that errors can occur. If they occur in the TINY BASIC system, they must be captured and action taken to preserve the system. If the error occurs in the TINY BASIC program entered by the user, the system should report the error and allow the user to fix his problem. An error in TINY BASIC can result from a badly formed statement, an illegal action (attempt to divide by zero, for example), or the exhaustion of some resource such as memory space. In any case, the desired response is some kind of error message. We plan to provide a message of the form:
!mmm AT nnn
where mmm is the error number and nnn is the line number at which it occurs. For direct statements, the form will be:
!mmm
since there is no line number.

Some error indications we know we will need are:

1 Syntax error 5 RETURN without GOSUB 2 Missing line 6 Expression too complex 3 Line number too large 7 Too many lines 4 Too many GOSUBs 8 Division by zero

THE BASIC LINE EXECUTOR

The execution routine is written in the interpretive language, IL. It consists of a sequence of instructions which may call subroutines written in IL, or invoke special instructions which are really subroutines written in machine language.

Two different things are going on at the same time. The routines must determine if the TINY BASIC line is a legal one and determine its form according to the grammar; secondly, it must call appropriate action routines to execute the line. Consider the TINY BASIC statement:

GOTO 100
At the start of the line, the interpreter looks for BASIC key words (LET, GO, IF, RETURN, etc.) In this case, it finds GO, and then finds TO. By this time it knows that it has found a GOTO statement. It then calls the routine EXPR to obtain the destination line number of the GOTO. The expression routine calls a whole bunch of other routines, eventually leaving the number 100 (the value of the expression) in a special place, the top of the arithmetic expression stack. Since everything is legal, the XFER operator is invoked to arrange for the execution of line 100 (if it exists) as the next line to be executed.

Each TINY BASIC statement is handled similarly. Some procedural section of an IL program corresponds to tests for the statement structure and acts to execute the statement.

ENCODING

There are a number of different considerations in the TINY BASIC design which fall in this general category. The problem is to make efficient use of the bits available to store information without losing out by requiring a too complex decoding scheme.

In a number of places we have to indicate the end of a string of characters (or else we have to provide for its length somewhere). Commonly, one uses a special character (NUL = OOH for example) to indicate the end. This costs one byte per string but is easy to check. A better way depends upon the fact that ASCII code does not use the high order bit; normally it is used for parity on transmission. We can use it to indicate the end (that is, last character) of a string. When we process the characters we must AND the character with 07FH to scrub off the flag bit.

The interpreter opcodes can be encoded into a single byte. Operations fall into two distinct classes -- those which call machine language subroutines, and those which either call or transfer within the IL language itself. The diagram indicates one encoding scheme. The CALL operations have been subsumed into the IL instruction set. Addressing is shown to be relative to PC for IL operations. Given the current IL program size, this seems adequate. If it is not, the address could be used to index an array with the ML class instructions.

ONE POTENTIAL IL ENCODING


 
 

TINY BASIC INTERPRETIVE OPERATIONS

TST lbl,'string'  delete leading blanks
If string matches the BASIC line, advance cursor over the
matched string and execute the next IL instruction If a match fails, 
execute the IL instruction at the labled lbl. CALL lbl Execute the IL subroutine starting at lbl. Sawe the IL 
address following the CALL on the control stack. RTN Return to the IL location specified by the top of the control stack. DONE Report a syntax error if after deletion leading blanks the 
cursor is not positioned to road a carriage return. JMP lbl Continue execution of IL at the line specified. PRS Print characters from the BASIC text up to but not including the 
closing quote mark. If a cr is found in the program text, report an 
error. Move the cursor to the point following the closing quote. PRN Print number obtained by popping the top of the expression stack. SPC Insert spaces, to move the print head to next zone. NLINE Output CRLF to Printer. NXT If the present mode is direct (line number zero), then return to line 
collection. Otherwise, select the next line and begin interpretation. XFER Test valiue at the top of the AE stack to be within range. If not, 
report an error. If so, attempt to position cursor at that line. 
If it exists, begin interpretation there; if not report an error. SAV Push present line number on SBRSTK. Report overflow as error. RSTR Replace current line number with value on SBRSTK. 
If stack is empty, report error. CMPR Compare AESTK(SP), the top of the stack, with AESTK(SP-2) 
as per the relations indicated by AESTK(SP-1). Delete all from stack. 
If the condition specified did not match, then perform NXT action. LIT num Push the number num onto the AESTK (Originally omitted) INNUM Read a number from the terminal and push its value onto the AESTK.  FIN Return to the line collect routine. ERR Report syntax error am return to line collect routine. ADD Replace top two elements of AESTK by their sum. SUB Replace top two elements of AESTK by their difference. NEG Replace top of AESTK with its neqative. MUL Replace top two elements of AESTK by their product. DIV Replace top two elements of AESTK by their quotient. STORE Place the value at the top of the AESTK into the variable 
designated by the index specified by the value immediately 
below it. Delete both from the stack. TSTV lbl Test for variable (i.e letter) if present. Place its index value 
onto the AESTK and continue execution at next suggested 
location. Otherwise continue at lbl. TSTN lbl  Test for number. Of present, place its value onto the AESTK and 
continue execution at next suggested location. Otherwise continue at lbl. IND Replace top of stack by variable value it indexes. LST List the contents of the program area. INIT Perform global initilization
Clears program area, empties GOSUB stack, etc. GETLINE Input a line to LBUF. TSTL lbl After editing leading blanks, look for a line number. Report error 
if invalid; transfer to lbl if not present. INSRT Insert line after deleting any line with same line number. XINIT Perform initialization for each stated execution. Empties AEXP stack.

A STATEMENT EXECUTOR WRITTEN IN IL

This program in IL will execute a TINY BASIC statement. The operators TST, TSTV, TSTN, and PRS all use a cursor to find characters of the TINY BASIC line. Other operations (NXT, XPER) move the cursor so it points to a TINY BASIC line. [I corrected a few obvious errors, in red -- TP; Jeffrey Henning found a couple more, in green]
;THE IL CONTROL SECTION

START:  INIT                  ;INITIALIZE
        NLINE                 ;WRITE CRLF
CO:     GETLINE               ;WRITE PROMPT AND GET LINE
        TSTL    XEC           ;TEST FOR LINE NUMBER
        INSERT                ;INSERT IT (MAY BE DELETE)
        JMP     CO
XEC:    XINIT                 ;INITIALIZE

;STATEMENT EXECUTOR

STMT:   TST     S1,'LET'      ;IS STATEMENT A LET
        TSTV    S17           ;YES, PLACE VAR ADDRESS ON AESTK
        TST     S17,'='       ;(This line originally omitted)
        CALL    EXPR          ;PLACE EXPR VALUE ON AESTK
        DONE                  ;REPORT ERROR IF NOT NEXT
        STORE                 ;STORE RESULT
        NXT                   ;AND SEQUENCE TO NEXT
S1:     TST     S3,'GO'       ;GOTO OT GOSUB?
        TST     S2,'TO'       ;YES...TO, OR...SUB
        CALL    EXPR          ;GET LABEL
        DONE                  ;ERROR IF CR NOT NEXT
        XPER                  ;SET UP AND JUMP
S2:     TST     S17,'SUB'     ;ERROR IF NO MATCH
        CALL    EXPR          ;GET DESTINATION
        DONE                  ;ERROR IF CR NOT NEXT
        SAV                   ;SAVE RETURN LINE
        XPER                  ;AND JUMP
S3:     TST     S8,'PRINT'    ;PRINT
S4:     TST     S7,'"'        ;TEST FOR QUOTE
        PRS                   ;PRINT STRING
S5:     TST     S6,','        ;IS THERE MORE?
        SPC                   ;SPACE TO NEXT ZONE
        JMP     S4            ;YES JUMP BACK
S6:     DONE                  ;ERROR IF CR NOT NEXT
        NLINE
        NXT
S7:     CALL    EXPR
        PRN                   ;PRINT IT
        JMP     S5            ;IS THERE MORE?
S8:     TST     S9,'IF'       ;IF STATEMENT
        CALL    EXPR          ;GET EXPRESSION
        CALL    RELOP         ;DETERMINE OPR AND PUT ON STK
        CALL    EXPR          ;GET EXPRESSION
        TST     S17,'THEN'    ;(This line originally omitted)
        CMPR                  ;PERFORM COMPARISON -- PERFORMS NXT IF FALSE
        JMP     STMT
S9:     TST     S12,'INPUT'   ;INPUT STATEMENT
S10:    TSTV    S17           ;GET VAR ADDRESS (Originally CALL VAR = nonexist)
        INNUM                 ;MOVE NUMBER FROM TTY TO AESTK
        STORE                 ;STORE IT
        TST     S11,','       ;IS THERE MORE?
        JMP     S10           ;YES
S11:    DONE                  ;MUST BE CR
        NXT                   ;SEQUENCE TO NEXT
S12:    TST     S13,'RETURN'  ;RETURN STATEMENT
        DONE                  ;MUST BE CR
        RSTR                  ;RESTORE LINE NUMBER OF CALL
        NXT                   ;SEQUENCE TO NEXT STATEMENT
S13:    TST     S14,'END'
        FIN
S14:    TST     S15,'LIST'    ;LIST COMMAND
        DONE
        LST
        NXT
S15:    TST     S16,'RUN'     ;RUN COMMAND
        DONE
        NXT
S16:    TST     S17,'CLEAR'   ;CLEAR COMMAND
        DONE
        JMP     START

S17:    ERR                   ;SYNTAX ERROR

EXPR:   TST     E0,'-'
        CALL    TERM          ;TEST FOR UNARY -.
        NEG                   ;GET VALUE
        JMP     E1            ;NEGATE IT
E0:     TST     E1A,'+'       ;LOOK FOR MORE
E1A:    CALL    TERM          ;TEST FOR UNARY +
E1:     TST     E2,'+'        ;LEADING TERM
        CALL    TERM
        ADD
        JMP     E1
E2:     TST     E3,'-'        ;ANY MORE?
        CALL    TERM          ;DIFFERENCE TERM
        SUB
        JMP     E1
E3:T2:  RTN                   ;ANY MORE?
TERM:   CALL    FACT
TO:     TST     T1,"*"
        CALL    FACT          ;PRODUCT FACTOR.
        MUL
        JMP     T0
T1:     TST     T2,'/'
        CALL    FACT          ;QUOTIENT FACTOR.
        DIV
        JMP     T0

FACT:   TSTV    F0
        IND                   ;YES, GET THE VALUE.
        RTN
F0:     TSTN    F1            ;NUMBER, GET ITS VALUE.
        RTN
F1:     TST     F2,'('        ;PARENTHESIZED EXPR.
        CALL    EXPR
        TST     F2,')'
        RTN
F2:     ERR                   ;ERROR.

RELOP:  TST     RO,'='
        LIT     0             ;=
        RTN
R0:     TST     R4,'<'
        TST     R1,'='
        LIT     2             ;<=
        RTN
R1:     TST     R3,'>'
        LIT     3             ;<>
        RTN
R3:     LIT     1             ;<
        RTN
R4:     TST     S17,'>'
        TST     R5,'='
        LIT     5             ;>=
        RTN
R5:     TST     R6,'<'
        LIT     3
        RTN                   ;(This line originally omitted)
R6:     LIT     4
        RTN