[pups] Bringing up the fist C compiler

[pups] Bringing up the fist C compiler

[Tim Bradshaw]

Is there a description anywhere of how C was originally bootstrapped?
I'm sure it was nothing unconventional, but the question of how you
bring up compilers for other languages which are implemented in their
own language seems to mystify some people to the extent that they
argue that the compiler must be written in C (which is `always
there'), and I thought it would be good to have the real story about C
to tell them.

Thanks

--tim

[pups] Bringing up the fist C compiler

[Warren Toomey]

In article by Tim Bradshaw:
> Is there a description anywhere of how C was originally bootstrapped?

Have a look at "The Development of the C Language"
at http://cm.bell-labs.com/cm/cs/who/dmr/chist.html

	Warren

[pups] Bringing up the fist C compiler

[Johnny Billquist]

On Thu, 5 Sep 2002, Tim Bradshaw wrote:

> Is there a description anywhere of how C was originally bootstrapped?
> I'm sure it was nothing unconventional, but the question of how you
> bring up compilers for other languages which are implemented in their
> own language seems to mystify some people to the extent that they
> argue that the compiler must be written in C (which is `always
> there'), and I thought it would be good to have the real story about C
> to tell them.

Well, I have a C compiler written in MACRO-11...
C wasn't written in C at the start, you know...

	Johnny

Johnny Billquist                  || "I'm on a bus
                                  ||  on a psychedelic trip
email: bqt at update.uu.se           ||  Reading murder books
pdp is alive!                     ||  tryin' to stay hip" - B. Idol

[pups] Bringing up the fist C compiler

[Tim Bradshaw]

* Johnny Billquist wrote:

> Well, I have a C compiler written in MACRO-11...
> C wasn't written in C at the start, you know...

Yes, I realise that! Many people (not readers of this list!) seem to
assume that C is eternal though.  From the paper that Warren pointed
me at (thanks) it looks like the only missing link is how TMG
originally got onto the PDP-7...

--tim

[pups] Bringing up the fist C compiler

[Johnny Billquist]

On Thu, 5 Sep 2002, Tim Bradshaw wrote:

> * Johnny Billquist wrote:
> 
> > Well, I have a C compiler written in MACRO-11...
> > C wasn't written in C at the start, you know...
> 
> Yes, I realise that! Many people (not readers of this list!) seem to
> assume that C is eternal though.  From the paper that Warren pointed
> me at (thanks) it looks like the only missing link is how TMG
> originally got onto the PDP-7...

How? It was written, of course. In assembler. By that time, you already
had the assembler, an editor, and other commonly used system programs, so
it's just a case of the normal development cycle.

	Johnny

Johnny Billquist                  || "I'm on a bus
                                  ||  on a psychedelic trip
email: bqt at update.uu.se           ||  Reading murder books
pdp is alive!                     ||  tryin' to stay hip" - B. Idol

[pups] Bringing up the fist C compiler

[Lars Brinkhoff]

Johnny Billquist <bqt at update.uu.se> writes:
> On Thu, 5 Sep 2002, Tim Bradshaw wrote:
> > * Johnny Billquist wrote:
> > > Well, I have a C compiler written in MACRO-11...
> > > C wasn't written in C at the start, you know...
> > Yes, I realise that! Many people (not readers of this list!) seem to
> > assume that C is eternal though.  From the paper that Warren pointed
> > me at (thanks) it looks like the only missing link is how TMG
> > originally got onto the PDP-7...
> How? It was written, of course. In assembler. By that time, you already
> had the assembler, an editor, and other commonly used system programs, so
> it's just a case of the normal development cycle.

And tracing further backwards, the assembler was pheraps originally
developed in GECOS?

-- 
Lars Brinkhoff          http://lars.nocrew.org/     Linux, GCC, PDP-10,
Brinkhoff Consulting    http://www.brinkhoff.se/    HTTP programming

[pups] Bringing up the fist C compiler

[Tim Bradshaw]

* Johnny Billquist wrote:

> How? It was written, of course. In assembler. By that time, you already
> had the assembler, an editor, and other commonly used system programs, so
> it's just a case of the normal development cycle.

Is this known or is it deduction?

(In case there is any confusion here: I do understand very well how
compilers can be implemented on naked machines without preexisting
tools (and indeed I've done more-or-less this with assemblers on
microcomputers, ending up with a perfectly fine assembler which used
the wrong opcode names, because we didn't know what the right ones
were...).  So my question `how was x done' is not `I don't understand
how you can do this' but `historically, what were the steps in this
case'. What I'm trying to find out is what the actual course of events
was for C, so I can give glib answers to people (:-))

--tim

[pups] Bringing up the fist C compiler

[Johnny Billquist]

On Thu, 5 Sep 2002, Tim Bradshaw wrote:

> * Johnny Billquist wrote:
> 
> > How? It was written, of course. In assembler. By that time, you already
> > had the assembler, an editor, and other commonly used system programs, so
> > it's just a case of the normal development cycle.
> 
> Is this known or is it deduction?

[...]

Ah. Ok, now I understand what you're asking for.
You want to know what the first C was written in, and what that
compiler/assembler was written in/on, and so on...

No, I'm just deducting. Since the reference posted said that TMG was the
first higher level language implemented, it follows that it must have been
written in a low level language, namely assembler.

Admittedly, the PDP-7 TMG *could* have been written in some high level
language on some other machine using some tool that made a PDP-7
executable, so your guess is as good as mine.

But even though I cannot account for all steps, I can guarantee that at
the end of the chain, you *will* find assembler.

I guess my MACRO-11 implementation of C isn't good enough. :-)
(Well, it ain't mine, it's the normal DECUS C, but I'm hacked some at it.)

	Johnny

Johnny Billquist                  || "I'm on a bus
                                  ||  on a psychedelic trip
email: bqt at update.uu.se           ||  Reading murder books
pdp is alive!                     ||  tryin' to stay hip" - B. Idol

[pups] Bringing up the fist C compiler

[Michael Davidson]

Johnny Billquist wrote:

>
>But even though I cannot account for all steps, I can guarantee that at
>the end of the chain, you *will* find assembler.
>

Or, just possibly, Alan Turing hand punching Mark 1 machine code onto 
paper tape ;-)

[pups] Bringing up the fist C compiler

[Peter Jeremy]

On 2002-Sep-05 09:11:38 -0700, Michael Davidson <MichaelDavidson at pacbell.net> wrote:
>Johnny Billquist wrote:
>>But even though I cannot account for all steps, I can guarantee that at
>>the end of the chain, you *will* find assembler.
>
>Or, just possibly, Alan Turing hand punching Mark 1 machine code onto
>paper tape ;-)

Actually, to use one of the other "first stored-program computer"
candidates, EDSAC provided what I consider to be a very sophisticated
assembler/loader that read programs off paper tape into memory.  This
assembler/loader ("initial orders") was 41 instructions long and was
hard-wired onto uniselectors which were automatically loaded into
memory when the start switch was pressed.

It supported:
- single-letter mnemonics for each of the 18 instructions
- decimal entry of numbers (EDSAC was binary internally)
- 13 single-letter variables which could be assigned or added to the
  address in each instruction.
- program relocation (courtesy of the above)

Overall, the input language looks much closer to assembler language
than the instruction bit patterns in memory.  (The Mathematical
Laboratory also developed an extensive collection of reusable
subroutines intended to simplify program development).

Ref: "The Preparation of Programs for an Electronic Digital Computer",
   M.V. Wilkes, D.J. Wheeler, S. Gill, Addison-Wesley, 1951.

A rummage around on the WEB will turn up a couple of EDSAC simulators
and sample programs.

Peter

[pups] bringing up the fist C compiler

[Warren Toomey]

> > > Warren Toomey <wkt at minnie.tuhs.org> writes:
> > > > The chist paper doesn't mention NB

In article by Lars Brinkhoff:
> > > How about this?
> > >   In 1971 I began to extend the B language by adding a character type
> > >   [...]

> > Yes that's it!! Where did you find it?
> In the chist paper.

<blushes>Oh .... </blushes>

	Warren

[pups] bringing up the fist C compiler

[Lars Brinkhoff]

Warren Toomey <wkt at minnie.tuhs.org> writes:
> In article by Lars Brinkhoff:
> > Warren Toomey <wkt at minnie.tuhs.org> writes:
> > > The chist paper doesn't mention NB, which was the missing link between
> > > B and C.
> > 
> > How about this?
> > 
> >   In 1971 I began to extend the B language by adding a character type
> >   and also rewrote its compiler to generate PDP-11 machine instructions
> >   instead of threaded code.  Thus the transition from B to C was
> >   contemporaneous with the creation of a compiler capable of producing
> >   programs fast and small enough to compete with assembly language.  I
> >   called the slightly-extended language NB, for `new B.'
> > 
> >   [...]
> 
> Yes that's it!! Where did you find it?

In the chist paper.

-- 
Lars Brinkhoff          http://lars.nocrew.org/     Linux, GCC, PDP-10,
Brinkhoff Consulting    http://www.brinkhoff.se/    HTTP programming

[pups] bringing up the fist C compiler

[Warren Toomey]

In article by Lars Brinkhoff:
> Warren Toomey <wkt at minnie.tuhs.org> writes:
> > The chist paper doesn't mention NB, which was the missing link between
> > B and C.
> 
> How about this?
> 
>   In 1971 I began to extend the B language by adding a character type
>   and also rewrote its compiler to generate PDP-11 machine instructions
>   instead of threaded code.  Thus the transition from B to C was
>   contemporaneous with the creation of a compiler capable of producing
>   programs fast and small enough to compete with assembly language.  I
>   called the slightly-extended language NB, for `new B.'
> 
>   [...]

Yes that's it!! Where did you find it?

	Warren

[pups] bringing up the fist C compiler

[Lars Brinkhoff]

Warren Toomey <wkt at minnie.tuhs.org> writes:
> The chist paper doesn't mention NB, which was the missing link between
> B and C.

How about this?

  In 1971 I began to extend the B language by adding a character type
  and also rewrote its compiler to generate PDP-11 machine instructions
  instead of threaded code.  Thus the transition from B to C was
  contemporaneous with the creation of a compiler capable of producing
  programs fast and small enough to compete with assembly language.  I
  called the slightly-extended language NB, for `new B.'

  [...]

  After creating the type system, the associated syntax, and the
  compiler for the new language, I felt that it deserved a new name;
  NB seemed insufficiently distinctive.  I decided to follow the
  single-letter style and called it C, leaving open the questing
  whether the name represented a progression through the alphabet or
  through the letters in BCPL.

> I seem to recall a story where there was an NB interpreter and also
> a compiler, and Ken kept adding functionality to one which made it
> slower, and this had a knock-on effect.

Maybe this?

  After the TMG version of B was working, Thompson rewrote B in itself
  (a bootstrapping step).  During development, he continually struggled
  against memory limitations: each language addition inflated the
  compiler so it could barely fit, but each rewrite taking advantage
  of the feature reduced it size.

-- 
Lars Brinkhoff          http://lars.nocrew.org/     Linux, GCC, PDP-10,
Brinkhoff Consulting    http://www.brinkhoff.se/    HTTP programming

[pups] bringing up the fist C compiler

[Lars Brinkhoff]

Dennis Ritchie <dmr at plan9.bell-labs.com> writes:
> There is not much about TMG on the web that I can find
> (and some of it is inaccurate).

There's some on www.multicians.org, but it doesn't relate to B
or Unix:
  http://google.com/search?q=site:multicians.org+tmg

"About TMG" on the McClure Group page is unfortunately not available:
  http://www.mccluregroup.ca/

FOLDOC entry on TMG:
  http://wombat.doc.ic.ac.uk/foldoc/foldoc.cgi?TMG

Another page which describes TMG (but the phrase "MULTIX was the name
of the first-generation UNIX" makes me suspicious):
  http://www.geocities.com/ResearchTriangle/2363/tmg011.html

-- 
Lars Brinkhoff          http://lars.nocrew.org/     Linux, GCC, PDP-10,
Brinkhoff Consulting    http://www.brinkhoff.se/    HTTP programming

[pups] bringing up the fist C compiler

[Warren Toomey]

In article by Dennis Ritchie:
> The chist paper on my home page is pretty complete (if telegraphic)
> about bootstrapping B on the PDP-7 and later C (via B) on the -11.

The chist paper doesn't mention NB, which was the missing link between
B and C. I seem to recall a story where there was an NB interpreter
and also a compiler, and Ken kept adding functionality to one which
made it slower, and this had a knock-on effect. Sorry, that's all I
can dredge out of my wetware bit store. Was this in `A Quarter Century
of UNIX' by Peter Salus? Are there any other paper/web references to NB?

	Warren

[pups] bringing up the fist C compiler

[Dennis Ritchie]

The chist paper on my home page is pretty complete (if telegraphic)
about bootstrapping B on the PDP-7 and later C (via B) on the -11.
It does not, indeed, explain TMG.  Doug McIlroy did write TMG
(on the -7) first in assembly language, then bootstrapped
that into itself.  Doug had used TMG to write EPL, the early
Pl/I compiler for Multics.  I don't know whether he needed
to create a new implementation of TMG for that or whether
it was already running on the IBM 7094.

The paper also mentions (as does some of the other history stuff)
that Unix itself was written first in assembler on the GE-645
(running GECOS, not Multics at that point),
using a macro package that turned symbolic -7 instructions into
an object deck that could be rendered onto paper tape.

There is not much about TMG on the web that I can find
(and some of it is inaccurate).

Incidentally, TMG didn't immediately survive the move
to the -11. B was already in its own language,
and nothing else was using TMG besides itself.
Doug did revive it later just for fun, and it is in the
6th edition distribution--you can get it nearby!

Both on the -7 and the -11, TMG was implemented as
an interpreter for an abstract machine.

	Dennis

[pups] Bringing up the fist C compiler

[Johnny Billquist]

On Thu, 5 Sep 2002, Al Kossow wrote:

>  > I guess my MACRO-11 implementation of C isn't good enough. > (Well, it ain't mine, it's the normal DECUS C, but I'm hacked some at it.) 
> 
>   and to bring this full circle, do you know where DECUS C came from? 

I've seen rumours that it's supposed to be derived from a c compiler
output of a c compiler.
Might be true, and might not. I've been digging a little in it by now, and
it has atleast been pretty modified from that possible source anyhow.

I seem to remmeber that there was a discussion on this topic somewhere
about a year ago, but I don't remember if anyone relly knew.

	Johnny

Johnny Billquist                  || "I'm on a bus
                                  ||  on a psychedelic trip
email: bqt at update.uu.se           ||  Reading murder books
pdp is alive!                     ||  tryin' to stay hip" - B. Idol

[pups] Bringing up the fist C compiler

[Carl Lowenstein]

> From: Al Kossow <aek at spies.com>
> To: pups at tuhs.org
> Subject: Re: [pups] Bringing up the fist C compiler
> Content-ID: <9012_13188_1031248039_2 at spies.com>
> Date: Thu, 5 Sep 2002 10:47:19 -0700
> 
> <nl>
> > I guess my MACRO-11 implementation of C isn't good enough.
> > (Well, it ain't mine, it's the normal DECUS C, but I'm hacked some at i=
> t.)
> <nl><nl>
> 
> and to bring this full circle, do you know where DECUS C came from?
> <nl><nl>

It is my understanding that it was a "clean room" reimplementation of
the 6th Edition Unix "cc" and "as".

    carl
-- 
    carl lowenstein         marine physical lab     u.c. san diego
                                                 clowenst at ucsd.edu

[pups] Bringing up the fist C compiler

[Al Kossow]

A non-text attachment was scrubbed...
Name: not available
Type: text/richtext
Size: 232 bytes
Desc: not available
URL: <http://minnie.tuhs.org/pipermail/tuhs/attachments/20020905/510f1b0b/attachment.rtx>

[pups] Bringing up the fist C compiler

[Ian King]

About a thousand years ago, I recall hand-building programs for 8-bit microprocessors (in what we'd call embedded systems today).  In many cases, I was the "assembler", writing directly in machine code which was then either keyed in through front-panel switches or burned into a PROM....  -- Ian 

	-----Original Message----- 
	From: Johnny Billquist [mailto:bqt at update.uu.se] 
	Sent: Thu 9/5/2002 5:05 AM 
	To: Tim Bradshaw 
	Cc: pups at minnie.tuhs.org 
	Subject: Re: [pups] Bringing up the fist C compiler
	
	

	On Thu, 5 Sep 2002, Tim Bradshaw wrote:
	
	> * Johnny Billquist wrote:
	>
	> > How? It was written, of course. In assembler. By that time, you already
	> > had the assembler, an editor, and other commonly used system programs, so
	> > it's just a case of the normal development cycle.
	>
	> Is this known or is it deduction?
	
	[...]
	
	Ah. Ok, now I understand what you're asking for.
	You want to know what the first C was written in, and what that
	compiler/assembler was written in/on, and so on...
	
	No, I'm just deducting. Since the reference posted said that TMG was the
	first higher level language implemented, it follows that it must have been
	written in a low level language, namely assembler.
	
	Admittedly, the PDP-7 TMG *could* have been written in some high level
	language on some other machine using some tool that made a PDP-7
	executable, so your guess is as good as mine.
	
	But even though I cannot account for all steps, I can guarantee that at
	the end of the chain, you *will* find assembler.
	
	I guess my MACRO-11 implementation of C isn't good enough. :-)
	(Well, it ain't mine, it's the normal DECUS C, but I'm hacked some at it.)
	
	        Johnny
	
	Johnny Billquist                  || "I'm on a bus
	                                  ||  on a psychedelic trip
	email: bqt at update.uu.se           ||  Reading murder books
	pdp is alive!                     ||  tryin' to stay hip" - B. Idol
	
	_______________________________________________
	PUPS mailing list
	PUPS at minnie.tuhs.org
	http://minnie.tuhs.org/mailman/listinfo/pups