algebraic effects for PHP

the last couple weeks i've been working on effect-system-php, a PHP library that implements algebraic effects in PHP, backed by generators.

if you aren't familiar with algebraic effects, i strongly recommend reading through Algebraic Effects for the Rest of Us by Dan Abramov. it explains effect systems using a made up Javascript language extension, which should make it easy to understand.

in short, you can think of algebraic effects as a generalization of try/catch, but with the ability to resume function execution from where the "exception" was raised. this means you can write something like $my_value = throw new MyException($other_value), and then in the catch block you are provided a way to "return" to the function with a value, which will get assigned to the $my_value variable.

let's see a basic example of how this looks in practice when using effect-system-php. we can define an effect by declaring a class that extends Effect:

use Versary\EffectSystem\{Effect, Handler};

class AddNumbers extends Effect {
    public function __construct(public int $a, public int $b) {}
}

here, we are declaring an effect called AddNumbers that takes in 2 integers as parameters. notice how the effect itself doesn't perform any computation, it just stores the numbers. the actual computation is performed in effect handlers, which we define by declaring a class that extends Handler:

class AddNumberHandler extends Handler {
    // effect handled by this Handler
    public static $effect = AddNumbers::class;

    public function resume(mixed $effect) {
        return $effect->a + $effect->b;
    }
}

in this case, we're declaring a handler that simply adds both numbers together. now that we have declared both our effect and a handler for it, we can write a function that uses said effect:

function my_function() {
    $v = yield new AddNumbers(3, 7);
    // $v is 10 here
    return $v * 2;
}

remember how i said we'd write something like throw? this is it. yield is part of PHP's Generators, which allow functions to "return" multiple values. effect-system-php uses this feature to pass effects up the callstack, where the computation can be performed. because of this, calling this function will actually return a \Generator object instead of 10. we need a way to run this generator to completion while handling the effects yielded.

for this, we use two functions: Effect::handle(\Generator $generator, Handler $handler) and Effect::run(\Generator $generator). the former lets us to tie a Handler to an effectful function, and the latter actually runs the function and its handlers:

function run_my_function() {
    // wrap `basic` with a handler for `AddNumbers`. No code has run yet here.
    $gen = Effect::handle(my_function(), new AddNumberHandler);
    // run the function to completion, handling all effects.
    $result = Effect::run($gen);

    assertEquals(20, $result);
}

in the previous example, we declared a handler that overrides the resume(mixed $effect) function. this is not the only function we can override in Handler. handle(mixed $effect, \Closure $resume) is a more powerful tool, which allows us to perform advanced control flow.

resume is conceptually simple: it takes in a mixed $effect argument, and whatever value gets returned will be used as the result of the effect. on the other hand, handle takes in a mixed $effect and a $resume closure, which in turn takes in a single argument. calling this closure will resume execution of the function from the point at which the effect was yielded. the value passed to $resume is what the effect will return.

for a more practical example, here's how AddNumberHandler would look like if we wrote it using handle instead of resume:

class AddNumberHandlerByHandle extends Handler {
    public static $effect = AddNumbers::class;

    public function handle(mixed $effect, \Closure $resume) {
        yield from $resume($effect->a + $effect->b);
    }
}

we have to yield from because $resume is also a generator that will yield effects, which we have to bubble up so they can be handled.

the main strength of handle is that we get to decide how and when to call this closure. we can execute some code before or after resuming, or we can even choose to not call the closure, aborting execution of the effectful function.

you might notice something: we are not returning $resume's result, but yielding it instead. this is because of the next important aspect of handle: any returned value will be used as the return value of Effect::run. let's see an example.

we'll declare a new effect, and a handler which returns a string from its handle method:

class DivideByZero extends Effect {}
class DivideByZeroAbortHandler extends Handler {
    public static $effect = DivideByZero::class;

    public function handle(mixed $effect, \Closure $resume) {
        return 'tried to divide by 0 :(';
    }
}

then we'll declare an effectful function that yields this effect:

function division(int $a, int $b) {
    if ($b === 0) yield new DivideByZero;

    return $a / $b;
}

function my_calculations() {
    $x = yield from division(6, 2);
    $y = yield from division(1, 0);
    return $x + $y;
}

and finally we can run our effectful function:

function calculate_division() {
    $result = Effect::run(Effect::handle(my_calculations(), new DivideByZeroAbortHandler));
    assertEquals('tried to divide by 0 :(', $result);
}

let's walk through the execution of this function: in the $x case, division doesn't yield any effects. DivideByZeroAbortHandler never gets invoked, and division executes normally.

in the $y case, we have $b === 0, so division yields a DivideByZero effect. DivideByZeroAbortHandler gets called, doesn't resume execution, and instead returns 'tried to divide by 0 :(', and the result of the Effect::run call is 'tried to divide by 0 :('. we never reach the $x + $y statement.

in calculate_division, we handled the DivideByZero effect by simply returning from the handle function in DivideByZeroHandler. this allows us to abort execution of my_calculations halfway through. but what happens if we write a handler that resumes execution instead?

class DivideByZeroResumeHandler extends Handler {
    public static $effect = DivideByZero::class;

    // when we encounter a division by 0, resume with 0
    // (written with `resume`, since we don't need anything else)
    public function resume(mixed $effect) {
        return 0;
    }
}

we can then apply one small change to division: we add return before the yield:

function division(int $a, int $b) {
    // note the added `return`
    if ($b === 0) return yield new DivideByZero;

    return $a / $b;
}

// same as before, here again as a refresher
function my_calculations() {
    $x = yield from division(6, 2);
    $y = yield from division(1, 0);
    return $x + $y;
}

if we now run my_calculations() with DivideByZeroResumeHandler, yielded DivideByZeros will be resumed with 0. this means that on the $y case, the result of yield new DivideByZero is 0, so division returns 0, and so $y is set to 0. function execution then continues, $x + $y runs, and the function returns 3.

we've implemented a try/catch system, but we can go further, and also implement finally. we'll declare an effect that takes in a single closure, and a handler for it:

class Finally extends Effect {
    public function __construct(public \Closure $closure) {}
}

class FinallyHandler extends Handler {
    public static $effect = Finally::class;

    public function handle(mixed $effect, \Closure $resume) {
        // continue execution of the function
        yield from $resume();

        // after the rest of the function has executed, run the closure
        ($effect->closure)();
    }
}

this handler calls $resume to run the function to the end, and then calls the closure in the effect. we can use it like this:

$v = 0;

function program() {
    $v = 1;

    yield new Finally(fn () => $v = 3);

    // the closure has not run yet
    assertEquals(1, $v);
}

public function run_program() {
    Effect::run(Effect::handle(program(), new FinallyHandler));

    // the program has finished executing, and all `Finally` closures have run
    assertEquals(3, $this->v);
}

this is similar to a defer statement that languages like Go or Zig have, that make the given code execute at the end of the function¹. and we get this for free with our effect system!

we've seen how an effect system gives us really fine grained control over program execution. by choosing how and when we call $resume, we can get really interesting behaviors basically for free.

it's a fair question to ask! after all, $resume is a function, and in PHP we expect functions to be callable as many times as we want ². and usually, effect systems in other languages do allow resuming multiple times, like in Koka.

sadly, resuming multiple times is not supported in effect-system-php. in order to resume multiple times, we'd need to be able to resume the same generator multiple times from the same spot. this could be achievable by either cloning a generator right before resuming it, so that we can always clone it again and resume it from that same spot; or by rewinding the generator back to the previous position, in order to resume it from the same spot. sadly, PHP generators are not cloneable nor are they rewindeable.

as it stands, effect-system-php throws an exception if you try to resume multiple times.

php allowed generator cloning at one point (in php 5.4 beta 2), but it got removed due to some difficulties with the implementation (some sort of unsoundness).

now, i recently learned that PHP allows us to write extensions in C. and if there is one thing i know about C, is that we can just do whatever the fuck we want, like for example copy some memory from one spot to another, without caring about silly things like "soundness" or "not hitting segmentation faults". so, in my infinite naiveness and hubris, i'm convinced i can implement a half-broken C extension that implements generator cloning. at least one that works well enough to make a couple tests pass.

i've started implementing one, but it's my first time messing with PHP internals so i'm a bit lost. if you know about PHP internals and/or you'd be interested in helping out, here's the work in progress. so far it immediately segfaults.

this was mostly a for-fun little experiment, it's probably not a great idea to use this library for anything important. i haven't tested it too much, and i'm unsure about the performance characteristics of turning all of your code into generators and continuations. i'm guessing it's not great.

if you do use this (against my strong discouragement), please do let me know! i'm also open to contributions if you find any bugs or things to improve.