Mutable cells

[byorgey]

It's a little hard to believe we don't already have an issue for this, but I couldn't find one. It would be fun to add mutable reference cells to the language, so you could do some imperative programming when convenient. Our CESK machines already track a mutable store, so this really just requires adding some surface language features that allow accessing it directly.

Proposal

In particular, we could add the following primitives:

• Ref a is the type of references to a mutable cell holding a value of type a
• ref : a -> Cmd (Ref a) creates a new mutable cell holding the given value
• read : Ref a -> Cmd a reads the current value of a mutable cell
• write : Ref a -> a -> Cmd Unit writes a new value to a mutable cell

We could optionally use special syntax for read and write, e.g. !r for read r and r := x for write r x. It may be OK to get rid of the Cmd on some or all of the above primitives (particularly read); that would require some careful thought/research to make sure it doesn't break type safety somehow.

Additional considerations

• I am not sure whether references + polymorphism could introduce type safety issues in our language; see https://en.wikipedia.org/wiki/Value_restriction . We should either convince ourselves that this problem does not apply, or come up with appropriate restrictions/safeguards to prevent unsoundness.
• We should put a bit of thought into what device(s) will provide the capability to create and use mutable cells.
• Within the world we've created, I'm not sure it makes sense to have shared mutable state. Or at least, it would only make sense in certain restricted situations which we can work out in the future. So passing a Ref a value to another robot (e.g. via Inter-robot communication #94 ) should result in the cell being copied, not in a shared reference to the same mutable cell. Or a value of type Ref a could contain not just a memory address but also a robot ID, so we can tell when we are trying to access memory stored on another robot (with a suitable exception being thrown in that case).
• Once we implement immutable arrays (Array type #98), we could get mutable arrays simply by making an immutable array full of references; if desired, we could optimize this to use an actual mutable array under the hood.