In computer science

Computer science

Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...

, program derivation is the derivation of a program from its specification, by mathematical means.

To derive a program means to write a formal specification, which is usually non-executable, and then apply mathematically correct rules in order to obtain an executable program satisfying that specification. The program thus obtained is then correct by construction. Program and correctness proof are constructed together.

The approach usually taken in formal verification

Formal verification

In the context of hardware and software systems, formal verification is the act of proving or disproving the correctness of intended algorithms underlying a system with respect to a certain formal specification or property, using formal methods of mathematics .- Usage :Formal verification can be...

 is to first write a program, and then provide a proof

Mathematical proof

In mathematics, a proof is a convincing demonstration that some mathematical statement is necessarily true. Proofs are obtained from deductive reasoning, rather than from inductive or empirical arguments. That is, a proof must demonstrate that a statement is true in all cases, without a single...

 that it conforms to a given specification. The main problems with this are that

• the resulting proof is often long and cumbersome;
• no insight is given as to how the program was developed; it appears "like a rabbit out of a hat";
• should the program happen to be incorrect in some subtle way, the attempt to verify it is likely to be long and certain to be fruitless.

Program derivation tries to remedy these shortcomings by

• keeping proofs shorter, by development of appropriate mathematical notations;
• making design decisions through formal manipulation of the specification.

Terms that are roughly synonymous with program derivation are: transformational programming, algorithmics, deductive programming.

See also

• Bird-Meertens Formalism
  Bird-Meertens Formalism
  The Bird-Meertens Formalism is a calculus for deriving programs from specifications , devised by Richard Bird and Lambert Meertens....
  
  
• Hoare logic
  Hoare logic
  Hoare logic is a formal system with a set of logical rules for reasoning rigorously about the correctness of computer programs. It was proposed in 1969 by the British computer scientist and logician C. A. R. Hoare, and subsequently refined by Hoare and other researchers...
  
  
• Program refinement
• Design by contract
  Design by contract
  Design by contract , also known as programming by contract and design-by-contract programming, is an approach to designing computer software...