1(*
2    Title:      References that allow a single assignment
3    Author:     David Matthews
4    Copyright   David Matthews 2010, 2016
5
6	This library is free software; you can redistribute it and/or
7	modify it under the terms of the GNU Lesser General Public
8	License version 2.1 as published by the Free Software Foundation.
9
10	This library is distributed in the hope that it will be useful,
11	but WITHOUT ANY WARRANTY; without even the implied warranty of
12	MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
13	Lesser General Public License for more details.
14
15	You should have received a copy of the GNU Lesser General Public
16	License along with this library; if not, write to the Free Software
17	Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
18*)
19
20(*!The `SingleAssignment` structure provides a reference
21  that can be assigned a value only once.*)
22
23structure SingleAssignment:>
24sig
25    (*!The type of a single-assignment reference. It is similar to the standard
26      `ref` type constructor.*)
27    type 'a saref (* Equality not allowed *)
28    (*!This exception is raised if an attempt is made to assign a value twice
29      to the same reference.*)
30    exception Locked
31    (*!Construct a single-assignment reference.*)
32    val saref: unit -> 'a saref
33    (*!Assign a value to the reference. If it has already been assigned a value
34      this will raise `Locked`. Note that this function is not thread-safe. A `mutex`
35      must be associated with reference if there is the possibility that two different
36      threads may attempt to assign to the same reference.*)
37    val saset: 'a saref * 'a -> unit
38    (*!Extract the current value of the reference. If it has not yet been assigned
39      a value it will return `NONE`. If it has,
40      it will return `SOME v` where `v`
41      is the value that was assigned.*)
42    val savalue: 'a saref -> 'a option
43end
44=
45struct
46    exception Locked
47
48    type 'a saref = 'a option ref
49
50    fun saref () = ref NONE
51
52    val savalue = !
53
54    fun saset(saVar as ref NONE, newValue) =
55    (
56        saVar := SOME newValue;
57        RunCall.clearMutableBit saVar
58    )
59    |   saset _ = raise Locked
60end;
61(*!The reason behind the `SingleAssignment` structure
62  has to do with the way the Poly/ML storage management system deals with *mutable*
63  and *immutable* data. Immutable memory cells are given a value when they
64  are created and once created never change. They are used for lists, tuples,
65  vectors and other datatypes. In contrast, refs and arrays are mutable data.
66  They are given a value when they are created in the same way as immutable data
67  but their contents can change by assignment. In addition Standard ML also distinguishes
68  between mutable and immutable data in the treatment of equality. Immutable data
69  structures are considered equal if their contents are the same, mutable cells
70  are considered equal only if they are the pointers to the same cell.
71
72  Because of these differences mutable data has to be handled separately from
73  immutable data by the garbage collector. Using mutable cells imposes an extra
74  cost on each collection when compared with immutable data. In addition it is
75  possible to reduce the heap size by merging immutable cells that have the same
76  contents. In some circumstances the garbage collector may do this automatically;
77  more often it is done explicitly using `PolyML.shareCommonData`.
78
79  The `SingleAssignment` structure allows for a
80  combination of mutable and immutable data. A value of type `saref`
81  is initially mutable but once it has been assigned a value it is marked as immutable.
82  This allows the garbage-collector and sharing code to treat it as purely immutable
83  once it has been locked.
84
85  A typical use for a single-assignment reference is when a data structure is
86  being built by multiple threads. A `saref` can
87  be used within the data structure to represent a portion of the structure to
88  be built and a thread created to build it. When the thread completes it assigns
89  the `saref` with the results of its work. The
90  full structure is now immutable with all the advantages of immutable data.*)
91