Status of user defined effects and handlers?

[stephentetley]

What is the status of user defined effects and handlers?

This has become rather an active issue for me as unchecked_cast changed between versions 0.37.0 and 0.38.0 so my GradedLib of graded functors, applicatives and monads no longer works. Using casts to help constructors capture effects was always a bit unseemly so I'm not clamoring for old behavior to be reactivated but I am wondering what to do for my libraries that depended on GradedLib in the meantime until we have user defined effects.

[magnus-madsen]

CC @JonathanStarup

We have been working on it for about two months, but with little progress. However, just recently we figured out what the major steps are. Unfortunately, I think it will take 2-6months before we have something working.

What the status on the graded lib, i.e. what's the blocker / breaking change? We are currently looking into associated type aliases which may offer an alternative solution. If you DM me on Gitter a can send a bit more information.

[magnus-madsen]

Can you remind again where the casts show up? I have something like:

enum State[s: Type, ef: Eff, a: Type] {
    case State(s -> (s, a) \ ef)
}

def smap(f: a -> b \ ef2, ma: State[s, ef1, a]): State[s, {ef1, ef2}, b] =
    match ma {
        case State.State(g) => 
            def run(x) = {
                let (s, a) = g(x);
                (s, f(a))
            };
            State.State(run)
    }

def sflatMap(f: a -> State[s, ef1, b], ma: State[s, ef2, a]): State[s, {ef1, ef2}, b] =
    match ma {
        case State.State(g) => 
            def run(x) = {
                let (s, a) = g(x);
                let State.State(h) = f(a);
                h(s)
            };
            State.State(run)
    }

class MyFunctor[m: Eff -> Type -> Type] {
    pub def map(f: a -> b \ ef1, ma: m[ef2, a]): m[ef1 + ef2, b]
}

instance MyFunctor[State[s]] {
    pub def map(f: a -> b \ ef1, ma: State[s, ef2, a]): State[s, {ef1, ef2}, b] = smap(f, ma)
}

def print(s: String): State[Unit, IO, Unit] = State.State(_ -> ((), println(s)))

[stephentetley]

Thanks Magnus

The typical way I've been writing graded monads is here:

https://github.com/stephentetley/graded-lib/blob/master/src/Graded/Codensity.flix

I had been casting the constructor (e.g. line 65) which is now a runtime cast error in v0.38.0 and above. The monads are all written in the codensity style to be stack safe - I think I'm correct in saying Codensity is the Identity monad in CPS. I had envisaged needing only one or two of the monads as State, Reader etc. could be effects once we can write them in Flix. Casting the constructor was quite easy while it worked.

I've managed to code map and flatMap of the Codensity monad in the style you wrote + unchecked_cast as the codensity style requires the more complexity in the run body. This seems to avoid the runtime cast error but the cost is severe complexity.

// file: Codensity.flix


mod MonadLib {

    ///
    /// Just a Codensity monad graded with an effect
    ///
    pub enum Codensity[ka: Type, ef: Eff, a: Type]((a -> ka \ ef) -> ka \ ef)



}

mod MonadLib.Codensity {


    use MonadLib.Codensity
    use MonadLib.Codensity.{Codensity}


    ///
    /// Run Codensity
    ///
    pub def runCodensity(ma: Codensity[a, ef, a]): a \ ef =
        let Codensity(f) = ma;
        let cont = a -> checked_ecast(a);
        f(cont)

    pub def point(x: a): Codensity[ka, ef, a] = 
        Codensity(k -> k(x))


    pub def map(f: a -> b \ ef1, ma: Codensity[ka, ef, a]): Codensity[ka, ef + ef1, b] =
        match ma {
            case Codensity(g) => {
                def run(k) = unchecked_cast(g(a -> {let b = unchecked_cast(f(a) as _ \ ef); unchecked_cast(k(b) as _ \ ef)}) as _ \ ef + ef1);
                Codensity(run)
            }
        }

    pub def flatMap(f: a -> Codensity[ka, ef1, b] \ ef2, ma: Codensity[ka, ef, a]): Codensity[ka, ef + ef1 + ef2, b] =
        match ma {
            // g = (a -> ka \ ef) -> ka \ ef
            case Codensity(g) => {
                def run(k) = unchecked_cast(g(a -> {let Codensity(h) = unchecked_cast(f(a) as _ \ ef); unchecked_cast(h(b -> unchecked_cast(k(b) as _ \ ef1)) as _ \ ef)}) as _ \ ef + ef1 + ef2);
                Codensity(run)
            }
        }

    pub def cprint(s: String): Codensity[ka, IO, Unit] = 
        Codensity(k -> {println(s); k()})


}

// file: TestCodensity.flix

use MonadLib.Codensity.{runCodensity, map, flatMap, point}

@test
def test01(): Int32 = 
    runCodensity(point(9))

@test
def test02(): Int32 \ IO = 
    runCodensity(map(x -> {println(x); x + 1}, point(9)))

@test
def test03(): String \ IO = 
    runCodensity(flatMap(x -> {println(x); point("zero")}, point(9)))

[magnus-madsen]

I am still thinking about this. I suspect one issue is that in the definition of Codensity you have two functions (or rather its a curried/higher-order function) where one of them is increasing in its effects which requires sub-effecting.

[magnus-madsen]

Unfortunately we had to fix the old cast mechanism; it was simply broken and did not enable us to generate the code we need to add handlers. But as side-effect we probably broke your code :/

[magnus-madsen]

From a practical standpoint, what would be downside -- as a temporary measure -- to simply assign the functions inside Codensity the IO effect?

[stephentetley]

Thanks Magnus - I can get by with considerable fewer casts if I use IO iternally. I'll probably try and convert GradedLib to this style over the weekend.

mod MonadLib {

    ///
    /// Just a Codensity monad graded with an effect
    ///
    pub enum Codensity[ka: Type, _ef: Eff, a: Type]((a -> ka \ IO) -> ka \ IO)



}

mod MonadLib.Codensity {


    use MonadLib.Codensity
    use MonadLib.Codensity.{Codensity}


    ///
    /// Run Codensity
    ///
    pub def runCodensity(ma: Codensity[a, ef, a]): a \ ef =
        let Codensity(f) = ma;
        let cont = a -> checked_ecast(a);
        unchecked_cast(f(cont) as _ \ ef)

    pub def point(x: a): Codensity[ka, ef, a] = 
        Codensity(k -> k(x))


    pub def map(f: a -> b \ ef1, ma: Codensity[ka, ef, a]): Codensity[ka, ef + ef1, b] =
        match ma {
            case Codensity(g) => {
                def run(k) = g(a -> {let b = unchecked_cast(f(a) as _ \ IO); k(b)});
                Codensity(run)
            }
        }

    pub def flatMap(f: a -> Codensity[ka, ef1, b] \ ef2, ma: Codensity[ka, ef, a]): Codensity[ka, ef + ef1 + ef2, b] =
        match ma {
            // g = (a -> ka \ ef) -> ka \ ef
            case Codensity(g) => {
                def run(k) = g(a -> {let Codensity(h) = unchecked_cast(f(a) as _ \ IO); h(b -> k(b))});
                Codensity(run)
            }
        }

    pub def cprint(s: String): Codensity[ka, IO, Unit] = 
        Codensity(k -> {println(s); k()})


}

I didn't realize increasing the effect in map and flatMap would require sub-effects to do without cheating. I was quite excited about graded monads for "scripting effects" as we would be able to keep all the nice functor-applicative-monad combinators like <*, *>, foldLeftM, Traversable.sequence etc. but I'm not so sure now. I did notice that Koka doesn't seem to miss them and combines effects with multiple with clauses.

[magnus-madsen]

I think its because when you build the new continuation it does not have the same effect as the current continuation. You seem to have previously resolved this by casting to a super-type, but that unfortunately no longer works.

[magnus-madsen]

I think using IO everywhere is a reasonable "intermediate step" until we get a better handle on things.

As for map, foldLeft, traversable, we are looking into associated effects as a solution. But I am not sure it gets us all the way there. We are currently both implementing and writing on this.

[magnus-madsen]

In addition to this, algebraic effects (when they finally arrive), may also provide a solution.

[magnus-madsen]

I actually had something more like:

enum Codensity[ka: Type, a: Type]((a -> ka \ IO) -> ka \ IO)

pub def map(f: a -> b \ ef1, ma: Codensity[ka, a]): Codensity[ka, b] =

In mind.

(I understand this is like disabling effect tracking or "programming with java.lang.Object everywhere")

[magnus-madsen]

@stephentetley Unofficially support is starting to arrive. I am writing up a document with what works and what does not. If you swing by Gitter I can share it with you. Officially we are not announcing this feature until more infrastructure and tests are in place.

[stephentetley]

Thanks Magnus, I'm busy for the next few days, but I will check Gitter later in the week.