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:
We could then obtain the first item by applying the resulting function to \(true\), and the second item by applying it to \(false\):
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.
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 26 illustrates this layout:
Figure 26 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.
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 27.
Figure 27 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 28.
Figure 28 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:
Look up the member (e.g.
bin the case ofaptr->b()) in the static type of the receiver, performing function-overload resolution if necessary to determine which method is being called.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 toA::fwould be generated sinceA::f, the result of the lookup, is non-virtual.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 isA::b, which is the second entry in the vtable forA. 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 29 illustrates the two views.
Figure 29 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 30.
Figure 30 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:
struct A {
int x;
};
struct B : A {
};
struct C : A {
};
struct D : B, C {
};
In the example above, D derives from A twice, once through
B and once through C. Should an object of type D contain a
single copy of the fields inherited from A, 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 A
can be specified using virtual inheritance:
struct A {
int x;
};
struct B : virtual A {
};
struct C : virtual A {
};
struct D : B, C {
};
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.
As this example demonstrates, the intermediate classes B and C
are the ones that must declare A as a virtual base class, even
though it is the class D 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.