CS 509 Class Notes

Lecture Notes for Advanced Programming II

15 April 2004 - Implementing Subtype Polymorphism

Outline

Member-Function Look-Up
Static Look-Up
Dynamic Look-Up
Virtual Member Functions
Gotchas
- The Virtual Flip-Flop
- Virtual Destructors
- Virtual Function Definitions
Abstract Virtual Functions

Member-Function Look-Up

Given
```
Ctype i;
i.f();
```
where is f()?

Use member-function look-up to answer the question.

C = i's declared class (Ctype, in this case).

while C::f() does not exist

  if C does not have a parent
    error: f() not found.

  C = C's parent class

Climb the inheritance hierarchy looking for f().
- Starting at i's declared type.
- This is also known as i's static type.
- This form of look-up is known as static look-up.

Subtype Polymorphism vs. Static Look-Up

Subtype polymorphism doesn't interact well with static look-up.

class VirtualFileSystem {
  status open(string name, mode m) { }
  }

class ext2 : VirtualFileSystem {
  status open(string name, mode m) {
    // whatever
    }
  }

Given

static ext2 linux_fs
VirtualFileSystem * vfs = &linux_fs
vfs->open("joe", VirtualFileSystem::read)

where is open()?

Static look-up puts it in VirtualFileSystem, which is not what we want.
- vfs's declared (or static) type is VirtualFileSystem.

Dynamic Look-Up

Static look-up breaks subtype polymorphism.
- The search must start lower in the inheritance hierarchy.
- The search must start at the value's class.
- This is known as the variable's dynamic type.
  - "Dynamic" because it changes with the value held.

Dynamic look-up starts at a variable's dynamic type.

C = i's value's declared class (ext2)

while C::f() does not exist
  if C does not have a parent
    error: f() not found.
  C = C's parent class

Dynamic look-up correctly finds ext2::open().

Static vs. Dynamic Look-Up

Static look-up is the default member-function look-up.
- These problems were discovered after C++ was defined.
A virtual member function is located by dynamic look-up.
- By default, member functions are non-virtual.
- By default, you get static look-up.
Classes involved in subtype polymorphism must use virtual member functions.
- Static look-up breaks subtype polymorphism.
Other languages default to dynamic look-up.
- Java and Smalltalk, for example.

Declaring Virtual Member Functions

Preceding a member-function declaration with the virtual keyword makes the member function virtual.
```
class VirtualFileSystem
  virtual status open(...);
```
- Do not repeat virtual when defining member functions outside the class.
```
virtual VirtualFileSystem::status
ext2::open(...) { ... }
```
virtual is a per-function keyword.
- A class can mix virtual and non-virtual member functions.
- Think hard before doing this.
All descendents of a virtual member function are virtual.
- Dynamic look-up is inherited; no virtual keyword necessary.
Ancestors of a virtual function are not virtual.
- Unless explicitly declared so.

Virtual Member Function Examples

class DeviceInterface {
  bool initialized(void);
  virtual status open(...) { }
  }

class VirtualFileSystem : DeviceInterface {
  virtual status rename(...) { }
  }

class ext2 : VirtualFileSystem {
  status open(...) { ... } 
  status rename(...) { ... }
  }

class ntfs : VirtualFileSystem {
  virtual status open(...) { ... }
  virtual bool initialized(void);
  }

VirtualFileSystem::open() is virtual.
- Because DeviceInterface::open() is virtual.

Virtual Member Function Gotchas

Needless to say (this is C++, right?) there are lots of little details waiting to trip you up.
No, really - when is a member function virtual?
Even if you don't want it, you got it: virtual destructors.
Compiler follies: defining virtual functions.
Matching member function prototypes.

A Little Quiz

Given

class DeviceInterface
  bool initialized(void) { }

class VirtualFileSystem : DeviceInterface 
  virtual bool initialized(void) { }

class HFS : VirtualFileSystem 
  bool initialized(void) { }

static HFS mac_fs
VirtualFileSystem & vfs = mac_fs
DeviceInterface * dip = &mac_fs

Where is vfs.initialized()?
Where is dip->initialized()?

The Virtual Flip-Flop

The static type determines if a member function is virtual.
Given
```
class DeviceInterface
  bool initialized(void) { }

class VirtualFileSystem : DeviceInterface 
  virtual bool initialized(void) { }

class HFS : VirtualFileSystem 
  bool initialized(void) { }

static HFS mac_fs
VirtualFileSystem & vfs = mac_fs
DeviceInterface * dip = &mac_fs
```
Where is vfs.initialized()?
- vfs has static type VirtualFileSystem.
  initialized() is virtual in VirtualFileSystem.
  vfs has dynamic type HFS.
  Dynamic look-up finds HFS::initialized().
Where is dip->initialized()?
- dip has static type DeviceInterface.
  initialized() is non-virtual in DeviceInterface.
  Static look-up finds DeviceInterface::initialized().

Virtual Destructors

Given

class Number { ... }
class Complex : Number { ... }

void f()
  Number * np = new Complex()
  delete np

What happens when delete np is called?

If Number::~Number is not virtual, static look-up is used and Complex::~Complex is never called.
Classes defining virtual functions almost always need to define a virtual destructor.
- The virtual destructor needn't do anything, it just forces dynamic look-up.
- This is separate from dynamic memory - even without dynamic memory, a class with virtual functions needs a virtual destructor.
  - Only non-pointer plain-old data is exempt.
- Compare this with the rule of three.

A Heart-Felt Question

Why does this code fail?

$ cat t.cc
struct Number
  virtual void output(ostream &) const;

struct Complex : Number
  void output(ostream &) const
    cout << "Hello from Complex::output().\n"

int main()
  Complex c ; c.output(cout)

$ g++ -o t t.cc
/tmp/f.o(.gnu.linkonce.d._vt.7Complex+0xc): 
  undefined reference to Number::output(ostream &)
/tmp/f.o: In function Complex type_info function:
/tmp/f.o(.gnu.linkonce.t.__tf7Complex+0x1c): 
  undefined reference to Number type_info function
/tmp/f.o: In function Number::Number(void):
/tmp/f.o(.Number::gnu.linkonce.t.(void)+0x8): 
  undefined reference to Number virtual table
collect2: ld returned 1 exit status

$ CC -c t.cc
"t.cc", line 15: 
Warning: Complex::output hides the virtual function
Number::output(basic_ostream<char, char_traits<char>>&)
1 Warning(s) detected.

$

Virtual Function Definitions

A virtual function must be defined, even if it's "obviously" never called.

$ cat t.cc
struct Number
  virtual void output(ostream &) const { };

struct Complex : Number
  void output(ostream &) const
    cout << "Hello from Complex::output().\n";

int main()
  Complex c ; c.output(cout)

$ g++ -o t t.cc

$ CC -o t t.cc

$

This is different from regular member functions.

Compilers usually aren't helpful on this error.
Be careful how you define the virtual function
- Accidently calling the parent virtual function is annoying.
- Have the parent virtual declaration explode when called.

Matching Virtual Functions

Be careful matching virtual parent and child function prototypes.
- The matches must be exact for parameters.
Mismatched prototypes mean different functions.
- And the child isn't virtual.

For example, what does this program print when run?

struct A
  virtual void hi(unsigned)
    std::cout << "in A::hi(unsigned)"

struct B : A
  void hi(int)
    std::cout << "in B::hi(int)"

struct C : B
  void hi(unsigned)
    std::cout << "in C::hi(unsigned)"

int main()
  A * ap = new C()
  B * bp = new C()
  ap->hi(1)
  bp->hi(1)

Virtual Functions Matched

B::hi(int) is not virtual.
- void B::hi(int) does not match void A::hi(unsigned).

C::hi(unsigned) is virtual.

void C::hi(unsigned) matches void A::hi(unsigned).

$ g++ -o t -ansi -pedantic -Wall t.cc

$ ./t
in C::hi(unsigned)
in B::hi(int)

$ CC -o t t.cc
"t.cc", line 13: 
  Warning: B::hi hides the virtual function 
  A::hi(unsigned).
1 Warning(s) detected.

$ ./t
in C::hi(unsigned)
in B::hi(int)

$

Don't Forget the `const`

How about

struct A
  virtual void hi(void) { ... }

struct B : A {
  void hi(void) const { ... }

struct C : B {
  void hi(void) { ... }


int main() {
  A * ap = new C()
  B * bp = new C()
  ap->hi()  // ?::hi()
  bp->hi()  // ?::bye()
  }

The const member-function modifier takes part too.
- C::hi()
- B::bye()
  void hi(void) does not match void hi(void) const.

Not Even Children are Spared

$ cat t.cc
struct shape { ... }
struct circle : shape { ... }

struct A
  virtual void hi(shape *) { ... }
struct B : A
  void hi(circle *) { ... }
struct C : B
  void hi(shape * ) { ... }

int main()
  A * ap = new C()
  B * bp = new C()
  circle * cp
  ap->hi(cp)
  bp->hi(cp)

$ g++ -o t -ansi -pedantic -Wall t.cc

$ ./t
in C::hi(shape *)
in B::hi(circle *)

$ CC -o t t.cc

$ ./t
in C::hi(shape *)
in B::hi(circle *)

$

Abstract Virtual Functions

Defining virtual functions can be a pain, particularly if there's a lot of them.
Also, it's easy to forget to redefine a virtual function in a child class.
Also, instances of a virtual function class are not useful, particularly if the virtual functions explode.
Abstract virtual functions take care of all these problems.
An abstract virtual function is a virtual function initialized to zero (this is disgusting syntax).
```
struct Number {
  virtual void output(ostream &) = 0;
};
```
A class containing an abstract virtual function is an abstract virtual class.

Abstract Virtual Properties

Creating an instance of an abstract virtual class causes a compile-time error.
- Defining pointers and references to abstract virtual class instances is ok.
Abstractness is inherited by descendents.
- A child function is abstract unless its defined.
  - Once defined, the child and its descendents are virtual but not abstract.
  - Unless a descendent is re-defined as abstract.
- No need to use abstract again in the child.
Forgetting to redefine a child makes the child abstract.
- A relatively easy error to catch.

Points to Remember

Static look-up starts from the variable's class.
- Static look-up breaks subtype polymorphism.
Dynamic look-up starts from the value's class
- Dynamic look-up supports subtype polymorphism.
Virtual member functions use dynamic look-up.
- The default is non-virtual static look-up.
Watch out for the virtual flip-flop.
- The static type determines the class.
Abstract virtual functions make virtual functions safer.
- No definition required, no forgetting.

This page last modified on 21 May 2004.