Does C implement the first C compiler itself?

[lovecreatesbea...]

K&R says the following in the preface to the first edition,

"... the C compiler, and ... are written in C."

I'm wondering, does it say even the first / original C compiler was
written in C?

[Dave Hansen]

On Feb 14, 11:38 am, "David T. Ashley" <[e-mail] rote:
[...]

If one has the C source code for an optimizing compiler, the compiles the
compiler, creating a new compiler, and repeats this process over many
iterations, will the compiler executable get smaller and smaller each time?

Umm. The generated code should always be the same. Unless there's a
bug in the optimizer. Optimization is easy if you don't have to get
the right answer.

But you reminded me of something I heard years ago: It is said that
every program contains at least one bug, and can be shortened by one
instruction. Therefore, by induction, every program can be reduced to
a single instruction, but it will be wrong.

Regards,

-=Dave

[Stephen Sprunk]

"lovecreatesbea [e-mail]" <lo************ ***@gmail.comwr ote in message
news:11******** *************@k 78g2000cwa.goog legroups.com...

K&R says the following in the preface to the first edition,

"... the C compiler, and ... are written in C."

I'm wondering, does it say even the first / original C compiler was
written in C?

That would leave you with a rather serious chicken-and-egg problem.

The very, very first C compiler was written in B. It was subsequently
rewritten in C (which wasn't a major change) and recompiled with the first
compiler.

DMR has a web site that explains the history of how C (and its original
compiler) evolved into existence.

S

--
Stephen Sprunk "Those people who think they know everything
CCIE #3723 are a great annoyance to those of us who do."
K5SSS --Isaac Asimov

--
Posted via a free Usenet account from http://www.teranews.com

[Flash Gordon]

Dave Hansen wrote, On 14/02/07 19:51:

On Feb 14, 11:38 am, "David T. Ashley" <[e-mail] rote:
[...]

>If one has the C source code for an optimizing compiler, the compiles the
compiler, creating a new compiler, and repeats this process over many
iterations, will the compiler executable get smaller and smaller each time?

Umm. The generated code should always be the same. Unless there's a
bug in the optimizer. Optimization is easy if you don't have to get
the right answer.

Indeed.

But you reminded me of something I heard years ago: It is said that
every program contains at least one bug, and can be shortened by one
instruction. Therefore, by induction, every program can be reduced to
a single instruction, but it will be wrong.

The versions I have heard have an additional clause which removes the
problem. The additional clause being something like, "of significant
complexity." It is important because of useful programs such as:

int main()
{
return 0;
}

Note, I've deliberately not specified a void parameter list to make it
compatible with what I know of pre-standard C as well as C89 & C99.
--
Flash Gordon

[christian.bau]

On Feb 14, 6:45 pm, Roberto Waltman <use...@rwaltma n.netwrote:

"David T. Ashley" wrote:

[OT] No, (at least not as worded) A simple test that every
self-compiling compiler should pass, is that when compiling its own
sources it should produce exact duplicates of itself.

Not necessarily.

The order in which subexpressions are evaluated is compiler-dependent.
For example, if we have a function

int f (void* p);

then it is compiler-dependent whether in the expression

f (right) + f (left)

f (right) is called first or f (left) is called first.

Now assume that your compiler A has a function codegen (), and when
the compiler wishes to generate code for two function calls in
unspecified order, with the results discarded, it calls

codegen (right_tree) + codegen (left_tree)

Lets say we compile this with a compiler X, which calls the left
function first. So the assembler code in the compiled code is

codegen (right_tree)
codegen (left_tree)

Compile the compiler using the compiler compiled by X. The assembler
code will now be

codegen (left_tree)
codegen (right_tree).

Compile the compiler with the generated code. The assembler code will
be

codegen (right_tree)
codegen (left_tree)

and so on. All the even versions are different from all the odd
versions.

[Roberto Waltman]

"christian. bau" wrote:

>Roberto Waltman wrote:

>[OT] No, (at least not as worded) A simple test that every
self-compiling compiler should pass, is that when compiling its own
sources it should produce exact duplicates of itself.

Not necessarily.

The order in which subexpressions are evaluated is compiler-dependent.
For example, if we have a function

int f (void* p);

then it is compiler-dependent whether in the expression

f (right) + f (left)

f (right) is called first or f (left) is called first.

Now assume that your compiler A has a function codegen (), and when
the compiler wishes to generate code for two function calls in
unspecified order, with the results discarded, it calls

codegen (right_tree) + codegen (left_tree)

Lets say we compile this with a compiler X, which calls the left
function first. So the assembler code in the compiled code is

codegen (right_tree)
codegen (left_tree)

Compile the compiler using the compiler compiled by X. The assembler
code will now be

codegen (left_tree)
codegen (right_tree).

Compile the compiler with the generated code. The assembler code will
be

codegen (right_tree)
codegen (left_tree)

and so on. All the even versions are different from all the odd
versions.

OK, I stand corrected. So the generated compilers fall into a cycle,
of length 2 in this case, (easily expanded to more.)
Is this always the case? (To have cyclic versions, that is.)

Roberto Waltman

[ Please reply to the group,
return address is invalid ]

[Malcolm McLean]

"lovecreatesbea [e-mail]" <lo************ ***@gmail.comwr ote in message
news

K&R says the following in the preface to the first edition,

"... the C compiler, and ... are written in C."

I'm wondering, does it say even the first / original C compiler was
written in C?

Yes.
So how did it compile itself? The usual way is to write a little
interpreter. Interpreters are far easier to write than compilers. See my
homepage for one in a single reasonable-length file.

The interpreter runs the compiler source on itself and creates the first
native compiler.

[Keith Thompson]

"Malcolm McLean" <re*******@btin ternet.comwrite s:

"lovecreatesbea [e-mail]" <lo************ ***@gmail.comwr ote in message
news

>K&R says the following in the preface to the first edition,

"... the C compiler, and ... are written in C."

I'm wondering, does it say even the first / original C compiler was
written in C?

Yes.

No, it doesn't say that. Somebody in this thread said that the first
C compiler was written in B. I just scanned
<http://cm.bell-labs.com/cm/cs/who/dmr/chist.htmlfor the word
"compiler"; I didn't see a clear statement to that effect. It appears
that there was an evolutionary path from B to C, with "NB" (New B)
somewhere in the middle. I think that the compiler and the language
evolved in parallel, with new language features being implemented by
the compiler, then used in the next version of the compiler.

So how did it compile itself? The usual way is to write a little
interpreter. Interpreters are far easier to write than compilers. See my
homepage for one in a single reasonable-length file.

The interpreter runs the compiler source on itself and creates the first
native compiler.

It could have been done that way, but as far as I can tell it wasn't.

--
Keith Thompson (The_Other_Keit h) ks***@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <* <http://users.sdsc.edu/~kst>
We must do something. This is something. Therefore, we must do this.

[David T. Ashley]

"Dave Hansen" <id**@hotmail.c omwrote in message
news:11******** *************@p 10g2000cwp.goog legroups.com...

On Feb 14, 11:38 am, "David T. Ashley" <[e-mail] rote:

Optimization is easy if you don't have to get
the right answer.

Regrettably, some compiler vendors have this integrated into their business
model. I was once told by tech support "Don't use optimizaton level 5 until
we get the bugs fixed".
--
David T. Ashley (dt*@e3ft.com)
http://www.e3ft.com (Consulting Home Page)
http://www.dtashley.com (Personal Home Page)
http://gpl.e3ft.com (GPL Publications and Projects)

[=?utf-8?B?SGFyYWxkIHZhbiBExLNr?=]

Roberto Waltman wrote:

"christian. bau" wrote:

Roberto Waltman wrote:

[OT] No, (at least not as worded) A simple test that every
self-compiling compiler should pass, is that when compiling its own
sources it should produce exact duplicates of itself.

Not necessarily.

The order in which subexpressions are evaluated is compiler-dependent.
For example, if we have a function

int f (void* p);

then it is compiler-dependent whether in the expression

f (right) + f (left)

f (right) is called first or f (left) is called first.

Now assume that your compiler A has a function codegen (), and when
the compiler wishes to generate code for two function calls in
unspecified order, with the results discarded, it calls

codegen (right_tree) + codegen (left_tree)

Lets say we compile this with a compiler X, which calls the left
function first. So the assembler code in the compiled code is

codegen (right_tree)
codegen (left_tree)

Compile the compiler using the compiler compiled by X. The assembler
code will now be

codegen (left_tree)
codegen (right_tree).

Compile the compiler with the generated code. The assembler code will
be

codegen (right_tree)
codegen (left_tree)

and so on. All the even versions are different from all the odd
versions.

OK, I stand corrected. So the generated compilers fall into a cycle,
of length 2 in this case, (easily expanded to more.)
Is this always the case? (To have cyclic versions, that is.)

No, this is not always the case. tinycc, for example, puts garbage in
its generated output. Its x86 long doubles are 96 bits, with only 80
value bits. When storing a long double in the generated object file,
all 96 bits are copied, but the 16 padding bits are never explicitly
initialised, and are for practical purposes completely random. You
can't even assume that one specific binary of the compiler with one
specific set of compiler options will always generate bitwise-
identical object code.

(I hope what I mean by "value bit" and "padding bit" is clear enough,
even though it does not exactly match the meanings of the same terms
as used by the standard.)

[Roberto Waltman]

"Harald van D?k" wrote:

>...
No, this is not always the case. tinycc, for example, puts garbage in
its generated output. Its x86 long doubles are 96 bits, with only 80
value bits. When storing a long double in the generated object file,
all 96 bits are copied, but the 16 padding bits are never explicitly
initialised, and are for practical purposes completely random. You
can't even assume that one specific binary of the compiler with one
specific set of compiler options will always generate bitwise-
identical object code.

[OT] Thanks, after I posted my last question I realized this is
possible, (thinking of uninitialized structs padding.)
There was a recent thread in comp.software-eng about verifying that
two source files are equivalent after "pretty-printing" one.
The OP resorted to compiling them and comparing the resulting object
files, it is clear now this is not guaranteed to work.

Roberto Waltman

[ Please reply to the group,
return address is invalid ]