ElixirEffects - a library that emulates algebraic effects in Elixir

I made a non-monadic Algebraic Effects library, just to see if I could (tl;dr yes I was mostly able to, but the lack of cloneable and returnable continuations on the BEAM limits it a bit), can see the (surprisingly trivial) code at:

See the readme for more details, but in essence you can do something like define a State effect like:

defmodule State do
  import ElixirEffects

  defmodule Get do
    ElixirEffects.defeffect
  end

  defmodule Set do
    ElixirEffects.defeffect [:value]
  end

  def get, do: perform %Get{}
  def set(value), do: perform %Set{value: value}

  def run(init, fun) do
    run_effect init, fun.() do
      state, %Get{} -> {:return, state}
      state, %Set{value: new_state} -> {:return, new_state, state} # Return old state
    end
  end
end

And you can use it like:

State.run 0, fn ->
  import State
  assert 0 = get()
  assert 0 = set(42)
  assert 42 = get()
  6.28
end

And of course the function can call other functions that call other functions that all can talk to the State effect. You can compose more effects together by just calling run’s inside run’s. And of course this makes it easy to test as you could take that same function and pass it to a testing version of the State effect to do specific testing without any need of mocking or passing in functions or anything.

No it is not really intended for use. Yes the BEAM needs to expose it’s CPS to user code for this to be properly powerful, but even as-is it is oddly useful. Regardless, I held myself to certain strict limitations to see if I could implement a full effects system (as much as possible, more so than monadic effects for sure) on elixir, and I’d say I succeeded in as much as the beam allows me to (to do more I’d need to manually transform everything in the callstack to CPS, blehg). It was fun. ^.^

6 Likes

I don’t know exactly what you’re talking about, but since you’re creating modules just to call defeffect, why not an API like this:

defmodule State do
  defeffect Get
  defeffect Set, [:value]
  ...
end

Or would you like to do other things inside tbe Get or Set modules?

1 Like

defeffect is just delegating to defexception, and yep you could easily have other functions on them (useful constructors and such). Although a defeffect/2 could be an interesting addition if I intended for this to be fleshed out. ^.^;

@OvermindDL1 I know it’s an old thing. But I’m taking a shot at implementing Algebraic Effects for Elixir as well with a little bit different twist - all of current side effects in Elixir automatically being Algebraic Effects.
I noticed you don’t implement k as for continuations in your library.
Do you know what are specific advantages to having continuations? I’ve hit a wall trying to implement them. Not an easy task

1 Like

Yep, All of the side effects that the beam can do are indeed representable by algebraic effects. ^.^

It is possible but not something I’ve done, it would require performing manual CPS transformations over all code that can possibly call an algebraic effect, which is a bit irritating to write but not overly difficult (and something the beam already does, I wish I could hook in to it…). Are you performing a CPS transformation yet?

That’s the idea. Feel free to put in any of your thoughts in the projects issues:

Are you performing a CPS transformation yet?

Nope. I decided it’s too little bang for the buck here for implementing that.
So far I’m trying to do the Algebraic Effects with handlers and project wide effects inference.
So that effect specifications fail at compile time if you specify them wrong. So far it’s going really good :tada:

1 Like

A super simple example of an algebraic effects is something like (this example will work in OCaml when using the algebraic effects fork), this is the classic memoization algebraic effect:

Implementation:

module Memo : sig

  val memoize : ('a -> 'b) -> ('a -> 'b)
  val cut : unit -> unit

end = struct

  effect Cut : unit
  let cut () = perform Cut

  type ('a,'b) cache_entry =
    {input : 'a;
     mutable cont : unit -> 'b}

  let memoize f =
    let cache = ref None in
    fun x ->
      try
        match !cache with
        | Some {input; cont} when x = input -> cont ()
        | _ ->
            let err_msg = "Memoized function was not cut" in
            cache := Some {input = x; cont = fun () -> failwith err_msg};
            f x
      with
      | effect Cut k ->
          match !cache with
          | Some c ->
              let rec save_cont k () =
                c.cont <- save_cont (Obj.clone_continuation k);
                continue k ()
              in
              save_cont k ()
          | None -> failwith "impossible"
end

And let’s use it like this:

let print_succ x =
  Printf.printf "input change: %d\n" x;
  (* ......
   * expensive computation
   * .....*)
  Memo.cut();
  Printf.printf "Succ of %d is %d\n" x (x+1)

let memoized_print_succ = Memo.memoize print_succ

In essence you can put Memo.cut() into a function and it runs ‘up to’ that point as normal the first time, but each time the function is called again with the same arguments it continues ‘at’ that point, skipping everything before it, so running memoized_print_succ 0 will print input change: 0\nSucc of 0 is 1\n , but then running memoized_print_succ 0 again just prints only Succ of 0 is 1\n and will do so until a different argument is passed in (and you could easily change this implementation to remember more than just the latest used argument, say a map of entries or so, perhaps FIFO or Last-Used or so).

Without CPS I’m unsure how you would be able to compile a memoization algebraic effect (among most algebraic effects)? CPS is generally considered an absolute requirement for algebraic effects (well, CPS is a hard requirement for a lot of things).

Yeah. I was aware mostly of the memoization example and the one in which all of the effects (like logs) are reversed by calling the continuation before the rest.

How would one approach CPS in Elixir though? I mean without manual manipulation of the code. Automated code walking is not a problem since my library (compiler extension?) already does it. But I’m completely clueless on how to transform code to CPS on an existing codebase.
For instance

Enum.map(list, fn a ->
  IO.puts(a)
end)

I’m not aware of how it’s possible to return continuations after each call of the IO.puts effect without rewriting Enum.map.

Currently it seems like the Algebraic Effects without continuations already have a lot of advantages. Easiness of writing mocks, new log processors and enforcing purity for example. But I can imagine CPS would add a bunch atop of this

That’s exactly what would have to be done, CPS tends to have to be either program-wide, or as an attribute on functions to mark them for the transformation (of which you can then not pass CPS functions to non-CPS).

If only there were a way to duplicate the running state of an actor on the BEAM… ^.^;

As it is though it’s not effects, it essentially has the same capabilities as the Mox library or a few other like that.

Think of it this way as a set of examples:

  1. Exceptions are Algebraic Effects that don’t return back to the caller (they are non-resumeable continuations essentially). You can implement exceptions as an algebraic effect that just doesn’t resume the continuation.
  2. Python generators are an Algebraic Effect, they both send data and receive it back, though they are not multi-resumeable.
  3. Stackless Python has full multi-resumeable continuations (via cloning, like in OCaml), it allows the full range of algebraic effects capabilities (though don’t think anyone’s written a library for that in it yet? It has full cloneable continuations and if you have those you generally don’t need algebraic effects as those are on an even higher level).

In fact, let me make that memoizer in stackless Python right quick:

╰─➤  python -i
Python 3.5.4 Stackless 3.1b3 060516 (default, Apr 30 2019, 11:28:36) 
[GCC 8.1.0] on linux
Type "help", "copyright", "credits" or "license" for more information.
>>> from stackless import getcurrent, tasklet
>>> import pickle
>>> 
>>> memo_base = None
>>> def cut():
...   global memo_base
...   memo_base.run()
... 
>>> def memoize(f):
...   p = [None, None]
...   def _m(x):
...     global memo_base
...     memo_base = getcurrent()
...     if p[0] != x or p[1] == None: # Setup
...       t = tasklet(f)(x)
...       t.run()
...       p[0] = x
...       p[1] = pickle.dumps(t)
...       t.run()
...     else:
...       pickle.loads(p[1]).run()
...     memo_base = None
...   return _m
...   
... 
>>> 
>>> def print_succ(x):
...   print("input change: %d" % (x))
...   cut()
...   print("Succ of %d is %d" % (x, x+1))
... 
>>> memo_print_succ = memoize(print_succ)
>>> 
>>> memo_print_succ(0)
input change: 0
Succ of 0 is 1
>>> memo_print_succ(0)
Succ of 0 is 1
>>> memo_print_succ(0)
Succ of 0 is 1
>>> memo_print_succ(1)
input change: 1
Succ of 1 is 2
>>> memo_print_succ(1)
Succ of 1 is 2

Not done via algebraic effects, instead it is done via full continuations (you can implement algebraic effects on top of full continuations, you cannot do the opposite), but the code is almost the same.

In fact, the BEAM’s actor model can be implemented via algebraic effects, and with something that can ‘halt’ an effect continuation after a certain number of ‘reductions’ (as the BEAM calls it), then you can duplicate BEAM’s style of OTP with full pre-emption and proper sharing of resources (Unlike Rust’s actix, or java’s or C++'s libraries, which are all cooperatively scheduled for example), thus meaning you could implement all of the BEAM’s style of concurrency, the pre-emption and actor model to build up the OTP in another language, and Stackless Python has all these capabilities, thus you could implement OTP in full in stackless python (excepting that you can call ‘unsafe code’ pretty easily, but as long as you kept to the model…), and in fact I did in stackless python for old Python 2.4 way way back in the day with node communication. I had a few extra features like the ability to duplicate a running process and even able to fully migrate processes across node’s (neither of which the BEAM can do) thanks to stackless python’s ability to serialize a full continuation state. :slight_smile:

With a full CPS transformation (not just simple trampolines and so forth) you could gain the same features on the beam. It would mean function calls would be slowed down by roughly 50% overall though, which is not actually even remotely bad compared to how much it slows down other languages when used:

##### With input types #####
Name                     ips        average  deviation         median         99th %
Direct               22.72 M      0.0440 μs    ±74.66%      0.0420 μs      0.0590 μs
Direct-Apply         22.24 M      0.0450 μs     ±9.59%      0.0430 μs      0.0600 μs
Anon-Closure         15.49 M      0.0646 μs   ±197.02%      0.0600 μs       0.130 μs
Anon-Module          14.31 M      0.0699 μs     ±8.61%      0.0660 μs      0.0950 μs
Anon-Empty           13.66 M      0.0732 μs   ±215.62%      0.0700 μs       0.150 μs
Indirect-Apply       12.68 M      0.0789 μs     ±9.50%      0.0760 μs       0.102 μs
Indirect             12.65 M      0.0790 μs     ±9.44%      0.0760 μs      0.0920 μs

Comparison: 
Direct               22.72 M
Direct-Apply         22.24 M - 1.02x slower
Anon-Closure         15.49 M - 1.47x slower
Anon-Module          14.31 M - 1.59x slower
Anon-Empty           13.66 M - 1.66x slower
Indirect-Apply       12.68 M - 1.79x slower
Indirect             12.65 M - 1.80x slower

So Direct* calls would become Anon-Closure or Anon-Module calls after a CPS transformation (depending on if state is being passed in or not).

Processes on the BEAM are already pure. Message passing is the only ‘effectful’ processing they can do and those are already an algebraic effect (if there was a way to clone an actor’s full state on the BEAM then you could implement algebraic effects on top of processes, though you can’t so…)

Already trivial, just dynamically compile code in the system, the Mox library already does that.

The logging library already handles that fine though? You can already dynamically replace code as needed too if you still need as the system can compile and load at any time.

Wow. Haven’t heard that name since reading on concurrent servers almost a decade ago (I think it was a book about EVE Online)

Theoretically that’s true. But I’d argue it has a lot of advantages to be able to categorise side effects and be able to explicitly access the list of effects a function uses (or rather ‘can use’).
That’d make testing isolation way easier alongside many other things, I can imagine.
A world with pure_test/1 where you are sure test’s body doesn’t leave any state behind is already a luxury worth pursuing.

Yeah, what my library does is mocking on steroids basically. Maybe with an advantage over other Mock libraries that it makes it possible to override Kernel functions (with an emphasis on Kernel.send/2)

I would consider adding CPS, but my ideal scenario for that project was to be able to use it in a project “for free”. While enforcing any manual modification to the codebase is usually a no-go in quality-of-life libraries

Lol, they used to use stackless python, but I think I recall hearing that they’ve since replaced it with a C/C++ system that basically does the same thing manually, for speed reasons… ^.^;

Stackless Python still exists and is updated to this day, most of it’s API exists in PyPy too!

That’s not really an algebraic effect system then, that’s more of a witness pattern (of which typeclasses are, for example, a simplified and restricted witness pattern, just as a side note, not that this usage is like typeclasses).

Algebraic Effects are about continuations, through and through. Much of it is inherently untypeable yet it remains type-safe, that is why it exists independently of things like ‘effect monads’ (to use a haskellism, haskell’s effect monads are impure witnesses is all they are).

With full CPS transformations there is nothing manual that needs to be done. :slight_smile:

Can it be done just by traversing code, without reimplementing everything from scratch?
I can’t think of a way to implement CPS out of the box for Elixir except for using it deliberately by the programmer which I want to avoid at all costs (these lazy bastards :wink: )
If there’s a way to traverse the code (as it already is in wende/efx) and make it CPS compliant just like that then the future is bright, I just can’t see it yet

The only practical solution I can think of is lazily unfolding the entire codebase, but that’s far from trivial to implement

Yes! That’s the point of CPS transformations actually. :slight_smile:

A CPS transformation can take effect in a couple of different ways, but the jist of it (not necessarily the most efficient, but still…, I’m modeling it in Elixir rather than a more traditionally low level structure, so I’m taking advantage of the BEAM’s TCO in this example) is to take every function call and instead of calling it you pass the continuation point into the function, so essentially this:

def do_stuff(a, b, c) do
  d = do_more(a, b)
  e = more_stuff(a, c, d)
  c + d + e
end

Gets transformed into this:

def do_stuff(a, b, ret_) do
  do_more(a, b, fn d ->
    more_stuff(a, c, d, fn e ->
      ret_.(c+d+e)
    end)
  end)
end

This is an extremely naive implementation with no optimizations and so forth, but this is a CPS transformation (oh I should also note what CPS is, it stands for Continuation Passing Style ). Conceptually the BEAM does this as well (although it does it via bytecode pausing instead as I recall).

In more of a native language CPS’s are performed via passing a function pointer and a pointer to it’s continued state together.

If you notice, the Javascript-hell people speak of async handlinger pre-futures is just a manually performed CPS, the async calls require CPS.

You could always just go over the code and transform it yourself, even the BEAM bytecode itself and transform it. Adding the continuations all over the place will slow down execution slightly but you can always make two code paths (one with and one without CPS) if you don’t mind double code generated (not like BEAM files take up much space anyway) and you only need to perform CPS on functions that are ‘pauseable’ (so if nothing is called in it or in anything it calls on down then no CPS transformation is necessary). Etc… etc…

CPS is actually a pretty fun exercise, I’ve implemented it in a few toy languages I’ve made. It unlocks so many capabilities and it can actually get pretty well optimized on native code (even CPU’s have gotten pretty good at the function pointer call instruction preloading, which they used to not be good at). :slight_smile:

But yeah, you’d need to transform the pre-existing code if you want to be able to call CPS transformed functions through it, and something like the Enum module is definitely one, so doing it generically on the beam bytecode itself is best (works with erlang too! which elixir is implemented in) but even just recompiling elixir with the transform would be sufficient for most uses… ^.^;

And as I gave in my benchmark earlier, an anon-closure as in this example was only 1.47x slower than a native direct call, so it’s not that much of a speed hit, though definitely not free (so if you can minimize it only to functions that need it…).

Do notice (if curious), CPS makes every call a tail call, meaning you can optimize out those calls to be stackless, meaning on native code it becomes a longjmp so no stack or function frames need to get set up at all, which can often make up “some” of the speed cost if you don’t mind losing the frame usefulness (which you can often encode it back into the ‘frame pointer’ continuation object too). :slight_smile:

Yeah, I’ve come to the very same conclusion thinking about it today.

Now I realise what you meant.
If I wanted to do CPS of a side effect inside a function passed to Enum.map/2 I’d have to traverse the code of Enum.map/2 itself and make it CPS compatible, not the code using it.
That makes it significantly more complex, but no less doable.

Seems like a fun exercise. Definitely worth a try. Cheers!
I’m sure I’ll report back when I implement it, or more likely even sooner :wink:

In ‘addition’ to the code that is passed in to it, if the function at any point is even remotely capable of calling something that requires CPS. :slight_smile:

I actually quite enjoy making CPS transformers, I keep meaning to on Elixir but just never got around to it yet. ^.^;

It’s pretty easy to write, just harder to write ‘efficiently’ (though it’s a lot easier on the beam than it is on native code). :slight_smile: