Editing Tiny BASIC (section)

==Description==
===Basic concepts===
{{See also|BASIC interpreter#Compilers vs. interpreters|l1=BASIC interpreters}}

Tiny BASIC was designed to use as little memory as possible, and this is reflected in the paucity of features as well as details of its [[BASIC interpreter|interpreter system]]. Early microcomputers lacked the RAM and [[secondary storage]] for a BASIC [[compiler]], which was more typical of timesharing systems.

Like most BASICs of the era, Tiny Basic was interactive with the user typing statements into a command line. As microcomputers of the era were often used with teletype machines or "dumb" terminals, direct editing of existing text was not possible and the editor instead used takeout characters, often the backslash, to indicate where the user backed up to edit existing text.

If the user typed a statement into the command line the system examined it to see if it started with a number. If it did not, the line was immediately parsed and operated on, potentially generating output via {{code|PRINT}}. This was known as "direct mode".

If the line was entered with a leading number, the number was converted from decimal format, like "50", and converted to a 8-bit value, in this case, {{code|$32}} [[hexadecimal]]. This number was used as an index into an [[array]]-like storage area where the rest of the line was stored in exactly the format it was typed. When the user typed {{code|LIST}} into the command line the system would loop over the array, convert the line number back to decimal format, and then print out the rest of the text in the line.

When a program was present in memory and the user types in the {{code|RUN}} command, the system enters "indirect mode". In this mode, a pointer is set to point to the first line of the program, for instance, 10 ({{mono|{{#invoke:BaseConvert|10to16|10|width=2|prefix=$|suffix={{sub|hex}}}}}}). The original text for that line is then retrieved from the store and run as if the user had just typed it in direct mode. The pointer then advances to the next line and the process continues.

===Formal grammar===
The grammar is listed below in [[Backus–Naur form]], almost exactly as it was specified in the Design Note.<ref>{{cite magazine |title=Build Your Own BASIC |first=Dennis |last=Allison |magazine=Dr. Dobb's Journal |volume=1 |number=1 |date=1976 |url=https://archive.org/details/dr_dobbs_journal_vol_01/page/n9 |page=9}}</ref> In the listing, an asterisk ("<code>*</code>") denotes zero or more of the object to its left{{snd}} except for the first asterisk in the definition of "<code>term</code>", which is the multiplication operator; parentheses group objects; and an epsilon ("<code>ε</code>") signifies the empty string. As is common in computer language grammar notation, the vertical bar ("<code>|</code>") distinguishes alternatives, as does their being listed on separate lines. The symbol "<code>CR</code>" denotes a [[carriage return]] (usually generated by a keyboard's "Enter" key). A BREAK from the console will interrupt execution of the program.
<!-- Note: there might be some typos in the listing, which IIRC is an exact copy of the DrD original. A correction of those errors would have to be shown with (foot)notes, so that the reader will be presented with the original text as printed in the DrD. --Wernher        -->
<syntaxhighlight lang="abnf">
    line ::= number statement CR | statement CR
 
    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 ::= (+|-|ε) term ((+|-) term)*
 
    term ::= factor ((*|/) factor)*
 
    factor ::= var | number | (expression)
 
    var ::= A | B | C ... | Y | Z
 
    number ::= digit digit*
 
    digit ::= 0 | 1 | 2 | 3 | ... | 8 | 9
 
    relop ::= < (>|=|ε) | > (<|=|ε) | =

    string ::= " ( |!|#|$ ... -|.|/|digit|: ... @|A|B|C ... |X|Y|Z)* "
</syntaxhighlight>

Note that string wasn't defined in the Design Note.

This syntax, as simple as it was, added one innovation: {{code|GOTO}} and {{code|GOSUB}} could take an expression rather than just a line number, providing an [[Goto#Computed GOTO and Assigned GOTO|assigned GOTO]]<ref>{{cite magazine |title=Quick Reference Guide for Tiny BASIC |first=Dennis |last=Allison |magazine=Dr. Dobb's Journal |volume=1 |number=1 |date=1976 |url=https://archive.org/details/dr_dobbs_journal_vol_01/page/n6 |page=6}}</ref> rather than the [[switch statement]] of the {{code|GOTO/GOSUB ... OF ...}}, a structure then supported in [[HP Time-Shared BASIC]] and predating {{code|ON ... GOTO}}. The syntax allowing {{code|IF-THEN statement}} (as opposed to just a line number to branch to) was not yet supported in Dartmouth BASIC at this time but had been introduced by Digital<ref>{{cite book|url=https://archive.org/details/bitsavers_decpdp11rsSICPLUSLangManOct72_10455777|title=BASIC-PLUS Language Manual|publisher=Digital Equipment Corporation|year=1972|location=Maynard, Massachusetts|type=PDF|pages=3–13|ref=CITEREFPLUS1972}}</ref> and copied by Microsoft.

===Implementation in a virtual machine===
The Design Note specified a [[virtual machine]], in which the Tiny BASIC [[interpreter (computing)|interpreter]] is itself run on a virtual machine interpreter. The designer's idea to use an application virtual machine goes back to Val Schorre (with [[META II]], 1964) and Glennie (Syntax Machine). The choice of a virtual machine approach economized on memory space and implementation effort, although the BASIC programs run thereon were executed somewhat slowly.<ref>{{cite journal|last1=Allen|first1=Dennis|title=TINY BASIC|journal=People's Computer Company|volume= 4|issue= 3}}</ref>

Dialects that used the virtual machine included Tiny BASIC Extended, [[Tom Pittman (computer scientist)|Tom Pittman]]'s Tiny BASIC<ref>{{cite web|last1=Veit|first1=Holger|title=Tom Pittman's 6800 tiny BASIC|url=http://www.ittybittycomputers.com/IttyBitty/TinyBasic/TB_6800.asm|access-date=2 May 2017}}</ref> and NIBL. Other dialects such as Denver Tiny BASIC (DTB) and Palo Alto Tiny BASIC were direct interpreters. Some programmers, such as Fred Greeb with DTB, treated the IL (Interpretive Language) program as [[pseudocode]] for the [[algorithm]] to implement in assembly language; Denver Tiny BASIC did not use a virtual machine, but it did closely follow the IL program.

This is a representative excerpt from the 120-line IL program:
<syntaxhighlight lang="nasm">
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
S3:  TST     S8,'PRINT'    ;PRINT.
</syntaxhighlight>

A common pattern in the program is to test for a keyword or part of a keyword, 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 {{mono|GO}} and if it fails to find it then jumps to line {{mono|S3}}. If it finds it, execution continues with the next IL command. In this case, the system next tests for {{mono|TO}}, skipping to line {{mono|S2}} if it fails (a test for {{mono|SUB}}, to see if this is instead a {{mono|GOSUB}} command). If it passes, control continues; in this case, calling an IL subroutine that starts at label {{mono|EXPR}}, which parses an expression. In Tiny BASIC, {{code|GOTO X*10+100}} (a computed GO TO) is as legal as {{code|GOTO 100}} and is the alternative to the ON-GOTO of larger BASIC implementations. The subroutine {{mono|EXPR}} pushes the result of the expression onto the arithmetic stack (in this case, the line number). {{mono|DONE}} verifies no other text follows the expression and gives an error if it does. {{mono|XFER}} pops the number from the stack and transfers execution (GOes TO) the corresponding line number, if it exists.

The following table gives a partial list of the 32 commands of the virtual machine in which the first Tiny BASIC interpreter was written.<ref>''Dr. Dobb's Journal'', Volume 1, Number 1, 1976, p.&nbsp;12.</ref> 
; {{mono|TST ''lbl'', ''string''}}
: If ''string'' matches the BASIC line, advance cursor over {{mono|''string''}} and execute the next IL instruction; if the test fails, execute the IL instruction at the label ''lbl''
; {{mono|CALL ''lbl''}} : Execute the IL subroutine starting at {{mono|''lbl''}}; save the IL address following the CALL on the control stack
; {{mono|DONE}} : Report a syntax error if after deleting leading blanks the cursor is not positioned to reach a carriage return
; {{mono|XFER}} : Test value 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. 
; {{mono|JUMP ''lbl''}} : Continue execution of the IL at the label specified
; {{mono|RTN}} : Return to the IL location specified at the top of the control stack
; {{mono|PRS}} : Print characters from the BASIC text up to but not including the closing quotation mark
; {{mono|PRN}} : Print number obtained by popping the top of the expression stack
; {{mono|SPC}} : Insert spaces to move the print head to next zone
; {{mono|NLINE}} : Output a CRLF<ref>The <code>CRLF</code> there symbolizes a carriage return followed by a [[line feed]].</ref> to the printer

[[Tom Pittman (computer scientist)|Tom Pittman]], discussing the IL, says: "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."<ref>{{cite web| url=http://www.ittybittycomputers.com/IttyBitty/TinyBasic/TBEK.txt | title=Tiny BASIC Experimenter's Kit | last=Pittman | first=Tom | access-date=August 9, 2020}}</ref>

===Deviations from the design===
Defining Tiny BASIC for the Homebrew Computer Club, Pittman wrote, "Tiny BASIC is a proper subset of Dartmouth BASIC, consisting of the following statement types only: LET, PRINT, INPUT, IF, GOTO, GOSUB, RETURN, END, CLEAR, LIST, RUN. Arithmetic is in 16-bit integers only with the operators + - * / and nested parentheses. There are only the 26 single letter variable names A, B, ...Z, and no functions. There are no strings or arrays... Tiny BASIC specifies line numbers less than 256."<ref>{{cite web|url=https://archive.computerhistory.org/resources/access/text/2015/02/102740021-05-14-acc.pdf |archive-url=https://ghostarchive.org/archive/20221009/https://archive.computerhistory.org/resources/access/text/2015/02/102740021-05-14-acc.pdf |archive-date=2022-10-09 |url-status=live| title= TINY BASIC 6800 |access-date=13 Aug 2020}}</ref> He then went on to describe his implementation: "This language has been augmented to include the functions RND, USR, and PEEK and POKE, giving the user access to all his system components in the 6800 from the BASIC program."

Many implementers brought their own experiences with [[HP Time-Shared BASIC]] or [[BASIC-PLUS|DEC BASIC-PLUS]] to their designs and relaxed the formal Tiny BASIC language specification. Of the seven prominent implementations published by 1977:
* All added some sort of random number function, typically {{code|RND()}}. Though not included in the specification, a newsletter article prior to the Design Note for Tiny BASIC requested only this function.
* All enabled {{code|LET}} to be optional and most let expressions in assignment statements contain [[relational operators]].
* All but 6800TB supported statement delimiters in lines, typically {{code|:}} although TBX used {{code|$}} and PATB used {{code|;}}.
* In {{code|IF}} statements, all but MINOL removed the need for expressions to contain relational operators (e.g., {{code|2=basic|1=IF X THEN LET Y=X}} was valid). Implementations removed {{code|THEN}} altogether or made it optional or supported it only for implied {{code|GOTO}}. None supported {{code|ELSE}} clauses.
* Many modified {{code|PRINT}} to support print zones, using {{code|,}} to go to the next zone and {{code|;}} to not advance the cursor.
* All but 6800TB and DTB added {{code|NEW}}.
* All but 6800TB and MINOL added a function to return memory size: TBX had {{code|SZE}}, DTB and PATB had {{code|SIZE}}, L1B had {{code|MEM}}, and NIBL had {{code|TOP}}.
* Four implementations added arrays, whether a single, undimensioned array in PATB and L1B or {{code|DIM}}ensionable arrays in TBX and DTB.
* Four implementations added the {{code|REM}}ark statement.
* Four implementations added the {{code|FOR}} loop: PATB, NIBL, and L1B offered {{code|FOR-TO-STEP/NEXT}}, while TBX did not support {{code|STEP}} and used the keyword {{code|NXT}} to end a loop.
* Only NIBL had any nod towards structured programming, with {{code|DO/UNTIL}}, despite Allison's lament in Issue 2 about problems with BASIC.

As an alternative to tokenization, to save RAM, TBX,<ref name="Tiny BASIC Extended">{{Cite journal |journal=[[Dr. Dobb's Journal|Dr. Dobb's Journal of Computer Calisthenics & Orthodontia, Running Light Without Overbyte]] |title=Tiny BASIC Extended |volume=1 |issue=2 |date=February 1976}}</ref> DTB,<ref name="Denver Tiny BASIC">{{Cite journal |journal=[[Dr. Dobb's Journal|Dr. Dobb's Journal of Computer Calisthenics & Orthodontia, Running Light Without Overbyte]] |title=Denver Tiny BASIC |volume=1 |issue=3 |date=March 1976}}</ref> and MINOL<ref name="MINOL">{{Cite journal |journal=[[Dr. Dobb's Journal|Dr. Dobb's Journal of Computer Calisthenics & Orthodontia, Running Light Without Overbyte]] |title=MINOL |volume=1 |issue=4 |date=April 1976}}</ref> truncated keywords: {{code|PR}} for {{code|PRINT}}, {{code|IN}} for {{code|INPUT}}, {{code|RET}} for {{code|RETURN}}. The full, traditional keywords were not accepted. In contrast, PATB allowed accepted traditional keywords but also allowed any keyword to be abbreviated to its minimal unique string, with a trailing period. For instance, {{code|PRINT}} could be typed {{code|P.}}, although {{code|PR.}} and other variations also worked. This system was retained in [[Level I BASIC]] for the [[TRS-80]], which used PATB, and was also later found in [[Atari BASIC]] and the BASIC of various [[Sharp PC-1211|Sharp Pocket Computers]].<ref name=revisit>{{cite magazine |first=Roger |last=Rauskolb |title=Dr. Wang's Palo Alto Tiny BASIC |magazine=Interface Age |date=December 1976 |pages=92–108 |url=http://www.jk-quantized.com/experiments/8080Emulator/TinyBASIC-2.0.pdf |archive-url=https://ghostarchive.org/archive/20221009/http://www.jk-quantized.com/experiments/8080Emulator/TinyBASIC-2.0.pdf |archive-date=2022-10-09 |url-status=live}}</ref>