References

A reference is just a singleton array, that is, an array containing one element. Given a type T, a reference for storing a value of the type T is given the type ref(T). The following simple program makes use of all the essential functionalities on references:

val intr = ref<int>(0) // create a ref and init. it with 0 val ((*void*)) = !intr := !intr + 1 // increase the integer at [intr] by 1

The first line creates a reference for storing an integer and initializes it with the value 0 and then names it intr. Note that this style of reference creation cannot be separated from its initialization. The second line updates the reference intr with its current value plus 1. In general, given a reference r of type ref(T) for some T, the expression !r means to fetch the value stored at r, which is of the type T. However, !r can also be used as a left-value. For instance, the assignment (!r := exp) means to evaluate exp into a value and then store the value into r. Therefore, the value stored in intr is 1 after the second line in the above program is evaluated.

Various functions and function templates on references are declared in the file reference.sats, which is automatically loaded by atsopt. In particular, it is also possible to read from and write to a reference by using the function templates ref_get_elt and ref_set_elt of the following interfaces, respectively:

fun{a:t@ype} ref_get_elt(r: ref a): a // !r fun{a:t@ype} ref_set_elt(r: ref a, x: a): void // !r := x

References are often misused in practice, especially, by beginners of functional programming who had some previous exposure to imperative programming languages such C and Java. Such programmers often think that they can just "translate" their programs in C or Java into functional programs. For example, the following defined function sumup is such an example, which sums up all the integers between 1 and a given integer, inclusive:

fun sumup (n: int): int = let val i = ref<int>(1) val res = ref<int>(0) fun loop(): void = if !i <= n then (!res := !res + !i; !i := !i + 1; loop()) // end of [loop] in loop(); !res end // end of [sumup]

This is a correct but poor implementation, and its style, though not the worst of its kind, is deplorable. As references are allocated in heap, reading from or writing to a reference can be much more time-consuming than reading from or writing to a register. So, this implementation of sumup is unlikely to be time-efficient. Every call to sumup creates two references in heap and leaves them there when it returns, and the memory allocated for such references can only be reclaimed through garbage collection (GC). So, this implementation of sumup is not memory-efficient. More importantly, a program making heavy use of references is often difficult to reason about.

I consider references a dangerous feature in functional programming. If you want to run your program without GC, please do not create references in the body of a function (besides many other restrictions). If you find that you are in need of references to "translate" imperative programs into functional ones, then it is most likely that you are lost and you have not learned well to program in a functional style yet.