Re: Integrity Implied by Ada Compiler Validation?



Date view Thread view Subject view Author view

Pete Mellor (pm(at)csr.city.ac.uk)
Mon, 10 Jul 1995 11:18:07 BST


Immediately after the initial message on this subject, I did not have time to get stuck in properly, although I would dearly have liked to have done so. In the meantime, a number of people (most recently John McDermid) have said most of what I would have liked to have said (probably in a rather more articulate way! :-) In fact, the problem did not begin with Ada. Brian Wichman [1] of the National Physical Laboratory once gave a talk about the validation of Pascal compilers, for which he was then (and might still be) responsible. Pascal is a *much* simpler language than Ada. Over the years, the NPL has developed a suite of fairly stressful test programs for Pascal compilers. These have been built up in two ways:- - a priori: "If we look at the Pascal syntax definition, then a compiler should accept program X and reject program Y." - a posteriori: "We gave program Z to our Turdo Pascal compiler, and look at what it did!" (Program Z is promptly added to the growing validation suite.) The validation suite is concerned not only with compilation (a compiler should accept anything that is syntactically correct and reject anything that is syntactically wrong) but also with run-time results (semantically, the program should do what the programmer intended when it is executed). Despite many years of building such a validation suite, the NPL is adamant that:- - It does not catch everything. A compiler could pass all the existing tests with flying colours and still fail tomorrow on some new set of source code. - To be "validated", a compiler does not have to pass all of the tests (otherwise there would be no such thing as a validated Pascal compiler! :-). I forget what percentage constitutes a "pass mark". - A "validated" compiler might still insert bugs into the object program when compiling an apparently "correct" source program. My own experience bears this out:- A. A *very* widely used Pascal compiler for PCs gave results for a statistical analysis of failure data which showed a trend exactly the opposite of what was expected. After spending two days convincing myself that this was not due to a bug in the source code, I wrote a little benchmark program and demonstrated in 5 minutes that the compiler "thought" that exp(+x) = exp(-x) (a fairly gross misconception when dealing with the mathematics of reliability! :-) Solution: replace every occurrence of exp(-x) with 1/exp(x), and everything was hunky-dory. B. The same Pascal compiler was reissued in a 16-bit version. (OK, I know this dates me! :-) The same statistical analysis package was recompiled for 16-bit machines, and a rerun on a set of data which had previously taken 30 minutes to analyse took 2 hours. Again, a benchmark test showed that, although integer arithmetic showed the predictable increase in performance over the 8-bit machine, floating point arithmetic took four times as long! Presumed cause: the idiots who wrote the compiler had not taken advantage of the 16-bit architecture, but had simply handled 16-bit FP as a two-stage 8-bit algorithm. Solution: scrap the damn thing, and get a decent compiler! (NPL later confirmed privately that the new compiler we had acquired was one of the better ones as indicated by their validation suite, whereas the previous one was sh ... errr, not quite so good! :-) C. A completely different Pascal compiler on a completely different platform (UNIX workstation) was acclaimed in its own manual to conform to the ISO standard. When it became apparent that (again while doing reliability calculations) it was "losing" very small FP numbers, a quick benchmark program revealed that, although all internal FP calculations were done double-length (as stated in the manual), I/O and the setting up of program constants were done single-length. Result: try to use an FP number with a negative exponent whose magnitude exceeded what could be represented in single length format, and the damn thing underflowed silently and set all the affected constants and input values to zero! Solution: I wrote my own I/O routines and calculated all the program constants at run-time, and everything was tickety-boo. THIS IS PASCAL!!! Nice easy simple noddy little Pascal, and we still can't get it right! For Ada, multiply the magnitude of the potential problems by 100, or even 1000. When will they ever learn? (Quote from a song, which dates me again! :-) Pascal was the result of an attempt to "improve on" (nice easy simple noddy little) ALGOL 60. The actual "result" of years of deliberation by the committee was (nasty difficult baroque non-intuitive) ALGOL 68. I remember it fondly, having taught it to myself from the manual in order to calculate correlation coefficients from matrices for my first ever "bit on the side" consultancy contract. At the time there was a vicious rumour circulating that in fact ALGOL 68 was not the answer to all our prayers, but that some of the committee (Wirth, Hoare, et al.) had produced a dissenting report, and one of them had even gone away and designed his own language. Then came compiler wars. I was in the ALGOL 68 corner, and regarded Pascal as beneath contempt. Graffiti spotted in the gents' lavatory in the Eagle in Cambridge around this time read "ALGOL 68 rules REF OK!", to which I nearly added "REF REF right-on, brother!" :-) The rest, as they say, is history. ALGOL 68 lies buried at the foot of the Tower of Babel, smothered in its own facilities, and some silly little "teaching language" has gone from strength to strength in just about every application domain you can think of. For the full story, anyone with the slightest interest in the history of computing should run (don't walk!) to the library and read Tony Hoare's Turing lecture "The Emperor's Old Clothes". Pete Mellor, Centre for Software Reliability, City University, Northampton Square, London EC1V 0HB Tel: +44 (171) 477-8422, Fax.: +44 (171) 477-8585, E-mail (JANET): p.mellor(at)csr.city.ac.uk [1] Disclaimer: The presentation was many years ago, and I am relying on my unreliable memory. If Brian happens to read this, and disagrees, I stand to be corrected. -----------------------------------------------------------------------------


Date view Thread view Subject view Author view