Retrocomputing project: an Algol W compiler.

I've begun writing an Algol W compiler for historical reasons1?. One reason: Algol W was the first language to treat records as data types, that's a fairly significant step. There are open source implementations of Algol 605? and Algol 686? but none yet for this third dialect, Algol W. --GlynWebster

What is Algol W?

Algol W is one of Nicholas Wirth's first language designs2?. Algol W is Algol 60 with string handling, complex numbers and dynamically allocated records, with some of Algol 60's syntactic idiosyncrasies stripped away. It kept Algol 60's "call by name" argument passing style, and is the probably the only other language to have used it. Nicholas Wirth presented it to the committee that was designing the successor to Algol 60, but it was rejected as a design basis in favour of a set of vague ideas that later became Algol 68. Which was a shame really, because Algol 68 turned out to be so difficult to implement it never really got off the ground, so programmers were left slogging along with Fortran and Cobol for long time.

The recollections of Algol W that I can dredge up from Google News's archives seem evenly split between fond memories and frustrations with the original compilers' limitations. In the middle of the primal Goto Considered Harmful flame war one Algol W compiler gave the warning message "Is this goto really necessary?" for every GOTO, and there was no way to turn it off. (I don't think I'll do that. None of you grew up abusing GOTOs, did you?)

Why did Algol W disappear?

It was not Pascal. Then it was not C. OS/360 is not that popular a platform anymore. Algol W was rejected as the template language for Algol 68. Wirth went on to invent Pascal, which superseded Algol 60 and Algol W in schools. The Stanford Algol W compiler seems to have had annoying limitations. And there was that whole "Is this goto really necessary?" thing. Historical reasons, like I said :-)

! A little Algol W sample

comment statements can be procedure parameters; begin

procedure vectoroperation (integer j; integer value n; procedure p);

begin

j := 1; while j <= n do

begin

p; j := j + 1

end

end vectoroperation;

integer i; real array a, b, c (1::10); real prod;

(initialize a and b here)

vectoroperation (i, 10, c(i) := a(i) + b(i)); (c is now the sum of vectors a and b)

prod := 0.0; vectoroperation (i, 10, prod := prod + a(i) * b(i)); (prod is now the product of vectors a and b)

end.

The compiler

I intend to make my implementation compatible with the Stanford Algol W compiler4?. That seems to be the one that was most used, and it's one I have documentation for.

I'm writing in standard C, and the compiler will generate Gnu C code. Algol and Pascal-like languages can be translated into Gnu C simply and directly because of GNU's extensions to the C language. (They fit so well to this task that I think this is the very reason Gnu added them.) Statement expressions, nested functions, variable length arrays and inline functions are the ones Algol W will need. Algol W programs need a garbage collector. I'm thinking of using the Boehm collector10?. I'm writing in C just to reduce the number of tools necessary for someone else to get the compiler going9?, although I'd prefer to be using Objective Caml for something like this. I might use Splint7? annotations to try to take the curse off it.

I was thinking of modifying the GNU Marst5? compiler to accept Algol W but Algol 60 and Algol W are enough different that I think the Gnu C route might be easier.

Extensions. I don't intend to extend the Algol W language. (If I want a nicer language I should to be designing a modern one of my own.) But the compiler will allow inline C code; this is for writing the standard library and interfaces to existing C libraries, not general Algol W programming. And I intend to lift limits placed on the language by the Stanford compiler, nowadays we have the privilege of working on much better computers.

Progress

I have a Flex and Bison lexer and parser written, and buffer and symbol table modules to support them.

I have worked out how to translate the most un-C-like features of Algol W into Gnu C. (I didn't want to discover it was impossible at the last moment!)

I have translated most of the Algol W manuals from a partially OCRed photostat4? into LaTex?, but I've decided to stop until I can get permission to republish it3?. I was thinking of writing the compiler in literate style8?, as a series of annotations and appendices to the reference document, but now I'm not so sure - it would be copyright trouble if I wanted to release the compiler under GPL.

Tasks

Parse tree

The part where mallocs fly all over the place and the frees struggle to keep up.

Type analyzer

I intend this thing to be a compiler rather that a translator, so no errors should crop up the C compilation stage.

C code emitter

Translating the parse tree to Gnu C code. The translation scheme needs to be well documented because programmers can include inline C blocks in Algol W code. They will need to know how the surrounding compiler-generated C code is constructed.

Algol W standard library (a.k.a. the prelude)

This can be written in mixed C and Algol code. I'd like to do two versions of this: one using native data types; one using IBM 360 types (EBCDIC characters and a different floating-point representation) so old numeric programs give exactly the expected results, and images of old data card decks can be read.

Algol W manual

Find and author and ask permission to republish. I assume they're all still alive. Somewhere. (Meanwhile: does anyone know how to get pretty tables out of LaTex??)

Manual and man pages

Of course.

1? This isn't so odd, people restore old cars and computers, also go look at the Retrocomputing Museum (http://www.pdc.kth.se/jas/retro/retromuseum.html).

2? See http://www.inf.ethz.ch/wirth/projects.html

3? the editor went on to be the manager of the team designing the Alpha CPU chips, and now I can't find his email address. Funny that.

4? Stanford University Technical Report CS-TR-71-230.pdf [3.5MB?, "This manual refers to the version of the Algol W compiler dated 1.6 January 1972". It has a formal description of the language and a manual for its standard library is in the back, which is good. (This document was a print-out that sat in a ring-binder for years before someone scanned it with some weird OCR system that starts with a bitmap of the page, then replaces as many characters as it can with PDF text after guessing at their fonts. The system must work well on laser-printed documents, but electric-typewriter and ball-point documents seem to be just on the point were its effectivness begins to break down. The result is readable but quite weird in places.)

5? GNU Marst (http://www.gnu.org/software/marst/). GNU Marst is 100 pages of very clear, simple C code, heavily and helpfully commented. I've printed it out and I'm reading it in bed. (Have you tried this? A really good piece of code is readable, and enjoyable. I'm sure I'm learning things. There are several signs of the author being an "experienced" hacker: he refers to RAM as "main core" for example :-)

6? Marcel van der Veer's Algol68G (http://www.xs4all.nl/jmvdveer/algol68g.manual.html) and Sian Leitch's Algol68toC port (http://www.sleitch.nildram.co.uk/algol68.html).

7? Splint (http://lclint.cs.virginia.edu/).

8? Probably using Nuweb (http://nuweb.sourceforge.net/), since this project requires a mixture of languages. See http://www-cs-faculty.stanford.edu/knuth/lp.html for more about literate programming.

9? Someone please talk me out of this.

10? Boehm garbage collector (http://www.hpl.hp.com/personal/Hans_Boehm/gc/). Mostly because I don't yet know how to write anything but a reference counting garbage collector, which I don't think will do. Algol W should be easy-as-it-gets to write a garbage collector for because only records are dynamically allocated, any book-keeping fields necessary can be secretly added to those.

This is a subpage of Projects.