Re: Certified C compilers for safety-critical embedded systems

["Robert I. Eachus" <rieachus@comcast.net>]

Chad R. Meiners wrote:

> Rice's theorem states this.  It is a result of the undecidablility of the
> Halting problem, and it is also related to Godel's incompleteness theorem.
> I would suggest taking a class on computation theory, but it might suffice
> to read a book on computation theory and work through the problems.
...
> No it isn't a contradiction.  SPARK is not a general purpose language; it is
> a special purpose language (SPARK is not Turing-Complete hence Rice's
> theorem doesn't apply to it), which is designed to facilitate deep static
> analysis.

True in practice, and also in theory due to limits on memory sizes.  But 
if you were to write a SPARK program that was an interpreter for a 
general purpose language, verification would only result in proving that 
the interpreter worked correct and say nothing about programs in the 
interpreted language.

Not how you would use SPARK in any case, but it is worth remembering. 
Just as I can write Ada programs that are not SPARK programs but can 
statically proven to halt, or I can write an Ada program for which no 
such proof is possible.  SPARK just provides a convenient way to write 
programs that can be proven correct, and to automate much of the proof.

In C it is much, much harder to write programs that can be proven 
correct, but it can be done.  One way is with an Ada to C translator. If 
I had to produce a large safety-critical system for a chip which did not 
have an Ada compiler, using an Ada to C translator (several exist) and 
the SPARK tools might be a decent alternative to an Ada port.

In practice for the small programs that are common on 8-bit chips, I 
find it easier to validate the generated code to the original requirements.

-- 
                                           Robert I. Eachus

"The war on terror is a different kind of war, waged capture by capture, 
cell by cell, and victory by victory. Our security is assured by our 
perseverance and by our sure belief in the success of liberty." -- 
George W. Bush