Algebraic Effects

mklbtz · June 30, 2023, 6:12pm

The "Keyword Generics Initiative" from Rust provided some really interesting insights, thanks for sharing that @KeithBauerANZ !

In particular, I had never thought of rethrows as a kind of "generic" but that makes total sense to me now. (In other words, a rethrows func is "generic over" whether or not it throws, and depends on its arguments / call site.)

Extending from that, I love their idea of having a super-generic effect keyword that encompasses rethrows, reasync, and any other future effects. If we can get reasync working in Swift — from what I understand there's been some implementation issues — I would love to see some exploration in this area. It seems like it would be a huge boon for library authors.

mklbtz · June 30, 2023, 6:41pm

On the topic of a user-extensible effects system…

You can get a feel for how useful this would be by hacking together a system just based on Errors and Closures. Doing it this way does require your code to use continuation-passing-style, so you can't use simple return types. But to me it's encouraging to see that it's possible. And those limitations could be lifted with a more foundational design.

Here's an example based off the original post's depends effect example.

/// An "Effect" modeled with an Error and Continuation function
struct RequireDependency<Dep>: Error {
    let fulfill: (Dep) -> Void
}

// A function that declares the `depends` effect.
// Ideally this would `return` the vector, not use a closure.
func withRandomVector(_ operation: ([Int]) -> Void) throws {
    // Simulating a builtin keyword like `await` but for accessing a dependency
    throw RequireDependency<RandomNumberGenerator> { generator in 
        let vector = [generator.int(), generator.int(), ...]
        operation(vector)
    } 
}

// A call site that just uses the `depends` function.
func printRandomVectorSum() throws {
    try withRandomVector { vector in 
        print(vector.reduce(0, +))
    } 
}

// The top of the call stack, which fulfills the dependency.
func main() {
    do { 
        try printRandomVectorSum()
    } catch let requirement as RequireDependency<RandomNumberGenerator> { 
        // The `throw` propagates to here, which fulfills the dependency and continues the code flow.
        requirement.fulfill(CustomRNG())
    } catch {
        fatalError("some other error \(error)")
    }
}

(This is an incomplete example. I didn't bother with recursion, i.e. requiring multiple dependencies.)
I'm pretty sure you could model just about anything this way, if you're okay with continuation-passing-style. It's cool that this is possible, but obviously the ergonomics are lacking.

The thing I'm not sure about is how to compose effects. Like async throws. I would guess not all effects could compose together gracefully. And maybe only if used in a certain order. If we wanted to make a user-extensible effect system, that would have to be sorted out.

Joe_Groff · June 30, 2023, 7:11pm

You could build an even closer analog in terms of async, since with*Continuation gives you a delimited continuation for the task (albeit a one-shot continuation, unlike the multi-shot continuations that "pure" algebraic effect systems provide in functional languages). You could for example store the effect handler in task-local state, and have the effect operations be functions that use withCheckedContinuation to access the current handler and resume the task with the result:

class State {
  var value: Int
}

@TaskLocal var stateHandler: State?

// Run the block with a state handler
func with(state: State, _ body: () async throws -> R) rethrows -> R {
  stateHandler = state
  defer { stateHandler = nil }
  return try await body()
}

// Access the current state
var stateValue: Int {
  get async {
    return withCheckedContinuation { cc in
      cc.resume(returning: stateHandler!.value)
    }
  }
}

Anachron · September 27, 2023, 11:16pm

Just throwing this out there: in the meantime, I've come up with a "system" to do something like the "monad interpreter pattern" that kinda does the algebraic effect trick, except in a more traditional monad-y way instead of keywords.

I encourage you to try and play with the Free template.

The cool thing about this approach is that adding "new effects" is as simple as adding an enum case. This will automatically force you to rewrite all your "effect handlers" so they handle the new effect. Adding new monadic "target types" into which you can parse your monad is just a little boilerplate, but the template already comes with a few that you can use/change.

This gives us the necessary hint how we ought to think of "combining" effects: since we're working on a restricted subset of all monads (namely the free monads over some "alphabet"), we can think of effects as a kind of sum type! Combining them is super easy, barely an inconvenience.

Thinking about an algebraic effect system, I'd by now imagine it as follows:

One declares a data type that can represent an effect and annotates the type with @Effect. The annotation will require one to define keywords similar to "throws", "rethrows" and "try", while throwing will always happen via the keyword "throw".
Stacking effects can be done in any arbitrary order in the declaration of the function. All that this does is that in the background, a new sum type is generated that can store each effect; and a new "free" type is generated that allows for chaining effects.
Effect handlers (do/catch) simply parse the effects into other effects that are declared in the enclosing function declaration. No effect in the declaration of the enclosing function means that you actually run the code.

That's at least a mental model. I'm sure this can be built deeper into the compiler so that generating a sum type and a free type isn't necessary.

Anachron · October 8, 2023, 2:02am

Found an even more general "solution", but it's not exactly type safe. One can write some boilerplate though to make it "kinda" safe...


public struct Free<Meta, T> {
    
    let kind : Kind
    
    enum Kind {
        case pure(T)
        case free(Meta, (Any) -> Free<Meta, T>)
    }
    
    private static func pure(_ t: T) -> Self {
        .init(kind: .pure(t))
    }
    
    public static func free(_ meta: Meta, _ trafo: @escaping (Any) -> Free<Meta, T>) -> Self {
        .init(kind: .free(meta, trafo))
    }
    
    static func lift(_ meta: Meta) -> Self {
        .free(meta) {any in .pure(any as! T)}
    }
}

public extension Free {
    func erased() -> Free<Meta, Any> {
        flatMap{.pure($0)}
    }
    func map<U>(_ trafo: @escaping (T) -> U) -> Free<Meta, U> {
        flatMap{arg in .pure(trafo(arg))}
    }
    func flatMap<U>(_ trafo: @escaping (T) -> Free<Meta, U>) -> Free<Meta, U> {
        switch kind {
        case .pure(let t):
            return trafo(t)
        case .free(let free, let trf):
            return .free(free) {any in trf(any).flatMap(trafo)}
        }
    }
    func parseRec<NewMeta>(_ rec: @escaping (Free<Meta, T>) -> Free<NewMeta, T>,
                           _ trafo: @escaping (Meta) -> Free<NewMeta, Any>) -> Free<NewMeta, T> {
        switch kind {
        case .pure(let t):
            return .pure(t)
        case .free(let meta, let trf):
            return trafo(meta).flatMap{any in trf(any).parseRec(rec, trafo)}
        }
    }
    func runUnsafe(_ exec: (Meta) async throws -> Any) async rethrows -> T {
        var this = kind
        while true {
            switch this {
            case .pure(let t):
                return t
            case .free(let meta, let trafo):
                this = try await trafo(exec(meta)).kind
            }
        }
    }
}

Given the following enum:

enum Console {
    case print(String)
    case readLn
}

I wonder if we could somehow have a macro that generates the following (or similar) code:


extension Free {
    static func print(_ arg: String) -> Free<Console, Void> where Meta == Console, T == Void {
        .lift(.print(arg))
    }
    static func readLn() -> Free<Console, String> where Meta == Console, T == String {
        .lift(.readLn)
    }
}

extension Free where Meta == Console {
    
    func parse<M>(parsePrint: @escaping (String) -> Free<M, Void>,
                  parseReadLn: @escaping () -> Free<M, String>) -> Free<M, T> {
        parseRec({$0.parse(parsePrint: parsePrint, parseReadLn: parseReadLn)}) {meta in
            switch meta {
            case .print(let string):
                parsePrint(string).erased()
            case .readLn:
                parseReadLn().erased()
            }
        }
    }
    
    func runUnsafe(onPrint: (String) -> Void,
                   onRead: () -> String) async -> T {
        await runUnsafe{meta in
            switch meta {
            case .print(let string):
                return onPrint(string)
            case .readLn:
                return onRead()
            }
        }
    }
    
}

vitamin · April 16, 2024, 1:06am

I do really like this idea, concerns about actual feasibility aside. It seems in alignment with Swift's existing emphasis on adding safety without compromising code legibility.

It does raise the question of how something like the original syntax you proposed could be compatible with asynchronous effects? Does the caller then also have to be explicitly async or can asyncronicity be subsumed as an inherited trait, like protocol inheritance?

If not I might be concerned about keyword proliferation like "async depends throws" etc.

In creating a dependency injection framework one thing we ran into was that you tend to have lots of dependencies that can easily enough be initialized off the main thread, but many that can't, so I ideally one could choose to define "depends" as inherently async.