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. ^.^
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
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
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:
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.
Python generators are an Algebraic Effect, they both send data and receive it back, though they are not multi-resumeable.
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.
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.
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 )
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.
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).
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).
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
)
