Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!mnetor!seismo!rutgers!mit-eddie!necntc!frog!john
From: john@frog.UUCP (John Woods, Software)
Newsgroups: sci.lang,comp.lang.misc
Subject: Re: Using C to describe itself
Message-ID: <1336@frog.UUCP>
Date: Thu, 30-Apr-87 17:42:00 EDT
Article-I.D.: frog.1336
Posted: Thu Apr 30 17:42:00 1987
Date-Received: Sun, 3-May-87 01:35:55 EDT
References: <437@haddock.UUCP> <1829@enea.UUCP> <440@haddock.UUCP> <7360@boring.mcvax.cwi.nl> <738@usfvax2.UUCP>
Organization: Superfrog Heaven [ CRDS, Framingham MA ]
Lines: 43
Xref: mnetor sci.lang:565 comp.lang.misc:371

>In article <7360@boring.mcvax.cwi.nl>, Steven Pemberton writes:
>> In article <1403@uwmacc.UUCP> Mark Edwards writes:
>>>   Yes indeed C can describe itself.
>>Actually, I'm not completely convinced of this...
>>Evidence of this is in Dennis Ritchie's Turing award lecture: he had built a
>>trojan horse into the C compiler. The compiler looked identical to its
>>previous self, but actually compiled a (slightly) different language.
> 
>I've never heard of Ritchie's "Turing award lecture".  What was that lecture,
>and what exactly was the Trojan horse you mention?

See Communications of the ACM, August 1984 (Vol 27 #8), page 761:
"Reflections on Trusting Trust", Ken Thompson (NOTE:  'twas KT who
"enbugged" :-) the compiler, not DMR) (They both won the 1983 Turing Award).
His Trojan Horse had two parts:

(1) A section of code inserted into the C compiler which would detect that it
was compiling login, and add code to login to enable a "magic password".

(2) A second section of code which detected that it was compiling the C
compiler, and inserted "features" (1) and (2).  This is a special case of the
famous "self-reproducing program" concept.

Once compiler (2) was compiled, the source was thrown away, and in effect, the
source to compiler (0) WAS the source to compiler (2)!.

C can't "describe" itself, at least not in the person of the text of the C
compiler, unless you ALREADY have a higher authority to appeal to to decide
what the C compiler itself means.  This is, in fact, quite a deep observation,
which extends to far more than the C language, or computer languages in
general.

The text of this message is actually instructions on how to construct an
atomic bomb, if you interpret it correctly :-).


--
John Woods, Charles River Data Systems, Framingham MA, (617) 626-1101
...!decvax!frog!john, ...!mit-eddie!jfw, jfw%mit-ccc@MIT-XX.ARPA

"Happiness is the planet Earth
	in your rear-view mirror."
		- Sam Hurt, in "Eyebeam, Therefore I Am"