Relay-Version: version B 2.10.3 4.3bsd-beta 6/6/85; site seismo.UUCP Posting-Version: version B 2.10.2 9/3/84; site genrad.UUCP Path: seismo!harvard!talcott!panda!genrad!sources-request From: sources-request@genrad.UUCP Newsgroups: mod.sources Subject: A BASIC interpretor (part 0 of 4) Message-ID: <987@genrad.UUCP> Date: 30 Jul 85 17:33:19 GMT Sender: john@genrad.UUCP Lines: 92 Approved: john@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.