In the fall of 1975, the People’s Computer Company (PCC) poured more energy into their “Build Your Own BASIC” project, fired up by the announcement of Altair 4K BASIC by MicroSoft [as it was then] for $150. They wanted to create an implementation that was free for anyone to use. With microcomputers and microprocessors proliferating, they envisioned a virtual machine that could be ported from platform to platform:
When you write a program in TINY BASIC there is an abstract 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 theirs 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.
“The machine … interpreting the interpreter interpreting the interpreter interpreting BASIC is in fact interpreted.” These guys were having fun! Geeky fun, but fun.
While writing compilers was just being generalized (lex and yacc were published circa 1975), PCC recognized that hobbyists wouldn’t have access to these new tools. Writing a parser is a very specific domain. Accordingly, they created a simple language, IL (Interpretive Language), to write their Tiny BASIC in and encode the parsing in.
Let’s look at a representative example:
S1: TST S3,'GO' ;GOTO OR GOSUB?
TST S2,'TO' ;YES...TO, OR...SUB
CALL EXPR ;GET LABEL
DONE ;ERROR IF CR NOT NEXT
XFER ;SET UP AND JUMP
A common pattern in IL is to test for a keyword or token, then act on that information. Each test is an assertion as to what is next in the line buffer. If the assertion fails, control jumps to a subsequent label (usually looking for a new keyword or token). Here the system advances its buffer cursor over any spaces and tests for “GO” and if it fails to find it then jumps to line “S3”. If it finds it, execution continues with the next IL command. In this case, the system next tests for “TO”, skipping to line “S2” if it fails (a test for “SUB”, to see if this is instead a GOSUB command). If it passes, control continues; in this case, calling an IL subroutine that starts at label “EXPR”, which parses an expression. In Tiny BASIC, “GOTO X*10+100” (a computed GO TO) is as legal as “GOTO 100” and is the alternative to the ON-GOTO of larger BASIC implementations. The subroutine “EXPR” pushes the result of the expression onto the arithmetic stack (in this case, the line number). “DONE” verifies no other text follows the expression and gives an error if it does. “XFER” pops the number of the stack and transfers (GOTOs) the corresponding line number, if it exists.
The IL listing was concise: just 124 lines long! Just 124 lines to implement a workable BASIC that you can write programs and even games in. It’s very elegant.
IL is simple enough that I thought I could program it in a high-level language in an evening. (It took two, plus another to debug.) I wrote a two-pass assembler from the specs, implementing each command. Then I assembled the program, using the listing that Tom Pittman had shared and corrected a few errors in. As far I can tell, I’m the first person to actually write an IL assembler in the 42 years the language has been around. (Tom had his own version of the IL: he changed the mnemonics to two characters each, to be easier to parse on a microcomputer, and modified some commands, and added others.)
I encountered three different types of problems.
The first class of problems were mental mistakes in the listing and the spec:
- “CALL VAR” needed to be “TSTV S17”, as the listing has no VAR routine but does have a built-in command to test a variable.
- The use of “MPY” in the listing for the “MUL” command (all five math functions in IL are the first three letters of their corresponding word: ADDition, SUBtraction, MULtiplication, DIVision, NEGation).
- The language specification neglected to define “LIT”, which pushes the following byte onto the arithmetic stack.
The second problem was that the language hardcodes jumps: for instance, “DONE” jumps to the third instruction (label “CO”). For what is essentially a finite state machine, I found this to be pretty insufferable. In my implementation, I changed commands to take their destination label. (In defense of PCC, they had to worry about carefully managing 4KB of RAM. I have 16GB: 4 million times more.) I later discovered that Tom Pittman changed “DONE” to “BE” (“Branch if Not Endline”) with a label as his solution to this issue.
The third problem with the program was subtler, and escaped my notice at first. Typically, “RUN” resets all variables (in this case, the 26 variables A to Z) to zero. There’s nowhere for that to happen in the listing. You could do this programmatically in IL:
1
0
STORE
2
0
STORE
…
26
0
STORE
However, 78 added instructions to a listing of 124 instructions (not counting comments) seemed excessive.
Sadly, while IL uses a stack machine, it doesn’t provide any way to actually manipulate the stack: no DUP, no SWAP, no conditional jump based on the top of the stack. If it had, the following would have been possible:
LIT 26 ; START AT THE 26TH VARIABLE
VINIT: DUP ; DUPLICATE THE TOP OF THE STACK
LIT 0 ; PUSH 0
STORE ; STORE 0 INTO THE VARIABLE
LIT 1 ; PUSH 1
SUB ; SUBTRACT 1 FROM THE VARIABLE INDEX
DUP ; DUPLICATE
JMPC VINIT ; JUMP IF NOT 0
So I implemented a VINIT keyword to do this instead.
Tom Pittman notes:
The TINY BASIC interpreter was designed by Dennis Allison as a Recursive Descent parser. Some of the elegant simplicity of this design was lost in the addition of syntactical sugar to the language but the basic form remains. The IL is especially suited to Recursive Descent parsing of TINY BASIC because of the general recursive nature of its procedures and the simplicity of the TINY BASIC tokens. The IL language is effectively optimized for the interpretation of TINY. Experience has shown that the difficulty of adding new features to the language is all out of proportion with the nature of the features. Usually it is necessary to add additional machine language subroutines to support the new features. Often the difficulty outweighs the advantages.
This is from The Tiny BASIC Experimenter’s Kit that he wrote 40 years ago. It is well worth reading in detail, as his is the only Tiny BASIC implementation to use an IL. (The first Tiny BASIC, TBX, used the IL as pseudocode for the outline of the machine language program.)
Here are additions I made to the IL to extend my own Tiny BASIC:
- I added a single array A(), a la Palo Alto Tiny BASIC’s @(), which can take a subscript from 0 to 255. (But note that subscripts of 230 to 255 map to the values of variables A to Z, since I use the “IND” operator to reference variables.)
- I added RND(X), which returns a pseudorandom number from 1 to X.
- I added ASC(“A”), which can take as an argument “A” to “Z” and returns the ASCII value from 65 to 90. (This limitation is because it uses the TSTV function as a test for a letter of the alphabet.) I added this because I extended INPUT A to return the ASCII value of the first character if a number is not entered. This is so that rather than “1 FOR YES OR 2 FOR NO” you can write “(Y)ES OR (N)O” and IF A=ASC(“Y”) THEN.
If you have an iPhone, you can download the free version of LowRes Coder and use my Tiny BASIC on your phone.
Whatever its merits as a language, IL helped inspire a proliferation of BASICs to compete with Microsoft. There was Tiny BASIC Extended , Denver Tiny BASIC, 6800 Tiny BASIC, MINOL, Palo Alto Tiny BASIC, Integer BASIC, and Micro Basic. Palo Alto Tiny BASIC became the basis of TRS-80 Level I BASIC, which launched the TRS-80. Of course, Microsoft BASIC ultimately triumphed, replacing Integer BASIC on the Apple, Level I BASIC on the TRS-80, and being the only BASIC for the Commodore PET. And even today you can buy a Microsoft BASIC for your own use, as part of Visual Studio. Yet IL remains an important landmark in the history of personal computing.
Modified Tiny BASIC IL Listing
;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
;
;STATEMENT EXECUTOR
XEC: XINIT ;INITIALIZE
STMT: TST S1,'LET' ;IS STATEMENT A LET
TST S1A,'A('
CALL EXPR
TST SYN,')'
JMP S1B
S1A: TSTV SYN ;YES, PLACE VAR ADDRESS ON AESTK
S1B: TST SYN,'=' ;(THIS LINE ORIGINALLY OMITTED)
CALL EXPR ;PLACE EXPR VALUE ON AESTK
DONE SYN ;REPORT ERROR IF NOT NEXT
STORE ;STORE RESULT
NXT STMT ;AND SEQUENCE TO NEXT
S1: TST S3,'GO' ;GOTO OR GOSUB?
TST S2,'TO' ;YES...TO, OR...SUB
CALL EXPR ;GET LABEL
DONE SYN ;ERROR IF CR NOT NEXT
XFER STMT ;SET UP AND JUMP
S2: TST SYN,'SUB' ;ERROR IF NO MATCH
CALL EXPR ;GET DESTINATION
DONE SYN ;ERROR IF CR NOT NEXT
SAV ;SAVE RETURN LINE
XFER STMT ;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 SYN ;ERROR IF CR NOT NEXT
NLINE
NXT STMT
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 SYN,'THEN' ;TEST FOR THEN
CMPR STMT ;COMPARE -- PERFORMS NXT IF FALSE
JMP STMT
S9: TST S12,'INPUT' ;INPUT STATEMENT
S10: TSTV SYN ;YES, PLACE VAR ADDRESS ON AESTK
INNUM ;MOVE NUMBER FROM TTY TO AESTK
STORE ;STORE IT
TST S11,',' ;IS THERE MORE?
JMP S10 ;YES
S11: DONE SYN ;MUST BE CR
NXT STMT ;SEQUENCE TO NEXT
S12: TST S13,'RETURN' ;RETURN STATEMENT
DONE SYN ;MUST BE CR
RSTR ;RESTORE LINE NUMBER OF CALL
NXT STMT ;SEQUENCE TO NEXT STATEMENT
S13: TST S14,'END'
FIN CO
S14: TST S14A,'LIST' ;LIST COMMAND
DONE SYN
LST
NXT STMT
S14A: TST S15,'LLIST'
DONE SYN
LLST
NXT STMT
S15: TST S16,'RUN' ;RUN COMMAND
DONE SYN
VINIT ;(NEW COMMAND TO CLEAR VARIABLES)
LIT 1 ;(NEED TO TRANSFER TO FIRST LINE OF PROGRAM)
XFER STMT ;(XFER MODIFIED TO FIND NEXT HIGHER LINE # RATHER THAN PRODUCE AN ERROR)
S16: TST SYN,'CLEAR' ;CLEAR COMMAND
DONE SYN
JMP START
SYN: ERR CO ;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: RTN ;ANY MORE?
TERM: CALL FACT
T0: TST T1,'*'
CALL FACT ;PRODUCT FACTOR.
MUL
JMP T0
T1: TST E3,'/'
CALL FACT ;QUOTIENT FACTOR.
DIV
JMP T0
FACT: TST F01,'RND(' ;(ADDED RND(X) FUNCTION WHERE X>1)
CALL EXPR ;***
TST SYN,')' ;***
RND ;(ADDED RND COMMAND TO PUSH # ON AESTK)
RTN ;***
F01: TST F0A,'ASC('' ;(ADDED ASC("A") FUNCTION)
TSTV SYN ;***
TST SYN,'')' ;***
LIT 166 ;(A = 231 IN MEMORY SCHEME)
SUB ;(REDUCE BACK TO 65 TO 90)
RTN ;***
F0A: TST F0B,'A(' ;(ADDED 1 BUILT-IN ARRAY)
CALL EXPR ;***
TST SYN,')' ;***
IND ;(CHANGED IND TO SUPPORT 0 TO 255)
RTN ;***
F0B: 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 CO ;ERROR.
RELOP: TST R0,'=' ; 0, =; 1, <; 2, <=; 3, <>; 4, >; 5, >=
LIT 0 ;=
RTN
R0: TST R4,'<'
TST R1,'='
LIT 2 ;<=
RTN
R1: TST R3,'>'
LIT 3 ;<>
RTN
R3: LIT 1 ;<
RTN
R4: TST SYN,'>'
TST R5,'='
LIT 5 ;>=
RTN
R5: TST R6,'<'
LIT 3 ; ><
RTN ;(THIS LINE ORIGINALLY OMITTED)
R6: LIT 4 ; >
RTN
EOF: ;(ENDS INPUT)
