PEP 308: Rejection of C ?? T || F

Steven Taschuk staschuk at telusplanet.net
Thu Feb 13 15:59:22 EST 2003


Quoth Michael Hudson:
> Steven Taschuk <staschuk at telusplanet.net> writes:
> 
> > Although ?? suggests testing (and surely this is why ? is used
> > here in C syntax), I do not feel that || suggests alternation,
> 
> Well, | is used for alternation in regular expressions.  I don't know
> the origin of the notation, but wouldn't be surprised if it pre-dated
> C.

An excellent point.  (Though for the purposes of the PEP, an
analogy to regular expression syntax is not much better than an
analogy to C syntax: neither is perspicuous to the uninitiated.)

A little web research (details below) finds | for alternation
attested from about 1967, at which time it appears both in Ken
Thompson and Dennis Ritchie's language B and in Thompson's
implementation of regular expressions for the CTSS version of the
QED editor (which afaik was the first such implementation).

So it seems you are right to suspect that the notation pre-dates C
(though not by much if these are in fact its earliest uses).

The origin of regular expressions in mathematics is afaik a 1956
paper by Stephen Kleene.  I don't have a copy of this paper on
hand, but I think he used "A U B" for alternation, because he was
constructing sets of sequences.  (Incidentally, | as a logical
operator in mathematics is afaik never alternation, but always
alternative denial: p | q <=> not (p and q) <=> not p or not q.  I
think this notation dates from at least the 1910s, and it might
even occur in Russell and Whitehead's _Principia_.)

| for alternation might well be Thompson and/or Ritchie's
invention.

Details:

Thompson's CTSS port of QED was "among the first things he did on
arriving [at Bell Labs]" [QED].  He arrived there in 1966 [KTBIO];
his paper on the regular expression algorithm was published in
mid-1968 (CACM 11:6).

Ritchie describes | as one of the "classical set of operators (*,
|, concatenation, grouping for parentheses)" [QED], implying its
use in the syntax of Thompson's original implementation.  (The
star was Kleene's, I think.)

B's logical operators "were & and |.  [These operators] are now
visible too in modern BCPL, and almost certainly were adopted very
soon into barely-past-1967 BCPL [...]" [BCPL].  B was based on a
ca. 1967 version of BCPL [CHIST].

References:
  [BCPL]  http://cm.bell-labs.com/cm/cs/who/dmr/bcpl.html
  [CHIST] http://cm.bell-labs.com/cm/cs/who/dmr/chist.html
  [QED]   http://cm.bell-labs.com/cm/cs/who/dmr/qed.html
  [KTBIO] http://www.bell-labs.com/history/unix/thompsonbio.html

Note that I'm relying entirely on Ritchie's accounts, except for
the question of when Thompson arrived at Bell Labs.

-- 
Steven Taschuk           | "Its force is immeasurable.  Even Computer
staschuk at telusplanet.net |  cannot determine it."
                         |       -- _Space: 1999_ episode "Black Sun"





More information about the Python-list mailing list