BASIC JIT Compiler?

[dolomiah]

whartung raises the very valid points about why BASIC interpreters have often used the line number rather than the line address i.e. to enable programs to be modified and continued. Mind you, I have personally not found this to be an often used scenario - although I was never a professional BASIC programmer, just a teenager in the 80s writing programs for personal use.

Regarding the HP41 approach to labels, I didn't know that, but it turns out the interpreter I have built uses a similar approach in terms of how it calls procedures (subroutines). I have a variable name table and variable value table (similar to Atari BASIC). The name table merely contains the actual name of a variable or procedure. The value table then contains the corresponding value which for a normal variable of course can change and be updated by during run. For procedures, the value table contains the line address of the procedure start. Whenever the program is started, the interpreter zeroes out the line address of all procedures. The first time a procedure is invoked, the interpreter will do a normal line search to fine the address - and that is saved in the value table. Subsequent invocations of the procedure are much quicker because the value table already has an address to go directly to.

So the above approach to procedures, plus tokenisation of keywords, constants, and variable names (as per Atari BASIC they are tokenisaed to be an index in to the VNT and VVT) really makes a speed difference over pure interpretation of each line of source as originally entered by the programmer. It's not really JIT (because the tokenisation is done on entry of a new line of program), but it's certainly a form of compilation in to an intermediate format for the run-time to execute more quickly than pure source - so in that sense not far from the Java and .net paradigm.

[barrym95838]

whartung wrote:

... Also, don't forget, many BASICs allowed the program to halted and then CONTinued from where they left off, even if you changed the code. So it's a very real scenario that a running program is stopped, changed, and then continued.

I messed around with a few different BASIC interpreters back in the day, and none of them allowed a CONT after a program line was added, deleted, or edited. Variables could be examined and changed, but not the program itself, or you would get a CAN'T CONTINUE error.

Quote:

The Atari BASIC XL FAST command demonstrated how expensive the pre-calculation of these values was with a noticeable delay at the start of programs ...

A clever command line interpreter could make those adjustments during program editing by scanning and correcting all of the existing pointers after each line was entered and tokenized, instead of waiting for FAST to do it at run-time. The total time spent scanning would increase (due to repetition), but the delay at the start of execution would be completely eliminated. I know that I wouldn't mind a short delay after entering each program line before the prompt returned, if the pay-off was faster execution. Klaus was exploring similar ideas with the VTL-02 interpreter, and I was thinking of doing some exploring myself, but I decided that keeping the entire interpreter and editor size under 1 KB was more important at the time.

Mike B.

[whartung]

barrym95838 wrote:

A clever command line interpreter could make those adjustments during program editing by scanning and correcting all of the existing pointers after each line was entered and tokenized, instead of waiting for FAST to do it at run-time. The total time spent scanning would increase (due to repetition), but the delay at the start of execution would be completely eliminated. I know that I wouldn't mind a short delay after entering each program line before the prompt returned, if the pay-off was faster execution. Klaus was exploring similar ideas with the VTL-02 interpreter, and I was thinking of doing some exploring myself, but I decided that keeping the entire interpreter and editor size under 1 KB was more important at the time.

Oh, I think I disagree. On a large program, having lag for each line would be dreadful, and it's a noticeable lag, it's not sub-second.

Since you had control over when FAST was run, you could put it after the "Loading…" screen, for lack of a better word, so it would be lumped in with the general delay that happens at startup anyway.

[GARTHWILSON]

GARTHWILSON wrote:

A few years later I stepped up to the HP-41 calculator. <snip> As I understand it however, each jump to a label (except indirects) also keeps an address field which is hidden from the user. When the program is run and there's a jump to a label, the calculator looks where the address field points, and looks to make sure that yes, that's the label. If so, time is saved. But if it's not, it goes searching. When it finds it, it records the address back at the jump instruction, to save time in the future. I think this happens for both local and global labels. The difference in speed is definitely noticeable.

I should have added that when it searches for local labels, it starts from where the program counter points at the moment, and only searches the current program, whereas when it searches for global labels, it starts the search from the end of program memory, searching in all programs, not just the one you're in. Global labels should be unique, and they make it possible to call a subroutine in another program, since the search is not limited to the current program. Since searches for local labels start where the program counter points at the moment, you can re-use local labels as many times as you want, like for a sequence of short conditional forward branches. Hopefully this gives some ideas.

[repose]

Some good points in here. I worked on this myself.
I wanted it to be fast, so I started with a minimal runtime that could do loops, variables, and arithmetic. Tokens were dispatched to subroutines taking care of each command, numbers were stored as actual numbers instead of strings, branches were compiled directly to machine code.
I remember being happy writing my first loop directly in tokens and it working.
I found a simple way to parse code, without using the textbook LLR parsers etc. I guess you'd just call it a custom parser, but it could handle any numeric expression. I basically converted infix to prefix, that means an expression was broken down to a stack type sequence of the calculations needed in order.
I intended to make a compiler compiler so you could list your own keywords and supply assembly subroutines to go with them, or even compiles basic ones.
I thought with an extensible language, I could use the language itself to extend it and thus emulate all other basic flavours, and be compiled.
That was my dream, but I only got as far as a working runtime with variable management, fast arithmetic, and arithmetic parsing.
Would love to work on that again.
(I lost it, but may have posted it somewhere as a file called bcomp).

[barrym95838]

What system was the host for your bcomp, repose?

Mike B.

[repose]

I wrote it on c64. Since I also owned a 128 and Atari, I had interest in porting to those systems as well.

There's a small list of basic compilers here:
http://commodore.software/downloads/cat ... -compilers