# 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](stm-tutorial.md). This guide focuses on the API and mechanics.

## Core Concepts

| Concept | Description |
|---|---|
| `TVar` | A mutable cell readable/writable only inside a transaction |
| `atomically` | Runs a transaction; retries automatically on conflict |
| `retry` | Voluntarily abort and block until a watched `TVar` changes |
| `or-else` | Try one branch; if it retries, try the other |

## TVar Lifecycle

```turmeric
(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`:

```turmeric
;; 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

```turmeric
;; 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 `TVar`s read during this transaction changes, then re-runs from the beginning:

```turmeric
;; 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:

```turmeric
;; 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:

```turmeric
(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)

```turmeric
;; 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)

```turmeric
;; 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:

```turmeric
;; 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:

```turmeric
;; 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 (v1)

- **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.
- **Read set limit:** 256 TVars per transaction.
- **Write set limit:** 128 TVars per transaction.
- **Defer limit:** 32 defers per transaction.
- **Global lock (v1):** Phase 20 uses a single global mutex; per-TVar fine-grained locking arrives in Phase 21.

## Quick Reference

| Function | Description |
|---|---|
| `tvar/new val` | Create a TVar with initial value |
| `tvar/read tv` | Read TVar (must be inside `atomically`) |
| `tvar/write tv val` | Write TVar (must be inside `atomically`) |
| `tvar/swap tv new` | Write and return old value |
| `tvar/cas tv old new` | Conditional write; returns bool |
| `atomically fn` | Run `fn` as an atomic transaction |
| `retry` | Abort and block until a read TVar changes |
| `or-else fn-a fn-b` | Try `fn-a`; if it retries, try `fn-b` |

## See Also

- [STM Tutorial](stm-tutorial.md) — Conceptual overview and worked examples
- [Threading Guide](threading-guide.md) — Locks, mutexes, `Arc<T>` for contrast
- [HAMT Guide](hamt-guide.md) — Persistent maps suitable for storage inside TVars
- [Effects System Guide](effects-system-guide.md) — Exception handling within transactions
- [src/stm.h](../../src/stm.h) — Full C API with implementation notes