I'm trying to flesh out the articles related to BASIC on the Wiki and on AtariWIki. As part of this I've been delving into historical BASICs and others that I was not familiar with. And here's some ideas for everyone to chew on:
1) line searching
Atari BASIC infamously had to search the entire program to look for a GOTO/GOSUB target, while MS-derived BASICs used a simple trick of starting at the top only if the line number was smaller than the one you were reading.
Now I would say that in most programs, most GOTOs tend to be short, maybe a dozen lines in either direction. So in the case of a forward jump, moving forward from your current position is likely to be efficient, but jumping backward from it is not, it has to start at the top.
Why? Because the original Altair BASIC, on which everything is patterned, had a forward pointer only, so there was no way they could scan backward. So you could only start from where you were, or the top.
Now one solution would be to cache all the line numbers you encounter in a GOTO/GOSUB, but that requires lots of memory even if they are never called at runtime. Another solution would be to put a backpointer on every line as well, but that would use even more memory, and do so for every line instead of just the interesting ones.
So what about a trailing XXX lines cache? That is, as you roll through the code you keep track of the last, say, 16 lines, as back pointers. Now on a backward jump, you can scan that list first, and if you don't find it there, start at the top. This is likely almost as fast as full caching, because if you're not jumping back a little, you're likely jumping back a LOT, so a start-from-top would be the right one anyway.
This would require much less memory than the other solutions, yet likely offer almost all the same speed.
2) variable lookup
I'm not exactly sure what Atari BASIC does here, but I assume its the same as Altair/MS in that there is a list of variable names and their memory locations that it scans when it encounters a variable name in code.
One of the really fast BASICs is BBC BASIC and I was curious why and got some great answers. One of the reasons is that instead of one big list of variable names, it has a bunch of smaller ones, I think one for each possible starting letter.
I think a great improvement on that would be a shorter hash table, say with 16 entries. This can be hand-shuffled - there's a whole lot of I, J, K and X, Y, Z's in most programs, so maybe they get their own list each, and then sort out the rest into four groups of five letters each, ABCDE, FGHLM, etc. Now you have 10 lists, you can easily figure out which one to start in, and it should be really much faster.
BBC BASIC also had a completely separate list with fixed entries for every possible integer variable. This makes sense if you think about it - you use these for speed
3) integer math package
One of the great mysteries to me is why the later MS BASICs had integer variables but did not have a separate math library for working with them. Looking into this, it seems the only interest here was saving memory - they did not see people actually doing math on these, but if you used them for indexes and such it could save you enough memory to make up for the slightly larger interpreter size needed to parse them.
Of course, this seems odd in retrospect. After all, if you use them as intended, you're likely going to do a LOT of math on them, specifically a +1 in FOR loops. Ok, so we wouldn't put SIN() in the library, but increment, decrement, +, - and maybe even * and / seem like no brainers. And of course a trunk that just does a NOOP would likely be useful too, and perhaps a RND%(), and I'm sure you can all think of others.
Now FastBasic does this naturally, but for the other Atari BASICs out there do not appear to have these. Given the savings in code size (or at least memory use) it would seem such a package could be implemented within the 8k limits, a statement I base on the fact that MS's size increased about 1000 bytes with the addition of both 9-byte FP and ints.
Aside from pure-int BASICs, like FBI, is there a A%-capable BASIC on the Atari? Did the MS BASICs have this?
4) cool control structures
This is a little more esoteric, but cool nonetheless. DEC's line of BASICs derived from Dartmouth BASIC, which is pretty similar to MS. But they then added a feature that did not make it into MS, and I think it's worth mentioning.
In BASIC-PLUS, most commands could be followed by a logical operator. So for instance:
10 FOR I=1 TO 10: A=A+A: NEXT I
could be written this way:
10 A=A+A FOR I=1 TO 10
Now what's the difference? At first I thought nothing, but then some of the smarter people convinced me this might offer a great advantage in terms of constructing the loop in the resulting interpreted code. For instance, there can only possibly be one operation in the loop, which makes the construction much simpler. Whether this offsets the increase in complexity of the parser I cannot guess. But there were other variations...
A=A+10 WHILE I<100
A=A+10 UNTIL I>=100
These are basically different variations on the FOR, but simpler to read. The second one... I'm not sure this really clarifies anything compared to the WHILE.? There's also the one-time versions of the same:
A=A+10 IF A<>100
A=A+10 UNLESS A=100
Again, I question the need for the UNLESS version.
I still haven't decided if these are a good idea or a distributed cost.
Edited by Maury Markowitz, Thu May 17, 2018 10:45 AM.