[TUHS] Re: What would early alternatives to C have been?

[TUHS] Re: What would early alternatives to C have been?

[Douglas McIlroy]

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

> everyone should write for their first compiler in Pascal for a
> simple language and no cheating using YACC.  You need to write the whole
> thing if you want to understand how parsing really works.

Yacc certainly makes it easier to write parsers for big grammars, but
it's far from cheating. You need to know a lot more about parsing to use
Yacc than you need to roll your own.

Hand parsing of a tiny grammar is almost a  necessary step on the way to
understanding Yacc. But I think hand-building the whole parser for a
compiler is unnecessary torture--like doing trigonometry with log tables.

Doug

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

[TUHS] Re: What would early alternatives to C have been?

[Charles H. Sauer]

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

[While walking 5 miles through the snow …]

> On Mar 9, 2025, at 9:03 PM, Douglas McIlroy <douglas.mcilroy@dartmouth.edu> wrote:
> 
> > everyone should write for their first compiler in Pascal for a
> > simple language and no cheating using YACC.  You need to write the whole
> > thing if you want to understand how parsing really works.
> 
> Yacc certainly makes it easier to write parsers for big grammars, but it's far from cheating. You need to know a lot more about parsing to use Yacc than you need to roll your own. 
> 
> Hand parsing of a tiny grammar is almost a  necessary step on the way to understanding Yacc. But I think hand-building the whole parser for a compiler is unnecessary torture--like doing trigonometry with log tables.
> 
> Doug

In 1971 compiler construction course at UT-Austin, we had to use CDC Fortran to build a compiler for a subset of Algol 60. Undergraduates used punch cards and RJE to the 6600/6400 shared by all but the privleged few.

Charlie

--
voice: +1.512.784.7526       e-mail: sauer@technologists.com <mailto:sauer@technologists.com>           
fax: +1.512.346.5240         web: https://technologists.com/sauer/ <http://technologists.com/sauer/>
Facebook/Google/LinkedIn/mas.to: CharlesHSauer


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

[TUHS] Re: uphill both ways, was Re: What would early alternatives to C have been?

[John Levine]

It appears that Charles H. Sauer <sauer@technologists.com> said:
>In 1971 compiler construction course at UT-Austin, we had to use CDC Fortran to build a compiler for a subset of Algol 60. Undergraduates
>used punch cards and RJE to the 6600/6400 shared by all but the privleged few.

In my 1971 compiler course at Yale, Alan Perlis made us try to write a compiler
that translated a subset of APL into Basic. He suggested we write it in APL,
which was a terrible idea, so I wrote it in Trac, for which I happened to have
written my own interpreter.

I think my compiler was the only one that worked, and it was pretty clever,
turning the APL array expressions into structures with array boundaries and
example expressions, with no array temporaries. It only generated the loops to
evaluate the expressions when storing into another array.

Someone got a PhD in 1978 for a similar compiling technique but in 1971 I was a
17 year old twerp so what did I know?

R's,
John

[TUHS] Re: What would early alternatives to C have been?

[Rob Pike]

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

A rare case where I disagree with you, Doug. If the language is reasonably
regular (I do not mean in the strict Kleene sense), a recursive descent
parser is not much harder to write than a yacc grammar, and much smoother
at providing good error messages. Having done many yaccs and many RD
parsers, I no longer go to yacc.

To put it another way, there are few programming tasks I enjoy more than
writing a recursive descent parser for a sane language.

Now if the language is not so regular, my position might shift. I do recall
Bjarne dynamically editing the generated tables mid-parse to get yacc to
handle at least one stage of C++'s development.

Another way to think of it is that if you are designing the language and it
is undergoing frequent changes in grammar, yacc could certainly be move you
along faster. But even then once things had settled I'd still redo it as
RD, for the quality of the result.

You can credit Stephen R. "Software" Steve for this change in my thinking.

-rob


On Mon, Mar 10, 2025 at 1:12 PM Douglas McIlroy <
douglas.mcilroy@dartmouth.edu> wrote:

> > everyone should write for their first compiler in Pascal for a
> > simple language and no cheating using YACC.  You need to write the whole
> > thing if you want to understand how parsing really works.
>
> Yacc certainly makes it easier to write parsers for big grammars, but
> it's far from cheating. You need to know a lot more about parsing to use
> Yacc than you need to roll your own.
>
> Hand parsing of a tiny grammar is almost a  necessary step on the way to
> understanding Yacc. But I think hand-building the whole parser for a
> compiler is unnecessary torture--like doing trigonometry with log tables.
>
> Doug
>

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

[TUHS] Re: What would early alternatives to C have been?

[John Cowan]

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

I was working at the whiteboard during a job interview once. I had been
asked to write a function to report if its input had balanced parentheses.
No problem: I wrote an RD parser in Python (which I prefer for
whiteboarding) to detect balance and return True if the parse was
successful and False if EOF was reached.

I was starting to write some tests when the interviewer interrupted me.

"What is that?"

"It's a recursive descent parser. It detects if the input is well-formed."

Blank look.

I started to walk him through the code.

He interrupted me. "Excuse me, I'll be back in a few minutes."

Long wait, maybe 15-20 minutes. Someone else comes in. "Thank you, the
recruiter will get back to you." That's the last I hear from them.

On Mon, Mar 10, 2025, 12:10 AM Rob Pike <robpike@gmail.com> wrote:

> A rare case where I disagree with you, Doug. If the language is reasonably
> regular (I do not mean in the strict Kleene sense), a recursive descent
> parser is not much harder to write than a yacc grammar, and much smoother
> at providing good error messages. Having done many yaccs and many RD
> parsers, I no longer go to yacc.
>
> To put it another way, there are few programming tasks I enjoy more than
> writing a recursive descent parser for a sane language.
>
> Now if the language is not so regular, my position might shift. I do
> recall Bjarne dynamically editing the generated tables mid-parse to get
> yacc to handle at least one stage of C++'s development.
>
> Another way to think of it is that if you are designing the language and
> it is undergoing frequent changes in grammar, yacc could certainly be move
> you along faster. But even then once things had settled I'd still redo it
> as RD, for the quality of the result.
>
> You can credit Stephen R. "Software" Steve for this change in my thinking.
>
> -rob
>
>
> On Mon, Mar 10, 2025 at 1:12 PM Douglas McIlroy <
> douglas.mcilroy@dartmouth.edu> wrote:
>
>> > everyone should write for their first compiler in Pascal for a
>> > simple language and no cheating using YACC.  You need to write the whole
>> > thing if you want to understand how parsing really works.
>>
>> Yacc certainly makes it easier to write parsers for big grammars, but
>> it's far from cheating. You need to know a lot more about parsing to use
>> Yacc than you need to roll your own.
>>
>> Hand parsing of a tiny grammar is almost a  necessary step on the way to
>> understanding Yacc. But I think hand-building the whole parser for a
>> compiler is unnecessary torture--like doing trigonometry with log tables.
>>
>> Doug
>>
>

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

[TUHS] Re: What would early alternatives to C have been?

[Dave Horsfall]

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

On Mon, 10 Mar 2025, John Cowan wrote:

> I was working at the whiteboard during a job interview once. I had been
> asked to write a function to report if its input had balanced parentheses. 
> No problem: I wrote an RD parser in Python (which I prefer for
> whiteboarding) to detect balance and return True if the parse was successful
> and False if EOF was reached.

RD is a bit over the top, isn't it?

Pseudocode:

    set counter to 0

    while !EOF
    do
	read char
	char == "(" -> counter++
	char == ")" -> counter--
	abort "Unbalanced: )" if counter < 0
    done

    abort "Unbalanced: (" if counter > 0

Untested, of course :-)

-- Dave

[TUHS] Re: What would early alternatives to C have been?

[Bakul Shah via TUHS]

Perhaps the interviewer was looking for something dumb like the following
and not a full RD parser?

int count = 0;
while (*cp) {
	char c = *cp++;
	count += c == '(' ? 1 : c == ')' ? -1 : 0;
	if (count < 0) return -1; // FAIL: one too many )
}
if (count > 0) return -1; // FAIL: too many (
return 0; // SUCCESS

Though this will fall apart if you also want to also balance braces &/or
brackets and must catch invalid cases like "(..[..)..]"!

> On Mar 10, 2025, at 8:19 AM, John Cowan <cowan@ccil.org> wrote:
> 
> I was working at the whiteboard during a job interview once. I had been asked to write a function to report if its input had balanced parentheses.  No problem: I wrote an RD parser in Python (which I prefer for whiteboarding) to detect balance and return True if the parse was successful and False if EOF was reached.
> 
> I was starting to write some tests when the interviewer interrupted me.
> 
> "What is that?"
> 
> "It's a recursive descent parser. It detects if the input is well-formed."
> 
> Blank look.
> 
> I started to walk him through the code.
> 
> He interrupted me. "Excuse me, I'll be back in a few minutes."
> 
> Long wait, maybe 15-20 minutes. Someone else comes in. "Thank you, the recruiter will get back to you." That's the last I hear from them.

[TUHS] Re: What would early alternatives to C have been?

[Marc Rochkind]

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

This thread started to be about what I thought were system programming
languages (e.g., C, BLISS) and seems to have meandered into a general
discussion of languages that were around in the 1960s and 1970s, so, what
the heck, I'll add my own story.

PL/0 is an education programming language introduced in the book, *Algorithms
+ Data Structures = Programs*, by Niklaus Wirth in 1976. It's a great
language for teaching compiler writing because it contains interesting
concepts, such as recursive functions, yet isn't overly complicated. I
wrote a PL/0 compiler for the IBM 701 (
https://github.com/MarcRochkind/pl0compiler).

Yeah, that's not a misprint. I wrote perhaps the world's only 701 emulator (
https://www.mrochkind.com/mrochkind/a-701.html), and my PL/0 compiler runs
on it. Unfortunately, I can't verify that the compiled code runs on an
actual 701, since I'm sure there haven't been any in operation for many
decades. For those of you who haven't had the pleasure, programming the 701
is really hard. It had no index registers, and the sign bit didn't
participate in shifts. Still, my compiler compiles full-blown PL/0.

So there! ;-)

Marc Rochkind

On Mon, Mar 10, 2025 at 2:49 PM Bakul Shah via TUHS <tuhs@tuhs.org> wrote:

> Perhaps the interviewer was looking for something dumb like the following
> and not a full RD parser?
>
> int count = 0;
> while (*cp) {
>         char c = *cp++;
>         count += c == '(' ? 1 : c == ')' ? -1 : 0;
>         if (count < 0) return -1; // FAIL: one too many )
> }
> if (count > 0) return -1; // FAIL: too many (
> return 0; // SUCCESS
>
> Though this will fall apart if you also want to also balance braces &/or
> brackets and must catch invalid cases like "(..[..)..]"!
>
> > On Mar 10, 2025, at 8:19 AM, John Cowan <cowan@ccil.org> wrote:
> >
> > I was working at the whiteboard during a job interview once. I had been
> asked to write a function to report if its input had balanced parentheses.
> No problem: I wrote an RD parser in Python (which I prefer for
> whiteboarding) to detect balance and return True if the parse was
> successful and False if EOF was reached.
> >
> > I was starting to write some tests when the interviewer interrupted me.
> >
> > "What is that?"
> >
> > "It's a recursive descent parser. It detects if the input is
> well-formed."
> >
> > Blank look.
> >
> > I started to walk him through the code.
> >
> > He interrupted me. "Excuse me, I'll be back in a few minutes."
> >
> > Long wait, maybe 15-20 minutes. Someone else comes in. "Thank you, the
> recruiter will get back to you." That's the last I hear from them.
>
>

-- 
Subscribe to my Photo-of-the-Week emails at my website mrochkind.com.

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

[TUHS] Re: What would early alternatives to C have been?

[Clem Cole]

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

Marc - check out OpenSIMH( https://opensimh.org)
Check out over 40 different simulators including the I7000 which
supports IBM 701,7010,7070,7080, 7090 - https://opensimh.org/simulators/


ᐧ

On Mon, Mar 10, 2025 at 7:12 PM Marc Rochkind <mrochkind@gmail.com> wrote:

> This thread started to be about what I thought were system programming
> languages (e.g., C, BLISS) and seems to have meandered into a general
> discussion of languages that were around in the 1960s and 1970s, so, what
> the heck, I'll add my own story.
>
> PL/0 is an education programming language introduced in the book, *Algorithms
> + Data Structures = Programs*, by Niklaus Wirth in 1976. It's a great
> language for teaching compiler writing because it contains interesting
> concepts, such as recursive functions, yet isn't overly complicated. I
> wrote a PL/0 compiler for the IBM 701 (
> https://github.com/MarcRochkind/pl0compiler).
>
> Yeah, that's not a misprint. I wrote perhaps the world's only 701 emulator
> (https://www.mrochkind.com/mrochkind/a-701.html), and my PL/0 compiler
> runs on it. Unfortunately, I can't verify that the compiled code runs on an
> actual 701, since I'm sure there haven't been any in operation for many
> decades. For those of you who haven't had the pleasure, programming the 701
> is really hard. It had no index registers, and the sign bit didn't
> participate in shifts. Still, my compiler compiles full-blown PL/0.
>
> So there! ;-)
>
> Marc Rochkind
>
> On Mon, Mar 10, 2025 at 2:49 PM Bakul Shah via TUHS <tuhs@tuhs.org> wrote:
>
>> Perhaps the interviewer was looking for something dumb like the following
>> and not a full RD parser?
>>
>> int count = 0;
>> while (*cp) {
>>         char c = *cp++;
>>         count += c == '(' ? 1 : c == ')' ? -1 : 0;
>>         if (count < 0) return -1; // FAIL: one too many )
>> }
>> if (count > 0) return -1; // FAIL: too many (
>> return 0; // SUCCESS
>>
>> Though this will fall apart if you also want to also balance braces &/or
>> brackets and must catch invalid cases like "(..[..)..]"!
>>
>> > On Mar 10, 2025, at 8:19 AM, John Cowan <cowan@ccil.org> wrote:
>> >
>> > I was working at the whiteboard during a job interview once. I had been
>> asked to write a function to report if its input had balanced parentheses.
>> No problem: I wrote an RD parser in Python (which I prefer for
>> whiteboarding) to detect balance and return True if the parse was
>> successful and False if EOF was reached.
>> >
>> > I was starting to write some tests when the interviewer interrupted me.
>> >
>> > "What is that?"
>> >
>> > "It's a recursive descent parser. It detects if the input is
>> well-formed."
>> >
>> > Blank look.
>> >
>> > I started to walk him through the code.
>> >
>> > He interrupted me. "Excuse me, I'll be back in a few minutes."
>> >
>> > Long wait, maybe 15-20 minutes. Someone else comes in. "Thank you, the
>> recruiter will get back to you." That's the last I hear from them.
>>
>>
>
> --
> Subscribe to my Photo-of-the-Week emails at my website mrochkind.com.
>

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

[TUHS] Re: What would early alternatives to C have been?

[Marc Rochkind]

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

Clem, thanks... didn't know about those.

MIne has two features that the other one perhaps doesn't: A fully
functional control panel, and it operates at the speed of the 701.

On Mon, Mar 10, 2025 at 5:49 PM Clem Cole <clemc@ccc.com> wrote:

> Marc - check out OpenSIMH( https://opensimh.org)
> Check out over 40 different simulators including the I7000 which
> supports IBM 701,7010,7070,7080, 7090 - https://opensimh.org/simulators/
>
>
>

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

[TUHS] Re: What would early alternatives to C have been?

[Ken Thompson]

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

re yacc vs RD

i agree that they are about the same,
where the edge would tilt based on the parsed language.
BUT when the parsed language (like go) is not yet defined,
yacc is the only option.



On Mon, Mar 10, 2025 at 4:50 PM Clem Cole <clemc@ccc.com> wrote:

> Marc - check out OpenSIMH( https://opensimh.org)
> Check out over 40 different simulators including the I7000 which
> supports IBM 701,7010,7070,7080, 7090 - https://opensimh.org/simulators/
>
>
> ᐧ
>
> On Mon, Mar 10, 2025 at 7:12 PM Marc Rochkind <mrochkind@gmail.com> wrote:
>
>> This thread started to be about what I thought were system programming
>> languages (e.g., C, BLISS) and seems to have meandered into a general
>> discussion of languages that were around in the 1960s and 1970s, so, what
>> the heck, I'll add my own story.
>>
>> PL/0 is an education programming language introduced in the book, *Algorithms
>> + Data Structures = Programs*, by Niklaus Wirth in 1976. It's a great
>> language for teaching compiler writing because it contains interesting
>> concepts, such as recursive functions, yet isn't overly complicated. I
>> wrote a PL/0 compiler for the IBM 701 (
>> https://github.com/MarcRochkind/pl0compiler).
>>
>> Yeah, that's not a misprint. I wrote perhaps the world's only 701
>> emulator (https://www.mrochkind.com/mrochkind/a-701.html), and my PL/0
>> compiler runs on it. Unfortunately, I can't verify that the compiled code
>> runs on an actual 701, since I'm sure there haven't been any in operation
>> for many decades. For those of you who haven't had the pleasure,
>> programming the 701 is really hard. It had no index registers, and the sign
>> bit didn't participate in shifts. Still, my compiler compiles full-blown
>> PL/0.
>>
>> So there! ;-)
>>
>> Marc Rochkind
>>
>> On Mon, Mar 10, 2025 at 2:49 PM Bakul Shah via TUHS <tuhs@tuhs.org>
>> wrote:
>>
>>> Perhaps the interviewer was looking for something dumb like the following
>>> and not a full RD parser?
>>>
>>> int count = 0;
>>> while (*cp) {
>>>         char c = *cp++;
>>>         count += c == '(' ? 1 : c == ')' ? -1 : 0;
>>>         if (count < 0) return -1; // FAIL: one too many )
>>> }
>>> if (count > 0) return -1; // FAIL: too many (
>>> return 0; // SUCCESS
>>>
>>> Though this will fall apart if you also want to also balance braces &/or
>>> brackets and must catch invalid cases like "(..[..)..]"!
>>>
>>> > On Mar 10, 2025, at 8:19 AM, John Cowan <cowan@ccil.org> wrote:
>>> >
>>> > I was working at the whiteboard during a job interview once. I had
>>> been asked to write a function to report if its input had balanced
>>> parentheses.  No problem: I wrote an RD parser in Python (which I prefer
>>> for whiteboarding) to detect balance and return True if the parse was
>>> successful and False if EOF was reached.
>>> >
>>> > I was starting to write some tests when the interviewer interrupted me.
>>> >
>>> > "What is that?"
>>> >
>>> > "It's a recursive descent parser. It detects if the input is
>>> well-formed."
>>> >
>>> > Blank look.
>>> >
>>> > I started to walk him through the code.
>>> >
>>> > He interrupted me. "Excuse me, I'll be back in a few minutes."
>>> >
>>> > Long wait, maybe 15-20 minutes. Someone else comes in. "Thank you, the
>>> recruiter will get back to you." That's the last I hear from them.
>>>
>>>
>>
>> --
>> Subscribe to my Photo-of-the-Week emails at my website mrochkind.com.
>>
>

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

[TUHS] Re: What would early alternatives to C have been?

[Larry McVoy]

I'm guessing this is because yacc makes it easy to fiddle with the grammar?
Does performance factor in?

I'm actually curious because BitKeeper has what we call a dspec language
which lets you wander through the revision history and print it out in
a sort of awk/printf like language.  If my memory serves me, we had a 
version in yacc (really flex but same thing) and Rob (cc-ed) rewrote 
it in a recursive-descent parser for performance reasons.  If you are
curious, this is a dspec that spits out history in JSON format that 
I wrote because one of my engineers said it was impossible (it wasn't):

http://mcvoy.com/lm/bkdocs/dspec-changes-json-v.txt

$0 .. $9 are variables.  We used $if as a way to get an if statement
rather than just say "if", :whatever: is a way to fish some field out
of the history, Marc will get it, it's SCCS's :D: that means date, we
just took it a lot further.

I don't remember how much faster the RD version was but it was a lot,
for sure more than a factor of 2 and maybe much more than that.  All
I remember is at some point the dspec parser was a performance issue
and after Rob rewrote it, it wasn't.

On Mon, Mar 10, 2025 at 05:06:13PM -0700, Ken Thompson wrote:
> re yacc vs RD
> 
> i agree that they are about the same,
> where the edge would tilt based on the parsed language.
> BUT when the parsed language (like go) is not yet defined,
> yacc is the only option.
> 
> 
> 
> On Mon, Mar 10, 2025 at 4:50???PM Clem Cole <clemc@ccc.com> wrote:
> 
> > Marc - check out OpenSIMH( https://opensimh.org)
> > Check out over 40 different simulators including the I7000 which
> > supports IBM 701,7010,7070,7080, 7090 - https://opensimh.org/simulators/
> >
> >
> > ???
> >
> > On Mon, Mar 10, 2025 at 7:12???PM Marc Rochkind <mrochkind@gmail.com> wrote:
> >
> >> This thread started to be about what I thought were system programming
> >> languages (e.g., C, BLISS) and seems to have meandered into a general
> >> discussion of languages that were around in the 1960s and 1970s, so, what
> >> the heck, I'll add my own story.
> >>
> >> PL/0 is an education programming language introduced in the book, *Algorithms
> >> + Data Structures = Programs*, by Niklaus Wirth in 1976. It's a great
> >> language for teaching compiler writing because it contains interesting
> >> concepts, such as recursive functions, yet isn't overly complicated. I
> >> wrote a PL/0 compiler for the IBM 701 (
> >> https://github.com/MarcRochkind/pl0compiler).
> >>
> >> Yeah, that's not a misprint. I wrote perhaps the world's only 701
> >> emulator (https://www.mrochkind.com/mrochkind/a-701.html), and my PL/0
> >> compiler runs on it. Unfortunately, I can't verify that the compiled code
> >> runs on an actual 701, since I'm sure there haven't been any in operation
> >> for many decades. For those of you who haven't had the pleasure,
> >> programming the 701 is really hard. It had no index registers, and the sign
> >> bit didn't participate in shifts. Still, my compiler compiles full-blown
> >> PL/0.
> >>
> >> So there! ;-)
> >>
> >> Marc Rochkind
> >>
> >> On Mon, Mar 10, 2025 at 2:49???PM Bakul Shah via TUHS <tuhs@tuhs.org>
> >> wrote:
> >>
> >>> Perhaps the interviewer was looking for something dumb like the following
> >>> and not a full RD parser?
> >>>
> >>> int count = 0;
> >>> while (*cp) {
> >>>         char c = *cp++;
> >>>         count += c == '(' ? 1 : c == ')' ? -1 : 0;
> >>>         if (count < 0) return -1; // FAIL: one too many )
> >>> }
> >>> if (count > 0) return -1; // FAIL: too many (
> >>> return 0; // SUCCESS
> >>>
> >>> Though this will fall apart if you also want to also balance braces &/or
> >>> brackets and must catch invalid cases like "(..[..)..]"!
> >>>
> >>> > On Mar 10, 2025, at 8:19???AM, John Cowan <cowan@ccil.org> wrote:
> >>> >
> >>> > I was working at the whiteboard during a job interview once. I had
> >>> been asked to write a function to report if its input had balanced
> >>> parentheses.  No problem: I wrote an RD parser in Python (which I prefer
> >>> for whiteboarding) to detect balance and return True if the parse was
> >>> successful and False if EOF was reached.
> >>> >
> >>> > I was starting to write some tests when the interviewer interrupted me.
> >>> >
> >>> > "What is that?"
> >>> >
> >>> > "It's a recursive descent parser. It detects if the input is
> >>> well-formed."
> >>> >
> >>> > Blank look.
> >>> >
> >>> > I started to walk him through the code.
> >>> >
> >>> > He interrupted me. "Excuse me, I'll be back in a few minutes."
> >>> >
> >>> > Long wait, maybe 15-20 minutes. Someone else comes in. "Thank you, the
> >>> recruiter will get back to you." That's the last I hear from them.
> >>>
> >>>
> >>
> >> --
> >> Subscribe to my Photo-of-the-Week emails at my website mrochkind.com.
> >>
> >

-- 
---
Larry McVoy           Retired to fishing          http://www.mcvoy.com/lm/boat

[TUHS] Re: What would early alternatives to C have been?

[Ken Thompson]

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

i find that SD and yacc have about the same
time performance. yacc gets a bad rep when
it uses lex as its front-end. then it is pig-slow.


On Mon, Mar 10, 2025 at 6:52 PM Larry McVoy <lm@mcvoy.com> wrote:

> I'm guessing this is because yacc makes it easy to fiddle with the grammar?
> Does performance factor in?
>
> I'm actually curious because BitKeeper has what we call a dspec language
> which lets you wander through the revision history and print it out in
> a sort of awk/printf like language.  If my memory serves me, we had a
> version in yacc (really flex but same thing) and Rob (cc-ed) rewrote
> it in a recursive-descent parser for performance reasons.  If you are
> curious, this is a dspec that spits out history in JSON format that
> I wrote because one of my engineers said it was impossible (it wasn't):
>
> http://mcvoy.com/lm/bkdocs/dspec-changes-json-v.txt
>
> $0 .. $9 are variables.  We used $if as a way to get an if statement
> rather than just say "if", :whatever: is a way to fish some field out
> of the history, Marc will get it, it's SCCS's :D: that means date, we
> just took it a lot further.
>
> I don't remember how much faster the RD version was but it was a lot,
> for sure more than a factor of 2 and maybe much more than that.  All
> I remember is at some point the dspec parser was a performance issue
> and after Rob rewrote it, it wasn't.
>
> On Mon, Mar 10, 2025 at 05:06:13PM -0700, Ken Thompson wrote:
> > re yacc vs RD
> >
> > i agree that they are about the same,
> > where the edge would tilt based on the parsed language.
> > BUT when the parsed language (like go) is not yet defined,
> > yacc is the only option.
> >
> >
> >
> > On Mon, Mar 10, 2025 at 4:50???PM Clem Cole <clemc@ccc.com> wrote:
> >
> > > Marc - check out OpenSIMH( https://opensimh.org)
> > > Check out over 40 different simulators including the I7000 which
> > > supports IBM 701,7010,7070,7080, 7090 -
> https://opensimh.org/simulators/
> > >
> > >
> > > ???
> > >
> > > On Mon, Mar 10, 2025 at 7:12???PM Marc Rochkind <mrochkind@gmail.com>
> wrote:
> > >
> > >> This thread started to be about what I thought were system programming
> > >> languages (e.g., C, BLISS) and seems to have meandered into a general
> > >> discussion of languages that were around in the 1960s and 1970s, so,
> what
> > >> the heck, I'll add my own story.
> > >>
> > >> PL/0 is an education programming language introduced in the book,
> *Algorithms
> > >> + Data Structures = Programs*, by Niklaus Wirth in 1976. It's a great
> > >> language for teaching compiler writing because it contains interesting
> > >> concepts, such as recursive functions, yet isn't overly complicated. I
> > >> wrote a PL/0 compiler for the IBM 701 (
> > >> https://github.com/MarcRochkind/pl0compiler).
> > >>
> > >> Yeah, that's not a misprint. I wrote perhaps the world's only 701
> > >> emulator (https://www.mrochkind.com/mrochkind/a-701.html), and my
> PL/0
> > >> compiler runs on it. Unfortunately, I can't verify that the compiled
> code
> > >> runs on an actual 701, since I'm sure there haven't been any in
> operation
> > >> for many decades. For those of you who haven't had the pleasure,
> > >> programming the 701 is really hard. It had no index registers, and
> the sign
> > >> bit didn't participate in shifts. Still, my compiler compiles
> full-blown
> > >> PL/0.
> > >>
> > >> So there! ;-)
> > >>
> > >> Marc Rochkind
> > >>
> > >> On Mon, Mar 10, 2025 at 2:49???PM Bakul Shah via TUHS <tuhs@tuhs.org>
> > >> wrote:
> > >>
> > >>> Perhaps the interviewer was looking for something dumb like the
> following
> > >>> and not a full RD parser?
> > >>>
> > >>> int count = 0;
> > >>> while (*cp) {
> > >>>         char c = *cp++;
> > >>>         count += c == '(' ? 1 : c == ')' ? -1 : 0;
> > >>>         if (count < 0) return -1; // FAIL: one too many )
> > >>> }
> > >>> if (count > 0) return -1; // FAIL: too many (
> > >>> return 0; // SUCCESS
> > >>>
> > >>> Though this will fall apart if you also want to also balance braces
> &/or
> > >>> brackets and must catch invalid cases like "(..[..)..]"!
> > >>>
> > >>> > On Mar 10, 2025, at 8:19???AM, John Cowan <cowan@ccil.org> wrote:
> > >>> >
> > >>> > I was working at the whiteboard during a job interview once. I had
> > >>> been asked to write a function to report if its input had balanced
> > >>> parentheses.  No problem: I wrote an RD parser in Python (which I
> prefer
> > >>> for whiteboarding) to detect balance and return True if the parse was
> > >>> successful and False if EOF was reached.
> > >>> >
> > >>> > I was starting to write some tests when the interviewer
> interrupted me.
> > >>> >
> > >>> > "What is that?"
> > >>> >
> > >>> > "It's a recursive descent parser. It detects if the input is
> > >>> well-formed."
> > >>> >
> > >>> > Blank look.
> > >>> >
> > >>> > I started to walk him through the code.
> > >>> >
> > >>> > He interrupted me. "Excuse me, I'll be back in a few minutes."
> > >>> >
> > >>> > Long wait, maybe 15-20 minutes. Someone else comes in. "Thank you,
> the
> > >>> recruiter will get back to you." That's the last I hear from them.
> > >>>
> > >>>
> > >>
> > >> --
> > >> Subscribe to my Photo-of-the-Week emails at my website mrochkind.com.
> > >>
> > >
>
> --
> ---
> Larry McVoy           Retired to fishing
> http://www.mcvoy.com/lm/boat
>

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

[TUHS] Re: parsing tools, was What would early alternatives

[John Levine]

According to Ken Thompson <kenbob@gmail.com>:
>-=-=-=-=-=-
>
>i find that SD and yacc have about the same
>time performance. yacc gets a bad rep when
>it uses lex as its front-end. then it is pig-slow.

Parsing is never a performance issue since its time is generally O(n)
where n is the number of tokens emitted by the lexer and the constant
is not large. The lexer always is because it's the only part of the
compiler that has to look at every input character separately. If a
compiler does a lot of optimization, the analysis for that can be
slow, too.

Lex was a dog. Flex, which as far as I know was a complete rewrite
that shared no code with lex, are not bad.
-- 
Regards,
John Levine, johnl@taugh.com, Primary Perpetrator of "The Internet for Dummies",
Please consider the environment before reading this e-mail. https://jl.ly

[TUHS] Re: parsing tools, was What would early alternatives

[Rich Salz]

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

>
> Lex was a dog. Flex, which as far as I know was a complete rewrite
> that shared no code with lex, are not bad.
>

Yes, "it's true what they say about lex" was a common phrase.  (I think I
first saw it in the pathalias paper.)

There was a Usenix presentation -- late 80's (Washington?) but I couldn't
find it. -- by Vern Paxson about his rewrite called flex. I think he said
that the main reason lex was slow was the clever folding it had to do of
its internal tables to fit. Sadly Vern never got his paper in, but the
presentation showed a group with three lines, one at the top being slow
lex, the next two much lower on the Y axis being very close. He said the
second line was flex. Someone said what about the third, fastest, line? His
answer "that's cat"

Vern worked with Van on early network improvements (web-search the both of
them for a fun time).

Flex first posted to Usenet in 1988,
https://groups.google.com/g/comp.sources.unix/c/LZ_EHqd7XBg

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

[TUHS] Re: parsing tools, was What would early alternatives

[Larry McVoy]

On Tue, Mar 11, 2025 at 10:22:00PM -0400, Rich Salz wrote:
> Vern worked with Van on early network improvements (web-search the both of
> them for a fun time).

Van was my networking hero until Drew at Netfix did the two side by side
stacks.  I'm not sure who is better, but I'm sure they are both better
than me and I don't suck.  I agree with Rich, check Van out, check Drew
out.

[TUHS] Re: parsing tools, was What would early alternatives

[John R Levine]

On Tue, 11 Mar 2025, Rich Salz wrote:
>> Lex was a dog. Flex, which as far as I know was a complete rewrite
>> that shared no code with lex, are not bad.
> There was a Usenix presentation -- late 80's (Washington?) but I couldn't
> find it. -- by Vern Paxson about his rewrite called flex. I think he said
> that the main reason lex was slow was the clever folding it had to do of
> its internal tables to fit.

Maybe, maybe not just great programming.

It was mostly written by a summer student named Eric Schmidt.  I wonder 
what happened to him.

Regards,
John Levine, johnl@taugh.com, Taughannock Networks, Trumansburg NY
Please consider the environment before reading this e-mail. https://jl.ly

[TUHS] Re: parsing tools, was What would early alternatives

[Greg A. Woods]

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

At 12 Mar 2025 01:36:09 -0000, "John Levine" <johnl@taugh.com> wrote:
Subject: [TUHS] Re: parsing tools, was What would early alternatives
>
> Lex was a dog. Flex, which as far as I know was a complete rewrite
> that shared no code with lex, are not bad.

I've always understood the 'F' in Flex stood for "Fast".  In fact it
says as much right in the title of the manual page (right from the first
post to Usenet):

	flex - fast lexical analyzer generator

--
					Greg A. Woods <gwoods@acm.org>

Kelowna, BC     +1 250 762-7675           RoboHack <woods@robohack.ca>
Planix, Inc. <woods@planix.com>     Avoncote Farms <woods@avoncote.ca>

[-- Attachment #2: OpenPGP Digital Signature --]
[-- Type: application/pgp-signature, Size: 195 bytes --]

[TUHS] Re: What would early alternatives to C have been?

[John Cowan]

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

Very probably. But under pressure I went with what I knew I could get
right.  In hindsight it was like one of those non-quantitative
multiple-choice tests where you have to figure out not the correct answer
but the answer that the test author is most likely to believe to be correct.

On Mon, Mar 10, 2025, 4:49 PM Bakul Shah <bakul@iitbombay.org> wrote:

> Perhaps the interviewer was looking for something dumb like the following
> and not a full RD parser?
>
> int count = 0;
> while (*cp) {
>         char c = *cp++;
>         count += c == '(' ? 1 : c == ')' ? -1 : 0;
>         if (count < 0) return -1; // FAIL: one too many )
> }
> if (count > 0) return -1; // FAIL: too many (
> return 0; // SUCCESS
>
> Though this will fall apart if you also want to also balance braces &/or
> brackets and must catch invalid cases like "(..[..)..]"!
>
> > On Mar 10, 2025, at 8:19 AM, John Cowan <cowan@ccil.org> wrote:
> >
> > I was working at the whiteboard during a job interview once. I had been
> asked to write a function to report if its input had balanced parentheses.
> No problem: I wrote an RD parser in Python (which I prefer for
> whiteboarding) to detect balance and return True if the parse was
> successful and False if EOF was reached.
> >
> > I was starting to write some tests when the interviewer interrupted me.
> >
> > "What is that?"
> >
> > "It's a recursive descent parser. It detects if the input is
> well-formed."
> >
> > Blank look.
> >
> > I started to walk him through the code.
> >
> > He interrupted me. "Excuse me, I'll be back in a few minutes."
> >
> > Long wait, maybe 15-20 minutes. Someone else comes in. "Thank you, the
> recruiter will get back to you." That's the last I hear from them.
>
>

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

[TUHS] Re: What would early alternatives to C have been?

[Clem Cole]

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

below...  (At the risk of a case of being in disagreement with someone I
rarely am).

On Sun, Mar 9, 2025 at 10:03 PM Douglas McIlroy <
douglas.mcilroy@dartmouth.edu> wrote:

>
> Yacc certainly makes it easier to write parsers for big grammars, but
> it's far from cheating. You need to know a lot more about parsing to use
> Yacc than you need to roll your own.
>
I disagree here.  I have wtchged too many young programmers that I realized
did not understand what yacc  was doing and came to understanding that
never built a simple parse before.
I'm not asking them to rebuild a parser for Algol68 or  C++ in a one
semester course.  I asking that to you take something like Dennis Allisons
"tiny basic" assignment for his Stanfrodf students in the lat 1970s and ask
them to build that.

Peter Hibbard gave us a super small Algol-ish language, and we generated
code for the "CMU Mini" (which was basically Gordon Bell's the precursor to
the PDP-8 (see ISP below) - in my time the "Dragon Book was not yet written
BTW.  I really understood what Stev had accomplished.

The interesting thing is while I tend to use yacc for most parsers, I've
found myself building recursive descent parsers in a couple of cases where
it seems to make better sense.


>
> Hand parsing of a tiny grammar is almost a  necessary step on the way to
> understanding Yacc. But I think hand-building the whole parser for a
> compiler is unnecessary torture--like doing trigonometry with log tables.
>
Point table ... however a funny thing to consider. My father was a high
school math teacher for 40 years. He noted that the loss of slide rules and
trig tables made his "modern" (post-calculator) students not understand
interpolation.To me, learning to use mathematical tables is a skill that
never hurts.  I don't even think of asking people "to walk uphill both ways
to school in the snow and rain instead of riding a heated, dry yellow
school bus." I am asking the student to learn foundational ideas and build
skills up top of core understanding.
ᐧ

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

[TUHS] Re: What would early alternatives to C have been?

[Dan Cross]

On Mon, Mar 10, 2025 at 11:13 AM Clem Cole <clemc@ccc.com> wrote:
> On Sun, Mar 9, 2025 at 10:03 PM Douglas McIlroy <douglas.mcilroy@dartmouth.edu> wrote:
>> Yacc certainly makes it easier to write parsers for big grammars, but it's far from cheating. You need to know a lot more about parsing to use Yacc than you need to roll your own.
>
> I disagree here.  I have wtchged too many young programmers that I realized did not understand what yacc  was doing and came to understanding that never built a simple parse before.

Funny, I agree with both of you, and with Rob. :-)

If I'm not mistaken, I think what Doug was suggesting was that, to
really understand what YACC is _doing_ requires understanding a lot
more about the theory of parsing, grammars, and so on, than one needs
to understand to write a fairly simple RD parser.  RD makes a lot of
sense intuitively, but once you introduce table-driven parsing,
LALR(1), etc, you get into a whole different level of theory and
rigor. Of course, by design the tool abstracts that away from you, so
to just _use_ it you don't necessarily need to understand as much.

>[...]
> The interesting thing is while I tend to use yacc for most parsers, I've found myself building recursive descent parsers in a couple of cases where it seems to make better sense.

Funny, I'm the opposite: I've used YACC for a few parsers, but prefer
to roll my own. I find that I'm either parsing something very simple,
in which case reaching for YACC feels like cutting butter with a
chainsaw, or I need to do something that YACC isn't super great at
(like run in a multithreaded environment). YACC is superb at what it
does, but not something I feel like I need that often.

        - Dan C.