(std stm queue)

Overview

A transactional FIFO queue supporting atomic composition with other queues and locations, or synchronization as a CML event.

(import (std stm))
(import (std stm queue))

(def jobs (make-bounded-queue 100))
(def done (make-queue))

;; Outside a transaction, using channel-like operations.
(queue-put jobs "resize a.png")
(queue-get jobs)                       ; "resize a.png"

;; In a transaction: take a job and record it as started in one atomic step.
(atomically
 (fun (tx)
   (let ((job (queue-pop! tx jobs)))
     (queue-push! tx done job)
     job)))

;; Wait for a job with a 1-second timeout.
(sync (choose (wrap (queue-recv jobs) Some)
              (wrap (timeout (seconds 1)) (fun (_) None))))

A (TQueue T) stores elements of type T in first-in, first-out order. Backed by transactional locations from (std stm), all operations participate in the surrounding transaction.

Two API layers. Within a transaction, operations accept an explicit Tx: queue-push!, queue-pop!, queue-try-pop!, queue-peek, queue-try-peek, queue-pop-all!, queue-length, and queue-empty?. Outside a transaction, channel-style operations provide event-based access: queue-send and queue-recv return events, while queue-put and queue-get synchronously execute them.

Atomic composition. Unlike channels, transactions can atomically inspect and modify multiple queues and STM locations simultaneously: transfer elements between queues, dequeue from multiple queues at once, or consume an element and update shared state in a single atomic step without intermediate states visible to other fibers.

Waiting and retrying. queue-pop! and queue-peek retry when the queue is empty, and queue-push! retries when a bounded queue is full. The transaction blocks until another transaction modifies the queue. queue-recv and queue-send integrate with choose, allowing timeouts or multi-resource coordination. A cancelled branch performs no side effects.

Ordering. Elements are dequeued in the order in which the pushing transactions committed. Fibers waiting on a queue are resumed without guaranteed ordering.

Contention. Pushes write to the back of the queue and pops write to the front, so producers and consumers do not contend with each other unless the front list is exhausted and elements must be transferred. Pushes contend with other pushes, and pops contend with other pops. Bounded queues decouple push allocation counters from pop release counters, matching the design of Haskell’s TBQueue.

Complexity. Operations run in amortized O(1) time; queue-length runs in O(1) time; queue-pop-all! runs in O(n) time.

Reference

Types

TQueue

Functions

make-bounded-queue
make-queue
queue-empty?
queue-get
queue-length
queue-peek
queue-pop!
queue-pop-all!
queue-push!
queue-put
queue-recv
queue-send
queue-try-peek
queue-try-pop!

Types

`TQueue`

record ↑ Types

A transactional FIFO queue holding elements of type %a.

%a: The element type.

Functions

`make-queue`

function ↑ Functions

(: make-queue (-> (TQueue %a)))
(make-queue)

Creates an unbounded transactional queue.

returns: A new empty queue.

`make-bounded-queue`

function ↑ Functions

(: make-bounded-queue (-> int (TQueue %a)))
(make-bounded-queue capacity)

Creates a bounded transactional queue with the specified maximum capacity.

capacity: Maximum number of elements allowed in the queue. Must be at least 1.
returns: A new bounded queue.
raises System.ArgumentException: When capacity is less than 1.

Pushing to a full queue retries, providing backpressure so producers wait until consumers free space.

`queue-push!`

function ↑ Functions

(: queue-push! (-> Tx (TQueue %a) %a void))
(queue-push! tx q x)

Enqueues an element to the back of the queue within the transaction.

tx: The transaction log context.
q: The queue.
x: The element to enqueue.

On a bounded queue that is full, this operation retries until space is freed by a concurrent pop.

`queue-pop!`

function ↑ Functions

(: queue-pop! (-> Tx (TQueue %a) %a))
(queue-pop! tx q)

Dequeues and returns the front element within the transaction. Retries if the queue is empty.

tx: The transaction log context.
q: The queue.
returns: The front element.

`queue-try-pop!`

function ↑ Functions

(: queue-try-pop! (-> Tx (TQueue %a) (Option %a)))
(queue-try-pop! tx q)

Dequeues and returns the front element within the transaction, or None if the queue is empty.

tx: The transaction log context.
q: The queue.
returns: (Some item), or None if the queue is empty.

`queue-peek`

function ↑ Functions

(: queue-peek (-> Tx (TQueue %a) %a))
(queue-peek tx q)

Returns the front element without removing it, within the transaction. Retries if the queue is empty.

tx: The transaction log context.
q: The queue.
returns: The front element.

`queue-try-peek`

function ↑ Functions

(: queue-try-peek (-> Tx (TQueue %a) (Option %a)))
(queue-try-peek tx q)

Returns the front element without removing it, or None if the queue is empty.

tx: The transaction log context.
q: The queue.
returns: (Some item), or None if the queue is empty.

`queue-pop-all!`

function ↑ Functions

(: queue-pop-all! (-> Tx (TQueue %a) (List %a)))
(queue-pop-all! tx q)

Dequeues and returns all elements from the queue in order.

tx: The transaction log context.
q: The queue.
returns: A list of elements from front to back, or an empty list if the queue is empty (does not retry).

On a bounded queue, this frees all reserved capacity.

`queue-length`

function ↑ Functions

(: queue-length (-> Tx (TQueue %a) int))
(queue-length tx q)

Returns the current number of elements in the queue.

tx: The transaction log context.
q: The queue.
returns: The element count.

Reads both ends of the queue, causing transaction conflicts with concurrent pushes and pops. Call only when necessary.

`queue-empty?`

function ↑ Functions

(: queue-empty? (-> Tx (TQueue %a) bool))
(queue-empty? tx q)

Checks whether the queue is empty.

tx: The transaction log context.
q: The queue.
returns: #t if the queue is empty, #f otherwise.

`queue-send`

function ↑ Functions

(: queue-send (-> (TQueue %a) %a (Event Unit)))
(queue-send q x)

Returns an event that enqueues x to the back of the queue.

q: The queue.
x: The element to enqueue.
returns: An event enabled when the push commits.

On a bounded queue that is full, the event is not enabled until a pop frees space. If another branch of a choose is selected, no element is enqueued.

`queue-recv`

function ↑ Functions

(: queue-recv (-> (TQueue %a) (Event %a)))
(queue-recv q)

Returns an event that dequeues and yields the front element.

q: The queue.
returns: An event enabled when an element is available.

If another branch of a choose is selected, no element is dequeued.

`queue-put`

function ↑ Functions

(: queue-put (-> (TQueue %a) %a void))
(queue-put q x)

Enqueues x to the back of the queue, blocking while a bounded queue is full.

q: The queue.
x: The element to enqueue.

Equivalent to (sync (queue-send q x)) in a fiber, or (sync/blocking (queue-send q x)) outside a fiber context.

`queue-get`

function ↑ Functions

(: queue-get (-> (TQueue %a) %a))
(queue-get q)

Dequeues and returns the front element, blocking while the queue is empty.

q: The queue.
returns: The front element.

Equivalent to (sync (queue-recv q)) in a fiber, or (sync/blocking (queue-recv q)) outside a fiber context.