In-place mutation?

[dan-zheng]

Context

I'm not a Haskell expert, but I heard that Haskell has different monads for working with stateful mutation:

1. State monad represents functional updates s -> (a, s) and is implementable within Haskell.
2. ST and IO monads allow in-place mutation and have special compiler support to do so.

Both options seem like reasonable ways of representing state-mutating operations, but (2) seems likely to have some performance benefits?

Question

Does Koka (and its writer/state effects) support in-place mutation? What are the performance implications?

Unlike Haskell, Koka has first-class effects - from Koka's documentation, it seems like the state effect is just a composition of other effects. Not supporting special-case effects seems ideal for composition with other effects and control flow.

alias st<h> = <read<h>,write<h>,alloc<h>>

Stateful funs can manipulate heap h using allocations, reads and writes.

Koka does seem to have many neat representational and implementation optimizations though (e.g. inlining bind when possible), so maybe special-case optimizing performance of in-place mutation isn't a big concern.

[SchrodingerZhu]

There are several In-place mutation strategies in Koka. Not sure whether one of the followings is what you wanted:

1. Locally, koka has a variable syntax (like ocaml's ref but only works within the local scope):

   var a := 1
   a := a + 1

2. In a larger scope, there is a ref<h,a>. see also local-var v.s. ref

3. Moreover, Koka has a powerful Perceus reuse analysis.
   In the generated code, you can see something like:

   kk_sometype_t some_function(kk_sometype_t arg) {
       //...
       if (is_unique(arg)) {
         set_value_to(arg);
         return arg;
       } else {
         decrease_refcount(arg);
         kk_sometype_t res = allocate_new_instance();
         set_value_to(res);
         return res;
       }
   }

[dan-zheng]

Thanks @SchrodingerZhu, these resources are helpful!

Could you or someone comment on whether these in-place mutation strategies are baked into the Koka language/compiler in a similar sense to ST and IO in Haskell, if that makes sense? If the compiler does have knowledge of these, what do that knowledge and related optimizations look like?

[patrickmn]

Check out https://koka-lang.github.io/koka/doc/book.html -- 20 mentions of "in-place"

[dan-zheng]

Check out https://koka-lang.github.io/koka/doc/book.html -- 20 mentions of "in-place"

Thanks Patrick. Most of those "in-place" references are about "functional but in-place optimizations" done as part of Perceus. I don't believe those are actually quite relevant to my question, which is focused on state effects (like ST and IO) and whether they support in-place mutation.

[daanx]

Hi @dan-zheng ; good questions! Here are some answers:

1. The builtin var gives local variables whose lifetime is limited to their lexical scope. These are "builtin" and do in-place updating for efficiency. However, the semantics of var is specified as using a regular state-effect handler (using a monadic approach) -- this makes them in practice a bit less efficient than C local variables as they are currently heap allocated (but this could be avoided though with a more sophisticated implementation I think). This is needed for giving the right semantics under multiple resumptions. I put "builtin" in quotes as the actual implementation is done in the std/core/types and std/core/hnd modules using (unsafe) primitives.
2. Similarly, ref<h,a> are first-class mutable reference cells and are also "builtin" and do in-place mutation. A nice feature is that we can limit the scope of the side-effects similar to runST in Haskell.
3. With the var builtin, we can now easily implement a state effect ourselves knowing that it will use in-place mutation internally (but the implementation of our effect is functional since the fact that var internally uses in-place update is an implementation detail)
4. Since Koka has value types, a state monad s -> (a,s) can be quite efficient since the returned tuple is returned as a value (and optimized to return both components in registers). Not sure how good the Koka optimizer is now but in principle inlining the bind operation should result in very efficient code -- even though it does not update in place, the state flows linearly from one function to the next.
5. And Perceus reuse could also be used to get functional-style update in-place.

[dan-zheng]

Thanks for the illuminating answers, Daan and all!

[SchrodingerZhu]

@dan-zheng Also, the following example may be useful.

effect state<s> {
  fun get() : s
  fun put( x : s ) : ()
}

// State handler.
fun state(init, action) {
  var s := init              // use a local mutable variable
  with {
    return x  { (x,s) }
    fun get() { s }
    fun put(x){ s := x }
  }
  action()
}

fun main() {
    with state(1)
    put(get() + 1999)
    println(get() : int)
}

@daanx , it seems that in println(get() : int), the println function failed to resolve the type of the arguments?