search

dart-lang / language

Design of the Dart language
Other
2.67k stars 205 forks source link

Algebraic Effect handlers #2567

Open gisborne opened 2 years ago

gisborne commented 2 years ago

Algebraic effect handlers are about to land in OCaml. There are a number of other languages that implement them, including at least one that compiles to Javascript (called Koka — that it’s implementable in Javascript is I’m sure important!).

An algebraic effect handler is basically an exception that carries a continuation so you can resume the original computation. Kind of a strongly typed LISP condition.

Given this (simple!) language feature, one can implement in a very straightforward way:

But the feature is generally helpful to the developer also (eg anywhere you have to pass an argument through a bunch of functions so it can be used later on — well, you don’t have to do that; it opens up this and a bunch more new delightful coding patterns in fact).

It’s simple to implement and efficient (the compiler should try to work out the simplest way of doing the thing; if the effect handler doesn’t call out to anything, you can just resolve its logic and then continue; worst case, you block copy the stack frames from the caller to the handler to somewhere else, and then restore them by just copying the stack frames back).

Here is a nice, simple basic description of the feature:

https://overreacted.io/algebraic-effects-for-the-rest-of-us/

Here is a really nice half-hour video by the guy who did the language that compiles to Javascript:

https://www.youtube.com/watch?v=hrBq8R_kxI0

TimWhiting commented 2 years ago

Haha, someone beat me to it. I have been mulling over creating this issue and whether or not it would even be a good fit for the dart language.

A more recent talk from Daan is here: https://www.youtube.com/watch?v=6OFhD_mHtKA (albeit a lot longer, but I highly recommend watching it) The section here on the Koka language website introduces how to use effect handlers in a very beginner friendly way, for anyone who wants a reading resource: https://koka-lang.github.io/koka/doc/book.html#sec-handlers (The whole 3.4 section)

One thing that I thought a lot about in relation to algebraic effects in dart is how difficult it would be to capture stacks for delimited continuations which is what effect handlers require. I'm guessing that dart already does this to some degree because of the event loop / async architecture. Additionally dart already does thread some continuation / async context specific state through the Zone machinery. Therefore the runtime machinery might already partially exist.

If not, I expect it would be a large undertaking to introduce this into the language. There is a C/C++ library developed by Daan https://github.com/koka-lang/libmprompt that implements the full event registering / stack capturing / switching machinery, but it would still require overhauling how dart handles stacks (again speculation).

A concern would be how it plays with the existing async / await, async, sync, event loop of dart, though I think this is addressable.

Implementation effort aside, a few questions are:

Let me try to address these issues (disclaimer I'm not a language designer, but I'm very interested in language design).

Drawbacks:

Advantages:

Does it fit with the language:

Again, not a language designer here, and I'm curious to hear what the dart team thinks of this, but I'm very much interested in algebraic effect handlers, and very much invested in the dart language. It's one of those things like async / await which seems so fundamentally groundbreaking, but will take many years to break into the common programming paradigms. It simplifies so many ad-hoc language concepts / mechanisms into a unified machinery.

Very curious how this plays together with dart's Zones. Essentially Zones let you do a limited form of Algebraic Effect Handling currently, by allowing you to for example override the print function. This would just potentially make Zones as a first class concept more generally useful.

To cite some issues this is related to:

2026

2245 & #2234 & #493 (With implicit parameters this problem could be simplified or done away with)

2476 (The builtin mocking / static method overriding could be done with algebraic effects) - and not require a test specific compilation mode

lrhn commented 2 years ago

So this is like a try/catch where the catch can also pass a value back to the throw point, instead of just escaping.

It requires running the effect handler on top of the stack, instead of eagerly unwinding. That's something I've considered before, and it should not be a problem as such (other than handling stack overflows). It has consequences for when intermediate finally blocks are run. And we need to be very clear about how we define the scope of effect handlers.

As a dual look, rather than a try/catch which can resume, the effect would be a function which can perform an escape. In that way, it's similar to call-with-current-continuation, but the effect function is dynamically scoped by its creation point (the handler), can only be used to escape once, and cannot escape its dynamic scope.

In a typed language, the effect/handler also needs to be typed, so that the handler hands back a value which fits in the hole left by the effect raising expression.

Let's say we introduce effects, say declared as:

effect AbsInt = int Function(int);

We can then introduce a handler like:

try { 
  var n = Random().nextInt(10) - 4; // -4 .. 5
  var abs = try AbsInt(n)
  print(abs);
} on AbsInt(int x) {
  // something
  if (x < 0) continue with -x;
}

The handler can still do other control flow, like break/continue/return/rethrow (and anything can throw as always), so it's not just a function. Also, the handler should probably run in the dynamic effect handler scope that was current when it was initialized, not run as if it is on the top of the current stack, even if we are running the handler on top of the stack to avoid unwinding.

If the handler doesn't continue with, it will exit the handler and that will (try to) unwind the stack down to where the try block started, then continue with that exit (either just continue running, or handle control flow). Since intermediate finally blocks will be run during this, and those can choose to change the control flow, we don't know for sure that control will reach the try block. But if not, behavior is still well-defined.

Needing to be in a dynamical context where a handler is declared seems like the harder part to ensure. If any code can do try Effect(value), how can that code statically know whether a suitable handler is defined around it?

One answer is that it can't, and an unhandled effect is treated just like an exception. It can be caught by on Object as an object looking like an instance of a class defined as struct Effect(args); (primary constructor). Maybe that is the definition of what Effect(args) does, and the handler does a pattern match to extract the values again.

The alternative is to somehow declare the effects used by a method, and only allowing you to call the method inside a scope which declares those effects (which means the body of a handler handling the effects, or a function declared to use at least those effects too). It's checked exceptions, basically. Probably a very hard sell.

Also, because of async, we need to be careful. The stack of effect handlers should be carried along the invocations, as a kind of implicit parameter. It's part of the state we return to in our async trampolines. It won't be Zone based, that's a different kind of dynamic scope. Because of the need to unwind the call stack, the effect handlers must follow that stack of invocations, or simulated it for async code with its stack gaps and implicit callbacks.

I think that should be doable, it'll necessarily cost a little to pass along extra data at each invocation.

(Although, on second thought, it's not very clear how it will work if a function calls an async function, but doesn't immediately await the future. Maybe async just doesn't work.)

generikvault commented 2 years ago

There is a proposal for a returnFrom in GO.

Souch a feature would allow closures to act as an Algebraic Effect handler and it should be compatable with existing code.

void example(){
  final absInt = (int x) {
    // something
    if (x < 0) return -x;
    returnFrom example;
  }
  var n = Random().nextInt(10) - 4; // -4 .. 5
  var abs = absInt(n)
  print(abs);
}
lrhn commented 2 years ago

Allowing functions to do non-local control flow (like returning from a function other than themselves) gets complicated in a language with first class functions.

Such a function must either not be allowed to survive the invocation scope where it was created, or you must be able to handle returning twice from the same function.

The latter is complicated, confusing, and likely expensive. The invocation stack must be retained after the first time the function returns, in case it returns again. Will the local variable up-stack keep their current value, or be modified (is the stack copied, or reused)?

Preventing the function from escaping seems simpler. It'd be something like marking the function as "scoped"/"local", and then transitively ensure that a scoped function is never stored in any place outside of the invocation stack. They can be used as arguments to other functions, but never returned. Say:

bool example
  final local absInt = (int x) {
    if (x < 0) return -x;
    example.return false;
  }
  action(absInt);
  return true;
}
void tweakSomeNumbers(local int Function(int) f) {
  var n = Random().nextInt(10) - 4;
  var fn = f(n);
  print(fn);
}

Being local affects a type, F \<: local F for any normal function type F. Anywhere you expect a local function, you can also use a non-local function. It just won't be leaked, even if it doesn't care about that. Which means that in parameter position, contravariantly, Function(local F) \<: Function(F), so you can make parameters local in a subclass, but not remove it.

In good Dart style, we'd make the local-ness part of the runtime type of a local function, which is any local function which uses the non-local control flow feature.

We'll still have some issues around async functions. A local function from a synchronous function can probably not be used in an async function, or vice versa. So we have sync local and async local functions.

Using local functions with non-local control flow seems to be half of the effect feature. The other half is the implicit dynamic scope, which has me worried anyway. Unless doing checked exceptions, it's impossible to know whether there is any surrounding handler. Doing the scoping manually feels better to me (but again, async is a problem).

gisborne commented 2 years ago

OCaml is a language with similar features to Dart and will be releasing v5 with Algebraic Effects any day now. On Oct 13, 2022, 05:09 -0700, Lasse R.H. Nielsen @.***>, wrote:

Allowing functions to do non-local control flow (like returning from a function other than themselves) gets complicated in a language with first class functions. Such a function must either not be allowed to survive the invocation scope where it was created, or you must be able to handle returning twice from the same function. The latter is complicated, confusing, and likely expensive. The invocation stack must be retained after the first time the function returns, in case it returns again. Will the local variable up-stack keep their current value, or be modified (is the stack copied, or reused)? Preventing the function from escaping seems simpler. It'd be something like marking the function as "scoped"/"local", and then transitively ensure that a scoped function is never stored in any place outside of the invocation stack. They can be used as arguments to other functions, but never returned. Say: bool example final local absInt = (int x) { if (x < 0) return -x; example.return false; } action(absInt); return true; } void tweakSomeNumbers(local int Function(int) f) { var n = Random().nextInt(10) - 4; var fn = f(n); print(fn); } Being local affects a type, F <: local F for any normal function type F. Anywhere you expect a local function, you can also use a non-local function. It just won't be leaked, even if it doesn't care about that. Which means that in parameter position, contravariantly, Function(local F) <: Function(F), so you can make parameters local in a subclass, but not remove it. In good Dart style, we'd make the local-ness part of the runtime type of a local function, which is any local function which uses the non-local control flow feature. We'll still have some issues around async functions. A local function from a synchronous function can probably not be used in an async function, or vice versa. So we have sync local and async local functions. Using local functions with non-local control flow seems to be half of the effect feature. The other half is the implicit dynamic scope, which has me worried anyway. Unless doing checked exceptions, it's impossible to know whether there is any surrounding handler. Doing the scoping manually feels better to me (but again, async is a problem). — Reply to this email directly, view it on GitHub, or unsubscribe. You are receiving this because you authored the thread.Message ID: @.***>

TimWhiting commented 2 years ago

@gisborne Arguing that a language is similar is probably not the right way to address @lrhn's concerns.

One of the issues is that to address some of @lrhn's concerns and comments requires deep knowledge in how the event loop and function stacks are implemented in dart. I don't profess to be an expert there.

However, to address a few of the design / implementation questions that @lrhn has raised:

Allowing functions to do non-local control flow (like returning from a function other than themselves) gets complicated in a language with first class functions. Such a function must either not be allowed to survive the invocation scope where it was created, or you must be able to handle returning twice from the same function.

I agree. Which is why I think for the dart language in particular it should not allow for multiple resumptions, at least for an initial implementation of this feature. This also allows for performance improvements.

From the koka documentation about tail resumptive operations: (single resumption). > Moreover, operations declared as fun are much more efficient than general ctl operations. The Koka compiler uses (generalized) evidence passing [[19](https://koka-lang.github.io/koka/doc/book.html#xie:evidently)–[21](https://koka-lang.github.io/koka/doc/book.html#xie:evp)] to pass down handler information to each call-site. At the call to ask in [add-twice](https://koka-lang.github.io/koka/doc/book.html#add_twice), it selects the handler from the evidence vector and when the operation is a tail-resumptive fun, it calls it directly as a regular function (except with an adjusted evidence vector for its context). Unlike a general ctl operation, there is no need to yield upward to the handler, capture the stack, and eventually resume again. This gives fun (and val) operations a performance cost very similar to virtual method calls which can be quite efficient.

koka additionally has effect val operations which are essentially a nullary function that returns the value sugared as just providing a value. This can further be optimized.

The alternative is to somehow declare the effects used by a method, and only allowing you to call the method inside a scope which declares those effects (which means the body of a handler handling the effects, or a function declared to use at least those effects too). It's checked exceptions, basically. Probably a very hard sell.

I know that this will be a hard sell. I don't like the idea of dynamic algebraic effects, I'd rather see dart adopt typed / statically checked effects. I think that effect inference and effect polymorphism addresses most of the concerns here. https://koka-lang.github.io/koka/doc/book.html#sec-polymorphic-effects For example in koka the type of the function map is the following: 

map : (xs : list<a>, f : (a) -> e b) -> e list<b>

Where the function f is applied to each element of xs, and since f could raise an effect e, map also could raise that effect. This can be inferred and omitted potentially.

As far as the async issue which I believe to be the one that would prevent this feature from ever being introduced into dart:

There are two ways to approach this.

The first way is just to understand how to deal with transitioning between the value and effect world, and maybe adding some restrictions to unawaited futures.

In koka it explains how you can convert between the world of values and the world of effects: https://koka-lang.github.io/koka/doc/book.html#sec-return

For example here is a function to convert from an exception (raise) effect to a maybe result.

fun raise-maybe( action : () -> <raise|e> a ) : e maybe<a>
  with handler
    return(x)  Just(x)   // normal return: wrap in Just
    ctl raise(msg) Nothing   // exception: return Nothing directly  
  action()

fun div42()
  (raise-maybe{ safe-divide(1,0) }).default(42)

From this viewpoint, it seems as if converting between and effect of async and a value of Future is much the same thing. From what I understand of koka's implementation of async is that you can do this, any unawaited future is essentially a function call that never resumes to the original call-site, but as @lrhn mentioned I don't know what that means to that function's ability to access the dynamically scoped functions introduced by the scope. Maybe they are limited to ones that don't require capturing a stack. I'll read this paper to try to understand more.

Where async gets tricky is understanding how this fits into the current event loop of dart, and I don't know enough to know what that entails.

The other approach is to build dart's async / await on top of the effect handling machinery. That is to implement the event loop in a dart function that automatically wraps the main function in an effect handler that manages the async values and callbacks: An example of this approach is here: https://github.com/koka-lang/koka/blob/8feaf18b58816b9cd08a9b5148b1f3c19a00da6e/lib/std/async.kk#L544. However I believe this approach requires more than just tail call resumptions (line 575). This might mean that async & effect handlers are fundamentally incompatible in a language like dart in which we might not want to allow for resumptions that are not tail-call optimized.

Personally I feel that if the Iterable / Async / Await / Exception handling mechanisms of dart can't be swapped out for effect handling runtime machinery + reimplementation of these concepts in the standard library, it might not be worth introducing effect handlers as in the literature.

However, I don't think that means that we can't take ideas and inspiration from these concepts. Implicitly passed variables with dynamic scoping would be a restriction that I would personally be happy with. Usages of these variables would infer an implicit variable requirement for anyone calling the function, and anyone calling the function but without providing a value would also infer the requirement, until you get to a function that has an annotation of what effects it expects (and the value is not included in which case it is an error), or it gets to the main function where all implicit variables that are not given must be supplied.

This might look something like this.

effect MyPrettyPrintOptions {
  int maxLineLength;
  File? prettyPrintFile;
}

void prettyPrint(String s) { // inferred effect type / requirement [MyPrettyPrintOptions]
  if (prettyPrintFile != null){
    prettyPrintFile.writeln(s.truncate(maxLineLength));
  } else {
    print(s.truncate(maxLineLength));
  }
}

// Assuming effect types are in [] right after function name. Not sure best design for this.
void extraSpecialPrettyPrint[MyPrettyPrintOptions](String s){
  with override MyPrettyPrintOptions(120, File('test.txt')) {
    prettyPrint(s);
  }
} 

void otherFunction() { // inferred effect type / requirement [MyPrettyPrintOptions]
  prettyPrint("something");
}

void otherFunction2[]() {
  // Error: explicit mention that otherFunction2 has handled all inner effects []
  // but is using function prettyPrint which requires a handler for MyPrettyPrintOptions
  prettyPrint("something");
}

void main() { // Error MyPrettyPrintOptions not handled 
 otherFunction("something");
}
// Okay
void main() {
  with MyPrettyPrintOptions(80, null) {
    otherFunction("something");
    extraSpecialPrettyPrint("hi");
  }
}

Any functions that don't infer an effect or a polymorphic effect, would then be optimized not to pass an implicit parameter. Functions that would require a polymorphic effect such as map, could just be compiled to always take the implicit parameter, or could compile two different functions that could be dispatched to depending on whether the function being passed requires an implicit paramter or not.

GregoryConrad commented 9 months ago

For what it's worth, if Flutter adopted algebraic effects, state management would largely cease to be an issue across the ecosystem. In a breaking change, or perhaps just in a new widget for backwards compatibility, you can do everything via algebraic effects:

// Simple counter example:
@effectfulWidget // macro via static metaprogramming
Effect<Widget, SideEffect> myCountingWidget() {
  final (count, setCount) = try state(default: 123);
  void incrementCount() => setCount(count + 1);
  return TextButton(
    onPressed: incrementCount,
    child: Text('$count'),
  );
}

// We can also allow for composition of side effects:
Effect<(int, void Function(), AsyncSnapshot<int>), SideEffect> myPersistedCountSideEffect() {
  final (state, setState) = try state<int?>();
  final AsyncSnapshot persistedState = try hydrate(state, read: readFromMyDb, write: writeToMyDb);
  return (state, () => setState(state + 1), persistedState);
}

// And even easy async:
@effectfulWidget // macro via static metaprogramming
Effect<Widget, SideEffect> myFutureWidget() {
  final AsyncSnapshot snapshot = try future(someFuture);
  return Text('$snapshot');
}

Issue is we would need one "root" side effect type for the type system to be happy (SideEffect above). It'd be nice for Flutter to provide such a mechanism, but 3rd party libs also can (ReArch basically does this, and is how it works under the hood).

Edit: I'm just spitballing syntax here, but since Effect<Foo, Bar> would be a breaking change, you could also adopt a syntax like:

Widget myWidget() performs SideEffect { // or maybe "trys" instead of "performs"
  // ...
}
munificent commented 8 months ago

I have to admit, I'm skeptical that this would be a good fit for Dart. I generally love the idea of using the type system to reason about programs better, but there comes a point of diminishing returns and I suspect that algebraic effects are beyond that point for most Dart users.

gisborne commented 8 months ago

I’m puzzled by that. This feature is simple to understand, I believe not terrible to implement, and yet is of great generality and expressiveness. It is in fact so simple yet general that Exceptions are a restricted special case.

Others have discussed how it could often greatly simplify writing Widgets, particularly complex compositions of Widgets. For Flutter in particular, this would be a great benefit. On 8 Mar 2024 at 14:23 -0800, Bob Nystrom @.***>, wrote:

I have to admit, I'm skeptical that this would be a good fit for Dart. I generally love the idea of using the type system to reason about programs better, but there comes a point of diminishing returns and I suspect that algebraic effects are beyond that point for most Dart users. — Reply to this email directly, view it on GitHub, or unsubscribe. You are receiving this because you were mentioned.Message ID: @.***>

lrhn commented 8 months ago

This feature is simple to understand,

I'm going to have to question that claim. The feature itself may seem simple, but it's decidedly unclear how it interacts with:

It's more than one feature. It includes, effectively:

Having exceptions being a restricted case isn't particularly illuminating when it's the parts outside of that restriction which are complicated. And even then, exceptions are notoriously untyped even in an otherwise typed language, so generalisering from that does not suggest a good fit for Dart.

I personally think "code blocks" that work as non-escaping "local" functions, and which can do control flow, could be a much better fit for Dart.

int firstNeg(Iterable<int> ns) {
  ns.forEach(x){
     if (x < 0) firstNeg.return x;
  };
  return 0;
}

That avoids the dynamic effect handler scope, you have to actually pass the function down the stack. That means typing is trivial. (Still non-trivial how it would interact with async.)

On the other hand, because the feature is as dynamic as it is, and we already have features to handle dynamic scopes, it should be possible to implement this in Dart. The only thing that's hard is typing. And doing async right. Something like this;

gisborne commented 8 months ago

On 9 Mar 2024, at 00:50, Lasse R.H. Nielsen @.***> wrote:

This feature is simple to understand,

I'm going to have to question that claim. The feature itself may seem simple, but it's decidedly unclear how it interacts with:

async functions finally first class functions static typing It's more than one feature. It includes, effectively:

non local return or control flow dynamic resolution of a function call The feature is available in the now aggressively parallelised OCaml. There are a number of discussions about adding it to Javascript eg https://github.com/macabeus/js-proposal-algebraic-effects I personally think "code blocks" that work as non-escaping "local" functions, and which can do control flow, could be a much better fit for Dart.

int firstNeg(Iterable ns) { ns.forEach(x){ if (x < 0) firstNeg.return x; }; return 0; }

Blocks would be great, but that seems a different question.

lrhn commented 8 months ago

I've read the JS proposal and the article it links to. I'm still not convinced that what's described is a good idea for Dart.

The article does say that algebraic effects can be typed in a static type system with first-class functions, but it also implies that's at the cost of having every function type include every effect that it depends on. If the function type lists a set of function types, by name, then it's effectively an extra set of parameters that are implicitly passed to the function when it's called.

That's a quite serious cost. Let's say we use identifiers to name effects, then a Dart function type could be (curly braces for required effects):

T Function<T>{id: T Function(T), escape: Never Function()}(T)

for a function which may use the id and escape effects at the given types. That would likely be a subtype of: 

T Function<T>{id: T Function(Object), escape: never Function(), other: int Function(int)}(T)

That is, contravariant in the effect types - can be used as a function type that requires at least the same effects. It's parameters, by any other name.

Every function will have these. You may get away with not declaring them, but they're there anyway. Required effects must be listed in DartDoc, explicitly written function types must list all effect types needed. A List<int Function(int)> cannot contain any function which performs an effect. There is probably no easy way to parameterize over effects, so you can't have List<int Function{*}(int)> that ignores the effects, because int Function{id: int Function(int)](int) and int Function{escape: Never Function()}(int) are completely unrelated types.

The explanation that the intermediate functions don't need to worry about effects, seems wrong then. All functions in the stack frame down to the effect perform needs to be aware that the effect is used, because otherwise it cannot possibly allow the effect to be performed in a sound and statically typed way. Which means that every function in that call stack must declare that they need the same effect. (At least unless closures can capture the current handlers, thereby removing the requirement from the function signature, but this is a dynamically resolved effect, so probably not).

This is all very verbose, unless it can be inferred, and if it can be inferred (not obvious for Dart's type system), then small changes can easily change the type signatures of a large hierarchy of functions. It really is checked exceptions all over again.

What the proposal and article says about the effect handler being able to be asynchronous, even if performed from a synchronous function, is wrong. At least for Dart, but I'd be very surprised if not also for JS. It says that the perform keyword creates a callback for the rest of the function. That's not enough, it has to create a callback for the rest of the stack, which is what async functions can do, and synchronous functions cannot. (Maybe that's what the @@ operator is about, it's something related to the Babel parser used, I think. But if you need a special way to invoke any method that may perform effects, then that's definitely a new function color.)

I don't believe we can forget about asynchrony at all, not the way Dart asynchrony works. We can have asynchronous effect handlers, but they must return a future, and then the caller must figure out how to deal with that if they're not themselves asynchronous. There is no way to suspend a non-async function in Dart.

The proposal seems to have the handle block always resume with a value. It even says:

Since perform is an expression, it always return a value. If resume wasn't called after a perform, it'll be undefined

That doesn't suggest that the effect handler can choose to escape by throwing or returning from its own scope. It really is called on top of the stack, as a function, and must return. Which means that this isn't even similar to exception handling, it's just a dynamically resolved, statically typed, scope that things can be looked up in, and called.

And that's why I suggest that simply passing functions as arguments is a perfectly reasonable implementation of this. Imagine if a function could have a set of implicit parameters, which are automatically forwarded from similar implicit parameters of the caller, so you only need to write the ones that you didn't get as arguments yourself (or that you wanted to change):

void processLog{log: void Function(String, {String? id}), extractId: String? Function(String)}(String input) {
  for (var line in LineSplitter.split(input)) {
    var id = extractId(line);
    processLine(line, id);
  }
}
void processLine{log: void Function(String, {String? id})}(String line, String? id) {
  if (id != null && id.contains("banana")) {
     line = "[Banana]: $line";
  }
  log(line, id);
}

This is, not coincidentally, what effect-annotated function declarations would (potentially) look like too. Here the log parameter is automatically forwarded to processLine, because it exists and was not passed explicitly. That design would, as I see it, perfectly match algebraic effect handlers as described for JS here - well typed, implicitly available (but declared as required) functions provided by the call stack.

Or just use a dynamic environment, like the example code I linked. (If that Effect class required a default implementation, which couldn't escape, it would be impossible to not have an implementation when calling it. Then it's all about scoping which implementation gets called.). That code even allows you to escape from the the handler to the code introducing the handler. The code blocks would be a function that can be passed as argument, and can be called and escape from the declaration site. If that's a feature we want. Otherwise, it's just a function.

I can see how this feature can be convenient, especially in an untyped language. I don't think it's a good fit for Dart. I don't see any particularly good and viable adaptions. If it's typed and checked, then we get effect annotations on every function, which has to be updated every time a function that might be called transitively, uses a new effect. That will be hell. If we skip the checked, then we don't need to know if an effect handler exists, but we then still need a way to specify the expected type of the handler, if it exists. A failure will be a runtime error. That's something Dart has generally moved away from. If it's not typed, well, probably not a big difference from not being checked, runtime errors can still happen if someone holds the effect wrong.

(Now, if Dart was a language with first class continuations ... but it isn't.)

gisborne commented 8 months ago

I’m not sufficiently familiar with compiler development to comment knowledgeably about this. What I know is:

  1. This is a great language feature that would be a tremendous enabler of simplifying Dart and Flutter work. Just removing colored functions would be amazing.

https://volodymyrpavlyshyn.medium.com/algebraic-effects-remove-color-from-functions-and-add-more-color-to-your-life-f087c0e2944d

It would also simplify a lot of Flutter complexities that lead to the large and confusing collection of state handling libraries we have.

  1. It is implemented in at least one real-world statically-typed language (OCaml) with robust parallelism constructs. Probably looking into how they did that would be the most useful step here.

Grateful for this thoughtful discussion.

On 9 Mar 2024, at 15:03, Lasse R.H. Nielsen @.***> wrote:

I've read the JS proposal and the article it links to. I'm still not convinced that what's described is a good idea for Dart.

The article does say that algebraic effects can be typed in a static type system with first-class functions, but it also implies that's at the cost of having every function type include every effect that it depends on. If the function type lists a set of function types, by name, then it's effectively an extra set of parameters that are implicitly passed to the function when it's called.

That's a quite serious cost. Let's say we use identifiers to name effects, then a Dart function type could be (curly braces for required effects):

T Function{id: T Function(T), escape: Never Function()}(T) for a function which may use the id and escape effects at the given types. That would likely be a subtype of:

T Function{id: T Function(Object), escape: never Function(), other: int Function(int)}(T) That is, contravariant in the effect types - can be used as a function type that requires at least the same effects. It's parameters, by any other name.

Every function will have these. You may get away with not declaring them, but they're there anyway. Required effects must be listed in DartDoc, explicitly written function types must list all effect types needed. A List<int Function(int)> cannot contain any function which performs an effect. There is probably no easy way to parameterize over effects, so you can't have List<int Function{*}(int)> that ignores the effects, because int Function{id: int Function(int)](int) and int Function{escape: Never Function()}(int) are completely unrelated types.

The explanation that the intermediate functions don't need to worry about effects, seems wrong then. All functions in the stack frame down to the effect perform needs to be aware that the effect is used, because otherwise it cannot possibly allow the effect to be performed in a sound and statically typed way. Which means that every function in that call stack must declare that they need the same effect. (At least unless closures can capture the current handlers, thereby removing the requirement from the function signature, but this is a dynamically resolved effect, so probably not).

What the proposal and article says about the effect handler being able to be asynchronous, even if performed from a synchronous function, is wrong. At least for Dart, but I'd be very surprised if not also for JS. It says that the perform keyword creates a callback for the rest of the function. That's not enough, it has to create a callback for the rest of the stack, which is what async functions can do, and synchronous functions cannot. (Maybe that's what the @@ operator is about, it's something related to the Babel parser used, I think. But if you need a special way to invoke any method that may perform effects, then that's definitely a new function color.)

I don't believe we can forget about asynchrony at all, not the way Dart asynchrony works. We can have asynchronous effect handlers, but they must return a future, and then the caller must figure out how to deal with that if they're not themselves asynchronous. There is no way to suspend a non-async function in Dart.

The proposal seems to have the handle block always resume with a value. It even says:

Since perform is an expression, it always return a value. If resume wasn't called after a perform, it'll be undefined

That doesn't suggest that the effect handler can choose to escape by throwing or returning from its own scope. It really is called on top of the stack, as a function, and must return. Which means that this isn't even similar to exception handling, it's just a dynamically resolved, statically typed, scope that things can be looked up in, and called.

And that's why I suggest that simply passing functions as arguments is a perfectly reasonable implementation of this. Imagine if a function could have a set of implicit parameters, which are automatically forwarded from similar implicit parameters of the caller, so you only need to write the ones that you didn't get as arguments yourself (or that you wanted to change):

void processLog{log: void Function(String, {String? id}), extractId: String? Function(String)}(String input) { for (var line in LineSplitter.split(input)) { var id = extractId(line); processLine(line, id); } } void processLine{log: void Function(String, {String? id})}(String line, String? id) { if (id != null && id.contains("banana")) { line = "[Banana]: $line"; } log(line, id); } This is, not coincidentally, what effect-annotated function declarations would (potentially) look like too. Here the log parameter is automatically forwarded to processLine, because it exists and was not passed explicitly. That design would, as I see it, perfectly match algebraic effect handlers as described for JS here - well typed, implicitly available (but declared as required) functions provided by the call stack.

Or just use a dynamic environment, like the example code I linked. (If that Effect class required a default implementation, which couldn't escape, it would be impossible to not have an implementation when calling it. Then it's all about scoping which implementation gets called.). That code even allows you to escape from the the handler to the code introducing the handler.

I can see how this feature can be convenient, especially in an untyped language. I don't think it's a good fit for Dart. I don't see any particularly good and viable adaptions.

— Reply to this email directly, view it on GitHub https://github.com/dart-lang/language/issues/2567#issuecomment-1987003663, or unsubscribe https://github.com/notifications/unsubscribe-auth/AAAG7X36RZSJ6WA6CXS5NXLYXOIL7AVCNFSM6AAAAAARA7JE5WVHI2DSMVQWIX3LMV43OSLTON2WKQ3PNVWWK3TUHMYTSOBXGAYDGNRWGM. You are receiving this because you were mentioned.

lrhn commented 8 months ago

So, to be clear: A full, typed and sound, implementation of algebraic effects, would very powerful.

However, the "full" implementation means being able to capture continuations. All the "you don't need to color your functions" come back to that, and it's not really the effect handlers, it's the ability to capture a continuation that matters. If you can do that, you don't need async/await to begin with.

Effect handlers is two features combined: Capturing continuations (even if only linear/single-use continuations) and a dynamic registry/dependency injection for functions that you can call with these continuations.

Dart does not have the ability to capture continuations. We might be able to get that, if JavaScript and Wasm does. The talk about using effect handlers with React is built on top of their React Fibers, which is (as I read it) their own reimplementation of async/await, which then allows them to capture the delimited "stack" of their fiber at specific points. Without the ability to capture continuations, effects handlers will still have all the same colors as every other function. (And with the ability to capture continuations, effect handlers or not, you don't need the colors.)

OCaml is an example of typing effects, but not typing the function's requirements. The effects are unchecked. You can declare an effect, with a type. You can introduce a handler for an effect. And you can try to perform the effect, but there is no static help in figuring out whether there is any handler in scope for the effect. That makes performing an effect a dynamic feature, one which can fail at runtime. I basically agree with this comment, in that that is not a good fit for a language that tries to be statically checked.

With neither continuation capturing, nor checked effects, there isn't much feature left. What's left is something you can implement in a limited number of lines of plain Dart, like this example (again).

So for algebraic effect handlers to actually be meaningful to add to Dart, it will require either being able to capture a continuation, or some way to have a checked effect system that doesn't get more cumbersome than Java checked exceptions.

And if we can capture continuations at all, without effect handlers, we can build effect handlers in pure Dart too.

(I think the comparison to exceptions is causing more confusion than it's helping. Effect handlers dynamically scoped like exceptions, which is part of the reason it's implemented as unchecked as exceptions, but the actual implementations are not unwinding the stack when performed. Even the OCaml implementation requires the continuation is either continued - (async) complete with a value - or discontinued - (async) complete with an error. Performing an effect is really just calling a dynamically resolved function which may block.)

TekExplorer commented 1 month ago

...couldnt we effectively do this with zones? I mean, okay, there would be a lack of type indicators, but otherwise it seems like something we can effectively already do...?

Could be interesting to see what examples might come of that

TimWhiting commented 1 month ago

You can definitely do dynamic scope with zones (even with asynchronous behavior). However, like @lrhn stated in his last comment you also need the ability to capture continuations to implement full effect handlers (to get rid of the function coloring problem). Additionally, you don't get any of the benefits of typed effects. You can definitely implement a subset of effect handlers with zones (which @lrhn has shown and links to in his comment), and maybe even most of effect handlers, but you have to deal with some issues and corner cases with async and await.