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.6 required=5.0 tests=DKIM_INVALID,DKIM_SIGNED, 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 [IPv6:2600:3c01:e000:146::1]) by inbox.vuxu.org (Postfix) with ESMTP id C688820043 for ; Tue, 7 May 2024 22:59:55 +0200 (CEST) Received: from minnie.tuhs.org (localhost [IPv6:::1]) by minnie.tuhs.org (Postfix) with ESMTP id 90EF341621; Wed, 8 May 2024 06:59:48 +1000 (AEST) Received: from ewsoutbound.kpnmail.nl (unknown [195.121.94.186]) by minnie.tuhs.org (Postfix) with ESMTPS id A1FAB4132A for ; Wed, 8 May 2024 06:59:33 +1000 (AEST) X-KPN-MessageId: ada80246-0cb4-11ef-959b-00505699b430 Received: from smtp.kpnmail.nl (unknown [10.31.155.5]) by ewsoutbound.so.kpn.org (Halon) with ESMTPS id ada80246-0cb4-11ef-959b-00505699b430; Tue, 07 May 2024 22:59:21 +0200 (CEST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=planet.nl; s=planet01; h=content-type:mime-version:subject:message-id:to:from:date; bh=zzONMVHemjd0rpZOxHN/FXnlX5Bomyjuo3C7OYxrlUc=; b=ZMFOJE1N/uHHXIgzGv4qKjKx/daO9iRcNubEuJberUt7mIVeWk/MQCqQWimULQSD7y7IRhf/v7bo6 8KW+K7x1S0Sq2zmBcWJ+X+VJZ5eIpdIp1sWp348zo23FIr0PYstiZEjHvn0d7VFMJewTWcub+Iw3Em mXIB50+b8fXiTmJk= X-KPN-MID: 33|bJpS9Tw2gesvfao15Nqf46PfwnVzNjpgMRxgzAKdVDUlGaBBZU3Zw9uboUIybDO 7VPmjbDN2VbnPxwwYn/G2PwlqS28U8Llcla0f+NkgzQ8= X-KPN-VerifiedSender: Yes X-CMASSUN: 33|Q8nv08R44qBNXfbVI4xf5GITVC/8R/fq4FLj0C1mJrDkSsXsehUGuAK3ivfDRi0 e3PghMQAoA6weSz0EqeO8ew== X-Originating-IP: 105.156.96.5 Received: from dummy.faircode.eu (unknown [105.156.96.5]) by smtp.kpnmail.nl (Halon) with ESMTPSA id ad085d05-0cb4-11ef-8b46-00505699b758; Tue, 07 May 2024 22:59:21 +0200 (CEST) Date: Tue, 7 May 2024 21:59:17 +0100 (GMT+01:00) From: Paul Ruizendaal To: tuhs@tuhs.org Message-ID: <18efd14f-4da6-4771-ad6a-901c6cb6105d@planet.nl> References: MIME-Version: 1.0 Content-Type: multipart/alternative; boundary="----=_Part_26_34994120.1715115557740" X-Correlation-ID: <18efd14f-4da6-4771-ad6a-901c6cb6105d@planet.nl> Message-ID-Hash: RUXAMSQG5I35QZ7ZXDK7RU4VVD4I72CP X-Message-ID-Hash: RUXAMSQG5I35QZ7ZXDK7RU4VVD4I72CP X-MailFrom: pnr@planet.nl 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 X-Mailman-Version: 3.3.6b1 Precedence: list Subject: [TUHS] 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: ------=_Part_26_34994120.1715115557740 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: quoted-printable 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=C2=A0 set out to find a compiler. Among the first programs were a por= t of the META 3 compiler-generator (similar to TMG on early Unix) and a por= t of Birch-Hansen=E2=80=99s Pascal compiler. META was used to create a comp= iler that generated threaded code. He found neither compiler good enough fo= r his goals and settled on writing his Unix-like OS in assembler. As the 99= 00 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 = 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 (say 3= 0%) As has been observed before, working at a higher abstraction level makes it= easier to work on algorithms and on refactoring, often earning back the ef= ficiency 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 (as compi= led for the 9900 architecture). There are three papers on DMR=E2=80=99s website about the history of the co= mpiler 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 genera= ting good quality code. As far as I can tell, BCPL and BLISS came close, bu= t 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 70= s there was no other compiler that generated good quality code and ran nati= vely 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 = 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 compiler= s. The =E2=80=9Cc1=E2=80=9D phase seems to have been unique in that it mana= ged to do register allocation and instruction selection with a pattern matc= her and associated code tables squeezed into a small address space. On a sm= all machine, other native compilers of the era typically proceeded to gener= ate threaded code, code for a virtual machine or poor quality native code t= hat 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= roots in other (larger) compilers of the 1960=E2=80=99s. The basic design = seems to have been in place from the very first iterations of his compiler = in 1972 (see V2 tree on TUHS) and he does not mention these algorithms as b= eing special or innovative in his later papers. Any observations / opinions on why DMR=E2=80=99s approach was not more wide= ly used in the 1970=E2=80=99s? ------=_Part_26_34994120.1715115557740 Content-Type: text/html; charset=UTF-8 Content-Transfer-Encoding: quoted-printable
In the last m= onths, I've spent a little time on curating John Walker's Unix clone and so= ftware stack, including an emulator to run it:
https://g= itlab.com/marinchip

After cre= ating a basic tool chain (edit, asm, link and a simple executive), John&nbs= p; 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 Birc= h-Hansen=E2=80=99s Pascal compiler. META was used to create a compiler that= generated threaded code. He found neither compiler good enough for his goa= ls and settled on writing his Unix-like OS in assembler. As the 9900 archit= ecture withered after 1980, this sealed the fate of this OS early on -- had= he found a good compiler, the code might have competed 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 ab= ility to run natively on small hardware (even an LSI-11 system)
3. Genera= ting code with modest overhead versus handwritten assembler (say 30%)

As has be= en observed before, working at a higher abstraction level makes it easier t= o work on algorithms and on refactoring, often earning back the efficiency = loss. John Walkers work may be case in point: I estimate that his hand-code= d kernel is 10% larger than an equivalent V6 Unix kernel (as compiled for t= he 9900 architecture).

There are= three papers on DMR=E2=80=99s website about the history of the compiler an= d a compare-and-contrast with other compilers of the era:
https://w= ww.bell-labs.com/usr/dmr/www/primevalC.html
https://w= ww.bell-labs.com/usr/dmr/www/chist.html
https://w= ww.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 to= o 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 w= as no other compiler that generated good quality code and ran natively on a= small (i.e. PDP-11 class) machine.

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 mac= hine, other native compilers of the era typically proceeded to generate thr= eaded code, code for a virtual machine or poor quality native code that eva= luated 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 roots in= other (larger) compilers of the 1960=E2=80=99s. The basic design seems to = have been in place from the very first iterations of his compiler in 1972 (= see V2 tree on TUHS) and he does not mention these algorithms as being spec= ial or innovative in his later papers.

Any obser= vations / opinions on why DMR=E2=80=99s approach was not more widely used i= n the 1970=E2=80=99s?
------=_Part_26_34994120.1715115557740--