A LIFO stack can make waiting clients starve. Suppose client waits at the bottom of the stack. Before each current owner releases, a fresh client submits a request. That newest request is pushed above and is selected next. Every animation can finish promptly while waits forever.
This is LIFO starvation: service completion alone does not ensure starvation freedom. A FIFO queue prevents newer same-priority requests from passing , whereas replacing either priority-class FIFO queue by a LIFO stack adds this problem even within one priority class. Strict priority can already starve ordinary work, as in (b); the LIFO stack introduces a further unfairness that can also affect urgent work.
Use two FIFO queues, one for each priority class, and perform nonpreemptive strict-priority arbitration whenever the display becomes free:The same ownership invariant proves mutual exclusion. Among requests already accepted by the server, every pending urgent request takes precedence over every ordinary one. Each class retains its own arrival order. A newly received urgent request goes ahead of waiting ordinary requests but waits for the current animation's
owner = NONE
ordinary = empty FIFO queue
urgent = empty FIFO queue
forever:
message = receive_from_any_client()
if message.kind == REQUEST:
assert message.priority in {0, 1}
if message.priority == 1:
urgent.push_back(message.client)
else:
ordinary.push_back(message.client)
else if message.kind == RELEASE:
assert message.client == owner
owner = NONE
if owner == NONE:
if not urgent.empty():
owner = urgent.pop_front()
else if not ordinary.empty():
owner = ordinary.pop_front()
if owner != NONE:
send(owner, GRANT)RELEASE; the given protocol has no interruption or revocation operation.This is strict priority at dispatch, based on requests the server has received. Requests still in transit cannot influence a decision. If the transport provides a mailbox-draining operation, the server may also collect all currently delivered requests before dispatching; the two-FIFO queue selection rule remains the same.
Strict priority does not guarantee starvation freedom for ordinary clients under an endless supply of urgent work. If urgent traffic eventually stops, accepted requests have only finitely many earlier requests, and all service times are finite, every pending ordinary request is eventually granted. Guaranteeing ordinary progress under unlimited urgent traffic would require a different fairness policy, such as limiting consecutive urgent grants; that would relax strict priority.
Use a message-passing mutual exclusion server with an A client sends
owner field and a FIFO queue. A request includes its client's identity. The server handles one received message at a time, and a client has at most one outstanding request. The following pseudocode assumes reliable message passing and compliant clients:owner = NONE
waiting = empty FIFO queue
forever:
(kind, client) = receive_from_any_client()
if kind == REQUEST:
waiting.push_back(client)
else if kind == RELEASE:
assert client == owner
owner = NONE
if owner == NONE and not waiting.empty():
owner = waiting.pop_front()
send(owner, GRANT)REQUEST, waits for GRANT, runs its complete animation, and sends RELEASE before making another request.The invariant proving mutual exclusion is: at most one client has received an unreturned grant, and that client is
owner. Only the final block issues a grant, and it first requires no current owner. A valid release removes that ownership. Since clients use the display only while holding a grant, simultaneous use is impossible. The FIFO queue prevents accepted requests from being overtaken by later ones. With eventual message delivery, continued server execution, and finite animations, each accepted request is eventually served; these progress assumptions are separate from the safety invariant.Use the same bias, then an arithmetic right shift by ten:An arithmetic right shift of a two's complement integer computes division rounded down. For , this already equals truncation towards zero. For , the signed power-of-two division by biasing identity isIndeed, writing with makes the adjusted numerator ; its quotient rounded down is for every , including zero. Thus the code returns the signed quotient in all cases and contains no data-dependent branch. The final
div1024:
asrs r3, r0, #31 // -1 when a<0, otherwise 0
lsrs r3, r3, #22 // b = 1023 when a<0, otherwise 0
adds r0, r0, r3 // a+b, representable for every signed input
asrs r0, r0, #10 // floor((a+b)/1024)
bx lrbx lr simply returns to the caller.Let , let , and let denote the least nonnegative residue. Here is a signed 32-bit two's complement value. The source instructions, annotated with their derived values, are:The first instruction is an arithmetic right shift, so it replicates the sign bit. The second is a logical right shift, turning the all-one word into . The paired shifts then extract the low ten bits, as in (c). Their effect is the residue of even if its two's complement interpretation is negative, because divides the word modulus . The adjusted value is representable for every input: positive inputs are unchanged, and negative inputs gain only .
rem1024:
asrs r3, r0, #31 // r3 = -s: all zero bits or all one bits
lsrs r3, r3, #22 // r3 = b = 1023*s
adds r0, r0, r3 // r0 = a+b
lsls r0, r0, #22 // r0 has word value (a+b)*2^22 modulo 2^32
lsrs r0, r0, #22 // r0 = u = (a+b) modulo 1024, in 0,...,1023
subs r0, r0, r3 // r0 = u-b
bx lr // return u-bFor , , so the return value is the usual nonnegative remainder . For , put as a mathematical integer, and write with . If , then and the return value is zero. If , thenThese are precisely the remainders for C integer division, whose quotient truncates towards zero. In every case the result has the dividend's sign or is zero, has magnitude below , and satisfies . The proof includes the smallest representable input: was used only in mathematical reasoning, not as an overflowing machine operation.[ref]
C11 committee draft N1570. section 6.5.5 paragraph 6, quotient truncation and the quotient–remainder identity
For a 32-bit machine word and , use a left bit shift followed by a logical right shift:The left shift discards all but the lowest bits and moves those retained bits to the top. The logical right shift returns them to their original positions and fills the rest with zero. Hence
lsls r1, r0, #(32-k)
lsrs r1, r1, #(32-k)r1 contains , the remainder identified in (b). For the remainder is zero; for it is , so these endpoints can be handled directly.On a reduced instruction set computer, a bit mask such as may not fit an instruction's immediate field. Masking may therefore require materializing the constant in another processor register, possibly using several instructions or a memory load. Small shift counts are directly encodable, so the two shifts can save code space, a temporary processor register, or a load. This is an architecture-dependent advantage, rather than a universal speed claim. The source's compact instruction forms support these immediate shifts, while their bitwise AND form takes its other operand from a processor register.[ref]
Thumb 16-bit instruction set quick reference by Arm. page 1, Logical and Shift/rotate tables
A logical right shift by moves into position and fills the high positions with zero. Its unsigned interpretation isMeanwhile the original unsigned interpretation decomposes asBy integer division, , exactly the unsigned quotient. Thus the source instruction puts the required quotient into
r1. This is a proof from binary representation, rather than an assumption that every kind of right shift implements every kind of division. The displayed bit argument applies to , with endpoint operations implemented as a copy or zero where appropriate.Write an -bit binary string as , where each and is most significant. Its unsigned interpretation and two's complement interpretation areEquivalently, . The ranges are through and through , respectively. The same stored bits can therefore denote different integers depending on the chosen interpretation.
Keep a private immutable hash-map value in a mutable variable. Each update computes a complete replacement from snapshots and commits it once; this handles self-aliasing and arithmetic failure without partially modifying the receiver.
class MultiSetVarImp[T] extends MultiSetVar[T] {
private var table = Map.empty[T, Int]
def count(t: T): Int = table.getOrElse(t, 0)
def present: Seq[T] = table.keys.toVector
def copy(other: CompleteMultiSet[T]): Unit = {
val saved = other.present.distinct.iterator
.map(t => (t, other.count(t))).filter(_._2 != 0).toMap
table = saved
}
private def snapshot(other: MultiSetVar[T]): Map[T, Int] =
other.present.distinct.iterator
.map(t => (t, other.count(t))).filter(_._2 != 0).toMap
private def update(other: MultiSetVar[T], op: (Int, Int) => Int): Unit = {
val left = table
val right = snapshot(other)
val keys = left.keySet ++ right.keySet
val builder = Map.newBuilder[T, Int]
keys.foreach { t =>
val n = op(left.getOrElse(t, 0), right.getOrElse(t, 0))
if (n != 0) builder += ((t, n))
}
val replacement = builder.result()
table = replacement
}
def +(other: MultiSetVar[T]): Unit =
update(other, (a, b) => java.lang.Math.addExact(a, b))
def -(other: MultiSetVar[T]): Unit =
update(other, (a, b) => java.lang.Math.subtractExact(a, b))
def max(other: MultiSetVar[T]): Unit =
update(other, (a, b) => math.max(a, b))
def min(other: MultiSetVar[T]): Unit =
update(other, (a, b) => math.min(a, b))
def <=(other: CompleteMultiSet[T]): Boolean = {
val left = table
(left.keySet ++ other.present).forall { t =>
left.getOrElse(t, 0) <= other.count(t)
}
}
}The representation invariant is a finite map of nonzero counts with no representation exposed to callers. The abstraction function adds implicit zero elsewhere.
getOrElse implements that default; keys enumerates stored keys; distinct removes repeated input support entries; toMap builds an independent immutable map; and the builder accumulates the next representation before it is assigned. The private immutable snapshots remain stable while the new state is computed.For self-addition, both snapshots contain the same old counts, so they double; self-subtraction yields empty support; self-max and self-min leave the value unchanged. A distinct operand is never assigned or mutated. An overflow exception during building occurs before the final assignment, so the receiver remains unchanged. These are instances of snapshot-before-update semantics.
Lookup is expected under standard hash assumptions. Enumerating
present takes for support size . Combining two instances of this implementation takes expected time and temporary storage, including snapshot construction. For an arbitrary argument implementation, add the costs of its count calls: copying a default list-backed complete multiset can require , whereas copying the hash-backed version is expected linear. No generic interface can guarantee another implementation's query cost. Inputs are assumed to have finite, complete support enumerations and stable counts during an operation; concurrent mutation would need a separate synchronization contract.Yes: the mutable specification omits important state and frame clauses. Queries do not explicitly preserve the receiver, so an implementation could clear its state during
present, return an empty sequence, and satisfy the displayed coverage condition in the resulting state. Arithmetic does not explicitly preserve a distinct operand, so it could corrupt that operand as well as update the receiver. No initial value or independence requirement for copy is stated.The missing old-state annotation on the other operand is particularly serious under reference aliasing. If
other is the receiver, the printed addition equation becomes , which is impossible for a nonzero old count. Self-subtraction becomes rather than the intended zero; self-maximum admits arbitrarily increased counts. Specify instead, for every key,with both operands evaluated in their pre-states. Queries preserve all states; updates change only the receiver's abstract value and preserve a distinct operand; copy produces an independent snapshot of the argument's pre-state. Specify an empty initial state and checked representable arithmetic, or use unbounded counts.The fact that
present may contain duplicates or zero-count keys is not itself a violation: the printed condition expressly requires only a support-covering sequence. An implementation may strengthen this to an exact, duplicate-free support. Efficiency also needs a cost model or explicit bounds if it is to be a formal guarantee rather than an informal aspiration.Use the heap-numbered binary tree with root label zero and children . Its strict descendants in breadth-first search order are . A machine-safe
Node[Int] version stops at the largest representable label:class NumberNode(val label: Int) extends Node[Int] {
require(label >= 0)
def children(): Iter[Node[Int]] = new Iter[Node[Int]] {
private var candidate = 2L * label.toLong + 1L
private val last = candidate + 1L
def hasNext: Boolean = candidate <= last && candidate <= Int.MaxValue
def next(): Node[Int] = {
require(hasNext)
val answer = new NumberNode(candidate.toInt)
candidate += 1L
answer
}
}
}
val traversal = breadthFirst(new NumberNode(0))
var expected = 1
while (expected <= 1000) {
assert(traversal.hasNext)
assert(traversal.next().label == expected)
expected += 1
}The arithmetic is widened before computing child labels, so no negative wrapped labels occur. Repeated
hasNext calls should not skip nodes; a leaf root should produce immediate exhaustion, and uneven finite trees should retain sibling order across parents. A fresh second traversal should start again at one.Literal unbounded increase is impossible with the bounded
Int type. For a genuinely infinite test, change the label and child arithmetic to BigInt; the same construction then has no representational endpoint. The shown finite-prefix test already exercises lazy traversal without allocating the entire very large Int-labelled tree.Keep a FIFO queue of pending child iterators, ordered by the breadth-first order of their parents. Defer even the call creating a node's children until that iterator reaches the front and is needed:
def breadthFirst[T](node: Node[T]): Iter[Node[T]] = {
def childrenLater(n: Node[T]): Iter[Node[T]] = new Iter[Node[T]] {
private lazy val children = n.children()
def hasNext: Boolean = children.hasNext
def next(): Node[T] = {
require(children.hasNext, "empty child iterator")
children.next()
}
}
val pending = scala.collection.mutable.Queue.empty[Iter[Node[T]]]
pending.enqueue(childrenLater(node))
new Iter[Node[T]] {
private def normalize(): Unit = {
while (pending.nonEmpty && !pending.head.hasNext) pending.dequeue()
}
def hasNext: Boolean = {
normalize()
pending.nonEmpty
}
def next(): Node[T] = {
normalize()
require(pending.nonEmpty, "no more descendants")
val answer = pending.head.next()
pending.enqueue(childrenLater(answer))
answer
}
}
}Here “descendants” excludes the supplied root: the first output is its first child. A self-inclusive convention can prepend
unitIter(node) without changing the traversal logic. The queue invariant says its iterators enumerate the still-unreported children of already encountered parents, in parent breadth-first order. Consuming one child appends that child's deferred iterator after all earlier parents' pending children. Exhausted child iterators contribute nothing and can be discarded. This proves increasing depth and sibling order without constructing a complete level in advance.This lazy breadth-first traversal with child iterators never eagerly materializes all children or the whole tree. A finite prefix can therefore be traversed on a genuinely infinite tree. As with any strict breadth-first ordering, an infinite earlier level prevents reaching a deeper level; no algorithm can place a deeper node after every member of an infinite earlier level at a finite output position. For a locally finite tree, every finite-depth level is finite and each descendant is eventually reached, assuming the underlying iterator operations terminate. Fresh child iterators and exclusive ownership of consumed iterator states are essential to this argument.
def cat[T](t: Iter[T], u: Iter[T]): Iter[T] = new Iter[T] {
def hasNext: Boolean = t.hasNext || u.hasNext
def next(): T = {
if (t.hasNext) t.next()
else {
require(u.hasNext, "empty iterator")
u.next()
}
}
}
def cat[T](t: Cursor[T], u: Cursor[T]): Cursor[T] = new Cursor[T] {
def hasCurrent: Boolean = t.hasCurrent || u.hasCurrent
def current: T = {
if (t.hasCurrent) t.current
else {
require(u.hasCurrent, "empty cursor")
u.current
}
}
def next(): Unit = {
if (t.hasCurrent) t.next()
else {
require(u.hasCurrent, "empty cursor")
u.next()
}
}
}Assume the two destructive inputs have noninterfering states; in particular, passing the same iterator twice does not create a replayable copy of its original sequence. Fresh independent iterators provide that behavior. Under this ownership condition, the abstraction function is always the concatenation
t.seq ++ u.seq. Consumption from t removes the concatenation's head; once t is empty, consumption from u does so. Availability tests short-circuit, so an infinite first sequence never unnecessarily touches the second.For finite lengths , under a client loop with one availability test and one advance per element, the iterator version directly invokes
t.hasNext times, including the final false test. For a cursor client with one availability test, one current read and one advance per element, the corresponding count is . These count calls made by the shown adapters, not extra checks hidden inside arbitrary underlying methods. A client can repeat availability/current queries arbitrarily often, so no bound depending only on applies without such a client protocol.Cache a permanent “first input exhausted” flag after the first negative test to avoid repeated queries to
t while traversing u; this reduces the dependence to first-input queries under the same protocols. Availability caching can reduce additional repeated checks. The flag is sound because an iterator's consumed sequence does not spontaneously grow again.A single flag represents whether the only element remains:
def unitIter[T](t: T): Iter[T] = new Iter[T] {
private var available = true
def hasNext: Boolean = available
def next(): T = {
require(available, "empty iterator")
available = false
t
}
}
def unitCursor[T](t: T): Cursor[T] = new Cursor[T] {
private var available = true
def hasCurrent: Boolean = available
def current: T = {
require(available, "empty cursor")
t
}
def next(): Unit = {
require(available, "empty cursor")
available = false
}
}Map a pure, terminating function only when a value is demanded; use the adapters to obtain the cursor form with caching:
def map[T, U](f: T => U, it: Iter[T]): Iter[U] = new Iter[U] {
def hasNext: Boolean = it.hasNext
def next(): U = {
require(it.hasNext, "empty iterator")
f(it.next())
}
}
def map[T, U](f: T => U, cur: Cursor[T]): Cursor[U] =
asCursor(map(f, asIter(cur)))Each demanded output is the function applied to the corresponding input, preserving order and lazy access even for an infinite sequence. The cursor adapter caches its mapped current value, so repeated reads need not recompute
f. Totality/purity of f is the usual assumption for the mathematical sequence-map postcondition; an exception-throwing or state-changing function would need additional behavioral clauses.Both functions may be named
map because their second parameter types differ, Iter[T] versus Cursor[T]. Method overloading selects the applicable signature; its distinction is not based solely on the return type.def asIter[T](cur: Cursor[T]): Iter[T] = new Iter[T] {
def hasNext: Boolean = cur.hasCurrent
def next(): T = {
require(cur.hasCurrent, "empty iterator")
val answer = cur.current
cur.next()
answer
}
}The two abstract sequences are identical. A
next call returns the old head and removes it, while hasNext only queries availability. No element is read at construction or during an availability test, and no later element is read while returning the current one. Thus the adapter is not too eager. The source's Cursor.current clause needs the implicit precondition that its sequence is nonempty; taking the head of an empty sequence is undefined. The checks above satisfy that requirement even without relying on the client convention.Cache only a requested current element. Merely constructing the cursor, or asking whether it is nonempty, must not fetch a value from the iterator:
def asCursor[T](it: Iter[T]): Cursor[T] = new Cursor[T] {
private var cached: Option[T] = None
def hasCurrent: Boolean = cached.nonEmpty || it.hasNext
def current: T = {
if (cached.isEmpty) {
require(it.hasNext, "empty cursor")
cached = Some(it.next())
}
cached.get
}
def next(): Unit = {
if (cached.nonEmpty) cached = None
else {
require(it.hasNext, "empty cursor")
it.next()
()
}
}
}The abstraction function for the adapter is
it.seq when no value is cached and [cachedValue] ++ it.seq otherwise. Fetching current removes one underlying iterator value but saves it, so the cursor's abstract sequence is unchanged; repeated reads return the same value. Advancing either discards that cache or consumes one uncached iterator value. No following element is prefetched.A too-eager implementation could call
it.next() at construction, or fetch a new element immediately after every advance, even when the client never requests it. That can trigger unnecessary work or nontermination on a difficult stream. This lazy iterator-to-cursor adapter avoids both behaviors and checks the underlying access preconditions itself. The wrapped iterator is assumed to be used exclusively through the adapter; independent external consumption would invalidate the shared-state abstraction.Construct the mixed object with a concrete document implementation beneath the plugin:
val doc: DocImp with CharCountPlugin = new DocImp with CharCountPluginIts type combines
DocImp and CharCountPlugin, so document operations and count are available. For example, inserting two 'a' characters and then deleting one leaves doc.count('a') == 1. The plugin is on the right of the concrete superclass in Scala's composition, so its edit methods extend the underlying implementations.Reuse the machinery with the digit interval:
trait DigitCountPlugIn extends CharCountPlugin {
override protected def firstCounted: Char = '0'
override protected def numberCounted: Int = 10
}Its
count precondition is now '0' <= ch && ch <= '9'. It counts digits while permitting all characters to be stored. This is an alternative configured counter, rather than a second independent lowercase counter in the same object; simultaneous independent alphabets would require separate counters or a combined mapping.Use a fixed-size count array and protected hooks defining a stable character-to-slot mapping. The default hooks count the ASCII lowercase interval. The document must start empty, and all subsequent edits must pass through the mixin methods, as they do for
new DocImp with CharCountPlugin.trait CharCountPlugin extends Doc {
protected def firstCounted: Char = 'a'
protected def numberCounted: Int = 26
protected def slot(ch: Char): Int = {
val k = ch.toInt - firstCounted.toInt
if (0 <= k && k < numberCounted) k else -1
}
private lazy val totals = Array.fill(numberCounted)(0)
abstract override def insert(pos: Int, ch: Char): Unit = {
val k = slot(ch)
super.insert(pos, ch)
if (k >= 0) totals(k) += 1
}
abstract override def delete(pos: Int): Char = {
val removed = super.delete(pos)
val k = slot(removed)
if (k >= 0) totals(k) -= 1
removed
}
def count(ch: Char): Int = {
val k = slot(ch)
require(k >= 0, "character is outside the counted alphabet")
totals(k)
}
}The additional representation invariant is that each array slot equals the number of corresponding characters in the current document. Initially all counts are zero. Each successful underlying edit changes exactly one relevant count, while a failed position check throws before any count is changed. Returning the actual deleted character lets deletion adjust the correct slot.
count takes time for the fixed alphabet, as do the mixin's additions to edit cost. The lazy array avoids reading subclass-overridden size hooks during trait construction; the hooks must remain stable. An extension can override the interval hooks, or override slot with another fixed finite mapping. This is stackable modification by a trait: abstract override permits the method to call the next implementation of super, supplied here by DocImp.[ref] There are unlisted articles, also show them or only show them.