Refinement is a generic term of computer science that encompasses various approaches for producing correct computer programs and simplifying existing programs to enable their formal verification.
11-434: The refinement calculus is a formalized approach to stepwise refinement for program construction. The required behaviour of the final executable program is specified as an abstract and perhaps non-executable "program", which is then refined by a series of correctness-preserving transformations into an efficiently executable program. Proponents include Ralph-Johan Back , who originated the approach in his 1978 PhD thesis On
22-401: A program should also be satisfied by any refinement of it, which notion leads directly to specification statements as pre- and postconditions standing, on their own, for any program that could soundly be placed between them. This formal methods -related article is a stub . You can help Misplaced Pages by expanding it . Program refinement In formal methods , program refinement is
33-480: Is a stub . You can help Misplaced Pages by expanding it . Refinement calculus The refinement calculus is a formalized approach to stepwise refinement for program construction. The required behaviour of the final executable program is specified as an abstract and perhaps non-executable "program", which is then refined by a series of correctness-preserving transformations into an efficiently executable program. Proponents include Ralph-Johan Back , who originated
44-455: Is also commonly described as refinement. Data refinement is used to convert an abstract data model (in terms of sets for example) into implementable data structures (such as arrays ). Operation refinement converts a specification of an operation on a system into an implementable program (e.g., a procedure ). The postcondition can be strengthened and/or the precondition weakened in this process. This reduces any nondeterminism in
55-485: Is an industrial-strength implementation of refinement. The B-Method is also a formal method that extends refinement calculus with a component language: it has been used in industrial developments. In type theory , a refinement type is a type endowed with a predicate which is assumed to hold for any element of the refined type. Refinement types can express preconditions when used as function arguments or postconditions when used as return types : for instance,
66-425: Is unimplementable; it is impossible to select a member from the empty set . The term reification is also sometimes used (coined by Cliff Jones ). Retrenchment is an alternative technique when formal refinement is not possible. The opposite of refinement is abstraction . Refinement calculus is a formal system (inspired from Hoare logic ) that promotes program refinement. The FermaT Transformation System
77-448: The verifiable transformation of an abstract (high-level) formal specification into a concrete (low-level) executable program . Stepwise refinement allows this process to be done in stages. Logically, refinement normally involves implication , but there can be additional complications. The progressive just-in-time preparation of the product backlog (requirements list) in agile software development approaches, such as Scrum ,
88-652: The Correctness of Refinement Steps in Program Development , and Carroll Morgan , especially with his book Programming from Specifications (Prentice Hall, 2nd edition, 1994, ISBN 0-13-123274-6 ). In the latter case, the motivation was to link Abrial 's specification notation Z , via a rigorous relation of behaviour-preserving program refinement , to an executable programming notation based on Dijkstra 's language of guarded commands . Behaviour-preserving in this case means that any Hoare triple satisfied by
99-576: The approach in his 1978 PhD thesis On the Correctness of Refinement Steps in Program Development , and Carroll Morgan , especially with his book Programming from Specifications (Prentice Hall, 2nd edition, 1994, ISBN 0-13-123274-6 ). In the latter case, the motivation was to link Abrial 's specification notation Z , via a rigorous relation of behaviour-preserving program refinement , to an executable programming notation based on Dijkstra 's language of guarded commands . Behaviour-preserving in this case means that any Hoare triple satisfied by
110-480: The specification, typically to a completely deterministic implementation. For example, x ∈ {1,2,3} (where x is the value of the variable x after an operation) could be refined to x ∈ {1,2}, then x ∈ {1}, and implemented as x := 1. Implementations of x := 2 and x := 3 would be equally acceptable in this case, using a different route for the refinement. However, we must be careful not to refine to x ∈ {} (equivalent to false ) since this
121-416: The type of a function which accepts natural numbers and returns natural numbers greater than 5 may be written as f : N → { n : N | n > 5 } {\displaystyle f:\mathbb {N} \rightarrow \{n:\mathbb {N} \,|\,n>5\}} . Refinement types are thus related to behavioral subtyping . This software-engineering -related article
SECTION 10
#1733104906149#148851