Past exam of the year 1 of the computer science course of the University of Oxford / 2022 / Imperative programming (resit) / 8

Table of contents
- a 8
  - Solution a
- b 8
  - Solution b
- c 8
  - Solution c
- d 8
  - Solution d
- e 8
  - i e
    - Solution i
  - ii e
    - Solution ii

A complete multiset is a finite-support signed count function. An absent key has count zero; negative counts are allowed. One simple default implementation uses a protected immutable association list with unique keys and nonzero values. Its default is empty, and optimized subclasses may override the public queries.

trait CompleteMultiSet[T] {
  // Representation contract: finite, immutable, unique keys, nonzero counts.
  protected def entries: List[(T, Int)] = Nil

  def count(t: T): Int =
    entries.find { case (key, _) => key == t }.map(_._2).getOrElse(0)

  lazy val present: Seq[T] = entries.map(_._1)

  private def combine(other: CompleteMultiSet[T],
                      op: (Int, Int) => Int): CompleteMultiSet[T] = {
    val keys = (present.toList ++ other.present.toList).distinct
    val resultRows = keys.flatMap { t =>
      val n = op(count(t), other.count(t))
      if (n == 0) Nil else List((t, n))
    }
    new CompleteMultiSet[T] {
      override protected val entries: List[(T, Int)] = resultRows
    }
  }

  def +(other: CompleteMultiSet[T]): CompleteMultiSet[T] =
    combine(other, (a, b) => java.lang.Math.addExact(a, b))

  def -(other: CompleteMultiSet[T]): CompleteMultiSet[T] =
    combine(other, (a, b) => java.lang.Math.subtractExact(a, b))

  def max(other: CompleteMultiSet[T]): CompleteMultiSet[T] =
    combine(other, (a, b) => math.max(a, b))

  def min(other: CompleteMultiSet[T]): CompleteMultiSet[T] =
    combine(other, (a, b) => math.min(a, b))

  def <=(other: CompleteMultiSet[T]): Boolean =
    (present.toList ++ other.present.toList).distinct.forall { t =>
      count(t) <= other.count(t)
    }

  override def toString: String =
    present.distinct.filter(t => count(t) != 0)
      .map(t => s"$t:${count(t)}").mkString("{", ", ", "}")
}

The representation invariant and abstraction function assign the association-list value at a stored key and zero elsewhere. Every operation preserves both operands and returns a fresh immutable value. The finite-support pointwise operations principle makes the support union sufficient because every operation sends

(0, 0)

to zero. It is necessary for signed counts: the empty value is not at most a value having count $- 1$ at one key, although the empty left support alone would give a vacuous true comparison. Likewise, pointwise minimum can retain a negative count appearing only in the other operand.

present == List() represents the all-zero, empty complete multiset. The list-backed default count takes

Θ (1)

time for a first-entry hit or an empty list, and

Θ (N)

in the worst case for a missing or final key, assuming constant-cost key equality. The default binary operations can consequently take quadratic time; they are deliberately simple defaults, not optimized implementations. The lazy present avoids an early call to a subclass's representation during initialization.

Counts use Int, so addition and subtraction explicitly throw ArithmeticException when the mathematical result is unrepresentable instead of silently wrapping. Equivalently, their mathematical precondition requires representable result counts. This machine-size restriction is separate from permitting negative counts.

b

 0  0

Solution

 0  0

With the completed default trait from part (a), the expression is well-typed and creates the empty complete multiset, provided the type T is in scope. Every member has a concrete default, entries is empty, and every count is zero.

With only the originally printed abstract trait, it is not a legal instantiation, because abstract queries and operations remain unimplemented. The distinction is whether part (a)'s supplied defaults are in force, rather than any special treatment of anonymous objects.

c

 0  0

Solution

 0  0

Use an immutable hash map for the concrete value, omitting zero-count entries:

class CompleteMultiSetImp[T](initial: Map[T, Int]) extends CompleteMultiSet[T] {
  private val table = initial.filter { case (_, n) => n != 0 }
  override def count(t: T): Int = table.getOrElse(t, 0)
  override lazy val present: Seq[T] = table.keys.toVector
}

def cms[T](ts: T*): CompleteMultiSet[T] =
  new CompleteMultiSetImp[T](ts.distinct.map(t => (t, 1)).toMap)

The abstraction function is the map with implicit zero outside its keys. Immutable storage makes saved values independent of later operations, and the inherited defaults dispatch through the overridden count and present. A hash lookup has expected constant cost under ordinary hashing assumptions, with collision-dependent worst cases.

Repeated arguments still get count one, because the constructor first removes duplicates. All other elements have count zero, satisfying the intended stronger reading of the constructor specification. Treating ts as a bag and adding one for every repetition would implement a different operation.

d

 0  0

Solution

 0  0

Nonnegative count functions form a valid subtype of the immutable value interface, but they are not closed under its exact subtraction. Preserve the inherited result type rather than silently changing the subtraction contract:

trait MultiSet[T] extends CompleteMultiSet[T] {
  // Additional invariant: count(t) >= 0 for every t.
  // Inherited arithmetic still returns CompleteMultiSet[T].
}

class MultiSetImp[T](initial: Map[T, Int])
    extends CompleteMultiSetImp[T](initial) with MultiSet[T] {
  require(initial.values.forall(_ >= 0), "negative multiplicity")
}

def ms[T](ts: T*): MultiSet[T] =
  new MultiSetImp[T](ts.distinct.map(t => (t, 1)).toMap)

The invariant guarantees nonnegative multiplicities in every MultiSet object, and the factory gives each supplied element exactly one occurrence. Since the objects are immutable, inherited operations cannot invalidate that invariant in the receiver. Their declared result is a complete multiset, which can legitimately contain negative counts; for example, subtracting a positive count from zero produces a signed result.

If an ordinary multiset-only difference is desired, introduce a separate operation with count

max (0, a (t) - b (t))

, or an interface whose subtraction explicitly has that contract. Replacing the parent's exact difference by truncated difference under the same signature would violate behavioral subtyping; strengthening its precondition to forbid negative results would also fail to implement the parent's unrestricted mathematical contract. Retaining the complete result type above reuses every correct default without that substitution error.

e

 0  0

i

 0  0

Solution

 0  0

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

a^{'} = a_{0} + a^{'}

, which is impossible for a nonzero old count. Self-subtraction becomes

a^{'} = a_{0} - a^{'}

rather than the intended zero; self-maximum admits arbitrarily increased counts. Specify instead, for every key,

a^{'} (t) = o p (a_{0} (t), b_{0} (t)),

(1)

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.

ii

 0  0

Solution

 0  0

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

O (1)

under standard hash assumptions. Enumerating present takes

O (K)

for support size

K

. Combining two instances of this implementation takes expected

O (K + M)

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

Θ (M^{2})

, 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.

Past exam of the year 1 of the computer science course of the University of Oxford / 2022 / Imperative programming (resit) / 8

a

Solution

b

Solution

c

Solution

d

Solution

e

i

Solution

ii

Solution

 Ancestors (10)

 Discussion (0)

 Articles by others on the same topic (0)

Past exam of the year 1 of the computer science course of the University of Oxford / 2022 / Imperative programming (resit) / 8

 Discussion (0)  Subscribe (1)

 Discussion (0)