sml-stm

A single-threaded software-transactional-memory-style API for Standard ML. Provides transactional variables (tvar) and atomically blocks with genuine all-or-nothing rollback: if a transaction raises (including Retry), every write it performed is undone via an undo log. Inspired by Haskell's STM, but without concurrency — see the limitations.

Breaking change: the transfer helper has been removed from the public API. It was a banking-specific example, not a primitive. Inline it at the call site with atomically + readTVar/writeTVar (see the example below).

API sketch

(* Create transactional variables *)
val acc1 : int Stm.tvar = Stm.newTVar 1000
val acc2 : int Stm.tvar = Stm.newTVar  500

(* Atomic transfer — either both updates happen or neither.
   (transfer is no longer built in; inline it like this.) *)
val () = Stm.atomically (fn () =>
  let val bal = Stm.readTVar acc1
  in if bal < 200 then raise Stm.Retry
     else (Stm.writeTVar acc1 (bal - 200);
           Stm.writeTVar acc2 (Stm.readTVar acc2 + 200))
  end)

(* Read outside a transaction (snapshot) *)
val bal = Stm.readTVar acc1   (* 800 *)

(* orElse: retry first branch, fall back to second *)
val result = Stm.orElse
  (fn () => if Stm.readTVar acc1 < 0 then raise Stm.Retry else "ok")
  (fn () => "fallback")

(* check b is `if b then () else retry ()` — drives the orElse fallback *)
val ok = Stm.orElse
  (fn () => (Stm.check (Stm.readTVar acc1 >= 1000); "rich"))
  (fn () => "poor")

(* read-modify-write helpers *)
val () = Stm.atomically (fn () => Stm.modifyTVar acc1 (fn n => n + 1))
val prev = Stm.atomically (fn () => Stm.swap acc2 0)   (* set 0, return old *)

(* stateTVar: read, transform, write back the new state, return a result *)
val popped = Stm.atomically (fn () =>
  Stm.stateTVar acc1 (fn n => (n, n - 1)))   (* returns old, decrements *)

(* atomicallyOpt: NONE instead of a Retry exception *)
val r = Stm.atomicallyOpt (fn () => (Stm.check false; 1))   (* NONE *)

(* runOrRetry: re-run up to N times until it stops retrying *)
val r2 = Stm.runOrRetry 5 (fn () => (Stm.check (cond ()); compute ()))

(* commit-time invariant: roll back and raise Stm.Invariant if violated *)
val () = Stm.invariant (fn n => n >= 0) acc1 (fn () =>
  Stm.modifyTVar acc1 (fn n => n - 50))

Semantics

• atomically f runs f; on success its writes commit. If f raises any exception (including Retry), all tvar writes made inside the transaction are rolled back to their pre-transaction values and the exception propagates.
• atomicallyOpt f is atomically f but returns NONE on Retry (other exceptions still propagate after rollback). runOrRetry n f re-runs f as a fresh transaction up to n times, stopping at the first non-retrying run.
• atomically does not block or automatically re-run. It is not an "optimistic-commit-and-validate" loop and there is no wait-for-change: a Retry simply rolls back and re-raises, leaving the caller to decide.
• orElse t1 t2 runs t1 as its own transaction; if t1 raises Retry it is rolled back fully (so none of its writes leak) and t2 is run.
• retry () raises Retry; check b is if b then () else retry (). Together they drive the orElse fallback: a failing check in the first branch rolls that branch back and runs the second.
• modifyTVar tv f is a transactional read-modify-write; modifyTVar' forces the new value first; swap tv x sets x and returns the previous value; stateTVar tv f applies f, writes the new state, and returns a result. All participate in rollback.
• always inv body / invariant pred tv body run body and then check the invariant once at commit; a violation rolls the whole transaction back and raises Invariant. This is a commit-time assertion, not the continuously revalidated always of a concurrent STM (there are no interleavings here).
• Nested transactions: an inner atomically that commits hands its undo entries to the enclosing transaction, so if the outer transaction later aborts, the inner writes are rolled back too.

Scope and limitations

• Single-threaded, no concurrency. This is not thread-safe and provides no parallelism or contention handling — it gives transactional rollback semantics for sequential code, not multi-threaded isolation.
• No read-set / version validation. With no other thread mutating tvars mid-transaction, optimistic conflict detection would never fire, so it is deliberately absent; this is honest rollback, not an optimistic-commit loop.
• No automatic retry/blocking. Retry does not suspend and wake on a tvar change; it aborts the transaction (and, inside orElse, selects the fallback). Use runOrRetry or build any wait-and-retry loop yourself.
• always/invariant are commit-time only, not continuous revalidation.

Example

make example builds and runs examples/demo.sml, which runs a transaction that increments a counter tvar and appends to a log tvar, then exercises swap, stateTVar, an orElse/check-driven retry fallback, and a commit-time invariant (output is byte-identical under MLton and Poly/ML):

Transaction 1: increment counter, append to log
  counter = 1
  log     = [incremented]

swap counter to 100, old value was 1
stateTVar: returned 100, counter now 99

orElse: took the fallback branch

invariant (counter >= 0) held; counter = 104

Installing with smlpkg

smlpkg add github.com/sjqtentacles/sml-stm
smlpkg sync

Reference from your .mlb:

lib/github.com/sjqtentacles/sml-stm/stm.mlb

Building and testing

make test        # MLton
make test-poly   # Poly/ML
make all-tests   # both
make clean

Project layout

sml.pkg
Makefile
lib/github.com/sjqtentacles/sml-stm/
  stm.sig     STM signature
  stm.sml     tvar + atomically/atomicallyOpt/runOrRetry + orElse + retry/check
              + modify/swap/stateTVar + always/invariant
  stm.mlb
test/
  test.sml    transfer (inlined), retry, modify/swap/stateTVar, check/orElse,
              atomicallyOpt/runOrRetry, invariant, rollback tests

License

MIT. See LICENSE.