From mboxrd@z Thu Jan 1 00:00:00 1970 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on inbox.vuxu.org X-Spam-Level: X-Spam-Status: No, score=-0.8 required=5.0 tests=DKIM_INVALID,DKIM_SIGNED, HTML_FONT_LOW_CONTRAST,HTML_MESSAGE,MAILING_LIST_MULTI, T_SCC_BODY_TEXT_LINE autolearn=ham autolearn_force=no version=3.4.4 Received: (qmail 23352 invoked from network); 20 Aug 2022 16:18:42 -0000 Received: from minnie.tuhs.org (50.116.15.146) by inbox.vuxu.org with ESMTPUTF8; 20 Aug 2022 16:18:42 -0000 Received: from minnie.tuhs.org (localhost [IPv6:::1]) by minnie.tuhs.org (Postfix) with ESMTP id 96E4340D24; Sun, 21 Aug 2022 02:18:37 +1000 (AEST) Received: from mail-vs1-f48.google.com (mail-vs1-f48.google.com [209.85.217.48]) by minnie.tuhs.org (Postfix) with ESMTPS id 38E3040D1E for ; Sun, 21 Aug 2022 02:18:30 +1000 (AEST) Received: by mail-vs1-f48.google.com with SMTP id d126so7190469vsd.13 for ; Sat, 20 Aug 2022 09:18:30 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=ccc.com; s=google; h=cc:to:subject:message-id:date:from:in-reply-to:references :mime-version:from:to:cc; bh=FgXmyPppcsQ3X6pELeII7P9byT22kwCFCDFdw/7pes4=; b=ZvK9pYyKjaJlGC+RwNbr0wOe4D5ok1uOK+sMEzp2Bz7LrRD/MRxDRYQMs3Z3/vMA6q z5ZdMvKpW4mojZSrG9Zz3hF+5TZsypAmyMczb7dBxZeuhnICR90inJl4Mo2opBX6Y1Hr 6iPqY9Pj8ycH6K8ynrlJCJInxv5+RI7prRkTE= X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=cc:to:subject:message-id:date:from:in-reply-to:references :mime-version:x-gm-message-state:from:to:cc; bh=FgXmyPppcsQ3X6pELeII7P9byT22kwCFCDFdw/7pes4=; b=FYV3MYUsi7XgZR3DzYJeJ+4xvuDRp9rWStemVv8fcuegwR8Y6eJUFX3HFoC3JbQd0h mk3z49WKQObacC4JTxHOjY2nHUZDnyynQ2LXiRV/MlriXrFNp/STrHEMN3VSzwYI3f0i qeeL9LceKeA45trn7LuPfOGECu0wNFURowaV/zTzrYWw+MQEZq5WwoEQ1USJPfkErbq6 WQovrnJGEu0y+QWAZcZEDrVy73tMUymBMPd6MMvHQqkvlIxlgy1d3bEugy2dbxYnmx5c BNEjmZ7ZSEbffMQx3MAqfbrpzpwN6hL+FDpSROrz+wUTsXRjixuCD5MaH7JmkRXWZGDL H9Fw== X-Gm-Message-State: ACgBeo3pk6CTRPYcR4WUIUWJdfHv3P/fc4ufH+/6Wd+Qmr/MeW2hhQZ3 nm/ZSxM7hMiCQqsz7pnZynISIaWLD0NH4QdGaS3r4XN+/01Qeg== X-Google-Smtp-Source: AA6agR7uDM/Lku8NPhX0AlObcBSLca/S+Hd3hbpWp5h6WUp4iiPkMlEoaXsG5QAFyA61ZdtGS55jReysZ+lQDpcqS+E= X-Received: by 2002:a67:a44d:0:b0:38a:ce33:da9e with SMTP id p13-20020a67a44d000000b0038ace33da9emr5224692vsh.17.1661012249092; Sat, 20 Aug 2022 09:17:29 -0700 (PDT) MIME-Version: 1.0 References: In-Reply-To: From: Clem Cole Date: Sat, 20 Aug 2022 12:17:02 -0400 Message-ID: To: Douglas McIlroy Content-Type: multipart/alternative; boundary="0000000000001342ec05e6ae8dba" Message-ID-Hash: MVCFWI5NXVRLAOGNT7N2PS4XK4XVHG2E X-Message-ID-Hash: MVCFWI5NXVRLAOGNT7N2PS4XK4XVHG2E X-MailFrom: clemc@ccc.com X-Mailman-Rule-Misses: dmarc-mitigation; no-senders; approved; emergency; loop; banned-address; member-moderation; header-match-tuhs.tuhs.org-0; nonmember-moderation; administrivia; implicit-dest; max-recipients; max-size; news-moderation; no-subject; digests; suspicious-header CC: TUHS main list X-Mailman-Version: 3.3.6b1 Precedence: list Subject: [TUHS] Re: Nice video with Brian Kernighan List-Id: The Unix Heritage Society mailing list Archived-At: List-Archive: List-Help: List-Owner: List-Post: List-Subscribe: List-Unsubscribe: --0000000000001342ec05e6ae8dba Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable Doug, 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. Clem =E1=90=A7 On Sat, Aug 20, 2022 at 11:49 AM Douglas McIlroy < douglas.mcilroy@dartmouth.edu> 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 > --0000000000001342ec05e6ae8dba Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable
Doug,

No matter.=C2=A0 I have ofte= n=C2=A0thought about what an amazing muse you were to so many people regard= ing so many different ideas that have panned out.=C2=A0 It seems to me that= you were always there at the right time.=C2=A0 Your powers to get the best= from everyone around you are unlike anyone else I have ever been=C2=A0luck= y enough to have met. Although=C2=A0I have also often said to students the = one really hard thing to directly=C2=A0teach, that you can learn by looking= at people that came before you is 'good taste.'=C2=A0 =C2=A0We all= owe you as much thanks for being there and inspiring your=C2=A0peers, as f= or their brilliance=C2=A0in implementing the=C2=A0concepts with style and t= aste.

Clem
3D""=E1=90=A7

On Sat, Aug 2= 0, 2022 at 11:49 AM Douglas McIlroy <douglas.mcilroy@dartmouth.edu> wrote:
Brian's tribute to the brill= iant regex mechanism that awk borrowed
from egrep=C2=A0 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.)

=C2=A0 =C2=A0 =C2=A0 =C2=A0 (^|[ (,;])(([Aa]ug[^ ]* *|(08|8)/)0*20)([^01234= 56789]|$)
=C2=A0 =C2=A0 =C2=A0 =C2=A0 (^|[ (,;])(([Aa]ug[^ ]* *|(08|8)/)0*21)([^01234= 56789]|$)
=C2=A0 =C2=A0 =C2=A0 =C2=A0 (^|[ (,;])(([Aa]ug[^ ]* *|(08|8)/)0*22)([^01234= 56789]|$)

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