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.5 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 autolearn=ham autolearn_force=no version=3.4.4 Received: from minnie.tuhs.org (minnie.tuhs.org [50.116.15.146]) by inbox.vuxu.org (Postfix) with ESMTP id 17BEA20043 for ; Wed, 8 May 2024 15:12:55 +0200 (CEST) Received: from minnie.tuhs.org (localhost [IPv6:::1]) by minnie.tuhs.org (Postfix) with ESMTP id 95A6E432F7; Wed, 8 May 2024 23:12:49 +1000 (AEST) Received: from mail-pj1-x102d.google.com (mail-pj1-x102d.google.com [IPv6:2607:f8b0:4864:20::102d]) by minnie.tuhs.org (Postfix) with ESMTPS id B6292432EF for ; Wed, 8 May 2024 23:12:40 +1000 (AEST) Received: by mail-pj1-x102d.google.com with SMTP id 98e67ed59e1d1-2b239b5fedaso3359418a91.0 for ; Wed, 08 May 2024 06:12:40 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1715173960; x=1715778760; 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=IhKEulELZMNqCrV1IKgi9jRxCLhq9Vv5IoMr6HeDf58=; b=Tsc1Xq4X9dhGIo94V+0kapLY/wjhhmigObSgmuW0Tp5QVpS9wb5q4Ez1G5ED1cQRB2 POschemsABEUdeSKSjHFBakeXiCVejSe7kfE7/OtOtoCod50jUr5PqhOmhjbYgZlxfAy 3VXbxjaw21bl/sROqWKF9+Zv6kk/4B64nR4ZkC3XybCG7/D+YNEwCIknqhYkSoNn29S8 GUGNtXSx8xAabHdDakPp9S7FGai6rRbd98P+eODsKGgREd4RQ9K23kFnaNph7cMCmSEP 5YHC+CQ62fbQBKmsjkqQ8vpZn86c4bhwCVnBT/3hAxXKCEgycxcEVXLFoyP5BRpfYerB 3m1w== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1715173960; x=1715778760; 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=IhKEulELZMNqCrV1IKgi9jRxCLhq9Vv5IoMr6HeDf58=; b=bObjabb507ALDzwznqtmdQS3T5nHjSno6lPZAu/+AQWeNVqcpO1zfwoesjIOL3pKVj ad9BhrjobG2ge//bjsxvJGCdLbfGTyVJlwysf5FfTb3v0KnZG9+wQ918zl9LJUBb745A 3zumXa+9CEMTYvyjh/TALyvWIcDMcXg1MKNQfJMYUDafkTh76UWzXzw+mxsJixzq4daj b+qglaqOXF7jBFPEcFu9dKWXwZR+59mlb7BUDZy5Yv6SOWjrpMQF322WnCWGmsmewXv3 sA3uhACmXoqMUC77Dvl50FkwvUXG2OjybOhBD+ZDQUGUN2E8aJwnrgqGQdjmUcfvJ0yn dbeQ== X-Gm-Message-State: AOJu0YwDrz6SnpdNm9wXbg+quWZE9sDR/QHwOqWk0VD5zM3F9WRG1qE3 GilrCnvzhW/P9ebZKBd6Ns9ciBE91SILDe7JP+6ul7u6tMFJ1eFsgR1qKwdAS5wRKFrhdm4NtlM 0K/yuYBt68scos0U/y14YX6yurke2xw== X-Google-Smtp-Source: AGHT+IFZ9gHWHvWv7zmPvfYutegehb0LMkEh0ZaBHlostBXRPmC6xL6uS5tDsXKxJcZvqELhghISvGzxgabBJCOvrdw= X-Received: by 2002:a17:90a:fa02:b0:2b2:7c53:2601 with SMTP id 98e67ed59e1d1-2b6169e1edamr2290769a91.37.1715173959727; Wed, 08 May 2024 06:12:39 -0700 (PDT) MIME-Version: 1.0 References: <18efd14f-4da6-4771-ad6a-901c6cb6105d@planet.nl> <57a37626-728c-4f34-b08b-a4f521f1db03@planet.nl> In-Reply-To: <57a37626-728c-4f34-b08b-a4f521f1db03@planet.nl> From: Rob Pike Date: Wed, 8 May 2024 23:12:28 +1000 Message-ID: To: Paul Ruizendaal Content-Type: multipart/alternative; boundary="0000000000009904620617f10e95" Message-ID-Hash: L7P47TVDFJTB3HJIUC5XHU22ROQR5KQF X-Message-ID-Hash: L7P47TVDFJTB3HJIUC5XHU22ROQR5KQF X-MailFrom: robpike@gmail.com X-Mailman-Rule-Misses: dmarc-mitigation; no-senders; approved; emergency; loop; banned-address; member-moderation; nonmember-moderation; administrivia; implicit-dest; max-recipients; max-size; news-moderation; no-subject; digests; suspicious-header CC: tuhs@tuhs.org X-Mailman-Version: 3.3.6b1 Precedence: list Subject: [TUHS] Re: On the uniqueness of DMR's C compiler List-Id: The Unix Heritage Society mailing list Archived-At: List-Archive: List-Help: List-Owner: List-Post: List-Subscribe: List-Unsubscribe: --0000000000009904620617f10e95 Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable I believe Ken Thompson might have been a referee for that paper. At least, he once mentioned to me that he had reviewed a paper about the threading in the DEC Fortran compiler. -rob On Wed, May 8, 2024 at 7:35=E2=80=AFPM Paul Ruizendaal wrot= e: > Thanks for pointing that out. Here's an interesting paper on the DEC PDP1= 1 > Fortran compilers: > > http://forum.6502.org/download/file.php?id=3D1724&sid=3Df6a721f3e05774cff= 076da72f5a731a6 > > Before 1975 they used direct threading, thereafter there was a native > compiler for the higher-end models. I think this one may have required > split i/d, but that is not entirely clear from the text. > > I think the same holds for BCPL on the PDP11: compiling to "ocode" or > "intcode" in the early 70s, native thereafter -- still have to find sourc= e > for the latter. > > Still, I should have first asked: Does anyone have pointers to small > machine native compilers from the 1970's that produced efficient assemble= r > output? > > I am already aware of the 1978 Whitesmith C compiler. > > 7 May 2024 23:07:58 Rob Pike : > > I'm not sure I accept your starting position. There were several compiler= s > for RT-11 and RSX/11-M. RSX (and perhaps RT) Fortran were threaded code, > but I don't believe they all were. And of course there was BCPL, which wa= s > - and is - tiny; was it on the 11? > > And there were other small machines from other manufacturers, all of whic= h > had some form of Fortran and other bespoke things, such as RPG on the sma= ll > IBMs. I think the uniqueness was in the set of conditions more than in th= e > Unix C compiler itself. > > But you may be right. > > -rob > > > > > On Wed, May 8, 2024 at 6:59=E2=80=AFAM Paul Ruizendaal wr= ote: > >> In the last months, I've spent a little time on curating John Walker's >> Unix clone and software stack, including an emulator to run it: >> https://gitlab.com/marinchip >> >> After creating a basic tool chain (edit, asm, link and a simple >> executive), John set out to find a compiler. Among the first programs w= ere >> a port of the META 3 compiler-generator (similar to TMG on early Unix) a= nd >> a port of Birch-Hansen=E2=80=99s Pascal compiler. META was used to creat= e a >> compiler that generated threaded code. He found neither compiler good >> enough for his goals and settled on writing his Unix-like OS in assemble= r. >> As the 9900 architecture withered after 1980, this sealed the fate of th= is >> OS early on -- had he found a good compiler, the code might have compete= d >> alongside Coherent, Idris, and Minix during the 80=E2=80=99s. >> >> This made me realise once more how unique the Ritchie C compiler was. In >> my view its uniqueness combines three aspects: >> 1. The C language itself >> 2. The ability to run natively on small hardware (even an LSI-11 system) >> 3. Generating code with modest overhead versus handwritten assembler (sa= y >> 30%) >> >> As has been observed before, working at a higher abstraction level makes >> it easier to work on algorithms and on refactoring, often earning back t= he >> efficiency loss. John Walkers work may be case in point: I estimate that >> his hand-coded kernel is 10% larger than an equivalent V6 Unix kernel (a= s >> compiled for the 9900 architecture). >> >> There are three papers on DMR=E2=80=99s website about the history of the= compiler >> and a compare-and-contrast with other compilers of the era: >> https://www.bell-labs.com/usr/dmr/www/primevalC.html >> https://www.bell-labs.com/usr/dmr/www/chist.html >> https://www.bell-labs.com/usr/dmr/www/hopl.html >> >> It seems to me that these papers rather understate the importance of >> generating good quality code. As far as I can tell, BCPL and BLISS came >> close, but were too large to run on a PDP-11 and only existed as >> cross-compilers. PL/M was a cross-compiler and generated poorer code. >> Pascal on small machines compiled to a virtual machine. As far as I can >> tell, during most of the 70s there was no other compiler that generated >> good quality code and ran natively on a small (i.e. PDP-11 class) machin= e. >> >> As far as I can tell the uniqueness was mostly in the =E2=80=9Cc1=E2=80= =9D phase of the >> compiler. The front-end code of the =E2=80=9Cc0=E2=80=9D phase seems to = use more or less >> similar techniques as many contemporary compilers. The =E2=80=9Cc1=E2=80= =9D phase seems to >> have been unique in that it managed to do register allocation and >> instruction selection with a pattern matcher and associated code tables >> squeezed into a small address space. On a small machine, other native >> compilers of the era typically proceeded to generate threaded code, code >> for a virtual machine or poor quality native code that evaluated >> expressions using stack operations rather than registers. >> >> I am not sure why DMR's approach was not more widely used in the 1970=E2= =80=99s. >> The algorithms he used do not seem to be new and appear to have their ro= ots >> in other (larger) compilers of the 1960=E2=80=99s. The basic design seem= s to have >> been in place from the very first iterations of his compiler in 1972 (se= e >> V2 tree on TUHS) and he does not mention these algorithms as being speci= al >> or innovative in his later papers. >> >> Any observations / opinions on why DMR=E2=80=99s approach was not more w= idely >> used in the 1970=E2=80=99s? >> > --0000000000009904620617f10e95 Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable
I believe Ken Thompson might have been a referee for that paper. = At least, he once mentioned to me that he had reviewed a paper about the th= reading in the DEC Fortran compiler.

-rob


On Wed, May 8, 2024 at 7= :35=E2=80=AFPM Paul Ruizendaal <pnr@pla= net.nl> wrote:
=20 =20 =20
Thanks for = pointing that out. Here's an interesting paper on the DEC PDP11 Fortran= compilers:
http://forum.6502.org/download/fil= e.php?id=3D1724&sid=3Df6a721f3e05774cff076da72f5a731a6

Before = 1975 they used direct threading, thereafter there was a native compiler for= the higher-end models. I think this one may have required split i/d, but t= hat is not entirely clear from the text.

I think= the same holds for BCPL on the PDP11: compiling to "ocode" or &q= uot;intcode" in the early 70s, native thereafter -- still have to find= source for the latter.

Still, = I should have first asked: Does anyone have pointers to small machine nativ= e compilers from the 1970's that produced efficient assembler output?

I am al= ready aware of the 1978 Whitesmith C compiler.

7 May 2024 23:07:58 Rob Pike <robpike@gmail.com>:

I'm not sure I accept your starting position. There were several = compilers for RT-11 and RSX/11-M. RSX (and perhaps RT) Fortran were threade= d code, but I don't believe they all were. And of course there was BCPL= , which was - and is - tiny; was it on the 11?

And there were other small machines from other manufacturers, all of = which had some form of Fortran and other bespoke things, such as RPG on the= small IBMs. I think the uniqueness was in the set of conditions more than = in the Unix C compiler itself.

But you may be right.

-rob




On Wed, May 8, 2024 at 6:59=E2=80=AFAM Paul Ruizendaal <pnr@planet.nl> wrote:=20
In the= last months, I've spent a little time on curating John Walker's Un= ix clone and software stack, including an emulator to run it:
https://gitlab.com= /marinchip

Af= ter creating a basic tool chain (edit, asm, link and a simple executive), J= ohn=C2=A0 set out to find a compiler. Among the first programs were a port = of the META 3 compiler-generator (similar to TMG on early Unix) and a port = of Birch-Hansen=E2=80=99s Pascal compiler. META was used to create a compil= er that generated threaded code. He found neither compiler good enough for = his goals and settled on writing his Unix-like OS in assembler. As the 9900= architecture withered after 1980, this sealed the fate of this OS early on= -- had he found a good compiler, the code might have competed alongside Co= herent, Idris, and Minix during the 80=E2=80=99s.

Th= is made me realise once more how unique the Ritchie C compiler was. In my v= iew its uniqueness combines three aspects:
1.= The C language itself
2.= The ability to run natively on small hardware (even an LSI-11 system)
3.= Generating code with modest overhead versus handwritten assembler (say 30%= )

As= has been observed before, working at a higher abstraction level makes it e= asier to work on algorithms and on refactoring, often earning back the effi= ciency loss. John Walkers work may be case in point: I estimate that his ha= nd-coded kernel is 10% larger than an equivalent V6 Unix kernel (as compile= d for the 9900 architecture).

Th= ere are three papers on DMR=E2=80=99s website about the history of the comp= iler and a compare-and-contrast with other compilers of the era:
https://www.bell-labs.com/usr/dmr/www/primevalC.html
https://www.bell-labs.com/usr/dmr/www/chist.html
https://www.bell-labs.com/usr/dmr/www/hopl.html

It= seems to me that these papers rather understate the importance of generati= ng good quality code. As far as I can tell, BCPL and BLISS came close, but = were too large to run on a PDP-11 and only existed as cross-compilers. PL/M= was a cross-compiler and generated poorer code. Pascal on small machines c= ompiled to a virtual machine. As far as I can tell, during most of the 70s = there was no other compiler that generated good quality code and ran native= ly on a small (i.e. PDP-11 class)=C2=A0machine.

As= far as I can tell the uniqueness was mostly in the =E2=80=9Cc1=E2=80=9D ph= ase of the compiler. The front-end code of the =E2=80=9Cc0=E2=80=9D phase s= eems to use more or less similar techniques as many contemporary compilers.= The =E2=80=9Cc1=E2=80=9D phase seems to have been unique in that it manage= d to do register allocation and instruction selection with a pattern matche= r and associated code tables squeezed into a small address space. On a smal= l machine, other native compilers of the era typically proceeded to generat= e threaded code, code for a virtual machine or poor quality native code tha= t evaluated expressions using stack operations rather than registers.

I = am not sure why DMR's approach was not more widely used in the 1970=E2= =80=99s. The algorithms he used do not seem to be new and appear to have th= eir roots in other (larger) compilers of the 1960=E2=80=99s. The basic desi= gn seems to have been in place from the very first iterations of his compil= er in 1972 (see V2 tree on TUHS) and he does not mention these algorithms a= s being special or innovative in his later papers.

An= y observations / opinions on why DMR=E2=80=99s approach was not more widely= used in the 1970=E2=80=99s?
--0000000000009904620617f10e95--