Personal Technical Projects

This page is especially under construction. There should be a lot more listed as I decode it from my archives. It's a matter of incompatible file formats, with files dating back all the way to the sixties.
language design
I'm currently trying to work out some ideas for a programming language. I'd like to try to combine the low- and high-level nature of a systems language like Modula 3 with constructive type theory. So far, little of use has resulted, but very loose drafts, frequently being revised, hang out in this language design tryout area. NEW: There's some exposition about this project in here. That previous link needs to be revisited.
Algol 68
An incomplete Algol 68 compiler, written in Algol W. Its source code can be pulled from the monotone repository at by the following shell command:

mtn pull \*

I started the project at the University of Alberta in 1972. I got a fair ways into that compiler in the two years I spent there -- I got the front end working, but not the code generator.

In 1975, at the Mathematical Centre in Amsterdam, I was persuaded to continue work on the compiler, at the Mathematisch Centrum. This was a mistake, because the resources available were far from adequate -- using a IBM mainframe running an IBM OS/370 with limited TSO at the other end of a 30 character per second phone line. I got much less done on the compiler in those four years than in two at the University of Alberta.

What I learned from this project is that the coding strategy for a large project should yield useable, albeit incomplete results, as soon as possible, even if that implies that significant components have to be replaced later. This yields crucial feedback in the form of early user experience, and the user community can provide encouragement and support toward completion. In my case that could have been an implementation of a small, but pithy sublanguage, which could well have been more appropriate than Algol W as implementation language.

I still tinker on it occasionally, but motivation is lacking, because I deeply suspect that no one is really interested in using it any more.

An idiosyncratic dialect of Lisp. It was written in a subset of itself, and bootstrapped using Bill Waite's Stage2 macro processor. Bill Waite has called this the most impressive abuse of Stage2 he had ever seen -- single macro calls thousands of characters long. Stage 2 is extremey easy to implement. IT was appropriate because it makes sure that parentheses are matched in macro arguments -- and parentheses are almost the only syntactic structure in Lisp.

One feature of Lithp that I found very convenient was purely notational: the abiluty to linearize lists with sublists as last element. (A B C (D E F ( G H I))) could be written (A B C / D E F / G H I). At first is seems to be just a way of eliminating parentheses (which diehard Lispers refuse to do, apparently on principle). But it enables one to write readable if-the-else chains without using 'cond' to obviate nesting. And (given let clauses like (let a b c) instead of (let((a b)) c) ) you can comfortably mix let clauses into with the if chains.

A type-theory-based programming language/verifier. It has been used to verify small programs, like merge-sort. It was written in an obscure dialect of Lisp. I ran into problems back in the 80's with the size and speed of the machines and software I was using. Today, that should not be a problem. If I were to resurrect the project, I'd probably do it with one of the modern compiled dialects of Scheme or Ocaml, instead of my homebrew Lithp system. But back then it was a matter of making do with what was available, not what I wanted.
A recursive-descent processor. It includes a parser, a code emitter, and a tree-transformation engine. It has been used to implement itself in eight levels of bootstrapping. It turns out to be difficult to debug complicated systems of tree transformations.
Anal and Parse
A rather sophisticated LR(1) and NSLR(1) parser generator. Synergy between these two parsing techniques produces a parser generator that handles grammars that neither LR(1) nor NSLR(1) can handle on their own. Parse interprets the parse tables produced by Anal, and contains a rather inefficient attribute evaluatino technique. Versions of this pair of programs exist written in Pascal and in Modula 3. The Modula 3 version is just a rote translation of the Pascal version, mostly performed by machine, with a lot of hand-editing afterward. It really ought to use the object-oriented facilities of Modula 3, but it's more important to replace the attribute evaluator with something that works an order of magnitude or two faster. A very early version of Anal (written in Algol W, no attributes, SLR(1) only) was used in the development of the Algol 68 compiler mentioned above.
A tech demo, written in Java. It maintains a parse tree and allows a separate editor perform edit operations on the tree itself, such as insertion and deletion of characters. Of course the data structure for parse trees can represent both valid and invalid parse trees. After each edit operation, the tree is reparsed, using the old tree as the text to be parsed and as a cache to avoid unnecessary work. The demo uses parse tables constructed by anal above, and has been tested on a grammar describing text with properly nested parentheses.
Game components
I have a river landscape generator, written in Modula 3. It's a not quite hierarchical not-quite tree of square tiles. Half the levels in the hierachy are tilted 45 degrees from the others, so that diagonals in one level correspond loosely to edges in the next. Have a look at the code, and its description. There's a screenshot here.