Introduction

An Algebraic Effects System for Golang.

Fx.go is currently experimental.

API surface is very much in flux and evolving.

New effects will be added as they are discovered to be useful in the golang ecosystem.

How are Algebraic Effects useful?

Algebraic Effects are useful because they allow programs to be expressed not only in terms of what kind of value they can compute but also on what possible side-effects or external resources will such a computation require.

By using Effect Handlers, the interpretation of how an effect is performed is independent of the program description. This means that a single program description can be interpreted in different ways. For example, using a test-handler that mocks request to external services, or using a live-handler that actually performs such requests.

If you want to read more about different language implementations and theory behind effects, read the effects-bibliography.

Fx.go is inspired by the following two implementations, and uses a similar notion of the Handler, Ability, and Effect concepts:

Unison Abilities
Kyo (Scala3) - special thanks to @fbrasisil, Kyo's author who kindly provided a minimal kyo-core that helped me understand algebraic effect systems and inspired this library.

However, Fx.go has a different surface API since we are trying to provide the best dev-experience for Golang programmers.

Concepts Tour

This section will try to introduce you to the concepts of Effects, Abilities and Handlers as present in Fx.go.

No knowledge or previous experience with other effect sytems is expected. We will try to explain things by working out from simple concepts to more interesting ones.

Effects

An Effect ( Fx[S, V] read: V provided S ) is the description of a program that computes V, provided that the requirement S is present, so that the computation of V can be performed.

Since effects are descriptions of programs, they compute nothing nor produce side-effects until they are finally evaluated, once all their requirements are at met.

Some people also use the recipe analogy for effects: you first have a precise description of each step it takes to cook something, along with a list of the requirements for it (the ingredients and utencils you will use) and once you have them all, you can actually perform the recipe.

Abilities

In Fx[S, V], S is said to be the Ability (sometimes also referred as the set of Abilities, Capabilities, Effect Environment or Effect Requirements) that are needed for computing V.

Abilities describe the external resources that would be needed, as well as the side-effects that are possible while computing V.

Examples of such Abilities are:

network abilities (eg, performing http requests)
console abilities (eg, printing to the terminal or reading user input)
non-deterministic abilities (eg, generating random numbers or coin-flips)
resource handling (eg, disciplined acquire/use/release of shared/limited resources)
exception handling (eg, interruption/resumption and finalizers)
anything else that interacts with the world outside of the program.

Handlers

A Handler for the S ability is a particular interpretation of what S means.

Handlers are the only side-effectful portion of your programs. It is possible, and quite common, to have different handlers (interpretations) for the same Ability, and each Handler decides how/when to perform world-modifying side-effects.

For example, for an http-request ability you can have a test-handler that just mock responses to fixed values so that you can easily assert on known values on your tests. You could also have a live-handler that actually performs requests via the network for production runs.

Basic Effects on `Fx.go`

This section expands on Concepts and shows how they relate to the Fx.go API, as well as providing a basic intuition on Effect requirements and evaluation.

`Pure[V]`: Immediate Effects

The most basic of all possible effects are Immediate effects. These are effects of type Fx[Nil, V], meaning that they have no ability requirements (Nil) and evaluate to a value (V).

Immediate effects are created using the Pure(V) Fx[Nil, V] function.

As you can see, Pure(V) takes an existing value V, that means that a pure effect just holds an already known value instead of trying to compute it.

The value given to Pure can be retrieved by using Eval(Fx[Nil, V]) V. Only effects that have no requirements (Nil) can be evaluated.

import ( fx "github.com/vic/fx.go" )

func PureExample() {
    v := "Hello World"
    // Code annotated with types for clarity
    var effect fx.Fx[fx.Nil, string] = fx.Pure(v)
    var result string = fx.Eval(effect)
    assert(result == v)
}

`Fx[S, V]`: Pending effects

An effect Fx[S, V] where S != Nil is a pending effect that needs S to be provided for computing V.

The most basic pending computation is one you are already familiar with: A function.

In the following example, the function LengthOfString(string) int can be expressed as an Effect of type Fx[string, int]. Meaning that in order to have a value of int you need first to provide an string value:

func LengthOfString(s string) int {
    return len(s)
}

func FuncExample() {
    // Code annotated with types for clarity
    var effect fx.Fx[string, int] = fx.Func(LengthOfString)
    var requirement string = "Hello World"
    var provided fx.Fx[fx.Nil, int] = fx.Provide(effect, requirement)
    var result int = fx.Eval(provided)
    assert(result == len(requirement))
}

From the code above:

Func(func (S) V) produces a pending effect of type Fx[S, V].
Provide(Fx[S, V], S) discharges the S requirement and returns Fx[Nil, V].
Note that no computation is performed in this step. Fx[Nil, V] is still a description of a program, and V has not been computed yet, nor any side-effect has been performed.
Eval(Fx[Nil, V]) will actually perform the computation of V. Since all non-Nil requirements have already been provided, the computation can be run.

These two are the most basic effects in Fx.go. More interesting effects will be presented as we explore the topics of effect Rquests and Handlers.

Effect Requirements

So far, we have seen that an effect Fx[S, V] can have S be Nil for effects that can be evaluated right away and non-Nil for those pending effects that still need to be provided some value.

In this chapter we will talk about aggregating requirements using the And type. And how different types of functions/effects can represent the very same computation. We also look at similarities with higher-order functions in functional-programming and how rotating or re-arranging effect requirements is indifferent in Fx.go. Finally, we show some theAnd* and Provide* combinators that can help you reshape your effect requirements.

Composite requirements

Using the same "length of string" function from the previous chapters, we can describe it in different ways.

// This is an strange way of writing `func(string) int`.
// But this shape can help to understand the types bellow.
//
// Focus your attention on the requirements that are
// needed for a computing a value.
//
// In particular, note that `Fx[Nil, V]` is like a `func() V`
func LengthOfString(s string) func() int {
    return func() int { return len(s) }
}

// The type of LengthOfString expressed as an effect request.
type LenFn = func(string) Fx[Nil, int]

Note that all of the following types are equivalent, as they describe the very same requirements and result types:

func(string) int
Fx[string, int]
func(string) func() int
func(string) Fx[Nil, int]
Fx[string, Fx[Nil, int]]
Fx[And[string, Nil], int]
Fx[And[Nil, string], int]

The last three examples represent nested effects and are equivalent to functions of arity > 1 or functions that return functions.

And[A, B] is the requirement for both A and B abilities. Notice in the last two examples, that their components are swapped. It is important to note that in Fx.go, the order of the abilities on And requirements does not matter and they can be freely swapped/joined/unjoined. More on this when we talk about And* combinators.

Also, note that And[A, Nil] is equivalent to just A. All of these types represent the same type of computation and an effect can be transformed to any of those types freely.

`>1` arity functions as effects.

Suppose you have a function that multiplies an string length by n.

func MulLen(s string, n int) int {
    return len(s) * n
}

MulLen can be described by the following types:

func(string, int) int
func(string) func(int) int
Fx[And[string, int], int]
Fx[string, Fx[int, int]]
Fx[int, Fx[string, int]]
Fx[And[int, string], int]

Note that And[X, X] is equivalent to just a single X requirement, and that And[And[X, Y], And[Y, X]] is also equivalent to And[X, Y].

Shuffling `And`ed requirements.

An important thing to note is that in Fx.go, requirements are identified by their type and not by name or position as in regular functions.

Effect requirements can be freely re-arranged with no impact in the meaning of the program.

`And*` combinators.

There are some functions (more will be added as they are found useful) that help you re-arrange Anded effect requirements.

Shuffling And requirements is useful because you might want to provide some requirements first than others even if they are not in the head position of the requirement list.

// Since `And[A, A]` is equivalent to just `A`.
// Used to collapse Nil requirements just before evaluation.
func AndCollapse(Fx[And[A, A], V]) Fx[A, V]

// Ands S with Nil in the effect requirements
func AndNil(Fx[S, V]) Fx[And[S, Nil], V]

// Swaps A and B. Note: this has no impact on how computation is
// performed, since requirements can be freely re-arranged.
func AndSwap(Fx[And[A, B], V]) Fx[And[B, A], V]


// FlatMaps the inner effect into the outer by 
// Anding their requirements.
func AndJoin(Fx[A, Fx[B, V]]) Fx[And[A, B], V]

// Reverse of Join
func AndDisjoin(Fx[And[A, B], V]) Fx[A, Fx[B, V]]

Providing Requirements

Effect requirements can be provided in any order with no impact in the evaluation of the program.

`Provide*` Combinators.

These functions are used to eliminate requirements from effects. Only when Nil is the only remaining requirement, the effect can be evaluated.

The result of provide functions will always be another effect, meaning that no computation has been performed yet, nor any side-effect produced. The result is just another effect but with less requirements.

// Discharges the single S requirement.
func Provide(Fx[S, V], S) Fx[Nil, V]


// Discharges the requirement of A by providing it.
func ProvideLeft(Fx[And[A, B], V], A) Fx[B, V]

// Discharges the requirement of B by providing it.
func ProvideRight(Fx[And[A, B], V], B) Fx[A, V]

// Discharges both A and B
func ProvideBoth(Fx[And[A, B], V], A, B) Fx[Nil, V]



// Provides A, the first part of the left And.
func ProvideFirstLeft(Fx[And[And[A, C], And[B, D]], V], A) Fx[And[C, And[B, D]], V]

// Provides B, the first part of the right And.
func ProvideFirstRight(Fx[And[And[A, C], And[B, D]], V], B) Fx[And[And[A, C], D], V]

// Provides A and B, the first part of both Ands.
func ProvideFirsts(Fx[And[And[A, C], And[B, D]], V], A, B) Fx[And[C, D], V]

Context Requirements

The Ctx[V]() Fx[V, V] function creates an effect that requires some value V as part of the environment and evaluates to V.

It can be used to request the presence of some services (interfaces or collections of methods that produce related effects) or more generally, an evidence that a value V is part of the environment.

In the following example we simply map over an string to compute its length.

var eff Fx[string, int] = Map(Ctx[string](), LengthOfString)
var result int = Eval(Provide(eff, "hello"))
assert(result == len("hello"))

Calling the Const[S](V) Fx[S, V] is like maping a context over a constant function. As you might have guessed, Pure is defined in terms of Const.

var a Fx[string, int] = Map(Ctx[string](), func(_ string) int { return 42 })
var b Fx[string, int] = Const[string](42)

var c Fx[Nil, int] = Pure(22)
var d Fx[Nil, int] = Const[Nil](22)

Functional Requirements

As we have seen in the previous Context chapter, you can ask for any type to be part of an effect's environment.

You can also ask for functions of some type to be present and use them in your program descriptions without knowing their exact implementation.

For example, suppose we ask for a function that takes an integer. And then apply it to a value.

// The type of the function from int to int
type OnInt func(int) nit

// Apply OnInt(12)
var a Fx[OnInt, int] = Map(Ctx[OnInt](), func(f OnInt) int {
    return f(12)
})

// fx.Apply is just an abbreviation of the previous code:
// It takes the type of a unary function and the value to apply.
var b Fx[OnInt, int] = Apply[OnInt](12)

Because OnInt is part of the environment, we only know its signature (its request and response type), but not the actual implementation of it. This way, different implementations of OnInt can be provided later.

Now, suppose you have the following code:

type HttpRq string
var url = HttpRq("https://example.org")

// `Http` is the type of an *effect request* function.
// it takes a plain value and creates an effect.
type Http func(HttpRq) Fx[HttpService, HttpRs]

// NOTE: applying to Http, creates a nested effect
var a Fx[Http, Fx[HttpService, HttpRs]] = Apply[Http](url)

// Flatenning creates an Anded environment.
var b Fx[And[Http, HttpService], HttpRs] = AndJoin(a)


// Same as previous two lines:
var x Fx[And[Http, HttpService], HttpRs] = Suspend[Http](url)

fx.Suspend is an abbreviation of AndJoin(Apply[Http](url)) for effect requests (functions returning an effect)

This is the principle behind suspended effect application in Fx.go and is a fundamental part when we talk about effect Requests and Handlers.

Effect Requests

Another way of creating effects in Fx.go is via an effect-request function.

A function of type func(I) Fx[S, O] is said to take an effect-request I and produce an suspended effect Fx[S, O].

An example, is the function func(HttpReq) Fx[HttpService, HttpRes] we saw in the previous chapter.

Using the "length of string" example of the previous chapters, we can use it to model an effect request:

type LenFn = func(string) fx.Fx[fx.Nil, int]

// Code is type annotated for clarity
var lenFx fx.Fx[fx.And[LenFn, fx.Nil], int] = fx.Suspend[LenFn]("hello")

Note that Suspend takes the type of a request-effect function and the request value for it. And yields a suspended effect of type Fx[And[LenFn, Nil], int]. The computation is said to be suspended because it knows not what particular implementation of LenFn should be used, and because of this, LenFn is part of the requirements, along with Nil the ability requirement on the result of LenFn.

Different implementations of LenFn can be provided to the lenFx effect.

var lies LenFn = func(_ string) fx.Fx[fx.Nil, int] {
    return fx.Pure(42)
}
var truth LenFn = func(s string) fx.Fx[fx.Nil, int] {
    return fx.Pure(len(s))
}

var x int = fx.Eval(fx.ProvideLeft(lenFx, lies))
assert(x == 42)

var y int = fx.Eval(fx.ProvideLeft(lenFx, truth))
assert(y == 5)

Notice that by delaying which implementation of LenFn is used, the lenFx program description includes the effect request "hello" and knows the general form of its response Fx[Nil, int], but knows nothing about which particular interpretation of LenFn will be used.

Handlers

A Handler is an effect transformation function of type func(Fx[R, U]) Fx[S, V].

Handlers are free to change the effect requirements, they tipically reduce the requirement set, but they could also introduce new requirements. They can also change or keep the result type.

Handling an effect

Lets re-write our previous "length of string" function as a Handler.

type LenFn func(string) Fx[Nil, int]

// Code is type annotated for clarity
var lenFx Fx[And[LenFn, Nil], int] = fx.Suspend[LenFn]("hello")

// type of a handler. not needed but added for clarity.
type LenHn func(Fx[And[LenFn, Nil], int]) Fx[Nil, int]

var handler LenHn = fx.Handler(func(s string) fx.Fx[fx.Nil, int] {
    return fx.Pure(len(s))
})

// apply the handler directly to lenFx
var x *int = fx.Eval(handler(lenFx))
assert(*x == 5)

As you might guess, fx.Handler is just a wrapper for ProvideLeft(Fx[And[Fn, S], O], Fn) Fx[S, O] where Fn = func(I) Fx[S, O], an request-effect function.

Requesting Handlers (effect-transformers) from the environment.

Of course, you can also request that a particular effect transformer (Handler) be present as a requirement of some computation. This way the handler is provided only once but can be applied anywhere it is needed inside the program.

// Same examples as above with some more types for clarity

// effect-request function type.
type LenFn func(string) Fx[Nil, int]
// effect handler type
type LenHn = func(Fx[And[LenFn, Nil], int]) Fx[Nil, int]

// effect ability
type LenAb = And[LenHn, Nil]
// effect type producing V
type LenFx[V any] = fx.Fx[LenAb, V]

// Same as: Suspend[LenHn](Suspend[LenFn](input))
var lenFx LenFx = fx.Handle[LenHn]("hello")

var handler LenHn = fx.Handler(func(s string) fx.Fx[fx.Nil, int] {
    return fx.Pure(len(s))
})

// Now instead of applying the handler directly to each effect
// we provide it into the environment.
var provided Fx[Nil, int] = fx.ProvideLeft(lenFx, handler)
val x int = fx.Eval(provided)
assert(x == 5)

Example HTTP Req/Res program

As an example of the concepts we have seen so far, lets write a program that needs to perform an HTTP Request, expects an HTTP response from the webservice it accesses and then perform some logic on that response.

On an effect system like Fx.go, we do not directly contact external services, we just express our need to perform such requests and we expect a Handler to actually decide how and when such request should be performed (if any).

package http_example

// Notice we do not import any HTTP library, just effects.
import (
	"testing"
	fx "github.com/vic/fx.go"
)

// For simplicity our request is just an string: An URL.
type HttpRq string

// For simplicity out response is just an string: The response body.
type HttpRs string

// Type of the effect-request function. 
// This will be implemented by some handler to provide actual responses.
//
// fx.Nil in the result type indicates that our Http ability does
// not requires any other ability.
type HttpFn func(HttpRq) fx.Fx[fx.Nil, HttpRs]

// Type of the Http Handler that discharges effect requirements
type HttpHn = func(fx.Fx[fx.And[HttpFn, fx.Nil], HttpRs]) fx.Fx[fx.Nil, HttpRs]

// Type of the Http Ability: the handler and aditional abilities.
type HttpAb = fx.And[HttpHn, fx.Nil]

// An http effect that produces V
type HttpFx[V any] = fx.Fx[HttpAb, V]

// An effect of HTTP GET requests.
func Get(url HttpRq) HttpFx[HttpRs] {
	return fx.Handle[HttpHn](url)
}

// A program that computes the respose length of https://example.org
func Program() HttpFx[int] {
	return fx.Map(Get("https://example.org"), func(r HttpRs) int {
		return len(r)
	})
}

func TestProgram(t *testing.T) {
	var httpHandler HttpHn = fx.Handler(func(r HttpRq) fx.Fx[fx.Nil, HttpRs] {
		mock := HttpRs("example")
		return fx.Pure(&mock)
	})
	var provided fx.Fx[fx.Nil, int] = fx.ProvideLeft(Program(), httpHandler)
	var result int = fx.Eval(provided)
	if result != len("example") {
		t.Errorf("Unexpected result %v", result)
	}
}

Core Effects

The list of effects provided by Fx.go will increase as we see the need for them and as long as they provide useful on Golang programs.

Current Ideas for contributions:

Resource management (reserve/use/release shared resources)
Structured concurrency (instead of manually using mutex/channels)
any other idea you find useful, Issues and PRs are welcome!

Reader/Writer

A Reader[T] allows to read values of type T from the environment while Writer[T] allows to set them.

Implementation
- read.go
- write.go
Tests rw_test.go

Read and Write Handlers take an effectful operation that can modify the external world. See TestReadWrite.

Abort

Abort[V, E](E) aborts a computation of V with E.

When aborted, a computation is halted, meaning that any Map or FlatMap operation over it will not be executed.

The AbortHandler replaces aborted effects (those computations where Abort was called) with a Result with E. Otherwise if the effect was never aborted, a Result with V is returned.

Implementation
- abort.go
- result.go
Tests abort_test.go

Contributing

Yes, please. All PRs are welcome, documentation, code improvements, ideas or suggestions, ways to improve this book prose, etc.