Object-Oriented Concepts

4 Object-Oriented Concepts

 

The previous sections already introduce some ``object-oriented'' concepts. However, they were applied in an procedural environment or in a verbal manner. In this section we investigate these concepts in more detail and give them names as used in existing object-oriented programming languages.

4.1 Implementation of Abstract Data Types

The last section introduces abstract data types (ADTs) as an abstract view to define properties of a set of entities. Object-oriented programming languages must allow to implement these types. Consequently, once an ADT is implemented we have a particular representation of it available.

Consider again the ADT Integer. Programming languages such as Pascal, C, Modula-2 and others already offer an implementation for it. Sometimes it is called intor integer. Once you've created a variable of this type you can use its provided operations. For example, you can add two integers:

  int i, j, k;    /* Define three integers */

  i = 1;          /* Assign 1 to integer i */
  j = 2;          /* Assign 2 to integer j */
  k = i + j;      /* Assign the sum of i and j to k */

Let's play with the above code fragment and outline the relationship to the ADT Integer. The first line defines three instances i, j and k of type Integer. Consequently, for each instance the special operation constructor should be called. In our example, this is internally done by the compiler. The compiler reserves memory to hold the value of an integer and ``binds'' the corresponding name to it. If you refer to i you actually refer to this memory area which was ``constructed'' by the definition of i. Optionally, compilers might choose to initialize the memory, for example, they might set it to 0 (zero).

The next line

  i = 1;

sets the value of i to be 1. Therefore we can describe this line with help of the ADT notation as follows:

Perform operation set with argument 1 on the Integer instance i. This is written as follows: i.set(1).

We now have a representation at two levels. The first level is the ADT level where we express everything that is done to an instance of this ADT by the invocation of defined operations. At this level, pre- and postconditions are used to describe what actually happens. In the following example, these conditions are enclosed in curly brackets.

{ Precondition: i = n where n is any Integer }
i.set(1)
{ Postcondition: i = 1 }
Don't forget that we currently talk about the ADT level! Consequently, the conditions are mathematical conditions.

The second level is the implementation level, where an actual representation is chosen for the operation. In C the equal sign ``='' implements the set() operation. However, in Pascal the following representation was chosen:

  i := 1;

In either case, the ADT operation set is implemented.

Let's stress these levels a little bit further and have a look at the line

  k = i + j;

Obviously, ``+'' was chosen to implement the add operation. We could read the part ``i + j'' as ``add the value of j to the value of i'', thus at the ADT level this results in

{ Precondition: Let i = n1 and j = n2 with n1, n2 particular Integers }
i.add(j)
{ Postcondition: i = n1 and j = n2 }
The postcondition ensures that i and j do not change their values. Please recall the specification of add. It says that a new Integer is created the value of which is the sum. Consequently, we must provide a mechanism to access this new instance. We do this with the set operation applied on instance k:

{ Precondition: Let k = n where n is any Integer }
k.set(i.add(j))
{ Postcondition: k = i + j }
As you can see, some programming languages choose a representation which almost equals the mathematical formulation used in the pre- and postconditions. This makes it sometimes difficult to not mix up both levels.

4.2 Class

  A class is an actual representation of an ADT. It therefore provides implementation details for the data structure used and operations. We play with the ADTInteger and design our own class for it:

  class Integer {
  attributes:
    int i

  methods:
    setValue(int n)
    Integer addValue(Integer j)
  }

In the example above as well as in examples which follow we use a notation which is not programming language specific. In this notation class {...} denotes the definition of a class. Enclosed in the curly brackets are two sections attributes: and methods: which define the implementation of the data structure and operations of the corresponding ADT. Again we distinguish the two levels with different terms: At the implementation level we speak of ``attributes'' which are elements of the data structure at the ADT level. The same applies to ``methods'' which are the implementation of the ADT operations.

In our example, the data structure consists of only one element: a signed sequence of digits. The corresponding attribute is an ordinary integer of a programming language. We only define two methods setValue() and addValue() representing the two operations set and add.

Definition (Class) A class is the implementation of an abstract data type (ADT). It defines attributes and methods which implement the data structure and operations of the ADT, respectively. Instances of classes are called objects. Consequently, classes define properties and behaviour of sets of objects.

4.3 Object

  Recall the employee example of chapter 3. We have talked of instances of abstract employees. These instances are actual ``examples'' of an abstract employee, hence, they contain actual values to represent a particular employee. We call these instances objects.

Objects are uniquely identifiable by a name. Therefore you could have two distinguishable objects with the same set of values. This is similar to ``traditional'' programming languages where you could have, say two integers i and j both of which equal to ``2''. Please notice the use of ``i'' and ``j'' in the last sentence to name the two integers. We refer to the set of values at a particular time as the state of the object.

Definition (Object) An object is an instance of a class. It can be uniquely identified by its name and it defines a state which is represented by the values of its attributes at a particular time.

The state of the object changes according to the methods which are applied to it. We refer to these possible sequence of state changes as the behaviour of the object:

Definition (Behaviour) The behaviour of an object is defined by the set of methods which can be applied on it.

We now have two main concepts of object-orientation introduced, class and object. Object-oriented programming is therefore the implementation of abstract data types or, in more simple words, the writing of classes. At runtime instances of these classes, the objects, achieve the goal of the program by changing their states. Consequently, you can think of your running program as a collection of objects. The question arises of how these objects interact? We therefore introduce the concept of a message in the next section.

4.4 Message

  A running program is a pool of objects where objects are created, destroyed and interacting. This interacting is based on messages which are sent from one object to another asking the recipient to apply a method on itself. To give you an understanding of this communication, let's come back to the class Integer presented in section 4.2. In our pseudo programming language we could create new objects and invoke methods on them. For example, we could use

  Integer i;     /* Define a new integer object */
  i.setValue(1); /* Set its value to 1 */

to express the fact, that the integer object i should set its value to 1. This is the message ``Apply method setValue with argument 1 on yourself.'' sent to object i. We notate the sending of a message with ``.''. This notation is also used in C++; other object-oriented languages might use other notations, for example ``-''.

Sending a message asking an object to apply a method is similar to a procedure call in ``traditional'' programming languages. However, in object-orientation there is a view of autonomous objects which communicate with each other by exchanging messages. Objects react when they receive messages by applying methods on themselves. They also may deny the execution of a method, for example if the calling object is not allowed to execute the requested method.

In our example, the message and the method which should be applied once the message is received have the same name: We send ``setValue with argument 1'' to object i which applies ``setValue(1)''.

Definition (Message) A message is a request to an object to invoke one of its methods. A message therefore contains

• the name of the method and
• the arguments of the method.

Consequently, invocation of a method is just a reaction caused by receipt of a message. This is only possible, if the method is actually known to the object.

Definition (Method) A method is associated with a class. An object invokes a method as a reaction to receipt of a message.

4.5 Summary

To view a program as a collection of interacting objects is a fundamental principle in object-oriented programming. Objects in this collection react upon receipt of messages, changing their state according to invocation of methods which might cause other messages sent to other objects. This is illustrated in Figure 4.1.

 

Figure 4.1:  A program consisting of four objects.

In this figure, the program consists of only four objects. These objects send messages to each other, as indicated by the arrowed lines. Note that the third object sends itself a message.

How does this view help us developing software? To answer this question let's recall how we have developed software for procedural programming languages. The first step was to divide the problem into smaller manageable pieces. Typically these pieces were oriented to the procedures which were taken place to solve the problem, rather than the involved data.

As an example consider your computer. Especially, how a character appears on the screen when you type a key. In a procedural environment you write down the several steps necessary to bring a character on the screen:

1.

wait, until a key is pressed.

2.

get key value

3.

write key value at current cursor position

4.

advance cursor position

You do not distinguish entities with well-defined properties and well-known behaviour. In an object-oriented environment you would distinguish the interacting objects key and screen. Once a key receive a message that it should change its state to be pressed, its corresponding object sends a message to the screen object. This message requests the screen object to display the associated key value.

4.6 Exercises

1.

Class.

(a)

What distinguishes a class from an ADT?

(b)

Design a class for the ADT Complex. What representations do you choose for the ADT operations? Why?

2.

Interacting objects. Have a look to your tasks of your day life. Choose one which does not involve too many steps (for example, watching TV, cooking a meal, etc.). Describe this task in procedural and object-oriented form. Try to begin viewing the world to consist of objects.

3.

Object view. Regarding the last exercise, what problems do you encounter?

4.

Messages.

(a)

Why do we talk about ``messages'' rather than ``procedure calls''?

(b)

Name a few messages which make sense in the Internet environment. (You must therefore identify objects.)

(c)

Why makes the term ``message'' more sense in the environment of the last exercise, than the term ``procedure call''?

Object Oriented Concepts

4 Object-Oriented Concepts

The previous sections already introduce some ``object-oriented'' concepts. However, they were applied in an procedural environment or in a verbal manner. In this section we investigate these concepts in more detail and give them names as used in existing object-oriented programming languages.

4.1 Implementation of Abstract Data Types

The last section introduces abstract data types (ADTs) as an abstract view to define properties of a set of entities. Object-oriented programming languages must allow to implement these types. Consequently, once an ADT is implemented we have a particular representation of it available.

Consider again the ADT Integer. Programming languages such as Pascal, C, Modula-2 and others already offer an implementation for it. Sometimes it is called intor integer. Once you've created a variable of this type you can use its provided operations. For example, you can add two integers:

  int i, j, k;    /* Define three integers */

  i = 1;          /* Assign 1 to integer i */
  j = 2;          /* Assign 2 to integer j */
  k = i + j;      /* Assign the sum of i and j to k */

Let's play with the above code fragment and outline the relationship to the ADT Integer. The first line defines three instances i, j and k of type Integer. Consequently, for each instance the special operation constructor should be called. In our example, this is internally done by the compiler. The compiler reserves memory to hold the value of an integer and ``binds'' the corresponding name to it. If you refer to i you actually refer to this memory area which was ``constructed'' by the definition of i. Optionally, compilers might choose to initialize the memory, for example, they might set it to 0 (zero).

The next line

  i = 1;

sets the value of i to be 1. Therefore we can describe this line with help of the ADT notation as follows:

Perform operation set with argument 1 on the Integer instance i. This is written as follows: i.set(1).

We now have a representation at two levels. The first level is the ADT level where we express everything that is done to an instance of this ADT by the invocation of defined operations. At this level, pre- and postconditions are used to describe what actually happens. In the following example, these conditions are enclosed in curly brackets.

{ Precondition: i = n where n is any Integer }
i.set(1)
{ Postcondition: i = 1 }
Don't forget that we currently talk about the ADT level! Consequently, the conditions are mathematical conditions.

The second level is the implementation level, where an actual representation is chosen for the operation. In C the equal sign ``='' implements the set() operation. However, in Pascal the following representation was chosen:

  i := 1;

In either case, the ADT operation set is implemented.

Let's stress these levels a little bit further and have a look at the line

  k = i + j;

Obviously, ``+'' was chosen to implement the add operation. We could read the part ``i + j'' as ``add the value of j to the value of i'', thus at the ADT level this results in

{ Precondition: Let i = n1 and j = n2 with n1, n2 particular Integers }
i.add(j)
{ Postcondition: i = n1 and j = n2 }
The postcondition ensures that i and j do not change their values. Please recall the specification of add. It says that a new Integer is created the value of which is the sum. Consequently, we must provide a mechanism to access this new instance. We do this with the set operation applied on instance k:

{ Precondition: Let k = n where n is any Integer }
k.set(i.add(j))
{ Postcondition: k = i + j }
As you can see, some programming languages choose a representation which almost equals the mathematical formulation used in the pre- and postconditions. This makes it sometimes difficult to not mix up both levels.

4.2 Class

  A class is an actual representation of an ADT. It therefore provides implementation details for the data structure used and operations. We play with the ADTInteger and design our own class for it:

  class Integer {
  attributes:
    int i

  methods:
    setValue(int n)
    Integer addValue(Integer j)
  }

In the example above as well as in examples which follow we use a notation which is not programming language specific. In this notation class {...} denotes the definition of a class. Enclosed in the curly brackets are two sections attributes: and methods: which define the implementation of the data structure and operations of the corresponding ADT. Again we distinguish the two levels with different terms: At the implementation level we speak of ``attributes'' which are elements of the data structure at the ADT level. The same applies to ``methods'' which are the implementation of the ADT operations.

In our example, the data structure consists of only one element: a signed sequence of digits. The corresponding attribute is an ordinary integer of a programming language. We only define two methods setValue() and addValue() representing the two operations set and add.

Definition (Class) A class is the implementation of an abstract data type (ADT). It defines attributes and methods which implement the data structure and operations of the ADT, respectively. Instances of classes are called objects. Consequently, classes define properties and behaviour of sets of objects.

4.3 Object

  Recall the employee example of chapter 3. We have talked of instances of abstract employees. These instances are actual ``examples'' of an abstract employee, hence, they contain actual values to represent a particular employee. We call these instances objects.

Objects are uniquely identifiable by a name. Therefore you could have two distinguishable objects with the same set of values. This is similar to ``traditional'' programming languages where you could have, say two integers i and j both of which equal to ``2''. Please notice the use of ``i'' and ``j'' in the last sentence to name the two integers. We refer to the set of values at a particular time as the state of the object.

Definition (Object) An object is an instance of a class. It can be uniquely identified by its name and it defines a state which is represented by the values of its attributes at a particular time.

The state of the object changes according to the methods which are applied to it. We refer to these possible sequence of state changes as the behaviour of the object:

Definition (Behaviour) The behaviour of an object is defined by the set of methods which can be applied on it.

We now have two main concepts of object-orientation introduced, class and object. Object-oriented programming is therefore the implementation of abstract data types or, in more simple words, the writing of classes. At runtime instances of these classes, the objects, achieve the goal of the program by changing their states. Consequently, you can think of your running program as a collection of objects. The question arises of how these objects interact? We therefore introduce the concept of a message in the next section.

4.4 Message

  A running program is a pool of objects where objects are created, destroyed and interacting. This interacting is based on messages which are sent from one object to another asking the recipient to apply a method on itself. To give you an understanding of this communication, let's come back to the class Integer presented in section 4.2. In our pseudo programming language we could create new objects and invoke methods on them. For example, we could use

  Integer i;     /* Define a new integer object */
  i.setValue(1); /* Set its value to 1 */

to express the fact, that the integer object i should set its value to 1. This is the message ``Apply method setValue with argument 1 on yourself.'' sent to object i. We notate the sending of a message with ``.''. This notation is also used in C++; other object-oriented languages might use other notations, for example ``-''.

Sending a message asking an object to apply a method is similar to a procedure call in ``traditional'' programming languages. However, in object-orientation there is a view of autonomous objects which communicate with each other by exchanging messages. Objects react when they receive messages by applying methods on themselves. They also may deny the execution of a method, for example if the calling object is not allowed to execute the requested method.

In our example, the message and the method which should be applied once the message is received have the same name: We send ``setValue with argument 1'' to object i which applies ``setValue(1)''.

Definition (Message) A message is a request to an object to invoke one of its methods. A message therefore contains

• the name of the method and
• the arguments of the method.

Consequently, invocation of a method is just a reaction caused by receipt of a message. This is only possible, if the method is actually known to the object.

Definition (Method) A method is associated with a class. An object invokes a method as a reaction to receipt of a message.

4.5 Summary

To view a program as a collection of interacting objects is a fundamental principle in object-oriented programming. Objects in this collection react upon receipt of messages, changing their state according to invocation of methods which might cause other messages sent to other objects. This is illustrated in Figure 4.1.

 

Figure 4.1:  A program consisting of four objects.

In this figure, the program consists of only four objects. These objects send messages to each other, as indicated by the arrowed lines. Note that the third object sends itself a message.

How does this view help us developing software? To answer this question let's recall how we have developed software for procedural programming languages. The first step was to divide the problem into smaller manageable pieces. Typically these pieces were oriented to the procedures which were taken place to solve the problem, rather than the involved data.

As an example consider your computer. Especially, how a character appears on the screen when you type a key. In a procedural environment you write down the several steps necessary to bring a character on the screen:

1.

wait, until a key is pressed.

2.

get key value

3.

write key value at current cursor position

4.

advance cursor position

You do not distinguish entities with well-defined properties and well-known behaviour. In an object-oriented environment you would distinguish the interacting objects key and screen. Once a key receive a message that it should change its state to be pressed, its corresponding object sends a message to the screen object. This message requests the screen object to display the associated key value.

4.6 Exercises

1.

Class.

(a)

What distinguishes a class from an ADT?

(b)

Design a class for the ADT Complex. What representations do you choose for the ADT operations? Why?

2.

Interacting objects. Have a look to your tasks of your day life. Choose one which does not involve too many steps (for example, watching TV, cooking a meal, etc.). Describe this task in procedural and object-oriented form. Try to begin viewing the world to consist of objects.

3.

Object view. Regarding the last exercise, what problems do you encounter?

4.

Messages.

(a)

Why do we talk about ``messages'' rather than ``procedure calls''?

(b)

Name a few messages which make sense in the Internet environment. (You must therefore identify objects.)

(c)

Why makes the term ``message'' more sense in the environment of the last exercise, than the term ``procedure call''?

Personal Computer

Configuration of Personal Computer


Exploded view of a modern personal computer:


1. Display
2. Motherboard
3. CPU (Microprocessor)
4. Primary storage (RAM)
5. Expansion cards
6. Power supply
7. Optical disc drive
8. Secondary storage (HD)
9. Keyboard
10. Mouse
Personal computers can be categorized by size and portability:
• Desktop computers
• Laptop or notebooks
• Personal digital assistants (PDAs)
• Portable computers
• Tablet computers
• Wearable computers

Most personal computers are standardized to the point that purchased software is expected
to run with little or no customization for the particular computer. Many PCs are also userupgradable,
especially desktop and workstation class computers. Devices such as main memory,
mass storage, even the motherboard and central processing unit may be easily replaced by an end
user. This upgradeability is, however, not indefinite due to rapid changes in the personal computer
industry. A PC that was considered top-of-the-line five or six years prior may be impractical to
upgrade due to changes in industry standards. Such a computer usually must be totally replaced
once it is no longer suitable for its purpose. This upgrade and replacement cycle is partially related
to new releases of the primary mass-market operating system, which tends to drive the acquisition
of new hardware and tends to obsolete previously serviceable hardware (see planned obsolescence).
The hardware capabilities of personal computers can sometimes be extended by the addition of
expansion cards connected via an expansion bus. Some standard peripheral buses often used for
adding expansion cards in personal computers as of 2005 are PCI, AGP (a high-speed PCI bus
dedicated to graphics adapters), and PCI Express. Most personal computers as of 2005 have
multiple physical PCI expansion slots. Many also include an AGP bus and expansion slot or a PCI
Express bus and one or more expansion slots, but few PCs contain both buses.
5 Display
A computer display (also known as a computer monitor, computer screen, or computer
video display) is a device that can display signals generated by a computer as images on a screen.
There are many types of monitors, but they generally conform to display standards. Once an
essential component of computer terminals, computer displays have long since become standardised
peripherals in their own right.
6 Motherboard
The motherboard (or mainboard) is the primary circuit board for a personal microcomputer.
Many other components connect directly or indirectly to the motherboard. Motherboards usually
contain one or more CPUs, supporting circuitry and ICs for CPU operation, main memory, and
facilities for initial setup of the computer immediately after being powered on (often called boot
firmware or a BIOS). In many portable and embedded personal computers, the motherboard houses
nearly all of the PC's core components. Often a motherboard will also contain one or more
peripheral buses and physical connectors for expansion purposes. Sometimes a secondary daughter
board is connected with the motherboard to provide further expandability or to satisfy space
constraints.
7 Central processing unit
The central processing unit, or CPU, is the part of the computer that executes software
programs, including the operating system. Nearly all PCs contain a type of CPU known as a
microprocessor. The microprocessor often plugs into the motherboard using one of many different
types of sockets. IBM PC compatible computers use an x86-compatible processor, usually made by
Intel, AMD, VIA Technologies or Transmeta. Apple Macintosh processors were based on the
Power PC (a RISC architecture) but as of 2005, Apple has used x86 compatible processors from
Intel.
Jelena Mamčenko Operating Systems
Lecture Notes on Operating Systems 12
Intel 80486DX2 microprocessor in a ceramic PGA package
A central processing unit (CPU), or sometimes simply processor, is the component in a
digital computer that interprets instructions and processes data contained in computer programs.
CPUs provide the fundamental digital computer trait of programmability, and are one of the
necessary components found in computers of any era, along with primary storage and input/output
facilities. A CPU that is manufactured using integrated circuits is known as a microprocessor. Since
the mid-1970s, single-chip microprocessors have almost totally replaced all other types of CPUs,
and today the term "CPU" is usually applied to some type of microprocessor.
The phrase "central processing unit" is, in general terms, a description of a certain class of
logic machines that can execute complex computer programs. This broad definition can easily be
applied to many early computers that existed long before the term "CPU" ever came into
widespread usage. However, the term itself and its initialism have been in use in the computer
industry at least since the early 1960s (Weik 1961). The form, design and implementation of CPUs
have changed dramatically since the earliest examples, but their fundamental operation has
remained much the same.
Early CPUs were custom-designed as a part of a larger, usually one-of-a-kind, computer.
However, this costly method of designing custom CPUs for a particular application has largely
given way to the development of inexpensive and standardized classes of processors that are suited
for one or many purposes. This standardization trend generally began in the era of discrete transistor
mainframes and minicomputers and has rapidly accelerated with the popularization of the integrated
circuit (IC). The IC has allowed increasingly complex CPUs to be designed and manufactured in
very small spaces (on the order of millimeters). Both the miniaturization and standardization of
CPUs have increased the presence of these digital devices in modern life far beyond the limited
application of dedicated computing machines. Modern microprocessors appear in everything from
automobiles to cell phones to children's toys.
8 Primary storage
Primary storage, or internal memory, is computer memory that is accessible to the central
processing unit of a computer without the use of computer's input/output channels. Primary storage
is used to store data that is likely to be in active use. Primary storage is typically very fast, in the
case of RAM which is also volatile, losing the stored information in an event of power loss, and
quite expensive. ROM is not volatile, but not suited to storage of large quantities of data because it
is expensive to produce. Typically, ROM must also be completely erased before it can be rewritten,
making large scale use impractical, if not impossible. Therefore, separate secondary storage, or
external memory, is usually required for long-term persistent storage.
Confusingly, the term primary storage has recently been used in a few contexts to refer to
online storage (hard disks), which is usually classified as secondary storage.
Primary storage may include several types of storage, such as main storage, cache memory, and
special registers, all of which can be directly accessed by the processor. Primary storage can be
accessed randomly, that is, accessing any location in storage at any moment takes the same amount
of time. A particular location in storage is selected by its physical memory address. That address
remains the same, no matter how the particular value stored there changes.
9 Expansion card

Fitting an expansion card into a motherboard
An expansion card in computing is a printed circuit board that can be inserted into an
expansion slot of a computer motherboard to add additional functionality to a computer system.
One edge of the expansion card holds the contacts that fit exactly into the slot. They establish the
electrical contact between the electronics (mostly integrated circuits) on the card and on the
motherboard.
Connectors mounted on the bracket allow the connection of external devices to the card.
Depending on the form factor of the motherboard and case, around one to seven expansion cards
can be added to a computer system. There are also other factors involved in expansion card
capacity. For example, some expansion cards need two slots like some NVidia GeForce FX
graphics cards and there is often a space left to aid cooling on some high-end cards.
9.1 History of the expansion card
The first microcomputer to feature a slot-type expansion card bus was the Altair 8800,
developed 1974-1975. Initially, implementations of this bus were proprietary (such as the Apple II
and Macintosh), but by 1982 manufacturers of Intel 8080/Zilog Z80-based computers running
CP/M had settled around the S-100 standard. IBM introduced the XT bus with the first IBM PC in
1983. XT was replaced with ISA in 1984. IBM's MCA bus, developed for the PS/2 in 1987, was a
competitor to ISA, but fell out of favor due to the latter's industry-wide acceptance. EISA, the 16-bit
extended version of ISA, was common on PC motherboards until 1997, when Microsoft declared it
as "legacy" subsystem in the PC 97 industry white-paper. VESA Local Bus, an early expansion bus
that was inherently tied to the 80486 CPU, became obsolete (along with the processor) when Intel
launched the Pentium processor in 1996.
The PCI bus was introduced in 1991 as replacement for ISA. The standard (now at version 2.2) is
still found on PC motherboards to this day. Intel introduced the AGP bus in 1997 as a dedicated
Jelena Mamčenko Operating Systems
Lecture Notes on Operating Systems 14
video acceleration solution. Though termed a bus, AGP supports only a single card at a time. Both
of these technologies are now slated to be replaced by PCI-Express, beginning in 2005. This latest
standard, approved in 2004, implements the logical PCI protocol over serial communication
interface.
Expansion slot standards
• PCI Express
• AGP
• PCI
• ISA
• MCA
• VLB
• CardBus/PC card/PCMCIA (for notebook computers)
• Compact flash (for handheld computers)
Expansion card types
• Graphics card
• Sound card
• Network card
• TV card
• Modems
• Wireless network (such as WiFi) cards.
• Hard disk/RAID controllers (host adapter)
• POST cards
• Physics cards, only recently became commercially available
10 Power supply
A power supply (sometimes known as a power supply unit or PSU) is a device or system
that supplies electrical or other types of energy to an output load or group of loads. The term is most
commonly applied to electrical energy supplies.
The complete range of power supplies is very broad, and could be considered to include all
forms of energy conversion from one form into another. Conventionally though, the term is usually
confined to electrical or mechanical energy supplies. Constraints that commonly affect power
supplies are the amount of power they can supply, how long they can supply it for without needing
some kind of refueling or recharging, how stable their output voltage or current is under varying
load conditions, and whether they provide continuous power or pulses.
The voltage regulation of power supplies is done by incorporating circuitry to tightly control
the output voltage and/or current of the power supply to a specific value. The specific value is
closely maintained despite variations in the load presented to the power supply's output, or any
reasonable voltage variation at the power supply's input.
Jelena Mamčenko Operating Systems
Lecture Notes on Operating Systems 15
Electrical power supplies
A "wall wart" style variable DC power supply with its cover removed. Simpler AC supplies
have nothing inside the case except the transformer.
This term covers the mains power distribution system together with any other primary or
secondary sources of energy such as:
• Conversion of one form of electrical power to another desired form and voltage. This
typically involves converting 120 or 240 volt AC supplied by a utility company (see electricity
generation) to a well-regulated lower voltage DC for electronic devices. For examples, see
switched-mode power supply, linear regulator, rectifier and inverter (electrical).
• Batteries
• Chemical fuel cells and other forms of energy storage systems
• Solar power
• Generators or alternators (particularly useful in vehicles of all shapes and sizes, where the
engine has rotational power to spare, or in semi-portable units containing an internal combustion
engine and a generator) (For large-scale power supplies, see electricity generation.) Low voltage,
low power DC power supply units are commonly integrated with the devices they supply, such as
computers and household electronics.
11 Computer power supply
A computer power supply typically is designed to convert 120 V or 240 V AC power from
the electrical company to usable power for the internal components of the computer. The most
common computer power supply is built to conform with the ATX form factor. This enables
different power supplies to be interchangeable with different components inside the computer. ATX
power supplies also are designed to turn on and off using a signal from the motherboard (PS-ON
wire), and provide support for modern functions such as the Standby mode of many computers.
Computer power supplies are rated for certain wattages based on their maximum output
power. Typical wattages range from 200 W to 500 W, although some new personal computers with
high energy requirements may draw as much as 1000 W (1 kW).
Most computer power supplies have a large bundle of wires emerging from one end. One
connector attached to the opposite end of some wires goes to the motherboard to provide power.
The PS-ON wire is located in this connector. The connector for the motherboard is typically the
largest of all the connectors. There are also other, smaller connectors, most of which have four
wires: two black, one red, and one yellow. Unlike the standard electrical wire color-coding, each
black wire is a Ground, the red wire is +5 V, and the yellow wire is +12 V.
Inside the computer power supply is a complex arrangement of electrical components,
ranging from diodes to capacitors to transformers. Also, many power supplies have metal heatsinks
and fans to dissipate large amounts of heat produced. It is dangerous to open a power supply while
Jelena Mamčenko Operating Systems
Lecture Notes on Operating Systems 16
it is connected to an electrical outlet as high voltages may be present even while the unit is switched
off.
In desktop computers, the power supply is a small (PSU) box inside the computer; it is an
important part of the computer because it provides electrical power in a form that is suitable for
every other component inside or attached to the computer in order for it to work. If only a small
voltage is needed, the mains power needs to be transformed to a suitable level in order for the
component to work.
In portable computers there is usually an external power supply that produces low voltage
DC power from a mains electrical supply (typically a standard AC wall outlet). Circuitry inside the
portable computer uses this transformed power to charge the battery as needed, in addition to
providing the various voltages required by the other components of the portable computer.
11.1 Domestic mains adaptors
A power supply (or in some cases just a transformer) that is built into the top of a plug is
known as a wall wart, power brick, or just power adapter.
11.2 Linear power supply
A simple AC powered linear power supply uses a transformer to convert the voltage from
the wall outlet to a lower voltage. A diode circuit (generally either a single diode or an array of
diodes called a diode bridge but other configurations are possible) then rectifies the AC voltage to
pulsating DC. A capacitor smooths out most of the pulsating of the rectified waveform to give a DC
voltage with some ripple. Finally depending on the requirements of the load a linear regulator may
be used to reduce the voltage to the desired output voltage and remove the majority of the
remaining ripple. It may also provide other features such as current limiting.
11.3 Switched-mode power supply
In a switched-mode power supply the incoming power is passed through a transistor and
transformer network that switches on and off thousands to millions of times per second. This means
that a smaller, less expensive, lighter transformer can be used, because the voltage is being made to
alternate faster, and thus a smaller magnetic core can be used.
Switching power supplies can be used as DC to DC converters. In this application, the
power supply is designed to accept a limited range DC input and then output a different DC voltage.
This is particularly useful in portable devices, as well as power distribution in large electronic
equipment. A transformerless switching power supply that outputs a voltage higher than its input
voltage is typically called a boost converter. A transformerless switching power supply that outputs
a voltage lower than its input voltage is typically called a buck converter. These transformerless
switching power supplies use an inductor as the primary circuit element in converting the voltage.
Circuitry is used to pass current through the inductor to store a certain amount of electrical energy
as a magnetic field. The current flow is then stopped, and the magnetic field collapses causing the
stored energy to be released as current again. This is done rapidly (up to millions of times per
second). By carefully metering the amount of energy stored in the inductor, the current released by
the inductor can be regulated thus allowing the output voltage to be tightly regulated. A switching
power supply incorporating a transformer can provide many output voltages simultaneously, and is
typically called a flyback converter. Switching power supplies are typically very efficient if well
designed, and therefore waste very little power as heat. Because of these efficiencies, they are
typically much smaller and lighter than an equivalently rated linear supply.
Power conversion
The term "power supply" is sometimes restricted to those devices that convert some other
form of energy into electricity (such as solar power and fuel cells and generators). A more
accurate term for devices that convert one form of electric power into another form of electric
power (such as transformers and linear regulators) is power converter.
Uses in aviation
The most exotic power supplies are used in aviation to enable reliable restarting of stalled
engines.
In jet transports, an engine is restarted from the power produced by the 400 Hz, three-phase AC
generators attached to the shafts of the other engine(s). Most of the starting torque generated by the
engine's motor/generator is provided by the current at the peaks of the AC waveform.
If the aircraft electronics used simple rectifying power supplies, they would use current only
from these peaks, since the diodes conduct only during the voltage peaks where the input voltage is
higher than the output voltage. This could prevent the pilot from restarting an engine in an
emergency.
Therefore, aircraft power supplies take energy evenly from all parts of the AC waveform.
this is done by using a switching power supply technique called "power factor correction" which
creates a balanced current draw over the entire AC waveform.
12 Optical disc
In computing, sound reproduction, and video, an optical disc is flat, circular, usually
polycarbonate disc whereon data is stored. This data is generally accessed when a special material
on the disc (often aluminum) is illuminated with a laser diode.
David Paul Gregg developed an analog optical disk for recording video and patented it in
1961 and 1969 (U.S. patent 3430966). Of special interest is U.S. 4,893,297, first filed in 1968 and
issued in 1990, so that it will be a source of royalty income for Pioneer’s DVA until 2007. It
encompasses systems such as CD, DVD, and even Blu-ray Disc. Gregg's company, Gauss
Electrophysics, was acquired, along with Gregg's patents, by MCA in the early 1960s.
Parallel, and probably inspired by the developments in the U.S., a small group of physicists
started their first optical videodisc experiments at Philips Research in Eindhoven, The Netherlands
in 1969. In 1975, Philips and MCA decided to join forces. In 1978, much too late, the long waited
laserdisc was introduced in Atlanta. MCA delivered the discs and Philips the players. It turned out
to be a total technical and commercial failure, and quite soon the Philips/MCA cooperation came to
an end. In Japan and the U.S., Pioneer has been successful with the videodisc till the advent of
DVD.
Philips and Sony formed a consortium in 1979 to develop a digital audio disc, which
resulted in the very successful introduction of the compact disc in 1983.
The promotion of standardised optical storage is undertaken by the Optical Storage
Technology Association (OSTA).
The information on an optical disc is stored sequentially on a continuous spiral track from
the innermost track to the outermost track.
12.1 First-generation optical discs
Optical discs were initally used for storing music and software. The Laserdisc format stored
analog video, but it fought an uphill battle against VHS.
• Compact disc (CD)
• Laserdisc
• Magneto-optical disc
12.2 Second-generation optical discs
These discs were invented roughly in the 1990s. Second-generation optical discs were
created to store large amounts of data, including TV-quality digital video.
• Minidisc
• Digital Versatile Disc (DVD)
• Digital Multilayer Disk
Jelena Mamčenko Operating Systems
Lecture Notes on Operating Systems 18
• Digital Video Express
• Fluorescent Multilayer Disc
• GD-ROM
• Phase-change Dual
• Universal Media Disc
12.3 Third-generation optical discs
Major third-generation optical discs are currently in development. They will be optimal for
storing high-definition video and extremely large video games.
• Blu-ray Disc
• Enhanced Versatile Disc
• Forward Versatile Disc
• Holographic Versatile Disc
• HD DVD
• Ultra Density Optical
• Professional Disc for DATA
• Versatile Multilayer Disc
13 Secondary storage
In computer storage, secondary storage, or external memory, is computer memory that is
not directly accessible to the central processing unit of a computer, requiring the use of computer's
input/output channels. Secondary storage is used to store data that is not in active use. Secondary
storage is usually slower than primary storage, or internal memory, but also almost always has
higher storage capacity and is non-volatile, preserving the stored information in an event of power
loss.
Storage devices in this category include:
• CD, CD-R, CD-RW
• DVD
• Flash memory
• Floppy disk
• Hard disk
• Magnetic tape
• Paper tape
• Punch card
• RAM disk
14 Computer keyboard
A computer keyboard is a peripheral modeled after the typewriter keyboard. Keyboards
are designed for the input of text and characters, and also to control the operation of the computer.
Physically, computer keyboards are an arrangement of rectangular or near-rectangular buttons, or
"keys". Keyboards typically have characters engraved or printed on the keys; in most cases, each
press of a key corresponds to a single written symbol. However, to produce some symbols requires
pressing and holding several keys simultaneously, or in sequence; other keys do not produce any
symbol, but instead affect the operation of the computer, or the keyboard itself. See input method
editor.
A 104-key PC US English QWERTY keyboard layout
Roughly 50% of all keyboard keys produce letters, numbers or signs (characters). Other
keys can produce actions when pressed, and other actions are available by simultaneously pressing
more than one action key.
15 Mouse (computing)
Fig. 1. Operating mechanical mouse
Operating a mechanical mouse (Fig. 2).
1: Moving the mouse turns the ball.
2: X and Y rollers grip the ball and transfer movement.
3: Optical encoding disks include light holes.
4: Infrared LEDs shine through the disks.
5: Sensors gather light pulses to convert to X and Y velocities.
Fig. 2. The first computer mouse
Jelena Mamčenko Operating Systems
Lecture Notes on Operating Systems 20
A mouse is a handheld pointing device for computers, being a small object fitted with one
or more buttons and shaped to sit naturally under the hand. The underside of the mouse houses a
device that detects the mouse's motion relative to the flat surface on which it moves. The mouse's
2D motion is typically translated into the motion of a pointer on the display.
It is called a mouse primarily because the cord on early models resembled the rodent's tail,
and also because the motion of the pointer on the screen can be mouse-like (Fig. 2).
16 Main memory
A PC's main memory place (or primary storage) is fast storage space that is directly
accessible by the CPU. It is generally used for storing relatively short-term data needed for software
execution. Main memory is usually much faster than mass storage devices like hard disks or optical
discs, but usually cannot retain data for more than a few fractions of a second without power and is
more expensive. Therefore, it is not generally suitable for long-term or archival data storage. As
with the CPU, most PCs use some form of semiconductor random access memory such as DRAM
or SRAM as their primary storage.
17 Hard disk drive
The disk drives use a sealed head/disk assembly (HDA) which was first introduced by
IBM's "Winchester" disk system. The use of a sealed assembly allowed the use of positive air
pressure to drive out particles from the surface of the disk, which improves reliability.
If the mass storage controller provides for expandability, a PC may also be upgraded by the addition
of extra hard disk or optical drives. For example, DVD-ROMs, CD-ROMs, and various optical disc
recorders may all be added by the user to certain PCs. Standard internal storage device interfaces
are ATA, Serial ATA, SCSI, and CF+ Type II in 2005.
18 Graphics - Video card
The graphics card - otherwise called a graphics adapter, video adapter, or video card - processes and
renders the graphics output from the computer to the VDU or computer monitor and is an essential
part of the modern computer. On older and budget models graphics cards tended to be integrated
with the motherboard but, more commonly, they are supplied in PCI, AGP, or PCI Express format.
Graphic cards are also the most glamorised computer component as it is the component which
creates all the visual effects on the computer which is essential for playing games.

Object-Oriented Programming Using C++

3 Abstract Data Types

 

Some authors describe object-oriented programming as programming abstract data types and their relationships. Within this section we introduce abstract data types as a basic concept for object-orientation and we explore concepts used in the list example of the last section in more detail.

3.1 Handling Problems

The first thing with which one is confronted when writing programs is the problem. Typically you are confronted with ``real-life'' problems and you want to make life easier by providing a program for the problem. However, real-life problems are nebulous and the first thing you have to do is to try to understand the problem to separate necessary from unnecessary details: You try to obtain your own abstract view, or model, of the problem. This process of modeling is called abstractionand is illustrated in Figure 3.1.

 

Figure 3.1:  Create a model from a problem with abstraction.

The model defines an abstract view to the problem. This implies that the model focusses only on problem related stuff and that you try to define properties of the problem. These properties include

• the data which are affected and
• the operations which are identified

by the problem.

As an example consider the administration of employees in an institution. The head of the administration comes to you and ask you to create a program which allows to administer the employees. Well, this is not very specific. For example, what employee information is needed by the administration? What tasks should be allowed? Employees are real persons who can be characterized with many properties; very few are:

• name,
• size,
• date of birth,
• shape,
• social number,
• room number,
• hair colour,
• hobbies.

Certainly not all of these properties are necessary to solve the administration problem. Only some of them are problem specific. Consequently you create a model of an employee for the problem. This model only implies properties which are needed to fulfill the requirements of the administration, for instance name, date of birth and social number. These properties are called the data of the (employee) model. Now you have described real persons with help of an abstract employee.

Of course, the pure description is not enough. There must be some operations defined with which the administration is able to handle the abstract employees. For example, there must be an operation which allows you to create a new employee once a new person enters the institution. Consequently, you have to identify the operations which should be able to be performed on an abstract employee. You also decide to allow access to the employees' data only with associated operations. This allows you to ensure that data elements are always in a proper state. For example you are able to check if a provided date is valid.

To sum up, abstraction is the structuring of a nebulous problem into well-defined entities by defining their data and operations. Consequently, these entities combinedata and operations. They are not decoupled from each other.

3.2 Properties of Abstract Data Types

The example of the previous section shows, that with abstraction you create a well-defined entity which can be properly handled. These entities define the data structure of a set of items. For example, each administered employee has a name, date of birth and social number.

The data structure can only be accessed with defined operations. This set of operations is called interface and is exported by the entity. An entity with the properties just described is called an abstract data type (ADT).

Figure 3.2 shows an ADT which consists of an abstract data structure and operations. Only the operations are viewable from the outside and define the interface.

 

Figure 3.2:  An abstract data type (ADT).

Once a new employee is ``created'' the data structure is filled with actual values: You now have an instance of an abstract employee. You can create as many instances of an abstract employee as needed to describe every real employed person.

Let's try to put the characteristics of an ADT in a more formal way:

Definition (Abstract Data Type) An abstract data type (ADT) is characterized by the following properties:

1.

It exports a type.

2.

It exports a set of operations. This set is called interface.

3.

Operations of the interface are the one and only access mechanism to the type's data structure.

4.

Axioms and preconditions define the application domain of the type.

With the first property it is possible to create more than one instance of an ADT as exemplified with the employee example. You might also remember the list example of chapter 2. In the first version we have implemented a list as a module and were only able to use one list at a time. The second version introduces the ``handle'' as a reference to a ``list object''. From what we have learned now, the handle in conjunction with the operations defined in the list module defines an ADTList:

1.

When we use the handle we define the corresponding variable to be of type List.

2.

The interface to instances of type List is defined by the interface definition file.

3.

Since the interface definition file does not include the actual representation of the handle, it cannot be modified directly.

4.

The application domain is defined by the semantical meaning of provided operations. Axioms and preconditions include statements such as

• ``An empty list is a list.''
• ``Let l=(d1, d2, d3, ..., dN) be a list. Then l.append(dM) results in l=(d1, d2, d3, ..., dN, dM).''
• ``The first element of a list can only be deleted if the list is not empty.''

However, all of these properties are only valid due to our understanding of and our discipline in using the list module. It is in our responsibility to use instances of Listaccording to these rules.

Importance of Data Structure Encapsulation

The principle of hiding the used data structure and to only provide a well-defined interface is known as encapsulation. Why is it so important to encapsulate the data structure?

To answer this question consider the following mathematical example where we want to define an ADT for complex numbers. For the following it is enough to know that complex numbers consists of two parts: real part and imaginary part. Both parts are represented by real numbers. Complex numbers define several operations: addition, substraction, multiplication or division to name a few. Axioms and preconditions are valid as defined by the mathematical definition of complex numbers. For example, it exists a neutral element for addition.

To represent a complex number it is necessary to define the data structure to be used by its ADT. One can think of at least two possibilities to do this:

• Both parts are stored in a two-valued array where the first value indicates the real part and the second value the imaginary part of the complex number. If xdenotes the real part and y the imaginary part, you could think of accessing them via array subscription: x=c[0] and y=c[1].
• Both parts are stored in a two-valued record. If the element name of the real part is r and that of the imaginary part is i, x and y can be obtained with: x=c.r and y=c.i.

Point 3 of the ADT definition says that for each access to the data structure there must be an operation defined. The above access examples seem to contradict this requirement. Is this really true?

Let's look again at the two possibilities for representing imaginary numbers. Let's stick to the real part. In the first version, x equals c[0]. In the second version, xequals c.r. In both cases x equals ``something''. It is this ``something'' which differs from the actual data structure used. But in both cases the performed operation ``equal'' has the same meaning to declare x to be equal to the real part of the complex number c: both cases archieve the same semantics.

If you think of more complex operations the impact of decoupling data structures from operations becomes even more clear. For example the addition of two complex numbers requires you to perform an addition for each part. Consequently, you must access the value of each part which is different for each version. By providing an operation ``add'' you can encapsulate these details from its actual use. In an application context you simply ``add two complex numbers'' regardless of how this functionality is actually archieved.

Once you have created an ADT for complex numbers, say Complex, you can use it in the same way like well-known data types such as integers.

Let's summarize this: The separation of data structures and operations and the constraint to only access the data structure via a well-defined interface allows you to choose data structures appropriate for the application environment.

3.3 Generic Abstract Data Types

ADTs are used to define a new type from which instances can be created. As shown in the list example, sometimes these instances should operate on other data types as well. For instance, one can think of lists of apples, cars or even lists. The semantical definition of a list is always the same. Only the type of the data elements change according to what type the list should operate on.

This additional information could be specified by a generic parameter which is specified at instance creation time. Thus an instance of a generic ADT is actually an instance of a particular variant of the ADT. A list of apples can therefore be declared as follows:

    List<Apple> listOfApples;

The angle brackets now enclose the data type for which a variant of the generic ADT List should be created. listOfApples offers the same interface as any other list, but operates on instances of type Apple.

3.4 Notation

As ADTs provide an abstract view to describe properties of sets of entities, their use is independent from a particular programming language. We therefore introduce a notation here which is adopted from [3]. Each ADT description consists of two parts:

• Data: This part describes the structure of the data used in the ADT in an informal way.
• Operations: This part describes valid operations for this ADT, hence, it describes its interface. We use the special operation constructor to describe the actions which are to be performed once an entity of this ADT is created and destructor to describe the actions which are to be performed once an entity is destroyed. For each operation the provided arguments as well as preconditions and postconditions are given.

As an example the description of the ADT Integer is presented. Let k be an integer expression:

ADT Integer is

Data

A sequence of digits optionally prefixed by a plus or minus sign. We refer to this signed whole number as N.

Operations

constructor

Creates a new integer.

add(k)

Creates a new integer which is the sum of N and k.Consequently, the postcondition of this operation is sum = N+k. Don't confuse this with assign statements as used in programming languages! It is rather a mathematical equation which yields ``true'' for each value sum, N and k after add has been performed.

sub(k)

Similar to add, this operation creates a new integer of the difference of both integer values. Therefore the postcondition for this operation issum = N-k.

set(k)

Set N to k. The postcondition for this operation is N = k.

...

end

The description above is a specification for the ADT Integer. Please notice, that we use words for names of operations such as ``add''. We could use the more intuitive ``+'' sign instead, but this may lead to some confusion: You must distinguish the operation ``+'' from the mathematical use of ``+'' in the postcondition. The name of the operation is just syntax whereas the semantics is described by the associated pre- and postconditions. However, it is always a good idea to combine both to make reading of ADT specifications easier.

Real programming languages are free to choose an arbitrary implementation for an ADT. For example, they might implement the operation add with the infix operator ``+'' leading to a more intuitive look for addition of integers.

3.5 Abstract Data Types and Object-Orientation

ADTs allows the creation of instances with well-defined properties and behaviour. In object-orientation ADTs are referred to as classes. Therefore a class defines properties of objects which are the instances in an object-oriented environment.

ADTs define functionality by putting main emphasis on the involved data, their structure, operations as well as axioms and preconditions. Consequently, object-oriented programming is ``programming with ADTs'': combining functionality of different ADTs to solve a problem. Therefore instances (objects) of ADTs (classes) are dynamically created, destroyed and used.

3.6 Excercises

 

1.

ADT Integer.

(a)

Why are there no preconditions for operations add and sub?

(b)

Obviously, the ADT description of Integer is incomplete. Add methods mul, div and any other one. Describe their impacts by specifying pre- and postconditions.

2.

Design an ADT Fraction which describes properties of fractions.

(a)

What data structures can be used? What are its elements?

(b)

What does the interface look like?

(c)

Name a few axioms and preconditions.

3.

Describe in your own words properties of abstract data types.

4.

Why is it necessary to include axioms and preconditions to the definition of an abstract data type?

5.

Describe in your own words the relationship between

• instance and abstract data type,
• generic abstract data type and corresponding abstract data type,
• instances of a generic abstract data type.

Object-Oriented Programming Using C++

3 Abstract Data Types

 

Some authors describe object-oriented programming as programming abstract data types and their relationships. Within this section we introduce abstract data types as a basic concept for object-orientation and we explore concepts used in the list example of the last section in more detail.

3.1 Handling Problems

The first thing with which one is confronted when writing programs is the problem. Typically you are confronted with ``real-life'' problems and you want to make life easier by providing a program for the problem. However, real-life problems are nebulous and the first thing you have to do is to try to understand the problem to separate necessary from unnecessary details: You try to obtain your own abstract view, or model, of the problem. This process of modeling is called abstractionand is illustrated in Figure 3.1.

 

Figure 3.1:  Create a model from a problem with abstraction.

The model defines an abstract view to the problem. This implies that the model focusses only on problem related stuff and that you try to define properties of the problem. These properties include

• the data which are affected and
• the operations which are identified

by the problem.

As an example consider the administration of employees in an institution. The head of the administration comes to you and ask you to create a program which allows to administer the employees. Well, this is not very specific. For example, what employee information is needed by the administration? What tasks should be allowed? Employees are real persons who can be characterized with many properties; very few are:

• name,
• size,
• date of birth,
• shape,
• social number,
• room number,
• hair colour,
• hobbies.

Certainly not all of these properties are necessary to solve the administration problem. Only some of them are problem specific. Consequently you create a model of an employee for the problem. This model only implies properties which are needed to fulfill the requirements of the administration, for instance name, date of birth and social number. These properties are called the data of the (employee) model. Now you have described real persons with help of an abstract employee.

Of course, the pure description is not enough. There must be some operations defined with which the administration is able to handle the abstract employees. For example, there must be an operation which allows you to create a new employee once a new person enters the institution. Consequently, you have to identify the operations which should be able to be performed on an abstract employee. You also decide to allow access to the employees' data only with associated operations. This allows you to ensure that data elements are always in a proper state. For example you are able to check if a provided date is valid.

To sum up, abstraction is the structuring of a nebulous problem into well-defined entities by defining their data and operations. Consequently, these entities combinedata and operations. They are not decoupled from each other.

3.2 Properties of Abstract Data Types

The example of the previous section shows, that with abstraction you create a well-defined entity which can be properly handled. These entities define the data structure of a set of items. For example, each administered employee has a name, date of birth and social number.

The data structure can only be accessed with defined operations. This set of operations is called interface and is exported by the entity. An entity with the properties just described is called an abstract data type (ADT).

Figure 3.2 shows an ADT which consists of an abstract data structure and operations. Only the operations are viewable from the outside and define the interface.

 

Figure 3.2:  An abstract data type (ADT).

Once a new employee is ``created'' the data structure is filled with actual values: You now have an instance of an abstract employee. You can create as many instances of an abstract employee as needed to describe every real employed person.

Let's try to put the characteristics of an ADT in a more formal way:

Definition (Abstract Data Type) An abstract data type (ADT) is characterized by the following properties:

1.

It exports a type.

2.

It exports a set of operations. This set is called interface.

3.

Operations of the interface are the one and only access mechanism to the type's data structure.

4.

Axioms and preconditions define the application domain of the type.

With the first property it is possible to create more than one instance of an ADT as exemplified with the employee example. You might also remember the list example of chapter 2. In the first version we have implemented a list as a module and were only able to use one list at a time. The second version introduces the ``handle'' as a reference to a ``list object''. From what we have learned now, the handle in conjunction with the operations defined in the list module defines an ADTList:

1.

When we use the handle we define the corresponding variable to be of type List.

2.

The interface to instances of type List is defined by the interface definition file.

3.

Since the interface definition file does not include the actual representation of the handle, it cannot be modified directly.

4.

The application domain is defined by the semantical meaning of provided operations. Axioms and preconditions include statements such as

• ``An empty list is a list.''
• ``Let l=(d1, d2, d3, ..., dN) be a list. Then l.append(dM) results in l=(d1, d2, d3, ..., dN, dM).''
• ``The first element of a list can only be deleted if the list is not empty.''

However, all of these properties are only valid due to our understanding of and our discipline in using the list module. It is in our responsibility to use instances of Listaccording to these rules.

Importance of Data Structure Encapsulation

The principle of hiding the used data structure and to only provide a well-defined interface is known as encapsulation. Why is it so important to encapsulate the data structure?

To answer this question consider the following mathematical example where we want to define an ADT for complex numbers. For the following it is enough to know that complex numbers consists of two parts: real part and imaginary part. Both parts are represented by real numbers. Complex numbers define several operations: addition, substraction, multiplication or division to name a few. Axioms and preconditions are valid as defined by the mathematical definition of complex numbers. For example, it exists a neutral element for addition.

To represent a complex number it is necessary to define the data structure to be used by its ADT. One can think of at least two possibilities to do this:

• Both parts are stored in a two-valued array where the first value indicates the real part and the second value the imaginary part of the complex number. If xdenotes the real part and y the imaginary part, you could think of accessing them via array subscription: x=c[0] and y=c[1].
• Both parts are stored in a two-valued record. If the element name of the real part is r and that of the imaginary part is i, x and y can be obtained with: x=c.r and y=c.i.

Point 3 of the ADT definition says that for each access to the data structure there must be an operation defined. The above access examples seem to contradict this requirement. Is this really true?

Let's look again at the two possibilities for representing imaginary numbers. Let's stick to the real part. In the first version, x equals c[0]. In the second version, xequals c.r. In both cases x equals ``something''. It is this ``something'' which differs from the actual data structure used. But in both cases the performed operation ``equal'' has the same meaning to declare x to be equal to the real part of the complex number c: both cases archieve the same semantics.

If you think of more complex operations the impact of decoupling data structures from operations becomes even more clear. For example the addition of two complex numbers requires you to perform an addition for each part. Consequently, you must access the value of each part which is different for each version. By providing an operation ``add'' you can encapsulate these details from its actual use. In an application context you simply ``add two complex numbers'' regardless of how this functionality is actually archieved.

Once you have created an ADT for complex numbers, say Complex, you can use it in the same way like well-known data types such as integers.

Let's summarize this: The separation of data structures and operations and the constraint to only access the data structure via a well-defined interface allows you to choose data structures appropriate for the application environment.

3.3 Generic Abstract Data Types

ADTs are used to define a new type from which instances can be created. As shown in the list example, sometimes these instances should operate on other data types as well. For instance, one can think of lists of apples, cars or even lists. The semantical definition of a list is always the same. Only the type of the data elements change according to what type the list should operate on.

This additional information could be specified by a generic parameter which is specified at instance creation time. Thus an instance of a generic ADT is actually an instance of a particular variant of the ADT. A list of apples can therefore be declared as follows:

    List<Apple> listOfApples;

The angle brackets now enclose the data type for which a variant of the generic ADT List should be created. listOfApples offers the same interface as any other list, but operates on instances of type Apple.

3.4 Notation

As ADTs provide an abstract view to describe properties of sets of entities, their use is independent from a particular programming language. We therefore introduce a notation here which is adopted from [3]. Each ADT description consists of two parts:

• Data: This part describes the structure of the data used in the ADT in an informal way.
• Operations: This part describes valid operations for this ADT, hence, it describes its interface. We use the special operation constructor to describe the actions which are to be performed once an entity of this ADT is created and destructor to describe the actions which are to be performed once an entity is destroyed. For each operation the provided arguments as well as preconditions and postconditions are given.

As an example the description of the ADT Integer is presented. Let k be an integer expression:

ADT Integer is

Data

A sequence of digits optionally prefixed by a plus or minus sign. We refer to this signed whole number as N.

Operations

constructor

Creates a new integer.

add(k)

Creates a new integer which is the sum of N and k.Consequently, the postcondition of this operation is sum = N+k. Don't confuse this with assign statements as used in programming languages! It is rather a mathematical equation which yields ``true'' for each value sum, N and k after add has been performed.

sub(k)

Similar to add, this operation creates a new integer of the difference of both integer values. Therefore the postcondition for this operation issum = N-k.

set(k)

Set N to k. The postcondition for this operation is N = k.

...

end

The description above is a specification for the ADT Integer. Please notice, that we use words for names of operations such as ``add''. We could use the more intuitive ``+'' sign instead, but this may lead to some confusion: You must distinguish the operation ``+'' from the mathematical use of ``+'' in the postcondition. The name of the operation is just syntax whereas the semantics is described by the associated pre- and postconditions. However, it is always a good idea to combine both to make reading of ADT specifications easier.

Real programming languages are free to choose an arbitrary implementation for an ADT. For example, they might implement the operation add with the infix operator ``+'' leading to a more intuitive look for addition of integers.

3.5 Abstract Data Types and Object-Orientation

ADTs allows the creation of instances with well-defined properties and behaviour. In object-orientation ADTs are referred to as classes. Therefore a class defines properties of objects which are the instances in an object-oriented environment.

ADTs define functionality by putting main emphasis on the involved data, their structure, operations as well as axioms and preconditions. Consequently, object-oriented programming is ``programming with ADTs'': combining functionality of different ADTs to solve a problem. Therefore instances (objects) of ADTs (classes) are dynamically created, destroyed and used.

3.6 Excercises

 

1.

ADT Integer.

(a)

Why are there no preconditions for operations add and sub?

(b)

Obviously, the ADT description of Integer is incomplete. Add methods mul, div and any other one. Describe their impacts by specifying pre- and postconditions.

2.

Design an ADT Fraction which describes properties of fractions.

(a)

What data structures can be used? What are its elements?

(b)

What does the interface look like?

(c)

Name a few axioms and preconditions.

3.

Describe in your own words properties of abstract data types.

4.

Why is it necessary to include axioms and preconditions to the definition of an abstract data type?

5.

Describe in your own words the relationship between

• instance and abstract data type,
• generic abstract data type and corresponding abstract data type,
• instances of a generic abstract data type.