Source paper: released examination archive, member a10098w1-3.pdf; original cover dated 2016-09-15.
Because , exponentiation to base is strictly increasing. The definition of the floor function gives , so the equivalent characterization of the integer logarithm is
(1)
Here is a nonnegative integer; gives .
Keep both the exponent and its power. This Oberon procedure uses only the permitted arithmetic:
PROCEDURE IntLog(b, n: INTEGER): INTEGER;
VAR i, p: INTEGER;
BEGIN
  i := 0; p := 1;
  WHILE p*b <= n DO
    p := p*b; i := i+1
  END;
  RETURN i
END IntLog;
The loop invariant is and . It holds initially because . A successful guard permits the next power, and the two assignments preserve the relation between and . At exit, , which is exactly part (a). Each iteration increases , and only finitely many powers of are at most , proving algorithm termination. The returned value is . Its running time is arithmetic operations; integer overflow is deferred to part (e).
Use repeated squaring, including index zero:
b2[0] := b; top := 0;
WHILE b2[top]*b2[top] <= n DO
  b2[top+1] := b2[top]*b2[top];
  top := top+1
END;
The loop invariant is for , with for every stored entry except possibly the initial entry when . Squaring gives , proving preservation. The first failed guard identifies the first larger power outside the range. If , no power with needs storing.
Index zero is deliberately included. The original paper asks for indices but then claims that their products represent every allowable power. Taken without , that claim fails for odd exponents, since every available exponent would be even. The extra initialized entry makes the intended binary expansion argument valid without changing the requested entries.
Let be the largest representable positive integer. The worst case is , requiring indices through . Thus enough = 5 for signed 32-bit integers, or 6 for signed 64-bit integers, suffices for stored powers that fit; a larger convenient constant is harmless. This counts slots starting at zero and does not reserve a slot for an out-of-range sentinel. The multiplication in the guard can still suffer integer overflow, independently of this array capacity bound.
Store a second array weight with weight[k] = 2^k. Descending through the binary digits of the answer gives this greedy algorithm:
PROCEDURE FastLog(b, n: INTEGER): INTEGER;
VAR b2, weight: ARRAY enough OF INTEGER;
    top, k, i, p: INTEGER;
BEGIN
  b2[0] := b; weight[0] := 1; top := 0;
  WHILE b2[top]*b2[top] <= n DO
    b2[top+1] := b2[top]*b2[top];
    weight[top+1] := weight[top]+weight[top];
    top := top+1
  END;
  i := 0; p := 1; k := top;
  WHILE k >= 0 DO
    IF p*b2[k] <= n THEN
      p := p*b2[k]; i := i+weight[k]
    END;
    k := k-1
  END;
  RETURN i
END FastLog;
For the second loop, write . Immediately before processing , its loop invariant is
(1)
Initially the failed squaring guard gives ; this also holds when , since then . The test succeeds exactly when . If successful, adding selects that binary digit; otherwise the upper bound tightens to . Either way the invariant holds for the next smaller . At , , so i = L.
There are squarings and descending tests. For fixed , this is arithmetic operations, hence logarithmic in the bit length of , and also within the weaker bound. This counts arithmetic operations on integers as unit cost; bit complexity would also charge for the growing operands. No division is used.
Let be the maximum positive machine integer. A positive product suffers integer overflow when . The vulnerable expressions are p*b in part (b), b2[top]*b2[top] in the table guard, and p*b2[k] in the descending search. Even a rejected candidate must be evaluated before its comparison with .
The table guard becomes dangerous as soon as its current entry exceeds : approximately for signed 32-bit integers, or for signed 64-bit integers. These are thresholds for the intermediate power, not for alone. For example, with 32-bit arithmetic, and reach the stored power and then try its overflowing square . If , even the initial square may overflow for a tiny . In part (b), the final test can overflow when the next power above exceeds ; at , this already happens for .
For positive operands, integer division gives the exact equivalence . Therefore replace the three guards respectively by
p <= n DIV b
b2[top] <= n DIV b2[top]
p <= n DIV b2[k]
and perform each multiplication only after its guard succeeds. Every accepted product is then at most . With these guarded products and sufficient table capacity, the algorithms work throughout , . The stored exponents and weights also fit in those machine ranges. Checking for overflow after multiplying would be too late.
Separate integer partitions according to whether they contain a part equal to . Removing one such part is a bijection to partitions of whose parts are at most . The alternatives are disjoint, giving
(1)
Use , because the empty integer partition is counted once, and for , with for . This Oberon implementation avoids negative recursive arguments:
PROCEDURE P(i, n: INTEGER): INTEGER;
VAR answer: INTEGER;
BEGIN
  IF n = 0 THEN answer := 1
  ELSIF i = 0 THEN answer := 0
  ELSIF i > n THEN answer := P(i-1, n)
  ELSE answer := P(i-1, n) + P(i, n-i)
  END;
  RETURN answer
END P;

PROCEDURE Partitions(n: INTEGER): INTEGER;
BEGIN
  RETURN P(n, n)
END Partitions;
The precondition is . Each recursive call reduces , proving algorithm termination. Every positive part of a partition of is at most , so the required one-argument count is . Counts require a sufficiently wide integer representation.
For partitions into distinct parts, using a part prevents using it again. Hence
(1)
when , with , for , and for . When , use . Thus change the second call in the final branch of P to D(i-1, n-i) and rename all calls to D. The same split into two disjoint classes proves correctness; its second class removes its unique largest allowed part. The answer is , giving , from and .
Write parts in nonincreasing order. The array part stores the current prefix, and Emit(i,r,len) completes it using parts at most with remaining sum . With Out as the Oberon output module:
VAR part: ARRAY MaxParts OF INTEGER;

PROCEDURE Emit(i, r, len: INTEGER);
VAR j: INTEGER;
BEGIN
  IF r = 0 THEN
    j := 0;
    WHILE j < len DO
      IF j > 0 THEN Out.Char("+") END;
      Out.Int(part[j], 0); j := j+1
    END;
    Out.Ln
  ELSIF i > 0 THEN
    IF i <= r THEN
      part[len] := i;
      Emit(i, r-i, len+1)
    END;
    Emit(i-1, r, len)
  END
END Emit;

PROCEDURE PrintPartitions(n: INTEGER);
BEGIN
  Emit(n, n, 0)
END PrintPartitions;
The recursion invariant is that part[0..len) is nonincreasing, has sum , and every further part must be at most and at most the last existing part. The first branch includes the next part ; the second excludes it. These alternatives partition all completions, so each integer partition is printed exactly once. A recursive call reduces ; the printing loop's loop invariant is that the first entries have been printed with exactly the necessary separators.
For , no partition has more than parts, and the all-ones partition has exactly . Thus the fixed array requires to handle every partition. When a write occurs, and therefore len < n, so this bound prevents an out-of-range write. Zero prints one empty line, representing the empty integer partition. Available call stack space imposes a further practical limit.
Use dynamic programming in increasing order of the maximum permitted part and then of the remaining sum. Let Count be a sufficiently wide integer type and let table have dimensions (MaxN+1) by (MaxN+1):
PROCEDURE CountPartitions(n: INTEGER): Count;
VAR i, j: INTEGER;
    table: ARRAY MaxN+1, MaxN+1 OF Count;
BEGIN
  table[0,0] := 1; j := 1;
  WHILE j <= n DO table[0,j] := 0; j := j+1 END;
  i := 1;
  WHILE i <= n DO
    table[i,0] := 1; j := 1;
    WHILE j <= n DO
      table[i,j] := table[i-1,j];
      IF j >= i THEN
        table[i,j] := table[i,j] + table[i,j-i]
      END;
      j := j+1
    END;
    i := i+1
  END;
  RETURN table[n,n]
END CountPartitions;
Require . The outer loop invariant says all rows below equal . The inner loop invariant additionally says entries before column in the current row are correct. Its dependencies are the previous row and the earlier column , so no future entry is read. Each state is evaluated once, giving arithmetic operations and stored counts. A memoization table around part (a)'s recursion is another valid way to share states; its entries need a separate “computed” flag because zero is a legitimate answer. Growing count sizes affect bit complexity and can cause integer overflow in a fixed-width Count.
A trie node needs a terminal flag as well as its children: a stored word can also be the prefix of a longer stored word.
TYPE Trie = POINTER TO Node;
     Node = RECORD
       terminal: BOOLEAN;
       child: ARRAY 26 OF Trie
     END;
Index zero denotes a, index 25 denotes z; null pointers denote absent branches. The set represented by a nonnull node consists of the empty string if terminal is true, together with every child's words prefixed by that child's letter. Represent the empty set by NIL. The singleton containing the empty string instead has a terminal root and no children.
The declarations alone do not force a unique representation. A nonterminal leaf, or a whole branch without terminal descendants, contributes no word. To obtain uniqueness up to pointer addresses, impose a representation invariant: the structure is a finite rooted tree, and each allocated node lies on a path to a terminal node. Then precisely the prefixes of stored words exist, all flags are determined, and the empty set has only the NIL representation. The insertion procedures below preserve this invariant when starting with such a trie.
For the paper's 26-letter alphabet, use the Oberon CAP operation and contiguous character codes:
PROCEDURE Index(c: CHAR): INTEGER;
BEGIN
  RETURN ORD(CAP(c)) - ORD("A")
END Index;
Both cases of a letter map to the same uppercase letter before subtraction, so the result lies in 0..25. This relies on the ordinary Latin A–Z and a–z character encoding used by Oberon; it is not a Unicode case-folding algorithm. The stipulated letter-only precondition avoids any need to reject punctuation.
Perform a depth-first traversal, retaining the path's letters in a buffer. A terminal node must be printed before its children, so a word precedes its proper extensions in lexicographic order.
VAR word: ARRAY N OF CHAR;

PROCEDURE Visit(t: Trie; depth: INTEGER);
VAR j, c: INTEGER;
BEGIN
  IF t # NIL THEN
    IF t.terminal THEN
      j := 0;
      WHILE j < depth DO
        Out.Char(word[j]); j := j+1
      END;
      Out.Ln
    END;
    c := 0;
    WHILE c < 26 DO
      IF t.child[c] # NIL THEN
        word[depth] := CHR(ORD("a")+c);
        Visit(t.child[c], depth+1)
      END;
      c := c+1
    END
  END
END Visit;

PROCEDURE PrintTrie(t: Trie);
BEGIN
  Visit(t, 0)
END PrintTrie;
The recursion invariant is that word[0..depth) spells the path to t. The child loop's loop invariant says children with indices below c have been completely printed. Each edge appends its lowercase label; each terminal flag prints exactly one represented string. All words therefore appear once, in lowercase. The output loop prints precisely the prefix of length depth; no terminating zero needs storing in this buffer.
An N-character buffer suffices for words of length at most N. At depth N there can be no child, so word[N] is never accessed. A terminal root prints an empty line; a NIL root prints nothing. The running time is linear in allocated nodes plus the number of printed characters, since the alphabet size is fixed at 26.
Allocate nodes only as required, explicitly initializing every field:
PROCEDURE Make(VAR t: Trie);
VAR c: INTEGER;
BEGIN
  NEW(t); t.terminal := FALSE; c := 0;
  WHILE c < 26 DO t.child[c] := NIL; c := c+1 END
END Make;

PROCEDURE AddTail(VAR t: Trie; s: ARRAY OF CHAR; i: INTEGER);
BEGIN
  IF t = NIL THEN Make(t) END;
  IF s[i] = 0X THEN
    t.terminal := TRUE
  ELSE
    AddTail(t.child[Index(s[i])], s, i+1)
  END
END AddTail;

PROCEDURE Add(VAR t: Trie; s: ARRAY OF CHAR);
BEGIN
  AddTail(t, s, 0)
END Add;
Here 0X is the zero character, and s must contain its terminator within its array bounds. Make establishes that the first c child fields are NIL as its loop invariant. Passing t by reference lets the base allocation replace a missing root or child pointer.
For correctness, use induction on the number of characters before the terminator. At length zero, setting terminal adds exactly the empty suffix. Otherwise the chosen child stores exactly words with the required next letter, and the induction hypothesis adds the remaining suffix while preserving all other words. Thus the resulting set is the old set union the supplied word, ignoring case. Repeated insertion changes no word membership. A newly allocated path reaches the newly terminal node, preserving the canonical representation invariant after the procedure finishes. The running time is for a word of length , using call stack space without optimization.
A directly self-recursive procedure can be replaced by a simple loop when every recursive call is a tail call. This is tail recursion: no operation, including an update or cleanup action, remains to be performed after the call returns. The loop tests the same cases, performs the same nonrecursive work, and replaces the current parameters by the next call's arguments. Argument values must be computed before assignments if their expressions depend on old parameter values; by-reference bindings also need preserving.
A traversal that must return to explore another child is not in this form. It can still be implemented iteratively with an explicit stack, but that is a different transformation and generally retains the deferred work.
AddTail in part (d) is already tail-recursive: the recursive call is the final action of its branch. The following loop follows a separate cursor so that the caller's root pointer is preserved:
PROCEDURE AddIter(VAR t: Trie; s: ARRAY OF CHAR);
VAR u: Trie; i, c: INTEGER;
BEGIN
  IF t = NIL THEN Make(t) END;
  u := t; i := 0;
  WHILE s[i] # 0X DO
    c := Index(s[i]);
    IF u.child[c] = NIL THEN Make(u.child[c]) END;
    u := u.child[c]; i := i+1
  END;
  u.terminal := TRUE
END AddIter;
The loop invariant is that u points to the node reached by the first i letters, all necessary nodes along that path exist, and no previously terminal node has lost its flag. Each iteration advances one character. At the terminator, marking u inserts exactly the desired string. Using t := t.child[c] as the cursor update would instead overwrite the caller's root through the VAR parameter. This version has running time and constant auxiliary space, apart from newly allocated nodes in the result.
For a proposed loop invariant , initial condition , guard , body , and postcondition , establish these Hoare logic obligations:
(1)
The first establishes before the loop; the second preserves it after each iteration; the third derives the desired result when the guard is false. Together they prove partial correctness. For total correctness, also prove algorithm termination, for example by a nonnegative integer loop variant that strictly decreases whenever the body executes. The loop invariant need not be the postcondition: it generally describes completed and unfinished work together.
Let denote the original array, used only in the proof. Save its first entry before overwriting it:
PROCEDURE LeftOne;
VAR saved: T; i: INTEGER;
BEGIN
  saved := a[0]; i := 0;
  WHILE i < N-1 DO
    a[i] := a[i+1]; i := i+1
  END;
  a[N-1] := saved
END LeftOne;
The loop invariant is saved = A[0], for , and for . Thus the next source is untouched, and the assignment extends the completed prefix. At exit, the saved entry supplies the last position. The loop variant is . The result is . This also handles , and uses exactly element reads and element writes, counting the saved read and final write, with one extra value of type T.
Save the last entry and shift in decreasing index order, so no source is overwritten before being used:
PROCEDURE RightOne;
VAR saved: T; i: INTEGER;
BEGIN
  saved := a[N-1]; i := N-1;
  WHILE i > 0 DO
    a[i] := a[i-1]; i := i-1
  END;
  a[0] := saved
END RightOne;
The loop invariant is saved = A[N-1], for , and for . The decreasing loop variant is . At exit the untouched saved value fills index zero. The result is , again with reads, writes, and one extra value of type T. Applying this after part (b) restores every original entry.
Normalize the amount to , with ; negative then naturally denotes a right rotation. When , return without touching the elements. Otherwise the map has disjoint permutation cycles, each of length . Use representatives :
PROCEDURE RotateLeft(k: INTEGER);
VAR r, g, x, y, h, s, j, next: INTEGER; saved: T;
BEGIN
  r := k MOD N;
  IF r # 0 THEN
    x := N; y := r;
    WHILE y # 0 DO h := x MOD y; x := y; y := h END;
    g := x; s := 0;
    WHILE s < g DO
      saved := a[s]; j := s;
      IF j >= N-r THEN next := j-(N-r) ELSE next := j+r END;
      WHILE next # s DO
        a[j] := a[next]; j := next;
        IF j >= N-r THEN next := j-(N-r) ELSE next := j+r END
      END;
      a[j] := saved; s := s+1
    END
  END
END RotateLeft;
The conditional calculation of next implements addition modulo without first forming a possibly overflowing j+r. Oberon's MOD with positive divisor supplies the nonnegative remainder. The first loop is the Euclidean algorithm, with loop invariant and decreasing nonzero remainder.
For the outer loop, cycles with representatives below s are complete and every other cycle retains its original values. In one cycle, write . The inner loop invariant is saved = A[s], , and for , with the remaining sources still untouched. When the next index returns to s, the saved value closes the cycle. The cycle length is : writing and with , the least positive with is . Each residue class modulo is one cycle, justifying the chosen representatives.
Every element is read once and written once: element accesses, compared with for repetitions of part (b). The zero rotation uses none. The running time is and auxiliary space is constant; the original array is proof notation, not a copy made by the program.
Use the convention , as required by the paper's rotation example. Follow each permutation cycle once. Temporarily encode a visited value as , and restore the whole permutation before returning:
PROCEDURE Permute(VAR p: ARRAY OF INTEGER);
VAR s, j, next: INTEGER; saved: T;
BEGIN
  s := 0;
  WHILE s < N DO
    IF p[s] >= 0 THEN
      IF p[s] = s THEN
        p[s] := -p[s]-1
      ELSE
        saved := a[s]; j := s;
        next := p[j]; p[j] := -next-1;
        WHILE next # s DO
          a[j] := a[next]; j := next;
          next := p[j]; p[j] := -next-1
        END;
        a[j] := saved
      END
    END;
    s := s+1
  END;
  s := 0;
  WHILE s < N DO p[s] := -p[s]-1; s := s+1 END
END Permute;
Require LEN(p) >= N and that p[0..N) is the stipulated permutation. Its cells must be writable and distinct from the data array. The marking map is reversible and fits whenever the original valid indices and fit in the signed integer type.
At each outer test, all marked indices belong to fully completed cycles; all unmarked cycles still contain their original data and permutation entries. Within a cycle the same shifting loop invariant as part (d) applies, with successor given by the original p: all previously filled positions have their final values, and saved preserves the overwritten first source. A permutation has no path into a different cycle, so every new successor is unmarked until it returns to s; no encoded negative value is used as a source index. At outer-loop exit every index is marked and correct. The restoration loop has decoded precisely the indices below s.
The procedure uses one extra value of type T, time, and at most data reads plus data writes, with no data access for fixed points. It returns p unchanged, though it marks it temporarily. If p must remain read-only even during execution, test whether each index is its cycle's smallest member by traversing p before moving that cycle. That preserves constant space and the same optimal data accesses, but can require index-array accesses.
The output is BADDCD, without a newline. Method overloading chooses a signature using static types, including the instantiated class type parameter; numeric widening can make a Double parameter applicable to an Int argument.
  • a.m(o1) chooses m(Int), which is more specific than the polymorphic method: B.
  • a.m(o2) uses m[Double](Double): A.
  • b.m(o1) compares m(Any) and m(Double). Int can widen to Double, and Double is more specific than Any: D.
  • b.m(o2) chooses m(Double) over m(Any): D.
  • c.m(o1) compares the instantiated m(Int) with m(Double) and chooses m(Int): C.
  • c.m(o2) can use only m(Double): D.
The third call is the subtle one: the existence of m(Any) does not prevent the more specific numeric overload from winning. These are Scala 2 method overloading and numeric widening rules. [ref]
The output is YXWX, without a newline. Apply overload selection followed by dynamic dispatch separately to each call:
  • c.m(a) selects the m(A) signature because the argument's static type is A. The receiver is a D at runtime, so its override prints Y.
  • d.m(b) selects m(B). D.m(B) explicitly calls the inherited implementation with super.m(o), giving X.
  • e.m(a) selects C.m(A), giving W.
  • e.m(b) selects C.m(B), giving X.
Although a actually refers to a B, that runtime type does not select another overload. Dynamic dispatch chooses the implementation of the already selected signature on the receiver.
Read each Scala trait linearization from the most specific implementation toward the base. For a declaration with parents , concatenate their linearizations from right to left, deleting a duplicate from a left operand when it already occurs in the right operand. This can move a repeated ancestor later than a superficial “rightmost trait first” scan suggests. Omitting the common AnyRef, Any suffix, the answers are
C, Y, H, N, L, I, E
B, Y, H, N, L, D, I, E
A, N, O, Y, S, H, T, L, D, I, E
For example, T contributes T,L,D,I,E, while O contributes O,Y,S,H,E. In A, the separately mentioned Y also appears in the later merge with O, and N's ancestors also occur in T; resolving these duplicates yields the final order displayed above. The inherited trait orders are the displayed lists after removing their leading class names. [ref]
Each implementation first evaluates super.meth and then appends its own name. Consequently the contributions appear in reverse order of the defining traits in the Scala trait linearization. The four printed lines are
E I L N H Y 
E I D L N H Y 
E I D L T H S Y O N 
E I D L T H S Y O N
There is a trailing space before each newline. The third and fourth lines are identical: the declared type D of o4 permits the call but does not change the actual A object's dynamic dispatch or its super chain. Within N, for example, super.meth in an A follows the next implementation in A's full linearization rather than simply using L as its isolated textual parent.
The output is ABC, without a newline. The relevant Scala trait linearization is D,C,B,A. Calling d.m starts with C.m, whose super.m continues to B.m, then to A.m. The latter prints A; returning through the two method bodies then prints B followed by C. The braces keep each final print inside that object method.
The output becomes BCA, without a newline. Here each method body consists only of super.m; the semicolon ends that definition. The following print("B") or print("C") is a separate statement in the trait body, so it executes during construction.
Creating new D initializes the shared base and then the B and C mixins, printing BC. The subsequent d.m still forwards along C,B,A, but only A.m now prints anything, appending A. Thus it is the placement of the construction-time statements, not a changed Scala trait linearization, that changes the output. [ref]
Class inheritance defines a software class by extending another software class, inheriting its available operations and optionally adding members or providing method overriding. In languages supporting it, traits and mixins can contribute reusable behavior as well.
Use inheritance for a sound specialization whose instances can satisfy the superclass's contract wherever its instances are expected. For example, every specific gate in part (d) is usable through the common gate object interface. Subtyping supports this substitution and dynamic dispatch selects the specialized calculation. Merely noticing shared code does not establish the required behavioral relationship; object composition is often better for a replaceable component or policy that an object contains. A subclass must preserve the superclass's promised behavior, rather than just sharing its field names.
The two writable inputs and Boolean query belong to an abstract class; each concrete logic gate overrides just that query:
abstract class Gate {
  var inp1: Boolean = false
  var inp2: Boolean = false
  def evalGate: Boolean
}

class OrG extends Gate {
  override def evalGate: Boolean = inp1 || inp2
}

class AndG extends Gate {
  override def evalGate: Boolean = inp1 && inp2
}

class XorG extends Gate {
  override def evalGate: Boolean = inp1 ^ inp2
}
All three subclasses satisfy the same object interface, so the Gate declarations in the supplied simulator still allow access to inputs and invoke the correct Boolean function through dynamic dispatch. Boolean ^ is exclusive or; || is Boolean disjunction and && is Boolean conjunction.
The program first sets both inputs of y, so . It sets . Therefore and , giving
x: true
w: false
Those are the two output lines. This is a simulation of combinational logic in an order where each gate's inputs have already been calculated; the Boolean assignments copy values rather than create live wire connections.
The Prototype pattern is a creational pattern that creates new software objects by copying an existing configured object through a common cloning object interface. A client keeps or selects a prototype and requests a copy, without naming the concrete software class or repeating its construction recipe.
It is useful when the concrete type is selected at runtime, when many objects share a configuration, or when reconstructing an initialized object is expensive. For example, a drawing application can duplicate a configured graphical object through the same interface for many shape classes. The contract must specify what is copied: nested mutable state may require a deep copy, whereas a shallow copy would retain reference aliasing. A copy should preserve the intended configuration while allowing independent changes where promised.
This is the Decorator pattern, a structural pattern. Packages is a decorator object: it implements CableTV while holding another CableTV, to which its default queries delegate. Movies and HDChannels extend the price and description of the wrapped account. Because a wrapper itself satisfies CableTV, another wrapper can surround it; features combine without declaring a new software class for each possible package combination.
In this UML class diagram, hollow triangles point toward the more general type; dashed lines denote realization of the CableTV object interface. The plain association records that Packages retains one wrapped account, without claiming exclusive lifetime ownership.
Figure 1.
Decorator pattern for the cable television account, extended with Sports
. Details.
Add the following software class and client application to the supplied declarations. The inherited result type gives BasicPlan.cost an expected Double type, so its literal 30 is widened appropriately; no source change is needed.
class Sports(account: CableTV) extends Packages(account) {
  override def cost: Double = super.cost + 5.0
  override def packages: String = super.packages + ", Sports"
}

object CheckCableTV {
  def show(account: CableTV): Unit =
    println(account.packages + ": GBP " + account.cost)

  def main(args: Array[String]): Unit = {
    val basic: CableTV = new BasicPlan
    val movies: CableTV = new Movies(basic)
    val hd: CableTV = new HDChannels(movies)
    val sports: CableTV = new Sports(hd)
    show(basic)
    show(movies)
    show(hd)
    show(sports)
    assert(sports.cost == 52.0)
    assert(sports.packages == "Basic plan, Movies, HD channels, Sports")
  }
}
The printed accounts have costs 30.0, 40.0, 47.0, and 52.0, with each description extending the preceding one. The fully decorated account is Basic plan, Movies, HD channels, Sports, costing £52. The intermediate accounts remain available because wrapping constructs a new software object. [ref]
The Decorator pattern participants are:
  • CableTV: the component object interface, declaring the price and package description visible to clients.
  • BasicPlan: the concrete component, supplying the initial £30 account and its description.
  • Packages: the abstract decorator object, storing one component and forwarding its queries.
  • Movies and HDChannels, and the extension Sports: concrete decorator objects, adding respectively £10, £7, and £5 and appending their labels.
The checking application is the client that chooses and nests these participants. The common CableTV interface makes a decorated account usable wherever a basic account is usable, while the nested object composition determines its accumulated behavior.
A sequence diagram describes an interaction among participants using lifelines and ordered messages; time normally runs downward. Calls, replies, and execution intervals show a scenario such as the client asking a Sports wrapper for its cost, then that wrapper delegating through the inner packages to BasicPlan and adding charges on return. Alternatives or loops can describe more than one trace.
A state diagram describes states of an object or system and transitions triggered by events, possibly guarded by conditions and accompanied by actions. An account might move from active to suspended on a failed-payment event and back to active on payment. It describes allowed lifecycle behavior rather than the order of messages in one chosen interaction. Both are behavioral diagrams in UML.
The Strategy pattern is a behavioral pattern that encapsulates alternative algorithms behind a shared object interface. A context holds a strategy and delegates the relevant operation to it, letting the chosen algorithm vary independently of its caller.
Use it when the same task has interchangeable policies, such as alternative pricing or route-selection algorithms. Supplying a different strategy changes the policy without expanding a chain of type tests in the context, and each policy can be checked independently. Object composition makes the selected strategy replaceable; clients rely on its contract rather than on one concrete implementation.
This is the Observer pattern, a behavioral pattern. Service stores subscribers through the Company object interface. SomeService.updateValue first changes the underlying value and then sends a notification to every registered company; each company's meth() queries the new value and computes its own response. This is a pull-style notification: the message announces the change, while the observer reads the data from its retained subject reference.
The UML class diagram shows the subject's collection of observers and the added concrete observer. Each concrete company also retains the SomeService reference shown in its attributes; notifications call meth() through Company.
Figure 1.
Observer pattern for service values, extended with a NonProfit company
. Details.
Use an unscaled value both initially and in every callback:
class NonProfit(service: SomeService) extends Company {
  private var v: Double = service.value
  service.addCompany(this)

  override def meth(): Unit = {
    v = service.value
    printf("New service value: %f\n", v)
  }
}
Initializing v before registration prevents a callback from observing an uninitialized field if registration is later extended to notify immediately. For a service initially valued at 100.0, this initializes v to 100.0; after updateValue(125.0), the callback sets v to 125.0 and prints New service value: 125.000000 under a decimal-point locale. The NonProfit update uses factor one.
The word “always” requires a qualification in the supplied design. In the intended single-threaded notification protocol, holds after construction and after a completed SomeService.updateValue. However, the printed public value_= setter changes the subject without calling sendMessage(). Calling service.value = ... can therefore leave every cached observer value stale. No implementation that merely caches v in meth() can guarantee literal equality after that unannounced change. If equality on every query is required, replace the field by private def v: Double = service.value, retaining registration and the same printing callback; alternatively every mutation route must notify observers. The source's distinct private/public company multipliers are not changed.
The Observer pattern participants are:
  • Service: the subject abstraction, owning the current value and registered Company references, and providing registration and notification operations.
  • SomeService: the concrete subject, making updateValue notify after establishing the new subject state.
  • Company: the observer object interface, declaring the meth() callback.
  • PrivateCompany and PublicCompany, together with the extension NonProfit: concrete observers, registering themselves, retaining their subject, and updating their own values on notification.
The printed PrivateCompany starts with factor but uses factor in its callback; PublicCompany starts with factor but later uses . These are the actual source behaviors, not a uniform pricing rule inferred from their names. The subject stores a list and prepends new subscriptions, so notification occurs in reverse registration order. Dependence on the Company interface lets the subject notify new observer types without naming their concrete classes. The omitted ... portions in the printed figure do not prevent identifying these roles or implementing the added observer.
True. A named software design pattern supplies shared vocabulary for recurring arrangements of responsibilities and interactions. Saying “observer” can identify subject registration and callbacks without first reproducing every implementation detail, provided developers still agree on the actual contract.
False as a general claim. An appropriately chosen software design pattern can make expected variation easier: a new strategy or decorator can be supplied through an existing object interface. An unnecessary pattern can add indirection and make some changes harder, so applying one is not an automatic guarantee of flexibility either.
True. A small proof-of-concept implementation makes the participants, delegation, and extension points of a software design pattern concrete. Trying a second strategy, an extra decorator, or another observer tests what changes locally and what assumptions remain. This supports learning when the arrangement is useful; it does not establish that every production system needs it.
True. Refactoring an existing implementation toward a software design pattern can be preferable once repeated structure and actual variation are visible. Existing behavior supplies a concrete contract to preserve, and tests can check that preservation. Starting from a pattern is appropriate when its problem is already established, but the pattern's name alone is not evidence that its extra structure is needed.

Ancestors (9)

  1. 2016
  2. Past exam of the year 1 of the computer science course of the University of Oxford
  3. Year 1 of the computer science course of the University of Oxford
  4. Computer science course of the University of Oxford
  5. Undergraduate course of the University of Oxford
  6. Course of the University of Oxford
  7. University of Oxford
  8. List of universities
  9. Home

View article source

Discussion (0) New discussion

There are no discussions about this article yet.

Articles by others on the same topic (0)

There are currently no matching articles.
See all articles in the same topic Create my own version