[TUHS] Regex archaeology

[Will Senn via TUHS]

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.

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