Flora's effect handlers

03 June 2024
@Quelklef asked:

how are floras effects implemented?

specifically i’m wondering if code being “effectful” means that it emits effects (ala haskell) or that it consumes effect handlers (ala effekt)

It’s actually really simple! They use CPS.

If you had a pure language without effects, your top-level eval function might have a type that looks something like this

eval :: String  -> Value
syntax highlighting by codehost

but in Flora, this type is (roughly equivalent to)

eval :: String -> EvalResult

data EvalResult
  = Completed Value
  | Effect String [Value] (Value -> EvalResult)

So from an API standpoint, what is happening is that evaluating an expression either returns or performs an effect (which returns the name of the effect, its arguments and a continuation) and so the host language can handle the effect by just matching on this EvalResult.

Actually, the full type is closer to

eval :: String -> Fuel -> EvalResult

data EvalResult
  = Completed Value
  | Effect String [Value] (Value -> EvalResult)
  | Suspended (() -> EvalResult)

because there is also fuel system that can preempt long running computations, which slots in extremely nicely with effect handlers and works in practically the same way!

So what does that look like under the hood?

Internally, evaluation is entirely in CPS, so usually functions will never return but will only pass on or tail call into a continuation, which looks like this

eval :: Env -> Expr -> (Value -> EvalResult) -> EvalResult
eval env (Var x) cont = cont (findVariable x env)
eval env (App funExpr argExpr) =
    eval env funExpr \funValue ->
        eval env argExpr \argValue ->
            case funValue of
                Closure closureEnv param body ->
                    eval (define param argValue closureEnv) body

Where whatever runs this at the top level wraps the result in a Completed

evalFinal :: Env -> Expr -> EvalResult
evalFinal env expr = eval env expr (\result -> Completed result)

But, if the called code performs an effect, eval just returns immediately and passes the continuation on to the caller

eval env (Perform effectName argumentExprs) cont =
    evalAll argumentExprs \arguments ->
        Effect effectName arguments cont

On its own, this will immediately return the effect to the host-language, but if we have a handler we need to intercept the Effect result first and run our handler on it.

eval env (Handle handler expr) cont =
    case eval env expr (\x -> Completed x) of
        Completed x -> cont x
        Effect name arguments cont ->
            case findHandler name handler of
                 Nothing -> Effect name arguments cont
                 Just (params, body) ->
                     -- I'm handwaving some of the error handling away ^^
                     eval env (defineAll (zip params arguments) env) body cont

And that’s it! This should be pretty fast and it’s also roughly how ContT implements its delimited continuation operations I think. What’s nice about this is how handling effects in the host language works in almost the same way as handling them in flora itself so embedding programs is pretty nice.

So to answer your question: this is emitting effects like in Haskell or OCaml. I’m guessing by “consuming the handler” you mean what Koka does where it passes the handler implementation along and then calls the right handler right at the call site of perform? I’m not sure how well that would work here since you also want to be able to handle effects from the host language. You could pass in a handler, but that would limit its expressivity a little since the emitting approach doesn’t need to know the set of valid effects up front.