Does C implement the first C compiler itself?

[lovecreatesbea...@gmail.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?

[Christopher Layne]

Re: Does C implement the first C compiler itself?

lovecreatesbea. ..@gmail.com wrote:

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?

Put some deductive reasoning/logic into it.

[Roberto Waltman]

Re: Does C implement the first C compiler itself?

Christopher Layne wrote:

>lovecreatesbea ...@gmail.com wrote:

>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?

Read "The Development of the C Language" at Dennis Ritchie home page (
http://cm.bell-labs.com/who/dmr )

>Put some deductive reasoning/logic into it.

[OT] That may lead you to logically correct, but nevertheless false
conclusions. The first version of an Algol-like system programming
language for Burroughs mainframes (B5000?) was written in itself.
It was "hand compiled" into assembler to get the first running
version, and it was self-sustained from there.


Roberto Waltman

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

[Christopher Layne]

Re: Does C implement the first C compiler itself?

Roberto Waltman wrote:

[OT] That may lead you to logically correct, but nevertheless false
conclusions. The first version of an Algol-like system programming
language for Burroughs mainframes (B5000?) was written in itself.
It was "hand compiled" into assembler to get the first running
version, and it was self-sustained from there.

You just contradicted yourself. That was my point.

The first version was written in another language.

[Dave Hansen]

Re: Does C implement the first C compiler itself?

On Feb 14, 10:09 am, Christopher Layne <cla...@com.ano dizedwrote:

Roberto Waltman wrote:

[OT] That may lead you to logically correct, but nevertheless false
conclusions. The first version of an Algol-like system programming
language for Burroughs mainframes (B5000?) was written in itself.
It was "hand compiled" into assembler to get the first running
version, and it was self-sustained from there.

>
You just contradicted yourself. That was my point.
>
The first version was written in another language.

Not so.

The compiler was _written_ in the target language. It was
_translated_ to assembly.

This is a very common process referred to as "bootstrapp ing" a
compiler. It's a very useful exercise, in that it proves (or
disproves) the utility of the language with a non-trivial application,
and provides an immediate base of test code. Compilers tend to
require a wide range of algorithmic techniques and a variety of data
structures. If your language can implement a compiler, it's likely to
be useful for most other tasks as well.

Though these days, the intermediate language would more likely be C
than assembly, the process is essentially unchanged.

I guess you could argue that the first version of the compiler was
wetware writ by the finger of God, but that probably isn't very
helpful.

Regards,

-=Dave

[David T. Ashley]

Re: Does C implement the first C compiler itself?

"lovecreatesbea ...@gmail.com" <lovecreatesbea uty@gmail.comwr ote in message
news:1171467947 .107229.85480@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?

Surprisingly, I understand the thought process behind this frivolous
question.

Here is another related question:

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?

(This is no more and no less frivolous than the original.)
--
David T. Ashley (dta@e3ft.com)
http://www.e3ft.com (Consulting Home Page)
http://www.dtashley.com (Personal Home Page)
http://gpl.e3ft.com (GPL Publications and Projects)

[Chris McDonald]

Re: Does C implement the first C compiler itself?

"David T. Ashley" <dta@e3ft.comwr ites:

>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?

But there's no guarantees that there's optimizations to be made...

--
Chris.

[santosh]

Re: Does C implement the first C compiler itself?


lovecreatesbea. ..@gmail.com wrote:

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?

You may be interested in the following link:

<http://cm.bell-labs.com/cm/cs/who/dmr/chist.html>

[Keith Thompson]

Re: Does C implement the first C compiler itself?

"David T. Ashley" <dta@e3ft.comwr ites:

"lovecreatesbea ...@gmail.com" <lovecreatesbea uty@gmail.comwr ote in message
news:1171467947 .107229.85480@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?

>
Surprisingly, I understand the thought process behind this frivolous
question.
>
Here is another related question:
>
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?

No. An optimizer (if it's working properly) makes the target code run
more quickly; it doesn't change its behavior.

Suppose you have C sources for two C compilers, compiler1 and
compiler2. compiler1 includes a very clever optimizer; compiler2
doesn't. Use compiler2 to compile itself, yielding compiler2a.exe,
which compiles slowly. Use compiler1 to compile compiler2, yielding
compiler2b.exe, which compiles more quickly. But compiler2a.exe and
compiler2b.exe work the same way; the code they generate is identical.

--
Keith Thompson (The_Other_Keit h) kst-u@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.

[Roberto Waltman]

Re: Does C implement the first C compiler itself?

"David T. Ashley" wrote:

>"lovecreatesbe a...@gmail.com" wrote in message

>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?

>
>Surprisingly , I understand the thought process behind this frivolous
>question.

Why frivolous?

>Here is another related question:
>
>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?

[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.

If you then change the sources improving the optimization algorithms,
the compiler should produce a faster and/or smaller version of itself
reaching again a steady state after a few iterations.

To expect the cycle to continue for ever is akin to expect a file
compression algorithm to always reduce a file's size, which leads to
the conclusion that all files can be compressed into a single bit.

I could not find a reference now, but I recall reading about Niklaus
Wirth using this process to evaluate optimizations for his Pascal
compilers.

An optimization that would result in a faster or smaller compiler was
integrated in the code, but increasing the complexity of the compiler
with additional optimization steps that could improve code in some
marginal cases, but would not have a significant effect in the Pascal
compiler itself, was not considered a worthwhile trade-off.

Roberto Waltman

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

[Dave Hansen]

Re: Does C implement the first C compiler itself?

On Feb 14, 11:38 am, "David T. Ashley" <d...@e3ft.comw 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]

Re: Does C implement the first C compiler itself?

"lovecreatesbea ...@gmail.com" <lovecreatesbea uty@gmail.comwr ote in message
news:1171467947 .107229.85480@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]

Re: Does C implement the first C compiler itself?

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

On Feb 14, 11:38 am, "David T. Ashley" <d...@e3ft.comw 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]

Re: Does C implement the first C compiler itself?

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]

Re: Does C implement the first C compiler itself?

"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 ]