Editing Effect system

{{Short description|System which describes the computational effects of computer programs}}
{{More footnotes needed|date=September 2010}}
In [[computing]], an '''effect system''' is a [[formal system]] that describes the computational effects of computer programs, such as [[side effect (computer science)|side effect]]s. An effect system can be used to provide a [[compile-time]] check 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'' (parameters) 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). The term "algebraic effect" follows from the type system.

Effect systems may be used to prove the external [[Pure function|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.<ref>{{Cite book|last=Albin.|first=Turbak, Franklyn|url=http://worldcat.org/oclc/1261053520|title=Design concepts in programming languages|date=2010|publisher=PHI Learning|isbn=978-81-203-3996-5|oclc=1261053520}}</ref>

== Examples ==
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 {{code|forall r1 r2, unit ! {{mset|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 ''[[goto]]'' (i.e. the piece of code may perform a jump) and ''[[comefrom]]'' (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.

From a programmer's point of view, effects are useful as it allows for separating the implementation (''how'') of specific actions from the specification of what actions to perform. For example, an ''ask name'' effect can read from either the console, pop a window, or just return a default value. The control flow can be described as a blend of [[Generator (computer programming)|''yield'']] (in that the execution continues) and [[Exception handling|''throw'']] (in that an unhandled effect propagates down until handled).<ref>{{cite web |last1=Abramov |first1=Dan |title=Algebraic Effects for the Rest of Us |url=https://overreacted.io/algebraic-effects-for-the-rest-of-us/ |website=overreacted.io |language=en}}</ref>

== Implementations ==

=== Core Feature ===
* [[Koka (programming language)|Koka]] is a [[statically typed]] [[functional programming]] language with algebraic effect handlers as a main feature.<ref>{{cite web |title=The Koka Manual |url=https://koka-lang.github.io/koka/doc/kokaspec.html |website=koka-lang.github.io}}</ref>
* [[Eff (programming language)|Eff]] is a statically typed functional programming language centered around algebraic effect handlers.<ref>{{Citation|last=Pretnar|first=Matija|title=Eff|date=2021-12-07|url=https://github.com/matijapretnar/eff|access-date=2021-12-11}}</ref>
* [[Unison (programming language)|Unison]] is a statically typed functional programming language with algebraic effect handlers (called "abilities" in the language) as a core part of the type system.<ref>{{Cite web|title=The Unison language|url=https://www.unisonweb.org/|access-date=2021-12-07|website=www.unisonweb.org}}</ref>
* [https://effekt-lang.org/ Effekt] is a research language centered around effect handlers and polymorphic effects.<ref>{{Cite web |author=The Effekt research team|title=Effekt Language: Concepts and Features |url=https://effekt-lang.org/docs/concepts |access-date=2023-06-13 |website=Effekt Language}}</ref>

=== Full Support ===
* [[Haskell (programming language)|Haskell]] is a statically typed functional programming language with several packages that allow for encoding of effects.<ref>{{cite web |last1=Vera |first1=Josh |title=joshvera/freemonad-benchmark |url=https://github.com/joshvera/freemonad-benchmark |website=GitHub |date=18 April 2020 |quote=A benchmark comparing the performance of different free monad implementations.}}</ref> However, Haskell is generally more focused on [[Monad (functional programming)|monads]].
* [[OCaml|OCaml 5.0]] introduced support for experimental effect handler primitives,<ref>{{Cite web |title=OCaml - Language extensions |url=https://v2.ocaml.org/manual/effects.html |access-date=2023-06-13 |website=v2.ocaml.org}}</ref> with plans to introduce a proper high-level syntax in the future.

=== Partial Support and Prototypes ===
* [[Scala (programming language)|Scala 3.1]] is a statically typed, functional and [[object oriented]] programming language with experimental support for effects that is limited to [[Exception (computer science)|exception]]s, in the form of a <code>CanThrow</code> capability.<ref>{{Cite web|title=CanThrow Abilities|url=https://docs.scala-lang.org/scala3/reference/experimental/canthrow.html|access-date=2021-12-07|website=Scala Documentation}}</ref>
* [[Java (programming language)|Java]] is a statically typed, object oriented programming language; its [[checked exception]]s are a relatively limited example of an effect system. Only one effect kind — <code>throws</code> — is available, there is no way to resume with a value, and they cannot be used with functions (only methods) unless the function implements a custom <code>[[@FunctionalInterface]]</code>.<ref>{{Cite web|title=Java 8 Lambda function that throws exception?|url=https://stackoverflow.com/questions/18198176/java-8-lambda-function-that-throws-exception|access-date=2021-12-25|website=Stack Overflow}}</ref>

==References==
{{Reflist}}

===Textbook chapters===
*{{Cite book|last1=Hankin|first1=Chris|last2=Nielson|first2=Flemming|last3=Nielson|first3=Hanne Riis|author3-link=Hanne Riis Nielson|title=Principles of Program Analysis|year=1999|publisher=Springer|location=Berlin|isbn=978-3-540-65410-0}}
*{{Cite book|last1=Gifford|first1=David|last2=Turbak|first2=Franklyn A.|last3=Sheldon|first3=Mark A.|title=Design Concepts in Programming Languages|year=2008|publisher=MIT Press|location=Cambridge, Mass|isbn=978-0-262-20175-9|chapter=16}}

===Overview papers===
* {{cite journal|first1=Flemming|last1=Nielson|first2=Hanne Riis|last2=Nielson|author2-link=Hanne Riis Nielson|title=Type and Effect Systems|journal=Correct System Design: Recent Insight and Advances|year=1999|pages=[https://archive.org/details/correctsystemdes0000stef/page/114 114&ndash;136]|publisher=Springer-Verlag|series=[[Lecture Notes in Computer Science]]|volume=1710|isbn=978-3-540-66624-0|url=https://archive.org/details/correctsystemdes0000stef/page/114|doi=10.1007/3-540-48092-7_6|url-access=registration}}

==Further reading==
*{{Cite book|last1=Marino|first1=Daniel|first2=Todd |last2=Millstein|title=Proceedings of the 4th international workshop on Types in language design and implementation |chapter=A generic type-and-effect system |date=2009 |publisher=[[Association for Computing Machinery|ACM]]|page=39|doi=10.1145/1481861.1481868|url=http://www.cs.ucla.edu/~todd/research/tldi09.pdf|isbn=9781605584201|citeseerx=10.1.1.157.8373|s2cid=14538045 }}
*{{Cite book|last1=Lucassen|first1=John M.|first2=David K. |last2=Gifford|title=Proceedings of the 15th ACM SIGPLAN-SIGACT symposium on Principles of programming languages - POPL '88 |chapter=Polymorphic effect systems |year=1988|publisher=[[Association for Computing Machinery|ACM]]|pages=47–57|doi=10.1145/73560.73564|url=https://scholar.google.com/scholar?cluster=4860658690557317521|isbn=978-0897912525|citeseerx=10.1.1.73.4916|s2cid=13015611 }}

{{DEFAULTSORT:Effect System}}
[[Category:Program analysis]]
[[Category:Type theory]]