A BASIC interpretor (part 0 of 4)

[sources-request at genrad.UUCP]

Mod.sources:  Volume 2, Issue 22
Submitted by: ukma!david (David Herron)

About a month ago I posted a response saying that I had a BASIC
interpretor I'd written (that it wasn't a working interpretor)
and that I'd post it if anybody wanted to debug it.  Well, something
in the offer must have sounded tempting since I got about 30 replies
all saying yes.  So here it is.

Let me give a little bit of the history first.  About 3 years ago
I was taking a course entitled something like "Minicomputer Management".
Which, it was basically a smoke screen behind which to introduce students
to the wonderful world on Unix.  (On 2 PDP-11/23's (not 23+) running
Version 7 (now 2.9BSD)).  Two weeks before the end of class we were
assigned to write a BASIC interpretor.  Nobody else finished it
but me, but it took me a year and a half to get a working version.
(I spent a lot of that time playing with different ideas for parsing).

I had it working.  But it was in two parts.  A parser which turned
the BASIC programs into a stack based intermediate language, and
the interpretor for the intermediate language.  There was no immediate
type in program and run it capability.  You had to run ed, write the
file, save it, convert it, THEN run it.  I really wanted to have
the two parts in one piece, so I started improving it.

Unfortunately, about half way through improving the program I got
hired for my current job.  (One of those student slave labor deals).
And I never finished it.  I don't know the status of the code I am 
sending.  It may be code from the first iteration, or it may be 
from the current (now a year old) iteration.

There are three directories under here, as follows:

	bs2	This has sources which will make the two part
		translator/interpretor I described above.  But I
		don't know if the files will compile into a runnable
		program or not.
	bstest	Some basic programs and the output produced by the
		translator.  It should help you in understanding
		what the intermediate code should look like.
	newbs	This is where I was working on the new interpretor.
		I was trying to make bsgram.y produce EITHER
		the ascii intermediate file, or an incore version
		that could be run immediately.  I may also have
		been trying to clean up the grammar some.

The intermediate language is intended to be much like FORTH.  It is not
a full FORTH of course, butis much simplified.  I picked this route
partly as a path of least resistance, and partly to try out an
idea.   (I had a good description of how to build a FORTH, if you are
interested look for the article in 1981 or 1982 of the IEEE Computer
magazine).  Around that time I had an inspiration on a better way to
implement languages.  I had recieved a strong lesson in the amount of
work that was needed to implement a language on a new piece of
hardware.  My idea is similar to the P-code method of implementing
Pascal. Design a machine-independant intermediate language which is
simple yet provides facilities needed by a language interpretor.  You
would save a lot of time in porting languages to new hardware this way,
especially if the intermediate language was easy to interpret.  I
already knew that RPN was easy to interpret having worked with one
previously.   And I could show myself that it was easy to convert an
expression tree to an RPN expression.  So this looked good.

The idealistic form of this interpretor is simply an array of pointers
to procedures which are called in order.  In actuality arguments to the
routines are interspersed with the pointers.   The comments in the code
try to make this clear.  This is (currently) the only documentation,
and in some cases the code and the comments may not agree.  Remember
that this is a work in progress that was never completed.  (But now
that I'm thinking about it again, I see so many better ways of doing
things,  I  may just give it another go.)

A quick word about efficiency and I'll get off this subject.  My
standard quickie benchmark is the nearest equivalent to:


		 10 FOR I = 1 TO 10000 
		 20 NEXT I


I ran this on both a TRS-80 Color Computer (it was handy) with floating
point arithmetic, and my interpretor running on a LSI-11/23 with
integer arithmetic.   They both took about 15  seconds to run this.
As a first attempt I am pleased to have showed so well against seasoned
professionals.  On the other hand, considering the differences in data
types, and CPU speeds, should have given a two to three times
difference.   (In the favor of the LSI-11).  There is one GLARING thing
I should do when (if) I do this over.   I should not have the
interpretor doing procedure calls for each instruction, but should have
the main loop be a large switch statement.  This was an early design
decision that I now regret.  I went with using the procedure calls
because it seemed that I would end up with a less monolithic system.