15 people like it.
Like the snippet!

Monadic transactions for Clojure-style atoms

This is a simple implementation of a monadic transaction builder for Clojure-style atoms. Based on original code by Nick Palladinos.

 1: 
 2: 
 3: 
 4: 
 5: 
 6: 
 7: 
 8: 
 9: 
10: 
11: 
12: 
13: 
14: 
15: 
16: 
17: 
18: 
19: 
20: 
21: 
22: 
23: 
24: 
25: 
26: 
27: 
28: 
29: 
30: 
31: 
32: 
33: 
34: 
35: 
36: 
37: 
38: 
39: 
40: 
41: 
42: 
43: 
44: 
45: 
46: 
47: 
48: 
49: 
50: 
51: 
52: 
53: 
54: 
55: 
56: 
57: 
58: 
59: 
60: 
61: 
62: 
63: 
64: 
65: 
66: 
67: 
68: 
69:

open System.Threading

type Transaction<'State,'Output> = T of ('State -> 'State * 'Output)

type Atom<'T when 'T : not struct>(value : 'T) =
    let refCell = ref value
    
    let rec swap (f : 'T -> 'T) = 
        let currentValue = !refCell
        let result = Interlocked.CompareExchange<'T>(refCell, f currentValue, currentValue)
        if obj.ReferenceEquals(result, currentValue) then ()
        else Thread.SpinWait 20; swap f

    let transact (f : 'T -> 'T * 'A) =
        let output = ref Unchecked.defaultof<'A>
        let f' x = let t,s = f x in output := s ; t
        swap f' ; output.Value

    static member Create<'T> (x : 'T) = new Atom<'T>(x)

    member self.Value with get() : 'T = !refCell
    member self.Swap (f : 'T -> 'T) : unit = swap f
    member self.Commit<'A> (f : Transaction<'T,'A>) : 'A = 
        match f with T f0 -> transact f0 

    static member get : Transaction<'T,'T> = T (fun t -> t,t)
    static member set : 'T -> Transaction<'T,unit> = fun t -> T (fun _ -> t,())

type TransactionBuilder() =
    let (!) = function T f -> f

    member __.Return (x : 'A) : Transaction<'T,'A> = T (fun t -> t,x)
    member __.Bind (f : Transaction<'T,'A> , g : 'A -> Transaction<'T,'B>) : Transaction<'T,'B> =
        T (fun t -> let t',x = !f t in !(g x) t')

let transact = new TransactionBuilder()

// example : thread safe stack
type Stack<'T> () =
    let container : Atom<'T list> = Atom.Create []

    member __.Push (x : 'T) =
        transact {
            let! contents = Atom.get

            do! Atom.set <| x :: contents

            return ()
        } |> container.Commit

    member __.Pop () =
        transact {
            let! contents = Atom.get

            match contents with
            | [] -> return failwith "stack is empty!"
            | head :: tail ->
                do! Atom.set tail
                return head
        } |> container.Commit

    member __.Flush () =
        transact {
            let! contents = Atom.get

            do! Atom.set []

            return contents
        } |> container.Commit

namespace System

namespace System.Threading

type Transaction<'State,'Output> = | T of ('State -> 'State * 'Output)

Full name: Script.Transaction<_,_>

union case Transaction.T: ('State -> 'State * 'Output) -> Transaction<'State,'Output>

Multiple items
type Atom<'T (requires reference type)> =
  new : value:'T -> Atom<'T>
  member Commit : f:Transaction<'T,'A> -> 'A
  member Swap : f:('T -> 'T) -> unit
  member Value : 'T
  static member Create : x:'T -> Atom<'T>
  static member get : Transaction<'T,'T>
  static member set : ('T -> Transaction<'T,unit>)

Full name: Script.Atom<_>

--------------------
new : value:'T -> Atom<'T>

val not : value:bool -> bool

Full name: Microsoft.FSharp.Core.Operators.not

val value : 'T (requires reference type)

val refCell : 'T ref (requires reference type)

Multiple items
val ref : value:'T -> 'T ref

Full name: Microsoft.FSharp.Core.Operators.ref

--------------------
type 'T ref = Ref<'T>

Full name: Microsoft.FSharp.Core.ref<_>

val swap : (('T -> 'T) -> unit) (requires reference type)

val f : ('T -> 'T) (requires reference type)

val currentValue : 'T (requires reference type)

val result : 'T (requires reference type)

type Interlocked =
  static member Add : location1:int * value:int -> int + 1 overload
  static member CompareExchange : location1:int * value:int * comparand:int -> int + 6 overloads
  static member Decrement : location:int -> int + 1 overload
  static member Exchange : location1:int * value:int -> int + 6 overloads
  static member Increment : location:int -> int + 1 overload
  static member Read : location:int64 -> int64

Full name: System.Threading.Interlocked

Interlocked.CompareExchange<'T (requires reference type)>(location1: byref<'T>, value: 'T, comparand: 'T) : 'T
Interlocked.CompareExchange(location1: byref<nativeint>, value: nativeint, comparand: nativeint) : nativeint
Interlocked.CompareExchange(location1: byref<obj>, value: obj, comparand: obj) : obj
Interlocked.CompareExchange(location1: byref<float>, value: float, comparand: float) : float
Interlocked.CompareExchange(location1: byref<float32>, value: float32, comparand: float32) : float32
Interlocked.CompareExchange(location1: byref<int64>, value: int64, comparand: int64) : int64
Interlocked.CompareExchange(location1: byref<int>, value: int, comparand: int) : int

type obj = System.Object

Full name: Microsoft.FSharp.Core.obj

System.Object.ReferenceEquals(objA: obj, objB: obj) : bool

Multiple items
type Thread =
  inherit CriticalFinalizerObject
  new : start:ThreadStart -> Thread + 3 overloads
  member Abort : unit -> unit + 1 overload
  member ApartmentState : ApartmentState with get, set
  member CurrentCulture : CultureInfo with get, set
  member CurrentUICulture : CultureInfo with get, set
  member DisableComObjectEagerCleanup : unit -> unit
  member ExecutionContext : ExecutionContext
  member GetApartmentState : unit -> ApartmentState
  member GetCompressedStack : unit -> CompressedStack
  member GetHashCode : unit -> int
  ...

Full name: System.Threading.Thread

--------------------
Thread(start: ThreadStart) : unit
Thread(start: ParameterizedThreadStart) : unit
Thread(start: ThreadStart, maxStackSize: int) : unit
Thread(start: ParameterizedThreadStart, maxStackSize: int) : unit

Thread.SpinWait(iterations: int) : unit

val transact : (('T -> 'T * 'A) -> 'A) (requires reference type)

val f : ('T -> 'T * 'A) (requires reference type)

val output : 'A ref

module Unchecked

from Microsoft.FSharp.Core.Operators

val defaultof<'T> : 'T

Full name: Microsoft.FSharp.Core.Operators.Unchecked.defaultof

val f' : ('T -> 'T) (requires reference type)

val x : 'T (requires reference type)

val t : 'T (requires reference type)

val s : 'A

property Ref.Value: 'A

static member Atom.Create : x:'T -> Atom<'T>

Full name: Script.Atom`1.Create

val self : Atom<'T> (requires reference type)

member Atom.Value : 'T

Full name: Script.Atom`1.Value

member Atom.Swap : f:('T -> 'T) -> unit

Full name: Script.Atom`1.Swap

type unit = Unit

Full name: Microsoft.FSharp.Core.unit

member Atom.Commit : f:Transaction<'T,'A> -> 'A

Full name: Script.Atom`1.Commit

val f : Transaction<'T,'A> (requires reference type)

val f0 : ('T -> 'T * 'A) (requires reference type)

static member Atom.get : Transaction<'T,'T>

Full name: Script.Atom`1.get

static member Atom.set : ('T -> Transaction<'T,unit>)

Full name: Script.Atom`1.set

Multiple items
type TransactionBuilder =
  new : unit -> TransactionBuilder
  member Bind : f:Transaction<'T,'A> * g:('A -> Transaction<'T,'B>) -> Transaction<'T,'B>
  member Return : x:'A -> Transaction<'T,'A>

Full name: Script.TransactionBuilder

--------------------
new : unit -> TransactionBuilder

val f : ('a -> 'a * 'b)

member TransactionBuilder.Return : x:'A -> Transaction<'T,'A>

Full name: Script.TransactionBuilder.Return

val x : 'A

val t : 'T

val __ : TransactionBuilder

member TransactionBuilder.Bind : f:Transaction<'T,'A> * g:('A -> Transaction<'T,'B>) -> Transaction<'T,'B>

Full name: Script.TransactionBuilder.Bind

val f : Transaction<'T,'A>

val g : ('A -> Transaction<'T,'B>)

val t' : 'T

val transact : TransactionBuilder

Full name: Script.transact

Multiple items
type Stack<'T> =
  new : unit -> Stack<'T>
  member Flush : unit -> 'T list
  member Pop : unit -> 'T
  member Push : x:'T -> unit

Full name: Script.Stack<_>

--------------------
new : unit -> Stack<'T>

val container : Atom<'T list>

type 'T list = List<'T>

Full name: Microsoft.FSharp.Collections.list<_>

static member Atom.Create : x:'T -> Atom<'T>

member Stack.Push : x:'T -> unit

Full name: Script.Stack`1.Push

val x : 'T

val contents : 'T list

property Atom.get: Transaction<'T,'T>

property Atom.set: 'T -> Transaction<'T,unit>

member Atom.Commit : f:Transaction<'T,'A> -> 'A

val __ : Stack<'T>

member Stack.Pop : unit -> 'T

Full name: Script.Stack`1.Pop

val failwith : message:string -> 'T

Full name: Microsoft.FSharp.Core.Operators.failwith

val head : 'T

val tail : 'T list

member Stack.Flush : unit -> 'T list

Full name: Script.Stack`1.Flush

Previous Version Next Version Raw view Test code New version

More information

Link:	http://fssnip.net/bw
Posted:	12 years ago
Author:	Eirik Tsarpalis
Tags:	monadic transactions , thread safety , atom