10 Jan
2019
10 Jan
'19
12:19 a.m.
Time for a new thread :-)
As today is Knuth's birthday (posted over in COFF), I was wondering (in
the cesspool that is my mind) how much of Unix would have been influenced
by Knuth? We have qsort() of course (which Hoare actually wrote, based on
one of Knuth's algorithms), but I'm guessing that Ken and Dennis would
have been familiar with his work?
Or am I spreading fake news again? :-) Look, I love being corrected if I
make a mistake on a technical mailing list, so fire at will if need be...
-- Dave
10 Jan
10 Jan
12:54 a.m.
Knuth is great, and I too am interested to know about his influence on
UNIX, but Hoare is credited with the quicksort algorithm by the
authorities I've encountered.
(A little Googling suggests I'm not misremembering.)
On Wed, Jan 9, 2019 at 7:19 PM Dave Horsfall <dave(a)horsfall.org> wrote:
Time for a new thread :-)
As today is Knuth's birthday (posted over in COFF), I was wondering (in
the cesspool that is my mind) how much of Unix would have been influenced
by Knuth? We have qsort() of course (which Hoare actually wrote, based on
one of Knuth's algorithms), but I'm guessing that Ken and Dennis would
have been familiar with his work?
Or am I spreading fake news again? :-) Look, I love being corrected if I
make a mistake on a technical mailing list, so fire at will if need be...
-- Dave
--
Ed Cashin <ecashin(a)noserose.net>
7:39 a.m.
Ed Cashin <ecashin(a)noserose.net> wrote:
Knuth is great, and I too am interested to know about
his influence on
UNIX, but Hoare is credited with the quicksort algorithm by the
authorities I've encountered.
Hoare did indeed invent it. He describes the history, IIRC, in his Turing Award
lecture. (I know I read it, written by him, somewhere.)
Arnold
13 Jan
13 Jan
3:41 a.m.
One connection Knuth had to Unix was inventing LALR parsing, the basic
algorithm used in Yacc. I added some things (notably, the precedence
mechanism) and had to do a lot of engineering to be able to handle
large grammars (e.g. F77) on a PDP-11. But the underlying algorithm
(taught to my be Al Aho) was all Knuth.
I seem to recall also that a lot of us at that time were underwhelmed
by The Art of Computer Programming, especially the use of MIX.
Perhaps it just meant that Knuth was doing things bottom up, while we
were doing amazing things in small spaces with B and C.
Steve
----- Original Message -----
From: arnold(a)skeeve.com
To:<ecashin@noserose.net>, <dave(a)horsfall.org>
Cc:<tuhs@tuhs.org>
Sent:Thu, 10 Jan 2019 00:39:28 -0700
Subject:Re: [TUHS] Knuth and Unix
Ed Cashin <ecashin(a)noserose.net> wrote:
Knuth is great, and I too am interested to know about
his influence
on
UNIX, but Hoare is credited with the quicksort
algorithm by the
authorities I've encountered.
Hoare did indeed invent it. He describes the history, IIRC, in his
Turing Award
lecture. (I know I read it, written by him, somewhere.)
Arnold
4:40 a.m.
On Sat, 12 Jan 2019 19:41:26 -0800 "Steve Johnson" <scj(a)yaccman.com>
wrote:
One connection Knuth had to Unix was inventing LALR
parsing, the basic
algorithm used in Yacc. I added some things (notably, the precedence
mechanism) and had to do a lot of engineering to be able to handle large
grammars (e.g. F77) on a PDP-11. But the underlying algorithm (taught to
my be Al Aho) was all Knuth.
Knuth invented LR parsing but IIRC it was DeRemer who came up
with LALR parsing. In 78-79 I was implementing a LALR(1)
parser generator in Pascal on strength of which I got my first
real job. At that job I used DeRemer and Pennello's 1979
paper to reimplement the parser generator.
15 Jan
15 Jan
10:32 p.m.
I remember reading Knuth's paper, and certainly heard DeRemer's name,
but it didn't affect much of what I did. There was a paper out of
Stanford about that time that influenced me greatly -- it was about
pattern matching languages, and proposed separating two ideas: 1.
"Here are the patterns that match this tree". And 2. "If more than
one pattern matches, here's how to decide which one to use." Given
the constraints of size on the PDP 11, anything but LR(1) was
infeasable. But using ambiguous grammars and broadening the
shift/reduce test to trest operator precedence fit right into that
pattern. Another thing that I think was unique to Yacc at the time
was introducing symbols that matched the empty string whose reduction
caused program actions. Many similar parser systems at the time
could not deal with these "empty" symbols.
Steve
----- Original Message -----
From: "Bakul Shah" <bakul(a)bitblocks.com>
To:"Steve Johnson" <scj(a)yaccman.com>
Cc:<arnold@skeeve.com>, <ecashin(a)noserose.net>, <dave(a)horsfall.org>,
<tuhs(a)tuhs.org>
Sent:Sat, 12 Jan 2019 20:40:11 -0800
Subject:Re: [TUHS] Knuth and Unix
On Sat, 12 Jan 2019 19:41:26 -0800 "Steve Johnson" <scj(a)yaccman.com>
wrote:
One connection Knuth had to Unix was inventing LALR
parsing, the
basic
algorithm used in Yacc. I added some things (notably,
the
precedence
mechanism) and had to do a lot of engineering to be
able to handle
large
grammars (e.g. F77) on a PDP-11. But the underlying
algorithm
(taught to
my be Al Aho) was all Knuth.
Knuth invented LR parsing but IIRC it was DeRemer who came up
with LALR parsing. In 78-79 I was implementing a LALR(1)
parser generator in Pascal on strength of which I got my first
real job. At that job I used DeRemer and Pennello's 1979
paper to reimplement the parser generator.
16 Jan
16 Jan
2:53 a.m.
So you're the reason (Plan 9) awk has 83 reduce-reduce conflicts (and
42 shift-reduce).
-rob
On Wed, Jan 16, 2019 at 9:39 AM Steve Johnson <scj(a)yaccman.com> wrote:
I remember reading Knuth's paper, and certainly heard DeRemer's name, but it
didn't affect much of what I did. There was a paper out of Stanford about that time
that influenced me greatly -- it was about pattern matching languages, and proposed
separating two ideas: 1. "Here are the patterns that match this tree". And 2.
"If more than one pattern matches, here's how to decide which one to use."
Given the constraints of size on the PDP 11, anything but LR(1) was infeasable. But
using ambiguous grammars and broadening the shift/reduce test to trest operator precedence
fit right into that pattern. Another thing that I think was unique to Yacc at the time
was introducing symbols that matched the empty string whose reduction caused program
actions. Many similar parser systems at the time could not deal with these
"empty" symbols.
Steve
----- Original Message -----
From: "Bakul Shah" <bakul(a)bitblocks.com>
To:"Steve Johnson" <scj(a)yaccman.com>
Cc:<arnold@skeeve.com>, <ecashin(a)noserose.net>, <dave(a)horsfall.org>,
<tuhs(a)tuhs.org>
Sent:Sat, 12 Jan 2019 20:40:11 -0800
Subject:Re: [TUHS] Knuth and Unix
On Sat, 12 Jan 2019 19:41:26 -0800 "Steve Johnson" <scj(a)yaccman.com>
wrote:
One connection Knuth had to Unix was inventing
LALR parsing, the basic
algorithm used in Yacc. I added some things (notably, the precedence
mechanism) and had to do a lot of engineering to be able to handle large
grammars (e.g. F77) on a PDP-11. But the underlying algorithm (taught to
my be Al Aho) was all Knuth.
Knuth invented LR parsing but IIRC it was DeRemer who came up
with LALR parsing. In 78-79 I was implementing a LALR(1)
parser generator in Pascal on strength of which I got my first
real job. At that job I used DeRemer and Pennello's 1979
paper to reimplement the parser generator.
6:22 p.m.
You can't lay the blame for that on Steve.
The GNU Awk grammar has only 36 shift-reduce conflicts and no
reduce-reduce conflicts.
The mawk 1.3.4 grammar has an amazing count of only *four* shift-reduce
conflicts. (But then, Mike Brennan is an amazing programmer.)
I have no idea what happens if you run the POSIX awk grammar through
yacc / bison, but it'd be an interesting experiment.
Arnold
Rob Pike <robpike(a)gmail.com> wrote:
So you're the reason (Plan 9) awk has 83
reduce-reduce conflicts (and
42 shift-reduce).
-rob
On Wed, Jan 16, 2019 at 9:39 AM Steve Johnson <scj(a)yaccman.com> wrote:
>
> I remember reading Knuth's paper, and certainly heard DeRemer's name, but
it didn't affect much of what I did. There was a paper out of Stanford about that
time that influenced me greatly -- it was about pattern matching languages, and proposed
separating two ideas: 1. "Here are the patterns that match this tree". And 2.
"If more than one pattern matches, here's how to decide which one to use."
Given the constraints of size on the PDP 11, anything but LR(1) was infeasable. But
using ambiguous grammars and broadening the shift/reduce test to trest operator precedence
fit right into that pattern. Another thing that I think was unique to Yacc at the time
was introducing symbols that matched the empty string whose reduction caused program
actions. Many similar parser systems at the time could not deal with these
"empty" symbols.
>
> Steve
>
>
>
> ----- Original Message -----
> From: "Bakul Shah" <bakul(a)bitblocks.com>
> To:"Steve Johnson" <scj(a)yaccman.com>
> Cc:<arnold@skeeve.com>, <ecashin(a)noserose.net>,
<dave(a)horsfall.org>, <tuhs(a)tuhs.org>
> Sent:Sat, 12 Jan 2019 20:40:11 -0800
> Subject:Re: [TUHS] Knuth and Unix
>
>
> On Sat, 12 Jan 2019 19:41:26 -0800 "Steve Johnson" <scj(a)yaccman.com>
wrote:
> > One connection Knuth had to Unix was inventing LALR parsing, the basic
> > algorithm used in Yacc. I added some things (notably, the precedence
> > mechanism) and had to do a lot of engineering to be able to handle large
> > grammars (e.g. F77) on a PDP-11. But the underlying algorithm (taught to
> > my be Al Aho) was all Knuth.
>
> Knuth invented LR parsing but IIRC it was DeRemer who came up
> with LALR parsing. In 78-79 I was implementing a LALR(1)
> parser generator in Pascal on strength of which I got my first
> real job. At that job I used DeRemer and Pennello's 1979
> paper to reimplement the parser generator.
>
8:10 p.m.
I was speaking in jest... But the (official) awk grammar has been an
eye-opener for years.
-rob
On Thu, Jan 17, 2019 at 5:22 AM <arnold(a)skeeve.com> wrote:
You can't lay the blame for that on Steve.
The GNU Awk grammar has only 36 shift-reduce conflicts and no
reduce-reduce conflicts.
The mawk 1.3.4 grammar has an amazing count of only *four* shift-reduce
conflicts. (But then, Mike Brennan is an amazing programmer.)
I have no idea what happens if you run the POSIX awk grammar through
yacc / bison, but it'd be an interesting experiment.
Arnold
Rob Pike <robpike(a)gmail.com> wrote:
> So you're the reason (Plan 9) awk has 83 reduce-reduce conflicts (and
> 42 shift-reduce).
>
> -rob
>
> On Wed, Jan 16, 2019 at 9:39 AM Steve Johnson <scj(a)yaccman.com> wrote:
> >
> > I remember reading Knuth's paper, and certainly heard DeRemer's name,
but it didn't affect much of what I did. There was a paper out of Stanford about
that time that influenced me greatly -- it was about pattern matching languages, and
proposed separating two ideas: 1. "Here are the patterns that match this tree".
And 2. "If more than one pattern matches, here's how to decide which one to
use." Given the constraints of size on the PDP 11, anything but LR(1) was
infeasable. But using ambiguous grammars and broadening the shift/reduce test to trest
operator precedence fit right into that pattern. Another thing that I think was unique
to Yacc at the time was introducing symbols that matched the empty string whose reduction
caused program actions. Many similar parser systems at the time could not deal with these
"empty" symbols.
> >
> > Steve
> >
> >
> >
> > ----- Original Message -----
> > From: "Bakul Shah" <bakul(a)bitblocks.com>
> > To:"Steve Johnson" <scj(a)yaccman.com>
> > Cc:<arnold@skeeve.com>, <ecashin(a)noserose.net>,
<dave(a)horsfall.org>, <tuhs(a)tuhs.org>
> > Sent:Sat, 12 Jan 2019 20:40:11 -0800
> > Subject:Re: [TUHS] Knuth and Unix
> >
> >
> > On Sat, 12 Jan 2019 19:41:26 -0800 "Steve Johnson"
<scj(a)yaccman.com> wrote:
> > > One connection Knuth had to Unix was inventing LALR parsing, the basic
> > > algorithm used in Yacc. I added some things (notably, the precedence
> > > mechanism) and had to do a lot of engineering to be able to handle large
> > > grammars (e.g. F77) on a PDP-11. But the underlying algorithm (taught to
> > > my be Al Aho) was all Knuth.
> >
> > Knuth invented LR parsing but IIRC it was DeRemer who came up
> > with LALR parsing. In 78-79 I was implementing a LALR(1)
> > parser generator in Pascal on strength of which I got my first
> > real job. At that job I used DeRemer and Pennello's 1979
> > paper to reimplement the parser generator.
> >
18 Jan
18 Jan
12:55 a.m.
As I remember, the original EQN grammar had >300 S/R conflicts and 50
or so RR conflicts. But it mostly did what you wanted. I think Al
Aho got faint when he looked it it, though... (It got better when
precedence was added...)
Steve
----- Original Message -----
From: "Rob Pike" <robpike(a)gmail.com>
To:<arnold@skeeve.com>
Cc:<scj@yaccman.com>, <tuhs(a)tuhs.org>
Sent:Thu, 17 Jan 2019 07:10:58 +1100
Subject:Re: [TUHS] Knuth and Unix
I was speaking in jest... But the (official) awk grammar has been an
eye-opener for years.
-rob
On Thu, Jan 17, 2019 at 5:22 AM <arnold(a)skeeve.com> wrote:
You can't lay the blame for that on Steve.
The GNU Awk grammar has only 36 shift-reduce conflicts and no
reduce-reduce conflicts.
The mawk 1.3.4 grammar has an amazing count of only *four*
shift-reduce
conflicts. (But then, Mike Brennan is an amazing
programmer.)
I have no idea what happens if you run the POSIX awk grammar
through
yacc / bison, but it'd be an interesting
experiment.
Arnold
Rob Pike <robpike(a)gmail.com> wrote:
> So you're the reason (Plan 9) awk has 83 reduce-reduce conflicts
(and
> 42 shift-reduce).
>
> -rob
>
> On Wed, Jan 16, 2019 at 9:39 AM Steve Johnson <scj(a)yaccman.com>
wrote:
> >
> > I remember reading Knuth's paper, and certainly heard DeRemer's
name, but it didn't affect much of what I did. There was a paper out
of Stanford about that time that influenced me greatly -- it was about
pattern matching languages, and proposed separating two ideas: 1.
"Here are the patterns that match this tree". And 2. "If more than one
pattern matches, here's how to decide which one to use." Given the
constraints of size on the PDP 11, anything but LR(1) was infeasable.
But using ambiguous grammars and broadening the shift/reduce test to
trest operator precedence fit right into that pattern. Another thing
that I think was unique to Yacc at the time was introducing symbols
that matched the empty string whose reduction caused program actions.
Many similar parser systems at the time could not deal with these
"empty" symbols.
> >
> > Steve
> >
> >
> >
> > ----- Original Message -----
> > From: "Bakul Shah" <bakul(a)bitblocks.com>
> > To:"Steve Johnson" <scj(a)yaccman.com>
> > Cc:<arnold@skeeve.com>, <ecashin(a)noserose.net>,
<dave(a)horsfall.org>, <tuhs(a)tuhs.org>
> > Sent:Sat, 12 Jan 2019 20:40:11 -0800
> > Subject:Re: [TUHS] Knuth and Unix
> >
> >
> > On Sat, 12 Jan 2019 19:41:26 -0800 "Steve Johnson"
<scj(a)yaccman.com> wrote:
> > > One connection Knuth had to Unix was
inventing LALR parsing,
the basic
> > > algorithm used in Yacc. I added some
things (notably, the
precedence
> > > mechanism) and had to do a lot of
engineering to be able to
handle large
> > > grammars (e.g. F77) on a PDP-11. But
the underlying algorithm
(taught to
> > > my be Al Aho) was all Knuth.
> >
> > Knuth invented LR parsing but IIRC it was DeRemer who came up
> > with LALR parsing. In 78-79 I was implementing a LALR(1)
> > parser generator in Pascal on strength of which I got my first
> > real job. At that job I used DeRemer and Pennello's 1979
> > paper to reimplement the parser generator.
> >
16 Jan
16 Jan
8:50 p.m.
On Tue, 15 Jan 2019 14:32:16 -0800 "Steve Johnson" <scj(a)yaccman.com>
wrote:
I remember reading Knuth's paper, and certainly
heard
DeRemer's name, but it didn't affect much of what I did.
There was a paper out of Stanford about that time that
influenced me greatly -- it was about pattern matching
languages, and proposed separating two ideas: 1. "Here are
the patterns that match this tree". And 2. "If more than one
pattern matches, here's how to decide which one to use."
Given the constraints of size on the PDP 11, anything but
LR(1) was infeasable. But using ambiguous grammars and
broadening the shift/reduce test to trest operator precedence
fit right into that pattern. Another thing that I think was
unique to Yacc at the time was introducing symbols that
matched the empty string whose reduction caused program
actions. Many similar parser systems at the time could not
deal with these "empty" symbols.
Good to know all this. The Stanford paper you refer, would
that be "fast pattern matching" by Knuth, Morris & Pratt?
I remember struggling with empty strings and I also missed
other yacc tricks. In my formulation I had two kinds of
rules: set rules and sequence rules. Set rules avoided
unnecessary reductions in rules such as foo: bar|...
For example:
// sets
expr = relexpr | expr1
expr1 = addexpr | expr2
expr2 = mulexpr | expr3
...
// sequences
relexpr: expr1 RELOP expr1
addexpr: expr1 ('+'|'-') expr2
mulexpr: expr2 ('*'|'/') expr3
...
Basically I completely avoided empty symbols -- even an empty
file has an EOF! [I didn't try it on anything more complicated
than (extended) Pascal so no idea how it would have fared on
complexificated lanuages]
18 Jan
18 Jan
9:57 p.m.
The paper was called "The Competence/Performance Dichotomy" by
Pratt. He borrowed an idea from Chompsky and distinguished between
being able to understand something and being able to produce it. The
idea I took from it was to recognize grammar rules even if the parse
was ambiguous and then use other mechanisms (e.g., Shift/Reduce,
precedence) to decide what to do.
About empty productions: one of the most useful versions of this was
in handling scopes in programming languages, especially in C where xyz
could be a variable in one scope and a typedef in an inner one, or
vice versa. The empty production could get called at the right
moment to make the appropriate symbol table fixes, where otherwise we
would have had a syntax error.
Steve
----- Original Message -----
From: "Bakul Shah" <bakul(a)bitblocks.com>
To:"Steve Johnson" <scj(a)yaccman.com>
Cc:<arnold@skeeve.com>, <ecashin(a)noserose.net>, <dave(a)horsfall.org>,
<tuhs(a)tuhs.org>
Sent:Wed, 16 Jan 2019 12:50:35 -0800
Subject:Re: [TUHS] Knuth and Unix
On Tue, 15 Jan 2019 14:32:16 -0800 "Steve Johnson" <scj(a)yaccman.com>
wrote:
I remember reading Knuth's paper, and certainly
heard
DeRemer's name, but it didn't affect much of what I did.
There was a paper out of Stanford about that time that
influenced me greatly -- it was about pattern matching
languages, and proposed separating two ideas: 1. "Here are
the patterns that match this tree". And 2. "If more than one
pattern matches, here's how to decide which one to use."
Given the constraints of size on the PDP 11, anything but
LR(1) was infeasable. But using ambiguous grammars and
broadening the shift/reduce test to trest operator precedence
fit right into that pattern. Another thing that I think was
unique to Yacc at the time was introducing symbols that
matched the empty string whose reduction caused program
actions. Many similar parser systems at the time could not
deal with these "empty" symbols.
Good to know all this. The Stanford paper you refer, would
that be "fast pattern matching" by Knuth, Morris & Pratt?
I remember struggling with empty strings and I also missed
other yacc tricks. In my formulation I had two kinds of
rules: set rules and sequence rules. Set rules avoided
unnecessary reductions in rules such as foo: bar|...
For example:
// sets
expr = relexpr | expr1
expr1 = addexpr | expr2
expr2 = mulexpr | expr3
...
// sequences
relexpr: expr1 RELOP expr1
addexpr: expr1 ('+'|'-') expr2
mulexpr: expr2 ('*'|'/') expr3
...
Basically I completely avoided empty symbols -- even an empty
file has an EOF! [I didn't try it on anything more complicated
than (extended) Pascal so no idea how it would have fared on
complexificated lanuages]
10 Jan
10 Jan
3:14 a.m.
I learned about Knuth from reading Unix man pages. I was intrigued enough to purchase his
3 volume set "Art of Computer Programming".
From: "Dave Horsfall" <dave(a)horsfall.org>
To: "The Eunuchs Hysterical Society" <tuhs(a)tuhs.org>
Sent: Wednesday, January 9, 2019 7:19:05 PM
Subject: [TUHS] Knuth and Unix
Time for a new thread :-)
As today is Knuth's birthday (posted over in COFF), I was wondering (in
the cesspool that is my mind) how much of Unix would have been influenced
by Knuth? We have qsort() of course (which Hoare actually wrote, based on
one of Knuth's algorithms), but I'm guessing that Ken and Dennis would
have been familiar with his work?
Or am I spreading fake news again? :-) Look, I love being corrected if I
make a mistake on a technical mailing list, so fire at will if need be...
-- Dave
2088
days inactive
2096
days old
13 comments
7 participants
participants (7)
-
arnold＠skeeve.com -
Bakul Shah -
Dave Horsfall -
Ed Cashin -
Jim Capp -
Rob Pike -
Steve Johnson