[COFF] [simh] [TUHS] Regex archaeology

[Eve Quinn via COFF]

Will,

I dug into this because I think there may be one premise worth separating.

Thompson's 1968 CACM paper says, "A working example of the third stage
of the compiler" is written in ALGOL-60 and produces IBM 7094 machine
language. That establishes the language of the published working
example, but it does not identify an ALGOL implementation.

Dennis Ritchie's history of QED gives a different and useful fact
about the program itself: Thompson's CTSS QED was written in IBM 7090
assembly language and compiled its regular expressions to machine code
on the fly.

The patent version is interesting too. It describes the 7094
implementation using FAP routines, then introduces the ALGOL 60
compiler as "one such automatic test generating facility" being
illustrated. That makes me wary of assuming that the CACM listing
necessarily points to a particular historically-used ALGOL compiler.

Russ Cox also notes that he inspected an actual copy of Thompson's QED
in the CTSS sources. In his later references he identifies it in the
source-listing archive as `com5`, marked `0QED`. That seems like a
particularly good primary-source trail to follow.

So I don't think the evidence I've found yet chooses IBM ALGOL vs.
SHARE ALGOL vs. ALCOR. It may instead be useful to split the question
in two:

1. What did Thompson's actual CTSS QED use? The surviving evidence
points to assembly/FAP and on-the-fly 7090/7094 machine-code
generation.
2. What ALGOL 60 implementation will accept and run the *published*
third-stage example faithfully? That remains a very interesting
emulation question, but it may not have the same answer as the first
one.

If the goal is to recreate what Thompson actually ran, I'd start with
`0QED` in the CTSS source and work outward from there.

Sources I used:

Ken Thompson, "Regular Expression Search Algorithm," CACM 11(6), June 1968:
https://doi.org/10.1145/363347.363387

Dennis Ritchie, "An incomplete history of the QED Text Editor":
https://www.nokia.com/bell-labs/about/dennis-m-ritchie/qed.html

Ken Thompson, US Patent 3,568,156, "Text Matching Algorithm":
https://patents.google.com/patent/US3568156A/en

Russ Cox, "Implementing Regular Expressions":
https://swtch.com/~rsc/talks/regexp.pdf

MIT CSAIL CTSS documents and source-program archive notes:
https://www.csail.mit.edu/ctss-documents

Eve Quinn

On Wed, 2 Sep 2026 03:56:37 +0000, "Tim Shoppa via groups.io"
<tshoppa=gmail.com at groups.io> wrote:
> You mention MAD which is great!
>
> I actually got to use MAD a few times in the 1980s in a moonlighting job where i was further extending a special purpose RUNOFF variant that drove Calcomp plotters to make transparency decks for a geology department. I specifically extended it to talk to HP
> pen plotters and added a preview for Tek4014. I had a lot of fun, much more fun than anything else I ever did on the university’s IBM mainframes.
>
> Even today the favorite part of my job is hacking code that generates SVG.
>
> Tim N3QE
>
> Get [Outlook for iOS](https://aka.ms/o0ukef)
>
> From: simh at groups.io <simh at groups.io> on behalf of Clement T Cole via groups.io <clemc=ccc.com at groups.io>
>
> Sent: Tuesday, 01 September 2026 22:44:49
>
> To: Will Senn <will.senn at gmail.com>
>
> Cc: Computer Old Farts Followers <coff at tuhs.org>; simh at groups.io <simh at groups.io>
>
> Subject: Re: [simh] [TUHS] Regex archaeology
>
> 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
>
> _._,_._,_
>
> Groups.io Links:
>
> You receive all messages sent to this group.
>
> [View/Reply Online (#7079)](https://groups.io/g/simh/message/7079) |
>
> [Reply to Group](mailto:simh at groups.io?subject=Re:%20Re%3A%20%5Bsimh%5D%20%5BTUHS%5D%20Regex%20archaeology)
>
> | [Reply to Sender](mailto:tshoppa at gmail.com?subject=Private:%20Re:%20Re%3A%20%5Bsimh%5D%20%5BTUHS%5D%20Regex%20archaeology)
>
> |
>
> [Mute This Topic](https://groups.io/mt/121045633/10603048)
>
> | [New Topic](https://groups.io/g/simh/post)
>
> [Your Subscription](https://groups.io/g/simh/editsub/10603048) |
> [Contact Group Owner](mailto:simh+owner at groups.io) |
>
> [Unsubscribe](https://groups.io/g/simh/leave/15381612/10603048/486521163/xyzzy)
>
> [littlemousequinn at gmail.com]
>
> _._,_._,_