Data Abstraction

We now examine mechanisms for constructing abstract data types (ADTs), which allow us to abstract the interface for a piece of data from its implementation. We also look at mechanisms for encapsulation, which bind together the data of an ADT along with the functions that operate on that data.

Functional Data Abstraction

We start by modeling data using the tools of procedural abstraction, beginning with a simple pair abstraction and progressing to more complex abstract data types that encode behavior with messages.

Pairs and Lists

Recall that in \(\lambda\)-calculus, a pair is implemented as a function that takes in two items and returns another function:

\[pair ~=~ \lambda x.~ \lambda y.~ \lambda f.~ f~ x~ y\]

We could then obtain the first item by applying the resulting function to \(true\), and the second item by applying it to \(false\):

\[\begin{split}first ~&=~ \lambda p.~ p~ true\\ second ~&=~ \lambda p.~ p~ false\end{split}\]

Following a similar strategy, we can define a pair constructor in Python:

def pair(x, y):
    def get(i):
        return x if i == 0 else y

    return get

As in \(\lambda\)-calculus, the pair() function returns a function with the two items located in the latter’s non-local environment. Now instead of applying the resulting function to a boolean, we call it on an index to retrieve the first or the second item:

def first(p):
    return p(0)

def second(p):
    return p(1)
>>> p = pair(3, 4)
>>> first(p)
3
>>> second(p)
4

Using pairs, we can build a full sequence abstraction, as in Scheme’s pairs and lists. Before we proceed to do so, however, observe that our current pair implementation does not support mutation, which is a key feature of the sequence abstractions provided in imperative languages. We can implement mutation by defining separate get and set functions, using an immutable pair to return both when we construct a mutable pair:

def mutable_pair(x, y):
    def get(i):
        return x if i == 0 else y

    def set(i, value):
        nonlocal x, y
        if i == 0:
            x = value
        else:
            y = value

    return pair(get, set)

def mutable_first(p):
    return first(p)(0)

def mutable_second(p):
    return first(p)(1)

def set_first(p, value):
    second(p)(0, value)

def set_second(p, value):
    second(p)(1, value)
>>> p = mutable_pair(3, 4)
>>> mutable_first(p)
3
>>> mutable_second(p)
4
>>> set_first(p, 5)
>>> set_second(p, 6)
>>> mutable_first(p)
5
>>> mutable_second(p)
6

We use an immutable pair rather than a mutable one to return the get and set functions so as to avoid infinite recursion in mutable_pair(). In the definition of set(), the nonlocal statement is required so that the x and y in the non-local environment are modified.

While this representation works, it does not provide any encapsulation. We now have four functions that manipulate mutable pairs, and we had to name them carefully to avoid conflict with those that work with immutable pairs.

Message Passing

An alternative strategy, assuming that we have access to a string data type, is message passing, in which we send specific messages to an ADT that determine what operations are performed on the data. This can be implemented with a dispatch function that checks the input message against a known set of behaviors and then takes the appropriate action. Using message passing, we can define a mutable pair as follows:

def mutable_pair(x, y):
    def dispatch(message, value=None):
        nonlocal x, y
        if message == 'first':
            return x
        elif message == 'second':
            return y
        elif message == 'set_first':
            x = value
        elif message == 'set_second':
            y = value

    return dispatch
>>> p = mutable_pair(3, 4)
>>> p('first')
3
>>> p('second')
4
>>> p('set_first', 5)
>>> p('set_second', 6)
>>> p('first')
5
>>> p('second')
6

We still represent a pair as a function, but now instead of calling external functions on a pair, we pass it a message and, if appropriate, a value to obtain the action we want. The pair ADT is entirely encapsulated within the mutable_pair() function.

Lists

Now that we have mutable pairs, we can implement a mutable list as a sequence of pairs, as in Scheme. We will use the None object to represent an empty list:

def mutable_list():
    empty_list = None
    head = empty_list
    tail = empty_list

    def size(mlist):
        if mlist is empty_list:
            return 0
        return 1 + size(mlist('second'))

    def getitem(mlist, i):
        if i == 0:
            return mlist('first')
        return getitem(mlist('second'), i - 1)

    def setitem(mlist, i, value):
        if i == 0:
            mlist('set_first', value)
        else:
            setitem(mlist('second'), i - 1, value)

    def to_string():
        if head is empty_list:
            return '[]'
        return ('[' + str(head('first')) +
                to_string_helper(head('second')) + ']')

    def to_string_helper(mlist):
        if mlist is empty_list:
            return ''
        return (', ' + str(mlist('first')) +
                to_string_helper(mlist('second')))

    def append(value):
        nonlocal head, tail
        if head is empty_list:
            head = mutable_pair(value, empty_list)
            tail = head
        else:
            tail('set_second', mutable_pair(value, empty_list))
            tail = tail('second')

    def dispatch(message, arg1=None, arg2=None):
        if message == 'len':
            return size(head)
        elif message == 'getitem':
            return getitem(head, arg1)
        elif message == 'setitem':
            return setitem(head, arg1, arg2)
        elif message == 'str':
            return to_string()
        elif message == 'append':
            return append(arg1)

    return dispatch

To avoid implementing all our functionality within the dispatch() function, we’ve defined separate functions to perform each action. Then the task of the dispatch() function is to call the appropriate function based on the input message. The following demonstrates how to use the mutable list ADT:

>>> l = mutable_list()
>>> l('str')
'[]'
>>> l('len')
0
>>> l('append', 3)
>>> l('append', 4)
>>> l('append', 5)
>>> l('str')
'[3, 4, 5]'
>>> l('len')
3
>>> l('getitem', 1)
4
>>> l('setitem', 1, 6)
>>> l('str')
'[3, 6, 5]'

Dictionaries

We can implement a dictionary ADT using a list of records, each of which consists of a key-value pair.

def dictionary():
    records = mutable_list()

    def get_record(key):
        size = records('len')
        i = 0
        while i < size:
            record = records('getitem', i)
            if key == record('first'):
                return record
            i += 1
        return None

    def getitem(key):
        record = get_record(key)
        return record('second') if record is not None else None

    def setitem(key, value):
        record = get_record(key)
        if record is None:
            records('append', mutable_pair(key, value))
        else:
            record('set_second', value)

    def dispatch(message, key=None, value=None):
        if message == 'getitem':
            return getitem(key)
        elif message == 'setitem':
            setitem(key, value)

    return dispatch

For simplicity, we only implement two messages, one for inserting a key-value pair into a dictionary and one for retrieving the value of a key. A key is looked up by searching through the records for a matching key, and if it is found, the associated value is returned. A key-value pair is inserted by looking up the key and modifying the associated value if it is found. If it is not found, then a new record is inserted.

>>> d = dictionary()
>>> d('setitem', 'a', 3)
>>> d('setitem', 'b', 4)
>>> d('getitem', 'a')
3
>>> d('getitem', 'b')
4
>>> d('setitem', 'a', 5)
>>> d('getitem', 'a')
5

Compare this to code that works with Python’s built-in dictionaries, with special methods invoked directly rather than using operators:

>>> d = dict()
>>> d.__setitem__('a', 3)
>>> d.__setitem__('b', 4)
>>> d.__getitem__('a')
3
>>> d.__getitem__('b')
4
>>> d.__setitem__('a', 5)
>>> d.__getitem__('a')
5

The abstraction we provide is almost the same, with only minor differences in syntax. On the other hand, our dictionary implementation is particularly inefficient, requiring \(\mathcal{O}(n^2)\) time to perform an operation on a dictionary with \(n\) keys. We can reduce this to linear time by implementing an iterator abstraction on lists, but we will not do so here.

Dispatch Dictionaries

Now that we have dictionaries, we can make use of them to simplify our handling of messages. Previously, our dispatch function consisted of a lengthy conditional that called the appropriate internal function based on the message. In order to accommodate internal functions that take in different numbers of arguments, we had to arrange for the dispatch function to be able to take in the maximum number of arguments over the internal functions, and we had to use default arguments to enable fewer arguments to be passed. This can get unwieldy and error-prone the more complex our ADTs become.

Instead, we can store the mapping of messages to functions inside of a dispatch dictionary. When we pass a message to an ADT, it returns back the function corresponding to that message, which we can then call with the appropriate arguments. The following uses this pattern to define an ADT for a bank account:

def account(initial_balance):
    def deposit(amount):
        new_balance = dispatch('getitem', 'balance') + amount
        dispatch('setitem', 'balance', new_balance)
        return new_balance

    def withdraw(amount):
        balance = dispatch('getitem', 'balance')
        if amount > balance:
            return 'Insufficient funds'
        balance -= amount
        dispatch('setitem', 'balance', balance)
        return balance

    def get_balance():
        return dispatch('getitem', 'balance')

    dispatch = dictionary()
    dispatch('setitem', 'balance', initial_balance)
    dispatch('setitem', 'deposit', deposit)
    dispatch('setitem', 'withdraw', withdraw)
    dispatch('setitem', 'get_balance', get_balance)

    def dispatch_message(message):
        return dispatch('getitem', message)

    return dispatch_message

The dispatch dictionary contains an entry for the account balance, as well as functions to deposit, withdraw, and obtain the balance. The dispatch function just retrieves the appropriate function from the dispatch dictionary. We can then use an account as follows:

>>> a = account(33)
>>> a('get_balance')()
33
>>> a('deposit')(4)
37
>>> a('withdraw')(7)
30
>>> a('withdraw')(77)
'Insufficient funds'

Compare this to the interface provided by a bank account implemented as a Python class:

>>> a = Account(33)
>>> a.get_balance()
33
>>> a.deposit(4)
37
>>> a.withdraw(7)
30
>>> a.withdraw(77)
'Insufficient funds'

Once again, our implementation provides a very similar interface with only minor differences in syntax.

We have now constructed a hierarchy of ADTs using functions, progressing from immutable pairs to mutable pairs, lists, and dictionaries, finally arriving at a message-passing abstraction that bears striking resemblance to object-oriented programming. Next, we will examine language-level mechanisms for defining ADTs in the object-oriented paradigm.

Object-Oriented Programming

Object-oriented languages provide mechanisms for defining abstract data types in a systematic manner. Such languages provide means for the following features of ADTs:

  • Encapsulation: The ability to bundle together the data of an ADT along with the functions that operate on that data [1].

  • Information hiding: The ability to restrict access to implementation details of an ADT.

  • Inheritance: The ability to reuse code of an existing ADT when defining another ADT. This includes implementation inheritance, where the actual implementation of an ADT is reused, and interface inheritance, where the new ADT merely supports the same interface as the existing ADT.

  • Subtype polymorphism: The ability to use an instance of a derived ADT where a base ADT is expected. This requires some form of dynamic binding or dynamic dispatch, where the derived ADT’s functionality is used at runtime when the base ADT’s version is expected at compile time.

In object-oriented languages, an ADT is specified by a class, which defines the pattern to be used in instantiating objects of the class.

Members

An object is composed of individual pieces of data, variously called fields, attributes, or data members. Functions that are defined within a class and operate on the contents of an object are often called methods, or in C++ terminology, member functions.

class Foo {
public:
  int x;
  Foo(int x_);
  int baz(int y);
};

In the example above, x is a field, Foo() is a constructor that is called to initialize a new object of type Foo, and baz() is a member function.

A class may also have fields associated with it that are shared among all instances of the class. These are often called static fields or class attributes, and they are often specified with the static keyword, as in the following Java code:

class Foo {
  static int bar = 3;
}

A static field usually can be accessed through the class or through an instance:

System.out.println(Foo.bar); // access through class
System.out.println(new Foo().bar); // access through instance

The following is the same example in C++:

class Foo {
public:
  static int bar;
};

int Foo::bar = 3;

int main() {
  cout << Foo::bar << endl;
  cout << Foo().bar << endl;
}

C++ requires an out-of-line definition for static data members that are not compile-time constants to designate a storage location. Class members are accessed using the scope-resolution operator (::).

Finally, the following demonstrates this example in Python:

class Foo:
   bar = 3

print(Foo.bar)
print(Foo().bar)

Attributes that are defined directly within a class definition are automatically class attributes.

Access Control

Information hiding requires the ability to restrict access to the members of a class or object. Many object-oriented languages provide a mechanism for restricting accessibility (also called visibility) of members. Common categories of access include:

  • allowing only an object itself to access its own data

  • allowing all code in a class to access any data of the class or its instances

  • allowing the data inherited from a base class to be accessed by code in a derived class

  • allowing the data of a class and its instances to be accessed by all code in the same package or module

  • allowing all code in a program to access the data of a class and its instances

In C++, Java, and C#, the public keyword grants all code access to a member, while the private keyword restricts access to the class itself. In C++ and C#, the protected keyword grants access to inherited data to derived classes, while in Java, it additionally grants access to all code in the same package. In C#, the internal keyword grants access to a package. In Java, a member that does not have an access qualifier is accessible to other code in the same package but not to derived classes in other packages.

In many dynamic languages, such as Smalltalk and Python, all members have public accessibility. In Ruby, fields of an object are only accessible to the object itself and not to other objects of the same class.

Table 3 summarizes the access control provided by several languages.

Table 3 Access control in different languages

Access

public

private

C++ protected

Java protected

C# internal/Java default

Python

Same instance

X

X

X

X

X

X

Same class

X

X

X

X

X

X

Derived classes

X

X

X

X

Same package

X

X

X

X

Global access

X

X

A subtlety arises when it comes to the protected access level. Suppose a class Derived derives from Base, and Base defines a protected member x. Is Derived allowed to access the x member of instances of Base that are not also instances of Derived? The following C++ code demonstrates this case:

class Base {
protected:
  int x = 4;
};

class Derived : public Base {
public:
  void foo(Base *b, Derived *d) {
    cout << b->x << endl; // ERROR
    cout << d->x << endl; // OK
  }
};

C++, C#, and Java all prohibit Derived from accessing the protected member x of Base, unless the access is through an instance that is also of type Derived. Thus, the expression b->x above is erroneous, while d->x is permitted.

Kinds of Methods

Methods that operate on instances of a class generally take in the instance itself as a parameter. Often, this parameter is named self or this, either by convention or as a language keyword. In most languages, the instance is an implicit parameter, as in the following C++ code:

class Foo {
public:
  int x;

  int get_x() {
    return this->x;
  }
};

In many languages, the this qualification on a member can be elided, though it is necessary if another variable hides the declaration of the member:

class Bar {
public:
  int x, y;

  void baz(int x) {
    cout << this->x << endl;  // x hidden by parameter
    cout << y << endl;        // y not hidden, so this-> not needed
  }
};

In Python, the instance must be an explicit parameter, conventionally named self. The self qualification cannot be elided:

class Foo:
    def __init__(self, x):
        self.x = x

    def get_x(self):
        return self.x

In most languages, method-call syntax implicitly passes the instance as the implicit or explicit instance parameter, as the instance is syntactically provided as part of the method call:

f = Foo(3)
f.get_x()  # passes f as self parameter to get_x()

Most languages also provide a means for defining static methods, which do not operate on an instance but can generally be called on a class or instance. In languages in the C++ family, the static keyword specifies a static method. In Python, the @staticmethod decorator accomplishes this:

class Baz:
    @staticmethod
    def name():
        return 'Baz'

print(Baz.name())
print(Baz().name())

Without the @staticmethod decorator, the function name() cannot be called on an instance of Baz. Python also has a @classmethod decorator that allows definition of a static-like method that takes in the class itself as the first argument:

class Baz:
    @classmethod
    def name(cls):
        return cls.__name__

class Fie(Baz):
    pass

print(Baz.name())     # prints Baz
print(Baz().name())   # prints Baz
print(Fie.name())     # prints Fie
print(Fie().name())   # prints Fie

Some languages, such as C# and Python, provide a mechanism for defining property methods that act as accessors to fields. Such a method is called using field-access syntax and is useful for controlling access to a field. A property method can also be used to provide a field interface for data that must be computed on the fly, such as in the following complex-number representation:

import math

class Complex(object):
    def __init__(self, real, imag):
        self.real = real
        self.imag = imag

    @property
    def magnitude(self):
        return (self.real ** 2 + self.imag ** 2) ** 0.5

    @magnitude.setter
    def magnitude(self, mag):
        old_angle = self.angle
        self.real = mag * math.cos(old_angle)
        self.imag = mag * math.sin(old_angle)

    @property
    def angle(self):
        return math.atan2(self.imag, self.real)

    @angle.setter
    def angle(self, ang):
        old_magnitude = self.magnitude
        self.real = old_magnitude * math.cos(ang)
        self.imag = old_magnitude * math.sin(ang)

The @property decorator defines a getter, followed by which the @<method>.setter decorator can be used to define a setter, where <method> is the name of the function used with @property. With magnitude and angle defined as properties with both getters and setters, we can use them as follows:

>>> c = Complex(1, math.sqrt(3))
>>> c.magnitude
2.0
>>> c.angle / math.pi
0.3333333333333333
>>> c.magnitude = math.sqrt(2)
>>> c.angle = math.pi / 4
>>> c.real
1.0000000000000002
>>> c.imag
1.0

Thus, property methods allow the interface of a field to be abstracted from its implementation. In the example of Complex, we could change the implementation such that magnitude and angle are stored as standard fields and real and imag are implemented as property methods. This would not change the interface of Complex at all, abstracting the implementation change from outside code.

Nested and Local Classes

Some object-oriented languages allow a nested class to be defined within the scope of another class. This enables a helper class to be encapsulated within the scope of an outer class, enabling it to be hidden from users of the outer class. A language may also allow a class to be defined at local scope as well.

Languages in which classes are first-class entities allow the creation of new classes at runtime. Generally, such a creation may happen at any scope, and the class has access to its definition environment (i.e. it has static scope). Python is an example of such a language.

In C++, nested and local classes act as any other classes, except that they have access to the private members of the enclosing class. On the other hand, the enclosing class must be declared as a friend of a nested class in order to have access to the private members of the nested class. A local class does not have access to the local variables in the enclosing stack frame.

Java provides more flexibility in its nested and local classes. Local classes have access to local variables that are effectively final, meaning that they are only assigned once and never modified. When defined in a non-static scope, both nested and local classes are associated with an actual instance of the enclosing class and have direct access to its fields:

class Outer {
  private int x;

  Outer(int x) {
    this.x = x;
  }

  class Inner {
    private int y;

    Inner(int y) {
      this.y = y;
    }

    int get() {
      return x + y;
    }
  }
}

class Main {
  public static void main(String[] args) {
    Outer out = new Outer(3);
    Outer.Inner inn = out.new Inner(4);
    System.out.println(inn.get());
  }
}

In Java, nested and local classes have access to private members of the enclosing class, and the enclosing class has access to the private members of a nested class. The definition of a nested class can be prefaced with the static keyword to dissociate it from any instance of the enclosing class.

Implementation Strategies

In concept, object-oriented programming is built around the idea of passing messages to objects, which then respond in a manner appropriate for the object. Access to a member can be thought of as sending a message to the object. Languages differ in whether or not the set of messages an object responds to is fixed at compile time, as well as whether the actual message that is passed to an object is fixed at compile time.

In efficiency-oriented languages such as C++ and Java, the set of messages that an object supports is fixed at compile time and is the same for all instances of a class. Such a language enables objects to be implemented in a manner similar to records or structs: the fields of an object can be stored contiguously within the memory for the object, with one slot for each field. Access to a field can then be translated at compile time to a fixed offset into the object, similar to an offset-based implementation of activation records . As an example, consider the following class in C++:

class Foo {
public:
  int x, y;
  Foo(int x_, int y_);
};

The fields x and y are stored contiguously within the Foo object, with x at an offset of zero bytes from the beginning of the Foo object and y at an offset of four bytes, since x takes up four bytes (assuming that sizeof(int) == 4). Figure 28 illustrates this layout:

_images/record.svg

Figure 28 Record-based implementation of an object.

Then given a Foo object f, the field access f.x is translated at compile time to an offset of zero from the address of f, while f.y is translated to an offset of four. No lookup is required at runtime, making such an implementation very efficient.

In languages that enable a member to be added to a class or even an individual object at runtime, members are usually stored within a dictionary, analogous to a dictionary-based implementation of activation records. This is similar to the message-passing scheme demonstrated in the last section. Such a language defines a process for looking up a member. For example, in Python, accessing an attribute of an object first checks the dictionary for the object before proceeding to the dictionary for its class:

class Foo:
    y = 2

    def __init__(self, x):
        self.x = x

f = Foo(3)
print(f.x, f.y, Foo.y)   # prints 3 2 2
f.y = 4                  # adds binding to instance dictionary
print(f.x, f.y, Foo.y)   # prints 3 4 2

The class Foo has a class attribute y, and the constructor creates an instance attribute x. Looking up f.x first looks in the instance dictionary, finding a binding there. On the other hand, looking up f.y within the first call to print() does not find y in the instance dictionary, so lookup proceeds to the class dictionary, finding it there. The assignment f.y = 4 introduces a binding for y in the instance dictionary, so subsequent lookups find y there.

Python actually takes a hybrid approach, using a dictionary by default but allowing a class to specify a record-like implementation using the special __slots__ attribute. The following is a definition of the Complex class to use this mechanism:

import math

class Complex(object):
    __slots__ = ('real', 'imag')

    def __init__(self, real, imag):
        self.real = real
        self.imag = imag

    @property
    def magnitude(self):
        return (self.real ** 2 + self.imag ** 2) ** 0.5

    @magnitude.setter
    def magnitude(self, mag):
        old_angle = self.angle
        self.real = mag * math.cos(old_angle)
        self.imag = mag * math.sin(old_angle)

    @property
    def angle(self):
        return math.atan2(self.imag, self.real)

    @angle.setter
    def angle(self, ang):
        old_magnitude = self.magnitude
        self.real = old_magnitude * math.cos(ang)
        self.imag = old_magnitude * math.sin(ang)

Instances of a class that uses __slots__ no longer store attributes in a dictionary, saving space and providing better performance. However, they lose the ability of adding attributes to a specific instance at runtime.

Dictionary-based languages usually provide a mechanism for dynamically constructing a message and passing it to an object, such as the special __getattribute__ method of Python objects:

>>> x = [1, 2, 3]
>>> x.__getattribute__('append')(4)
>>> x
[1, 2, 3, 4]

Java also supports dynamic invocation of messages through a powerful reflection API, which provides a form of runtime type information:

import java.lang.reflect.Method;

class Main {
  public static void main(String[] args) throws Exception {
    String s = "Hello World";
    Method m = String.class.getMethod("length", null);
    System.out.println(m.invoke(s));
  }
}

Inheritance and Polymorphism

Inheritance and polymorphism are two key features of object-oriented programming, enabling code reuse as well as allowing the specialization of behavior based on the dynamic type of an object. Languages differ greatly in the design choices they make in the specifics of how they support inheritance and polymorphism. In this section, we discuss some of these design choices as well as how they are typically implemented.

Types of Inheritance

In Object-Oriented Programming, we alluded to the fact that interface inheritance only reuses the interface of an ADT, while implementation inheritance reuses the implementation. These two types of inheritance are strongly coupled in most languages; specifically, implementation inheritance almost always includes interface inheritance as well. C++ is an exception, allowing fields and methods to be inherited without exposing them as part of the interface of the derived class.

In particular, C++ supports private, protected, and public inheritance, which designate the accessibility of inherited members. In private inheritance, all inherited members are made private in the derived class. In protected inheritance, inherited members that were originally public are made protected, while more restricted members retain their original accessibility. In public inheritance, all inherited members retain their original accessibility. The general rule is that the accessibility of an inherited members is the more restrictive of its original accessibility and the type of inheritance. In keeping with the meaning of private discussed previously, inherited members that were originally private are not accessible to the derived class itself.

The default inheritance variant is public for classes defined using the struct keyword, while it is private if the class keyword is used. The programmer can override the default by placing an access modifier in front of the base class, as in the following:

class A {
public:
  void foo();

protected:
  void bar();

private:
  void baz();
};

class B : public A {
};

class C : protected A {
};

class D : A {
};

In this example, the method foo() is public in B, protected in C, and private in D. Thus, D inherits the implementation of foo() without exposing it as part of its interface. The method bar() is protected in B and C and private in D. Finally, the member function baz() is private in all three derived classes, while also being inaccessible to the classes themselves.

C++ also allows derived classes to delete non-virtual inherited methods.

Some languages allow an interface to be inherited without the implementation, requiring concrete derived classes to provide their own implementation. A method is abstract (pure virtual in C++ terminology) if no implementation is provided, and a class is abstract if it has at least one abstract method, whether the abstract method is declared directly in the class or inherited. In Java, abstract classes must be labeled as such:

abstract class A {
  abstract void foo();
}

A class that only has abstract methods is often called an interface, and Java has specific mechanisms for defining and implementing an interface:

interface I {
  void bar();
}

class C extends A implements I {
  void foo() {
    System.out.println("foo() in C");
  }

  public void bar() {
    System.out.println("bar() in C");
  }
}

Abstract methods in Java may have any access level except private, but interface methods are implicitly public. Java allows a class to implement multiple interfaces, though it only allows it to derive from a single class.

Some languages further decouple inheritance from polymorphism by allowing methods to be inherited without establishing a parent-child relationship between two classes. The class that defines these methods is called a mixin, and a mixin can be included from another class to obtain those methods. The use of mixins is particularly common in Ruby. The following is an example:

class Counter
  include Comparable
  attr_accessor :count

  def initialize()
    @count = 0
  end

  def increment()
    @count += 1
  end

  def <=>(other)
    @count <=> other.count
  end
end

c1 = Counter.new()
c2 = Counter.new()
c1.increment()
print c1 == c2
print c1 < c2
print c1 > c2

By including the Comparable mixin, the Counter class obtains comparison methods such as < and <= that use the general <=> comparison method defined in Counter.

We will see later how to implement mixins in C++ using the curiously recurring template pattern.

Class Hierarchies

In some languages, such as Java and Python, every class eventually derives from a root class, called Object in Java and object in Python. This results in a single class hierarchy rooted at the root class. In Java, this hierarchy is a tree, since Java does not allow multiple inheritance outside of interfaces. Python does allow multiple inheritance, so the hierarchy is a directed acyclic graph. Other languages, including C++, do not have a root class.

A root class enables code to be written that works on all class-type objects. For example, a Vector<Object> in Java can hold objects of any type. Because the Object class defines an equals() method, such a data structure can be searched to find an object that is semantically equal to an item:

Vector<Object> unique(Vector<Object> items) {
  Vector<Object> result = new Vector<Object>();
  for (Object item : items) {
    if (!result.contains(item)) {
      result.add(item);
    }
  }
  return result;
}

In this example, the contains() method of Vector<Object> calls the equals() method on an element. Since the root Object class defines equals(), it is valid to call on an instance of any class.

In contrast, C++ allows void * to hold a pointer to any object, so that a vector<void *> can store pointers to arbitrary objects. However, a void * does not implement any behavior, so we can only compare such pointers by pointer value and not whether the actual referenced objects are equal.

Method Overriding

The ability to override a method in a derived class is the key to polymorphism in object-oriented programming. Overriding requires dynamic binding, where the actual method to be invoked is determined by an object’s dynamic type rather than the type apparent in the program source.

As we will see shortly, dynamic binding comes at a runtime cost. To avoid this cost wherever possible, instance methods do not use dynamic binding by default in C++. Instead, an instance method must be designated as virtual in order for dynamic binding to be used. Java, on the other hand, uses dynamic binding for all instance methods, except those designated as final in some cases, since they cannot be overridden. Both languages use static binding for static methods, whether or not they are dispatched through an object.

Dynamically typed languages universally support dynamic binding, since objects do not have a static type. Such languages include Python and Ruby.

In languages that support method overloading, including C++ and Java, a method generally must have the same parameter list as the method it is overriding. Otherwise, the new definition is treated as overloading or hiding the base-class method instead. This can lead to unexpected behavior, such as the following code in Java:

class Foo {
  int x;

  Foo(int x) {
    this.x = x;
  }

  public boolean equals(Foo other) {
    return x == other.x;
  }
}

Vector<Foo> vec = new Vector<Foo>();
vec.add(new Foo(3));
System.out.println(vec.contains(new Foo(3)));

This code, when run, prints out false. The problem is that the equals() method defined in Object has the signature:

public boolean equals(Object other)

The difference in the parameter type causes the equals() that is defined in Foo to be an overload rather than overriding the inherited method. Combined with the fact that generics in Java do not generate code that is specialized to the type parameter, this results in the original equals() method being called from the contains() method in Vector.

Java allows a method to be annotated to assert that it is an override, as follows:

@Override
public boolean equals(Foo other) {
  return x == other.x;
}

The compiler will then detect that the method does not in fact override a base-class method and will report an error. C++11 has a similar override keyword that can be placed at the end of a method signature:

virtual void foo(Bar b) override;

Covariance and Contravariance

Some statically typed languages, including C++ and Java, permit covariant return types, where the return type of an overriding method is a derived type of the return type in the overridden method. Such a narrowing is semantically valid, since a derived object can be used (at least as far as the type system is concerned) where a base type is expected. The clone() method in Java is an example, where the version in Object returns Object:

class Foo {
  int x;

  @Override
  public Foo clone() {
    Foo f = new Foo();
    f.x = x;
    return f;
  }
}

Equally valid semantically for parameter types is contravariance, where an overriding method takes in a base type of the parameter type in the overridden method. However, in languages that allow overloading, parameter contravariance results in an ambiguity: is the newly defined method an override of the original method, an overload of the method, or does it hide the base-class method? Consider the following example in Java:

class Foo {
  int foo(Foo other) {
    return 0;
  }
}

class Bar extends Foo {
  int foo(Object other) {
    return 1;
  }
}

The call to b.foo(arg), where b is of type Bar, results in different behavior depending on the type of arg:

Bar b = new Bar();
System.out.println(b.foo(new Bar()));     // prints 0
System.out.println(b.foo(new Object()));  // prints 1

Thus, in Java, defining a method with a parameter that is contravariant to the base-class method results in an overload. On the other hand, in C++, this pattern hides the base-class method:

class Base {
};

class Foo : public Base {
public:
  int foo(const Foo &other) const {
    return 0;
  }
};

class Bar : public Foo {
public:
  int foo(const Base &other) const {
    return 1;
  }
};

int main() {
  Bar b;
  cout << b.foo(Bar()) << endl;   // prints 1
  cout << b.foo(Base()) << endl;  // prints 1
}

In both languages, the derived-class method with contravariant parameters does not override the base-class method.

Accessing Hidden or Overridden Members

In many languages, base-class members that are not overridden but redefined in a derived class are hidden by the definition in the derived class. This is the case for non-virtual methods in C++, as well as virtual methods that differ in signature from the method defined in the base class. In Java, on the other hand, a derived-class method with the same name as a base-class method but a different signature overloads the base-class method rather than override or hide it, as we saw in Method Overriding.

In record-based languages, redefining a field in a derived class usually results in the derived object containing both the hidden and the redefined field. In dictionary-based languages, however, objects usually only have a single field for a given name. Using __slots__ in Python, space is reserved for both the hidden and the redefined field, but field access always accesses the slot defined in the derived class.

A common pattern in a derived-class method is to add functionality to that of the base-class method that it is overriding or hiding. In order to avoid repeating code, most languages provide a means of calling the base-class method. In C++, the scope-resolution operator enables this:

struct A {
  void foo() {
    cout << "A::foo()" << endl;
  }
};

struct B : A {
  void foo() {
    A::foo();
    cout << "B::foo()" << endl;
  }
};

More common is some variation of super, as in the following in Java:

class A {
  void foo() {
    System.out.println("A.foo()");
  }
}

class B extends A {
  void foo() {
    super.foo();
    System.out.println("B.foo()");
  }
}

Python uses similar syntax:

class A:
    def foo(self):
        print('A.foo()')

class B(A):
    def foo(self):
        super().foo()
        print('B.foo()')

The same mechanisms can be used to access a hidden field, i.e. the scope-resolution operator in C++ and super in Java. In Python, super() can be used to access hidden static fields; instance fields are not replicated within an object.

Perhaps the most common case where a base class member needs to be accessed is the constructor for the derived class, where the base-class constructor needs to be invoked. In C++, a base-class constructor can be explicitly invoked from a constructor’s initializer list:

struct A {
  A(int x);
};

struct B : A {
  B(int x) : A(x) {}
};

If no explicit call is made to a base-class constructor, a call to the default constructor of the base class is inserted by the compiler, and it is an error if such a constructor does not exist. The base-class constructor runs before any other initializers or the body of the derived-class constructor, regardless of where the former appears in the latter’s initializer list.

In Java, a call to a base-class constructor must be the first statement in a constructor, and the compiler implicitly inserts a call to the zero-argument base-class constructor if an explicit call is not provided.

class A {
  A(int x) {
  }
}

class B extends A {
  B(int x) {
    super(x);
  }
}

In Python, a call to a base-class constructor must be made explicitly, and the interpreter does not insert one if it is missing.

class A:
    def __init__(self, x):
        pass

class B(A):
    def __init__(self, x):
        super().__init__(x)

Implementing Dynamic Binding

In dictionary-based languages such as Python, dynamic binding is straightforward to implement with a sequence of dictionary lookups at runtime. In particular, when accessing an attribute of an object in Python, Python first searches the dictionary for the object itself. If it is not found, then it searches the dictionary for the object’s class. If the attribute is still not found, it proceeds to the base-class dictionaries.

In record-based languages, however, efficiency is a primary concern, and dynamic name lookup can be prohibitively expensive. Instead, such languages commonly store pointers to methods that need to be looked up dynamically in a structure called a virtual table, or vtable for short. This name is a reflection of the term “virtual” in C++, which denotes methods that are dynamically bound.

As an example, consider the following C++ code:

struct A {
  int x;
  double y;
  virtual void a();
  virtual int b(int i);
  virtual void c(double d);
  void f();
};

struct B : A {
  int z;
  char w;
  virtual void d();
  virtual double e();
  virtual int b(int i);
  void f();
};

The storage for an object of type A contains as its first item a pointer to the vtable for class A, which is then followed by entries for fields x and y. The vtable for A contains pointers to each of its virtual methods in order, as shown in Figure 29.

_images/vtable_a.svg

Figure 29 A record-based implementation of an object with dynamically bound methods stores a vtable pointer at the beginning of the object. The vtable stores pointers to each dynamically bound method.

Neither the storage for an object of type A nor the vtable for A contains a pointer to A::f: the latter is not a virtual method and so is not dynamically bound. Instead, the compiler can generate a direct dispatch to A::f when the method is called on an object whose static type is A.

The storage for an object of type B also contains a vtable pointer as its first item. This is then followed by inherited fields, after which are slots for fields introduced by B. The vtable for B contains pointers for each of its methods. First come methods inherited from A or overridden, in the same order as in the vtable for A. Then the new methods introduced by B follow, as illustrated in Figure 30.

_images/vtable_b.svg

Figure 30 The layout of a derived-class object consists of a vtable pointer, then inherited fields, followed by fields introduced by the derived class. The vtable for the derived class begins with the same layout as that of the base class, followed by new methods introduced by the derived class.

As mentioned previously, fields are statically bound, but fields that are inherited from A are at the same offsets in both A and B. Thus, the compiler can translate a field access to an offset into an object, and the same offset will work for a base class and its derived classes. We can observe this by computing the offset of the member x in an A and a B from the beginning of the object:

A a;
B b;
cout << (((uintptr_t) &a.x) - (uintptr_t) &a) << endl;
cout << (((uintptr_t) &b.x) - (uintptr_t) &b) << endl;

Converting a pointer to a uintptr_t results in its address value. Running the above code results in the same offset of 8 using Clang on a 64-bit Intel machine, reflecting the size of the vtable pointer that comes before x.

Dynamically bound methods, on the other hand, require an indirection. A method override has the same offset in a derived class’s vtable as the overridden method in the base class’s vtable. In the example above, B::b is located in the second entry in the vtable for B, which is the same offset as where A::b is stored in the vtable for A. Thus, the compiler can translate a dynamic method call to a dereference into the object to get to its vtable, a fixed offset into the vtable, followed by another dereference to get to the actual code pointer. As an example, consider the following:

A *aptr = new B;
aptr->b();

The following pseudocode demonstrates the process of calling b():

// extract vtable pointer from start of object
vtable_ptr = aptr-><vtable>;
// index into vtable at statically computed offset for b
func_ptr = vtable_ptr[1];
// call function, passing the implicit this parameter
func_ptr(aptr);

This process requires two dereferences to obtain the code location of the dynamically bound method, one to extract the vtable pointer from the object and another to index into the vtable. In contrast, the code location for a statically bound method call can be determined at compile time, which is more efficient than the two runtime dereferences required in dynamic binding.

Full Lookup and Dispatch Process

In general, the receiver of a method call in a statically typed language can have a dynamic type that differs from its static type. For example, in the code below, the receivers of the first two method calls have static type A while their dynamic type is B:

A *aptr = new B;
A &aref = *aptr;
B *bptr = new B;
aptr->b();    // receiver has static type A, dynamic type B
aref.f();     // receiver has static type A, dynamic type B
bptr->b();    // receiver has static type B, dynamic type B

The following is the general pattern that statically typed languages use to look up the target method and generate a dispatch to the appropriate code:

  1. Look up the member (e.g. b in the case of aptr->b()) in the static type of the receiver, performing function-overload resolution if necessary to determine which method is being called.

  2. If the resolved method is non-virtual, then generate a direct dispatch to the code for that method. For example, in the call aref.f() above, a direct dispatch to A::f would be generated since A::f, the result of the lookup, is non-virtual.

  3. If the resolved method is virtual, then determine its offset in the vtable of the static type. In the case of aptr->b(), the resolved method is A::b, which is the second entry in the vtable for A. Then an indirect dispatch is generated, as described previously:

    vtable_ptr = aptr-><vtable>;
    func_ptr = vtable_ptr[1];
    func_ptr(aptr);
    

Multiple Inheritance

Some languages allow a class to directly inherit from multiple base classes. This includes the limited form enabled by Java’s interfaces, as well as the fully general multiple inheritance provided by Python and C++. Multiple inheritance raises several semantic and implementation issues that do not occur in single inheritance.

Dictionary-Based Implementation

In Python, where instance fields are stored in an object’s dictionary by default, there is no concept of inheriting instance fields from a base class. Thus, in the absence of __slots__, multiple inheritance poses no problems for looking up an instance field. On the other hand, methods are generally stored in the dictionary for a class, along with static fields. Thus, a key question raised by multiple inheritance is in which order to search base-class dictionaries if an attribute is not found in the dictionary for an object or its class. The solution is non-trivial, as can be seen in the example below:

class Animal:
    def defend(self):
        print('run away!')

class Insect(Animal):
    pass

class WingedAnimal(Animal):
    def defend(self):
        print('fly away!')

class Butterfly(Insect, WingedAnimal):
    pass

If defend() is called on a Butterfly, there are several orders in which the method can be looked up among its base classes. A naive depth-first search would result in Animal.defend, but WingedAnimal.defend is in a sense “more derived” than Animal.defend and should be preferred in most cases. The actual algorithm used by Python is C3 linearization, which results in an order that preserves certain important aspects of the inheritance hierarchy. The details are beyond the scope of this text, but the result is that WingedAnimal.defend is used:

>>> Butterfly().defend()
fly away!

Record-Based Implementation

In a record-based implementation, multiple inheritance makes it impossible to ensure that a field is stored at a consistent offset from the beginning of an object. Consider the following C++ code:

struct A {
  int x;
  virtual void a();
  virtual void b();
};

struct B {
  int y;
  virtual void c();
  virtual void d();
};

struct C : A, B {
  int z;
  virtual void a();
  virtual void c();
  virtual void e();
};

In objects of type A, the field x is stored in the first entry after the vtable pointer. Similarly, y in B is stored in the first entry. With C deriving from both A and B, only one of those fields can be stored in the first entry for C. A similar problem occurs for method entries in a vtable.

Python classes that define __slots__ suffer the same problem, as in the following:

class A:
    __slots__ = 'x'

class B:
    __slots__ = 'y'

class C(A, B):
    pass

Python’s solution to this conflict is to make it illegal for a class to derive from multiple base classes that define __slots__.

C++, on the other hand, does permit code like the above. The solution that C++ uses is to combine different views of an object that has multiple base classes within the storage for the object. In the example above, we would have one view of the object from the perspective of C and A, and a separate view from the perspective of B, each with its own vtable. Figure 31 illustrates the two views.

_images/vtable_c.svg

Figure 31 Multiple inheritance in a record-based implementation results in multiple views of an object, each with its own vtable.

Now the view used depends on the type of pointer or reference that refers to a C object:

C *c_ptr = new C();    // uses view A, C
A *a_ptr = c_ptr;      // uses view A, C
B *b_ptr = c_ptr;      // uses view B

When a pointer of type C * is converted to one of type B *, the compiler automatically adjusts the pointer to use the view for B. Then the offset for y from that view is the same as that of an object of type B. Similarly, the methods that are inherited from B or overridden are located at the same vtable offsets in the vtable for view B as in the vtable for an object of type B itself. The same properties hold for the A view and objects of actual type A.

The problem is not yet completely solved, however. What happens when we invoke an overridden method through the B view? Specifically, consider the following:

void C::c() {
  cout << z;
}

C *c_ptr = new C();
B *b_ptr = c_ptr;
c_ptr->c();
b_ptr->c();

If the code generated for C::c() assumes an offset for z based on the C view, then that same offset is not valid for the B view. In particular, z is two vtable pointers and two ints away from the beginning of the C view, but it is one vtable pointer and one int away in the B view. We need to arrange for the view of the object to be the C view in the body of C::c(), even when the method is invoked through a B pointer. One way to do this is to store offsets in vtable entries that designate how to change the pointer when the given method is invoked, as in Figure 32.

_images/vtable_c_off.svg

Figure 32 Calling a base-class method on an object that uses multiple inheritance may require a this-pointer correction to switch from one view of the object to another.

Now, when the entry for C::c is looked up in C‘s vtable for view B, the this pointer in C::c should be corrected by -off before it is invoked, where off is the distance between the C and B views of an object of type C. This will ensure that C::c receives the C view of the object.

In practice, a thunk (a compiler-generated function) is often used to both perform this correction and call the target method. The vtable entry for the method can then store a pointer to the thunk, and no offset need be stored in the vtable. This avoids replicating the correction code everywhere a method is called.

Another complication arises when multiple base classes define the same function, as in the Python example above. The following is the same example in C++:

class Animal {
public:
  void defend() const {
    cout << "run away!" << endl;
  }
};

class Insect : public Animal {
};

class WingedAnimal : public Animal {
public:
  void defend() const {
    cout << "fly away!" << endl;
  }
};

class Butterfly : public Insect, public WingedAnimal {
};

A call to defend() on a Butterfly object can resolve to either the version in Animal or WingedAnimal. Vtables alone cannot solve this problem, and a more involved dynamic lookup process such as C3 linearization would be required instead. However, C++ considers such a method call to be ambiguous and will produce a compile-time error if the call is attempted. Instead, C++ requires the programmer to select a specific version using the scope-resolution operator:

Butterfly bf;
bf.WingedAnimal::defend();

A final consideration in record-based implementations is how to handle the diamond problem, where a single class occurs multiple times as the base class for another class. In the example above, Butterfly derives from Animal twice, once through Insect and once through WingedAnimal. If Animal defines fields, should a Butterfly object contain a single copy of the fields inherited from Animal, or should there be two copies? Different situations may call for different approaches, and C++ allows both. The default is replication, but a shared copy of Animal can be specified using virtual inheritance:

class Animal {
  std::string name;
};

class Insect : public virtual Animal {
  int i;
};

class WingedAnimal : public virtual Animal {
  int w;
};

class Butterfly : public Insect, public WingedAnimal {
};

Virtual inheritance is commonly implemented by introducing indirection to access data members of the virtual base class, in a manner similar to vtables and vtable pointers. Figure Figure 33 illustrates one possible implementation of the class hierarchy above with virtual inheritance.

_images/virtual_inheritance.svg

Figure 33 Virtual inheritance uses indirection to avoid replicating a base-class sub-object. Both Insect and WingedAnimal have a pointer that refers to the Animal sub-object. Then their common Butterfly derived class has two pointers that point to the same Animal sub-object.

As this example demonstrates, the intermediate classes Insect and WingedAnimal are the ones that must declare Animal as a virtual base class, even though it is the class Butterfly that actually gives rise to the diamond problem. This implies that the writer of the intermediate classes must know a priori that derived classes may run into the diamond problem. Thus, to some degree, this breaks the abstraction barrier between base and derived classes.

Static Analysis

In processing a program, a compiler performs static analysis on the source code without actually running the program. Analysis is done to detect bugs in programs as well as to determine information that can be used to generate optimized code. However, as demonstrated by Rice’s theorem, the general problem of static analysis of the behavior of a program written in a Turing-complete language is undecidable, meaning that it is not solvable by a computer. Thus, program analysis on Turing-complete languages can only approximate the answer, and there will always be cases where the result determined by the analysis is incorrect.

In designing an analysis, we usually make the choice between the analysis being sound or complete, which characterizes where the analysis may produce an incorrect result:

  • A sound analysis only accepts programs that are correct with respect to the behavior being analyzed. If a program is incorrect, the analysis is guaranteed to reject it. On the other hand, if a program is correct, it is possible for the analysis to reject it, resulting in false negatives. Since a sound analysis only accepts correct programs, if a program passes the analysis, we know that it must be correct. However, if a program fails the analysis, it may or may not be correct.

  • A complete analysis accepts all programs that are correct with respect to the behavior being analyzed. If a program is incorrect, it is possible for the analysis to accept it, resulting in false positives. If a program fails the analysis, it must be erroneous, but if the program passes the analysis, it may or may not be correct.

It is often the case that static analyses are designed to be sound, while dynamic (runtime) analyses are typically designed to be complete.

An analysis cannot be both sound and complete, but it is possible for an analysis to be neither. In such a case, it produces both false positives and false negatives, which is undesirable. However, in practice, real-world analyses often end up being neither sound nor complete due to the complexity of the problems they are trying to solve.

We proceed to discuss two common forms of static analysis, on types and on control flow.

Types

In Formal Type Systems, we explored the theoretical underpinnings of types and type checking. Here, we take a less formal look at how languages handle types, reviewing some concepts from type checking along the way.

In most programming languages, expressions and objects have a type associated with them. An object’s type determines how its data are interpreted; all data are represented as bits, and it is a datum’s type that determines the meaning of those bits. Types also prevent common errors, such as attempting to perform a semantically invalid operation like adding a floating-point number and an array. For languages in which types of variables and functions are specified in the source code, they also serve as useful documentation concerning for what a variable or function is used. In languages that support ad-hoc polymorphism in the form of operator or function overloading, types determine the specific operation to be applied to the input data. Finally, types enable compilers to generate code that is specialized to the type of an object or expression.

Compilers perform type checking to ensure that types are used in semantically valid ways in a program. Languages that enable static analysis to perform type checking at compile time are statically typed, while those that can only be checked at runtime are dynamically typed. Many languages use a mixture of static and dynamic type checking.

Languages often provide a predefined set of primitive types, such as integers, floating-point numbers, and characters, as well as a mechanism for constructing composite types whose components, or fields, are simpler types. Common examples are arrays, lists, and records, the latter of which are known as structs in C and C++.

Type Equivalence

In some languages, composite types are distinguished by their structure, so that all types with the same structure are considered to be equivalent. This strategy is called structural equivalence, and under this scheme, the following two types (using C-like syntax) would be equivalent:

record A {
  int a;
  int b;
};

record B {
  int a;
  int b;
};

In a handful of languages, such as ML, reordering the fields does not affect type equivalence. Thus, a type such as the following would also be equivalent:

record C {
  int b;
  int a;
};

Most modern languages, on the other hand, use name equivalence, which distinguishes between different occurrences of definitions within a program. Under name equivalence, the types A and B above would be considered distinct.

Some languages allow aliases to be defined for an existing type, such as the following declarations in C++:

typedef double weight;
using height = double;

Under strict name equivalence, aliases are considered distinct types, so that weight and height are not equivalent. This can prevent errors involving inadvertently interchanging types that alias the same underlying type but are semantically distinct, as in the following involving weight and height:

height h = weight(200.);

The languages in the C family, however, have loose name equivalence, so that aliases are considered equivalent to each other and to the original type. The code above is permitted under loose name equivalence.

Type Compatibility

In most languages, strict equivalence of types is not required in order for the types to be used in the same context. Rather, most languages specify type compatibility rules that determine when one type can be used where another one is expected.

Subtype polymorphism is one example of type compatibility. Languages that support subtypes, such as those that support the object-oriented paradigm, allow an object of a derived type to be used where an object of a base type is expected.

In other contexts, a language may allow a type to be used where another is expected by converting a value of the former type to the latter. Such a conversion, when done implicitly, is called a type coercion. A common example is when performing an arithmetic operation on different numeric types. In an expression such as a + b, if one of the operands has integral type and the other has floating-point type, most languages coerce the integral value to floating-point before performing the addition. Languages usually specify rules for which numeric types are coerced, or promoted, to others. A few languages, such as C++, include a mechanism for defining type coercions on user-defined types.

Some languages allow coercion when initializing or assigning an object with a value from a different type. For numeric types, some languages only allow initialization or assignment that performs a coercion that follows the type promotion rules. For example, in Java, coercing an int value to a double is allowed, while the latter is prohibited:

int x = 3.4;   // error
double y = 3;  // OK

The promotion rules are often designed to avoid loss of information. In particular, converting a double value to an int loses information about the fractional part of the value. In other languages, however, such as C and C++, lossy coercions are permitted, and both definitions above would be accepted.

Another common example of coercion that we’ve already seen is that of l-values to r-values, where an r-value is expected.

Languages with type qualifiers specify rules for when a type with one qualification can be coerced to the same type with a different qualification. For example, C++ specifies when const and non-const types can be coerced to each other. In particular, a non-const l-value can be coerced to a const l-value, but the reverse is not allowed without an explicit const_cast. On the other hand, a const l-value can be coerced to a non-const r-value. The following illustrates some examples:

int a = 3;
const int b = a;    // OK: l-value to r-value
a = b;              // OK: const l-value to r-value
int &c = a;         // OK: no coercion
int &d = b;         // ERROR: const l-value to non-const l-value
const int &e = a;   // OK: non-const l-value to const l-value

In order to check the types in a program, a strongly typed language determines the type of every expression in the program. For example, in the compound expression a + b + c, the type of the subexpression a + b must be known in order to determine what operation to apply to its result and c, whether or not a coercion is necessary or permitted. In the case of a function-call expression, the type of the expression is the return type of the function. In the case of an operator, the language defines what the type of the expression is based on the types of the operands.

The following is an example in C++:

cout << ("Weight is " + to_string(10) + " grams") << endl;

The to_string() function returns a string, so that is the type of the expression to_string(10). Applying the + operator to a string and a string (character-array) literal in turn results in string. Applying the << operator to an ostream& and a string results in an ostream&. Lastly, endl is a function that is an I/O manipulator, and applying << to an ostream& and such a function also produces an ostream&.

A particular non-trivial case is that of the conditional expression in languages that use static typing. Consider the following example in C++:

int x = 3;
double y = 3.4;
rand() < RAND_MAX / 2 ? x : x + 1;
rand() < RAND_MAX / 2 ? x : y;

What are the types of the conditional expression? In the first case, both options are of type int, so the result should be of type int. In the second case, however, one option is of type int while the other is of type double. C++ uses a complex set of rules to determine which of the two types can be coerced to the other, and the coercion rules here differ from those in other contexts. The expression is only valid if exactly one of the types can be coerced to the other. In this case, the resulting expression has type double.

Type Inference

Since the type of each expression is not specified in source code, compilers perform type inference to compute their types. Some languages allow programmers to make use of the type-inference facilities of the compiler by allowing types to be elided from declarations if they can be inferred. Many modern statically typed languages allow types to be elided completely in certain contexts.

As an example, we have already seen that Java and C++ allow the return type to be elided from a lambda expression, and that Java also allows the parameter types to be elided:

public static IntPredicate makeGreaterThan(int threshold) {
  return value -> value > threshold;
}

We have also seen that C++ allows the type of a variable to be deduced with the auto keyword:

int x = 3;
auto y = x;    // deduced to have type int
auto &z = x;   // deduced to have type int &

The rules for type deduction in C++ have complex interactions with reference types, as illustrated above. We will not consider them here.

The auto keyword requires that a variable be initialized at declaration, so that the type can be deduced from the initializer. There are cases where this is not possible. Consider the following class template:

template<typename T, typename U>
class Foo {
  T a;
  U b;
  ??? c;   // type of a + b
};

Here, we want the type of Foo::c to be the same as the type of a + b, but without actually initializing it to that value. In fact, C++ prohibits auto from being used with a non-static class member. Instead, C++ provides the decltype keyword that computes the type of an expression:

template<typename T, typename U>
class Foo {
  T a;
  U b;
  decltype(a + b) c;   // type of a + b
};

Control-Flow Analysis

Compilers often perform analysis on the flow of control or data through a program in order to provide early detection of bugs as well as to optimize generated code. Such an analysis is referred to as control-flow or data-flow analysis. Here, we consider a few common examples of control-flow analysis.

Many imperative languages allow variables to be declared without being explicitly initialized. Some languages specify semantics for default initialization. In C and C++, however, variables of primitive type have undefined values upon default initialization, so the behavior of a program that uses such a variable is undefined. Other languages, such as Java, reject programs in which it cannot be proven that a variable has been initialized before being used. The compiler analyzes the source code to determine whether or not a control-flow path exists that may result in the use of a variable without initialization. This analysis is conservative, so that the standard Java compiler rejects the following code:

class Foo {
  public static void main(String[] args) {
    int i;
    if (args.length > 0) {
      i = args.length;
    }
    if (args.length <= 0) {
      i = 0;
    }
    System.out.println(i);
  }
}

Even though it may seem obvious that the body of one of the conditionals must be executed, the compiler is unable to determine that this is the case. Instead, it conservatively assumes that it is possible for neither conditional test to succeed, so that i may be used uninitialized. Thus, the compiler reports an error like the following:

foo.java:10: error: variable i might not have been initialized
    System.out.println(i);
                     ^
1 error

On the other hand, modifying the code as follows enables the compiler to determine that i must be initialized:

class Foo {
  public static void main(String[] args) {
    int i;
    if (args.length > 0) {
      i = args.length;
    } else {
      i = 0;
    }
    System.out.println(i);
  }
}

Here, the compiler can determine that one of the two branches of the conditional must execute, so that i is always initialized before use.

Some C and C++ compilers perform the same analysis and report a warning if a default-initialized variable of primitive type may be used. Java also performs a similar analysis to ensure that final variables are initialized no more than once.

In languages that require a function to explicitly return an object, a program may have control paths that do not ensure that a function encounters a return statement before exiting. Compilers often perform an analysis that is analogous to that of variable initialization in order to ensure that a function reaches a return statement. Consider the following method in Java:

static int bar(int x) {
  if (x > 0) {
    return 1;
  }
  if (x <= 0) {
    return 0;
  }
}

Once again, the compiler cannot guarantee that one of the conditionals will have its body executed, and it reports an error such as the following:

bar.java:9: error: missing return statement
  }
  ^
1 error

An equivalent example in C++ produces a warning in some compilers, such as the following in Clang:

bar.cpp:12:1: warning: control may reach end of non-void function
      [-Wreturn-type]
}
^
1 warning generated.

In some non-obvious cases, the compiler can guarantee that a return must be reached before a function exits. The following example succeeds in both the standard Java compiler and in Clang for equivalent C++ code:

static int baz(int x) {
  while (true) {
    if (x < 0) {
      return 0;
    }
  }
}

Here, the compiler can determine that the only way to exit the loop is through a return, so that the only way to exit the function is by reaching the return statement.

The same analysis can be used to detect code that will never be reached, and depending on the language and compiler, this may be considered an error. For example, the following modification to baz() is rejected by the standard Java compiler:

static int baz(int x) {
  while (true) {
    if (x < 0) {
      return 0;
    }
  }
  return 1;
}

The compiler reports the following error:

baz.java:8: error: unreachable statement
    return 1;
    ^
1 error

In Java, the language explicitly disallows statements that can be proven to be unreachable.

Dynamic Typing

In addition to dynamic binding, languages and implementations often make other uses of dynamic type information, also called runtime type information (RTTI), as well as making it available in some form to programmers.

Many languages provide a mechanism for checking whether or not an object has a specific type at runtime. Depending on the language, the query type may need to be specified at compile time, particularly if the language does not support first-class types, or it may be computed at runtime. For example, the following C++ code checks whether the dynamic type of an object referred to by a base class pointer is of the derived class:

struct A {
  virtual void bar() {
  }
};

struct B : A {
};

void foo(A *a) {
  if (dynamic_cast<B *>(a)) {
    cout << "got a B" << endl;
  } else {
    cout << "not a B" << endl;
  }
}

int main() {
  A a;
  B b;
  foo(&a);
  foo(&b);
}

The dynamic_cast operation attempts to cast an A * to a B *, which will only succeed if the pointed-to object is actually an instance of B. If the cast fails, then it produces a null pointer, which has truth value false. C++ also allows dynamic_cast to be used on references, in which case an exception is thrown upon failure.

In order for dynamic_cast to work, the types involved must define at least one virtual method. This allows an implementation to use vtable pointers, or entries in the vtable itself, to determine the dynamic type of an object. Types that do not have virtual methods do not have vtables, and their instances do not include vtable pointers.

C++ also has the typeid operator, which produces an object that contains information about the type of the given operand. In order to make use of typeid, the <typeinfo> header must be included. The operator works on objects of any type, as well as types themselves, and the result is an instance of std::type_info, which contains basic information about the type. The following is an example:

int main() {
  const type_info &i1 = typeid(int);
  const type_info &i2 = typeid(new A());
  const type_info &i3 = typeid(main);
  cout << i1.name() << " " << i2.name() << " " << i3.name() << endl;
}

The resulting names are implementation dependent. For example, GCC 5.5 produces i P1A FivE when the code above is run.

Java supports the instanceof operator, which determines whether or not an object is an instance of the given type at runtime. Python has the similar isinstance() function, which takes in an object and a type as arguments.

Java also supports an operation similar to typeid in the form of the getClass() method defined on all objects. The result is an instance of Class, which contains extensive information about the class of the object. Similarly, Python has a type() function. This returns the actual type of an object, since types are first-class entities in Python.

In Java, all casts on objects are dynamically checked. Rather than producing a null pointer on failure, Java throws a ClassCastException.

A specific case where Java needs to check the type of an object in its internal implementation is when an item is stored in an array. Originally, Java did not support parametric polymorphism, so the decision was made to support polymorphic functions on arrays by making all arrays whose elements are of object type derive from Object[]. This allowed methods like the following to be defined and called on any array of object type:

static void printAll(Object[] items) {
  for (int i = 0; i < items.length; i++) {
    System.out.println(items[i]);
  }
}

More specifically, Java specifies that A[] is a subtype of B[] if A is a subtype of B.

As an example of where this subtype relation can permit erroneous code, consider the following:

String[] sarray = new String[] { "foo", "bar" };
Object[] oarray = sarray;
oarray[0] = "Hello";
oarray[1] = new Integer(3);
sarray[1].length();

The second line is valid, since a String[] object can be assigned to a variable of type Object[]. The third line is also valid, since a String object can be stored in an Object[]. The fourth line is valid according to the type system, since Integer derives from Object, which can be stored in an element of an Object[] variable. However, Integer does not derive from String, so at runtime, we have an attempt to store an Integer object into an array of dynamic type String[]. This should be prevented, since we could then call a String method on the element as in the fifth line. Thus, Java checks the dynamic types of the array and the item being stored at runtime and throws an ArrayStoreException if they are incompatible.

A better solution to the problem would be to use parametric polymorphism for operations on arrays, rather than making arrays support subtype polymorphism. Unfortunately, parametric polymorphism was introduced much later in Java’s existence, leading to a significant body of code that depends on the subtype polymorphism of arrays.

Generics

Subtype polymorphism relies on subtype relationships and dynamic binding in order to provide the ability of a single piece of code to behave according to the dynamic type of an object. In contrast, parameteric polymorphism allows the same code to operate on different types without relying on either subtype relationships or dynamic binding. Languages that support parametric polymorphism do so in different ways, and we will examine the different strategies here.

Implicit Parametric Polymorphism

Many functional languages in the ML family, including OCaml and Haskell, are statically typed but allow the programmer to elide types from a function. In such a case, the function is implicitly polymorphic, and the compiler will infer the types for each use of the function. For example, the following defines a polymorphic max function in OCaml:

let max x y =
    if x > y then
        x
    else
        y;;

We can then call the function on two values of the same type:

# max 3 4;;
- : int = 4
# max 4.1 3.1;;
- : float = 4.1
# max "Hello" "World";;
- : string = "World"

Explicit Parametric Polymorphism

In other languages, a function or type must be explicitly specified as polymorphic. In C++, the template keyword introduces a polymorphic entity, and the parameters are specified in angle brackets:

template <typename T>
T max(const T &x, const T &y) {
  return x > y ? x : y;
}

While the definition of a parametric function must be explicitly denoted as such, in many languages the use of a parametric function does not normally require an explicit instantiation. Instead, as in implicit parametric polymorphism, the compiler uses type inference to determine the appropriate instantiation. Thus, we can use max() as follows:

max(3, 4); // returns 4
max(4.1, 3.1); // returns 4.1
max("Hello"s, "World"s) // returns "World"s

In the last call, we made use of C++14 string literals to compare std::string s rather than character arrays.

With a single template parameter, the compiler cannot infer the type parameter on a call that uses arguments of different types:

max(3, 4.1); // error

Instead, we can explicitly instantiate max():

max<double>(3, 4.1); // OK

Alternatively, we can modify max() to have separate type parameters for each function parameter. However, with C++11, we also need to make use of type deduction for the return type:

template <typename T, typename U>
auto max(const T &x, const U &y) -> decltype(x > y ? x : y) {
  return x > y ? x : y;
}

As of C++14, the trailing return type can be elided, in which case the return type is deduced from the return statement:

template <typename T, typename U>
auto max(const T &x, const U &y) {
  return x > y ? x : y;
}

Non-Type Parameters

In some languages, a generic parameter need not be a type. In particular, Ada allows generics to be parameterized by values of any type. C++ is more restrictive, allowing a template parameter to be a value of an integral type, enumeration type, lvalue-reference type, pointer type, or pointer-to-member type. The template parameter must be a compile-time constant. A specific example of this is std::array, which is declared similar to the following:

template <typename T, int N>
class array;

We can then use it as follows:

array<double, 5> arr;
arr[3] = 4.1;

Constraints

An entity that supports parametric polymorphism can work with different types, but it is often the case that not every type is suitable for use in that entity. In the case of the max functions above, it does not make sense to call max on values of a type that does not support the > operator.

Depending on the language, the constraints on a polymorphic entity can be implicit or explicit. In the case of implicit constraints, the entity is instantiated for the given type argument, and then the result is checked for correctness. As an example, if we attempt to call max() on streams in C++, we get an error like the following:

foo.cpp:7:12: error: invalid operands to binary expression
      ('const std::__1::basic_istream<char>' and
      'const std::__1::basic_istream<char>')
  return x > y ? x : y;
         ~ ^ ~
foo.cpp:11:5: note: in instantiation of function template
      specialization 'max<std::__1::basic_istream<char> >'
      requested here
  ::max(cin, cin);
    ^

We then get a lengthy list of all the generic overloads of the operator < that could not be instantiated with a basic_istream<char>. The inscrutability of error messages produced by C++ compilers upon instantiation failure is an unavoidable byproduct of deferring type checking until instantiation.

Other languages allow a generic entity to specify explicit constraints on the arguments with which the entity can be instantiated. Java and C#, in particular, support powerful systems of constraints that can restrict a generic for use with derived classes of specific types. The code for a generic entity can then be checked once, assuming that the constraints are satisfied. Then upon instantiating a generic, the type arguments need only be checked against the constraints, resulting in much cleaner error messages than C++.

We will look at the Java system for generics in more detail shortly.

Implementation

Languages and compilers also differ in the implementation of generics at runtime. In languages with strong support for dynamic binding, a common implementation strategy is to only produce a single copy of the code for a generic entity, relying on operations that depend on the type parameter to be dynamically bound to the appropriate implementation. This is the strategy used by Java and ML.

An alternative implementation is to generate separate code for each instantiation of a generic entity, as is done in C++. This approach is more flexible, since it does not require there to be a single piece of generated code that works for any set of type arguments. It is also often more efficient, since it does not rely on dynamic binding. The downside is that it results in larger executables, a problem that is exacerbated by the fact that the compiler needs access to the full source of a generic entity when it is being instantiated. This can lead to multiple copies of the same instantiation being included in the resulting executable.

Java Generics

We now examine Java’s support for generics in more detail, as there are key differences between how Java and C++ implement generics.

In Java, the basic syntax for using a generic is similar to C++. For example, the following uses the generic ArrayList<T> type:

ArrayList<String> strings = new ArrayList<String>();
strings.add("Hello");
strings.add("World");
System.out.println(strings.get(1));

Defining a generic type, in its most basic form, also has syntax that is related to C++, except for the distinct lack of the template keyword:

class Foo<T> {
  private T x;

  public Foo(T x_in) {
    x = x_in;
  }

  public T get() {
    return x;
  }
}

A generic function requires its type parameters to be specified prior to the return type, as the return type may use the type parameter:

static <T> T max(T x, T y) {
  return x.compareTo(y) > 0 ? x : y;
}

Unfortunately, this code will fail to compile, since not all objects support the compareTo() method. By default, Java only allows methods defined on Object to be called from within a generic. The compareTo() method is not defined in Object but is defined in the following interface in the standard library:

interface Comparable<T> {
  int compareTo(T other);
}

Thus, we need to a mechanism for constraining the type parameter of max() be a derived type of Comparable<T>, so that an object of the type parameter can be compared to another object of the same type. We can do this by adding extends Comparable<T> to the type parameter when we introduce it:

static <T extends Comparable<T>> T max(T x, T y) {
  return x.compareTo(y) > 0 ? x : y;
}

We can modify the Foo class as follows to implement the Comparable<Foo<T>> interface:

class Foo<T> implements Comparable<Foo<T>> {
  private T x;

  public Foo(T x_in) {
    x = x_in;
  }

  public T get() {
    return x;
  }

  public int compareTo(Foo<T> other) {
    return x.compareTo(other.x);
  }
}

To compare a Foo<T> to another Foo<T>, we in turn compare their respective x fields with another call to compareTo(). Again, we run into the problem that the type parameter T, which is the type of x, may not implement the compareTo() method. So we have to specify the constraint here as well that T be derived from Comparable<T>:

class Foo<T extends Comparable<T>> implements Comparable<Foo<T>> {
  private T x;

  public Foo(T x_in) {
    x = x_in;
  }

  public T get() {
    return x;
  }

  public int compareTo(Foo<T> other) {
    return x.compareTo(other.x);
  }
}

We can now use max() with instantiations of Foo:

Foo<String> f1 = new Foo<String>("Hello");
Foo<String> f2 = new Foo<String>("World");
System.out.println(max(f1, f2).get());     // prints World

A final problem is that an instance of a class may be comparable to an instance of a base class. Consider the following classes:

class Rectangle implements Comparable<Rectangle> {
  private int side1, side2;

  public Rectangle(int s1_in, int s2_in) {
    side1 = s1_in;
    side2 = s2_in;
  }

  public int area() {
    return side1 * side2;
  }

  public int compareTo(Rectangle other) {
    return area() - other.area();
  }
}

class Square extends Rectangle {
  public Square(int side) {
    super(side, side);
  }
}

We can now try to use the Foo generic type with Square, as in:

public static void main(String[] args) {
  Foo<Square> f1 = new Foo<Square>(new Square(3));
  Foo<Square> f2 = new Foo<Square>(new Square(4));
  System.out.println(f1.compareTo(f2));
}

Unfortunately, we get errors like the following:

foo.java:36: error: type argument Square is not within bounds
  of type-variable T
    Foo<Square> f1 = new Foo<Square>(new Square(3));
        ^
  where T is a type-variable:
    T extends Comparable<T> declared in class Foo

The problem is that Square derives from Comparable<Rectangle>, not Comparable<Square> as required by the type parameter. However, semantically it should not be a problem, since if a Square can be compared to another Rectangle, it can also be compared to another Square. The solution is to modify the type constraint to allow a type argument as long as it is comparable to some superclass of the type:

class Foo<T extends Comparable<? super T>>
  implements Comparable<Foo<T>> {
  ...
}

The syntax Comparable<? super T> specifies that the type argument of Comparable can be any type, as long as it is a supertype of T. Thus, Square satisfies the constraint, since it derives from Comparable<Rectangle>, and Rectangle is a superclass of Square.

Java implements generics using type erasure. Once a generic has been checked, using any constraints it specifies, and once all uses have been checked, the generic is replaced with a version that is no longer parameterized, usually with the type parameters replaced by Object. This prevents a generic from being used directly with primitive types, since they do not derive from Object. However, Java does allow primitives to be implicitly converted to representations that derive from Object, at significant efficiency costs.

Curiously Recurring Template Pattern

In Java, the pattern of a type T deriving from a generic instantiated with T is quite common, as in the Rectangle class above. This pattern also exists in C++ templates, and it is known as the curiously recurring template pattern (CRTP).

template<class T>
class GenericBase {
  ...
};

class Derived : public GenericBase<Derived> {
  ...
};

We can use such a pattern to construct a mixin, as in Ruby’s Comparable mentioned in Types of Inheritance:

template<class T>
class Comparable {
public:
  bool operator<(const T &rhs) const {
    return compare(rhs) < 0;
  }

  bool operator<=(const T &rhs) const {
    return compare(rhs) <= 0;
  }

  ...

  virtual int compare(const T &other) const = 0;
};

The Comparable class template defines the comparison operators in terms of a compare() method, which the derived class must implement. We can thus implement a counter class that inherits the comparison operators:

class Counter : public Comparable<Counter> {
  int count = 0;

public:
  void increment() {
    ++count;
  }

  void decrement() {
    --count;
  }

  int get_count() const {
    return count;
  }

  virtual int compare(const Counter &other) const override {
    return count - other.count;
  }
};

While the code above works, a major drawback of the implementation is that it requires dynamic binding, incurring the cost of a vtable pointer in every Counter object as well as a vtable lookup for each application of a comparison operator.

Surprisingly, we can actually eliminate dynamic binding by adding an implicit constraint to the Comparable class template: an instance of Comparable<T> must also be an instance of T. For example, a Counter object is an instance of Comparable<Counter>, but of course it is also an instance of Counter. With this constraint, we can perform an unchecked type cast of a Comparable<T> * down to T *:

template<class T>
class Comparable {
public:
  bool operator<(const T &rhs) const {
    return static_cast<const T *>(this)->compare(rhs) < 0;
  }

  ...
};

With the type cast, we no longer need to define compare() as a pure virtual method in Comparable. It need only exist in T, and it may be defined as a non-virtual function:

class Counter : public Comparable<Counter> {
  int count = 0;

public:
  ...

  int compare(const Counter &other) const {
    return count - other.count;
  }
};

The end result is polymorphism without dynamic binding, and it is known as static polymorphism[2] or simulated dynamic binding. The pattern is widely used in Microsoft’s Active Template Library (ATL) and Windows Template Library (WTL) for development on Windows.

Duck Typing

Languages that do not have static typing are often implicitly polymorphic. Type information is not available at compile time, so a function is usable with values of any type that supports the required operations. This is called duck typing: it doesn’t matter what the type of the value actually is; as long as it looks like a duck and quacks like a duck, it is considered for all intents and purposes a duck.

As an example, the following is a definition of max() in Python:

def max(x, y):
    return x if x > y else y

The function will work at runtime on any types that support the special __gt__ method, which is called by the > comparison.

A downside of duck typing is that whether or not a type is considered to support an operation is based solely on the name of the operation, which may not have the same semantic meaning in different contexts. For example, a run() method on an Athlete object may tell the athlete to start running in a marathon, while a run() method on a Thread object may tell it to start executing some code. This can lead to unexpected behavior and confusing errors in duck-typed code that calls run().

Modules and Namespaces

An abstract data type (ADT) defines an abstraction for a single type. Some abstractions, however, consist of not just a single type, but a collection of interdependent types, variables, and other entities. Such a collection of items is a module, and the modularization of a system is a means of making its maintenance more manageable.

Many languages provide mechanisms for organizing items into modules. In some languages, the mechanism is closely tied to that used for separate compilation, such that each module is compiled independently and later linked together with other modules. In other languages, the mechanisms for modules and separate compilation are independent.

Translation Units

A translation unit or compilation unit is the unit of compilation in languages that support separate compilation. Often, it consists of a single source file. In languages such as C and C++ that enable other files to be included with a preprocessor directive, a translation unit consists of a source file and all the files that it recursively includes.

In order to support separate compilation, a translation unit need only know basic information about entities in other translation units. For example, in C++, only declarations of external entities that are used need be known [3]. For a variable, a declaration provides the name and type, and for functions, the name, return type, and parameter type. For classes, in order to be able to access members, the class declaration with its member declarations needs to be available, though actual definitions of member functions do not. Normally, this is accomplished by writing declarations in a header file and then including the header file in any translation unit that needs access to those declarations. The definitions of variables, functions, and member functions are written in a separate source file, which will usually be compiled as its own translation unit.

As an example, the following may be placed in the header file Triangle.hpp to provide the declarations for a Triangle ADT:

class Triangle {
  double a, b, c;
public:
  Triangle();
  Triangle(double, double, double);
  double area() const;
  double perimeter() const;
  void scale(double s);
};

Then the definitions would be placed in a Triangle.cpp file:

#include "Triangle.hpp"

Triangle::Triangle()
  : Triangle(1, 1, 1) { }

Triangle::Triangle(double a_in, double b_in, double c_in)
  : a(a_in), b(b_in), c(c_in) { }

double Triangle::area() const {
  return a * b * c;
}

double Triangle::perimeter() const {
  return a + b + c;
}

void Triangle::scale(double s) {
  a *= s;
  b *= s;
  c *= s;
}

The #include directive pulls the code from Triangle.hpp into Triangle.cpp, making the Triangle declarations available to the latter.

In other languages, including Java and C#, there is no notion of a separate header file, and all declarations must also be definitions. Instead, the compiler automatically extracts the declaration information from a source file when needed by other translation units.

Modules, Packages, and Namespaces

Languages also specify units of organization for names in a program. This allows the same name to be used in different units without resulting in a conflict. In many cases, the unit of organization is at the granularity of a source file, while in other languages, an organizational unit can span multiple source files.

In Python, the first unit of organization is a source file, which is called a module in Python terminology. A module is associated with a scope in which the names defined in the module reside. In order to use names from another module, the external module, or names from within it, must be explicitly imported into the current scope. The import statement does so, and it can be located at any scope. Consider the following example:

from math import sqrt

def quadratic_formula(a, b, c):
    disc = sqrt(b * b - 4 * a * c)
    return (-b + disc) / (2 * a), (-b - disc) / (2 * a)

def main():
    import sys
    if len(sys.argv) < 4:
        print('Usage: {0} a b c'.format(sys.argv[0]))
    else:
        print(quadratic_formula(int(sys.argv[1]),
                                int(sys.argv[2]),
                                int(sys.argv[3])))

if __name__ == '__main__':
    main()

In the code above, the import statement in the first line directly imports the sqrt name from the math module into the scope of the current module. It does not, however, import the math name itself. In the first line of main(), the name of the sys module is imported into the local scope of main(). The standard dot syntax can be used to refer to a name nested inside of sys.

Python also allows a second level of organization in the form of a package, which is a collection of modules. For example, if the code above were in a module named quadratic, we might want to organize it with other mathematical formulas in a package named formulas. Defining a file __init__.py within a directory enables the modules in that directory to constitute a package, with the directory name as the name of the package. Packages can then further have subpackages in the form of subdirectories with their own __init__.py files.

The following is an example of how a sound module can be organized in Python:

sound/                          Top-level package
      __init__.py               Initialize the sound package
      formats/                  Subpackage for file format conversions
              __init__.py
              wavread.py
              wavwrite.py
              aiffread.py
              aiffwrite.py
              auread.py
              auwrite.py
              ...
      effects/                  Subpackage for sound effects
              __init__.py
              echo.py
              surround.py
              reverse.py
              ...
      filters/                  Subpackage for filters
              __init__.py
              equalizer.py
              vocoder.py
              karaoke.py
              ...

Java follows a similar organizational scheme as Python. The first unit of organization is a class, since all code in Java must be contained within a class. Multiple classes may be contained within the same translation unit, but a translation unit does not constitute a scope on its own. (If a class is to be used outside a translation unit, however, it should be located in its own file in order to make it possible for the compiler to find its source when it is used.) A source file may include a package directive in order to place its code within the context of the specified package:

package formulas

public class Quadratic {
  ...
}

Packages can be nested, as in Python.

Also like Python, Java has import statements in order to import names into the local scope. Unlike Python, however, an unimported name can be used by giving it full qualification, including the sequence of packages that it is a part of:

java.util.Vector vec = new java.util.Vector();

Import statements in Java must appear at the top of a file, after any package declaration but before any class definition. A single member can be imported from a package, or all of the package’s contents can be imported:

import java.util.Vector; // import just one member
import java.util.*;      // import all members

Java also allows static methods and constants to be imported from a class with the static import statement:

import static java.lang.System.out;

public class Foo {
  public static void main(String[] args) {
    out.println("Hello world!");
  }
}

C++ has the concept of namespaces rather than modules or packages. A namespace defines a scope in which names reside, and an entity can be defined within a namespace as follows:

namespace foo {

  struct A {
  };

  int x;
}

namespace foo {

  struct B : A {
  };

}

As demonstrated above, multiple entities can be defined within a single namespace block, and multiple namespace blocks can define entities for the same namespace. Namespaces can also be nested.

In order to access a namespace member from an external context, the scope-resolution operator is required:

foo::A *a = new foo::A;

C++ allows individual names to be imported from a namespace into the current scope with a using declaration:

using foo::A;

Alternatively, all of the names declared within a namespace may be imported as follows:

using namespace foo;

This latter form should be used with caution, as it significantly increases the likelihood of inadvertent name clashes.

An entity defined outside of a namespace is actually within the global namespace, and it can be referred to with the scope-resolution operator by including nothing on the left-hand side:

int bar();

void baz() {
  std::cout << ::bar() << std::endl;
}

Java similarly places code that is lacking a package specifier into the anonymous package.

C# combines the concept of Python’s modules, which it calls assemblies, with namespaces as in C++.

Linkage

C does not have namespaces, so it uses an alternate mechanism to avoid name conflicts between translation units. (C++ also includes this, since it is mostly backwards compatible with C.) A programmer can specify a linkage for a function or variable, which determines whether or not the item is visible outside of the translation unit. The keyword static, when used on a function or variable at global scope, specifies that the given item has internal linkage, meaning that it is not available outside of the translation unit. This is crucial when the same name may be defined within different translation units, as it avoids a conflict at the link stage. In particular, global variables and functions that are not just declared but also defined in a header file should almost always be given internal linkage, since a header file is likely to be included from multiple translation units.

A global function or non-const variable has external linkage if it is missing the static specifier. This means that the name will be accessible from other translation units. A variable or function with external linkage must have exactly one definition between the translation units in a program. Otherwise, a conflict arises between the multiple definitions, and a linker error will result. For a function, the distinction between a simple declaration and a definition is clear, since the latter provides a function body. For a variable, however, a declaration is generally also a definition, since a missing initializer implies default initialization. The programmer must explicitly state that a declaration of a global variable is not a definition using the extern specifier:

extern int count; // just a declaration
int count;        // also a definition

A const global variable has internal linkage by default, and the extern keyword must be present to give it external linkage instead. An initialization can be provided, making a declaration of such a variable also a definition:

extern const int SIZE;      // just a declaration
extern const int SIZE = 10; // also a definition

Information Hiding

Many languages provide a mechanism for information hiding at the granularity of modules or packages. In Java, for example, a class that is declared without the public keyword is only available to other classes within the same package. In C and C++, the standard method of information hiding is to avoid declaring internal entities in a header file, but to declare them within a .c or .cpp file, and in the case of variables and functions, declare them with internal linkage.

As mentioned above, in order to use the members of a class in C++, the class definition itself must be available in the current translation unit. However, access to internal members of a class can be restricted using the private or protected specifiers.

C, on the other hand, does not provide a means of declaring struct members private. However, there is a common pattern of preventing direct access to struct members by providing only the declaration of a struct, without its definition, in the header file. As an example, the following defines the interface for a stack ADT:

typedef struct list *stack;
stack stack_make();
void stack_push(stack s, int i);
int stack_top(stack s);
void stack_pop(stack s);
void stack_free(stack s);

Here, no definition of the list struct is provided, making it an opaque type. This prevents another translation unit from creating a list object, since it can’t event tell what the size of the object will be, or accessing its members directly. We can then write the definitions for the stack ADT in its own .c file:

typedef struct node {
  int datum;
  struct node *next;
} node;

struct list {
  node *first;
};

stack stack_make() {
  stack s = (stack) malloc(sizeof(struct list));
  s->first = NULL;
  return s;
}

void stack_push(stack s, int i) {
  node *new_node = (node *) malloc(sizeof(node));
  new_node->datum = i;
  new_node->next = s->first;
  s->first = new_node;
}

...

Another .c file can then make use of the stack, without being able to directly access internal details, as follows:

#include "stack.h"

int main(int argc, char **argv) {
  stack s = stack_make();
  stack_push(s, 3);
  stack_push(s, 4);
  printf("%d\n", stack_top(s));
  stack_pop(s);
  printf("%d\n", stack_top(s));
  stack_free(s);
}

Initialization

In a program with code organized among different modules or translation units, an important consideration is when the code that initializes a module is executed. Interdependencies between modules can lead to bugs due to the semantics of initialization, and there are cases where the only solution is to reorganize the structure of a program.

In Python, the code in a module is executed when it is first imported. Once a module has been imported, any subsequent imports of the module will not cause its code to be re-executed. However, it is possible to construct circular dependencies between modules that result in errors or unexpected behavior. Consider the following, located in module foo:

import bar

def func1():
    return bar.func3()

def func2():
    return 2

print(func1())

Assume that the following is located in module bar:

import foo

def func3():
    return foo.func2()

If we then run module foo from the command line, the import statement will cause the code in bar to be executed. The code in bar has as its first statement an import of foo. This is the first import of foo from bar, so the code for foo will execute. It starts with import bar; however, this is now the second import of bar into foo, so it will not have any effect. Then when func1() is called, the definition for func3() in bar has not yet been executed, so we will get an error:

Traceback (most recent call last):
  File "foo.py", line 1, in <module>
    import bar
  File "bar.py", line 1, in <module>
    import foo
  File "foo.py", line 9, in <module>
    print(func1())
  File "foo.py", line 4, in func1
    return bar.func3()
AttributeError: module 'bar' has no attribute 'func3'

One way to fix this is to delay the import of foo into bar until func3() is called:

def func3():
    import foo
    return foo.func2()

However, this still causes the code in foo to execute twice:

$ python3 foo.py
2
2

A better solution is to move func2() from foo into its own module, and then to import that module from both foo and bar.

In Java, the static initialization of a class occurs when it is first used, which includes creating an instance of the class or accessing a static member. Thus, the order of initialization depends on the dynamic execution of a program, and a programmer generally should not rely on a specific order of initialization between different classes.

In C++, initialization follows a multi-step process. First is what C++ calls static initialization, which initializes compile-time constants to their respective values and other variables with static storage duration to zero. Then is dynamic initialization, which runs the specified initialization for static-duration variables. In general, variables are initialized in program order within a translation unit, with some exceptions. However, the order of initialization between translation units is unspecified, and in fact may be delayed until the first time a translation unit is used. The end result is that a programmer should avoid any assumption that any other translation unit has been initialized when writing initialization code for a given translation unit.