CL-STM

Protocol 

Transactions 

(defclass transaction ()
  ())
(defgeneric perform (transaction)
  (:documentation "Run TRANSACTION atomically with respect to
all other threads in a new thread.

If the transaction retries, then the thread loops again
re-executing the transaction and commiting it to memory.

PERFORM returns a thread created by BORDEAUX-THREADS as its
value."))
(defgeneric execute (transaction)
  (:documentation "Execute TRANSACTION and return 3 values.

1. A boolean specifying whether or not the transaction retried.

2. A transaction log of all the changes that occured.

3. A list of values that TRANSACTION returns."))
(defgeneric orelse (tx1 tx2)
  (:documentation "Compose two transactions alternatively.
ORELSE returns a new transaction.

We perform TX1 and if it succeeds then we're done.  If it fails
then we perform TX2.

If performing TX2 succeeds then we're done.  If it fails we try
to perform TX1 again, and so on.

The transaction's return value (not ORELSE's) is nondeterministic
because we can't tell in advance which transaction succeeds.

ORELSE is just the plumbing behind the TRY macro, which is
just a variable arity version of ORELSE."))
(defgeneric sequence (tx1 tx2)
  (:documentation "Compose two transactions sequentially.
SEQUENCE returns a new transaction.

If either TX1 or TX2 retries then the whole transaction retries.

The transaction's return value (not SEQUENCE's) is the return
value of TX2.

SEQUENCE is just the plumbing behind the PROGT macro, which is
just a variable arity version of SEQUENCE."))

Transaction logs 

(defclass tlog ()
  ()
  (:documentation "A transaction log (TLOG) is a record of what
reads and writes have been done.

Transaction logs are written during the execution of a
transaction (using READ-TVAR and WRITE-TVAR).  Transactions logs
are committed to memory by COMMIT later on."))
(defgeneric commit (log)
  (:documentation "Commit a LOG to memory.

It returns a boolean specifying whether or not the transaction
log was committed.  If the transaction log couldn't be committed
it probably means that another transaction log that writes the
same variables is being committed."))
(defgeneric check? (log)
  (:documentation "Check that LOG is consistent.

It returns a boolean specifying whether or not LOG is valid with
respect to the current Common Lisp world.  CHECK can be used to
see if a transaction isn't consistent before committing it."))
(defgeneric merge-logs (log1 log2)
  (:documentation "Merge LOG1 and LOG2.

Any reads and writes in LOG2 shadow the reads and writes in
LOG1."))
(defgeneric wait (log)
  (:documentation "WAIT causes the current thread to wait for a
change in any of LOG's reads and writes."))

Transaction variables 

(defclass tvar ()
  ()
  (:documentation "A transactional variable (TVAR) holds a value.

See READ-TVAR and WRITE-TVAR for reading and writing them."))
(defgeneric read-tvar (var log)
  (:documentation "Record the reading of VAR to LOG.

READ-TVAR is only called when transactions are being recorded,
and LOG is normally the special variable *LOG*.

READ-TVAR is just the plumbing behind taking the SLOT-VALUE of a
transactional slot.  Just use readers and accessors as you
normally would on transactional objects."))
(defgeneric write-tvar (var log val)
  (:documentation "Record the writing of VAL to VAR to LOG.

WRITE-TVAR is only called when transactions are being recorded,
and LOG is normally the special variable *LOG*.

WRITE-TVAR is just the plumbing behind SETF'ing a transactional
slot.  Just use SETF as you normally would on transactional
objects."))
(defgeneric unwait (var)
  (:documentation "UNWAIT causes all threads waiting for VAR to
change to wake up."))

Recording transactions 

(defvar *record-transactions* nil
  "A boolean specifying whether or not transactions are recorded
to log.")
(defun recording-p ()
  *record-transactions*)
(defmacro with-recording (&body body)
  "Turn recording of reads and writes on.  Recording is normally
on inside transactions."
  `(let1 *record-transactions* t
     ,@body))
(defmacro without-recording (&body body)
  "Turn recording of reads and writes off.  Recording is normally
off outside transactions (ie at the REPL) and when initializing
transactional objects."
  `(let1 *record-transactions* nil
     ,@body))

Current transaction log 

(defvar *tlog* nil
  "The current transaction log.")
(defun current-tlog ()
  *tlog*)
(defmacro with-tlog (log &body body)
  "Execute BODY with the default transasction log being LOG."
  `(let1 *tlog* ,log
     (with-recording
       ,@body)))
(defmacro with-new-tlog (var &body body)
  "Execute BODY with the default transaction log being a newly
allocated transaction log bound to VAR."
  `(let1 ,var (new 'standard-tlog)
     (with-tlog ,var
       ,@body)))