Sunday, 6 May 2012

Why don't purely functional languages use reference counting?

You can create cyclic data structures using purely functional programming simply by defining mutually-recursive values at the same time. For example, two mutually-recursive lists in OCaml:
let rec xs = 0::ys and ys = 1::xs
However, it is possible to define languages that make it impossible to create cyclic structures by design. The result is known as a unidirectional heap and its primary advantage is that garbage collection can be as simple as reference counting.
Some real languages do prohibit cycles and use reference counting. Erlang and Mathematica are examples. For example, in Mathematica when you reference a value you make a deep copy of it so mutating the original does not mutate the copy:
In[1] := xs = {1, 2, 3}
Out[1] = {1, 2, 3}

In[2] := ys = xs
Out[2] = {1, 2, 3}

In[3] := xs[[1]] = 5
Out[3] = 5

In[4] := xs
Out[4] = {5, 2, 3}

In[5] := ys
Out[5] = {1, 2, 3}

No comments: