Data Structures and Algorithms with Object-Oriented Design Patterns in Python

Abstract Data Types

An object in a programming language such as C++ , Java , and Python , is an abstraction. The abstraction comprises a number of attributes --name , address , value , lifetime , scope , type , and size . Each attribute has an associated value. For example, if we create an integer object in Python, x = int(5), we say that the name attribute has value ``x'' and that the type attribute has value ``int''.

Unfortunately, the terminology can be somewhat confusing: The word ``value'' has two different meanings--in one instance it denotes one of the attributes and in the other it denotes the quantity assigned to an attribute. For example, after the statement x = int(5), the value attribute of the object named x has the value five.

The name of an object is the textual label used to refer to that object in the text of the source program. The address of an object denotes is location in memory. The value attribute is the quantity which that object represents. The lifetime of an object is the interval of time during the execution of the program in which the object is said to exist. The scope of an object is the set of statements in the text of the source program in which the object is said to be visible . The type of an object denotes the set of values which can be assigned to the value attribute and the set of operations which can be performed on the object. Finally, the size attribute denotes the amount of storage required to represent the object.

The process of assigning a value to an attribute is called binding . When a value is assigned to an attribute, that attribute is said to be bound to the value. Depending on the semantics of the programming language, and on the attribute in question, the binding may be done statically by the compiler or dynamically at run-time. For example, in Python the type of an object is usually determined at compile time--static binding . On the other hand, the value of an object is usually not determined until run-time--dynamic binding .

In this chapter we are concerned primarily with the type attribute of an object. The type of an object specifies two sets:

a set of values; and,
a set of operations.

For example, when we create an object, say x, of type int, we know that x can represent an integer in the range

and that we can perform operations using x such as addition, subtraction, multiplication, and division.

The type int is an abstract data type in the sense that we can think about the qualities of an int apart from any real thing having that quality. In other words, we don't need to know how ints are represented nor how the operations are implemented to be able to be able to use them or reason about them.

In designing object-oriented programs, one of the primary concerns of the programmer is to develop an appropriate collection of abstractions for the application at hand, and then to define suitable abstract data types to represent those abstractions. In so doing, the programmer must be conscious of the fact that defining an abstract data type requires the specification of both a set of values and a set of operations on those values.

Indeed, it has been only since the advent of the so-called object-oriented programming languages that the we see programming languages which provide the necessary constructs to properly declare abstract data types. For example, in Python, the class construct is the means by which both a set of values and an associated set of operations is declared. Compare this with the struct construct of C or Pascal's record , which only allow the specification of a set of values!