[TUHS] Regex archaeology

[Clem Cole via TUHS]

Will, CCing COFF and SIMH which is really where this question belongs and
BCC: TUHS.org

On Tue, Sep 1, 2026 at 9:21 PM Will Senn via TUHS <tuhs at tuhs.org> wrote:

> All,
>
> I've been doing some experimentation to test my language, aiki, a small
> interpreted language. Most of my pressure tests have begun to move
> toward emulation because emulating machines is challenging in an
> interpreter (can you say sllllloooooowwwww?). Anyhow, when I had the
> regex implemented by my outsourced team (claude & chatgpt), I lacked any
> comprehension of how it actually worked beyond textbook level (which is
> to say, names of things that I didn't truly comprehend). So, I went
> looking to primary sources, as I usually do and I came across a sweet
> little regex implementation by none other than Ken Thompson, in his well
> known article, Regular Expression Search Algorithm, CACM v. 11, No. 6,
> June 1968. I found a decent copy and transcribed it so I could use it's
> examples more directly. It's a piece of work - an Algol 60 three stage
> program that emits IBM 7094 machine code that processes a string and
> produces signals.
>
> What I really appreciate is that the code "works", it's not a fragment,
> not partial implementation, but serious work, the core third stage.
> Anyhow, I wrote a small 7094 processor (only enough instructions to
> execute thompson's search) in aiki, and tried it out and it's glorious
> (to me) running the machine code it generates and producing expected
> results (as provided in this exceptional article).
>
> This like all shiny objects took me down a rabbit trail. My language is
> interpreted remember? I have been thinking about compilers - didn't
> think I wanted one originally, but man slow is so not me, but not just
> any implementation. My language is grammar bound, I already have an IR
> in the AST output, it's closed and therefore, I can prolly just emit it
> or better yet, follow Thompson with a bytecode emit (something for a go
> vm, for example). Anyhow, I started wondering, what about algol 60, it's
> always popping up in any serious language discussion and that took to
> Randell & Russell's 1964 Algol 60 implementation where translation is
> discussed, confirming my suspicion on how I might do the compiler for
> Aiki and preserve it's exact semantic representation and profiling
> capabilities dtrace style. Then I came back to Thompson, and that's
> hopefully where y'all come in... Do any of you know what implementation
> of algol-60 he might have used on the 7094? BC Algol is out in the wild
> and could be right, but I'm really jazzing to implement the search on an
> emulated 7094 using an actual algol and preferably the one he was using.
>

As I understand it, there are at least three:

   - IBM ALGOL 60 (System Monitor Compiler) for the IBSYS operating system
   - SHARE ALGOL 60 Translator  targeting the IBM 709/7090/7094 hardware and
   I thought could run on CTSS
   - ALCOR ALGOL 60 European-American consortium dedicated to standardized
   ALGOL deployment for the for the 7090/7094

You might ask Ken what he remembers.   I haven't read the paper inm a
few years,
did he say which OS he was using that might help you track it down.  Google
tells me that ALCOR-Illinois 7090/7094 compiler project has some influence
in CTSS.   But it also says:

*"**While standard ALGOL 60 dialects like ALCOR existed on the hardware,
they were not the primary way people wrote algorithmic code on CTSS
day-to-day. CTSS users heavily favored two deeply related "ALGOL-cousin"
systems. ... MAD (Michigan Algorithm Decoder - ALGOL 58, and compiled
unbelievably fast): was one of the most popular high-level languages on
CTSS ...  AED (Algol Extended for Design): created at MIT, AED was an
explicit, major extension of ALGOL 60 designed specifically to run under
CTSS."*


> I know, on topic? maybe a little stretch for folks only interested in
> bandying about in the userland/kernel, but regex and it's implementation
> in ed and elsewhere were surely influenced by this exact work.
>
> Thanks!
>
> Will
>
>