Path: utzoo!attcan!uunet!husc6!bloom-beacon!bu-cs!mirror!necntc!ima!compilers-sender From: peterd@june.cs.washington.edu (Peter C. Damron) Newsgroups: comp.compilers Subject: Re: Why Can't We Build a C Compiler? Summary: nobody knows how Message-ID: <3080@ima.ima.isc.com> Date: 21 Dec 88 22:07:47 GMT References: <3070@ima.ima.isc.com> Sender: compilers-sender@ima.ima.isc.com Reply-To: peterd@june.cs.washington.edu (Peter C. Damron) Organization: U of Washington, Computer Science, Seattle Lines: 76 Approved: compilers@ima.UUCP 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 -- 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