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