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.
Program refinement
In
formal methods, program refinement is the
verifiable transformation of an ''abstract'' (high-level)
formal specification into a ''concrete'' (low-level)
executable program. ''
Stepwise refinement
Top-down and bottom-up are both strategies of information processing and knowledge ordering, used in a variety of fields including software, humanistic and scientific theories (see systemics), and management and organization. In practice, they c ...
'' 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, is also commonly described as refinement.
Data refinement
Data refinement is used to convert an abstract data model (in terms of
set
Set, The Set, SET or SETS may refer to:
Science, technology, and mathematics Mathematics
*Set (mathematics), a collection of elements
*Category of sets, the category whose objects and morphisms are sets and total functions, respectively
Electro ...
s for example) into implementable
data structures
In computer science, a data structure is a data organization, management, and storage format that is usually chosen for efficient access to data. More precisely, a data structure is a collection of data values, the relationships among them, ...
(such as
arrays). Operation refinement converts a
specification of an operation on a system into an implementable
program
Program, programme, programmer, or programming may refer to:
Business and management
* Program management, the process of managing several related projects
* Time management
* Program, a part of planning
Arts and entertainment Audio
* Programm ...
(e.g., a
procedure). The
postcondition can be strengthened and/or the
precondition weakened in this process. This reduces any
nondeterminism in the specification, typically to a completely
deterministic implementation.
For example, ''x'' ∈ (where ''x'' is the value of the
variable ''x'' after an operation) could be refined to ''x'' ∈ , then ''x'' ∈ , 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 is unimplementable; it is impossible to select a
member
Member may refer to:
* Military jury, referred to as "Members" in military jargon
* Element (mathematics), an object that belongs to a mathematical set
* In object-oriented programming, a member of a class
** Field (computer science), entries in ...
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
Abstraction in its main sense is a conceptual process wherein general rules and concepts are derived from the usage and classification of specific examples, literal ("real" or " concrete") signifiers, first principles, or other methods.
"An abst ...
.
Refinement calculus
Refinement calculus is a
formal system
A formal system is an abstract structure used for inferring theorems from axioms according to a set of rules. These rules, which are used for carrying out the inference of theorems from axioms, are the logical calculus of the formal system.
A fo ...
(inspired from
Hoare logic) that promotes program refinement. The
FermaT Transformation System
Pierre de Fermat (; between 31 October and 6 December 1607 – 12 January 1665) was a French mathematician who is given credit for early developments that led to infinitesimal calculus, including his technique of adequality. In particular, he i ...
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.
Refinement types
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 type
In computer programming, the return type (or result type) defines and constrains the data type of the value returned from a subroutine or method. In many programming languages (especially statically-typed programming languages such as C, C+ ...
s: for instance, the type of a function which accepts natural numbers and returns natural numbers greater than 5 may be written as
. Refinement types are thus related to
behavioral subtyping In object-oriented programming, behavioral subtyping is the principle that subclasses should satisfy the expectations of clients accessing subclass objects through references of superclass type, not just as regards syntactic safety (such as the abse ...
.
See also
*
Reification (computer science)
References
Formal methods terminology
Computer programming
{{soft-eng-stub