(std stm)

Submodules:

(std stm map): a transactional hash map, TMap.
(std stm queue): a transactional FIFO queue, TQueue, that is also a CML event.
(std stm counter): a striped counter, TCounter, with few write conflicts between cores.

Overview

Software transactional memory (STM): atomic multi-location transactions with CML event integration.

(import (std stm))

(def from (make-loc 100))
(def to (make-loc 0))

;; Transfer 30 between accounts atomically:
(atomically
 (fun (tx)
   (tx-set! tx from (- (tx-ref tx from) 30))
   (tx-set! tx to (+ (tx-ref tx to) 30))))

;; Wait for account balance with a 1-second timeout:
(sync (choose (atomically-evt
               (fun (tx)
                 (if (> (tx-ref tx to) 0)
                     (tx-ref tx to)
                     (tx-retry tx))))
              (wrap (timeout (seconds 1)) (fun (_) 0))))

(Loc T) represents a transactional memory location holding a value of type T. A transaction is a function taking a Tx log argument. It reads and writes locations through Tx using tx-ref, tx-set!, tx-update!, and tx-swap!.

Atomicity and isolation. Speculative writes are buffered in the transaction log until commit time. The commit applies all writes atomically, provided no locations in the read set were modified by concurrent transactions. If a conflict occurs, the transaction rolls back and retries automatically.

Execution. Run transactions using atomically (which blocks or suspends until commit), or atomically-evt (which integrates with CML event synchronization). Use try-atomically in non-fiber .NET callbacks where waiting is not permitted.

Conditional synchronization. Calling tx-retry aborts the current transaction run and suspends until at least one location in the read set changes. Combined with atomically-evt, retrying transactions compose cleanly in choose alongside timeouts and channels.

Alternatives. (tx-or-else tx a b) attempts transaction a. If a retries, its writes are rolled back and b executes.

Transaction rules.

Transactions must be free of side effects outside Tx: no printing, no I/O, and no mutation of external state.
Transactions cannot perform CML synchronization (sync).
The Tx log token is single-use; accessing a Tx after transaction completion throws an error.
Store immutable values in locations. Mutations to objects inside locations bypass transaction tracking.

Consistency. The log is validated periodically during execution and before commit to prevent dirty reads. Transactions never commit from inconsistent views.

Credits. Based on kcas by Vesa Karvonen and contributors (https://github.com/ocaml-multicore/kcas), using multi-word compare-and-swap algorithms with read-only validation.

Reference

Types

Loc
Tx

Functions

atomically
atomically-evt
loc-ref
make-loc
try-atomically
tx-or-else
tx-ref
tx-retry
tx-set!
tx-swap!
tx-update!

Types

`Loc`

type alias ↑ Types

Transactional memory location holding a value of type %a.

%a: The type of the contained value.

See also: make-loc, tx-ref, loc-ref

`Tx`

type alias ↑ Types

Transaction log token passed to transaction functions.

See also: tx-ref, tx-set!, atomically

Functions

`make-loc`

function ↑ Functions

(: make-loc (-> %a (Loc %a)))

Creates a new transactional location initialized with a value.

value: Initial value stored in the location.
returns: A new transactional location cell.

`loc-ref`

function ↑ Functions

(: loc-ref (-> (Loc %a) %a))

Reads the current value of a location outside a transaction.

loc: The location to read.
returns: The value from the most recent commit.

Reading multiple locations via consecutive loc-ref calls does not provide a consistent snapshot. To read multiple locations atomically, use a transaction.

`tx-ref`

function ↑ Functions

(: tx-ref (-> Tx (Loc %a) %a))

Reads the value of a location within a transaction.

tx: The transaction log context.
loc: The location to read.
returns: The transaction's pending write for loc, or its committed value.

`tx-set!`

function ↑ Functions

(: tx-set! (-> Tx (Loc %a) %a void))

Writes a value to a location within a transaction.

tx: The transaction log context.
loc: The location to modify.
value: The new value to write.

Writes are speculative and buffered in the transaction log; concurrent threads observe the new value only after successful commit.

`tx-update!`

function ↑ Functions

(: tx-update! (-> Tx (Loc %a) (-> %a %a) %a))

Applies a transformation function to a location within a transaction.

tx: The transaction log context.
loc: The location to update.
f: Transformation function taking old value and returning new value.
returns: The updated value written to the location.

`tx-swap!`

function ↑ Functions

(: tx-swap! (-> Tx (Loc %a) %a %a))

Replaces the value of a location within a transaction, returning the previous value.

tx: The transaction log context.
loc: The location to update.
value: The new value to store.
returns: The value held in the location immediately before the swap.

`tx-retry`

function ↑ Functions

(: tx-retry (-> Tx %a))

Aborts the transaction and waits until any location read by the transaction changes.

tx: The transaction log context.
returns: Never returns directly.

;; Dequeue an item or wait until available:
(: take! (-> (Loc (Option string)) string))
(defun (take! slot)
  (atomically
   (fun (tx)
     (match (tx-ref tx slot)
       ((Some item) (tx-set! tx slot None) item)
       (None (tx-retry tx))))))

Discards speculative writes. Retrying transactions suspend until a concurrent transaction commits a new value to at least one location in the read set.

`tx-or-else`

function ↑ Functions

(: tx-or-else (-> Tx (-> Tx %a) (-> Tx %a) %a))

Tries transaction first; if it retries, rolls back writes and tries second.

tx: The transaction log context.
first: The primary transaction to attempt.
second: The fallback transaction to run if first retries.
returns: The return value of the successful branch.

;; Dequeue from high-priority queue, falling back to low-priority queue:
(tx-or-else tx (fun (tx) (pop! tx high)) (fun (tx) (pop! tx low)))

If second retries as well, the entire tx-or-else form retries, waiting on locations read by either branch.

`atomically-evt`

function ↑ Functions

(: atomically-evt (-> (-> Tx %a) (Event %a)))

Creates a CML event that executes and commits a transaction.

f: The transaction function taking a Tx argument.
returns: A CML event available when f commits without retrying.

;; Wait for a transactional flag, a channel message, or a timeout:
(sync (choose (atomically-evt
               (fun (tx) (if (tx-ref tx flag) "flag" (tx-retry tx))))
              (wrap (chan-recv messages) (fun (_) "message"))
              (wrap (timeout (seconds 1)) (fun (_) "timeout"))))

Function f runs when the event synchronizes. If f calls tx-retry, the event remains unavailable until locations read by f are modified. If another branch in choose synchronizes first, f rolls back all writes.

`atomically`

function ↑ Functions

(: atomically (-> (-> Tx %a) %a))
(atomically f)

Executes and commits a transaction, waiting while it retries.

f: The transaction function taking a Tx argument.
returns: The value returned by f in the committed run.

In a fiber, this expands to (sync (atomically-evt f)). Outside a fiber, it executes synchronously and blocks the calling thread while waiting.

`try-atomically`

function ↑ Functions

(: try-atomically (-> (-> Tx %a) (Option %a)))

Attempts to commit a transaction immediately without waiting, returning Option.

f: The transaction function taking a Tx argument.
returns: (Some value) if f commits, or None if f calls tx-retry.

Conflicting transactions retry immediately; returns None only if f explicitly invokes tx-retry. Safe for non-fiber .NET callbacks because it never blocks.