Re: Why Can't We Build a C Compiler?

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

Return to the comp.compilers page.
Search the comp.compilers archives again.