Algol 68 compiler
About 40 years ago I had been writing an Algol 68 compiler. I started it at the University of Alberta. It wasn't finished after I spent about two and a half years on it, and I decided that was enough. I has essentially a complete, functioning front end, and a fairly incomplete draft of a code generator. The whole thing was written in Algol W.
When I moved to the Mathematical Centre in Amsterdam it didn't take long for one of its directors to get wind of the incomplete compiler. He had access to an IBM 370, which was compatible with the machine I had first implemented on, so he prevailed on me to resume work on it. I agreed. I now look at that as a mistake. The facilities available weren't as good as they had been in Alberta (TSO instead of MTS, which meant slow turnaround whether I took the train to Delft every day of stayed in Amsterdam and used a 300 bps phone line.) Over the next few years I got the compiler to the point that it correctly handled about half the test set, but it really wasn't ready for serious use.
Then funding ran out, I left the Netherlands, and after that I had essentially no opportunity to continue work on it. Perhaps I could have reimplemented Algol W and then rewrote the code generator for another machine, but in new jobs I had other responsibilities.
Still, I have spent occasional sleepless nights wondering how I *should* have gone about this project.
The first thought is that I should have *started* with the code generator and the inner run-time system (garbage collection, stack management, and the most primitive I/O). There were lots of people writing front ends for Algol 68 compilers. I might have been able to glue someone else's front end to my back end if I had gone in that direction.
The second thought is that I should have gone to complete machine-independence early, rather than late. Algol W might have been a machine-independent language (or close enough to it), but it had been implemented only on the IBM 360 (and therefore also 370), and it was a much bigger language than I needed.
But the real trick is how could I have best gone about that, given the state of the art back in the early 70's when I started the thing.
I now see there were a number of options.
First start in Algol W, as I had, but implementing a small language, possibly a very small Algol 68 sublanguage, that had just the features necessary for writing a compiler. Then rewrite that compiler in its own language, taking care to produce a suitable intermediate code.
(Moving that to a new machine would involve writing a new code generator from the intermediate code, using whatever tools were available on the target machine. Ideally, the intermediate code would have enough redundancy that it could be interpreted as easily as compiled. Ideally, the intermediate code would be word-size-independent, but even if it weren't, it would still be possible to interpret it.).
The small language would have as data types unions, structs, integers, characters, references, and procedures. Most coercions would have to be explicitly coded. There would be no operator or priority declarations, There would probably be other restrictions like this in the direction of explicitness, including a few extra keywords to simplify parsing in places where the Algol 68 is almost, but not quite, ambiguous.
Full type-checking would still be done.
Making these restrictions would cut out a moderate amount of lexical scanner, vastly simplify the context-free parser, wipe out most of the coercion pass, and leave much of the final code-generator and the run-time garbage-collector intact. And this would probably have cut a year or more off total development time (measured in terms of MTS development time, not TSO development time). The system might very well have been machine-independent within two years. Although it wouldn't have been an Algol 68 compiler, it would have been well on the way, and development could have continued on almost any machine. No long-distance phone calls to Delft's computer would have been needed.
There are quite a few techniques I can know of now that might have further accelerated development if they had been known back then. But none of what I've described above involved any technologies I was unfamiliar way back in the early 70's. I could have made the decisions I've just described way back then, except for one important fact:
Back then I lacked the wisdom to go about it this way. The wisdom to get something usable working as soon as possible as opposed to the complete thing sometime later.
-- hendrik
When I moved to the Mathematical Centre in Amsterdam it didn't take long for one of its directors to get wind of the incomplete compiler. He had access to an IBM 370, which was compatible with the machine I had first implemented on, so he prevailed on me to resume work on it. I agreed. I now look at that as a mistake. The facilities available weren't as good as they had been in Alberta (TSO instead of MTS, which meant slow turnaround whether I took the train to Delft every day of stayed in Amsterdam and used a 300 bps phone line.) Over the next few years I got the compiler to the point that it correctly handled about half the test set, but it really wasn't ready for serious use.
Then funding ran out, I left the Netherlands, and after that I had essentially no opportunity to continue work on it. Perhaps I could have reimplemented Algol W and then rewrote the code generator for another machine, but in new jobs I had other responsibilities.
Still, I have spent occasional sleepless nights wondering how I *should* have gone about this project.
The first thought is that I should have *started* with the code generator and the inner run-time system (garbage collection, stack management, and the most primitive I/O). There were lots of people writing front ends for Algol 68 compilers. I might have been able to glue someone else's front end to my back end if I had gone in that direction.
The second thought is that I should have gone to complete machine-independence early, rather than late. Algol W might have been a machine-independent language (or close enough to it), but it had been implemented only on the IBM 360 (and therefore also 370), and it was a much bigger language than I needed.
But the real trick is how could I have best gone about that, given the state of the art back in the early 70's when I started the thing.
I now see there were a number of options.
First start in Algol W, as I had, but implementing a small language, possibly a very small Algol 68 sublanguage, that had just the features necessary for writing a compiler. Then rewrite that compiler in its own language, taking care to produce a suitable intermediate code.
(Moving that to a new machine would involve writing a new code generator from the intermediate code, using whatever tools were available on the target machine. Ideally, the intermediate code would have enough redundancy that it could be interpreted as easily as compiled. Ideally, the intermediate code would be word-size-independent, but even if it weren't, it would still be possible to interpret it.).
The small language would have as data types unions, structs, integers, characters, references, and procedures. Most coercions would have to be explicitly coded. There would be no operator or priority declarations, There would probably be other restrictions like this in the direction of explicitness, including a few extra keywords to simplify parsing in places where the Algol 68 is almost, but not quite, ambiguous.
Full type-checking would still be done.
Making these restrictions would cut out a moderate amount of lexical scanner, vastly simplify the context-free parser, wipe out most of the coercion pass, and leave much of the final code-generator and the run-time garbage-collector intact. And this would probably have cut a year or more off total development time (measured in terms of MTS development time, not TSO development time). The system might very well have been machine-independent within two years. Although it wouldn't have been an Algol 68 compiler, it would have been well on the way, and development could have continued on almost any machine. No long-distance phone calls to Delft's computer would have been needed.
There are quite a few techniques I can know of now that might have further accelerated development if they had been known back then. But none of what I've described above involved any technologies I was unfamiliar way back in the early 70's. I could have made the decisions I've just described way back then, except for one important fact:
Back then I lacked the wisdom to go about it this way. The wisdom to get something usable working as soon as possible as opposed to the complete thing sometime later.
-- hendrik