STM

Software transactional memory: shared variables that tasks read and update in composable atomic transactions.

A transaction is a callback typed () ->{STM} a. atomically runs it so that its reads observe one consistent snapshot and its writes become visible to other tasks all at once, or not at all. Several variables therefore change together, and functions performing STM combine into larger transactions. retry abandons an attempt until a variable it read changes, so any condition over shared state becomes a blocking wait. orElse chooses between alternatives that may retry, and attempt undoes the writes of an action that fails.

A transaction may be run more than once: when another task commits to a variable it read, it is discarded and started again. Its row is closed, so it cannot perform IO, Async, or any other effect handled outside it, and replaying it is unobservable. Effects handled inside the transaction, such as a local Fail.attempt or Runtime.Local.run, are allowed. Read outside services before atomically and pass the values in; return side effects that depend on the outcome as data and perform them after it commits. atomically itself needs Async, so transactions do not nest.

Only atomically handles STM; its operations are private to this module.

import Async exposing (Outcome(..))
import STM

result = Async.runOutcome {
    alice = STM.atomically { STM.new 100 }
    bob = STM.atomically { STM.new 0 }
    STM.atomically { STM.modify alice { n -> n - 30 }; STM.modify bob { n -> n + 30 } }
    STM.atomically { (STM.read alice, STM.read bob) }
    }
result == Completed (70, 30)

Only atomically handles STM, so no other module can add a primitive, such as a commit hook, or interpret STM differently; tests run under the real atomically. Everything else is built from the operations here: the bundled STM.MVar and STM.Queue are ordinary modules over them. Granularity is the main choice in such a structure. A Var (Dict k v) makes every update conflict with every other, while a Dict k (Var v) conflicts only per key but needs a fixed key set or a variable for membership.

A handler whose clauses perform STM interprets another effect inside a transaction. Its writes are logged, so they roll back and replay with the transaction, and code written against State runs atomically against shared state:

import Async exposing (Outcome(..))
import State exposing (State)
import STM exposing (STM)

runVar : STM.Var s -> (() ->{State s, e} a) ->{STM, e} a
runVar var action =
    handle action() on
        State.get () -> resume (STM.read var)
        State.put next -> resume (STM.write var next)
        State.update step ->
            (result, next) = step (STM.read var)
            STM.write var next
            resume result

result = Async.runOutcome {
    counter = STM.atomically { STM.new 1 }
    STM.atomically { runVar counter { State.modify { n -> n * 5 } } }
    STM.atomically { STM.read counter }
    }
result == Completed 5

Var

type Var aSource

A shared mutable variable holding an a. Its identity, not its value, distinguishes it; it may cross task boundaries freely. A variable lives until it is unreachable, and has no equality or Show.

STM

effect STMSource

Running inside a transaction. Only atomically handles it.

atomically

atomically : (() ->{STM} a) ->{Async} aSource

Runs transaction until it commits and answers its value.

Every attempt observes one consistent snapshot of the variables it reads; a read that would see a later commit restarts the attempt at once, so a transaction never computes on inconsistent values. Its writes become visible together when it commits. If another task committed to a variable it read in the meantime, the attempt is discarded and the transaction runs again. Conflict restarts are invisible to the program.

A transaction responds to cancellation only while waiting after retry. One that never retries runs to commit even in a cancelled task, so cancellation cleanup can still release a lock or return a permit with atomically.

import Async exposing (Outcome(..))
import STM

Async.runOutcome { STM.atomically { STM.read (STM.new 7) } } == Completed 7

attempt

attempt : (() ->{Fail a, STM} b) ->{STM} Result a bSource

Runs action, answering Ok with its value, or Err with its failure after discarding every write it made. Its reads are kept, so they still decide whether the transaction commits. The transaction itself commits either way; Fail.fromResult raises the error after atomically.

import Async exposing (Outcome(..))
import Fail
import Result exposing (Result(..))
import STM

result = Async.runOutcome {
    account = STM.atomically { STM.new 10 }
    withdrawn = STM.atomically {
        STM.attempt {
            STM.modify account { n -> n - 30 }
            if STM.read account < 0 then Fail.fail "overdrawn" else ()
        }
    }
    (withdrawn, STM.atomically { STM.read account })
    }
result == Completed (Err "overdrawn", 10)

check

check : Bool ->{STM} ()Source

Does nothing when condition holds, and retrys otherwise.

import Async exposing (Outcome(..))
import STM

result = Async.runOutcome {
    permits = STM.atomically { STM.new 0 }
    worker = Async.spawn {
        STM.atomically {
            available = STM.read permits
            STM.check (available > 0)
            STM.write permits (available - 1)
        }
        "acquired"
    }
    STM.atomically { STM.modify permits { n -> n + 1 } }
    Async.await worker
    }
result == Completed "acquired"

exchange

exchange : Var a -> a ->{STM} aSource

Replaces the variable’s value with next and answers the value it replaced.

import Async exposing (Outcome(..))
import STM

result = Async.runOutcome { STM.atomically { v = STM.new "old"; previous = STM.exchange v "new"; (previous, STM.read v) } }
result == Completed ("old", "new")

modify

modify : Var a -> (a -> a) ->{STM} ()Source

Replaces the variable’s value with f applied to it.

import Async exposing (Outcome(..))
import STM

Async.runOutcome { STM.atomically { v = STM.new 3; STM.modify v { n -> n * 7 }; STM.read v } } == Completed 21

new

new : a ->{STM} Var aSource

A fresh variable holding value. Outside a transaction, use atomically { STM.new value }. A variable created by an attempt that is discarded is never seen by anyone.

import Async exposing (Outcome(..))
import STM

Async.runOutcome { STM.atomically { STM.read (STM.new "hi") } } == Completed "hi"

orElse

orElse : (() ->{STM} a) -> (() ->{STM} a) ->{STM} aSource

Runs first, or second if first retries. The writes first made are discarded before second runs, but its reads are kept: if both retry, the transaction waits until a variable either of them read changes. A conflict in first restarts the whole transaction rather than choosing second.

import Async exposing (Outcome(..))
import STM

result = Async.runOutcome {
    empty = STM.atomically { STM.new 0 }
    full = STM.atomically { STM.new 5 }
    takeFrom = { var ->
        n = STM.read var
        STM.write var 0
        STM.check (n > 0)
        n
    }
    STM.atomically {
        taken = STM.orElse { takeFrom empty } { takeFrom full }
        (taken, STM.read empty, STM.read full)
    }
    }
result == Completed (5, 0, 0)

read

read : Var a ->{STM} aSource

The variable’s value, including the transaction’s own earlier writes.

import Async exposing (Outcome(..))
import STM

Async.runOutcome { STM.atomically { v = STM.new 1; STM.write v 2; STM.read v } } == Completed 2

retry

retry : () ->{STM} aSource

Abandons the attempt: its writes are discarded, and the task waits until another transaction commits a write to a variable the attempt read, then runs the transaction again from the start. A retry that read nothing waits until the task is cancelled.

import Async exposing (Outcome(..))
import Maybe exposing (Maybe(..))
import STM

result = Async.runOutcome {
    box = STM.atomically { STM.new Nothing }
    consumer = Async.spawn {
        STM.atomically {
            case STM.read box of
                Just value -> value
                Nothing -> STM.retry ()
        }
    }
    STM.atomically { STM.write box (Just 42) }
    Async.await consumer
    }
result == Completed 42

write

write : Var a -> a ->{STM} ()Source

Replaces the variable’s value when the transaction commits. Later reads in the same transaction see it at once.

import Async exposing (Outcome(..))
import STM

result = Async.runOutcome {
    v = STM.atomically { STM.new [1] }
    STM.atomically { STM.write v [2, 3] }
    STM.atomically { STM.read v }
    }
result == Completed [2, 3]