Worked examples with algebraic effects

I've been trying to understand how algebraic effects work. Mainly I wanted to work some examples to build an intuition around them that is tangible. So here we go:

There are a few programming languages that have support for algebraic effects:

Ocaml (>=5.0), haskell (sort of?) and scala(>=3.1) are probably the most mainstream (which tells you a lot about how popular this paradigm is..) langages to implement a version of algebraic effects. As a note, afaict the ocaml type system doesn't yet actually support checking effects yet.

I want these examples to be easy to understand and motivated by some real world examples, and I have an existing link management project written in ocaml.

Link managers are simple, you create a "redirect" which specicies where someone who hits a link should be subsequently sent.

Here is an example of a database entry:

[Entry-1]
id: 1
to: https://mattcarroll.net
from: https://mylinktracker.com/mattcarrollnet

so when someone arrives at https://mylinktracker.com/mattcarrollnet, we lookup the route in the database and redirect accordingly.

slug = extract the slug from the url
redirect_instructions = find slug in the database

if redirect_instructions exist:
   redirect the request
else:
   respond with not found

let handle_slug req =
  let slug = Dream.param req "slug" in
  let r =
    match Db.find_redirect ~slug with
    | Some _ as r -> r
    | None -> None
  in
  match r with
  | None   -> Dream.respond ~status:`Not_Found "Link not found"
  | Some r -> do_redirect req r

this code includes a few concerns. We need the request to be what Dream expects, we need the database to be available and healthy, and then we need to make another http request (the redirect).

compare to below, where we define an effect:

define an effect that can
  1. find a new redirect
  2. perform the redirection
  3. say that we failed to find a redirect

type _ Effect.t +=
  | Find_redirect : string -> redirect option Effect.t
  | Redirect : redirect -> Dream.response Effect.t
  | Not_found : string -> Dream.response Effect.t

and then use the effect to handle the actual business logic:

let handle_slug slug =
  match Effect.perform (Find_redirect slug) with
  | Some redirect ->
      Effect.perform (Redirect redirect)
  | None ->
      Effect.perform (Not_found "Link not found")

we still need to actually write code somewhere that "handles" the implementation of these effects right? I never actually expressed how we find a redirect, I have sort of only spoken in abstracts.

we can think about this as a conversation:

example 1:

example 2:

to implement the "Steve" version, I may write something like:

let production_slug_handler slug =

  match_with handle_slug slug
  {
    retc = (fun response -> response);

    exnc = raise;

    effc = fun (type a) (eff : a Effect.t) ->
      match eff with
      | Find_redirect slug ->
          Some (fun (k : (a, _) continuation) ->
            let result = Db.find_redirect ~slug in
            continue k result
          )

      | Redirect redirect ->
        ...


      | Not_found msg ->
        ...

      ...
  }

And Jackie:

let test_slug_handler slug =

  match_with handle_slug slug
  {
    retc = (fun response -> response);

    exnc = raise;

    effc = fun (type a) (eff : a Effect.t) ->
      match eff with
      | Find_redirect slug ->
         # todo make this testing

      | Redirect redirect ->
        ...


      | Not_found msg ->
        ...

      ...
  }

this is like a really simple example. how is this different than dependency injection? or mocking?

at this point, it's really not.

we can just pass in fuctions:

let handle_slug fetching_function redirect_function raise_not_found_function =
   ...
   same orchestration as the effect code

then just make test and prod specific functions, and pass those into the orchestor.

ok, so what is the proported benefit of all of this? passing functions as arguments is pretty much table-stakes in almost every modern programming language.

imagine we want to also send an email when someone clicks on my link:

click link ->
find redirect in db ->
send email to me that link was clicked ->
send user to new link

there are a lot of potential implementations for the send email functionality:

we could 1. make a best effort attempt at sending the email:

| Send_click_email redirect ->
    Some (fun k ->
      try
        Email.send redirect;
      with _ ->
        Logs.warn "Couldn't send email";

      continue k ()
    )

we could 2. queue the email

try:
  Some (fun k ->
      Job_queue.push (SendEmail redirect);
      continue k ()
    )

we could 3. explode if the email is not sendable

| Send_click_email redirect ->
    Some (fun k ->
      match Email.send redirect with
      | Ok () ->
          continue k ()
      | Error e ->
          Dream.respond
            ~status:`Internal_Server_Error
            "Couldn't send notification"
    )

version 1 and 2 both look like this:

click link ->
find redirect in db ->
send email to me that link was clicked ->
send user to new link

version 3 looks like this:

click link ->
find redirect in db ->
send email to me that link was clicked ->
(~send user to new link~) responded with an error

in some ways this is like spooky action at a distance. we are changing the control flow via the handler itself, even thought the actual "pipeline" business logic remains the same, but thats not too different than general dependecy injection.

basically the handler gets to "Decide" what we are doing with the rest of the computation. i.e we may run a bunch of code before we continue on with the rest of the program. we may decide to entirely bail (akin to raising a fatal exception) etc.

i think i'm probably doing the power of algebraic effects a diservice here, as they likely enable way more that im failing to understand.