val square: Fun[Int, Int] = new Fun[Int, Int] {
override def apply(x: Int): Int = x * x
}Parametric polymorphism occurs because the generic trait is specialized by choosing its argument and result types. Subtype polymorphism occurs because the anonymous implementing software class is used through a
Fun[Int, Int] reference; calls to its apply operation use the object interface contract and dynamic dispatch. Multiplication itself is not the second polymorphism needed for this explanation.For values whose mathematical squares fit in a signed 32-bit integer, the result is the ordinary square. Outside that range, the supplied integer return type cannot represent every mathematical square, and the multiplication follows Scala integer-overflow behavior. An implementation requiring exact mathematical results for all integer inputs would need a wider result type or an explicit overflow exception.
TODO: supply or verify the exact Ewoks practical version used for this examination, including its relevant object interface, implementing classes and call site. The printed paper names the editor but supplies no software class hierarchy or API from which its particular example can be reconstructed.
An earlier official 2015–2016 synopsis identifies Ewoks as a text-editor case study and associates that material with commands represented as software objects and with dynamic binding. That is historical context, not verification of the 2021 practical implementation.[ref]
Object Oriented Programming course synopsis of the University of Oxford (2015-2016). Designing with objects, lectures 6–8: Ewoks, commands as objects, and dynamic binding
The method for completing the answer is to identify a common command or editing object interface, two actual implementations from the verified project, and a client call made through the common object interface. Subtype polymorphism would let that client select different behavior without inspecting concrete classes, improving extensibility and separating editing behavior from the code that invokes it. No particular Ewoks software class names or object method signatures are asserted here, so this context-dependent leaf remains incomplete.
Subtype polymorphism lets a reference with a common supertype denote values of different implementing classes. A call through that reference uses dynamic dispatch to select the concrete implementation.
Parametric polymorphism defines an operation or data structure using type parameters, such as a collection with an element-type parameter. Instantiations retain type information while reusing one generic definition.
Ad hoc polymorphism, commonly expressed by method overloading, gives several implementations the same name but different parameter signatures. The compiler selects a suitable overload using the available static types. This selection differs from later dynamic dispatch on the receiver of a selected instance method. A programming language can support all three in one program.
Give the wrapper exclusive ownership of a fresh delegate. It maintains its own inherited size so that inherited emptiness queries remain correct:
class IntegerSetWithCount extends IntegerSetPattern() {
private val delegate = new IntegerSet()
private var attempts = BigInt(0)
override def contains(x: Int): Boolean = delegate.contains(x)
override def insert(x: Int): Unit = {
attempts += 1
val wasPresent = delegate.contains(x)
delegate.insert(x)
if (!wasPresent) size += 1
}
override def delete(x: Int): Unit = {
val wasPresent = delegate.contains(x)
delegate.delete(x)
if (wasPresent) size -= 1
}
override def pop(): Int = {
if (isEmpty) throw new NoSuchElementException("set is empty")
val answer = delegate.pop()
size -= 1
answer
}
override def clear: Unit = {
delegate.clear
size = 0
attempts = BigInt(0)
}
def getCount: BigInt = attempts
}Use the explicit membership signature and fresh default-constructible concrete set qualified in part d. The representation invariant is that the wrapper's
size equals the delegate's cardinality and its counter equals client insertion attempts since construction or the latest successful client clear. The updates shown preserve that invariant when delegated operations fulfill their set contracts and failure checks leave the delegate unchanged. A duplicate does not increase size; deleting an absent element does not decrease it. Size changes follow successful delegation, whereas an attempted insertion is counted immediately.Object composition prevents internal delegate calls from dispatching into the wrapper's counter object methods. It therefore survives the particular base revision in part e. The cost is forwarding code, another software object, some redundant size state imposed by the chosen abstract superclass, and extra membership queries. Future object interface additions must also be forwarded explicitly. This solution is an alternative definition of the software class in part d, not a second simultaneous definition.
A base-class change can preserve its own set abstraction while breaking a subclass that intercepts internal calls. For example, suppose
IntegerSet.delete(x) is reimplemented by collecting the elements to retain, calling clear, then calling insert for each retained element. Conceptually its body isval retained = snapshotOfElements.filter(_ != x)
clear
retained.foreach(insert)Here
snapshotOfElements denotes the base implementer's own internal snapshot operation in this hypothetical revision, not an API supplied by the examination. The algorithm still removes exactly the requested value and preserves all other set members.On an
IntegerSetWithCount, however, these unqualified calls use dynamic dispatch. The internal clear resets the subclass counter and the internal insertions increase it. After client calls insert(10), insert(20), insert(10), the correct count is three. Calling delete(10) with this revised base implementation leaves the right set, containing only the other value, but resets the counter and reinserts that value, leaving count one instead of three. The client made no further insertion attempt and requested no clear.This is the fragile base class problem: subclass correctness depends on the base implementation's internal call structure, beyond its public set postconditions. A change need not alter the base API to expose that dependence.
Count each invocation before delegating, including duplicate insertions, and reset after clearing:
class IntegerSetWithCount extends IntegerSet() {
private var attempts = BigInt(0)
override def insert(x: Int): Unit = {
attempts += 1
super.insert(x)
}
override def clear: Unit = {
super.clear
attempts = BigInt(0)
}
def getCount: BigInt = attempts
}The inherited implementation already maintains
size; the new counter measures insertion attempts, not successful increases in cardinality. Deletion and popping do not subtract from it. Incrementing before delegation also counts an attempted insertion that subsequently fails a capacity check. Arbitrary-precision arithmetic avoids silently wrapping the historical count, though its arithmetic is not constant-cost for arbitrarily large counts.As the source supplies no object constructor signature for the concrete set, this code uses a fresh default-constructible
IntegerSet, with matching default capacity. Its correct behavior also assumes the base implementation does not internally invoke these overridable operations in a way that interferes with the counter. Part e exhibits that dependency.Source-signature qualification for the following set implementations: the intended membership query must be declared
def contains(x: Int): Boolean. The printed abstract declaration omits its result type; interpreted literally as Scala 2 procedure syntax, it returns Unit. The solutions use the explicit Boolean query contract, and Unit for the two mutators. Parameterless clear is overridden without adding parentheses.[ref]Scala 2.13 basic declarations and definitions specification. Procedures: a method declaration omitting its result type implicitly has Unit result
Throw an informative exception, such as
NoSuchElementException, and leave the set unchanged. This makes a violated nonempty precondition visible at the point of misuse. Returning a distinguished integer would be ambiguous because every integer is a legitimate set member.A different object interface could return an optional integer, representing failure explicitly, but that changes the declared return type. For the supplied integer-returning operation, a checked failure is useful and consistent with the stated precondition.
Protected access makes
size available to subclasses implementing the set operations, while preventing ordinary outside clients from assigning arbitrary values to it. The implementations need to update the count when membership changes; clients should affect membership only through the public operations. A publicly writable count could make an emptiness query disagree with the stored elements.Protection supports encapsulation but does not prove the representation invariant. Subclasses can still update the field incorrectly and must maintain its relationship to the actual set cardinality. In particular, subclass code does not obtain unrestricted access to the protected field of every unrelated set software object.
A suitable relationship is a circle implementing a read-only shape object interface whose operations include area. Every circle satisfies that object interface's behavioral contract, so clients using a shape can use a circle through subtype polymorphism; dynamic dispatch selects its area implementation.
A car is not appropriately modeled as a subclass of an engine merely because it needs engine behavior. Use object composition: the car contains an engine and delegates engine-related work to it. An engine is a component of a car, not a category containing cars. The design can replace the component independently without making all engine operations part of the car's public object interface. Class inheritance should reflect substitutability, rather than serve solely as a convenient way to obtain another software class's code.
A single bucket holding about a quarter of all keys suggests severely nonuniform hashing or a strongly skewed/adversarial key set, rather than ordinary load growth alone. With one hundred well-used buckets the expected fraction in one fixed bucket is about one hundredth. Persistent concentration near one quarter is evidence to investigate, not a proof identifying one particular implementation bug.
Inspect the bucket histogram, raw hash outputs and patterns in the names. A hash depending only on an initial character, weak mixing of common prefixes, or an indexing rule using few possible buckets could create this behavior. Improve the hash so that it uses the complete key and spreads this workload across the table, then rehash every stored entry. Check the valid-index rule as well, including negative machine hash values.
Increasing the table size is useful if index reduction caused the concentration; it cannot separate keys that all receive the same raw hash. For maliciously chosen keys, randomized or keyed hashing and balanced collision structures may be appropriate. The observed occupancy does not justify assuming uniformly random hashes in a performance claim.
The relevant quantity is the hash-table load factor , where is the number of distinct keys and the bucket count. With a suitable distribution of hashes, separate chaining has expected operation cost , treating key operations as constant-cost. Keeping only one hundred buckets while grows therefore increases average search length.
Balanced binary search trees could reduce a bucket search from linear time in its occupancy to logarithmic time. Unbalanced binary search trees provide no such guarantee: insertion order can produce a chain. Even balanced trees add comparison and node-management overhead, which may dominate for small buckets.
A usual first remedy is grow the table and rehash its entries, keeping the load factor bounded. Geometric growth gives amortized constant resizing overhead per insertion; with suitable hashing, expected lookup, update and insertion costs remain constant. Resizing is when performed and is not a worst-case constant-time guarantee for that particular operation. Balanced buckets can still be useful for heavy or adversarial collisions, but replacing every bucket tree does not by itself repair a poor hash function. For variable-length strings, hashing and string comparisons add their own character-processing costs.
Find the entry once and check the abstract membership precondition on that result:
def recall(name: String): String = {
val entry = find(name, table(hash(name)))
require(entry != null, "name is not in the book")
entry.number
}The check turns an invalid call into an explicit precondition failure rather than an accidental null dereference or an invented default number. For a valid call, the unique matching entry contains exactly the mapped value, so the stored number is returned and the map is unchanged. Testing membership by calling
isInBook first would traverse the same bucket twice; retaining the found reference avoids that redundant work.Membership is exactly whether the bucket search finds an entry:
def isInBook(name: String): Boolean = {
find(name, table(hash(name))) != null
}By the bucket-placement representation invariant, an entry with this name can occur only in this bucket. The
find contract therefore proves true exactly for keys in the map's domain, with no state change. One hash calculation and one bucket traversal suffice; no insertion is performed during the query.Assume the supplied hash function is stable and produces valid table indices. The representation invariant places each name in its hashed bucket, permits at most one entry per name, and requires finite acyclic, disjoint bucket chains.
def store(name: String, number: String): Unit = {
val bucket = hash(name)
val entry = find(name, table(bucket))
if (entry == null) {
table(bucket) = new Entry(name, number, table(bucket))
} else {
entry.number = number
}
}If the key exists, updating its associated number implements map override without creating a duplicate entry. Otherwise a new entry is prepended to the correct bucket and leaves every existing mapping unchanged. Its immutable name preserves bucket membership. Thus the mapping afterwards is the old mapping overridden at precisely the supplied key. Hash collisions between different names do not imply key equality and are handled by separate chaining.
Use null to indicate that the requested key is absent:
private def find(name: String, head: Entry): Entry = {
var cursor = head
while (cursor != null && cursor.name != name) {
cursor = cursor.next
}
cursor
}The loop invariant is that the skipped string prefix contains no entry with the requested name and
cursor starts the unsearched string suffix of the unchanged bucket. Its remaining length is a loop variant. Short-circuit evaluation prevents accessing a null entry. On exit, either cursor is null and the whole bucket has been ruled out, or its name equals the key. No list links or stored numbers are modified. String comparison here uses value equality; node deletion elsewhere uses reference identity.Let and describe the entry state. The postcondition is: the multiset is empty; the returned chain is sorted nondecreasingly; its node sequence is a permutation of . Thus it has exactly the original multiset of data and preserves all duplicates. Strict increase is impossible when the multiset contains repeated values.
def getAllSorted(): Node = {
var head: Node = null
var tail: Node = null
while (bagHeader.next != null) {
val nextSmallest = findMin(bagHeader.next)
delete(nextSmallest)
nextSmallest.next = null
if (head == null) head = nextSmallest
else tail.next = nextSmallest
tail = nextSmallest
}
head
}The loop invariant partitions the original node identities into the remaining multiset and the returned-prefix chain. The latter is sorted, its last node is
tail, and every datum in it is no larger than every remaining datum. Selecting a minimum and appending that detached node preserves all these facts. The loop variant is the number of real nodes remaining in the multiset, decreasing by one. When it reaches zero the string prefix contains the entire original node set, proving the postcondition. An initially empty multiset returns null.This is linked-list selection sort. Its time is in general, from successive scans of lengths , and it uses constant auxiliary space: it relinks original nodes instead of allocating a new node for each item.
Check that at least one real node exists, then compose the two helpers:
def deleteMin(): Int = {
require(bagHeader.next != null, "bag is empty")
val smallest = findMin(bagHeader.next)
val answer = smallest.datum
delete(smallest)
answer
}The precondition check makes
findMin applicable. Its result belongs to the real-node sequence, satisfying delete's precondition. Consequently one minimum value is returned and exactly one occurrence is removed; duplicates remain as distinct nodes. Saving the datum before deletion also separates the return value from subsequent link mutation. Two linear traversals still give time for a multiset containing nodes, with constant auxiliary space.The precondition is
n != null and , using node identity rather than datum equality. Search for its predecessor:def delete(n: Node): Unit = {
var previous = bagHeader
while (previous.next ne n) {
previous = previous.next
}
previous.next = n.next
n.next = null
}The loop invariant states that
previous is the header or a preceding real node, and . The loop variant is the number of links from previous to n minus one. The precondition guarantees that this search reaches the predecessor before a null dereference. Replacing its successor by n.next bypasses exactly the requested node; clearing the removed node's link detaches it for later reuse. The order and identities of every other node remain unchanged. In abstract terms, only the multiplicity of n.datum decreases, by one. The worst-case time is linear; the pointer modification itself is constant-time. There are unlisted articles, also show them or only show them.