[RFC][Relay] Reference(Mutation).

[MarisaKirisame]

This RFC aim to add ML style Reference into Relay, which is crucial for modeling traditional imperative algorithm, and for higher order reverse mode automatic differentiation (backpropagation require using reference to store the gradient).

Informally speaking, a Ref(erence)<a> point to a box, which hold a value of a.
We can fetch value from the box, or update a new value into the box, forgetting the old one.
It is crucial to note that this 'update' is the only source of mutability in relay. The value in the box is immutable, and the reference itself is immutable (cannot point to new box). If you want the reference to be mutable, you need a reference of reference(Ref<Ref<Int>>). If you want the value to be mutable, you need to sprinkle reference inside the value((Ref<Int>, Ref<Int>) for a tuple of reference, where Ref<(Int, Int)> is a reference of tuple - the tuple itself is still immutable).

More formally speaking, there are 3 function that come with reference:
MakeRef : a -> Ref<a>, construct a new box, returning a reference pointing to it.
ReadRef : Ref<a> -> a, look at the input Reference, and return the value in the box.
WriteRef : (Ref<a>, a) -> (), put the new a in the box pointed to by a reference.

to make their semantic clearer, here are some example code:

a : Ref<Int> = MakeRef 1
b : Ref<Int> = a # a and b will *always* be aligned. there are no way to make them point to different box.
assert (ReadRef(b) == 1)
WriteRef(a, 2)
assert (ReadRef(b) == 2)

In relay, we will provide special syntax like :=, ! to make using reference easier.

[ZihengJiang]

The value in the box is immutable, and the reference itself is immutable (cannot point to new box). If you want the reference to be mutable, you need a reference of reference(Ref<Ref>)

Why the Ref<Int> in Ref<Ref<Int>> is mutable while "The value in the box is immutable"?

[MarisaKirisame]

@ZihengJiang this is like a const pointer to a pointer to a const object.
the Ref is still immutable per se, but Ref<Ref> has the effect of mimicing a pointer to an int, in which both the pointer and the int is mutable. The pointer mutability is provided by calling WriteRef on Ref<Ref>, and the int mutability is provided by calling WriteRef on Ref

[tqchen]

closed by #2489