Path: utzoo!utgpu!watmath!clyde!ima!compilers-sender
From: pardo@june.cs.washington.edu (David Keppel)
Newsgroups: comp.compilers
Subject: Re: Why Can't We Build a C Compiler?
Summary: Because
Message-ID: <3073@ima.ima.isc.com>
Date: 19 Dec 88 19:11:52 GMT
References: <3070@ima.ima.isc.com>
Sender: compilers-sender@ima.ima.isc.com
Reply-To: pardo@june.cs.washington.edu (David Keppel)
Organization: U of Washington, Computer Science, Seattle
Lines: 45
Approved: compilers@ima.UUCP

acw!guthery@uunet.uu.net (Scott Guthery) writes:
>[Why can't we build a C compiler?]

I certainly have to agree with the text of Scott's article.  A couple
things to think about:

* One standard implementation of P() and V() (semaphore operations)
  was proposed, I believe, in the early 60's.  It is 20 lines of code
  in nearly any language (even assembly!), yet it took 15+ years and
  dozens (hundreds?) of implementations before we all found out that
  there was a little itsy-bitsy bug in it.  One line was in the wrong
  procedure and every once in a while you'd lose a race.

* Proofs of correctness are very useful, particularly in things such
  as P() and V(), but they are hard to do straight and hard to
  automate.  My advisor of days gone by told me ``proofs of
  correctness, done by humans, anyway, are subject to bugs just like
  the programs that they are supposed to prove.''  Good point.

* The implementor is often not sure of the specification of some
  detail of the protocol[*] they are trying to implement.  One look
  at comp.std.c should be enough to convince you that there are lots
  of ``gray areas'' in the ``standard'' C.  It is essentially
  impossible to fully-specify all but the simplest protocols (even if
  just to remember to say ``behavior is implementation-defined''),
  and, given current systems, a too-detailed specifcation can
  sometimes lead to performance problems (e.g., using IEEE
  floating-point math vs. Cray floating-point math).

Footnote [*]: essentially all programs can be thought of as protocols.

Realize, also, that a compiler is a bit of an obfuse example.  The
code generator for a given computer is ``useless'' == untestable for
any other computer, and many parts of the compiler depend on the
correctness of the code generator.  In one sense this makes Scott's
points even more relevant: it even more important to ``get it right
the first time''.  On the other hand, the points that Scott made are
all true of machine-independent programs as well.  Well-known examples
are, perhaps, harder to find, but more people might agree about the
nature of some of the bugs.

	;-D on  ( Folowup discussions of SDI to ??? )  Pardo
-- 
		    pardo@cs.washington.edu
    {rutgers,cornell,ucsd,ubc-cs,tektronix}!uw-beaver!june!pardo
--
Send compilers articles to ima!compilers or, in a pinch, to Levine@YALE.EDU
Plausible paths are { decvax | harvard | yale | bbn}!ima
Please send responses to the originator of the message -- I cannot forward
mail accidentally sent back to compilers.  Meta-mail to ima!compilers-request