Algebraic Effects

This is my second attempt to start a conversation about this feature. My first attempt might have failed because of a rather missleading title that I chose in order to get some attention:

Algebraic effects are among the most interesting features that in a couple of years everybody might be talking about. You can already get a glimpse of what is coming here:

https://www.eff-lang.org/

or if you prefer to watch:



For those of you who want to read it here: what are algebraic effects and how might Swift benefit from them?

Very generally speaking, algebraic effects are a special kind of annotation. They typically appear inside function declaration, but it is straightforward to generalize them so that they can annotate arbitrary variables in your code. However, unlike property wrappers, you would need some different annotation to read those variables or call those functions and you will need some special execution context.

Concrete example: Suppose, you write a function that does something random. As a good functional programmer, you know that nobody will read your documentation and people may even ignore the word "random" in the name of your function. So how can you make sure people are aware of the randomness "side effect" of your function? Answer: by having a "random effect" in the type signature of your function:

func getRandomVector(length: Int) random -> [Double]{
(0..<length).map{_ in getrandom Double.self}
}

This function cannot be called by accident without the programmer noticing. Inside the function, you will notice the new getrandom "keyword". This indicates the use of some primitive code for the randomness effect, similar to the "throw" keyword inside throwing closures (that are called with try).

Just like with throws and try, there are only two ways you can call a random function: 1. inside another function annotated with random or 2. via special language constructs that allow you to convert a random function into a non-random function; these language constructs may require you to provide additional context like, e.g., a random generator.

In case 1, you will have to add another annotation, to make the randomness explicit:

func callsRandomVector(length: Int) random -> Double{
let randomVector = flip getRandomVector(length: length)
return randomVector.reduce(0,+)
}

Case 2 may be solved with a do-catch block:

func unsafeRandomCaller(){

do{
let randomVector = flip getRandomVector(length: 42)
doSomething(randomVector)
}
catch {continuation : (RandomGeneratorProtocol) -> Void  in
continuation(UsualRandomGenerator())
}

}

In the above scenario, it will of course be necessary that the catch block is aware of all random effects that happen. For test purposes, you may want to override the randomness and actually provide some concrete value, so the catch blocks need to provide you with a continuation of the correct random generator type for each such event.

A different solution to the do-catch block may be a special function:

func unsafeRandomCaller(){

runRandom(RandomGenerator()){
doSomething(flip getRandomVector(length: 42))
}

}

This may look a bit more natural, however it is a bit tricky to get the types right.

Another example: Say, your function reads some more or less global information. However, this information is dependent on the app's configuration which is only available at runtime. So, you need to make absolutely sure the information has been loaded before you actually run this function. This also means that nobody thinks they can use this function to provide the information, i.e., the direction of dependency needs to be absolutely clear.

The solution is the dependency effect:

func solveHaltingProblem(goedelNumber: Int, input: Int) depends -> Bool{
let oracle = require Oracle.self //require being the primitive keyword for the dependency effect
return oracle.willProgrammStop(onInput: input, programmCode: goedelNumber)
}

(Note that whichever environment you tried to provide in above example, the code would still be semantically incorrect - unless you find a way to do computations well beyond what Turing machines are capable of).

In a way, this is just a generalization of the randomness effect. Having both of the above effects around may however be useful if you like self-documenting code. Like in the random example, you will need a third keyword, e.g. read, to call non-primitive depends functions.

Another example: Say, you have a function manipulating a more or less global state. You know already your colleagues will hate you for this, as manipulating global state is generally frowned upon. But if we're honest for a moment, any useful program will have some kind of global state and all history of design patterns is just about making global state changes explicit so we don't shoot ourselves in the foot all the time.

Enter the state effect:

func setGlobalVariable(newValue: Int) mutatessharedstate {
mutate SharedState.myVariable = newValue
}

Note that, if you want to actually run this function, you have to inject a shared mutable state variable explicitly. That way, you control how global the access will be in reality. You may decide to run multiple functions in parallel that all try to mutate the "global" state, but really you give each of them their own copy.

Fourth example: Say, a function accesses some streams of events. For example, you wrote some long running process that asynchronously emits log data and eventually the message "I'm done". When the process is done, you want to start some other process using the result data.

This may be orchestrated by an observable effect:

//ProcessEvent and FinalResult would be custom types 
func orchestrateProcesses() emits -> ProcessEvent<FinalResult> {

let messageStream = observe longProcess1()

switch messageStream{
case logMessage(let log):
return .logMessage(log)
case result(let result): //intermediate result 
return observe longProcess2(input: result)
}

}

The above code can be easily understood by reading it from the top to the bottom - or from the bottom to the top. It's just a sequential computation - however, there's a catch. The code will not just run once, but many times! With the observe keyword, we are actually registering an observer on longProcess1, and longProcess1 may actually "return" multiple times. This could for instance be solved with a third keyword:

func longProcess1() emits -> ProcessState<IntermediateResult>{

for _ in 0..<100{
emit .logMessage("Not done yet...")
sleep(1)
}

return .result(...)

}

In the case of this effect, emitting and returning may actually be used interchangably, except that return still has to appear exactly once on each code path (unless we have a void function). Also, the emitted values must agree with the type signature of the function.

Note you can also have a simpler version of the above that will return only once. That version would be more suitable to create function-like code that looks like normal synchronous code but can run asynchronously without ever blocking.

One last example: Say, you are modelling a process that has checkpoints. On each checkpoint, some outside code will decide if and to proceed with the task or not. This may look like this:

func divide(_ lhs: Int, by rhs: Int) guided -> Int{
guard rhs != 0 else{
let defaultValue : Int = help DivisionByZero()
return defaultValue
}
return lhs/rhs
}

DivisionByZero is a type conforming to some protocol that can be handled by guided functions. A non-guided calling function may then feature code like this:

do{
let divisor : Int = help GetSomeInt(suitableFor: "division")
let number = guide divide(1337, by: 0)
return "\(number)"
}
catch{(continuation: (((GetSomeInt) -> Int), (DivisionByZero) -> Int) -> String) in 
return "Nope, not gonna touch this."
}

I would love if Swift had some way for developers to introduce custom effects - in addition to having some more built-in effects (like the already existing throws).

At this point, let me admit something: The above ideas are probably inconsistent with each other. I don't have a detailed design yet how exactly the rules would be in Swift for custom effects, and I'm not exactly an expert on algebraic effects. I just wanted to make you as curious as I am and spark a discussion about that topic.

Here are some thoughts on what problems those effects solve and what they have in common. There are lots and lots of problems that can be solved with these effects. The above examples show that they all provide the following benefits:

  1. They introduce some special logic that depends on outside information.
  2. They hide a whole lot of complexity and boilerplate.
  3. They make inversion of control (and therefore testing) super handy and easy.
  4. They look way better than the prominent alternative from functional programming (see below) that you can already use in Swift.

For an effect to make intuitive sense, they need to obey some rules:

  1. As long as all your variables are immutable, it must not make a difference if you read your code from the top to the bottom or from the bottom to the top.
  2. Functions that don't use the effect must retain their meaning when called inside a function using the effect. In particular, chaining functions must work the same way inside effectful functions as ot does outside (the compiler will try to call as many chained "pure" functions as possible, but sometimes it might be necessary to "map" them to an effectful function).
  3. func foo() someeffect -> Int{42} must do the same thing as func foo() someeffect -> Int{runeffect 42} (the compiler will warn you that no call actually uses your effect - and when running with optimizations, the compiler means it [whenever it can]).

The above rules roughly constitute what is called a "Monad" (the aforementioned functional alternative). It is well known that in order to properly represent a monad protocol (which may help to implement the syntax feature proposed here), Swift's type system needs to be extended quite a bit. However, you can already see a lot of monads in action in today's Swift: Optional, Result, Array and Promise are just some.

This time, I want to mention two alternatives in the original post before it is brought up in the discussion: Other languages have other designs to make monads "look good", i.e. look like usual imperative code. There is Haskell's do-notation and there are languages that solved the problem with for-comprehensions.

On the plus side, this is just one syntactical concept that you have to keep in mind, whereas with custom keywords, you have to learn a lot more. However, this is a one-size-fits-all approach. Those notations don't really make sense for each and every monad. Also, the custom syntax version to some extent bypasses the need of monad transformers.

It has been speculated that the availability of custom keywords may lead to a proliferation of them. However, with the do notation and the for comprehensions, we would still need to learn the names of certain monads if they proliferate. The overhead of learning 3 keywords instead of 1 class name is O(1), and if custom syntax makes monads a more shiny tool that is in wider use, I would welcome this very much. It is the community's responsibility to filter out less useful applications - but by popularizing this useful tool from functional programming, we may actually find additional useful examples that we hadn't thought of before.

I am looking forward to the discussion.

4 Likes

I don't understand you want to advise. A Monad modal extension to swift or a new programming paradigm with swift?

I don't think Swift is a functional language or never would be in the future. Otherwise, combine other minority languages feature/concept into swift probably not a suitable way. Different lang fits different problems or domains, as a general purpose imperative language, Swift has its own application domain and industry position; NOT an almighty lang toy with all mixed/borrowed conceptions from other langs.

guided emit observe mutate all new keywords would incur potential compatibility problems, and the compatibility rule is a very high bar and so hard to break for now.

Maybe we can explore Algebraic Effects for some funny research but not engineering goal/target.

2 Likes

I'm not sure I totally understand this feature - but are random, flip, emit, guided etc new keywords, or user-definable attributes? I assumed it was the latter! My understanding so far is that this is sort of like protocols in reverse, in that a callee can specify that the caller satisfies certain constraints - e.g anyone who wants to call a random method must explicitly flip, and then either become random themselves, or contain or resolve the effect if they want to stop the random-ness from leaking out, via a continuation or something similar.

Your examples are great but are missing some code that would make it fully click for me. If for example the non-random method in Case 2 needed to return an Int, what would the code look like?

@Anachron I'm very interested in algebraic effects and effect systems in general, but found the original post very hard to read with no indentation in code examples and some lines requiring horizontal scrolling. Would it be possible to update those code snippets for readability? Thanks!

11 Likes

On an initial thought, I'm afraid it might cause code to be plagued with do-catch blocks everywhere.

I thought Swift's end goal was "total world domination"?

1 Like

Algebraic effects are not a special kind of annotation as much as a different way of structuring programs and (if we get them) will have strong rippling effects throughout both the toolchain and language, including (but not limited to) the type checker, code generation, runtime, LLDB, ABI, library evolution and the entire Swift ecosystem. It's not obvious how algebraic effects can be properly integrated with Swift's default memory management strategy of reference counting without leaking memory all over the place, and whether they can be reconciled with having zero-overhead interop with C-like languages for systems programming. It is also not clear how algebraic effects can be integrated with move-only types, which is a feature a lot of people are interested in.

By focusing almost exclusively on the surface syntax in such a long post, I think you're seriously underestimating (or worse, ignoring) the complexities and challenges involved in implementing and adopting algebraic effects. :slightly_frowning_face:

2 Likes

And yet, Swift was designed as exactly that:

Screenshot 2020-07-26 at 19.43.10

And it worked pretty well so far. It's an imperative language compatible with Objective-C and UIKit/AppKit (on Apple platforms), but also allows declarative and functional programming to fully support SwiftUI and Combine/FRP. Its enum and struct types heavily resemble algebraic data types in Haskell, while protocols are much more similar to Haskell type classes than Objective-C protocols that preceded them. Swift generics are more inspired by parametric polymorphism in functional programming languages than templates in C++. Immutable value types make writing pure functions much easier and from some perspective could be considered a "syntax sugar" to what you get with a State monad in monadic programming. Whether consciously or not, Swift did borrow heavily from other "minority" languages and tremendously benefited from it. I'm not even talking about differentiable programming coming to future Swift versions, which arguably is more niche than functional programming at the moment.

Adaptability and flexibility is one of the best features of Swift in my opinion, and it allowed us to more or less seamlessly transition from the existing imperative Objective-C frameworks to declarative and functional SwiftUI and Combine. This is great, and I hope that Swift doesn't stagnate, but we have to pay attention to where the puck is going to stay relevant.

4 Likes

I think that controlled mutation in Swift improves the maintainability of our programs, and controlled effects would improve their maintainability further. Interestingly, controlled mutation in Swift can be seen as a “baby version” of controlled effects. Perhaps they share the same design space?

Fun fact: Sometimes I imagine the future programmers looking at our programming languages in disbelief: “Wait, you could launch missiles from a computed property with no type-level disclosure?” This is similar to how we look at the old operating systems: “Wait, you could change the memory of other processes?”

2 Likes

They totally are, mutating state is just an effect of a given computation on "the outside world". Haskell relies on monads, monad transformers and do-notation to fit this in its advanced type system. We could also see something similar emerging in SwiftUI with property wrappers, where @State is a state effect local to a specific View (State monad), @Environment is a reader effect (Reader monad), @ObservableObject, @StateObject and @EnvironmentObject give access to non-local state (more similar to the IO monad in their unrestricted power).

Property wrappers are obviously ad-hoc instruments here, and to make them work properly there's a fair bit of infrustructure needed that SwiftUI itself provides, which makes them limited just to SwiftUI use cases. We need something more general, and at least thinking about these things in terms of "effects" does help to formulate the problem in a better way.

1 Like

I agree. Swift's ability to apply many different programming paradigms with concise and well-defined semantics is part of what makes it so powerful.

Algebraic effects looks to be an interesting proposal to the language, and fills a niche that is not already filled by protocols, generics, or opaque return types. It actually seems to me like it would fit rather well.

Maybe someone could cook up what an ideal states of that structure would look like possibly with some ad-hoc syntaxes. It's tricky to follow the discussion and agree with the utility of effects in a language that doesn't require pure function to begin with. Some example of usage would be nice.

1 Like

We probably should circle back to the actual problem being solved before focusing on language features. And let's evaluate the current landscape first:

  1. There's a consensus that pure functions are great for composability and testability.
  2. Mutable value types (but not reference types!) allow having internal state even in pure functions without worrying about global state (let's call it a var effect).
  3. When you do need to modify something outside of the pure function call, inout is semantically equivalent to a value being returned (not true for reference types).
  4. The only other effect that impacts the control flow available to us currently is throw. Important to note that this is a typed effect that requires every such function to be marked with the throws attribute.

There are a few more effect types that are actively being researched with pitches flying around:

  1. Generators, to describe a computation being suspended. yield in modify accessors is the first step towards that, in more advanced cases we could see functions with multiple yield statements within them. Let's also chuck basic coroutines into the same bucket to simplify things for now. I don't see a clear consensus forming there, neither in terms of terminology, nor from the implementation perspective. Almost every language does it slightly differently, and the fact that the first approach to this in Swift is done only within modify accessors means that there's a lot here to explore.
  2. async/await, which is semantically very close to coroutines, but in most languages we can see some consensus forming that this is a typed effect with an async "marker" (or lack of it) describing the effect "flavor" of the function. In terms of syntax there are many parallels here with how error throwing is done in Swift. It also raises interesting questions whether these two effects can be mixed and how? Also, would it make sense for these to be mixed with generators? JavaScript toyed around with async generators, but seems like the proposal was abandoned. As a whole it would be interesting and useful concept, any Combine publisher is an async generator if you squint. Describing new publishers in a single function instead of creating a separate type could be quite useful in theory. I'm also not touching on multi-threading here as this is clearly orthogonal to concurrency.

All of these are quite useful in day-to-day programming experience, but we already see that there at least three types of effects that need special syntax (we're not touching the var effect here as it's so basic and low level that in my opinion the existence of "special syntax" for it is hardly debatable). Throwing functions require throws, asynchronous functions require async, what about generators? If one were able to write a throwing Combine publisher in a single function, would that be a throws async generator function? With effects multiplying and us wanting to keep track of them, we quickly run out of keywords even with these broadly applicable situations.

There are more interesting effects one would want to describe, Eff tutorial page gives some great examples:

  1. Extensible and testable logging (or any IO for that matter), where log/print calls are essentially effects, but with customizable effect handlers you can intercept the output and do what you want with it (ignore, redirect, analyze etc).
  2. Recoverable errors. Imagine a throwing function that could proceed from the same place it threw an error from if its error handler decided that the error is recoverable.
  3. Non-determinism and probability, which are useful in testing and simulations.
  4. Different multi-threading and multi-processing models.

The unifying theme in all these effects is that they all describe they way how computation is performed, but not how it's described. One would want to keep the basic language affordances without a need to learn new keywords for each effect, and the important question of how these can be mixed and matched should be answered too.

I personally don't think that we should explore the new hot algebraic stuff untill we examine in details the lessons learned from monadic programming in languages that make these things easier to use. In those the "flavor" of each effect is described by the type of the monad, while the way you work with them stays the same, and the effects themselves can be mixed with each other through monad transformers (if any are available for these specific monad types.

I already voiced my support for do-notation support previously on these forums, and I think that making that work is much easier and less disruptive than any of the more specialized effect systems that are being explored at the moment. It has become a de-facto standard for expressing effects in purely functional programming languages over the last few decades, starting with Haskell, and then appearing in PureScript, Agda and Idris. PureScript had an interesting approach with extensible records, but seems like that was abandoned a couple of years ago.

As @Varun_Gandhi writtes above there's a big implementation question here. Any proposal that introduces new semantic should also be clear about the performance and implementation cost. That's why I think that something like do-notation could work better as it's more about syntax sugar than any new semantic.

3 Likes

That's true, but we have to keep in mind that the absence of the pure functions requirement doesn't prevent us from expressing some of these effects. Consider throws or async, we could have used Result everywhere we use throw and catch, and abandon the need for async/await and stick to Future and flatMap (or even plain callbacks). But seems like there's a broad agreement that these features make life easier for us, even without a requirement for pure functions to be used everywhere.

What makes effect systems alluring is that there are more types of interesting effects and that one would need some more general syntax to express them conveniently. And these are effects we already describe and use in our code, we just don't think of them in those categories, similarly where one doesn't think of protocols and generics in a dynamically typed language.

Btw https://overreacted.io/algebraic-effects-for-the-rest-of-us/ This article is quite ok to get the idea. IMHO the biggest challenge for Swift will be the type system. Second probably easier to tackle is “resume”. But the concept of algebraic effect is totally worth consideration to be adopted by Swift as one of the main stream languages. I guess that Apple’s Swift team is already familiar with it. The problem that I see with this is uncertainty as there is no any other production ready implementation that could help spot the problems that may occur. To this time Swift mostly is built on the concepts that were “battle tested”. The best one were picked and adopted in a way that many of us are happy to use it every day. I’m afraid that we will have to wait until version Swift 20 until it could find its place in the language. I know that algebraic effects could replace async/await and event try/catch as algebraic effects allows to make your own this kind of behaviors which makes this concept very powerful. But it’s probably to early as we don’t have even clear path for the async/await. I’d would love to be wrong though

1 Like

On a side note: it's a little tricky to express rethrow (or reasync should we have that) with what I've seen in the AE discussion thus far.

1 Like

Yes, that's why I'm neutral about algebraic effects in general, I'm not advocating for it, but only for taking advantage of the terminology, where "effect" describes a specific "non-purity" flavor we'd like to work with, and "effect system" is a general framework of reasoning about effects and how they compose. As @nonameplum says, AE per se don't seem to be battle tested enough to consider it as the only possible effect system. I advocate for monads and do-notation because they have been battle tested for decades now in other languages (arguably not too mainstream, but not too obscure either). If we consider something like this

protocol Monad {
  associatedtype Value
  associatedtype Self<Value>

  init(_ value: Value)
  func flatMap<T>(_ mapper: (Value) -> Self<T>) -> Self<T>
}

final class Future<T>: Monad { /* implementation skipped for brevity */ }
extension Result: Monad {
  typealias Value = Success
}

flatMap here "rethrows" and "reasyncs" any effect that mapper has by definition. We don't need new keywords here, but only support for higher-kinded types to be able to write Self<T>.

After that for any Monad type we could write something like this:

func collect<M, T>(_ monadicValues: [M<T>]) -> M<[T]> where M: Monad {
  monadicValues.reduce([], { result, element in 
    result.flatMap { $0.append(element) }
  }
}

Note that this would be applicable to any effect, be it Result, Future, AnyPublisher, or even an Array or Optional (arrays and optionals are monads too). The actual do-notation could be more suitable for imperative control flow (pending any syntax bikeshedding):

func loginAndProcessUserInfo(
  email: String, 
  password: String
) -> Future<LoginResult, Error> {
  do {
    let userInfo <- backend.login(email, password)
    if userInfo.isAdmin {
      return backend.doAdminStuff()
    } else {
      return backend.doUserStuff()
    }
  }
}

where <- is transformed as syntax sugar into a flatMap call appropriate to this Monad type.

Terms of Service

Privacy Policy

Cookie Policy