[TUHS] On the uniqueness of DMR's C compiler

[TUHS] On the uniqueness of DMR's C compiler

[Paul Ruizendaal]

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

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 were a port of the META 3 compiler-generator (similar to TMG on early Unix) and a port of Birch-Hansen’s Pascal compiler. META was used to create a compiler 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 Coherent, Idris, and Minix during the 80’s.

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 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 the 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 (as compiled for the 9900 architecture).

There are three papers on DMR’s 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) machine.

As far as I can tell the uniqueness was mostly in the “c1” phase of the compiler. The front-end code of the “c0” phase seems to use more or less similar techniques as many contemporary compilers. The “c1” 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’s. The algorithms he used do not seem to be new and appear to have their roots in other (larger) compilers of the 1960’s. 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 special or innovative in his later papers.

Any observations / opinions on why DMR’s approach was not more widely used in the 1970’s?

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

[TUHS] Re: On the uniqueness of DMR's C compiler

[Rob Pike]

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

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 threaded 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 AM Paul Ruizendaal <pnr@planet.nl> wrote:

> 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 were
> a port of the META 3 compiler-generator (similar to TMG on early Unix) and
> a port of Birch-Hansen’s Pascal compiler. META was used to create a
> compiler 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 Coherent, Idris, and Minix during the 80’s.
>
> 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
> 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 the
> 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 (as
> compiled for the 9900 architecture).
>
> There are three papers on DMR’s 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) machine.
>
> As far as I can tell the uniqueness was mostly in the “c1” phase of the
> compiler. The front-end code of the “c0” phase seems to use more or less
> similar techniques as many contemporary compilers. The “c1” 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’s.
> The algorithms he used do not seem to be new and appear to have their roots
> in other (larger) compilers of the 1960’s. 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 special
> or innovative in his later papers.
>
> Any observations / opinions on why DMR’s approach was not more widely used
> in the 1970’s?
>

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

[TUHS] Re: On the uniqueness of DMR's C compiler

[Paul Ruizendaal]

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

Thanks for pointing that out. Here's an interesting paper on the DEC PDP11 Fortran compilers:
http://forum.6502.org/download/file.php?id=1724&sid=f6a721f3e05774cff076da72f5a731a6

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 source 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 assembler output?

I am already 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 threaded 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 AM Paul Ruizendaal <pnr@planet.nl> wrote:
>> 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 were a port of the META 3 compiler-generator (similar to TMG on early Unix) and a port of Birch-Hansen’s Pascal compiler. META was used to create a compiler 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 Coherent, Idris, and Minix during the 80’s.
>> 
>> 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 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 the 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 (as compiled for the 9900 architecture).
>> 
>> There are three papers on DMR’s 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) machine.
>> 
>> As far as I can tell the uniqueness was mostly in the “c1” phase of the compiler. The front-end code of the “c0” phase seems to use more or less similar techniques as many contemporary compilers. The “c1” 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’s. The algorithms he used do not seem to be new and appear to have their roots in other (larger) compilers of the 1960’s. 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 special or innovative in his later papers.
>> 
>> Any observations / opinions on why DMR’s approach was not more widely used in the 1970’s?

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

[TUHS] Re: On the uniqueness of DMR's C compiler

[Michael Kjörling]

On 7 May 2024 21:59 +0100, from pnr@planet.nl (Paul Ruizendaal):
> 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.

https://www.softwarepreservation.org/projects/BCPL/index.html#York
appears to indicate that by 1974 there existed a native PDP-11 (/40 or
/45) BCPL compiler which ran under RSX-11.

--
Michael Kjörling                     🔗 https://michael.kjorling.se
“Remember when, on the Internet, nobody cared that you were a dog?”

[TUHS] Re: On the uniqueness of DMR's C compiler

[Rob Pike]

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

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 PM Paul Ruizendaal <pnr@planet.nl> wrote:

> Thanks for pointing that out. Here's an interesting paper on the DEC PDP11
> Fortran compilers:
>
> http://forum.6502.org/download/file.php?id=1724&sid=f6a721f3e05774cff076da72f5a731a6
>
> 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 source
> 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 assembler
> output?
>
> I am already 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 threaded 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 AM Paul Ruizendaal <pnr@planet.nl> wrote:
>
>> 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 were
>> a port of the META 3 compiler-generator (similar to TMG on early Unix) and
>> a port of Birch-Hansen’s Pascal compiler. META was used to create a
>> compiler 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 Coherent, Idris, and Minix during the 80’s.
>>
>> 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
>> 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 the
>> 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 (as
>> compiled for the 9900 architecture).
>>
>> There are three papers on DMR’s 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) machine.
>>
>> As far as I can tell the uniqueness was mostly in the “c1” phase of the
>> compiler. The front-end code of the “c0” phase seems to use more or less
>> similar techniques as many contemporary compilers. The “c1” 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’s.
>> The algorithms he used do not seem to be new and appear to have their roots
>> in other (larger) compilers of the 1960’s. 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 special
>> or innovative in his later papers.
>>
>> Any observations / opinions on why DMR’s approach was not more widely
>> used in the 1970’s?
>>
>

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

[TUHS] Re: On the uniqueness of DMR's C compiler

[Clem Cole]

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

I agree with Rob. I fear the OP might have more limited experience with
what was available at the time and how it was developed. The following is
undoubtedly incomplete. It is what I could remember quickly to answer the
question of real compilers for the PDP-11.

As others have pointed out, the original DEC PDP-11 FTN, like the original
PDP-6 and PDP-8, was based on threaded DEC F4 technology.  After
introducing the PDP-10, the 36-bit compiler team at DEC started a project
to rewrite FORTRAN (in BLISS) as a true compiler.  As was reminded at lunch
last week (I still eat weekly with many of the DEC TLG folks), DEC had two
groups -- a development team and a support team.    I think some of the
external confusion comes from both teams releasing products to the world,
and the outside world did not always understand the differences. So, when I
say the "compiler" group, I generally refer to the former - although many
people started in the latter and eventually became part of the former. They
key point here is that F4 (which was from the support folks), lived for a
while in parallel with stuff coming from what eventually would become TLG
[Technical Languages (and tools) Group].

The primary DEC-supported technical languages were all written in BLISS-11
and cross-compiled from the PDP-10 (originally).  However, they could run
in 11/40 class (shared I/D) space machines. Remember, DEC operating systems
could do overlays - although there were probably some differences with what
could be generated [I'd need to pull the old RT11 manuals for each]. Yes,
FORTRAN was the primary technical language, but DEC's TLG supported other
languages for the PDP-11 from COBOL to BASIC, and 3rd parties filled out
the available suite.

Probably the #1 3rd party, PDP-11 compiler, is (was) the OMSI Pascal
compiler (which generated direct PDP-11 code) for all classes of PDP-11s
[the OP referred to the Pascal that generated P4 code and ran interpreter
for same.  The UCSD Pascal worked this way, but I never saw anything other
than students use it for teaching, while the OMSI compiler was a force for
PDP-11 programmers, and you saw it in many PDP-11 shops - including some I
worked].  I'm pretty sure the RT11 and  RSX11 versions of this can be
easily found in the wild, but I have not looked for the UNIX version (note
that there was one).

Note - from a SW marketplace for PDP-11s, the money was on the DEC
operating systems, not UNIX.  So, there was little incentive to move those
tools, which I think is why the OP may not have experienced them.  Another
important political thing to consider is that TLG did their development on
PDP-10s and later Vaxen inside DEC.   Since everything was written in BLISS
and DEC marketing 100% missed/sunk that boat, the concept of self-hosting
the compiler was not taken seriously (ISTR: there was a project to make it
self-host on RSX, but it was abandoned since customers were not beating
DEC's door down for BLISS on many PDP-11 systems).

Besides DMR's compiler for the PDP-11.  Steve Johnson developed PCC and
later PCC2.  Both ran on all flavors of PDP-11s, although I believe since
the lack of support for overlays in the research UNIX editions limited the
compilers and ISTR, there were both 11/40 and 11/45 class binaries with
different-sized tables.

On our Unix boxes, we also had a PDP-11 Pascal compiler from Free
University in Europe (VU) - I don't remember much about it nor can I find
it in a quick search of my currently online stuff. ISTR That one may have
been 11/45 class - we had it on the TekLabs 11/70 and I don't remember
having in on any of our 40-class systems.

The Whitesmith's C has been mentioned.  That compiler ran on all the PDP-11
UNIXs of the day, plus its native Idris, as well as the DEC OSs.  It did
not use an interpreter per se, but instead compiled to something Plauger
called 'ANAT" - a natural assembler.  He then ran an optimizer over this
output and his final pass converted from ANAT code to the PDP-11 (or Z80 as
it turns out).  I argue that ANAT was what we now think of in modern
compilers as the IL, but others might argue differently. We ran it on our
RT-11 systems, although ISTR came with the UNIX version, so we had it on
the 11/70, too. That may have been because we used it to cross-compile for
the Z80.

Tannabaum and the team have the Amsterdam compiler toolkit. This had front
ends for C and Pascal and could generate code for PDP-11s and several other
microprocessors. I do not know how widely it was used for the PDP11s.

Per Brinch, Hansen also implemented Parallel Pascal and his own OS for the
40-class PDP-11s. He talks about this in his book Pascal on Small Systems.

Holt and team wrote Concurrent Euclid and TUNIS for the 40-class machines.

Wirth released a Modula for the 11, although we mostly ran it on the 68000s
and a Lilith system.

IIRC, Mike Malcom and the team built a true B compiler so they could
develop Thoth.   As the 11/40 was one of the original Thoth target
systems,  I would have expected that to exist, but I have never used it.

As was mentioned before, there was  BCPL for the PDP-11.  I believe that a
BCPL compiler can even be found on one of the  USENIX tapes in the TUHS
archives, but I have not looked.

Finally, ISTR, in the mid-late 1970s one of the Universities in Europe
(??Edinburgh, maybe??), developed and released an Algol flavor for the
PDP-11, but I never used it.   Again, you might want to check the TUHS
archives.  In my own case, while I had used Algol on the PDP-8s and 10s,
plus the IBM systems, and by then Pascal had become the hot alternative
language and was close enough I never had a desire/need for it.   Plus
since there were a number of Pascal implementations available for 11s and
no one in Teklabs was asking for it, I never chased it down.

To quote Tom Lehrer .. "*These are the only ones that the news has come to
Huvrd. There may be many others ..*."

Clem




ᐧ
ᐧ

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

[TUHS] Re: On the uniqueness of DMR's C compiler

[Jon Forrest]

There was also a Modula2 compiler for the PDP-11 from a university in the UK,
propably York. It was used to some degree at Ford Aerospace for the
KSOS secure Unix project. I think it required separate I&D.

Jon

[TUHS] Re: On the uniqueness of DMR's C compiler

[Adam Sampson]

Clem Cole <clemc@ccc.com> writes:

> Finally, ISTR, in the mid-late 1970s one of the Universities in Europe
> (??Edinburgh, maybe??), developed and released an Algol flavor for the
> PDP-11, but I never used it.

That sounds like Edinburgh's IMP, which eventually had backends for a
very wide variety of platforms. Several versions are available here:
  https://history.dcs.ed.ac.uk/archive/languages/

-- 
Adam Sampson <ats@offog.org>                         <http://offog.org/>

[TUHS] Re: On the uniqueness of DMR's C compiler

[Al Kossow]

On 5/8/24 8:51 AM, Clem Cole wrote:

> IIRC, Mike Malcom and the team built a true B compiler so they could develop Thoth.   As the 11/40 was one of the original Thoth target 
> systems,  I would have expected that to exist, but I have never used it.
>

Thoth has been a white whale for me for decades. AFAIK nothing has survived from it.

"Decus" (Conroy's) C (transliteration of the assembler Unix C) should also be mentioned.

[TUHS] Re: On the uniqueness of DMR's C compiler

[Tom Perrine]

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

Hi Jon (and others),

I was part of the KSOS (later KSOS-11 and KSOS-32) team at LOGICON, which
picked up a follow-on contract to use KSOS-11 in a true multi-level-secure
production environment. Our target was SYSTEM_LOW as TOP SECRET.

Yes, we used that compiler for all the KSOS kernel and all the trusted
user-space code.

KSOS-11 only ran on PDP-11/70, and it did use split I&D.

I have access to the KSOS-11 source code, and have been trying to rebuild
that OS, BUT I haven't been able to find that Modula compiler.

KSOS-11 was a very small kernel, but there was a set of libraries that
presented a UNIX system call interface, so it could run some PWB userspace
tools, if they were re-compiled.

I'm using the term KSOS-11, as there was a follow-on project (KSOS-32) that
ported the original PDP KSOS to 11/780. I wrote a completely new (simpler)
scheduler, the bootstrap and memory management layer for that one.

And, for "reasons", the entire KSOS project at Logicon was shut down just a
week or so after the first user login to KSOS-32.

KSOS-11 itself and some multi-level applications did ship to DoD customers,
and it ran MLS applications for the Navy and USAFE.

--tep

ps. Jon was kind enough to remind me that we had corresponded about this in
the past -and- to remind me to send to the list, and not just him :-)


On Wed, May 8, 2024 at 9:08 AM Jon Forrest <nobozo@gmail.com> wrote:

> There was also a Modula2 compiler for the PDP-11 from a university in the
> UK,
> propably York. It was used to some degree at Ford Aerospace for the
> KSOS secure Unix project. I think it required separate I&D.
>
> Jon
>

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

[TUHS] Re: On the uniqueness of DMR's C compiler

[Clem Cole]

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

On Wed, May 8, 2024 at 1:46 PM Al Kossow <aek@bitsavers.org> wrote:

> Thoth has been a white whale for me for decades.

Ditto.  Although, I believe the late John Beety had his 'Thoth Thucks" tee
shirt for years.  I believe Kelly Booth still does.



> AFAIK nothing has survived from it.
>
You can argue that V-Kernel and QNX are children of Thoth - but they were
both in a flavor of Waterloo C that did not think ever targeted the PDP-11
[that might be a misunderstanding WRT Waterloo C].

>
> "Decus" (Conroy's) C (transliteration of the assembler Unix C) should also
> be mentioned.
>
Hmmmm, it's a flavor of Dennis' compiler in disguise and was sort of an
end-around for the AT&T lawyers by taking the *.s files, and converting
them to MACRO11, and then
redoing the assembler code to use originally RT11 I/O and later RSX11.
That said, it had its own life and ran on the DEC OSses, not UNIX, so it
probably counts.
That said, I thought Paul was asking about different core compiler
implementations, and I would argue the DECUS/Conroy compiler is the DMR
compiler, while the list I offered was all different core implementations.

I'm curious about Jon and Tom's MOD2 compiler.   Other than Wirth's, which
targeted the 68000, Lilith, and VAX, I did not know of another for the
PDP-11.  Any idea of its origin story? I would have expected it to have
derived from Wirth's Modula subsystem.  FWIW:  The DEC Mod-II and Mod-III
were new implementations from DEC WRL or SRC (I forget).  They targeted
Alpha and I, maybe Vax.  I'd have to ask someone like Larry Stewart or Jeff
Mogul who might know/remember, but I thought that the font end to the DEC
MOD2 compiler might have been partly based on Wirths but rewritten and by
the time of the MOD3 FE was a new one originally written using the previous
MOD2 compiler -- but I don't remember that detail.

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

[TUHS] Re: On the uniqueness of DMR's C compiler

[Clem Cole]

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

s/Beety/Beatty/  -- sorry
ᐧ

On Wed, May 8, 2024 at 2:12 PM Clem Cole <clemc@ccc.com> wrote:

>
>
> On Wed, May 8, 2024 at 1:46 PM Al Kossow <aek@bitsavers.org> wrote:
>
>> Thoth has been a white whale for me for decades.
>
> Ditto.  Although, I believe the late John Beety had his 'Thoth Thucks" tee
> shirt for years.  I believe Kelly Booth still does.
>
>
>
>> AFAIK nothing has survived from it.
>>
> You can argue that V-Kernel and QNX are children of Thoth - but they were
> both in a flavor of Waterloo C that did not think ever targeted the PDP-11
> [that might be a misunderstanding WRT Waterloo C].
>
>>
>> "Decus" (Conroy's) C (transliteration of the assembler Unix C) should
>> also be mentioned.
>>
> Hmmmm, it's a flavor of Dennis' compiler in disguise and was sort of an
> end-around for the AT&T lawyers by taking the *.s files, and converting
> them to MACRO11, and then
> redoing the assembler code to use originally RT11 I/O and later RSX11.
> That said, it had its own life and ran on the DEC OSses, not UNIX, so it
> probably counts.
> That said, I thought Paul was asking about different core compiler
> implementations, and I would argue the DECUS/Conroy compiler is the DMR
> compiler, while the list I offered was all different core implementations.
>
> I'm curious about Jon and Tom's MOD2 compiler.   Other than Wirth's, which
> targeted the 68000, Lilith, and VAX, I did not know of another for the
> PDP-11.  Any idea of its origin story? I would have expected it to have
> derived from Wirth's Modula subsystem.  FWIW:  The DEC Mod-II and Mod-III
> were new implementations from DEC WRL or SRC (I forget).  They targeted
> Alpha and I, maybe Vax.  I'd have to ask someone like Larry Stewart or Jeff
> Mogul who might know/remember, but I thought that the font end to the DEC
> MOD2 compiler might have been partly based on Wirths but rewritten and by
> the time of the MOD3 FE was a new one originally written using the previous
> MOD2 compiler -- but I don't remember that detail.
>

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

[TUHS] Re: On the uniqueness of DMR's C compiler

[Lawrence Stewart]

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

Regarding the Dec Research Modula-X compilers, I am fairly sure that Modula-2 for the VAX was a WRL (Digital Western Research Lab) thing, because it was used for the WRL CAD tool suite used to design the WRL Titan and the SRC (Systems Research Center) Firefly machines.  SRC did the Modula-2-Plus compiler for the VAX, which added garbage collection. The Firefly OS was Modula, but included an Ultrix system call set so it could run Ultrix binaries.  I may be wrong about this, but I think Wirth then did Modula-3 and then Oberon.  WRL and SRC never had any PDP-11’s as far as I know.
-L


> On May 8, 2024, at 2:12 PM, Clem Cole <clemc@ccc.com> wrote:
> 
> 
> 
> On Wed, May 8, 2024 at 1:46 PM Al Kossow <aek@bitsavers.org <mailto:aek@bitsavers.org>> wrote:
>> Thoth has been a white whale for me for decades.
> Ditto.  Although, I believe the late John Beety had his 'Thoth Thucks" tee shirt for years.  I believe Kelly Booth still does.
> 
>  
>> AFAIK nothing has survived from it.
> You can argue that V-Kernel and QNX are children of Thoth - but they were both in a flavor of Waterloo C that did not think ever targeted the PDP-11 [that might be a misunderstanding WRT Waterloo C]. 
>> 
>> "Decus" (Conroy's) C (transliteration of the assembler Unix C) should also be mentioned.
> Hmmmm, it's a flavor of Dennis' compiler in disguise and was sort of an end-around for the AT&T lawyers by taking the *.s files, and converting them to MACRO11, and then
> redoing the assembler code to use originally RT11 I/O and later RSX11.  That said, it had its own life and ran on the DEC OSses, not UNIX, so it probably counts.
> That said, I thought Paul was asking about different core compiler implementations, and I would argue the DECUS/Conroy compiler is the DMR compiler, while the list I offered was all different core implementations.
> 
> I'm curious about Jon and Tom's MOD2 compiler.   Other than Wirth's, which targeted the 68000, Lilith, and VAX, I did not know of another for the PDP-11.  Any idea of its origin story? I would have expected it to have derived from Wirth's Modula subsystem.  FWIW:  The DEC Mod-II and Mod-III were new implementations from DEC WRL or SRC (I forget).  They targeted Alpha and I, maybe Vax.  I'd have to ask someone like Larry Stewart or Jeff Mogul who might know/remember, but I thought that the font end to the DEC MOD2 compiler might have been partly based on Wirths but rewritten and by the time of the MOD3 FE was a new one originally written using the previous MOD2 compiler -- but I don't remember that detail.


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

[TUHS] Re: On the uniqueness of DMR's C compiler

[Paul Ruizendaal via TUHS]

Thanks everybody for the feedback and pointers, much appreciated!

The main point is clear: the premise that the DMR C compiler had unique (native, small machine) code generation during most of the 70’s does not hold up.

Clean Cole is correct in observing that (certainly for the 70’s) I’m skewed to stuff from academia with a blind spot for the commercial compilers of that era.

Doug McIlroy’s remarks on Digitek were most helpful and I’ll expand a bit on that below.

I was aware of the Digitek / Ryan-Macfarland compilers before, but in my mind they compiled to a virtual machine (mis-understanding a description of “programmed operators” and because their compilers for microcomputers did so in the 80’s). Digging into this more led me to a 1970 report "Programming Languages and their Compilers, Preliminary Notes” by John Cocke and J.T. Schwartz:
https://www.softwarepreservation.org/projects/FORTRAN/paper/Bright-FORTRANComesToWestinghouseBettis-1971.pdf

It is a nearly 800 page review of then current languages and compilers and it includes some discussion of the Digitek compilers as the state of the art for small machines and has some further description of how they worked (pp. 233-237, 749). It also mentions their PL/1 for Multics fiasco (for background https://www.multicians.org/pl1.html).

- The Digitek compilers were indeed small enough to run on PDP-11 class machines and even smaller, and they produced quite reasonable native code. In this sense, they were in the same spot as the DMR C compiler which was hence not unique in this regard -- as Doug points out.

- They consisted of two parts: a front end coded in “Programmed Operators" (POPS) generating an intermediate language, and a custom coded back-end that converted the IL to native code.

- POPS were in effect a VM for compiler construction (although expressed as assembler operations). To move a compiler to a new machine only the POPS VM had to be recoded, which was a very manageable job. From the description in the above book it sounds very similar to the META 3 compiler generator setup, but expressed in a different form.

- Unfortunately, I have not been able to find a description of the POPS IL.

- The smaller Digitek compilers had a limited level of optimisations, carried out at the code generation phase. The optimisations described sound quite similar to what the DMR C compiler did in its c1 phase (special casing +1 and -1, combining constants, mul/div to shift, etc.)

- Code generation seems to have been through code snippets for each IL operation, selecting from one of 3 addressing modes: register, memory and indexed; the text isn’t quite clear. It sounds reasonable for small machines in the 60’s.

- The later Ryan-MacFarland microcomputer compilers seem to have used the same POPS based front-end technology, but using an interpreter to execute the IL directly.

Interestingly, the above book has a final chapter about “the self-compiling compiler”. To quote: “The scheme to be described is one which has often been considered, and in some cases even implemented. It involves the use of a compiler written in its own language, and capable therefore of compiling itself over to a new machine.” It proceeds to describe such a compiler in quite some detail, including using a table driven code generator.

Seen through this lens, the DMR C compiler could be viewed as a re-imagining of the Digitek small system compilers using a self-compiling lexer/parser instead of POPS (or TMG or META) and a (also self-compiling) code generator evolved to handle the richer PDP-11 addressing modes. The concept seems to have been in the air at that time.

Now I am left wondering why the IL-to-native back-ends were not more used in academic small machine compilers in the 70’s -- but this too may be the result of a skewed view on my part.

[TUHS] Re: On the uniqueness of DMR's C compiler

[Al Kossow]

On 5/9/24 1:40 PM, Paul Ruizendaal via TUHS wrote:

> - Unfortunately, I have not been able to find a description of the POPS IL.

I went down that rabbit hole researching why Don Knuth had a high opinion of it.
If you dig around, the IL is described in the SDS Fortran documentation
http://bitsavers.org/pdf/sds/9xx/lang/900883A_9300_FORTRAN_IV_Tech_Aug65.pdf
and http://bitsavers.org/pdf/digitek/Data_Structures_in_Digiteks_FORTRAN_IV_Compiler_for_the_SDS_900_Series.pdf

and a compiler listing
https://archive.computerhistory.org/resources/text/Knuth_Don_X4100/PDF_index/k-1-pdf/k-1-C1051-Digitek-FORTRAN.pdf

[TUHS] Re: On the uniqueness of DMR's C compiler

[Paul Ruizendaal]

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

I’m further looking into BCPL / B / C family compilers on 16-bit mini-computers prior to 1979.

Lot’s of interesting stuff. BCPL was extended with structures at least twice and plenty struggle with (un)scaled pointers. It seems that the Nova was a much easier target than the PDP-11, with a simpler code generator sufficing to generate quality code. I’ll report more fully when I’m further along with my review.

> On May 8, 2024, at 5:51 PM, Clem Cole <clemc@ccc.com> wrote:
> 
> IIRC, Mike Malcom and the team built a true B compiler so they could develop Thoth.   As the 11/40 was one of the original Thoth target systems,  I would have expected that to exist, but I have never used it.

Yes, they did. I’m working through the various papers on Thoth and the Eh / Zed compilers (essentially B with tweaks). I’ve requested pdf’s of two theses that are only on micro-fiche from the Uni of Waterloo library, hopefully this is possible. The original target machines were Honeywell 6060, DG Nova, Microdata 1600/30 and TI-990. The latter is close enough to a PDP-11. This compiler is from 1976.

I’ve browsed around for surviving Thoth source code, but it would seem to be lost. Does anyone know of surviving Thoth bits?



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

[TUHS] Re: On the uniqueness of DMR's C compiler

[Peter Yardley]

I believe the Nova became a Mil Std instruction set (proven without hazard). Its architecture was pretty simple.

We sold ours to the Navy.

> On 31 May 2024, at 10:00 PM, Paul Ruizendaal <pnr@planet.nl> wrote:
> 
> I’m further looking into BCPL / B / C family compilers on 16-bit mini-computers prior to 1979.
> 
> Lot’s of interesting stuff. BCPL was extended with structures at least twice and plenty struggle with (un)scaled pointers. It seems that the Nova was a much easier target than the PDP-11, with a simpler code generator sufficing to generate quality code. I’ll report more fully when I’m further along with my review.
> 
>> On May 8, 2024, at 5:51 PM, Clem Cole <clemc@ccc.com> wrote:
>> 
>> IIRC, Mike Malcom and the team built a true B compiler so they could develop Thoth.   As the 11/40 was one of the original Thoth target systems,  I would have expected that to exist, but I have never used it.
> 
> Yes, they did. I’m working through the various papers on Thoth and the Eh / Zed compilers (essentially B with tweaks). I’ve requested pdf’s of two theses that are only on micro-fiche from the Uni of Waterloo library, hopefully this is possible. The original target machines were Honeywell 6060, DG Nova, Microdata 1600/30 and TI-990. The latter is close enough to a PDP-11. This compiler is from 1976.
> 
> I’ve browsed around for surviving Thoth source code, but it would seem to be lost. Does anyone know of surviving Thoth bits?
> 
> 

Peter Yardley
peter.martin.yardley@gmail.com

[TUHS] Re: On the uniqueness of DMR's C compiler

[G. Branden Robinson]

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

At 2024-05-10T13:28:40-0400, Paul Winalski wrote:
> On Wed, May 8, 2024 at 2:29 PM Douglas McIlroy <
> douglas.mcilroy@dartmouth.edu> wrote:
> > Dennis was one-up on Digitek in having a self-maintaining compiler.
> > Thus, when he implemented an optimization, the source would grow,
> > but the compiler binary might even shrink thanks to
> > self-application.
> 
> Another somewhat non-intuitive aspect of optimizing compilers is that
> simply adding optimizations can cause an increase in compilation speed
> by reducing the amount of IL in the program being compiled.  Less IL
> due to optimization means less time spent in later phases of the
> compilation process.

This fact was rediscovered later when people found that some code
compiled with "-Os" (optimize for space) was faster than some code
optimized for speed ("-O1", "-O2", and so on).

The reason turned out to be that the reduced code size meant fewer cache
evictions, so you gained performance by skipping instances of
instruction fetches all the way from the slow main memory bus.

Think of all those poor unrolled loops...

Regards,
Branden

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 833 bytes --]

[TUHS] Re: On the uniqueness of DMR's C compiler

[Ralph Corderoy]

Hi,

Paul W. wrote:
> The compilers were table-driven as much as possible, heavily overlaid,
> and used three scratch files on disk (split-cylinder allocated to
> minimize seek time).

I didn't know the term ‘split cylinder’.  A cylinder has multiple
tracks, each with its own read/write head.  Allocate different tracks to
different files and switching files needs no physical movement or
settling time; just electronically switch R/W head.

-- 
Cheers, Ralph.

[TUHS] Re: On the uniqueness of DMR's C compiler

[Paul McJones]

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

> On Thu, 9 May 2024 22:40:28 +0200, Paul Ruizendaal <pnr@planet.nl <mailto:pnr@planet.nl>> wrote:
> 
> .... Digging into this more led me to a 1970 report "Programming Languages and their Compilers, Preliminary Notes” by John Cocke and J.T. Schwartz:
> https://www.softwarepreservation.org/projects/FORTRAN/paper/Bright-FORTRANComesToWestinghouseBettis-1971.pdf

Actually, the link is here:

https://www.softwarepreservation.org/projects/FORTRAN/CockeSchwartz_ProgLangCompilers.pdf

And more about Jack Schwartz is here:

https://www.softwarepreservation.org/projects/SETL/index.html#Precursors


Paul

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

[TUHS] Re: On the uniqueness of DMR's C compiler

[Paul Winalski]

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

On Wed, May 8, 2024 at 2:29 PM Douglas McIlroy <
douglas.mcilroy@dartmouth.edu> wrote:

>
> Dennis was one-up on Digitek in having a self-maintaining compiler. Thus,
> when he implemented an optimization, the source would grow, but the
> compiler binary might even shrink thanks to self-application.
>

Another somewhat non-intuitive aspect of optimizing compilers is that
simply adding optimizations can cause an increase in compilation speed by
reducing the amount of IL in the program being compiled.  Less IL due to
optimization means less time spent in later phases of the compilation
process.

Regarding native compilers for small machines, IBM had compilers for
Fortran, COBOL, and PL/I that ran in 32K on System/360 and produced
tolerably good code (yes, one could do better with handwritten assembler).
And they generated real code, no threaded code cop-out.  And we're talking
full PL/I here, not the subset that ANSI later standardized.  The compilers
were table-driven as much as possible, heavily overlaid, and used three
scratch files on disk (split-cylinder allocated to minimize seek time).

-Paul W.

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

[TUHS] Re: On the uniqueness of DMR's C compiler

[Warner Losh]

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

On Wed, May 8, 2024, 9:39 PM Paul McJones <paul@mcjones.org> wrote:

> On Wed, 8 May 2024 14:12:15 -0400,Clem Cole <clemc@ccc.com> wrote:
>
>
> FWIW:  The DEC Mod-II and Mod-III
> were new implementations from DEC WRL or SRC (I forget).  They targeted
> Alpha and I, maybe Vax.  I'd have to ask someone like Larry Stewart or Jeff
> Mogul who might know/remember, but I thought that the font end to the DEC
> MOD2 compiler might have been partly based on Wirths but rewritten and by
> the time of the MOD3 FE was a new one originally written using the previous
> MOD2 compiler -- but I don't remember that detail.
>
>
> Michael Powell at DEC WRL wrote a Modula 2 compiler that generated VAX
> code. Here’s an extract from announcement.d accompanying a 1992 release of
> the compiler from gatekeeper.dec.com:
>
> The compiler was designed and built by Michael L. Powell, and originally
> released in 1984.  Joel McCormack sped the compiler up, fixed lots of
> bugs, and
> swiped/wrote a User's Manual.  Len Lattanzi ported the compiler to the
> MIPS.
>
>
> Later, Paul Rovner and others at DEC SRC designed Modula-2+ (a language
> extension with exceptions, threads, garbage collection, and runtime type
> dispatch). The Modula-2+ compiler was originally based on Powell’s
> compiler. Modula-2+ ran on the VAX.
>
> Here’s a DEC SRC research report on Modula-2+:
> http://www.bitsavers.org/pdf/dec/tech_reports/SRC-RR-3.pdf
>
> Modula-3 was designed at DEC SRC and Olivetti Labs. It had a portable
> implementation (using the GCC back end) and ran on a number of machines
> including Alpha.
>

FreeBSD's cvsup was written using it. The threading made it possible to
make maximum use of the 56k modems of the time and speed downloads of the
source changes. The port for modula-3 changed a number of time from gcc to
egcs back to gcc before running out of steam...

Warner

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

[TUHS] Re: On the uniqueness of DMR's C compiler

[Paul McJones]

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

> On Wed, 8 May 2024 14:12:15 -0400,Clem Cole <clemc@ccc.com <mailto:clemc@ccc.com>> wrote:
> 
> FWIW:  The DEC Mod-II and Mod-III
> were new implementations from DEC WRL or SRC (I forget).  They targeted
> Alpha and I, maybe Vax.  I'd have to ask someone like Larry Stewart or Jeff
> Mogul who might know/remember, but I thought that the font end to the DEC
> MOD2 compiler might have been partly based on Wirths but rewritten and by
> the time of the MOD3 FE was a new one originally written using the previous
> MOD2 compiler -- but I don't remember that detail.

Michael Powell at DEC WRL wrote a Modula 2 compiler that generated VAX code. Here’s an extract from announcement.d accompanying a 1992 release of the compiler from gatekeeper.dec.com <http://gatekeeper.dec.com/>:

The compiler was designed and built by Michael L. Powell, and originally
released in 1984.  Joel McCormack sped the compiler up, fixed lots of bugs, and
swiped/wrote a User's Manual.  Len Lattanzi ported the compiler to the MIPS. 

Later, Paul Rovner and others at DEC SRC designed Modula-2+ (a language extension with exceptions, threads, garbage collection, and runtime type dispatch). The Modula-2+ compiler was originally based on Powell’s compiler. Modula-2+ ran on the VAX.

Here’s a DEC SRC research report on Modula-2+:
http://www.bitsavers.org/pdf/dec/tech_reports/SRC-RR-3.pdf

Modula-3 was designed at DEC SRC and Olivetti Labs. It had a portable implementation (using the GCC back end) and ran on a number of machines including Alpha.


Paul



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

[TUHS] Re: On the uniqueness of DMR's C compiler

[Douglas McIlroy]

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

There was nothing unique about the size or the object code of Dennis's C
compiler. In the 1960s, Digitek had a thriving business of making Fortran
compilers for all manner of machines. To optimize space usage, the
compilers' internal memory model comprised  variable-size movable tables,
called "rolls". To exploit this non-native architecture, the compilers
themselves were interpreted, although they generated native code. Bob
McClure tells me he used one on an SDS910 that had 8K 16-bit words.

Dennis was one-up on Digitek in having a self-maintaining compiler. Thus,
when he implemented an optimization, the source would grow, but the
compiler binary might even shrink thanks to self-application.

Doug

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