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

I think that Scott has some good points about the state of compiler
technology. Reliability and correctness have generally taken a back seat to
performance, efficiency, and expediency. However, I think that several issues
are mis-stated or mis-understood.


In article <3070@ima.ima.isc.com>, acw!guthery@uunet.uu.net (Scott Guthery) writes:
> "C is not a `very high level' language, nor a `big' one ...".


It is big enough to cause problems.


> Its syntax and semantics are well-defined.


While I would agree that the syntax is well defined, I cannot say the same
about the semantics. Note the difficulty in standardizing C. There is
no formal semantic specification for the language.


Likewise, there is no formal semantic specification of the target machines.
This lack of formal semantics means that we cannot verify correctness of the
compiler even if we had the tools to do it. Of course, we cannot prove any but
the smallest of programs correct anyway.


> A C compiler is probably a relatively small and not a particularly
> complicated computer program.


I would argue that compilers are one of the most complex classes of computer
programs in regular use. Operating systems are the only class of programs I
can think of that are probably more complex. [How about data bases? -John]


> We have constructed a number of very powerful of tools to help us
> build C compilers.


The purpose of tools is to increase our assurance that the implementation
is correct. Since no single tool builds the complete compiler,
the interactions between different tools can still cause problems.


We are working on better tools for compilers, but it takes time (and money).
Thirty or so years is not very long in the development of a technology.


> We have an extensive theoretical and practical compiler literature
> going back at least 30 years.


> Is it even possible to build a C compiler?
> How will we recognize it if it does happen to come into being?


These are good questions. Although we may achieve the first, we may never be
able to prove it. We don't yet have the techniques to do the second, and we
may never.


Writing compilers, as with all software, is an engineering effort.
We try to build something that works within constraints on time and performance.


Testing is the closest we can coming to assuring ourselves of the correctness
of the compiler implementation. But testing is not well formalized either.
Complete testing might be too expensive and time consuming anyway.


I think that we have made enough progress in formal semantics that we can
specify the semantics of the language or the computer, but the specification
is as large and complex as a program, and is thus subject to error.


We do not have tools (or theory?) to compare a sentence in one semantic
domain to a sentence in another semantic domain. Thus we cannot compare
a translation with the original to verify that we have preserved
the original semantics.


Peter C. Damron
Dept. of Computer Science, FR-35
University of Washington
Seattle, WA 98195


peterd@cs.washington.edu
{ucbvax, decvax, ...}!uw-beaver!uw-june!peterd
--

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