More About Blocking

An example of the blocking problem, say with an IF/ENDIF block, if the IF/THEN line is entered first, this constitutes a context error until its corresponding ENDIF line is entered and once entered the block is complete and the context error count is reset allowing the program to run. Now say another IF/THEN line is entered between the first IF/THEN/ENDIF block. The new IF/THEN would be connected to the ENDIF line and the first IF/THEN is now in error. This block connection and disconnection can get rather involved and will require careful programming.

Once the screen editor component is implemented, it would be nice to highlight these context errors in the editor. For example if an IF/THEN or ENDIF line does not have a corresponding ENDIF or IF/THEN line, then the “IF” would display in reverse video or with a red background to let the user know there is a problem. The editor will also be able to automatically indent the contents within blocks, another visual cue to assist the programmer.

This error highlighting would apply to other types of context errors, for instances with arrays. Lines may be entered using an array before the DIM line for the array is entered. The number of subscripts that an array has can be inferred by the first time it is entered and if any subsequent references of the array have a different number of subscripts, a context error is flagged and all instances of the array are highlighted. The size of the array and the actual number of subscripts is not known until the actual DIM line is entered. There would be different highlighting for mismatch array subscripts and arrays that don't yet have a DIM (or perhaps have more than one DIM or a DIM after the array is referenced).  When a DIM line is entered (before the first reference of the array), the highlighting is removed from the instances of the array (assuming of course that there are no further context errors, like instanced having the wrong number of subscripts).

Blocking Commands

Where it's going to get complicated for my interactive compiler is with the blocking commands. Examples of blocking commands include IF/THEN/ELSE/ENDIF, FOR/NEXT, DO/LOOP and SELECT/CASE. These commands are entered on multiple lines and can be entered in any order. A regular compiler matches the blocks during compilation and any unmatched blocks are reported as “context” errors. Generally an interpreter does not catch these context errors until run time since the program lines can be entered in any order. Ideally, an interactive compiler should catch as many errors as possible as soon as possible and before run time, including these context errors.  For run time speed, the less checking done at run time, the faster it will run the program.

Brown suggests ignoring these context errors when the lines are entered and having a “pre-run” module that goes through the program checking for context errors before the program is run. Brown briefly discusses an alternative method where tables are kept as these context errors are created in a table and removing entries as the context errors are resolved, but decides this method is too complicated and opts for the simpler approach of having a pre-run module.

I disagree with the need to have a pre-run module, which would delay the starting of the program when the RUN command is entered.  This takes away one of the advantages of an interactive compiler and would make it appear to be simply compiling the program before running. I plan on taking Brown's table idea further. It's difficult to explain, but essentially as lines are entered, a table with information on the blocks in the code is built as the lines are entered and the number of current context errors is kept track of. These context errors are different from syntax errors that can be caught immediately when a line is entered. With a block table and context error outstanding count, when a RUN command is issued, this count simply needs to be checked and if not zero, the errors are reported and the program is not run.

Immediate Commands

With the goal of keeping the first stage simple, the program will use console mode with classic BASIC line numbers. This will require immediate commands – commands executed immediately when entered (but not allowed in a program). Initially the interactive compiler will have a prompt and command format like BASIC interpreters have. If the command entered starts with a line number, then it will be compiled and inserted into the program memory, otherwise the command will be executed. The regular BASIC commands will be allowed on the command line, but I'm not sure this moment about the looping commands. The immediate commands needed for now include the following:

1. SAVE
2. LOAD
3. LIST
4. EDIT
5. RENUM (to renumber the program lines)
6. DELETE (lines can also be deleted by entering a line number be itself)
7. RUN
8. NEW

These commands will also be converted into the RPN internal language before executed (which means without string support, the SAVE and LOAD commands will have no way to have a file name, therefore these commands will prompt for a file name).

Initial BASIC Language Subset

Below is a list of BASIC commands that will be implemented first. These commands will allow simple programs to be entered and run. It will allow the expression parser and the complicated blocking code to be implemented and tested. These are listed in the approximate order to be implemented.

1. LET (assignment)
2. PRINT
3. INPUT
4. DIM (for arrays)
5. REM
6. IF/THEN/ELSE/ENDIF
7. FOR/NEXT
8. DO/LOOP (with WHILE/UNTIL)

The features listed below will be part of the initial implementation:

1. Double precision math operators (+,-,*,/, \, MOD, and ^)
2. Variables (with any size name)
3. Constants
4. Numerical functions (ABS, FIX, INT, RND, SGN, and SQR)
5. Scientific functions (ATN, COS, EXP, LOG, SIN, and TAN)
6. Relational operators (=,<>,<,<=,>, >=, AND, EQV, IMP, NOT, OR, and XOR)
7. Print functions (comma, TAB, and SPC)
8. Multiple dimension arrays
9. Multiple statements per line

The important thing is to get something working and not to over complicate the initial stage. Important and necessary features like strings and integers with associated operators and variables, SELECT CASE, subroutines and user functions etc. will come in later stages. Notice the lack of a GOTO command - this was intentional. Initially classic BASIC line numbers will be used (despite the lack of a GOTO) as a way of entering the lines into memory via console mode. Eventually this will be replaced with a screen editor, but a screen editor is a major undertaking in itself, so this will be delayed for a later stage.

Internal Language

Brown suggests that the internal language be in the form of RPN (Reverse Polish Notation) and I agree. As it will allow the program to be easily and quickly run. Basically the following commands:

    A = B + C * 4
    PRINT A+B;TAB(20);C+5

Would be translated to RPN, which would symbolically be represented as something like:

A B C 4 * + =(assignment)
A B + 20 TAB C 5 + PRINT

When the program is run, each operand is pushed onto a stack. When an operator is reached, it's operands (e.g. two for *, one for TAB, etc.) are pulled from the stack, the operation is performed and the result is pushed back onto the stack. When a command is reached (e.g. PRINT), it preforms it's procedure on the values that are currently on the stack.  It's more involved than this, but this is the general idea. The actual internal language is encoded from the symbolic RPN representation.

Development Platform

Development will be done Windows XP Home as that is what my computer runs (for the moment I do not intend to upgrade, to Vista or 7, as XP Home is working just fine). For now I'm not planning to develop for cross platforms (like for example the way FreeBasic runs on several platforms). Besides, whatever criticisms there are about Windows, it does have the largest market share.

I thought about trying out some of the algorithms in Tcl (using the free ActiveTcl package) and even sketched some of out in Tcl, but Tcl is a relatively unknown language, is basically in interpreter itself (though it may somewhat compile code internally – I not familiar with the details) and is not really fast. I also considered using something like FreeBasic, but that would be something new to learn (and most of my BASIC experience is with GW-Basic). I have the most experience with C and C++, though I'm currently rusty on C++ as I haven't been using the last 10 years. I decided on C++ because I think it is a good language and this is a chance to get back into it (and it may be come is use in the near future in my regular job).

There are many C++ compilers I could use, but I decided on the free Borland C++ 5.5 command line tools using the free Vide2. The second choice would be the GNU GCC package with G++ if the Borland C++ proves unsatisfactory, but so far I was not able to get it work on Windows using MinGW and MSYS (I do use GCC for my regular job on Linux). I learned C++ on Borland's C++ package for DOS with DPMI upgrading through 4.5 during the 1990s. And was able to successfully get Borland C++ 5.5 to work with Vide2. I'm not buying a commercial product for this effort since this is right now just a hobby.

Background Part III – Current Plans

Flash forward to a couple of months ago during a house remodeling project, I came across the old notes of my BASIC and a book that I was taking inspiration from at the time called Writing Interactive Compilers and Interpreters, 1980 by P. J. Brown. I started reading the book and was fascinated. I remembered my BASIC, the promise of the incremental compiler QuickBasic 4.5, and now had a renewed interest in trying to create an interactive incremental BASIC compiler as I had some new ideas – things that I personally have not seen in a development environment during all my years of software development.

My intention this time around is to develop an Interactive BASIC Compiler with an end goal of what I thought QuickBasic should have been. This is going to be a complicated project, so starting small and doing it in stages with several steps each will be required. The initial goal is to get something working and then building upon it. I will not be using anything previously developed from my BASIC interpreter. That was in 6809 assembler and while I do have source listing printouts (any e-copies are long lost), it's not really applicable to the current project. I will be looking at some of the notes I made about the BASIC language itself that I was thinking about at the time as it may be applicable. I will also be looking at existing BASIC compilers for inspiration (FreeBasic, xBasic, RealBasic, TrueBasic, PowerBasic, thinBasic, Smallbasic and of course GW-Basic). This project will not be written in assembly language - that just more effort that I want to take on. The ground rules for now are as follows:

1. Implement a small subset of BASIC commands to start.
2. Implement a selection of immediate commands.
3. Develop on Windows using C++.
4. Use console mode for now (like a BASIC interpreter).
5. Release the code at each stage/step under GPL on SourceForge.

For an interactive compiler to be successful, each line of code must be compiled into a form that is fast to execute (unlike my interpreter), but also needs to be easily able to be converted back into the original source file in the interactive environment. However, the source output may not look identical to what is entered (for example spacing). A large part of the initial effort will be in the design of the internal language and the language parser.

Why even bother as there are so many good software development tools around?  Because the whole idea fascinates me and programming is not only my career, but also a hobby. And maybe I can demonstrate some unique ideas along the way. And I'm really attempting to compete with those other BASICs – that is just not the current goal.

Background Part II – Plans Not Realized

While I was working on my BASIC Interpreter,  a local computer store that dealt in SS-50 bus computers along with a handful of investors (not me though) designed their own SS-50 bus – a computer that was similar to other small computers of the time (had a built-in keyboard, just plug it in an attached a monitor or TV). These other computers (e.g. TRS-80, Apple, Commodore PET, OSI, etc.) came with BASIC in ROM (read-only memory) so BASIC was there when the computer was turned on. Most SS-50 bus type computers required a terminal to communicate with through a serial interface. One of the member designed a complete terminal on a board that when put into the computer appeared as a serial device. This board was actually a computer itself with a  6809 CPU, CRTC (CRT controller), EPROM and keyboard interface. I was the one the actually wrote the control program for this board. They wanted a BASIC in ROM for the computer. So I converted my 8K BASIC to run in 8K of EPROM and it was simply called ROM-BASIC.

The next issue that caused my 8K BASIC to be slower than Microsoft's was the math. The 8K BASIC used a packed BCD (binary coded decimal) 6-byte format for floating point numbers. The Microsoft BASIC used a 4-byte binary floating point (probably IEEE format or something very similar). Binary floating point with only 4 bytes is much fasted than 6 byte packed BCD. I had a book that explained binary floating point and contained code for a math package (only the standard 4 math functions plus the necessary support functions), but was written in 6800. I converted this to 6809 with all the optimizations possible. I still had to deal with all the scientific functions. I never did get this plugged into my 8K BASIC. I was going to college at the time and that took my time. I was keeping a notebook at the time and the dates end around 1981. There were few more notes from the end of 1984/ begin of 1985 (a break at college) and a few more dated October 1986. The time for a 6809 BASIC had passed and I never picked it back up.

During the 1980's I worked part/full time for a local company developing their business software. Initially this was developed on a TRS-80 Model II in BASIC (another Microsoft variety). Around 1984, the software was converted to BasicA/GW-Basic to run on PCs, using BASCOM3 to compile the code for production. Sometime in the mid-1980's, Microsoft released their QuickBasic 4.5 an incremental compiler. I though it was such a great idea and had good promise, but upon using it, I decided that they could have taken it much further. Also, it ran programs much more slowly than BASCOM3, so development continued with GW-Basic using BASCOM3 for compiling.

Background Part I – BASIC Interpreter

I worked on my own BASIC interpreter back around 1980-1981. The first computer I used was a SWTPC 6800 (SS-50 bus computer) with 4K of memory (1977). It did not have enough memory to run either the 4K or 8K BASIC that was available. Eventually it was upgraded with enough memory to run the 8K BASIC and eventually it upgraded to a 6809 (around 1979). The 6800 machine code could not be run on the 6809 directly. The 6809 was source level compatible with the 6800, which meant the a 6800 assembly source file could be assembled with a 6809 assembler with no changes to produce 6809 machine code.

This BASIC interpreter started out as a simple conversion from 6800 to 6809. I used a 6800 disassembler on the 8K BASIC. With some modification of the output, I was able to get the 8K BASIC running on the 6809. Around the same time we acquired Microsoft BASIC for this computer, I don't remember the exact timing or whether it was for the 6800 or 6809. I do remember that the Microsoft BASIC was much faster. So I dug deeper to find out why.

It turned out that the 8K BASIC interpreter was a pure interpreter. That is it put the lines entered directly into memory as is. I did discover that it did convert the first command on a line (PRINT, IF, etc.) into an address (pointer) to an internal table that contain the text of the command and the location of the subroutine for handling the command. This was probably done for executing direct commands. But it only converted the first command on the line, not any other commands on a line (multiple statements separated by colons). For these it reverted to parsing mode for execution. The Microsoft BASIC on the other hand converted all commands, words (TO, THEN, etc.) and operators (<>, <=, etc.) into one-byte tokens. So when it ran the program, the parsing of the tokens was already performed.

At this point, I did two things to my 8K BASIC, I parsed all tokens into one-byte codes and I rewrote most of the code to take advantage of the 6809. This significantly made it faster, but still not quite the speed of the Microsoft BASIC.

What is an Interactive Compiler?

A Compiler is a program that converts a human readable programming language like BASIC into a language understood by a computer. Once converted, the program is no longer readable by a human and is not easy if not impossible to convert back to the original human readable source file. However, the compiled program runs fast.

An Interpreter is a program that directly executes a human readable programming language directly. Interpreters tends to run the program slowly since it is continuously reading and parsing the source file to execute the program. However, interpreters offer interactivity where no separate compile step is necessary and offers the ability to execute commands immediately (like for examining program variables when the program is temporarily stopped like for debugging).

An Incremental Compiler converts or compilers each line of a source file into an internal language understood by the computer as it is entered. It offers the advantages of a compiler (speed) and the advantages of an interpreter (interactivity).

An Interactive Compiler is technically any programming environment that is interactive, anything from a pure interpreter to an incremental compiler, but not a full a compiler. What I am referring to as an Interactive Compiler is one that its internal language is in the form that is easily converted back into the original source lines (though not necessary exactly as typed) and in a form that the computer can run efficiently without doing an time wasting interpretation (which is done during the creation of the internal code and not during run time as in an interpreter).