The Unix Heritage Society mailing list
 help / color / mirror / Atom feed
From: Clem Cole <>
To: Douglas McIlroy <>
Cc: TUHS main list <>
Subject: [TUHS] Re: Nice video with Brian Kernighan
Date: Sat, 20 Aug 2022 12:17:02 -0400	[thread overview]
Message-ID: <> (raw)
In-Reply-To: <>

[-- Attachment #1: Type: text/plain, Size: 3095 bytes --]


No matter.  I have often thought about what an amazing muse you were to so
many people regarding so many different ideas that have panned out.  It
seems to me that you were always there at the right time.  Your powers to
get the best from everyone around you are unlike anyone else I have ever
been lucky enough to have met. Although I have also often said to students
the one really hard thing to directly teach, that you can learn by looking
at people that came before you is 'good taste.'   We all owe you as much
thanks for being there and inspiring your peers, as for their brilliance in
implementing the concepts with style and taste.


On Sat, Aug 20, 2022 at 11:49 AM Douglas McIlroy <> wrote:

> Brian's tribute to the brilliant regex mechanism that awk borrowed
> from egrep  spurred memories.
> For more than forty years I claimed credit for stimulating Ken to
> liberate grep from ed. Then, thanks to TUHS, I learned that I had
> merely caused Ken to spring from the closet a program he had already
> made for his own use.
> There's a related story for egrep. Al Aho made a deterministic
> regular-expression recognizer as a faster replacement for the
> non-deterministic recognizer in grep. He also extended the domain of
> patterns to full regular expressions, including alternation; thus the
> "e" in egrep.
> About the same time, I built on Norm Shryer's personal calendar
> utility. I wanted to generalize Norm's strict syntax for dates to
> cover most any (American) representation of dates, and to warn about
> tomorrow's calendar as well as today's--where "tomorrow" could extend
> across a weekend or holiday.
> Egrep was just the tool I needed for picking the dates out of a
> free-form calendar file. I wrote a little program that built an egrep
> pattern based on today's date. The following mouthful for Saturday,
> August 20 covers Sunday and Monday, too. (Note that, in egrep, newline
> is a synonym for |, the alternation operator.)
>         (^|[ (,;])(([Aa]ug[^ ]* *|(08|8)/)0*20)([^0123456789]|$)
>         (^|[ (,;])(([Aa]ug[^ ]* *|(08|8)/)0*21)([^0123456789]|$)
>         (^|[ (,;])(([Aa]ug[^ ]* *|(08|8)/)0*22)([^0123456789]|$)
> It worked like a charm, except that it took a good part of a minute to
> handle even a tiny calendar file. The reason: the state count of the
> deterministic automaton was exponentially larger than the regular
> regular expression; and egrep had to build the automaton before it
> could run it. Al was mortified that an early serious use of egrep
> should be such a turkey.
> But Al was undaunted. He replaced the automaton construction with an
> equivalent lazy algorithm that constructed a state only when the
> recognizer was about to visit it. This made egrep into the brilliant
> tool that Brian praised.
> What I don't know is whether the calendar program stimulated the idea
> of lazy implementation, or whether Al, like Ken before him with grep,
> already had the idea up his sleeve.
> Doug

[-- Attachment #2: Type: text/html, Size: 4249 bytes --]

  reply	other threads:[~2022-08-20 16:18 UTC|newest]

Thread overview: 10+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2022-08-20 15:48 Douglas McIlroy
2022-08-20 16:17 ` Clem Cole [this message]
2022-08-20 18:24   ` Rich Morin
2022-08-21 15:09     ` John Cowan
2022-08-21 15:41       ` Clem Cole
2022-08-22  2:49         ` John Cowan
2022-08-21 20:07       ` Rich Morin
2022-08-21  9:36 ` Mohamed Akram
  -- strict thread matches above, loose matches on Subject: below --
2022-08-18 10:01 [TUHS] " Arnold Robbins
2022-08-18 21:58 ` [TUHS] " Clem Cole
2022-08-18 22:48   ` Pete Wright via TUHS

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \ \ \ \ \

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).