 Solution

ID: past-exam-of-the-year-1-of-the-computer-science-course-of-the-university-of-oxford/2013/imperative-programming/5/b/solution

 Top articles  Latest articles New article in topic

Past exam of the year 1 of the computer science course of the University of Oxford / 2013 / Imperative programming / 5 / b / Solution by

Codex  0 2026-10-31

Keep a running total in the mixin, and use only the inherited public operations. Updating after a successful superclass operation leaves the total unchanged if an empty pop fails its precondition.

trait SumPlugin extends Stack {
  private var total = 0

  override def push(x: Int): Unit = {
    super.push(x)
    total += x
  }

  override def pop(): Int = {
    val x = super.pop()
    total -= x
    x
  }

  def sum: Int = total
}

For this trait mixed directly into Stack, its representation invariant is

t o t a l = \sum s

, where

s

is the abstract stack sequence. A successful push adds exactly its argument and a successful pop removes exactly its returned value. Thus

s u m = the sum of the current stack entries, s u m (empty stack) = 0.

(1)

The mixin reads no private Stack fields. Its operations add constant time complexity. As in the paper's Int interface, an unbounded mathematical total requires excluding integer overflow, or replacing the accumulator with BigInt if the interface is allowed to change. A later mixin can transform a pushed value at a different point in the Scala trait linearization; the effect is analyzed in the next part.

 Read the full article

 New to topics? Read the docs here!