STM Guide

Reference guide for Software Transactional Memory -- composable, deadlock-free concurrent state.

Overview

Software Transactional Memory (STM) replaces manual lock management with transactions. A transaction either commits atomically or rolls back and retries, with no risk of deadlock. Turmeric's STM is modeled on Haskell's Control.Concurrent.STM.

For a conceptual walkthrough and worked examples, see the STM Tutorial. This guide focuses on the API and mechanics.

Core Concepts

TVar Lifecycle

(import "stdlib/stm.tur")

;; Create a TVar with an initial value
(def counter (tvar/new 0))

;; Free when no longer needed (only when no transactions reference it)
;; (tvar/free counter)  ; called via inline C if needed

import("stdlib/stm.tur")

;; Create a TVar with an initial value
def counter tvar/new(0)

;; Free when no longer needed (only when no transactions reference it)
;; tvar/free(counter)  ; called via inline C if needed

tvar/new accepts any value; TVars are untyped at the Turmeric level.

Reading and Writing

All TVar access must happen inside atomically:

;; Read
(def val
  (atomically
    (fn []
      (tvar/read counter))))

;; Write
(atomically
  (fn []
    (tvar/write counter 42)))

;; Read-modify-write (common pattern)
(atomically
  (fn []
    (def v (tvar/read counter))
    (tvar/write counter (+ v 1))))

;; Read
def val
  atomically
    fn []
      tvar/read(counter)

;; Write
atomically
  fn []
    tvar/write(counter 42)

;; Read-modify-write (common pattern)
atomically
  fn []
    def v tvar/read(counter)
    tvar/write(counter {v + 1})

Swap and CAS

;; Swap: write new value and return old value (within one transaction)
(def old-val
  (atomically
    (fn []
      (tvar/swap counter 99))))

;; Compare-and-swap: write new only if current value equals expected
;; Returns true if the swap succeeded
(def swapped
  (atomically
    (fn []
      (tvar/cas counter 99 100))))

;; Swap: write new value and return old value (within one transaction)
def old-val
  atomically
    fn []
      tvar/swap(counter 99)

;; Compare-and-swap: write new only if current value equals expected
;; Returns true if the swap succeeded
def swapped
  atomically
    fn []
      tvar/cas(counter 99 100)

Retry

retry aborts the current transaction and blocks until one of the TVars read during this transaction changes, then re-runs from the beginning:

;; Block until counter reaches at least 10
(atomically
  (fn []
    (def v (tvar/read counter))
    (when (< v 10)
      (retry))
    v))

;; Block until counter reaches at least 10
atomically
  fn []
    def v tvar/read(counter)
    when {v < 10}
      retry()
    v

retry never returns. The runtime records the read set, sleeps the thread, and wakes it when any read TVar is modified by another transaction.

or-else

or-else tries the first transaction; if it calls retry, the second is tried instead:

;; Drain queue-a if possible, otherwise queue-b
(atomically
  (fn []
    (or-else
      (fn [] (dequeue queue-a))
      (fn [] (dequeue queue-b)))))

;; Drain queue-a if possible, otherwise queue-b
atomically
  fn []
    or-else
      fn [] dequeue(queue-a)
      fn [] dequeue(queue-b)

Both branches see the same transactional snapshot. If both retry, the outer transaction also retries.

Transaction Lifecycle

Each call to atomically runs a retry loop:

1. Begin -- allocate a transaction context; record thread-local pointer.
2. Execute -- run the closure; all tvar/read and tvar/write calls are journaled (read set / write set).
3. Validate -- check that every read TVar still has the version seen during step 2.
4. Commit -- apply the write set atomically; bump versions; notify waiters. Fire commit defers.
5. Abort -- if validation fails or retry was called, discard the write set, fire abort defers, then go to step 1.

The read set holds up to 256 entries; the write set holds up to 128. Transactions exceeding these limits will panic -- keep transactions focused.

Defers

A defer fires at the end of a transaction, after commit or abort. Register them via inline C:

(defn register-commit-defer [env-ptr fn-ptr] : void
  ```c
  STM_Transaction *tx = tur_stm_current_tx();
  tur_stm_defer_on_commit(tx, (stm_defer_fn_t)fn_ptr, env_ptr);
  ```)

(defn register-abort-defer [env-ptr fn-ptr] : void
  ```c
  STM_Transaction *tx = tur_stm_current_tx();
  tur_stm_defer_on_abort(tx, (stm_defer_fn_t)fn_ptr, env_ptr);
  ```)

defn register-commit-defer [env-ptr fn-ptr] :void
  ```c
  STM_Transaction *tx = tur_stm_current_tx();
  tur_stm_defer_on_commit(tx, (stm_defer_fn_t)fn_ptr, env_ptr);
  ```

defn register-abort-defer [env-ptr fn-ptr] :void
  ```c
  STM_Transaction *tx = tur_stm_current_tx();
  tur_stm_defer_on_abort(tx, (stm_defer_fn_t)fn_ptr, env_ptr);
  ```

Commit defers run once, in registration order, after the write set is applied. Abort defers run on every failed attempt, including retries -- design them to be idempotent.

Up to 32 defers per transaction; exceeding this panics.

Building Higher-Level Primitives

TMVar (single-slot mailbox)

;; An empty slot is represented as nil
(defn tmvar/new [] : ptr  (tvar/new (ptr/null)))
(defn tmvar/empty? [mv]  (nil? (tvar/read mv)))

(defn tmvar/take [mv]
  (atomically
    (fn []
      (def v (tvar/read mv))
      (when (nil? v) (retry))
      (tvar/write mv (ptr/null))
      v)))

(defn tmvar/put [mv val]
  (atomically
    (fn []
      (when (not (nil? (tvar/read mv))) (retry))
      (tvar/write mv val))))

;; An empty slot is represented as nil
defn tmvar/new [] :ptr
  tvar/new(ptr/null())
defn tmvar/empty? [mv]
  nil?(tvar/read(mv))

defn tmvar/take [mv]
  atomically
    fn []
      def v tvar/read(mv)
      when nil?(v)
        retry()
      tvar/write(mv ptr/null())
      v

defn tmvar/put [mv val]
  atomically
    fn []
      when not(nil?(tvar/read(mv)))
        retry()
      tvar/write(mv val)

TChan (unbounded FIFO)

;; Backed by a TVar holding a list
(defn tchan/new [] : ptr  (tvar/new '()))

(defn tchan/write [ch val]
  (atomically
    (fn []
      (def q (tvar/read ch))
      (tvar/write ch (append q (list val))))))

(defn tchan/read [ch]
  (atomically
    (fn []
      (def q (tvar/read ch))
      (when (nil? q) (retry))
      (tvar/write ch (cdr q))
      (car q))))

;; Backed by a TVar holding a list
defn tchan/new [] :ptr
  tvar/new('())

defn tchan/write [ch val]
  atomically
    fn []
      def q tvar/read(ch)
      tvar/write(ch append(q list(val)))

defn tchan/read [ch]
  atomically
    fn []
      def q tvar/read(ch)
      when nil?(q)
        retry()
      tvar/write(ch cdr(q))
      car(q)

Composability

Because retry and or-else work purely through the transaction's read set, any two transactions compose without deadlock:

;; Both operations run in a single atomic transaction
(atomically
  (fn []
    (transfer account-a account-b 30)
    (log-transfer account-a account-b 30)))

;; Both operations run in a single atomic transaction
atomically
  fn []
    transfer(account-a account-b 30)
    log-transfer(account-a account-b 30)

This is the key advantage over locks: you can call sub-transactions without worrying about lock ordering.

Side Effects Inside Transactions

Transactions may run more than once (on retry). Avoid observable side effects such as I/O, printing, or sending messages inside atomically. Use commit defers for effects that should fire exactly once on success:

;; BAD -- println may run multiple times
(atomically
  (fn []
    (tvar/write counter 42)
    (println "done")))

;; GOOD -- println fires once after commit
(atomically
  (fn []
    (tvar/write counter 42)
    (register-commit-defer nil log-fn)))

;; BAD -- println may run multiple times
atomically
  fn []
    tvar/write(counter 42)
    println("done")

;; GOOD -- println fires once after commit
atomically
  fn []
    tvar/write(counter 42)
    register-commit-defer(nil log-fn)

Limitations

• No nested atomically: Calling atomically inside atomically is an error. Compose by calling tvar/read/tvar/write directly in nested functions -- they share the caller's transaction context.
• No in-transaction I/O: A transaction body runs optimistically and may re-run several times before it commits (on a read conflict or a failed commit-time validation). Keep side effects -- printing, network, channel sends, consuming a ^linear value -- out of atomically; register on-commit work with the defer API instead.
• Read set limit: 256 TVars per transaction.
• Write set limit: 128 TVars per transaction.
• Defer limit: 32 defers per transaction.
• Pointee immutability for boxed payloads: A TVar's version stamp protects the stored pointer, not the bytes it points at. A TVar holding a boxed multi-word value (struct, vector, HAMT node) must treat that payload as immutable after it is published -- a writer allocates a fresh payload and swaps the pointer. Mutating a published payload in place defeats the optimistic read check and can expose a torn value to a concurrent reader.

Concurrency model

Commits use TL2 (Transactional Locking II), not a single global lock. Reads are optimistic and lock-free, validated against a global version clock; commit locks only the stripe buckets covering its write set (64 stripes), revalidates the read set, and publishes under a per-TVar lock bit. Throughput scales with the number of distinct TVars touched, not the number of live transactions.

Compiled vs interpreted. The compiled runtime (tur) is genuinely multi-threaded and runs the TL2 path above. The tree-walking interpreter (turi) is single-threaded, so a transaction never races a concurrent writer: its read-set validation always succeeds and it never aborts or blocks on retry. The observable isolation is identical -- an uncontended TL2 transaction behaves exactly like the interpreter's -- so a program that is correct under turi stays correct under tur. The one practical difference is that a retry/check-false with no way to make progress blocks forever under tur (another thread may yet commit) but is reported as an error under turi (nothing else can ever run).

Quick Reference

See Also

• STM Tutorial -- Conceptual overview and worked examples
• Threading Guide -- Locks, mutexes, Arc<T> for contrast
• HAMT Guide -- Persistent maps suitable for storage inside TVars
• Effects System Guide -- Exception handling within transactions
• src/stm.h -- Full C API with implementation notes