Persistent References

A reference is essentially a heap-allocated array of size 1. It is persistent in the sense that the memory allocated for storing the content of a reference cannot be freed manually. Instead, it can only be reclaimed through garbage collection (GC).

Given a viewtype VT, the type for references to values of viewtype VT is ref(VT). For convenience, the type constructor ref is declared to be abstract in ATS. However, it can be defined as follows:

typedef ref (a:viewt@ype) = [l:addr] (vbox (a @ l) | ptr l)

The interfaces for various functions on references can be found in prelude/SATS/reference.sats.

For creating a reference, the function template ref_make_elt of the following interface can be called:

fun{a:viewt@ype} ref_make_elt (x: a):<> ref a

For reading from and writing to a reference, the function templates ref_get_elt and ref_set_elt can be used, respectively, which are assigned the following interfaces:

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

Note that the symbol !ref indicates that these functions incur the so-called ref-effect when evaluated. Given a reference r and a value v, ref_get_elt(r) and ref_set_elt(r, v) can be written as !r and !r := v, respectively.

A reference is typically employed to record some form of persistent state. For instance, following is such an example:

// [ref] is a shorthand for [ref_make_elt]
val count = ref<int> (0)

in // in of [local]

fun getNewName
  (prfx: string): string = let
  val n = !count
  val () = !count := n + 1
  val name = sprintf ("%s%i", @(prfx, n))
  string_of_strptr (name)
end // end of [getNewName]

end // end of [local]

The function getNewName is called to generate fresh names. As the integer content of the reference count is updated whenever a call to getNewName is made, each name returned by getNewName is guaranteed to have not generated before. Note that each string returned by sprinf is a linear one (of the type strptr) and the cast funtion string_of_strptr is called to turn it into a nonlinear one. There is no run-time cost associated with such a call as every call to a cast function is always a no-op at run-time.

References are commonly misused in practice. The following program is often written by a beginner of functional programming who has already learned (some) imperative programming:

fun fact
  (n: int): int = let
  val res = ref<int> (1)
  fun loop (n: int):<cloref1> void =
    if n > 0 then !res := n * !res else ()
  val () = loop (n)
end // end of [fact]

The function fact is written in such a style as somewhat a direct translation of the following C code:

int fact (int n) {
  int res = 1 ;
  while (n > 0) res = n * res ;
  return res ;

In the ATS implementation of fact, res is a heap-allocated reference and it becomes garbage (waiting to be reclaimed by the GC) after a call to fact returns. On the other hand, the variable res in the C implementation of fact is stack-allocated (or it can even be mapped to a machine register), and there is no generated garbage after a call to fact returns. A proper translation of the C implementation in ATS can actually be given as follows, which makes no use of references:

fun fact
  (n: int): int = let
  fun loop (n: int, res: int): int =
    if n > 0 then loop (n, n * res) else res
  // end of [loop]
  loop (n, 1)
end // end of [fact]

Unless strong justification can be given, making extensive use of (dynamically created) references is often a sure sign of poor coding style.