Effect system
Encyclopedia
An effect system is a formal system
which describes the computational effects of computer programs, such as side effect
s. An effect system can be used to provide a compile-time checking of the possible effects of the program.
The effect system extends the notion of type to have an "effect" component, which comprises an effect kind and a region. The effect kind describes what is being done, and the region describes with what it is being done.
An effect system is typically an extension of a type system
. The term "type and effect system" is sometimes used in this case. Often, a type of a value is denoted together with its effect as type ! effect, where both the type component and the effect component mention certain regions (for example, a type of a mutable memory cell is parameterized by the label of the memory region in which the cell resides).
Some examples of the behaviors that can be described by effect systems include:
Effect systems may be used to prove the external purity of certain internally impure definitions: for example, if a function internally allocates and modifies a region of memory, but the function's type does not mention the region, then the corresponding effect may be erased from the function's effect.
Formal system
In formal logic, a formal system consists of a formal language and a set of inference rules, used to derive an expression from one or more other premises that are antecedently supposed or derived . The axioms and rules may be called a deductive apparatus...
which describes the computational effects of computer programs, such as side effect
Side effect (computer science)
In computer science, a function or expression is said to have a side effect if, in addition to returning a value, it also modifies some state or has an observable interaction with calling functions or the outside world...
s. An effect system can be used to provide a compile-time checking of the possible effects of the program.
The effect system extends the notion of type to have an "effect" component, which comprises an effect kind and a region. The effect kind describes what is being done, and the region describes with what it is being done.
An effect system is typically an extension of a type system
Type system
A type system associates a type with each computed value. By examining the flow of these values, a type system attempts to ensure or prove that no type errors can occur...
. The term "type and effect system" is sometimes used in this case. Often, a type of a value is denoted together with its effect as type ! effect, where both the type component and the effect component mention certain regions (for example, a type of a mutable memory cell is parameterized by the label of the memory region in which the cell resides).
Some examples of the behaviors that can be described by effect systems include:
- Reading, writing or allocating memory: the effect kind is read, write, allocate or free, and the region is the point of the program where allocation was performed (i.e., each program point where allocation is performed is assigned a unique label, and region information is statically propagated along the dataflow). Most functions working with memory will actually be polymorphic in the region variable: for example, a function that swaps two locations in memory will have type forall r1 r2, unit ! {read r1, read r2, write r1, write r2}.
- Working with resources, such as files: for example, the effect kind may be open, read and close, and again, the region is the point of the program where the resource is opened.
- Control transfers with continuations and long jumps: the effect kind may be gotoGotogoto is a statement found in many computer programming languages. It is a combination of the English words go and to. It performs a one-way transfer of control to another line of code; in contrast a function call normally returns control...
(i.e. the piece of code may perform a jump) and comefromCOMEFROMIn computer programming, COMEFROM is an obscure control flow structure used in some programming languages, originally as a joke....
(i.e. the piece of code may be the target of a jump), and the region denotes the point of the program from which or to which the jump may be performed. - Java's checked exceptions are an example of an effect system: the effect kind is throws and the region is the type of the exception being thrown.
Effect systems may be used to prove the external purity of certain internally impure definitions: for example, if a function internally allocates and modifies a region of memory, but the function's type does not mention the region, then the corresponding effect may be erased from the function's effect.