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 Programming 1.4 Towards Object-oriented Programming 1.2 A structured program: Hangman 1.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 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.

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);
}

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;
}

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");
}

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');
}

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);
}

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();
}

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;
}

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.

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.

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.

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.

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.

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