From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on inbox.vuxu.org X-Spam-Level: X-Spam-Status: No, score=-0.7 required=5.0 tests=DKIM_ADSP_CUSTOM_MED, DKIM_INVALID,DKIM_SIGNED,FREEMAIL_FORGED_FROMDOMAIN,FREEMAIL_FROM, HEADER_FROM_DIFFERENT_DOMAINS,HTML_MESSAGE,MAILING_LIST_MULTI, URIBL_SBL_A autolearn=ham autolearn_force=no version=3.4.4 Received: from minnie.tuhs.org (minnie.tuhs.org [IPv6:2600:3c01:e000:146::1]) by inbox.vuxu.org (Postfix) with ESMTP id 6380F211D4 for ; Tue, 11 Mar 2025 06:08:17 +0100 (CET) Received: from minnie.tuhs.org (localhost [IPv6:::1]) by minnie.tuhs.org (Postfix) with ESMTP id AF1944415B; Tue, 11 Mar 2025 15:08:11 +1000 (AEST) Received: from mail-ot1-x331.google.com (mail-ot1-x331.google.com [IPv6:2607:f8b0:4864:20::331]) by minnie.tuhs.org (Postfix) with ESMTPS id 4AAF444159 for ; Tue, 11 Mar 2025 15:08:07 +1000 (AEST) Received: by mail-ot1-x331.google.com with SMTP id 46e09a7af769-728a274632eso2912699a34.3 for ; Mon, 10 Mar 2025 22:08:07 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1741669686; x=1742274486; darn=tuhs.org; h=cc:to:subject:message-id:date:from:in-reply-to:references :mime-version:from:to:cc:subject:date:message-id:reply-to; bh=xZkxQ1UH8Nk4SJ6hkiSZmzufgS0a72qMh8rANsfgj1w=; b=LUqOwU1wibpdKVjr3fCaPTKZFzOFd9IogCJb7qd1uvqm43BVJpczsYw/piqibHILVg GJMS4CKwYy8hM4BoWWgYRfCc28djf2ya9FcShpsXmn3cQ5LCKEhAbM+UJVRS7q2CG9qJ ZY3EpBRJ2k3bUTWaOw+KZiQuhwJWGwNfizcfuY0dq23qJdQzAXHzFk9BK4fGZaGsgGSl zYog3iY0ZxAdv3Rj/YiIPWq2xizKnv3VxagaTRzKLEJFVMXFGAh3zSPlwBYmLVk1WAL+ tjqhZYagO2YdXtfpb/pMMwpxq6atRrvzoYSt73aJ6qnUXmy/ReCWOIFh7LUEwob67o3s GOrA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1741669686; x=1742274486; h=cc:to:subject:message-id:date:from:in-reply-to:references :mime-version:x-gm-message-state:from:to:cc:subject:date:message-id :reply-to; bh=xZkxQ1UH8Nk4SJ6hkiSZmzufgS0a72qMh8rANsfgj1w=; b=dKfHqF/RQXbLMYK2j1emCxASBPwOh/pzDO9G/nKIsI4ky94TZjQY57gXf4JdQC0M1V uy4NElojS0Yw3zjJK/wQljdAGJBv5lFRQdtnIHcZ8f3iKKP4xSgFtcscrLDfGo+ubUYC 6T2B4rugL2a5nVKKosTPy/wD4j2eL+Qpv0xPkdqJEmgxeaYpVtg0VAHED2XFFTZLI2dR wpGjIbcU90bAGgTPXRS8Dfew5ObHgrldjarlb3l7WD7z6T7tHoQvNEJeCIhJSZlqwgFY DYpTqcG3zlPBiDzkQL/coJJaPc428u499IuM9y6xJVqGDOVbJLH4l3dV5SkZ8MAtCzjd ePWg== X-Gm-Message-State: AOJu0Yxy+TII/MG8LrG7DbZq/2x0XJKnNtFq9+8NP94+LbG5cTYH+Xjj uZQpgQE+Nx3/bUAct/wNiyAdyHwPQoh+PO1/AGKc89WRrsHh71RCfVFJ7qPKkMFAY6YNbXabgPc D3K0qC52BYFVUyuBhhqJODICXiwTIxw== X-Gm-Gg: ASbGncticmUHsZ9AmeU7LLTKaB4pctLD5u8yZhyzGhBOZrn4AYUERY5cIcRwjmBNrwZ LfuSNdhpz6jQLKr9SJaGOi2O9Q4z480253UhiNFaJFrDPmfz085qSN+HzM9oPzphlGLqMMfjJ5X si/vDrx+06V/H3O7noGxbs1Tk7cw== X-Google-Smtp-Source: AGHT+IGaM9E/jcq97CHvqU+auAAQHU4+4rx9IE9yDGfPZ51o//4locF4h+1t2gFmYUsyXL0YXijPCcq2jxWXzqrSEFs= X-Received: by 2002:a05:6830:668e:b0:72b:7faa:93b0 with SMTP id 46e09a7af769-72b7faa985bmr4807794a34.1.1741669686076; Mon, 10 Mar 2025 22:08:06 -0700 (PDT) MIME-Version: 1.0 References: <20250311013502.GF24601@mcvoy.com> In-Reply-To: <20250311013502.GF24601@mcvoy.com> From: Ken Thompson Date: Mon, 10 Mar 2025 22:07:54 -0700 X-Gm-Features: AQ5f1Jo5dEmGhHYkCyT1YY0jWEeHxZnnuDtgWWRqalRlzG0dRXNJeAayCjXl9Ho Message-ID: To: Larry McVoy Content-Type: multipart/alternative; boundary="000000000000f46cc806300a12a3" Message-ID-Hash: 3ILKVMIEHGYU6MCFNPQRMOOWSYXQFDAK X-Message-ID-Hash: 3ILKVMIEHGYU6MCFNPQRMOOWSYXQFDAK X-MailFrom: kenbob@gmail.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 , rob@bolabs.com X-Mailman-Version: 3.3.6b1 Precedence: list Subject: [TUHS] Re: What would early alternatives to C have been? List-Id: The Unix Heritage Society mailing list Archived-At: List-Archive: List-Help: List-Owner: List-Post: List-Subscribe: List-Unsubscribe: --000000000000f46cc806300a12a3 Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable 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=E2=80=AFPM Larry McVoy wrote: > I'm guessing this is because yacc makes it easy to fiddle with the gramma= r? > 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 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 > wrote: > > > > > >> This thread started to be about what I thought were system programmi= ng > > >> languages (e.g., C, BLISS) and seems to have meandered into a genera= l > > >> 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 =3D Programs*, by Niklaus Wirth in 1976. It's a gr= eat > > >> language for teaching compiler writing because it contains interesti= ng > > >> 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 > > >> wrote: > > >> > > >>> Perhaps the interviewer was looking for something dumb like the > following > > >>> and not a full RD parser? > > >>> > > >>> int count =3D 0; > > >>> while (*cp) { > > >>> char c =3D *cp++; > > >>> count +=3D c =3D=3D '(' ? 1 : c =3D=3D ')' ? -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 wrote: > > >>> > > > >>> > I was working at the whiteboard during a job interview once. I ha= d > > >>> 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 w= as > > >>> 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 > --000000000000f46cc806300a12a3 Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable
i find that SD and yacc have about the same
time perfo= rmance. yacc gets a bad rep when
it uses lex as its front-end. th= en it is pig-slow.


On Mon, Mar 10= , 2025 at 6:52=E2=80=AFPM Larry McVoy <l= m@mcvoy.com> wrote:
I'm guessing this is because yacc makes it easy to fiddle wi= th the grammar?
Does performance factor in?

I'm actually curious because BitKeeper has what we call a dspec languag= e
which lets you wander through the revision history and print it out in
a sort of awk/printf like language.=C2=A0 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.=C2=A0 If you are<= br> 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.t= xt

$0 .. $9 are variables.=C2=A0 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.=C2=A0 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<= br> > > supports IBM 701,7010,7070,7080, 7090 - https://opensimh.o= rg/simulators/
> >
> >
> > ???
> >
> > On Mon, Mar 10, 2025 at 7:12???PM Marc Rochkind <mrochkind@gmail.com> wro= te:
> >
> >> This thread started to be about what I thought were system pr= ogramming
> >> languages (e.g., C, BLISS) and seems to have meandered into a= general
> >> discussion of languages that were around in the 1960s and 197= 0s, so, what
> >> the heck, I'll add my own story.
> >>
> >> PL/0 is an education programming language introduced in the b= ook, *Algorithms
> >> + Data Structures =3D Programs*, by Niklaus Wirth in 1976. It= 's a great
> >> language for teaching compiler writing because it contains in= teresting
> >> concepts, such as recursive functions, yet isn't overly c= omplicated. I
> >> wrote a PL/0 compiler for the IBM 701 (
> >> https://github.com/MarcRochkind/pl0compil= er).
> >>
> >> Yeah, that's not a misprint. I wrote perhaps the world= 9;s only 701
> >> emulator (https://www.mrochkind.com/mroc= hkind/a-701.html), and my PL/0
> >> compiler runs on it. Unfortunately, I can't verify that t= he compiled code
> >> runs on an actual 701, since I'm sure there haven't b= een any in operation
> >> for many decades. For those of you who haven't had the pl= easure,
> >> programming the 701 is really hard. It had no index registers= , and the sign
> >> bit didn't participate in shifts. Still, my compiler comp= iles 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 li= ke the following
> >>> and not a full RD parser?
> >>>
> >>> int count =3D 0;
> >>> while (*cp) {
> >>>=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0char c =3D *cp++;
> >>>=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0count +=3D c =3D=3D '= ;(' ? 1 : c =3D=3D ')' ? -1 : 0;
> >>>=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0if (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 bala= nce 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 intervi= ew once. I had
> >>> been asked to write a function to report if its input had= balanced
> >>> parentheses.=C2=A0 No problem: I wrote an RD parser in Py= thon (which I prefer
> >>> for whiteboarding) to detect balance and return True if t= he parse was
> >>> successful and False if EOF was reached.
> >>> >
> >>> > I was starting to write some tests when the intervie= wer interrupted me.
> >>> >
> >>> > "What is that?"
> >>> >
> >>> > "It's a recursive descent parser. It detect= s 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 i= n. "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.c= om.
> >>
> >

--
---
Larry McVoy=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0Retired to fishing=C2= =A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 http://www.mcvoy.com/lm/boat
--000000000000f46cc806300a12a3--