4

I was looking into the history and development of regular expressions. I found the following timeline:

  • 1956 - Kleene introduces regular expressions in his paper on nerve nets.
  • 1964 - Brzozowsi introduces the idea of a derivative of a regular expression.
  • 1968 - Thompson describes how to write a compiler for regular expressions
  • late 60's/early 70's
    • Thompson ported the QED editor to CTSS, adding regular expression support.
    • Thompson and Ritchie ported QED to Multics, and eventually to Unix 1970's
    • Thompson wrote ed, inspired by QED
    • Sometime after Unix V1, Thompson extracted the regular expression code from ed to make grep
    • in Unix V7, egrep and fgrep were introduced.

Kleene and Brzozowski have equivalent, but differing definitions of regular expressions, and Thompson, in his paper, explicitly assumes that his audience is familiar with these definitions.

What I am confused about is what happened to alternation (matches either of two regular expressions) in ed? Kleene, Brzozowski, and Thompson's papers include alternation. Thompson's regular expression implementation in QED includes alternation, and yet ed does not. Neither does early grep.

Weirder to me, ed introduced support for back-references in its regular expressions. That is, the regular expression (a.c)\1 will match abcabc but not abcadc. Back-references allows ed and grep to recognize some non-regular languages, and the lack of alternation means there are some regular languages they can't recognize.

Why did Thompson remove support for alternation between qed and ed? Why did back-references get added, but not alternation?

2
  • 1
    Standard ed, grep, and sed all uses basic regular expressions by default. Alterations are not part of the this type of regular expressions. grep and sed can often be made to use extended regular expressions as a non-standard extension, which includes alterations. GNU grep also supports Perl-compatible regular expressions, as a further extension to the POSIX specification for this utility. This is not an answer as it says nothing about why alterations were not part of the basic regular expression syntax (which is what I believe the question is really about).
    – Kusalananda
    Dec 8 '20 at 20:21
  • I suspect that support for alternation requires either a relatively large amount of memory or a large amount of backtracking (which is slow) in common cases, whereas support for alternation only requires a large amount of backtracking in unusual cases. But that's from a very dim memory of regexp compilation techniques (and I don't even know what techniques were known in Thompson's time), not from research into Thompson's motivations. Dec 8 '20 at 21:43
1

Dennis Ritchie once wrote a short text called An incomplete history of the QED Text Editor. In the text, we may read

The "standard Unix editor" ed was first written by Ken Thompson for the PDP-7. It kept the basic text-line orientation, but radically simplified the regular expressions to include only the * operator: no alternation, no parentheses. Where my QED embraced much of the context-free languages, this version could not even express all regular languages. It was not much of a loss.

Similarly, Ken's Unix ed ditched the notion of multiple buffers and of execution of buffers. Subsequent versions of ed for Unix (now written in C) began to add back some of the complexity (e.g. back-referencing in "regular" expressions, which now didn't quite include all the regular languages nor context-free languages, but did intrude a bit on the context-sensitive languages.)

From these short passages, I get the feeling that Ken was primarily concerned about using ed to get things done, rather than trying to implement regular expressions that would not actually get used. The "It was not much of a loss." may be a sign of Ken's personal way of working with text, that he didn't need alterations or back-referencing (at least not desperately).

As Gilles also points out in comments, the implementation of alternations may be slow and relatively memory intensive, while back-references may be slow in unusual cases, making back-references more likely to be implemented on limited hardware.

The PDP-7 that the Unix team used at the start of development had 8k word memory, whereas the Multics system, which Ken implemented one version of QED for, ran on machines boasting 64k words. This could well be another reason why the initial implementation of ed only had very basic pattern matching facilities.

In summary: Two possible reasons would be

  1. Restrictive hardware (PDP-7) made it impossible/cumbersome to implement alternation and back-references etc.
  2. Full regular expression syntax not actually needed for what the editor was used for. With the move to more powerful hardware (PDP-11), back-reference were added back into the editor, but there may simply not have been a need for alternations among the users of the editor at the time.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.