Theme index -- Keyboard shortcut: 'u'    Next slide in this lecture -- Keyboard shortcut: 'n'Introduction to Object-oriented Programming

A complete PDF version of the text book is now available. The PDF version is an almost complete subset of the HTML version (where only a few, long program listings have been removed). See here.

1.  From structured programming to object-oriented programming

We will assume that the reader of this material has some knowledge of imperative programming, and that the reader already has been exposed to the ideas of structured programming. More specifically, we will assume that the reader has some background in C programming. In Chapter 6 (corresponding to the second lecture of the course) we summarize the relationships between C and C#.

1.1 Structured Programming1.4 Towards Object-oriented Programming
1.2 A structured program: Hangman1.5 Abstract Datatypes
1.3 Observations about Structured Programming
 

1.1.  Structured Programming
Contents   Up Previous Next   Slide Annotated slide Aggregated slides    Subject index Program index Exercise index 

We approach object-oriented programming by reviewing the dominating programming approach prior to object-oriented programming. It is called structured programming. A brief background on structured programming, imperative programming, and - more generally - different schools of programming is provided in Focus box 1.1. I will recommend that you read the Wikipedia article about structured programming [wiki-str-pro]. It captures, very nicely, the essence of the ideas.

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 programming covers several, loosely coupled ideas. As summarized above, one of these is the use of control structures (such as if, switch/case, while and for) instead of gotos.

Use of relatively small procedures is another idea. A well-structured program should devote a single procedure to the solution of a single problem. The splitting of problems in subproblems should be reflected by breaking down a single procedure into a number of procedures. The idea of program development by stepwise refinement [Wirth71] advocates that this is done in a top-down fashion. The items below summarize the way it is done.

  • 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

Only few programmers are radical with respect to top-down structured programming. In the practical world it is probably much more typical to start somewhere in the middle, and then both work towards the top and towards the bottom.

Imperative programming, Structured programming, and Programming paradigms.

FOCUS BOX 1.1

Imperative programming is one of the four main programming paradigms. The others are functional programming, object-oriented programming, and logic programming.

Imperative programming is closely related to the way low-level machine languages work: Commands are used to change the values of locations in the memory of the computer. In high-level languages, this is achieved by use of assignment statements, which is used to change the values of variables. The assignment statement is therefore the archetypical command in imperative programming. Control structures (sequence, selection, and iteration) come on top of that together with procedural abstractions.

Programming done in the early years of the computing era (before the introduction of Algol) is often thought of as "unstructured programming". Unstructured programming is largely characterized by use of "jumping around" by means of goto commands. The introduction of if and while control structures together with procedures eliminated the need for gotos. This can be shown theoretically, but - more important - it also holds true in the practical world of imperative programming. Armed with the common control structures (if and while, for instance) and procedural abstraction, very few programmers are tempted to use a goto statement in the programs they write. Such programming, without use of goto statements, is often called structured programming.

 

1.2.  A structured program: Hangman
Contents   Up Previous Next   Slide Annotated slide Aggregated slides    Subject index Program index Exercise index 

In order to be concrete we will look at parts of a C program. The program implements a simple and rudimentary version of the well-known Hangman game. We will pretend that the program has been developed according to the structured programming ideas described in Section 1.1.

The main Hangman program, main, is shown in Program 1.1. The fragments shown in purple are postulated (in the sense discussed in Section 1.1). I.e., they are called, but not yet defined at the calling time. The postulated procedures are meant to be defined later in the program development process. Some of them are shown below.

1
2
3
4
5
6
7
8
9
10
11
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 1.1    The main function of the Hangman program.

The function getPlayerName is intended to prompt the Hangman player for his or her name. As it appears in Program 1.2 this function only uses functions from the C standard library. Therefore there are no emphasized parts in getPlayerName.

1
2
3
4
5
6
7
8
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 1.2    The function getPlayerName of main.

The function initHangman calls an additional initialization function called initPuzzles, which reads a puzzle from a text file. We will here assume that this function does not give rise to additional refinement. We do not show the implementation of initPuzzles.

1
2
3
4
void initHangman (void){
  srand(time(NULL));
  initPuzzles("puzzles.txt");
}
Program 1.3    The function initHangman of main.

askUser is a general purpose function, which was called in main in Program 1.1. We show it in Program 1.4 (only on web) and we see that it does not rely on additional functions.

1
2
3
4
5
6
7
8
9
10
11
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 1.4    The function askUser of main.

The function playHangman, seen in Program 1.5, is called by main in the outer loop in Program 1.1. playHangman contains an inner loop which is related to a single round of playing. As it appears from Program 1.5 playHangman calls a lot of additional functions (all emphasized, but not all of them included here).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
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 1.5    The function playHangman of main.

In Program 1.6 (only on web) and Program 1.7 (only on web), we show two additional functions, initGame and getPuzzle, both of which are called in playHangman in Program 1.5.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
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 1.6    The function InitGame of playHangman.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
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;
}
Program 1.7    The function getPuzzle of playHangman.

As already brought up in Section 1.1 many programmers do not strictly adhere to structured programming and top-down refinement when coding the hangman program. If you have programmed Hangman, or a similar game, it is an interesting exercise to reflect a little on the actual approach that was taken during your own development. In Section 4.1 we return to the Hangman example, restructured as an object-oriented program.


Exercise 1.1. 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.

There is no solution to this exercise


 

1.3.  Observations about Structured Programming
Contents   Up Previous Next   Slide Annotated slide Aggregated slides    Subject index Program index Exercise index 

We will now attempt to summarize some of the weaknesses of structured programming. This will lead us towards object-oriented programming.

Structured programming is not the wrong way to write programs. Similarly, object-oriented programming is not necessarily the right way. Object-oriented programming (OOP) is an alternative program development technique that often tends to be better if we deal with large programs and if we care about program reusability.

We make the following observations about structured programming:

  • 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

Let us briefly comment on each of the observations.

When we write a 'traditional' structured program it is most often the case that we have a single application in mind. This may also be the case when we write an object-oriented program. But with object-oriented programming it is more common - side by side with the development of the application - also to focus on development of program pieces that can be used and reused in different contexts.

The next observation deals with 'stable structures'. What is most stable: the overall control structure of the program, or the overall data structure of the program? The former relates to use of various control structures and to the flow procedure calls. The latter relates to data types and classes (in the sense to be discussed in Chapter 11). It is often argued that the overall program data structure changes less frequently than the overall program control structure. Therefore, it is probably better to base the program structure on decomposition of data types than on procedural decomposition.

The last observation is due to Bertrand Meyer [Meyer88]. He claims that "Real systems have no top". Let us take the Hangman program as an example. Even if it is likely that we can identify a single top of most hangman programs (in our program, main of Program 1.1) the major parts of the program should be able to survive in similar games, for instance in "Wheel of Fortune". In addition, a high score facility of Hangman should be applicable in a broad range of games. The high score part of the Hangman program may easily account for half of the total number of source lines in Hangman, and therefore it is attractive to reuse it in other similar games. The simple textual, line-oriented user interface could be replaceable by a more flexible user graphical user interface. In that way, even the simple Hangman program can easily be seen as a program with no top, or a program with multiple tops.

Readers interested in a good and extended discussion of 'the road to object-orientation' should read selected parts of Bertrand Meyers book 'Object-oriented Software Construction' [Meyer88]. The book illustrates object-oriented programming using the programming language Eiffel, and as such it is not directly applicable to the project of this course. The book is available in two versions. Either of them can be used. In my opinion 'Object-oriented Software Construction' is one of the best books about object-oriented programming.

 

1.4.  Towards Object-oriented Programming
Contents   Up Previous Next   Slide Annotated slide Aggregated slides    Subject index Program index Exercise index 

We are now turning our interests towards 'the object-oriented way'. Below we list some of the most important ideas that we must care about when we make the transition from structured programming to object-oriented programming. This discussion is, in several ways, continued in Chapter 2.

  • 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

  • Make use of a programming style that allows us to collapse the programming of objects

Our approach to object-oriented programming is continued in Chapter 2. Before that, we will clarify the concept of abstract data types.

 

1.5.  Abstract Datatypes
Contents   Up Previous Next   Slide Annotated slide Aggregated slides    Subject index Program index Exercise index 

A data type (or, for short, a type) is a set of values. All the values in a type share a number of properties. An abstract data type is a data type where we focus on the possible operations on the values in the type, in contrast to the representation of these values. This leads to the following definitions.

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.

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.

In this material, boxes on a dark blue background with white letters are intended to give precise definitions of concepts.

To strengthen our understanding of abstract data types (ADTs) we will show a few specifications of well-known data types: Stacks, natural numbers, and booleans. A specification answers "what questions", not "how questions". The details are only shown in the web version of the material.

Program 1.8 specifies what a stack is in term of the classic operations push, pop, top (and others as well). The specification is written in a (locally developed and fairly old) language called GAS. The specification does not bring forward any particular representation of a stack, and the specification does not tell how the stack operations are implemented. Stacks are represented as constructor terms, such as push(5, push (6, new ())). The equations in the specifications tells how to reduce other terms, such as pop(pop(push(5, push (6, new ())))).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
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 1.8    A specification of the abstract datatype stack.

The specification of natural numbers (0, 1, 2, ...) denotes a non-negative integer as successors of 0. Thus, the number 3 is denoted as succ(succ(succ(null())))). Given this, the equations specify the arithmetic operations plus and minus, together with the leq (less than or equal) operation.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
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 1.9    A specification of the abstract datatype natural numbers.

Finally, in Program 1.10 (only on web) we show the boolean type, where the constructors are very simple. The equations for and, or, not, and implies are shown.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
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.
Program 1.10    A specification of the abstract datatype boolean.

Please take a moment to study the abstract data type specifications, primarily to sharpen your intuition of the abstract data type concept as such.

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

 

1.6.  References
[Meyer88]Bertrand Meyer, Object-oriented software construction. Prentice Hall, 1988.
[Wirth71]Niklaus Wirth, "Program Development by Stepwise Refinement", Communications of the ACM, Vol. 14, No. 4, April 1971, pp. 221-227.
[Wiki-str-pro]Wikipedia: Structured_programming
http://en.wikipedia.org/wiki/Structured_programming

Generated: Monday February 7, 2011, 12:12:00
Theme index -- Keyboard shortcut: 'u'    Next slide in this lecture -- Keyboard shortcut: 'n'