Continuations (“function calls”) reduce the amount of optimisations you can do around memory - both space wise and computationally

Not sure I follow what you're trying to say. Can you elaborate?

Equating "algebraic effects" with "continuations" is like saying "if" is just "goto" (which isn't even true, e.g., an if can turn into a cmov or whatever).

The only mystique around algebraic effects is the same mystique there is around monads. I don't know if people have started equating algebraic effects to burritos yet but that's a pretty good way to take something simple and turn it into something confusing.

> Equating "algebraic effects" with "continuations" is like saying "if" is just "goto"

Fair enough. But are you responding to something I said? I didn't make that equation.

> The only mystique around algebraic effects is the same mystique there is around monads. I don't know if people have started equating algebraic effects to burritos yet but that's a pretty good way to take something simple and turn it into something confusing.

Ah, are you saying that fundamentally there isn't really much to algebraic effects and they're much simpler than they're made out to be? If so then it perhaps we agree?

We disagree that they're just continuations (only one of many possible implementation strategies) but agree they're nothing special ;)

I don't think I said they're just continuations. In fact I'm trying to make the point that they're mostly just function calls (and I think in my career I've come across one case where I wanted something beyond function calls (for a constraint solver)). There are "multi-shot" continuations (whether you consider that interface or implementation I don't really mind), which have behaviour than function calls can't express, but I don't know of any algebraic effects beyond that.

What do you think algebraic effects are, if they're not continuations?

EDIT: Ah, based on your comment at https://news.ycombinator.com/item?id=48334737 you might say they're a feature of an intermediate language? So you might take a surface language and "compile to an intermediate language of lambda calculus + algebraic effects", without specifying how that intermediate language is implemented (because it may not even be implemented, per se).

They're really just a protocol. You can implement them in various ways. They will always be some sort of delimited continuations but a "function call" or continuation passing style or anything of the sort does not have to be involved at all.

For example, let us say I don't allow "multi-shot" continuations like in your library, and I'm implementing Algebraic Effects in my own interpreted language.

One way I can implement effects and handlers is to have a handlers get registered in a stack, then when an effect is triggered, save the IP and current stackframe, search for the right handler and jump to it. "resume" then just resets the stackframe, pushes a value into the stack, and sets the saved IP.

(Only saw your edit after posting, sorry, but yes)

> They're really just a protocol.

Thanks, that clarifies where you're coming from. Is it possible to specify this protocol somehow, by defining an interface for it? Or by extending lambda calculus with the bits it needs?

(Maybe that's what the Koka folks do in their papers, and if so feel free to say, "yeah read their papers").

I'm thinking a less formally than that. Protocol in a very layman-y "perform is supposed to do this, resume is supposed to do this".

For example, Koka compiles handlers differently depending if they do multi-shot continuations or not. It can do this because all that matters is "perform is supposed to do this, resume is supposed to do this", not what they turn into (same as "if" turning into "cmov" in certain cases). I think it uses a continuation-passing style sort of implementation, but I can't quite remember.

Daan's libhandler implements effects for C in an entirely different manner. It captures the stack much like my example or a stackful coroutine library would.

I'm sure there a formal definitions in both the koka papers and the libhandler paper, but I just skim that stuff ;)

> Protocol in a very layman-y "perform is supposed to do this, resume is supposed to do this".

OK, but at the very least it has two primitives "perform" and "resume"? And they're supposed to interact in some particular way?

Yeah, there's three things you're supposed to implement: try/handle, perform, and resume. The names can vary (e.g., perform is often called "raise" or "do"). They have well defined interactions.

I don't actually know what the original paper describing what algebraic effects are supposed to do is, I just know them informally from Koka, Effekt, etc.

Interesting, then I wonder if anyone has distinguished them from continuation "protocols" such as shift/reset and prompt/control. Thanks!

Bringing it back to my original point, I guess I'd say that if you already have function calls, exceptions and threading built in to the language then you don't need perform/resume except in niche cases (multi-shot continuations being the only case I know of, but I don't even know of many applications of those).

A real effect system allows you to do things like NOT continue execution after using the effect (like the error effect does - if you "implement" this by using Exceptions, you're not using effects at all, just using Exceptions with extra steps) or only continuing it after some asynchronous work happens (the Future effect), or even "continue" execution several times. That just cannot be done with "just passing stuff in". You still don't seem to have understood effects.

Thanks for your response. Perhaps I'm missing some fundamental things. Could you help?

> A real effect system allows you to do things like NOT continue execution after using the effect

Right, Bluefin's Request allows you to do that too. For example here is an example of handling the request by continuing or not, depending on what the value yielded to the Request is.

    example :: Either String ()
    example = runPureEff $ try $ \ex -> do
      forEach
        ( \r -> do
            request r True
            request r True
            request r False
            request r True
            request r True
        )
        ( \case
            True -> pure ()
            False -> throw ex "Stopped"
        )

> if you "implement" this by using Exceptions, you're not using effects at all, just using Exceptions with extra steps

Not sure I follow that. Above you can see I used an exception (Bluefin's Throw capability), but I couldn't have used only an exception because that would have aborted unconditionally. What am I missing here, that makes "using Exceptions" "not using effects at all"?

> only continuing it after some asynchronous work happens (the Future effect)

I'm not really sure what "a Future effect" is, but I don't see how it's not something that can be run as a function call, at least in Haskell.

> or even "continue" execution several times

Right, these are the multishot continuations which Bluefin doesn't support. I haven't discovered many particularly compelling use cases for multishot continuations but would be very interested in finding some. The developer of the Kyo effect system for Scala, Flavio Brasil, suggested parsing, with multiple parse results, which makes sense.

I'm also not entirely sure Bluefin couldn't simulate common use cases of multishot continuations with threads, but I haven't thought about it very hard.

> You still don't seem to have understood effects.

Possibly true, and part of my puzzlement! I'm always happy to try to improve my understanding. Can you help me see what I've missed?

I think the parent may be getting at the continuation aspect of effects? Effect systems make the stack a first class object you can reuse, I think a standard example is implementing a scheduler. I'm not familiar with your Bluefin library so maybe it already handles this:

  effect Sched =
    yield : unit -> unit
    fork  : (unit -> unit) -> unit
  end
  
  let mut run_queue = []
  let enqueue t = run_queue := List.concat run_queue [t]
  
  let dequeue () =
    match run_queue with
    | [] -> ()
    | t :: rest ->
      run_queue := rest;
      t ()

  let rec spawn task =
    handle
      task ()
    with
    | return _ -> dequeue ()
    | yield () k ->
      enqueue (fn () -> resume k ());
      dequeue ()
    | fork f k ->
      enqueue (fn () -> resume k ());
      spawn f

  let run main = spawn main

  let worker name steps =
    let rec loop i =
      if i > steps do ()
      else do
        print $"{name}: step {i}";
        perform yield ();
        loop (i + 1)
      end
    in
    loop 1
  
  let () =
    run (fn () ->
      print "main: starting";
      perform fork (fn () -> worker "A" 3);
      perform fork (fn () -> worker "B" 3);
      print "main: forked workers, now yielding";
      perform yield ();
      print "main: done")

output:

  main: starting
  A: step 1
  B: step 1
  A: step 2
  main: forked workers, now yielding
  B: step 2
  A: step 3
  main: done
  B: step 3

Ah yes, OK, I missed the point that the timeout is applied to the entire continuation, not just the part of the computation until the next await. Bluefin can't currently do that. I think I could make it do that, using the same implementation strategy as awaitYield (fork a thread, communicate through an MVar) but I wonder what the point is, given that Bluefin allows you to run the continuation at most once. Is the use case of "run the continuation in a modified environment (e.g. with a timeout)" really that compelling? Maybe it is! But I don't see it yet.

On the other hand, I don't see any difficulty with implementing a scheduler using Await/Yield. I don't think it needs access to the full continuation.