BASIC interpreter

A BASIC interpreter is an interpreter that enables users to enter and run programs in the BASIC language and was, for the first part of the microcomputer era, the default application that computers would launch. Users were expected to use the BASIC interpreter to type in programs or to load programs from storage (initially cassette tapes then floppy disks).
BASIC interpreters are of historical importance. Microsoft’s first product for sale was a BASIC interpreter (Altair BASIC), which paved the way for the company's success. Before Altair BASIC, microcomputers were sold as kits that needed to be programmed in machine code (for instance, the Apple I). During the Altair period, BASIC interpreters were sold separately, becoming the first software sold to individuals rather than to organizations; Apple BASIC was Apple's first software product. After the MITS Altair 8800, microcomputers were expected to ship bundled with BASIC interpreters of their own (e.g., the Apple II, which had multiple implementations of BASIC). A backlash against the price of Microsoft's Altair BASIC also led to early collaborative software development, for Tiny BASIC implementations in general and Palo Alto Tiny BASIC specifically.
History.
BASIC helped jumpstart the time-sharing era, became mainstream in the microcomputer era, then faded to become just another application in the DOS and GUI era, and today survives in a few niches related to game development, retrocomputing, and teaching.
Time-sharing era.
First implemented as a compile-and-go system rather than an interpreter, BASIC emerged as part of a wider movement towards time-sharing systems. General Electric, having worked on the Dartmouth Time Sharing System, wrote their own underlying operating system and launched an online time-sharing system known as Mark I featuring a BASIC compiler (not an interpreter) as one of its primary selling points. Other companies in the emerging field quickly followed suit. By the early 1970s, BASIC was largely universal on general-purpose mainframe computers.
BASIC, as a streamlined language designed with integrated line editing in mind, was naturally suited to porting to the minicomputer market, which was emerging at the same time as the time-sharing services. These machines had very small main memory, perhaps as little as 4 KB in modern terminology and lacked the high-performance storage like hard drives that make compilers practical. In contrast, an interpreter would take fewer computing resources, at the expense of performance. In 1968, Hewlett Packard introduced the HP 2000, a system that was based around its HP Time-Shared BASIC interpreter. In 1969, Dan Paymar and Ira Baxter wrote another early BASIC interpreter, for the Data General Nova. By the early 1970s, BASIC had become almost universal in the minicomputer market, with the rise of Business BASIC, and competitors to BASIC, like FOCAL and JOSS, had been forgotten.
Microcomputer era.
The introduction of the first microcomputers in the mid-1970s continued the explosive growth of BASIC, which had the advantage that it was fairly well known to the young designers and computer hobbyists who took an interest in microcomputers, many of whom had seen BASIC on minis or mainframes. BASIC was one of the few languages that was both high-level enough to be usable by those without training and small enough to fit into the microcomputers of the day. In 1972, HP introduced the HP 9830A programmable desktop calculator with a BASIC Plus interpreter in read-only memory (ROM).
In June 1974, Alfred Weaver, Michael Tindall, and Ronald Danielson of the University of Illinois at Urbana-Champaign proved it was possible to produce "A BASIC Language Interpreter for the Intel 8008 Microprocessor," in their paper of the same name, though their application was deployed to an 8008 simulator for the IBM 360/75 and required 16 KB.
In January 1975, the Altair 8800 was announced and sparked the microcomputer revolution. One of the first microcomputer versions of BASIC was co-written by Gates, Allen, and Monte Davidoff for their newly formed company, Micro-Soft. This was released by MITS in punch tape format for the Altair 8800 shortly after the machine itself, showcasing BASIC as the primary language for early microcomputers.
In March 1975, Steve Wozniak attended the first meeting of the Homebrew Computer Club and began formulating the design of his own computer. Club members were excited by Altair BASIC. Wozniak concluded that his machine would have to have a BASIC of its own. At the time he was working at Hewlett Packard and used their minicomputer dialect, HP Time-Shared BASIC, as the basis for his own version. Integer BASIC was released on cassette for the Apple I, and was supplied in ROM when the Apple II shipped in the summer of 1977.
Other members of the Homebrew Computer Club began circulating copies of Altair BASIC on paper tape, causing Gates to write his Open Letter to Hobbyists, complaining about this early example of software piracy. Partially in response to Gate's letter, and partially to make an even smaller BASIC that would run usefully on 4 KB machines, Bob Albrecht urged Dennis Allison to write their own variation of the language. How to design and implement a stripped-down version of an interpreter for the BASIC language was covered in articles by Allison in the first three quarterly issues of the "People's Computer Company" newsletter published in 1975 and implementations with source code published in "". This led to a wide variety of Tiny BASICs with added features or other improvements, with well-known versions from Tom Pittman and Li-Chen Wang, both members of the Homebrew Computer Club. Tiny BASIC was published openly and Wang coined the term "copyleft" to encourage others to copy his source code. Hobbyists and professionals created their own implementations, making Tiny BASIC an example of a free software project that existed before the free software movement.
Many firms developed BASIC interpreters. In 1976, SCELBI introduced SCELBAL for the 8008 and the University of Idaho and Lawrence Livermore Laboratory announced that they would be publishing to the public domain LLL BASIC, which included floating-point support. In 1977, the Apple II and TRS-80 Model I each had two versions of BASIC, a smaller version introduced with the initial releases of the machines and a licensed Microsoft version introduced later as interest in the platforms increased.
Microsoft ported its interpreter to the MOS 6502, which quickly became one of the most popular microprocessors of the 8-bit era. When new microcomputers began to appear, such as the Commodore PET, their manufacturers licensed a Microsoft BASIC, customized to the hardware capabilities. By 1978, MS BASIC was a "de facto" standard and practically every home computer of the 1980s included it in ROM. In 1980, as part of a larger licensing deal that included other languages and PC DOS, IBM rejected an overture from Atari and instead licensed MS-BASIC over its own implementation, eventually releasing four versions of IBM BASIC, each much larger than prior interpreters (for instance, Cartridge BASIC took 40 KB). Don Estridge, leader of the IBM PC team, said, "IBM has an excellent BASIC--it's well received, runs fast on mainframe computers, and it's a lot more functional than micro-computer BASICs... But [its] number of users were infinitesimal compared to the number of Microsoft BASIC users. Microsoft BASIC had hundreds of thousands of users around the world. How are you going to argue with that?" "(See Microsoft BASIC for the subsequent history of these different implementations.)"
Many vendors did "argue with that" and used other firms or wrote their own interpreters. In September 1978, Shepardson Microsystems was finishing Cromemco 16K Structured BASIC for the Z80-based Cromemco S-100 bus machines. Paul Laughton and Kathleen O'Brien then created Atari BASIC as essentially a pared-down version of Cromemco BASIC ported to the 6502. In 1979, Warren Robinett developed the BASIC Programming cartridge for Atari, Inc., even though it only supported programs with 9 lines of code (64 characters in total). Also in 1979, Texas Instruments released TI-BASIC with its TI-99/4, which would sell nearly 3 million systems when revamped as the TI-99/4A. Sinclair BASIC was developed for the ZX-80 by John Grant and Steve Vickers of Nine Tiles. In 1980, Sophie Wilson of Acorn Computers developed Atom BASIC, which she later evolved into BBC BASIC, one of the first interpreters to offer structured BASIC programming, with named codice_1/codice_2 procedures and functions, codice_3 loops, and codice_4 structures inspired by COMAL. Jan Jones developed SuperBASIC, another British BASIC supporting structured programming, for the Sinclair QL. In 1983, Randall Hyde developed SmartBASIC for the Coleco Adam. Richard Clayton, Chris Hall, and Paul Overell developed Mallard BASIC for the BBC Micro and Locomotive BASIC for the Amstrad CPC, both supporting commands for an ISAM indexed file system. In 1985, MetaComCo released ABasiC for the Amiga and ST BASIC for the Atari ST.
In 1978, David Lien published the first edition of "The BASIC Handbook: An Encyclopedia of the BASIC Computer Language", documenting keywords across over 78 different computers. By 1981, the second edition documented keywords from over 250 different computers, showcasing the explosive growth of the microcomputer era.
Interpreters as applications.
With the rise of disk operating systems and later graphical user interfaces, BASIC interpreters became just one application among many, rather than providing the first prompt a user might see when turning on a computer.
In 1983, the TRS-80 Model 100 portable computer debuted, with its Microsoft BASIC implementation noteworthy for two reasons. First, programs were edited using the simple text editor, TEXT, rather than typed in line by line (but line numbers were still required). Second, this was the last Microsoft product that Bill Gates developed personally.
Also in 1983, Microsoft began bundling GW-BASIC with DOS. Functionally identical to IBM BASICA, its BASIC interpreter was a fully self-contained executable and did not need the Cassette BASIC ROM found in the original IBM PC. According to Mark Jones Lorenzo, given the scope of the language, "GW-BASIC is arguably the "ne plus ultra" of Microsoft's family of line-numbered BASICs stretching back to the Altair--and perhaps even of line-numbered BASIC in general." With the release of MS-DOS 5.0, GW-BASIC's place was taken by QBasic.
MacBASIC featured a fully interactive development environment for the original Macintosh computer and was developed by Donn Denman, Marianne Hsiung, Larry Kenyon, and Bryan Stearns. MacBASIC was released as beta software in 1985 and was adopted for use in places such as the Dartmouth College computer science department, for use in an introductory programming course. It was doomed to be the second Apple-developed BASIC killed in favor of a Microsoft BASIC. In November 1985, Apple abruptly ended the project as part of a deal with Microsoft to extend the license for BASIC on the Apple II.
BASIC interpreters were not just an American/British development. In 1984, Hudson Soft released Family BASIC in the Japanese market for Nintendo's Family Computer video game console, an integer-only implementation designed for game programming, based on Hudson Soft BASIC for the Sharp MZ80 (with English keywords). Turbo-Basic XL is a compatible superset of Atari BASIC, developed by Frank Ostrowski and published in the December 1985 issue of German computer magazine "Happy Computer", making it one of the last interpreters published as a type-in program. The language included a compiler in addition to the interpreter and featured structured programming commands. Several modified versions working with different DOS systems were released by other authors. In France, François Lionet and Constantin Sotiropoulos developed two BASIC interpreters with a focus on multimedia: STOS BASIC for the Atari ST, in 1988, and AMOS BASIC for the Amiga, in 1990.
In May 1991, Microsoft released Visual Basic, a third-generation event-driven programming language known for its Component Object Model (COM) programming model. Visual Basic supported the rapid application development (RAD) of graphical user interface (GUI) applications, access to databases using Data Access Objects, Remote Data Objects, or ActiveX Data Objects, and creation of ActiveX controls and objects. Visual Basic was used to develop proprietary in-house applications as well as published applications.
Niche BASICs.
In 1993, Microsoft released Visual Basic for Applications, a scripting language for Microsoft Office applications, which supersedes and expands on the abilities of earlier application-specific macro programming languages such as Word's WordBASIC (which had been introduced in 1989).
In 1996, Microsoft released VBScript as an alternative to JavaScript for adding interactive client-side functionality to web pages viewed with Internet Explorer.
In 1999, Benoît Minisini released Gambas as an alternative for Visual Basic developers who had decided to migrate to Linux.
In 2000, Lee Bamber and Richard Vanner released DarkBASIC, a game creation system for Microsoft Windows, with accompanying IDE and development tools.
In 2001, SmallBASIC was released for the Palm PDA. Another BASIC interpreter for Palm was HotPaw BASIC, an offshoot of Chipmunk Basic.
In 2002, Emmanuel Chailloux, Pascal Manoury and Bruno Pagano published a Tiny BASIC as an example of developing applications with Objective Caml.
In 2011, Microsoft released Small Basic (distinct from SmallBASIC), together with a teaching curriculum and an introductory guide., designed to help students who have learnt visual programming languages such as Scratch learn text-based programming. The associated IDE provides a simplified programming environment with functionality such as syntax highlighting, intelligent code completion, and in-editor documentation access. The language has only 14 keywords. In 2019, Microsoft announced Small Basic Online (SBO), allowing students to run programs from a web browser.
In 2014, Robin H. Edwards released Arduino BASIC for the Arduino, and now a widely forked implementation. Another implementation using the same name was adapted from Palo Alto Tiny BASIC in 1984 by Gordon Brandly for his 68000 Tiny BASIC, later ported to C by Mike Field. 
Many BASIC interpreters are now available for smartphones and tablets via the Apple App Store, or Google Play store for Android.
Today, coding BASIC interpreters has become part of the retrocomputing hobby. Higher level programming languages on systems with extensive RAM have simplified implementing BASIC interpreters. For instance, line management is simple if your implementation language supports sparse matrixes, variable management is simple with associative arrays, and program execution is easy with eval functions. As examples, see the open-source project Vintage BASIC, written in Haskell or the OCaml Tiny BASIC.
Sales and distribution.
Initially, interpreters were either bundled with computer hardware or developed as a custom service, before an industry producing independently packaged software for organizations came about in the late 1960s. BASIC interpreters were first sold separately from microcomputers, then built-in, before becoming sold as applications again in the DOS era.
As the market shifted to ROMs, ROM size came to dominate decisions about how large a BASIC interpreter could be. Because RAM were sold as 4 KB chips, Altair BASIC was initially packaged in separate editions for 4K, 8K, and 12K; this carried over to ROM chips, as manufacturers would decide how many ROM chips they could fit in their design, given price goals and other constraints.
Compilers vs. interpreters.
The first implementation of BASIC, Dartmouth BASIC, was a compiler. Generally, compilers examine the entire program in a multi-step process and produce a second file that is directly executable in the host computer's underlying machine language without reference to the source code. This code is often made up of calls to pre-written routines in the language's runtime system. The executable will normally be smaller than the source code that created it.
The main disadvantage of compilers, at least in the historical context, is that they require large amounts of temporary memory. As the compiler works, it is producing an ever-growing output file that is being held in memory along with the original source code. Additional memory for temporary lookups, notably line numbers in the case of BASIC, adds to the memory requirement. Computers of the era had very small amounts of memory; in modern terms a typical mainframe might have on the order of 64 KB. On a timesharing system, the case for most 1960s BASICs, that memory was shared among many users.
In order to make a compiler work, the systems had to have some form of high-performance secondary storage, typically a hard drive. Program editing took place in a dedicated environment that wrote the user's source code to a temporary file. When the user ran the program, the editor exited and ran the compiler, which read that file and produced the executable code, and then finally the compiler would exit and run the resulting program. Splitting the task up in this fashion reduced the amount of memory needed by any one of the parts of the overall BASIC system; at any given time, only the editor, compiler, or runtime had to be loaded, the rest was on storage.
While mainframes had small amounts of memory, minicomputers had even smaller amounts: 4 and 8 KB systems were typical in the 1960s. But far more importantly, minicomputers tended to lack any form of high-performance storage; most early designs used punch tape as a primary storage system, and magnetic tape systems were for the high end of the market. In this environment, a system that wrote out the source, compiled it, and then ran the result would have taken minutes. Because of these constraints, interpreters proliferated.
Interpreters ultimately perform the same basic tasks as compilers, reading the source code and converting that into executable instructions calling runtime functions. The primary difference is "when" they perform the various tasks. In the case of a compiler, the entire source code is converted during what appears to the user as a single operation, whereas an interpreter converts and runs the source one statement at a time. The resulting machine code is executed, rather than output, and then that code is then discarded and the process repeats with the next statement. This dispenses with the need for some form of secondary storage while an executable is being built. The primary disadvantage is that you can no longer split the different parts of the overall process apart - the code needed to convert the source into machine operations has to be loaded into memory along with the runtime needed to perform it, and in most cases, the source code editor as well.
Producing a language with all of these components that can fit into a small amount of memory and still has room for user's source code is a major challenge, but it eliminates the need for secondary storage and was the only practical solution for early minicomputers and most of the history of the home computer revolution.
Development.
Language design.
Language design for the first interpreters often simply involved referencing other implementations. For instance, Wozniak's references for BASIC were an HP BASIC manual and a copy of "101 BASIC Computer Games". Based on these sources, Wozniak began sketching out a syntax chart for the language. He did not know that HP's BASIC was very different from the DEC BASIC variety used in "101 Games". The two languages differed principally in terms of string handling and control structures. Data General Business Basic, an integer-only implementation, was the inspiration for Atari BASIC.
In contrast, Dennis Allison, a member of the Computer Science faculty at Stanford University, wrote a specification for a simple version of the language. Allison was urged to create the standard by Bob Albrecht of the Homebrew Computer Club, who had seen BASIC on minicomputers and felt it would be the perfect match for new machines like the Altair. Allison's proposed design only used integer arithmetic and did not support arrays or string manipulation. The goal was for the program to fit in 2 to 3 kilobytes of memory. The overall design for Tiny BASIC was published in the September 1975 issue of the People's Computer Company (PCC) newsletter.
The grammar is listed below in Backus–Naur form. In the listing, an asterisk ("*") denotes zero or more of the object to its left — except for the first asterisk in the definition of "term", which is the multiplication operator; parentheses group objects; and an epsilon ("ε") signifies the empty set. As is common in computer language grammar notation, the vertical bar ("|") distinguishes alternatives, as does being listed on separate lines. The symbol "CR" denotes a carriage return. 
 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 ::= < (>|=|ε) | > (<|=|ε) | =
This syntax, as simple as it was, added one innovation: and could take an expression rather than a line number, providing an assigned GOTO rather than the switch statement of the structure more typical of BASIC.
Sinclair BASIC used as its language definition the 1978 American National Standards Institute (ANSI) Minimal BASIC standard, but was itself an incomplete implementation with integer arithmetic only. The ANSI standard was published after the design of the first generation of interpreters for microcomputers.
Architecture.
Common components of a BASIC interpreter:
Coding.
Early microcomputers lacked development tools, and programmers either developed their code on minicomputers or by hand. For instance, Dick Whipple and John Arnold wrote Tiny BASIC Extended directly in machine code, using octal. Robert Uiterwyk handwrote MICRO BASIC for the SWTPC (a 6800 system) on a legal pad. Steve Wozniak wrote the code to Integer BASIC by hand, translating the assembler code instructions into their machine code equivalents and then uploading the result to his computer. (Because of this, the program was very hard to change, and Wozniak was not able to modify it quickly enough for Steve Jobs, who subsequently licensed BASIC from Microsoft.)
Gates and Allen did not have an Altair system on which to develop and test their interpreter. However, Allen had written an Intel 8008 emulator for their previous venture, Traf-O-Data, that ran on a PDP-10 time-sharing computer. Allen adapted this emulator based on the Altair programmer guide, and they developed and tested the interpreter on Harvard's PDP-10. When Harvard stopped their use of this system, Gates and Allen bought computer time from a timesharing service in Boston to complete their BASIC program debugging. Gates claimed, in his Open Letter to Hobbyists in 1976, the value of the computer time for the first year of software development was $40,000.
Not that Allen couldn't handcode in machine language. While on final approach into the Albuquerque airport on a trip to demonstrate the interpreter, Allen realized he had forgotten to write a bootstrap program to read the tape into memory. Writing in 8080 machine language, Allen finished the program before the plane landed. Only when he loaded the program onto an Altair and saw a prompt asking for the system's memory size did he know that the interpreter worked on the Altair hardware.
One of the most popular of the many versions of Tiny BASIC was Palo Alto Tiny BASIC, or PATB for short. PATB first appeared in the May 1976 edition of "Dr. Dobbs", written in a custom assembler language with non-standard mnemonics. Li-Chen Wang had coded his interpreter on a time-share system with a generic assembler.
One exception to the use of assembly was the use of ALGOL 60 for the Paisley XBASIC interpreter for Burroughs large systems. Another exception, and type-in program, was Classic BASIC, written by Lennart Benschop in Forth and published in the Dutch Forth magazine "Vijgeblad" (issue #42, 1993).
The source code of interpreters was often open source (as with Tiny BASIC) or published later by the authors. The complete annotated source code and design specifications of Atari BASIC were published as "The Atari BASIC Source Book" in 1983.
Virtual machines.
Some BASIC interpreters were coded in the intermediate representation of a virtual machine to add a layer of abstraction and conciseness above native machine language.
While virtual machines had been used in compile and go systems such as BASIC-PLUS, these were only for executing BASIC code, not parsing it. Tiny BASIC, in contrast, was designed to be implemented as a virtual machine that parsed and executed (interpreted) BASIC statements; in such an implementation, the Tiny BASIC interpreter is itself run on a virtual machine interpreter. The length of the whole interpreter program was only 120 virtual machine operations, consisting of 32 commands. Thus the choice of a virtual machine approach economized on memory space and implementation effort, although the BASIC programs run thereon were executed somewhat slowly. "(See Tiny BASIC: Implementation in a virtual machine for an excerpt and sample commands.)" While the design intent was for Tiny BASIC to use a virtual machine, not every implementation did so; those that did included Tiny BASIC Extended, 6800 Tiny BASIC, and NIBL. 
For its TI-99, Texas Instruments designed a virtual machine with a language called GPL, for "Graphic Programming Language". (Although widely blamed for the slow performance of TI-BASIC, part of the problem was that the virtual machine was stored in graphics ROM, which had a slow 8-bit interface.)
A misunderstanding of the Apple II ROMs led some to believe that Integer BASIC used a virtual machine, a custom assembler language contained in the Apple ROMs and known as SWEET16. SWEET16 is based on bytecodes that run within a simple 16-bit virtual machine, so memory could be addressed via indirect 16-bit pointers and 16-bit math functions calculated without the need to translate those to the underlying multi-instruction 8-bit 6502 code. However, SWEET16 was not used by the core BASIC code, although it was later used to implement several utilities, such as a line renumbering routine.
Program editing and storage.
Program editing.
Most BASIC implementations of the era acted as both the language interpreter as well as the line editor. When BASIC was running, a command prompt was displayed where the user could enter statements. This was known as "direct mode". Upon boot, a BASIC interpreter defaulted to direct mode.
Statements that were entered with leading numbers are entered into the program storage for "deferred execution", either as new lines or replacing any that might have had the same number previously. Statements that were entered without a line number were referred to as commands, and ran immediately. Line numbers without statements (i.e., followed by a carriage return) deleted a previously stored line. 
When a program was present in memory and the user types in the command, the system enters "indirect mode". In this mode, a pointer is set to point to the first line of the program, for instance, line 10. 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.
Different implementations offered other program-editing capabilities. Altair BASIC 8K had an command to shift into an editing mode for one line. Integer BASIC, also included the command to automatically enter line numbers at a given starting number like , adding 10 to the last number with every new line. would begin numbering at line 300 by fives; 300, 305, etc. Automatic numbering was turned off by entering . Some interpreters offered line-renumbering commands or utilities.
Tokenizing and encoding lines.
To save RAM, and speed execution, all BASIC interpreters would encode some ASCII characters of lines into other representations. For instance, line numbers were converted into integers stored as bytes or words, and keywords might be assigned single-byte tokens (for instance, storing as the byte value 145, in MS-BASIC). These representations would then be converted back to readable text when ing the program.
Abbreviations.
As an alternative to tokenization, to save RAM, early Tiny BASIC implementations like Extended Tiny BASIC, Denver Tiny BASIC and MINOL truncated keywords: for , for , for . The full, traditional keywords were not accepted.
In contrast, Palo Alto Tiny BASIC accepted traditional keywords but allowed any keyword to be abbreviated to its minimal unique string, with a trailing period. For instance, could be typed , although and other variations also worked. This system was retained in Level I BASIC for the TRS-80, which used PATB, and was also found in Atari BASIC and the BASIC of various Sharp Pocket Computers.
To expand an abbreviation, the Atari BASIC tokenizer searches through its list of reserved words to find the first that matches the portion supplied. More commonly used commands occur first in the list of reserved words, with codice_5 at the beginning (it can be typed as codice_6). When the program is later codice_7ed it will typically write out the full words. MS BASICs also allowed codice_8 as a short-form for codice_9, but did expand it when listing, treating it as an abbreviation, not a synonym.
Tokenization.
Most BASIC interpreters perform at least some conversion from the original text form into various platform-specific formats. Tiny BASIC was on the simple end: it only converted the line number from its decimal format into binary. For instance, the line number "100" became a single byte value, $64, making it smaller to store in memory as well as easier to look up in machine code (a few designs of Tiny BASIC permitted line numbers from only 1 to 254 or 255, although most used double byte values and line numbers of at least 1 to 999). The rest of the line was left in its original text format. In fact, Dennis Allison argued that, given memory constraints, tokenization would take more code to implement than it would save.
MS-BASICs went slightly further, converting the line number into a two-byte value and also converting keywords, like or , into a single-byte value, the "token". Microsoft BASIC's tokenization didn't tokenize spaces (e.g., was stored in two bytes, while was stored in three bytes); in contrast, Sinclair BASIC displayed a space after each tokenized keyword, producing more readable code. In MS BASIC, for a statement such as , the line number and would be tokenized, while the was left in its original format and had to be re-parsed into a 16-bit integer every time the line was encountered.
In contrast, Integer BASIC would convert the line entirely into tokens that could be immediately read and performed. Where Microsoft BASIC had one token for the keyword , Integer BASIC had three tokens: one if the keyword was followed by no arguments, one if followed by an arithmetic expression, and one if followed by a string literal. Since Integer BASIC processed more of the original source code into tokens, the runtime was faster than versions that required additional runtime parsing. Numeric literals, like the value 500, were converted into their 16-bit (two-byte) binary representation, in this case, $01F4 hexadecimal. To indicate this was a value and not a keyword, a single byte between $B0 and $B9 was inserted in front of the two-byte value. String literals, like "HELLO WORLD" were instead encoded by setting the high bit of each character so that was stored as $C1. Variable names were converted in the same fashion, with the letters encoded to have their high-bit turned on, and any digits in the name represented by the corresponding $B0 through $B9, so that the variable would be encoded as $C1B5 (not reduced to a token). 
Carrying this even further, Atari BASIC's tokenizer parses the entire line when it is entered or modified. Numeric constants are parsed into their 40-bit internal form and then placed in the line in that format, while strings are left in their original format, but prefixed with a byte describing their length. Variables have storage set aside as they are encountered, and their name is replaced with a pointer to their storage location in memory. Shepardson referred to this early-tokenizing concept as a "pre-compiling interpreter"; statements with syntax errors could not actually be stored, and the user was immediately prompted to correct them.
Tokenization at the keyboard.
Some interpreters, such as the Bally Astrocade and Sinclair systems, basically had the user do the tokenization by providing combined keystrokes to enter reserved words. The most common commands need one keystroke only; for example, pressing only at the start of a line on a Spectrum produces the full command codice_9. Less frequent commands require more complex key sequences: codice_11 (for example) is keyed by pressing plus to access extended mode (later models include an key), keeping held down and pressing . Keywords are colour-coded on the original Spectrum keyboard to indicate which mode is required:
The BASIC interpreter could quickly determine any command or function by evaluating one byte (the keyword token). Given the syntactic requirement that every line start with a command keyword (e.g., is not optional), pressing the one keypress for a command at the start of a line changes the editor from command mode to letter mode. Tokenization at the keyboard meant keywords were not "reserved words" like in other BASIC dialects, e.g., it is allowed to define a variable named codice_9 and output its value with codice_13.
Line management.
Valid line numbers varied from implementation to implementation, but were typically from 1 to 32767. 
Most of the memory used by BASIC interpreters was to store the program listing itself. Numbered statements were stored in sequential order in a sparse array implemented as a linear collection (technically not a list as no line number could occur more than once).
Many Tiny BASIC implementations stored lines as follows:
Microsoft BASIC, starting with Altair BASIC, stored lines as follows:
LLL BASIC:
The maximum length of a line varied: 64 characters in Palo Alto Tiny BASIC, including the decimal representation of the line number; 120 characters in Atari BASIC; 128 characters in Integer BASIC; and 255 characters in MS-BASIC (not including the line number).
Interpreters would search the program a line at a time, looking at each line number. If it were lower than the new line number, the later lines would be moved in memory to make room for the space required for the new line. If it were the same line number, and not the exact same length, subsequent lines would need to be moved forward or backward. (Because sequential order was always maintained in memory, these were not linked lists.)
In Tiny BASIC, these searches required checking every byte in a line: the pointer would be incremented again and again until a carriage return was encountered, to find the byte before the next line. In Altair BASIC and LLL BASIC, on the other hand, the pointer would instead be set to the start of the next sequential line; this was much faster, but required two bytes per line. Given that Tiny BASIC programs were presumed to be 4 KB or less in size, this was in keeping with Tiny BASIC's general design philosophy of trading off performance in favor of minimizing memory usage.
When the user typed into the command line, the system would loop over the array of lines, using one of these methods, convert the line number back to decimal format, and then print out the rest of the text in the line, decoding any tokens or other encoded representations.
As developers added structured programming constructs to BASIC, they often removed the need for line numbers altogether and added text editors and, later, integrated development environments.
Variables and data types.
Variable names.
Dartmouth BASIC and HP-BASIC limited variable names to at most two characters (either a single letter or a letter followed by one digit; e.g., A to Z9). MS-BASIC allowed variable names of a letter followed by an optional letter or digit (e.g., A to ZZ) but ignored subsequent characters: thus it was possible to inadvertently write a program with variables "LOSS" and "LOAN", which would be treated as being the same; assigning a value to "LOAN" would silently overwrite the value intended as "LOSS".
Integer BASIC was unusual in supporting any length variable name (e.g., SUM, GAMEPOINTS, PLAYER2), provided it did not contain a reserved word. Keywords could not be used in variables in many early BASICs; "SCORE" would be interpreted as "SC" OR "E", where OR was a keyword.
String variables are usually distinguished in many microcomputer dialects of BASIC by having $ suffixed to their name, and values are often identified as strings by being delimited by "double quotation marks". Later implementations would use other punctuation to specify the type of a variable: A% for integer, A! for single precision, and A# for double precision.
With the exception of arrays and (in some implementations) strings, and unlike Pascal and other more structured programming languages, BASIC does not require a variable to be declared before it is referenced. Values will typically default to 0 (of the appropriate precision) or the null string.
Symbol table.
Because Tiny BASIC only used 26 single-letter variables, variables could be stored as an array without storing their corresponding names, using a formula based on the ASCII value of the letter as the index. Palo Alto Tiny BASIC took this a step further: variables 'two-byte values were located in RAM within the program, from bytes 130 (ASCII 65, 'A', times two) to 181 (ASCII 90, 'Z', times two, plus one for the second byte).
Most BASICs provided for the ability to have far more than 26 variables and so needed symbol tables, which would set aside storage capacity for only those variables used.
In LLL BASIC, each entry in the symbol table was stored as follows:
Unlike most BASIC interpreters, UIUC BASIC had a hash function, hashing by the letter of the variable/function/array name, then conducting a linear search from there. In UIUC BASIC, a symbol table entry was:
In Atari BASIC, a set of pointers (addresses) indicated various data: variable names were stored in the "variable name table" (VNTP – 82, 8316) and their values were stored in the "variable value table" (pointed to at VVTP – 86, 8716). By indirecting the variable names in this way, a reference to a variable needed only one byte to address its entry into the appropriate table. String variables had their own area.
One BBC BASIC performance optimization included using multiple linked lists for variable lookup rather than a single long list, as in Microsoft BASIC.
Memory management.
Because of the small RAM capacity of most systems originally used to run BASIC interpreters, clever memory management techniques had to be employed. Altair BASIC let users reclaim the space for trigonometry functions if those weren't being used during a session. PATB placed the start of the most common subroutines at the front of the program for use by the 1-byte 8080 opcode instead of the 3-byte opcode. In LLL BASIC, some variables occupied the same memory locations, in cases where the different variables were used only in command mode or only at runtime.
Video was often memory addressable, and certain esoteric functions were available by manipulating values at specific memory values. For instance, addresses 32 to 35 contained the dimensions of the text window (as opposed to the graphics window) in Applesoft BASIC. The command and the function (adapted from machine code monitors such as the DECsystem-10 monitor) provided direct memory access, for a variety of purposes, especially for modifying special memory-mapped hardware registers to control particular functions of the computer such as the input/output peripherals. "Memory maps" (in the archaic sense of lists of memory addresses and their functions) were popular for use with PEEK and POKE, with one of the best known memory maps being the book "Mapping the Atari", written by Ian Chadwick.
Mathematics.
Integer BASIC, as its name implies, uses integers as the basis for its math package. These were stored internally as a 16-bit number, little-endian (as is the 6502). This allowed a maximum value for any calculation between −32767 and 32767. Calculations that resulted in values outside that range produced an error.
Most Tiny BASIC interpreters (as well as Sinclair BASIC 4K) supported mathematics using integers only, lacking floating-point support. Using integers allowed numbers to be stored in a much more compact 16-bit format that could be more rapidly read and processed than the 32- or 40-bit floating-point formats found in most BASICs of the era. However, this limited its applicability as a general-purpose language.
Business BASIC implementations, such as Data General Business Basic, were also integer-only, but typically at a higher precision: "double precision", i.e. 32-bit (plus or minus 2,147,483,648) and "triple precision" (plus or minus 1.4x10^14).
Other computer number formats were sometimes used. For instance, the MINOL Tiny BASIC supported only unsigned bytes, and the MICRO-BASIC Tiny BASIC used Binary Coded Decimal. But floating point would come to predominate.
Floating point.
One story encapsulates why floating point was considered so important. The original prototype of the TRS-80 Model I ran Li-Chen Wang's public domain version of Tiny BASIC. This required only 2 KB of memory for the interpreter, leaving an average of another 2 KB free for user programs in common 4 KB memory layouts of early machines. During a demonstration to executives, Tandy Corporation's then-President Charles Tandy tried to enter his salary but was unable to do so. This was because Tiny BASIC used 2-byte signed integers with a maximum value of 32,767. The result was a request for floating-point math for the production version. This led to the replacement of the existing 16-bit integer code with a version using 32-bit single-precision floating-point numbers by Tandy-employee Steve Leininger.
SCELBAL used floating point routines published by Wadsworth in 1975 in "Machine Language Programming for the 8008" based on a 32-bit (four byte) format for numeric calculations, with a 23-bit mantissa, 1-bit sign for the mantissa, a 7-bit exponent, and 1-bit sign for the exponent. These were organized in reverse order, with the least significant byte of the mantissa in the first byte, followed by the middle and then most significant byte with the sign in the high bit. The exponent came last, again with the sign in the high bit. The manual provides well-documented assembly code for the entire math package, including entry points and usage notes. 
Consultants were typically brought into handle floating-point arithmetic, a specialist domain well studied and developed for the scientific and commercial applications that had characterized mainframes. When Allen and Gates were developing Altair BASIC, fellow Harvard student Monte Davidoff convinced them to switch from integer arithmetic. They hired Davidoff to write a floating-point package that could still fit within the 4KB memory limits. Steve Wozniak turned to Roy Rankin of Stanford University for implementing the transcendental functions LOG, LOG10, and EXP; however, Wozniak never finished adding floating-point support to Integer BASIC. LLL BASIC, developed at the University of Idaho by John Dickenson, Jerry Barber, and John Teeter, turned to David Mead, Hal Brand, and Frank Olken for their floating-point support. For UIUC BASIC, a Datapoint 2200 floating-point package was licensed.
In contrast, time-shared systems had often relied on hardware. For instance, the GE-235 was chosen for implementing the first version of Dartmouth BASIC specifically because it featured an "Auxiliary Arithmetic Unit" for floating point and double-precision calculations.
Early interpreters used 32-bit formats, similar to the , which specifies:
Here is the value 0.15625 as stored in this format:
While 32-bit formats were common in this era, later versions of BASIC, starting with Microsoft BASIC for the MOS 6502, generally adopted a 40-bit (five byte) format for added precision.
Operators and functions.
Infix operators typically included (addition), (subtraction), (multiplication), (division), and exponent using the character. Relative operations included the standard set of , , , , , and for "not equal" either or the HP-TSB-inspired . Binary operators, such as , and , weren't in every implementation, and some did Boolean algebra and some did not. 
Dartmouth BASIC's initial edition included the following functions: (absolute value), (arctangent), (cosine), ("e" raised to the power), (truncate any fractional value, returning an integer), (logarithm), (pseudorandom number generator), (sine), (square root), and (tangent). It also included the statement to declare one-line functions, which would then be referred to as , , etc.
The function was the most widespread function to be supported in early BASICs, though implementations varied:
Arrays.
The second version of Dartmouth BASIC supported matrices and matrix operations, useful for the solution of sets of simultaneous linear algebraic equations; matrix operations such as assignment, addition, multiplication (of compatible matrix types) and evaluation of a determinant were supported.
In contrast, Tiny BASIC as initially designed didn't even have any arrays, due to the limited main memory available on early microcomputers, often 4 KB, which had to include both the interpreter and the BASIC program. Palo Alto Tiny BASIC added a single variable-length array of integers, the size of which did not have to be dimensioned but used RAM not used by the interpreter or the program listing, .
SCELBAL supported multiple arrays, but taken together these arrays could have no more than 64 items. Integer BASIC supported arrays of a single dimension, limited in size only by the available memory. Tiny BASIC Extended supported two-dimensional arrays of up to 255 by 255. Altair BASIC 4K supported only arrays (one dimension) while the 8K version supported matrices of up to 34 dimensions.
Many implementations supported the Dartmouth BASIC practice of not requiring an array to be dimensioned, in which case it was assumed to have 11 elements (0 to 10); e.g., would create the 11-element array as a side effect.
The dope vector of arrays varied from implementation to implementation. For instance, the dope vector of an Altair BASIC 4K array:
Then the array values themselves:
Implementations that supported matrices had to record the number of dimensions and the upper bound of each dimension. Further, as some interpreters had only one data type (either floating point or integer), the dope vector merely needed to record the number of dimensions and the upper bound of each dimension. Interpreters with multiple data types had to record the data type of the array. 
Even though Microsoft and other BASICs did support matrices, matrix operations were not built in but had to be programmed explicitly on array elements.
Strings.
The original Dartmouth BASIC, some of its immediate descendants, and Tiny BASIC implementations lacked string handling. Two competing schools of string-handling evolved, pioneered by HP and DEC, although other approaches came later. These required different strategies for implementation.
The simplest string handling copied HP Time-Shared BASIC and defined string variables as arrays of characters that had to be ensioned prior to use. Strings in HP TSB are treated as an array of characters, up to 72 in total, rather than a single multi-character object. By default, they are allocated one character in memory, and if a string of longer length is needed, they have to be declared. For instance, DIM A$[10] will set up a string that can hold a maximum of 10 characters.
Substrings within strings are accessed using a "slicing" notation: A$(L,R) or A$[L,R], where the substring begins with the leftmost character specified by the index L and continues to the rightmost character specified by the index R, or the A$[L] form where the substring starts at the leftmost character specified by the index L and continues to the end of the string. TSB accepts () or [] interchangeably. Array and substring indices start with 1.
This is in sharp contrast to BASICs following the DEC pattern that use functions such as codice_14, codice_15, and codice_16 to access substrings. Later adopted by ANSI BASIC, HP's notation can also be used on the destination side of a or statement to modify part of an existing string value, for example 100 A$[3,5]="XYZ" or 120 B$[3]="CHANGE ALL BUT FIRST TWO CHARS", which cannot be done with early implementations of .
Later versions of Dartmouth BASIC did include string variables. However, they did not use the codice_17 functions for manipulating strings, but instead used the codice_18 command which converted the string to and from equivalent ASCII values. (Later adopted as is by DEC and adapted by HP, which changed the keyword to codice_19.) Additionally, one could use the single-quote to convert a numeric constant to an ASCII character, allowing one to build up a string in parts; codice_20 produced the string "ABCDEF", without the need for the codice_21 function. Dartmouth BASIC Sixth Edition supported (for ) and (for ).
Integer BASIC, North Star BASIC and Atari BASIC mimicked HP's approach, which again contrasted with the style found in BASICs derived from DEC, including Microsoft BASIC, where strings are an intrinsic variable-length type.
Some of the Tiny BASIC implementations supported one or more predefined integer arrays, which could be used to store character codes, provided the language had functionality to input and output character codes (e.g., Astro BASIC had codice_22 and codice_23 for this purpose).
Garbage collection.
Having strings use a fixed amount of memory regardless of the number of characters used within them, up to a maximum of 255 characters, may have wasted memory but had the advantage of avoiding the need for implementing garbage collection of the heap, a form of automatic memory management used to reclaim memory occupied by strings that are no longer in use. Short strings that were released might be stored in the middle of other strings, preventing that memory from being used when a longer string was needed.
On early microcomputers, with their limited memory and slow processors, BASIC garbage collection could often cause apparently random, inexplicable pauses in the midst of program operation. Some BASIC interpreters, such as Applesoft BASIC on the Apple II family, repeatedly scanned the string descriptors for the string having the highest address in order to compact it toward high memory, resulting in O(n2) performance, which could introduce minutes-long pauses in the execution of string-intensive programs. Garbage collection was notoriously slow or even broken in other versions of Microsoft BASIC.
Other functionality.
Graphics and sound.
Most BASIC interpreters differed widely in graphics and sound, which varied dramatically from microcomputer to microcomputer. Altair BASIC lacked any graphics or sound commands, as did the Tiny BASIC implementations, while Integer BASIC provided a rich set.
Level I BASIC for the TRS-80 had as minimal a set as possible: , for CLear Screen; , which lit a location on the display; , which turned it off; and , which returned 1 if a location was lit, 0 if it was not. The coordinates could be any expression and ranged from 0 to 127 for the X-axis and 0 to 47 for the Y-axis. Only black-and-white display was supported.
In contrast, Integer BASIC supported color graphics, simple sound, and game controllers. Graphics mode was turned on with the statement and off with . Drawing was modal and normally started by issuing a command to change the color, which was accomplished by setting a pseudo-variable; would set the drawing color to 12, light green. One could then to produce a single spot of that color, to draw a horizontal line at row 20 that spanned the screen, or to draw a shorter vertical line down column 7. returned the color of the screen at X,Y. 
 Hardware manufacturers often included proprietary support for semigraphics, simple shapes and icons treated as special characters. Examples included the block graphics of the ZX-81, and the card symbols of ♠, ♣, ♥ and ♦ in the Commodore International PETSCII character set. BASIC could generate these symbols using .
Microsoft added many graphics commands to IBM BASIC: , (Pixel SET), (Pixel RESET), (stores a rectangle of the screen to an array), (displays a stored rectangular segment), (to move the text cursor), and , which sketches shapes using a LOGO-like syntax. Bill Gates and Neil Konzen wrote DONKEY.BAS, a bundled game, to demonstrate the interpreter's color graphics and sound.
Input/output.
Another area where implementations diverged was in keywords for dealing with media (cassettes and floppy disks), keyboard input, and game controllers (if any).
Since ROM-based BASIC interpreters often functioned as shells for loading in other applications, implementations added commands related to cassette tapes (e.g., and ), binary disk files (e.g., , , and ), and BASIC programs on disk (e.g., , , and ). Business BASIC implementations added commands for random-access files. (Even ROM-based BASIC interpreters were not designed or intended to be used as operating systems, and smaller microcomputers simply lacked any OS at all.)
Dartmouth BASIC lacked a command for getting input from the keyboard without pausing the program. To support videogames, BASICs added proprietary commands for doing so: was a function in Microsoft BASIC that would return an empty string if no key was pressed or otherwise a single character; (for "KeyPress") returned the ASCII value of the input in Astro BASIC.
Palo Alto Tiny BASIC lacked strings but would allow users to enter mathematical expressions as the answer to statements; by setting variables, such as codice_24, the user could answer “Y” or “1” or even "3*2-5" at a yes/no prompt.
Some systems supported game controllers. Astro BASIC supported codice_25 (specified joystick's horizontal position), codice_26 (joystick vertical position), codice_27 (knob status), and codice_28 (trigger status). Integer BASIC supported a game controller, a paddle controller, which had two controllers on a single connector. The position of the controller could be read using the function, passing in the controller number, 0 or 1, like , returning a value between 0 and 255.
Integer BASIC lacked any custom input/output commands, and also lacked the statement and the associated . To get data into and out of a program, the input/output functionality was redirected to a selected card slot with the and , which redirected output or input (respectively) to the numbered slot. From then on, data could be sent to the card using conventional commands and read from it using . Producing sounds was accomplished by ing the memory-mapped location of a simple "beeper", −16336.
Structured programming.
While structured programming, through the examples of ALGOL 58 and ALGOL 60, were known to Kemeny and Kurtz when they designed BASIC, they adapted only the for-loop, ignoring the else-statement, while-loop, repeat loop, named procedures, parameter passing, and local variables. As a result, subsequent dialects often differed dramatically in the wording used for structured techniques. For instance, (in Microsoft BASIC), (in Turbo-Basic XL), and even clauses (both in BASIC-PLUS).
Of the Tiny BASIC implementations, only National Industrial Basic Language (NIBL) offered a loop command of any sort, . This was despite the inventor of Tiny BASIC, Dennis Allison, publicly lamenting the state of BASIC.
BBC BASIC was one of the first microcomputer interpreters to offer structured BASIC programming, with named codice_1/codice_2 procedures and functions, codice_3 loops, and codice_4 structures inspired by COMAL. Second-generation BASICs—for example, SBASIC (1976), BBC BASIC (1981), True BASIC (1983), Beta BASIC (1983), QuickBASIC (1985), and AmigaBASIC (1986) -- introduced a number of features into the language, primarily related to structured and procedure-oriented programming. Usually, line numbering is omitted from the language and replaced with labels (for GOTO) and procedures to encourage easier and more flexible design. In addition keywords and structures to support repetition, selection and procedures with local variables were introduced.
The following example is in Microsoft QBASIC, Microsoft's third implementation of a structured BASIC (following Macintosh BASIC in 1984 and Amiga BASIC in 1985).
REM QBASIC example
REM Forward declaration - allows the main code to call a
REM subroutine that is defined later in the source code
DECLARE SUB PrintSomeStars (StarCount!)
REM Main program follows
DO
 INPUT "How many stars do you want? (0 to quit) ", NumStars
 CALL PrintSomeStars(NumStars)
LOOP WHILE NumStars>0
END
REM subroutine definition
SUB PrintSomeStars (StarCount)
 REM This procedure uses a local variable called Stars$
 Stars$ = STRING$(StarCount, "*")
 PRINT Stars$
END SUB
Object oriented.
Initial support for object-oriented programming provided only the re-use of objects created with other languages, such as how Visual Basic and PowerBASIC supported the Windows Component Object Model. As BASIC interpreters continued to evolve, they added support for object-oriented features such as methods, constructors, dynamic memory allocation, properties and temporary allocation.
Included assembler.
The Integer BASIC ROMs also included a machine code monitor, "mini-assembler", and disassembler to create and debug assembly language programs.
One of the unique features of BBC BASIC was the inline assembler, allowing users to write assembly language programs for the 6502 and, later, the Zilog Z80, NS32016 and ARM. The assembler was fully integrated into the BASIC interpreter and shared variables with it, which could be included between the [ and ] characters, saved via *SAVE and *LOAD, and called via the CALL or USR commands. This allowed developers to write not just assembly language code, but also BASIC code to emit assembly language, making it possible to use code-generation techniques and even write simple compilers in BASIC.
Execution.
Debugging.
As in most BASICs, programs were started with the command, and as was common, could be directed at a particular line number like . Execution could be stopped at any time using and then restarted with inue ( in Integer BASIC.
For step-by-step execution, the or instruction could be used at the command prompt or placed within the program itself. When it was turned on, line numbers were printed out for each line the program visited. The feature could be turned off again with or .
Unlike most BASICs, Atari BASIC scanned the just-entered program line and reported syntax errors immediately. If an error was found, the editor re-displayed the line, highlighting the text near the error in inverse video.
In many interpreters, including Atari BASIC, errors are displayed as numeric codes, with the descriptions printed in the manual. Many MS-BASIC used two-character abbreviations (e.g., SN for SYNTAX ERROR). Palo Alto Tiny BASIC and Level I BASIC used three words for error messages: "WHAT?" for syntax errors, "HOW?" for run-time errors like GOTOs to a line that didn't exist or numeric overflows, and "SORRY" for out-of-memory problems.
Parsing.
While the BASIC language has a simple syntax, mathematical expressions do not, supporting different precedence rules for parentheses and different mathematical operators. To support such expressions requires implementing a recursive descent parser.
This parser can be implemented in a number of ways:
Performance.
The range of design decisions that went into programming a BASIC interpreter were often revealed through performance differences.
Line-management implementations often affected performance and typically used linear search. Delimiting each line with a CR would make a GOTO or GOSUB to a later line would take longer, as the program would need to iterate over all the lines to find the target line number. In some implementations, such as Atari BASIC, the length of each line was recorded and stored after the line number, so that the program did not have to scan each character of the line to find the next carriage return. Many implementations would always search for a line number to branch to from the start of the program; MS-BASIC would search from the current line, if the destination line number was greater. Pittman added a patch to his 6800 Tiny BASIC to use a binary search.
Working solely with integer math provides another major boost in speed. As many computer benchmarks of the era were small and often performed simple math that did not require floating-point, Integer BASIC trounced most other BASICs. On one of the earliest known microcomputer benchmarks, the Rugg/Feldman benchmarks, Integer BASIC was well over twice as fast as Applesoft BASIC on the same machine. In the Byte Sieve, where math was less important but array access and looping performance dominated, Integer BASIC took 166 seconds while Applesoft took 200. It did not appear in the Creative Computing Benchmark, which was first published in 1983, by which time Integer BASIC was no longer supplied by default. The following test series, taken from both of the original Rugg/Feldman articles, show Integer's performance relative the MS-derived BASIC on the same platform.
In theory, Atari BASIC should have run faster than contemporary BASICs based on the Microsoft pattern. Because the source code is fully tokenized when it is entered, the entire tokenization and parsing steps are already complete. Even complex mathematical operations are ready-to-run, with any numerical constants already converted to its internal 40-bit format, and variables values are looked up by address rather than having to be searched for. In spite of these theoretical advantages, in practice, Atari BASIC is slower than other home computer BASICs, often by a large amount. In practice, this was not borne out. On two widely used benchmarks of the era, "Byte" magazine's Sieve of Eratosthenes and the Creative Computing benchmark test written by David H. Ahl, the Atari finished near the end of the list in terms of performance, and was much slower than the contemporary Apple II or Commodore PET, in spite of having the same CPU but running it at roughly twice the speed of either. It finished behind relatively slow machines like the Sinclair ZX81 and even some programmable calculators.
Most of the language's slowness stemmed from three problems. The first is that the floating-point math routines were poorly optimized. In the Ahl benchmark, a single exponent operation, which internally loops over the slow multiplication function, was responsible for much of the machine's poor showing. Second, the conversion between the internal floating-point format and the 16-bit integers used in certain parts of the language was relatively slow. Internally, these integers were used for line numbers and array indexing, along with a few other tasks, but numbers in the tokenized program were always stored in binary-coded decimal (BCD) format. Whenever one of these is encountered, for instance, in the line number in , the tokenized BCD value has to be converted to an integer, an operation that can take as long as 3500 microseconds. Other BASICs avoided this delay by special-casing the conversion of numbers that could only possibly be integers, like the line number following a , switching to special ASCII-to-integer code to improve performance. Third was how Atari BASIC implemented branches and codice_33 loops. To perform a branch in a codice_34 or codice_35, the interpreter searches through the entire program for the matching line number it needs. One minor improvement found in most Microsoft-derived BASICs is to compare the target line number to the current line number, and search forward from that point if it is greater, or start from the top if less. This improvement was missing in Atari BASIC. Unlike almost all other BASICs, which would push a pointer to the location of the codice_33 on a stack, so when it reached the codice_37 it could easily return to the codice_33 again in a single branch operation, Atari BASIC pushed the line number instead. This meant every time a codice_37 was encountered, the system had to search through the entire program to find the corresponding codice_33 line. As a result, any loops in an Atari BASIC program cause a large loss of performance relative to other BASICs.
Further reading.
Source code and design documents, in chronological order of the release of the BASIC implementations: