Thinking of one other Microcomputer “back then” that compiled what you entered, the Jupiter Ace. Unlike all others this was programmed in Forth. The system was such that when it compiled a new word it threw away the original text definition… Because the de-compiler was good enough.
-Gordon
Here is the Software Technical Manual: https://archive.org/details/grundy-newbrain-software-technical-manual/page/158/mode/2up Page 159 is briefly introducing BASIC and mention the compilation. I will go through some magazines I own and will come back here with some more details about the compiler.
Also, the computer was originally designed with just 2kB or RAM (the project started back in 1978). At the end it shipped with 32kB (and is directly expendable up to 2MB).
There’s even some more detailed information on the process on pages 165-170.
Apparently, the compilation is run as each line is encountered on execution (as opposed to compiling the entire program at once), more like caching the parse result for reuse. So every line has a line number, a pointer to a source area and a pointer to the object code (which is initially zero). As this is done per line, there isn’t much of a penalty for caching the parsed representation and purging object code on memory pressure should be uncritical. A nice system!
The source representation is actually more faithful to the original input than with most versions of BASIC, as, e.g., “?” and “PRINT” are represented by different tokens while pointing to the same routines. (On the other hand, there seems to be some positional logic involved, as well, as “LET” and “NOT” share the same token.)
That said, my built-in parser in my not-so-new-brain has difficulties parsing the following (from p. 165):
There are two sets of tokens; one set refers to initial keywords, the second set to other keywords.
Is this second set meant to address the two tokens used for “?” and “PRINT” (where one is the original token and the other one is understood as an alias), or is there more to this?
As I understand it, initial keyword is the one right after a line number or right after a colon. That would make sense using their example of the code 128 being both, LET and NOT (NOT as an initial keyword does not make much sense).
Slightly related: one of the 4th yr students in the year before me did his final year project on modifying our main system compiler to embed the source code along with each statement, both for use with a debugger, and for recovery in case the source was lost. I thought it was a great idea but ironically no copies of it have been preserved 
Thanks! Somehow I just remembered another example - the Basic of the ABC80. Perhaps see this thread
Luxor ABC series of Swedish computers
Nice story!
It’s an odd thing, that 32k is really a lot of RAM, in a context where machines might have 4k or so. But then along came 48k and 64k machines and it doesn’t seem so much.
Basic how ever could pack n characters per word the older computers. The PDP 8
Basic was good example of packing big things into small spaces. Basic and Focal were
ment to be the programable calculators of that era. Basic was designed for timesharing
where only the data segment needed to swapped out, and I/O was never faster than 110 baud. You could run say 5 users while your “hello world” program printed “hello world”.
Understanding this about the old Basics was a little disorienting. When I was learning the language as a kid, it was described as an interpreted language, but the explanation was bonkers, saying that your code was translated to machine code “line by line,” before it was executed. It was only many years later, when I read up on how to look at memory, and looked where the tokenized code was located, that I realized it was as you describe, and not that different from what’s done with languages that have run on VMs (compiled to bytecode, then interpreted).
It was confusing, because “machine code” was also used to describe programming in hexadecimal with opcodes executed directly by a hardware processor.
I think the distinction that’s interesting to me is how much work is done once, and how much work is done many times, when for example there’s a loop in the program. Tokenisation as found in most 8 bit microcomputer Basics is a bit of a saving in the parsing: once the keywords are tokenised, it’s straightforward to distinguish variable names and constant values from the various meaningful single characters. But the finding of variable storage, or the evaluation of expressions, or of constants, or the finding of line numbers, is still done (in those basics) each time some code is encountered.
There could I think be an intermediate form which is pure byte code, or direct or indirect threaded code, as we find in Forths. There are implementation choices here, as to whether the digested form sits alongside the original source, or after it, or interleaved within it, or replaces it. (As noted, replacing the source is memory efficient but may be lossy.)
There is often the “usual” time vs. effort, or Time to Market so adding pressures like that often results in short-cuts…
Also the extra effort of writing a compiler vs. interpreter - even if that interpreter uses some sort of tokenisation.
My own experiences suggest that if you are well versed in the art of compiler writing then writing a BASIC compile ought to be fairly straightforward - even compiling it on a line by line basis ought to be relatively easy. I’m not a natural compiler writer so when I looked at this, I decided to opt for the “traditional” tokenisation approach, but took it to the limit. I’m fairly sure this is how some FORTRAN compilers worked way back - e.g. on the PDP-8 - One compiler I tried to use produced a 2-part output, one was a form of tokenised code, the other was the symbol table, you then needed a separate run-time tape/library loaded before you ran your code.
Latterly, in my application I decided to try to cache some of the intermediate steps at run-time - so each expression, even though it’s tokenised is parsed at run time by a fairly traditional “Shunting Yard” approach into an RPN stream which is fed-into the RPN evaluator - I decided to cache the shunted RPN - created a token for it and stuffed it into the symbol table - so subsequent passes over that line of code took the already RPNd version. It did improve execution speed for a slight overhead the very first time that line was executed - so big linear functions were a bit slower, but loops, etc. much faster.
Where do you draw the line and make the jump to a proper compiler though?
Going back to the micros of the late 70s/early 80s… It’s amazing a lot of the micros of that day actually made it to market - although there were a lot of good (and probably overworked!) engineers on the case…
-Gordon
Could suggest a number of good compiler writing book used during your time, 60,70,80 or you know about
In the end, it’s probably about whether we store the evaluated path in some kind of internal representation for later use, or not, regardless of the level or at what time we do it.
Something I was somewhat stunned to see, though, was, on a machine code level, how much of the time is lost not in the parsing process proper, but in how often values residing in registers have to be stored away and retrieved again, as we switch between parsing and execution. This is maybe even more true, the finer the granularity of the clause/instruction level, e.g., with byte code on a processor with just a couple of registers.
(We must keep track of the code we’re inspecting, maybe stored inside a larger word as a vector, we must extract it, evaluate it, then jump to the execution, just to pick up where we left the main parsing loop, again. Each of these steps involves dropping and restoring registers, which easily amounts to more operations than the evaluation (probably just a jump table) and/or the execution itself. The smaller the granular units, the more often we have to switch, the higher the penalty.)
So byte code becomes really a viable concept as the number of registers increases – and I wouldn’t recommend it for, say, a 6502. With a small processor, you either want large atomic units or proper machine code.
There are really no good Compiler Books before the 1980’s, for the simple reason
most computers where too small for compilers to run on them. 32Kb is needed for a
good sized symble table, Most where language
specific like ALGOL Z ported to the HAL 7000 computer. Most books give a great introduction but never seem to cover the little run time details.
I have yet to see
a good example of how displays work yet for ALGOL like laguages. I rather think ,nested
variables are more problems than they are worth.
I use abebooks https://www.abebooks.com/ a used online bookstore for all my computer science books.
I like “BCPL the language and its compiler” , “Assemblers,Compilers, and Program Translation”, “Compiler Design In C”.
Maybe Niklaus Wirth’s Compilerbau (Compiler Construction). I’m actually not sure about the date, as the preface is signed 1979, but my German edition comes with a copyright of 1986, and the English edition points to 1996. Notably, the book has been constantly revised (starting with the third edition it switches to Modula II as the host language). However, it just covers the basics and the idea of incremental compilation, featuring the famous T-grams (update: apparently not in the English edition). – Not exhaustive, but an important book.
For Algol, this is a bit systematic as no discription covers the implementation of libraries, as far as I know. But this also spills over to derived languages, like Simula67, where there is no description of how this is actually implemented (there is just writting to buffers and a routine to flush said buffers, but that’s basically it). Arguably, Simula67 never reached that level of implementational refinement that it would matter…
we compiled things like fortran, Basic plus 2, etc in 16K user space on PDP-11’s
Symbol tables can be written to and read from disk during the process.
Now what computer compiled at 1 card per minute again?
Slow compile times was because of the lack of real memory, disc space,
and slow OS’s. Virtual memory was just that, slow but big.
This may of pushed the development of one pass compilers (C is two pass+)
but that just made things much slower at run time, like pascal.
Wirth likes to revise a new language every few years,why not do it right
the 2nd time, PASCAL or MODULA II, or ADA all gone now for OBERN.
I really think a complier is better multipass, parsing and error checking on pass number 1.real compiling pass 2. Nobody seemed to want to create a easy to compile language
and no wierd ; rules, like a null statement or no ; before a end.
The 80’s things got better, when you had ample memory for things like compiling.
After that everybody went to 32 bit cpu’s, and langauge development stopped
as changing CPU’s was the FAD for a while. 286, now 68000,now 486, now RISC,
now 586, divide bug now other brands, now ARM, now DEC’s RISC, now the CHEAP
686…
As a side note. I don’t like revised editions. it needs to be a new title for major changes.
The real rule for ;'s is statement | statement ‘;’ statement
nowhere does it end or terminate a statement.
I’m not clear on how compiling could save memory compared to interpreting. Is the source code not stored in RAM? Maybe makes sense of they come with discs or something.
Many BASIC’s tokenize the input for keywords. GO TO 52 {CR} becomes
{ GOTO} 5 2 { EOL} . This saves one or more characters per keyword.
This is actually a good point. In this case both, the source and compiled versions of the program, are in the memory.
Depending on the format of the compiled code, it may be possible to de-compile it to get back something equivalent (maybe even identical) to the original source code.