imported>Bkell: decap "distributed"

2025-09-30T21:55:07Z

decap "distributed"

New page

In [[computer science]], '''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 (computer science)|correctness]] proof are constructed together.

The approach usually taken in [[formal verification]] is to first write a program, and then provide a [[mathematical proof|proof]] that it conforms to a given [[program specification|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.

The [[Bird-Meertens Formalism]] is an approach to program derivation.

Approaches to achieving correctness in [[distributed computing]] include research languages such as the [[P (programming language)|P programming language]].

==See also==
* [[Automatic programming]]
* [[Hoare logic]]
* [[Program refinement]]
* [[Design by contract]]
* [[Program synthesis]]
* [[Proof-carrying code]]

==References==
* [[Edsger W. Dijkstra]], Wim H. J. Feijen, ''A Method of Programming'', Addison-Wesley, 1988, 188 pages
* Edward Cohen, ''Programming in the 1990s'', Springer-Verlag, 1990
* Anne Kaldewaij, ''Programming: The Derivation of Algorithms'', Prentice-Hall, 1990, 216 pages
* David Gries, ''The Science of Programming'', Springer-Verlag, 1981, 350 pages
* [[Carroll Morgan (computer scientist)]], [http://www.cs.ox.ac.uk/publications/books/PfS/ ''Programming from Specifications''], International Series in Computer Science (2nd ed.), Prentice-Hall, 1998.
* [[Eric Hehner|Eric C.R. Hehner]], [http://www.cs.toronto.edu/~hehner/aPToP/ ''a Practical Theory of Programming''], 2008, 235 pages
* A.J.M. van Gasteren. ''On the Shape of Mathematical Arguments''. Lecture Notes in Computer Science #445, Springer-Verlag, 1990. Teaches how to write proofs with clarity and precision.
* Martin Rem. "Small Programming Exercises", appeared in ''Science of Computer Programming'', Vol.3 (1983) through Vol.14 (1990).
* Roland Backhouse. ''Program Construction: Calculating Implementations from Specifications''. Wiley, 2003. {{ISBN|978-0-470-84882-1}}.
* Derrick G. Kourie, Bruce W. Watson. ''The Correctness-by-Construction Approach to Programming''. Springer-Verlag, 2012. {{ISBN|978-3-642-27919-5}}. Provides a step-by-step explanation of how to derive mathematically correct algorithms using small and tractable refinements.

[[Category:Program derivation| ]]

Program derivation - Revision history

imported>Bkell: decap "distributed"