[COFF] [TUHS] Re: Regex archaeology

[John P. Linderman via COFF]

Russ Cox has done some great stuff with regular expressions.
<https://swtch.com/~rsc/regexp/> This
<https://swtch.com/~rsc/regexp/regexp1.html> is a fine explanation of Ken's
approach, and a warning about the dangers of backtracking. -- jpl

On Tue, Sep 1, 2026 at 10:45 PM Clem Cole via TUHS <tuhs at tuhs.org> wrote:

> 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
> >
> >
>