Single value cache

[schicks]

I'm trying to create an effect that can cache a single value. The use case is a dynamic algorithm where we can skip a lot of work by caching the output for the largest input we've seen so far. My thought is that this could be an effect like this;

effect cached<a, b> {
    control cached(key: a, value: optional<b>): ()
}

which would resume with the value if given or the cached value if the key matched or nothing.

I tried to implement the handler like this;

var cache := None
    with control cached(key: int, value: optional<double>) {
        val new-cache: optional<(int, double)> = match (cache, value) {
            (None, None) -> None
            (None, Optional(n)) -> Optional((key, n))
            (Optional((old-key, _)), Optional(n)) -> if (key > old-key) then Optional((key, n)) else cache
            (Optional(_), None) -> cache
        }
        cache := new-cache
        resume(match (cache, value) {
            (_, Optional(n)) -> Optional(n)
            (Optional((old-key, n)), _) -> if (key == old-key) then Optional(n) else None
            _ -> None
        })
        ()
    }

but the compiler is giving me an error that I'm having trouble parsing.

error: types do not match
  context      :     with control cached(key: int, value: optional<double>) {
                 ...
                     }
  term         :                  cached(key: int, value: optional<double>) {
                 ...
                     }
  inferred type: std/core/hnd/clause2<int,optional<double>,optional<double>,_b,<exn,local<_h>|_e1>,()>
  expected type: std/core/hnd/clause2<int,optional<double>,(),.hnd-cached<int,double>,_e,_a>

Can I get some help understanding this error message? is there something obviously wrong about the implementation?

[anfelor]

I think the problem is that you declare the handler to return () without any effect and then resume in your handler by giving an optional<double> (the return type of the operation should match the value you give to resume). Furthermore you use a local variable that was declared outside of our handler which gives you the local<_h> effect and for some reason the compiler also gives you a exn effect. I think you can read this from the error message:

inferred type: std/core/hnd/clause2<int,optional<double>,optional<double>,_b,<exn,local<_h>|_e1>,()>
expected type: std/core/hnd/clause2<int,optional<double>,(),.hnd-cached<int,double>,_e,_a>
               input type, output type, something?, effect, something?

To fix this you should avoid using a local variable here and use a ref because those can be passed around between functions.

[schicks]

Why does the return value have to be the same type as resume? Don't they go to different places?

[anfelor]

It is somewhat confusing, but the return type of a handler should be the type of the value in resume() while the type of the returned value of the handler should be the type of the surrounding function. Maybe this program clarifies things:

effect ret-res {
    control res(i : int): int
}

fun use-ret-res(i : int): ret-res int {
    res(i) + 1
}

fun test(i : int): either<int, bool> {
    with control res(j : int) {
        if (j == 0) then resume(3) else Right(False)
    }
    Left(use-ret-res(i))
}

fun show-either(e : either<int, bool>) {
    match(e) {
        Left(i) -> show(i)
        Right(b) -> show(b)
    }
}

fun main() {
    println(show-either(test(0))) // outputs "4"
    println(show-either(test(1))) // outputs "False"
}

As you can see our handler resumes with an int but returns an either<a, bool>.

[anfelor]

Contradicting my previous advice, I think you can keep using a local variable though. Or you could start from the state effect and try to modify it to suit your needs.

[schicks]

So the state handler actually has a pretty direct application, so I ended up using that unmodified with the value of the cache being optional<(int, double)>. Unfortunately the caching didn't help performance at all, but I think I understand better now. Thanks!