Chapter 1
Introduction to Object-oriented Programming

Kurt Nørmark ©
Department of Computer Science, Aalborg University, Denmark


Abstract
Next lecture
Index References Contents
Following a practical course introduction, this lecture will focus on the transition from structured programming (in C, for instance) to object-oriented programming (in C#, for instance). We will discuss some the basic motivations in favor of object-oriented programming. In addition, we will review the inspiration from a theory about concepts and phenomena.


From structured programming to object-oriented programming

Structured Programming
Slide Annotated slide Contents Index
References Textbook 
Structured programming stands as a contrast to unstructured programming. Unstructured programming is a reminiscence of low-level, machine language programming with explicit use of goto statements.

Structured programming relies on use of high-level control structures instead of low-level jumping

Structured programming is also loosely coupled with top-down programming and program development by stepwise refinement

  • Structured top-down programming by stepwise refinement:

    • Start by writing the main program

      • Use selective and iterative control structures

      • Postulate and call procedures P1, ...,Pn

    • Implement P1, ... Pn, and in turn the procedures they make use of

    • Eventually, the procedures become so simple that they can be implemented without introducing additional procedures

Program Development by Stepwise Refinement is the title of a famous paper written by Niklaus Wirth in 1971. Niklaus Wirth is the inventor of the programming language Pascal. In this paper Wirth argues how to decompose a task in subtask, in a top-down fashion.

Reference

A structured program: Hangman
Slide Annotated slide Contents Index
References Textbook 

A sketch of Hangman 2006 - seen as a structured program

In this lecture we start out by showing a structured program for the well-known Hangmang game. In the hangman game the player is supposed to guess the letters of word or word phrase outline. The game is similar to the TV-game Wheel of Fortune. Each erroneous guess in Hangman is punished. The ultimate punishment is to be sent to the gallows.

At the end of the lecture, we will outline an object-oriented version of the Hangman program.

Program: The main function of the Hangman program.
int main(void){
  char *playerName;
  answer again;

  playerName = getPlayerName();
  initHangman();
  do{
    playHangman(playerName);
    again = askUser("Do you want to play again");
  } while (again == yes);
}    

Program: The function getPlayerName of main.
char *getPlayerName(){
  char *playerName = (char*)malloc(NAME_MAX);

  printf("What is your name? ");
  fgets(playerName, NAME_MAX, stdin);
  playerName[strlen(playerName)-1] = '\0';
  return playerName;
}

Program: The function initHangman of main.
void initHangman (void){
  srand(time(NULL));
  initPuzzles("puzzles.txt");
}

Program: The function askUser of main.
answer askUser(char *question){
  char ch;
  do {
    printf("%s [y/n]? ", question);
    while (isspace(ch = fgetc(stdin)));
    if (ch == 'y') 
      return yes;
    else if (ch == 'n')
      return no;}
  while (ch != 'y' || ch != 'n');
}   

Program: The function playHangman of main.
void playHangman (char playerName[]){
  int aPuzzleNumber, wonGame;
  puzzle secretPuzzle;
  hangmanGameState gameState;
  char playersGuess;

  initGame(playerName, &gameState);
  aPuzzleNumber = rand() % numberOfPuzzles();
  secretPuzzle = getPuzzle(aPuzzleNumber);

  while ((gameState.numberOfWrongGuesses < N) && 
         (gameState.numberOfCorrectGuesses < secretPuzzle.numberOfCharsToGuess)){ 
    gameStatistics(gameState, secretPuzzle);
    presentPuzzleOutline(secretPuzzle,gameState);  printf("\n");
    presentRemainingAlphabet(gameState);  printf("\n");
    if (CHEATING) presentSecretPuzzle(secretPuzzle);
    printf("\n");
    playersGuess = getUsersGuess(); 
    clrconsole();
    updateGameState(&gameState, secretPuzzle, playersGuess); 
  }
  gameStatistics(gameState, secretPuzzle);
  wonGame = wonOrLost(gameState,secretPuzzle);
  handleHighscore(gameState, secretPuzzle, wonGame);
}   

Program: The function InitGame of playHangman.
void initGame (char playerName[], hangmanGameState *state){
  strcpy(state->playerName, playerName); 
  state->numberOfWrongGuesses = 0;
  state->numberOfCorrectGuesses = 0;
  int i;
  for (i=0; i < 128; i++){
    if (isalpha(i)) 
      state->charGuessed[i] = 0;
    else 
      state->charGuessed[i] = 1;
  }
  initHighscoreFacility("highscorefile");
  clrconsole();
}   

Program: The function getPuzzle of playHangman.
puzzle getPuzzle(int n){
  FILE *puzzleFile;
  puzzle result;
  int i, ch, num;
  char *puzzleLine, *catStr, *puzzleStr;
  char *puzzleLineQ1, *puzzleLineQ2, *puzzleLineQ3, *puzzleLineQ4;

  puzzleLine = (char*)malloc(PUZZLEMAXCOUNT);
  catStr = (char*)calloc(PUZZLEMAXCOUNT,1);
  puzzleStr = (char*)calloc(PUZZLEMAXCOUNT,1);

  puzzleFile = fopen(puzzleFileName, "r");

  for(i = 0; i < n*4;  i++) matchDoubleQuoteFile(puzzleFile); /* read through n*4 double quotes */
  while (isspace(ch = getc(puzzleFile)));                 /* skip white space */
  ungetc(ch,puzzleFile);                                  /* put double quote back */

  fgets(puzzleLine, PUZZLEMAXCOUNT, puzzleFile);          /* read a line from puzzle file */

  puzzleLineQ1 = matchDoubleQuoteStr(puzzleLine);         /* identify quotes in string */
  puzzleLineQ2 = matchDoubleQuoteStr(puzzleLineQ1+1);
  puzzleLineQ3 = matchDoubleQuoteStr(puzzleLineQ2+1);
  puzzleLineQ4 = matchDoubleQuoteStr(puzzleLineQ3+1);

  strncpy(catStr, puzzleLineQ1+1, puzzleLineQ2 - puzzleLineQ1 - 1);
  strncpy(puzzleStr, puzzleLineQ3+1, puzzleLineQ4 - puzzleLineQ3 - 1);

  num = 0;
  for(i = 0; i < strlen(puzzleStr); i++)  if (isalpha(puzzleStr[i])) num++;

  result.category = catStr,
  result.phrase = puzzleStr;
  result.numberOfCharsToGuess = num;
  fclose(puzzleFile);
  return result;
}   

Reference

Etc., etc...

Exercise 1.2. How did you program the Hangman game?

This is an exercise for students who have a practical experience with the development of the Hangman program, or a similar game.

Recall how you carried out the development of the program.

To which degree did you adhere to top-down development by stepwise refinement?

If you did not use this development approach, then please try to characterize how you actually did it.

Reference

Observations about Structured Programming
Slide Annotated slide Contents Index
References Textbook 

Structured programming is a good and recommendable way to program

Despite of that we will identify a number of problematic aspects that motivate OOP

Structured programming is not bad at all.

Structured programming is not necessarily ideal for large programs. Object-oriented programming is strong with respect to structuring of large program. In addition, object-oriented programming is based on conceptual reasoning, and strong metaphors.

  • Structured programming is narrowly oriented towards solving one particular problem

    • It would be nice if our programming efforts could be oriented more broadly

  • Structured programming is carried out by gradual decomposition of the functionality

    • The structures formed by functionality/actions/control are not the most stable parts of a program

    • Focusing on data structures instead of control structure is an alternative approach

  • Real systems have no single top - Real systems may have multiple tops [Bertrand Meyer]

    • It may therefore be natural to consider alternatives to the top-down approach

Towards Object-oriented Programming
Slide Annotated slide Contents Index
References Textbook 
On this slide we list a few observations that bring us in the direction of object-oriented programming.

  • The gap between the problem and the level of the machine:

    • Fill the gap bottom up

  • Use the data as the basic building blocks

    • Data, and relations between data, are more stable than the actions on data

  • Bundle data with their natural operations

    • Build on the ideas of abstract datatypes

    • Consolidate the programming constructs that encapsulate data (structs/records)

  • Concentrate on the concepts and phenomena which should be handled by the program

    • Make use of existing theories of phenomena and concepts

    • Form new concepts from existing concepts

The idea of abstract datatypes is central to object-oriented programming. On the following slide page we attempt to give you a basic idea behind abstract datatypes.


Towards Object-oriented Programming

Client, Servers, and Messages
Slide Annotated slide Contents Index
References Textbook 

This is the first of a number of slides that will lead us in the direction of object-oriented programming.

Each of these slides contribute a bit. At this moment, you may be in doubt how "these bits" work together. Please be patient, however. It will be clarified later in the material.

Peter orders a Pizza at AAU Pizza by email.

Via interaction between a number of service providers, a pizza is delivered to Peters group room

The scenario of pizza ordering. The scenario focuses on a number of objects (persons) who communicate by message passing.

A client asks for a service at some given service provider (server ).

This may lead the service provider (which now plays a client role) to ask for subservices

Clients and servers communicate by passing messages that return results

Try the accompanying SVG animation

Try the SVG-based animation here.

To succeed, your brower must be SVG enabeled. In particular, SVG animations must be supported. This page has SVG examples, and explains how to set up Firefox with the Adobe SVG plugin.

Responsibilities
Slide Annotated slide Contents Index
References Textbook 

Responsibilities go hand in hand with contracts. Contracts are covered in the very end of this teaching material.

Objects that act as servers manage a certain amount of responsibility

Objects that manage too many responsibilities tend to be too complex. It is almost always better to distribute the responsibility on several "smaller objects". - The same is actually true for operations.

  • Responsibility

    • Of an object, as reflected by the interface it provides to other objects

    • Of an operation

      • Precondition for activation - proposition about prerequisites for calling

      • Postcondition - proposition about result or effects

    • Well-defined responsibilities provide for coherent objects

Preconditions and postconditions is an important topic in the lecture about Contracts and Assertions. See here.

You should care about the responsibilities of both objects and operations

The distribution of responsibilities will become a major theme later in the course

Data-centered modularity
Slide Annotated slide Contents Index
References Textbook 
In large program, modularity becomes a very important quality.

The concept modularity: Modularity is the property of a computer program that measures the extent to which it has been composed out of separate parts called modules [Wikipedia]

  • Procedural modularity

    • Made up of individual procedures or functions

    • Relatively fine grained

    • Not sufficient for programming in the large

  • Boxing modularity

    • A wall around arbitrary definitions

    • As coarse grained as needed

    • Visibility may be controlled - import and export

  • Data-centered modularity

    • A module built around data that represents a single concept

    • High degree of cohesion

    • Visibility may be controlled

    • The module may act as a datatype

We distinguish between three different kinds of modularity.

Procedural modularity is important in structure programming.

Data-centered modularity is the thing to watch in object-oriented programming.

Object-oriented programming is based on data-centered modularity

Abstract Datatypes
Slide Annotated slide Contents Index
References Textbook 

The concept datatype: A datatype is a set of values with common properties. A datatype is a classification of data that reflects the intended use of the data in a program.

We first define a datatype, and after this an abstract datatype.

The definitions given here are, to some degree, inspired by the free on-line dictionary of computing, FOLDOC at http://foldoc.org. Take a look at it!

The concept abstract datatype: An abstract datatype is a data type together with a set of operations on the values of the type. The operations hide and protect the actual representation of the data.

Program: A specification of the abstract datatype stack.

This an the other 'Programs' are examples of specifications of abstract datatypes. A specification tells what an abstract datatype is, NOT how it is implemented.

You may skip these specifications, if you are not motivated right now...


Type stack [int]
  declare
  	constructors
  		new () -> stack;
  		push (int, stack) -> stack;
  	destructors
  		pop (stack) -> stack;
  	selectors
  		top (stack) -> int;
  		isnew (stack) -> bool;
  for all
  	i in int;
  	s in stack;
  let
  	pop (new()) = error;
  	pop (push (i,s)) = s;
  	top (new()) = error;
  	top (push (i,s)) = i;
  	isnew (new()) = true;
  	isnew (push(i,s)) = false;
  end
end stack.

Program: A specification of the abstract datatype natural numbers.
Type natnum []
  declare
  	constructors
  		null () -> natnum;
  		succ (natnum) -> natnum;
  	others
                  plus(natnum,natnum) -> natnum;
                  minus(natnum, natnum) -> natnum;
                  leq(natnum,natnum) -> bool;
  for all i,j in natnum;
  let
          plus(null(),j) = j;
          plus(succ(i),j) = succ(plus(i,j));
  
          leq(null(),j) = true;
          leq(succ(i), null()) = false;
          leq(succ(i), succ(j)) = leq(i,j);
  
          minus(i, null()) = i;
          minus(null() , succ(j)) = error;
          minus(succ(i), succ(j)) = minus(i,j);
  end
end natnum.

Program: A specification of the abstract datatype boolean.
Type boolean []
  declare
    constructors
      true() -> boolean;
      false() -> boolean;
    others
      not (boolean) -> boolean;
      and (boolean, boolean) -> boolean;
      or (boolean, boolean) -> boolean;
      implies (boolean, boolean) -> boolean; 
  for all
      b, c in boolean;
    let
      not(true()) = false();
      not(false()) = true();
      and(true(),b) = b;
      and(false(),b) = false();
      or(true(),b) = true();
      or(false(),b) = b;
      implies(b,c) = or(not(b),c);
    end
end boolean.

The sample specifications of abstract datatypes illustrate a high-level and a somewhat theoretical approach

Reusability
Slide Annotated slide Contents Index
References Textbook 

More reuse - Less software to manage

In object-oriented programming, classes are meant to be reusable buildings blocks.

Inheritance between classes is - in addition - an important mechanism that boosts reusability.

  • The challenges of reusability:

    • Find

      • Where is the component, and how do I get it?

    • Understand

      • What does the component offer, and how does it fit with my own program?

    • Modify

      • Do I need to adapt the component in order to (re)use it?

    • Integrate

      • How do I actually organize and use the component together with the existing components?

The four items describe reusability challenges in general.

Action on objects
Slide Annotated slide Contents Index
References Textbook 

Ask not what the system does: Ask what it does it to!
[Bertrand Meyer]

In an objected-oriented program, most actions - as carried out by operations (instance methods) - happen on objects.

  • Actions in general

    • Implemented by procedure calls

    • Often, but not always, with parameters

  • Actions on objects

    • Activated via messages

      • A message always has a receiving object

      • A message is similar to a procedure calls with at least one actual parameter

    • A message activates an operation (a method)

      • The receiving object locates the best suited operation as responder (method lookup)

In non-object-oriented program, actions can happen without targeting an object. In an object-oriented program, such action can be implemented by class methods. Class methods are known as static methods in C#.

We act on an object obj by sending messages, see here. Either an outside object sends a message m to obj, or obj sends a message to itself.

When an object receives a message, a it will attempt to find an operation which can answer the message. In some languages, the process of locating the answering operation, is non-trivial.


Phenomena and Concepts

Phenomena and Concepts
Slide Annotated slide Contents Index
References Textbook 
We will now study concepts and phenomena, in order to get inspiration and guidance to our understanding of classes and objects.

The concept phenomenon: A phenomenon is a thing that has definite, individual existence in reality or in the mind. Anything real in itself.These are the definitions of 'phenomenon' and 'concept'. I have taken these from the PhD thesis of Jørgen Lindskov Knudsen and Kristine Stougaard Thomsen, Aarhus University. The thesis was published in the mid eighties.
The concept concept: A concept is a generalized idea of a collection of phenomena, based on knowledge of common properties of instances in the collection

Reference
  • A Conceptual Framework for Programming Languages: Jørgen Lindskov Knudsen and Kristine Stougaard Thomsen, Department of Computer Science, Aarhus Universitet, PB-192, April 1985.

  • Characteristic aspects of concepts

    • The concept name

    • The intension: The collection of properties that characterize the phenomena in the extension of the concept

    • The extension: The collection of phenomena that is covered by the concept

A concept is characterized by its name, its intension (= characteristic properties), and its extension (= the phenomena covered by the concept).

Please pay attention to these words!

Classification and exemplification
Slide Annotated slide Contents Index
References Textbook 
On this page we focus on the connection between concepts and phenomena.

The concept classify: To classify is to form a concept that covers a collection of similar phenomena.
The concept exemplify: To exemplify is to focus on a phenomenon in the extension of the concept

The relationships between concepts and phenomena. Given a concept we can identify the examples of phenomena in the extension of the concept. Given such an example, we can (the other way around) find the concept that classifies the sample phenomenon.

Aggregation and Decomposition
Slide Annotated slide Contents Index
References Textbook 
Aggregation and Decomposition is about the relationships between wholes and parts.

The concept aggregate: To aggregate is to form a concept that covers a number of parts
The concept decompose: To decompose is to split a concept into a number of parts

An illustration of aggregation and decomposition. Notice that the relations between wholes and parts are in between concepts. Thus, aggregation and decomposition show how to form new concepts from existing concepts.

Exercise 1.3. Aggregated Concepts

Take a look at the concepts which are represented by the phenomena in the room where you are located. Identify at least four aggregated concepts. Enumerate the concepts of the decomposition.

Examples of Aggregation
Slide Annotated slide Contents Index
References Textbook 

An aggregation of a Bike in terms of Frame, Wheel, Brake, etc. This illustration does not capture the number of involved parts. Thus, the diagram does not capture the number of spokes per wheel, and the number of wheels per bike. The diamond shape is UML notation for aggregation.

Generalization and Specialization
Slide Annotated slide Contents Index
References Textbook 
Generalization and Specialization is yet another way to form new concepts from existing concepts. We have already studied aggregation and decomposition as ways of making new concepts from existing concepts.

The concept generalization: Generalization forms a broader concept from a narrow concept
The concept specialization: Specialization forms a narrow concept from a broader concept

An illustration of generalization and specialization.

Exercise 1.4. Concepts and Phenomena

The purpose of this exercise is to train your abilities to distinguish between concepts and phenomena.

Decide in each of the following cases if the mentioned item is a concept or a phenomena:

  1. The door used to enter this room.
  2. Todays issue of your favorite newspaper.
  3. Your copy of today's issue of your favorite newspaper.
  4. The collection of all copies of today's newpapers
  5. Denmark.
  6. European country.
  7. The integer 7.
  8. The set of integers between 1 and 10.
  9. The set of all students who attend this course.
  10. The oldest student who attend this course.

For an item considered as a phenomenon, identify the underlying concept.

Examples of Specialization
Slide Annotated slide Contents Index
References Textbook 

A generalization/specialization hierarchy of 'Means of Transport'. All the concepts in this diagram are specialized means of transport. Notice that all the nodes in the specialization trees are concepts - not individual phenomena.

Exercise 1.5. University Concepts

In a university study, the study activities are usually structured in a number of semesters. There are two kinds of study activitities: projects and courses. At Aalborg University, there are currently two kinds of courses: Study courses (dk: studieenhedskurser) and project courses (dk: projektenhedskurser).

Characterize the concepts of university study, study activity, semester, project, course, study course, and project course relative to Aggregation/Decomposition and Generalization/Specialization.


Towards Object-oriented Programs

An object-oriented program: Hangman
Slide Annotated slide Contents Index
References Textbook 
As the end of the introductory lecture, we will approach an object-oriented Hangman program.

A sketch of an object-oriented Hangman Program.

The classes of a Hangman program. At the left hand side we see that PuzzleCollection is formed by Puzzle parts. Similarly, the HighscoreList is formed by HighScoreEntry parts. The HangManGame class if formed by three parts: PuzzleCollection, HighScoreList, and Player. Both file system and user interface aspects are "cloudy" in this diagram.

An object-oriented program: Hangman
Slide Annotated slide Contents Index
References 
Finally, in this lecture, we show incomplete sketches of the classes of the Hangman Game. The real important observation is the differences between the structured Hangman program, sketched earlier, and the object-oriented Hangman program outlined here.

Some (incomplete) classes in an object-oriented Hangman Program

Program: The class Puzzle.
abstract class Puzzle {
  
  public abstract string Category{
    get;
  } 

  public abstract string PuzzlePhrase{
    get;
  } 

  public abstract int NumberOfCharsToGuess();
}   

Program: The class HighScoreEntry.
abstract class HighScoreEntry {

  public abstract Player Player {
    get;
  } 

  public abstract int Score{
    get;
  } 
}   

Program: The class Player.
abstract class Player {

  public abstract string Name{
    get;
  }

}   

Program: The class PuzzleCollection.
abstract class PuzzleCollection {
  
  public abstract string Count{
    get;
  } 

  public abstract Puzzle this[int i]{
    get;
  }

  public abstract void Add(Puzzle p);

}   

Program: The class HighScoreList.
abstract class HighScoreList {

  /* Invariant: Entries always sorted */

  public abstract void Open(string FileName);

  public abstract string Count{
    get;
  }

  public abstract HighScoreEntry this[int i]{
    get;
  } 

  public abstract void Add(HighScoreEntry e);

  public abstract void Close();

}   

Program: The class HangmanGame.
public enum GameState {Ongoing, Won, Lost}

abstract class HangmanGame {
  /* Encapsulates the data of a single play of Hangman */

  /** Set the puzzle of this game */
  public abstract void setPuzzle(Puzzle p);

  /** Get the secret puzzle of this game */
  public abstract Puzzle CurrentPuzzle();

  /** Set the alphabet of this game - a array of all possible chars */
  public abstract void setAlphabet(char[] alphabet);

  /** Return the array of all chars not yet guessed */  
  public abstract char[] RemainingAlphabet();

  /** Return a string which represents the guessing state */
  public abstract string PuzzleOutline(Puzzle p);

  /** Call this method when the user wish to attempt ch */
  public abstract void GuessChar(char ch);

  /** Return the state of the game - Won, Lost or Ongoing */
  public abstract GameState GameState();

  /** Return the number of points obtained until now in this game */
  public abstract int HowManyPoints();

}   

References


Collected references
Contents Index
Wikipedia: Structured_programming
The OOP counterpart
A similar example: MiniBank (in Danish)
A Conceptual Framework for Programming Languages: Jørgen Lindskov Knudsen and Kristine Stougaard Thomsen, Department of Computer Science, Aarhus Universitet, PB-192, April 1985.
A similar example: MiniBank (in Danish)
The imperative counterpart

 

Chapter 1: Introduction to Object-oriented Programming
Course home     Author home     About producing this web     Previous lecture (top)     Next lecture (top)     Previous lecture (bund)     Next lecture (bund)     
Generated: February 7, 2011, 12:11:24