Effects

Effects are restricted Monads consisting of a set of abstract operations that can be bound to concrete handlers. Functions that use operations of an effect must be executed in the context of a handler that implements these operations. Leijen gives a nice introduction on Effects in Koka.

An operation of an effect may perform arbitrary computations. Additionally, it may resume execution or return, which effectively aborts the code that called this operation. An operation may resume execution repeatedly which results in the code calling the operation executing repeatedly with possibly different results from the operation. In this case, the handler has to accumulate the result in some way before it can return.

Effect Purposes

Effects provide a way to encapsulate and document side-effects of code. This allows code to be pure with the exception of operations performed by effects. This results in a clear documentation of the side effects of an operation.

When effects are part of a function's signature the caller clearly knows what effects a call might have and tools can verify that the code does not have any other effects but these.

Furthermore, effects allow a caller to provide specific implementations of effects. E.g., code providing encrypted communication channels typically requires a source of random numbers (How I Hacked Hacker News (with arc security advisory)). Instead of hard-wiring an encryption library to some implementation of random numbers, the library should specify that it depends on an effect random and the caller must ensure that the code is executed in an environment that provides random numbers of sufficient quality, which might be provided by specific OS functions or specialized hardware.

Effects and Feature Redefinition

A famous example for the introduction of surprising side-effects in a supposedly pure function is Java's implementation of hashCode() for java.net.URL, which causes DNS name resolution. The problem here is that a function like Object.hashCode() is expected to be pure, while the implementation in URL is not.

One solution would be to disallow any new side-effects in a redefinition, such that in the Java case, URL.hashCode would not be allowed to perform any network operation. However, this would be very restrictive, it would e.g., make it impossible to add debugging output or logging into any redefinition of hashCode without changing the signature of the original function.

A solution for higher-order functions is Effect Polymorphism as used by the Effekt Language. We might find a way to equip redefinitions with some sort of effect polymorphism.

Effect polymorphism would require annotation of functions with effects and the verification of these annotations by language processing tools like compilers. If these tools are required anyway, they could just as well produce the annotations automatically and verify that code requiring an effect is only executed in contexts that provide an implementation for this effect. Furthermore, tools could provide information on all the effects required by a given application, presenting side-effects to the user. A safety-analysis of an application would then include an analysis of these side-effects.

For library code, it seems to be reasonable to require annotations for all directly used effects in the library, excluding effects introduced by higher-order functions or redefinitions.

Effects in other languages

Koka

Koka has effects built-in, supporting multiple resumes. Some syntax sugar (with) to install handlers and to declare tail-resumptive operations.

// a generator effect with one operation
effect yield<a>
  fun yield( x : a ) : ()

// traverse a list and yield the elements
fun traverse( xs : list<a> ) : yield<a> ()
  match xs
    Cons(x,xx) -> { yield(x); traverse(xx) }
    Nil        -> ()

// bind the yield operation dynamically
pub fun main() : console ()
  with fun yield( i : int)
    println("yielded " ++ i.show)
  [1,2,3].traverse

Flix

Similar to Koka, effects in Flix are part of function results. But functions can be polymorphic in their effect:

/// Assume we have some pure and impure functions:
def inc1(x: Int32): Int32 & Pure = x + 1
def inc2(x: Int32): Int32 & Impure = println("Hello"); x + 1

/// We can write functions that expect pure or impure functions:
def twice1(f: Int32 -> Int32 & Pure, x: Int32): Int32 & Pure = f(f(x))
def twice2(f: Int32 -> Int32 & Impure, x: Int32): Int32 & Impure = f(f(x))

/// But we can also write *effect polymorphic* functions:
def twice3(f: Int32 -> Int32 & ef, x: Int32): Int32 & ef = f(f(x))

/// We can use `twice3` with both pure and impure functions:
def main(_args: Array[String]): Int32 & Impure =
    (twice3(inc1, 0) + twice3(inc2, 0)) |> println;
    0 // exit code

Effects in Fuzion

In Fuzion, the standard library feature effect is a specific oneway_monad that can be used to define the abstract operations of an effect.

Basic notation

Here is an example of the definition of a generator effect gen T that provides an operation yield:

gen (T type, yield T->unit,    # yield is called by code to yield values
        code ()->unit     # code is executed with this effect installed
       ) : effect is

gen receives two arguments, a function that implements yield and the code the effect is run on. gen inherits from the library feature effect which installs the instance and executes code. code can use the effect's operations.

Unlike Koka or Flix, the lookup of operations is not implicit, but we need to explicitly qualify calling an operation by the effect. An expression t.env is used to access the innermost effect handler installed for a type t. As an example, code that yields a value if type i32 looks like this

  (gen i32).env.yield 42

A function that yields three integers 0, 8, 15 may look like this

  threeInts =>
    (gen i32).env.yield 0
    (gen i32).env.yield 8
    (gen i32).env.yield 15

Before calling this function, we have to create an instance of gen i32 and perform the call within the code of that instance. The following example provides a function for yield that prints the yielded values:

# bind the yield operation dynamically
(gen i32) (i -> say "yielded $i") ()->
  threeInts

Example: yield

Here is a small example creating coroutines that communicate via a generator effect that defines an operation yield:

Using the same example with different sources that yield values to different sinks:

Returning from operations

Here is an example how Fuzion can return early from an effect by calling abort in an operation instead of returning normally.

Exception handling

Fuzion's standard library provides an effect called try that permits raising an error as exception to stop code execution immediately. Here is a small example using a feature check_password that may cause early terminations by raising an exception:

One convenience routine try_or_panic handles the exception by terminating the program using panic, shown by this example:

Multiple resumption

Multiple resumption seems to be a special case with little practical value that is very hard to implement. Consequently, Fuzion supports only operations that are either tail-resumptive or that return directly.