-
This code uses implementation inheritance. Where’s the bug?
class Point {
int x, int y;
Point(int x, int y) {
this.x = x;
this.y = y;
display();
}
void display() {
System.out.println(x + " " + y);
}
}
class CPoint extends Point {
Color c;
CPoint(int x, int y, Color c) {
super(x, y);
this.c = c;
}
void display() {
System.out.println(x + " " + y + " " + c.name());
}
} -
This code uses implementation inheritance. Where’s the bug?
/** A version of Hashtable that lets you do
* table.put("dog", "canine");, and then have
* table.get("dogs") return "canine". **/
public class HashtableWithPlurals extends Hashtable {
/** Make the table map both key and key + "s" to value. **/
public Object put(Object key, Object value) {
super.put(key + "s", value);
return super.put(key, value);
}
}Hint: After put("dog", foo), although "dogs" is in the table as expected, sometimes "dogss" is also in the table. Why?
-
Consider this object buffer in Java:
public class Buffer {
protected Object[] buf;
protected int MAX;
protected int current = 0;
Buffer(int max) {
MAX = max;
buf = new Object[MAX];
}
public synchronized Object get()
throws Exception {
while (current<=0) { wait(); }
current--;
Object ret = buf[current];
notifyAll();
return ret;
}
public synchronized void put(Object v)
throws Exception {
while (current>=MAX) { wait(); }
buf[current] = v;
current++;
notifyAll();
}
}Use inheritance to extend this class to support the gget() method, which is identical to get() except it cannot be executed immediately after a get(). In other words, it blocks until a put() or a gget() finishes.
public class HistoryBuffer extends Buffer {
// What goes here?
}
Answers
-
See "Masked types for sound object initialization" for the answer. Did you know initialization of superclasses in Java and C++ is unsound?
In Go, which lacks inheritance, we might write:
type Point struct {
x, y int
}
func NewPoint(int x, int y) *Point {
p := &Point{x, y}
p.Display()
return p
}
func (p Point) Display() {
println(p.x, p.y)
}
type CPoint struct {
x, y int
c Color
}
func NewCPoint(int x, int y, Color c) *CPoint {
p := &Cpoint{x, y, c}
p.Display()
return p
}
func (p CPoint) Display() {
println(p.x, p.y, c.Name())
}We must write factory methods instead of constructors. However, the language makes it easy to avoid the bug.
-
This question was taken from "The Java IAQ", which also explains the answer.
In Go, which lacks inheritance, we might write:
type PluralsTable struct {
*Table tab;
};
func (t *PluralsTable) Put(key string, value interface{}) interface{} {
t.tab.Put(key + "s", value)
return t.tab.Put(key, value)
}
func (t *PluralsTable) Get(key string) interface{} {
return t.tab.Get(key)
}
...We must define a wrappper for each method of Table that we want PluralsTable to support. Additionally, if we have code that should work on PluralsTable and Table, we must define an interface with Put and Get. However, the language makes it easy to avoid the surprise recursion bug.
We also avoid other kinds of bugs. For example, suppose we add PutFoo() to Table, which inserts "foo" into the table in a fast but strange way: the hash of "foo" is precomputed, so that the entry can be directly inserted into the underlying array.
With inheritance, calling PutFoo() on a PluralsTable will silently succeed, but neglect to insert "foos", a bug that might only be noticed long after a release. Without inheritance, the program will fail to compile when code calls PutFoo() on a PluralsTable, at which point a human can intervene and supply the PluralsTable edition of PutFoo().
-
Did you manage it without rewriting the entire class? If so, congratulations on solving the inheritance anomaly! Otherwise, you probably wrote something akin to the solution given in that paper:
public class HistoryBuffer extends Buffer {
boolean afterGet = false;
public HistoryBuffer(int max) { super(max); }
public synchronized Object gget()
throws Exception {
while ((current<=0)||(afterGet)) {
wait();
}
afterGet = false;
return super.get();
}
public synchronized Object get()
throws Exception {
Object o = super.get();
afterGet = true;
return o;
}
public synchronized void put(Object v)
throws Exception {
super.put(v);
afterGet = false;
}
}Implementation inheritance mixes poorly with concurrent programming.
In Go, this question takes a different character because concurrent object buffers are built-in types:
type Buffer chan interface{}
func NewBuffer(max int) Buffer {
return make(chan interface{}, max)
}
func (buf Buffer) Get() interface{} {
return <-buf
}
func (buf Buffer) Put(v interface{}) {
buf <- v
}One solution to the HistoryBuffer problem is:
type HistoryBuffer struct {
ch chan interface{}
get, gget, put, done chan bool
}
func NewHistoryBuffer(max int) *HistoryBuffer {
buf := &HistoryBuffer{
make(chan interface{}, max),
make(chan bool), make(chan bool), make(chan bool), make(chan bool),
}
go func() { // Synchronization logic.
maybe_gget := buf.gget
for {
select {
case <-maybe_gget:
case <-buf.put:
maybe_gget = buf.gget
case <-buf.get:
maybe_gget = nil
}
<-buf.done
}
}()
return buf
}
func (buf *HistoryBuffer) Get() interface{} {
buf.get <- true
v := <-buf.ch
buf.done <- true
return v
}
func (buf *HistoryBuffer) Put(v interface{}) {
buf.put <- true
buf.ch <- v
buf.done <- true
}
func (buf *HistoryBuffer) GGet() interface{} {
buf.gget <- true
v := <-buf.ch
buf.done <- true
return v
}Most of the synchronization logic resides in the anonymous function. Outside, we only have channel writes at the beginning and end of each method, comparable to Java’s synchronized keyword. Thus behaviour is decoupled from synchronization.
We can effortlessly and independently change the synchronization logic. Suppose now GGet() can only be called after 3 Put() calls and 2 Get() calls have completed in some order since the previous GGet(), or, if there are no previous GGet() calls, since the program started. We simply change the anonymous function:
go func() {
var maybe_gget chan bool
p, g := 0, 0
for {
select {
case <-maybe_gget:
p, g = 0, 0
maybe_gget = nil
case <-buf.put:
p++
case <-buf.get:
g++
}
if p >= 3 && g >= 2 {
maybe_gget = buf.gget
}
<-buf.done
}
}()The official Go documentation suggests channels of ints instead of bools, which leads to slightly smaller code (mainly because we can replace true with 1), and probably results in the same compiled binaries.
