CS141 Notes

Object-Oriented Programming

A language that is object oriented must provide support for three key language features:

Abstract Data Types
Inheritance
Dynamic binding of method calls to methods

Inheritance

Issues Solved

Frequent and long-lasting modifications on the program. Maybe the person doing the modification is not the program’s original author.
Organization problem is severe since programming with abstract data types is that the type definitions are all independent and are at the same level.

Terminologies

class: The abstract data types in object-oriented languages.
object: Class instances as with instances of abstract data types.
derived class / subclass: A class that is defined through inheritance from another class.
parent class / superclass: A class from which the new class is derived.
methods: The subprograms that define the operations on objects of a class.
messages: The calls to methods.
message protocol / message interface: The entire collection of methods of an object.

Differ From Subclasses

There are several ways a derived class can differ from its parent. Following are the most common differences between a parent class and its subclasses:

The parent class can define some of its variables or methods to have private access, which means they will not be visible in the subclass.
The subclass can add variables and/or methods to those inherited from the parent class.
The subclass can modify the behavior of one or more of its inherited methods. A modified method has the same name, and often the same protocol, as the one of which it is a modification. (Override)

Override

General

The purpose of an overriding method is to provide an operation in the subclass that is similar to one in the parent class, but is customized for objects of the subclass.

Example

A parent class, Bird, might have a draw method that draws a generic bird. A subclass of Bird named Waterfowl could override the draw method inherited from Bird to draw a generic waterfowl, perhaps a duck.

Classifications

Methods & Variables

instance methods / instance variables: Every object of a class has its own set of instance variables, which store the object’s state.
class methods / class variables: They are belonged to the class, rather than its object, so there is only one copy for the class.

Inheritance Types

single inheritance
multiple inheritance

The purpose of multiple inheritance is to allow a new class to inherit from two or more classes. But it is not used in common.

Complexity:
- Suppose a subclass named C inherits from both class A and class B and both A and B define an inheritable method named display. If C needs to reference both versions of display, how can that be done?
- Issue arises if both A and B are derived from a common parent, Z, and C has both A and B as parent classes. This situation is called diamond or shared inheritance. The question is whether C should inherit both versions of sum or just one, and if just one, which one?

Efficiency:
- In C++, for example, supporting multiple inheritance requires just one additional array access and one extra addition operation for each dynamically bound method call, at least with some machine architectures (Stroustrup, 1994, p. 270). Although this operation is required even if the program does not use multiple inheritance, it is a small additional cost.

C++ Inheritance

Derivation

The derivation_mode can be either public or private. (Do not confuse public and private derivation with public and private members.)

// General structure
class derived_class_name: derivation_mode base_class_name {
    data member and member function declarations
    ...
};

// Two kinds of derivation 
class subclass_1 : public base_class {...}; 
class subclass_2 : private base_class {...};

// Access the public & protected members of base_class
class subclass_3 : private base_class { 
private:
    base_class::c;
    ...
};

Public Derivation: The public and protected members of a base class are also public and protected, respectively, in a public-derived class.
Private Derivation: Both the public and protected members of the base class are private in a private-derived class.

Solved Problem:

The classes stack and queue both suffer from the same serious problem:

Clients of both can access all of the public members of the parent class, single_linked_list.
A client of a stack object could call insert_at_tail, thereby destroying the integrity of its stack. Likewise, a client of a queue object could call insert_at_head.

These unwanted accesses are allowed because both stack and queue are subtypes of single_linked_list. Public derivation is used where the one wants the subclass to inherit the entire interface of the base class.

class stack : public single_linked_list { 
public:
    stack() {}
    void push(int value) {
        insert_at_head(value);
    }
    
    int pop() {
        return remove_at_head();
    } 
};

class queue : public single_linked_list { 
public:
    queue() {}
    void enqueue(int value) {
        insert_at_tail(value);
    }
    
    int dequeue() {
        remove_at_head();
    } 
};

Our two example derived classes can be written to make them not subtypes of their parent class by using private, rather than public derivation.

Both will also need to reexport empty, because it will become hidden to their instances.

class stack_2 : private single_linked_list { 
public:
    stack_2() {}
    
    void push(int value) {
        single_linked_list::insert_at_head(value);
    }
    
    int pop() {
        return single_linked_list::remove_at_head();
    }
    
    single_linked_list::empty();
};

class queue_2 : private single_linked_list { 
public:
    queue_2() {}
    void enqueue(int value) {
        single_linked_list::insert_at_tail(value);
    }
    
    int dequeue() {
        single_linked_list::remove_at_head();
    }
    
    single_linked_list::empty();
};

Multiple Inheritance

Class DrawThread inherits all of the members of both Thread and Drawing.

class Thread { ... };
class Drawing { ... };
class DrawThread : public Thread, public Drawing { ... };

If both Thread and Drawing happen to include members with the same name, they can be unambiguously referenced in objects of class DrawThread by using the scope resolution operator ::.

Initialization

If a class has a parent, the inherited data members must be initialized when the subclass object is created.

subclass (subclass parameters): parent_class(superclass parameters){
    ...
}

// If the default constructor of parent class will be called, no need to write.
subclass (subclass parameters){
    ...
}

Dynamic Binding in C++

C++ does not allow value variables (as opposed to pointers or references) to be polymorphic.
Member functions that must be dynamically bound must be declared to be virtual functions by preceding their headers with the reserved word virtual, which can appear only in a class body.
The peculiar syntax =0 is used to indicate that this member function is a pure virtual function, meaning that it has no body and it cannot be called.
Any class that includes a pure virtual function is an abstract class.

// Example
class Shape { 
public:
    virtual void draw() = 0; 
    ...
};

class Circle : public Shape {
public:
    void draw() { ... }
    ... 
};

class Rectangle : public Shape { 
public:
    void draw() { ... } 
    ...
};

class Square : public Rectangle {
public:
    void draw() { ... }
    ... 
};

Square* sq = new Square; 
Rectangle* rect = new Rectangle; 
Shape* ptr_shape;

ptr_shape = sq;     // Now ptr_shape points to a
                    //  Square object
ptr_shape->draw();    // Dynamically bound to the draw
                    //  in the Square class
rect->draw();        // Statically bound to the draw
                    //  in the Rectangle class

Dynamic Binding

General

It is a kind of polymorphism provided by the dynamic binding of messages to method definitions; this is sometimes called dynamic dispatch.

Static Binding

Overloading Operators.
Overloading Methods.

Exclusivity of Object

Object-oriented programming retains the complete collection of types from a traditional imperative programming language and simply add the object typing model.
Using objects is to have an imperative-style type structure for the primitive scalar types, but implement all structured types (wrapper class) as objects. Bytes, Integer, Char, …

Subclasses & Subtypes

General

Does an “is-a” relationship hold between a derived class and its parent class? It depends.

A derived class is called a subtype if it has an is-a relationship with its parent class.
However, in C++, if the subclass is privately inherited from its superclass, then it is a ... implements in terms of ... relation instead of is-a.

Example

Here is an example: subtype Small_Int is Integer range -100…100;

Variables of Small_Int type have all of the operations of Integer variables but can store only a subset of the values possible in Integer. Furthermore, every Small_Int variable can be used anywhere an Integer variable can be used. That is, every Small_Int variable is, in a sense, an Integer variable.

Allocation & Deallocation

For a1 = b1;:

If a1 and b1 are references to heap-dynamic objects, there is no problem—the assignment is a simple pointer assignment.
If a1 and b1 are stack dynamic, then they are value variables and, if assigned the value of the object, must be copied to the space of the target object.

Object Slicing: If B adds a data field to what it inherited from A, then a1 will not have sufficient space on the stack for all of b1. The excess will simply be truncated.

C++ is using explicit destructor instead of implicit destructor such as Java uses garbage collector.

CIR & Vtable

CIR

The CIR typically contains information about a particular instance of a class (an object). This information can include:

Data Members: Information about the data that is stored by the object.
Method Pointers: If the class has virtual methods (methods that can be overridden by derived classes in languages like C++), pointers to these methods might be stored in the CIR.

Vtable

General

Vtable is a mechanism used to support dynamic dispatch. When an object is created from a class that contains virtual methods, a vtable is used to store addresses of the object’s virtual methods.

Polymorphic variables of an ancestor class always reference the CIR of the correct type object, so getting to the correct version of a dynamically bound method is assured.

Example 1

public class A {
    public int a, b;
    public void draw() { ... }
    public int area() { ... }
};

public class B extends A { 
    public int c, d;
    public void draw() { ... } 
    public void sift() { ... }
};

Example 2

class A { 
public:
    int a;
    virtual void fun() { ... } 
    virtual void init() { ... }
};

class B {
public: 
    int b;
    virtual void sum() { ... } 
};

class C : public A, public B { 
public:
    int c;
    virtual void fun() { ... } 
    virtual void dud() { ... }
};

There must also be two vtables: one for the A and C view and one for the B view. The first part of the CIR for C in this case can be the C and A view, which begins with a vtable pointer for the methods of C and those inherited from A, and includes the data inherited from A.