Coursebook pr2
Coursebook pr2
List of Tables iv
Preface 1
ii
CONTENTS
iii
CONTENTS
iv
CONTENTS
v
CONTENTS
vi
CONTENTS
vii
CONTENTS
Bibliography 347
viii
List of Figures
x
LIST OF FIGURES
xi
List of Tables
7.1 The essential design rules set that are supported by OOPChecker. . . . . 190
Unlike other books in OOPD, which tend to broadly cover class design together with
all the object oriented principles (including inheritance and polymorphism), this book
believes that objects and classes should be the core issues to be discussed in detail before
introducing other principles. The major emphasis of this book on verifiable program
design specification reflects the author’s belief that a good program is a well-thought-out
program. Consequently, a good programmer is a programmer that has a design thinking
and understands its close relationship with a target programming language platform.
This book hopes to demonstrate that there is much to be discovered in the centre of the
‘galaxy’ of objects and classes!
Goals
This book is suitable for intermediate to advanced programming courses whose
main emphasis is on OOPD. The aim of the book is to systematically present the
essential concepts, techniques and tools for developing verifiable programs.
The book has three main objectives. The first objective is to introduce the program-
ming language concept and a classification of languages. This will also include the basic
principles of the modern compiler – a key language tool that processes programs written
in a language. The second objective is to explain the concept of verifiable program and
how to develop such a program. This is a generic concept that covers both procedural
and object oriented programs. The third objective is to discuss the transition from pro-
cedural to object oriented programming and describe how to develop a basic OOP. A
key compoment of this is an annotation-based class design specification method, which
helps develop the verifiable classes of an OOP.
Prerequisites
To make the most of this book, students should ideally have already completed the
following courses (or equivalent):
Introduction to programming (preferrably) in Java.
Discrete mathematics (in particular, the fundamentals of logic)
2
LIST OF TABLES
Approach
A core component of a verifiable program is verifiable procedure, whose behaviour
is well defined. Verifiable procedures exist in two forms: stand-alone and object.
Verifiable stand-alone procecure is arguably a perfect starting point for learning how
to write good behaviour description, independent of any concerns with object oriented
design. This book, thus, takes the approach by Liskov and Guttag [20] to first explain
the concept of verifiable program in the context of procedural design. Once this concept
has been grapsed, the book introduces OOP, highlighting the key transitional concepts
to be learnt. Among these is the adaptation of the verifiable procedure concept to define
verifiable object procedure (a.k.a operation). This then becomes a basis to define the
development method for verifiable OOP.
The book next discusses the fundamental class design issues and apply these to,
more broadly, define a number of basic class design patterns. Although the design
patterns introduced in this book are at the introductory level, they help lay a foundation
for learning more sophisticated patterns at a later stage. To demonstrate the practicality
of the development method and design patterns, the book applies these to develop object
oriented solutions for two key abstract data types (list and tree).
Java is chosen as the programming language used in the book because it is a popular
platform-neutral object oriented programming language. However, we believe that the
concepts and methods discussed in this book can be applied to other OOPLs (e.g. C#)
that support similar language features.
3
LIST OF TABLES
Exercises
To help practise the concepts introduced in the book, each book chapter contains a
set of exercises. The book is also accompanied by an instructor workbook that contains
answers to and instruction guides for the exercises.
Notation
The essential notational style used in the book is described below:
Technical concepts and Java code are written in fixed font. For example, class
Student refers to the Java class named “Student”.
The singular and plural forms of a technical concept may be used to refer to
instance(s) (i.e. object(s)) of this concept. For example, the phrase “a Student
named Le Van Anh” refers to a specific object of class Student, while the plural
form Students refers more generally to the objects of this class.
Names of software frameworks and software are written in Roman All Caps Font.
4
Chapter 1
Overview of Programming Languages
Objectives
" Understand the programming language landscape and the spectrum of program-
ming languages
" Understand the common programming language features
" Explain the underlying principle that makes a good programming language
" Understand the motivation for studying programming language
1https://scholar.google.com
1.1 Programming Language Landscape: An Overview
Overflow2 lists the 25 most popular PLs among the developers. This list is quite diverse,
covering the two major types of languages: declarative and imperative.
This section gives an overview of the programming language landscape by first
explaining why there is a such a high number of languages. It then introduces a language
classification, which organises the languages based on their computational model.
2https://insights.stackoverflow.com/survey/2020
6
1.1 Programming Language Landscape: An Overview
Declarative PL
In principle, a declarative PL focuses on expressing a solution in terms of what
steps need to be taken. The PL platform is responsible for converting those into the
detailed instructions, suitable for being performed by the computer. The figure list
five sub-types of declarative PL, which include functional, data flow, template-based
and logic. A functional PL is one whose considers function as the main construct and
provides mechanism for writing programs recursively in terms of functions. A program
is a top-level function which is incrementally refined in terms of smaller ones, and each
of these is further refined in terms of even smaller ones. This process stops when all the
functions are those provided by the PL. Examples of functional PL are Lisp, ML and
Haskell [28].
A data flow PL treats a program as flows of data that pass through processing nodes.
Each node is triggered by an input flow of data and its output (if any) would be sent to
the next node(s). The nodes can potentially execute in parallel. Examples of data flow
PL include Id, Sisal (which evolves from Id) and Val [28].
A logic PL has its root in predicate logic. It considers a program as a set of logic
statements, describing relationships among the domain terms, and attempts to determine
(search for) values that satisfy the program. Examples of logic PL include Prolog,
Structured Query Language (SQL) and the XSLT scripting language [28].
Example 1.1 Declarative PL
Listing 1.1, which was adapted from a wiki page of the language3, lists the definition
of the function named gcd in Haskell. This function takes takes as input two integers
a and b and computes their greatest common divisor4. The function definition uses the
fast Euclidean method5 of computing the GCD. This method uses a fact that GCD also
3https://wiki.haskell.org/99_questions/Solutions/32
4https://mathworld.wolfram.com/GreatestCommonDivisor.html
5https://mathworld.wolfram.com/EuclideanAlgorithm.html
7
1.1 Programming Language Landscape: An Overview
divides the smaller number of the two input (b in this case) and the remainder (mod) of
the division ab .
The first line lists the type signature declaration of the function, which takes two
integer inputs returns one integer output. The next three lines show the function definition
which consists of two cases. The first case is applied when b = 0. In this case, we
cannot divide a by b but can easily see that result is abs a (abs means to take the
absolute value). The second case is applied when b \neq 0. In this case, GCD (a, b)
is recursively defined in terms of GCD(b, a mod b).
Listing 1.1: Program GCD in Haskell
1 gcd :: Integer -> Integer -> Integer
2 gcd a b
3 | b == 0 = abs a
4 | otherwise = myGCD b (a ‘mod‘ b)
Listing 1.2 shows the same program written in the Prolog language. The program
consists in three propositions that establish the truth about gcd(a, b, g). The first
two terms (a, b) are input while the third term (g) is the GCD to be determined. The
first proposition means that gcd(a, b, g)= true if a = b = g (same number). The
second proposition means that gcd(a, b, g)= true if a > b and gcd(c, b, g)=
true, for c = a - b. The third proposition states gcd(a, b, g)= true if a < b and
gcd(c, a, g)= true for c = b - a.
Listing 1.2: Program GCD in Prolog
1 gcd(A,B,G) :- A = B, G = A.
2 gcd(A,B,G) :- A > B, C is A-B, gcd(C,B,G).
3 gcd(A,B,G) :- B > A, C is B-A, gcd(C,A,G).
Although the logic rules of Prolog are different from Haskell’s functional ones, it is
clear from both programs that they consist in only high-level terms and their relationships
and do not concern how the these are processed by the PL platform. In particular, we see
no presence of variable modification in both programs. Internally, the PL platform would
need to use some kind of algorithm which manipulate values in order to determine the
GCD. However, these details are hidden from the programmer. This is a stark contrast
to imperative programs, which we will discuss below.
8
1.1 Programming Language Landscape: An Overview
Imperative PL
An imperative PL describes a solution in terms of how to perform a task. Figure 1.1
lists three sub-types of imperative PL, including von neumann, scripting and object-
oriented. Von neumann is the most successful type of language, which includes popular
PLs of the past (such as as Fortran, Ada 83 and C) and continues to influence many popular
PLs of the presence (such as Java and C#). A von neumann PL is designed to directly
mimics the Von Neumann computer architecture. At the abstract level (see Figure 1.2),
this architecture considers the computer as consisting three abstract components (the
processing unit (CPU), run-time memory and I/O devices) and information exchange
mechanisms between these components. What influences Von neumann PL is the
relationship between CPU and memory. CPU holds the basic instructions that are
performed on the data stored in memory. A key design feature of von neumann PL is the
declaration of variables (memory storage of data) and a systematic modification of these
variables (using various types of statement) with the intention to achieve the intended
program outcome.
9
1.1 Programming Language Landscape: An Overview
10
1.2 Programming Language Features
6 b = b - a;
7 }
8 return a;
9 }
11
1.2 Programming Language Features
1.2.4 Standardisation
This is the extent to which the PL specification is standardised. A PL specification
is a formal description of its syntax and semantics. Because a PL can potentially
be implemented by a diversed community of vendors, its specification needs to be
standardised so that all the implementations can process programs written in the language
the same way. This is needed to ensure the code portability across platforms. It is also
very important that the PL specification is frequently revised and updated as the language
evolves so that vendors can update their implementations accordingly. A good example
of standardisation can be found in the case of the Java language specification mentioned
above. The specification is made available online and frequently updated to ensure its
currency.
6https://docs.oracle.com/javase/specs/
7http://openjdk.java.net/
12
1.3 What Makes a Good Programming Language?
8https://common-lisp.net/
9https://docs.oracle.com/javase/8/docs/technotes/tools/index.html
10https://www.python.org/
11https://www.php.net/
13
1.4 Why Study Programming Languages?
these two features: expressive power and ease of use (see Section 1.2). On the other
hand, the PL implementor views a PL as a mean to write instructions to be executed in
a computing platform. Their main desire is thus ease of implementation and execution
efficiency.
Reconciling these two conflicting groups of features is not easy. It is often the
case that more expressive power requires more computing power and less efficient
code. For example, declarative PLs are usually slower in performance, compared to
the imperative counterparts [28]. Making the right trade-offs is not exact science and
requires experience and lots of experimentation. This also explains why there is no such
thing as a perfect PL and that most PLs evolve towards achieving a better compromise
over time.
K Chapter 1 Exercise k
The main objective of the exercises in this chapter is to review the basis of Java pro-
gramming. This is needed to learn other Java programming concepts and techniques in
the rest of the book.
1. Working with a Java IDE.
Starting from this chapter, you will use an Integrated Development Environment
(IDE) to write, compile and run your Java programs. This is easier than having
to manually use the commands javac and java on the terminal. In this book, we
14
1.4 Why Study Programming Languages?
will use the Eclipse IDE12. Other commonly used IDEs include Netbeans13 and
IntelliJ IDEA14.
Most IDEs use the concept of a project to organise your Java programs. A project
is basically a collection of related Java programs. Generally, you will need to
create two projects: one for the source code that you will be given in the lecures
and the other is for tutorials.
Open Eclipse from the Programs menu of your computer. Create two projects: (1)
project src for holding the source code of the lectures and (2) project tutorials
for the tutorials. For example, Figure 1.3 shows how to achieve this in Eclipse.
Note how project PR2tutorials reference the PR2 project in its “Java Build Path”
properties. You will use project tutorials for doing the exercises. For example,
create a package named tute1 for week 1’s exercises, tute1 for week 2, and so
on.
2. Working with source code package utils. The source code that comes with
this book, which hereforth will be referred to as the attached source code, use
of a number of shared Java classes in a package named utils. These are utility
classes that you would need to use for some of the exercises. For this chapter, for
instance, you will need to use a class named TextIO.java.
Extract the package utils from the attached source code and follow the instruc-
12https://www.eclipse.org
13https://netbeans.org
14https://www.jetbrains.com/idea/
15
1.4 Why Study Programming Languages?
tions of your IDE to create this package in your project. In a class that needs to
use TextIO, add one of these lines (depending how you want to call the methods
of this class):
import static utils.TextIO.*;
OR
import utils.TextIO;
3. Working with class TextIO. The following exercises in [6] help practise class
TextIO. You will do these exercises as part of the Java review (below).
Chapter 2: 2.3-5 and 2.7.
Chapter 3: 3.3-5.
4. Working with basic data types (1).
Listing 1.5: Program Interest
1 /**
2 * This class implements a simple program that
3 * will compute the amount of interest that is
4 * earned on 17,000 invested at an interest
5 * rate of 0.07 for one year. The interest and
6 * the value of the investment after one year are
7 * printed to standard output.
8 */
9 public class Interest {
10 public static void main(String[] args) {
11 /* Declare the variables. */
12 double principal;
13 double rate;
14 double interest;
15 /* Do the computations. */
16 principal = 17000;
17 rate = 0.07;
18 interest = principal * rate;
19 principal = principal + interest;
20 /* Output the results. */
21 System.out.print("The interest earned is ");
22 System.out.println(interest);
23 System.out.print("The value of the investment after one
year is ");
16
1.4 Why Study Programming Languages?
24 System.out.println(principal);
25 } // end of main()
26 } // end of class Interest
17
1.4 Why Study Programming Languages?
19 System.out.print("Sum: ");
20 System.out.println(sum);
21 } // end of main()
22 } // end of class Array
18
1.4 Why Study Programming Languages?
18 String w2 = str.substring(16,18);
19 boolean equal = w1.equals(w2);
20 /* Print out the results */
21 System.out.println("string: " + str);
22 System.out.println("length: " + len);
23 System.out.println("word 1: " + w1);
24 System.out.println("word 2: " + w2);
25 System.out.println("word 1 is equal to word 2? " +
equal);
26 System.out.println("characters: " + charsAsString);
27 } // end of main()
28
19
Chapter 2
The Java Programming Language
Objectives
" Understand programming language syntax and semantics and the relationship
between them
" Explain the context-free grammar rule structure and a diagram notation for
representing this structure
" Describe the Java language syntax rule
" Explain the syntax rules of the core Java language constructs, including identifer,
method declaration, block, statement and expression
In this chapter, we will study the Java programming language specification with an
aim to understand its features at a depth below the usage level. We will discuss language
and semantics as two components of a language specification and focus on the Java
syntax. We will learn the grammar structure of and how to interpret the Java syntax.
We illustrate the syntax using some of the core language constructs (identifier, method
declaration, block, statement and expression).
2.1 Motivation
We discussed in Chapter 1 the need for the programmer to study a PL’s features to
a level that would allow her to make informed decisions about which feature(s) are most
suitable for solving a particular problem. To achieve this, however, requires knowing
all the alternative features and the pros and cons of each. For example, let us consider
questions such as “how many ways can an array be defined?” and “how many ways can
a method be defined?”.
We can learn the different ways through reading code examples about arrays and
methods. Although this is the approach that is most common among programmers when
they learn to use a new langugage, it can not help find satisfactory answers to the questions
above. The only approach that does is to study the language specification syntax about
array and method declarations. This syntax, much like the natural language syntax,
describes the valid grammar rules for each language construct. These rules define the set
of all the valid sentences that can be written in the language concerning the construct.
2.2 Language Syntax and Semantics
In this chapter, we will briefly introduce this approach and demonstrate it with the Java
language.
2.2.1 Syntax
The Cambridge online dictionary has two definitions for syntax1. First in the NL
context, it is “. . . the grammatical arrangement of words in a sentence”. Second in the
computing context, it is defined somewhat similarly as “. . . the structure of statements or
elements in a computer language”. More generally, a language syntax [15, 28] consists in
a set of rules that specify how sentences are constructed from a given alphabet (the valid
characters set). The construction is typically defined incrementally: from characters to
words then words to sentences. Let us illustrate this with an analogy in NL. After that,
we will look at a PL example.
Example 2.1 Natural language text
Consider this excerpt from the preface of the Java language specification [11]:
“Java SE 8 represents the single largest evolution of the Java language in its history.
A relatively small number of features - lambda expressions, method references, and
functional interfaces - combine to offer a programming model that fuses the object-
oriented and functional styles”. This paragraph is broken down into sentences, words
and characters as shown in Figure 2.1.
1https://dictionary.cambridge.org/dictionary/english/syntax
21
2.2 Language Syntax and Semantics
Let us next consider an example Java program and, for illustration purpose, uses
the NL’s approach above to mechanically break down its text into elements. We will
study a precise approach for the Java language syntax later in this chapter.
Example 2.2 Java program text
Listing 2.1: Java program Gcd.java
1 public static void main(String[] args) {
2 int i = TextIO.getInt(),
3 j = TextIO.getInt();
4 while (i != j) {
5 if (i > j) i = i - j;
6 else j = j - i;
7 }
8 TextIO.putln(i);
9 }
Figure 2.2: Syntax analysis of the Java program Gcd in Listing 2.1.
The Java program named Gcd presented in Listing 2.1 is broken down into sentences,
words and characters as shown in Figure 2.2.
22
2.2 Language Syntax and Semantics
are defined using one of two types of grammar: regular and context-free grammars [28].
Further, these two grammars are defined in terms of four basic types of rules:
concatenation: sequentially combining elements
selection (one of, a.k.a alternation [28]): selection among a finite set of elements
repeation (a.k.a Kleene closure [28]): repeating an element a number of times
recursion: defining an element in terms simpler elements of the same type
Regular grammar consists of regular expressions that are defined in terms of the
first three rules, while context-free grammar (CFG) is constructed using all four types
of rules. We will focus on CFG in this book. Before illustrating these grammars, let us
briefly introduce the grammar rule notation.
23
2.2 Language Syntax and Semantics
CFG terminology
In CFG, in particular, each rule is called a production and the LHS symbol of every
production is called a nonterminal. The nonterminal of the first production is called the
start symbol, because it is the starting point of and, thus, represents the entire grammar.
The opposite of nonterminal is the type of symbol, called terminal. This includes the
pre-defined tokens of the grammar, which are not defined by productions. Terminals can
only appear on the RHS of productions.
Example 2.3 Regular and context-free grammars
To illustrate regular and context-free grammars, let us build two example languages,
one with each type of grammar. The first example is the regular grammar shown in
Listing 2.2, which is adopted from Chapter 2 of [28]. This grammar constructs a
language of natural numbers. It is a regular grammar because no rules use recursion,
that is the LHS of every rule does not appear in the RHS of any other rules.
Listing 2.2: Regular grammar for natural numbers
1 digit → (one of) 0 1 2 3 4 5 6 7 8 9
2 non_zero_digit → (one of) 1 2 3 4 5 6 7 8 9
3 natural_number → non_zero_digit {digit}
The second example is the CFG shown in Listing 2.3. In addition to the three
basic rules of regular grammar, this grammar uses recursion in the third rule to define
binary_number in terms of itself (appearing also in the RHS). It can be seen without
difficulty that this grammar defines a language containing the following subset of binary
numbers: {10, 11, 1010 . . . , 1111 . . . , 10111011 . . . , 11101110 . . . }.
Listing 2.3: CFG of a binary numbers subset
1 binary → (one of) 0 1
2 starts_one → 1 binary
3 binary_number → (one of) starts_one {binary_number}
Example 2.4 Java syntax grammar
To complete the syntax grammar example in this section, we show in Figure 2.3
the Java syntax rule for the local variable token. We will discuss the Java syn-
tax in more detail later in this chapter. As shown in the figure, the token name is
LocalVariableDeclarationStatement, which is defined in terms of the symbol
LocalVariableDeclaration followed by ‘;’. The grammar rule for this symbol is
also displayed in the figure. There are other rules that define components of this rule.
24
2.2 Language Syntax and Semantics
Figure 2.3: The context-free grammar rule for variable declaration in Java.
25
2.2 Language Syntax and Semantics
The number of edges defined for one production rule equals the number of
terms in the RHS that match the code statement
Example 2.5 Syntax Tree
26
2.2 Language Syntax and Semantics
2.2.5 Semantics
In general, the semantics component of a PL specifies the meaning of a program
written in the language. In principle, this meaning defines the values that are assigned
to the program symbols. Without these values, it is impossible to differentiate between
different symbols in the same language and to produce the expected program output.
A NL setence may be grammatically correct but does not make a valid sense
(i.e. incorrect meaning). What determines correctness depends on the context of use.
Similarly, syntactically-correct program may be semantically wrong. Let us illustrate
these with an NL example and a Java program example.
Example 2.7 A semantically-wrong NL sentence
In the context of the JLS excerpt presented in Example 2.1, the following sentence
has an incorrect meaning, despite the fact that its syntax is valid:
“Java SE 8 represents the evolution of the English language.”
The two semantic errors highlighted in the sentence are: (1) “evolution” (should be
a “single largest evolution”) and “English language” (should be “Java language”).
Example 2.8 A semantically-wrong Java program
In the context of the program Gcd of Example 2.2, the following Java statement is
incorrect, despite the fact that it does not violate any Java syntax rules. As such, this
statement will be reported at compile time as have errors.
27
2.3 The Java Language Syntax
28
2.3 The Java Language Syntax
Operator:
(one of)
= > < ! ~ ? : ->== >= <= != && || ++ --+ - *
/ & | ^ % << >> >>>+= -= *= /= &= |= ^= %=
<<= >>= >>>=
29
2.4 Identifier
2.4 Identifier
In this and the remaining sections of this chapter, we will study the syntax structures
of a number of core Java constructs. You are probably already familiar with these
constructs from previous programming courses. However, since our objective here is to
dive deeper into the syntax of the language, you are invited to revisit these constructs by
going through these materials.
Definition 2.1. Identifier
An identifier (§3.8) is an unlimited-length sequence of Java letters and Java digits,
the first of which must be a Java letter. ♣
30
2.5 Method Declaration
JavaLetter {JavaLetterOrDigit}
JavaLetter :
(one of) ‘_’ ‘$’ NonDigitUnicodeLetter
JavaLetterOrDigit :
(one of) JavaLetter Digit
Digit :
(one of) 0 1 2 3 4 5 6 7 8 9
Note that the productions for Javaletter and JavaLetterOrDigit have been
rewritten from the informal definition in JLS [11] to conform to the CFG notation.
Example 2.9 Identifier
According to the identifier’s definition, the following strings are valid identifiers:
id, id1, _id1 and $id1. However, these strings are invalid identifiers: 1id, i!d, @id
and #id.
Definition 2.2
A method (§8.4) declares executable code that can be invoked, passing a fixed
number of values as arguments. ♣
MethodModifier :
(one of)
Annotation public protected private
abstract static final synchronized native strictfp
Result :
31
2.6 Blocks and Statements
UnannType
void
Throws :
throws ExceptionTypeList
ExceptionTypeList :
ExceptionType { , ExceptionType}
MethodBody :
Block
;
FormalParameterList :
ReceiverParameter
FormalParameters , LastFormalParameter
LastFormalParameter
FormalParameters :
FormalParameter { , FormalParameter}
ReceiverParameter { , FormalParameter}
FormalParameter :
{VariableModifier} UnannType VariableDeclaratorId
Figure 2.6 is the NBD for the declaration of a method main. The NBD shows
structure of the top-level production rule for MethodDeclaration. Figure 2.7 shows
the NBD for the method header part of the method declaration shown in Figure 2.6.
Figure 2.8 shows the NBD for another method declaration example that throws an
exception.
32
2.6 Blocks and Statements
33
2.6 Blocks and Statements
VariableModifier :
(one of)
Annotation final
UnannType :
UnannPrimitiveType
UnannReferenceType
UnannPrimitiveType :
34
2.6 Blocks and Statements
NumericType
boolean
UnannReferenceType :
UnannClassOrInterfaceType
UnannTypeVariable
UnannArrayType
UnannClassOrInterfaceType :
UnannClassType
UnannInterfaceType
UnannClassType :
Identifier [TypeArguments]
UnannClassOrInterfaceType . {Annotation}
Identifier [TypeArguments]
UnannInterfaceType :
UnannClassType
UnannTypeVariable :
Identifier
UnannArrayType :
UnannPrimitiveType Dims
UnannClassOrInterfaceType Dims
UnannTypeVariable Dims
Dims :
{Annotation} [ ] {{Annotation} [ ] }
VariableInitializer :
Expression
ArrayInitializer
35
2.6 Blocks and Statements
ArrayInitializer :
{ [VariableInitializerList] [ , ] }
VariableInitializerList :
VariableInitializer { , VariableInitializer}
Figure 2.9 shows the NBD for a local variable declaration statement of two variables
i and j in the block forming the body of the same method main that we used in Figure 2.6
of Example 2.10.
2.6.2 Statement
Java requires that the else clause of an if statement belongs to the innermost if
statement. This is to support the case of an nested if statement. This leads to two rules
for statement: statement and statement-no-short-if. These are defined in Listing 2.11.
Listing 2.11: Statement
Statement :
StatementWithoutTrailingSubstatement
LabeledStatement
IfThenStatement
IfThenElseStatement
WhileStatement
ForStatement
StatementNoShortIf :
StatementWithoutTrailingSubstatement
LabeledStatementNoShortIf
36
2.6 Blocks and Statements
IfThenElseStatementNoShortIf
WhileStatementNoShortIf
ForStatementNoShortIf
StatementWithoutTrailingSubstatement :
Block
EmptyStatement
ExpressionStatement
AssertStatement
SwitchStatement
DoStatement
BreakStatement
ContinueStatement
ReturnStatement
SynchronizedStatement
ThrowStatement
TryStatement
LabeledStatement :
Identifier : Statement
LabeledStatementNoShortIf :
Identifier : StatementNoShortIf
2.6.3 if Statement
Definition 2.5
The if statement (§14.9) allows conditional execution of a statement or a condi-
tional choice of two statements, executing one or the other but not both. ♣
37
2.6 Blocks and Statements
Figure 2.10 shows the NBD for an if statement in the body of the same method
main that we used in Figure 2.6 of Example 2.10. This statement has an else clause.
Definition 2.6
The while statement (§14.12) executes a boolean Expression and a Statement
repeatedly until the value of the Expression is false.
♣
The production rule for the while statement is shown in Listing 2.13.
Listing 2.13: The while statement
WhileStatement :
while ( Expression ) Statement
WhileStatementNoShortIf :
while ( Expression ) StatementNoShortIf
38
2.6 Blocks and Statements
ForStatementNoShortIf :
BasicForStatementNoShortIf
EnhancedForStatementNoShortIf
BasicForStatement :
for ( [ForInit] ; [Expression] ; [ForUpdate] ) Statement
BasicForStatementNoShortIf :
for ( [ForInit] ; [Expression] ; [ForUpdate] )
StatementNoShortIf
ForInit :
StatementExpressionList
LocalVariableDeclaration
ForUpdate :
StatementExpressionList
39
2.6 Blocks and Statements
StatementExpressionList :
StatementExpression { , StatementExpression}
Figure 2.12 shows the NBD for the basic for statement that computes the running
total of a sequence of numbers.
EnhancedForStatementNoShortIf :
for ( {VariableModifier} UnannType VariableDeclaratorId
: Expression )
StatementNoShortIf
40
2.6 Blocks and Statements
Example 2.16 The switch statement Figure 2.14 shows the NBD for a switch statement
that prints to the console a message characterising an integer n.
Question What is/are missing from the diagram?
41
2.7 Expression
2.7 Expression
Definition 2.9
The result of evaluating expression denotes one of three things:
a variable (§4.12)
a value (§4.2, §4.3)
nothing (the expression is void): a method invocation that invokes a method
that does not return a value (i.e. declared void) ♣
Expression has many different forms. In this section, we will focus on expres-
sion name and some forms of primary expression. The production rule is shown in
Listing 2.17.
Listing 2.17: Expression name
ExpressionName :
Identifier
AmbiguousName . Identifier
AmbiguousName :
Identifier
AmbiguousName . Identifier
42
2.7 Expression
literals
object creations
field accesses
method invocations
method references
array accesses
parenthesized expression
The production rule for primary expression is shown in Listing 2.18.
Listing 2.18: Primary expression
Primary :
PrimaryNoNewArray
ArrayCreationExpression
PrimaryNoNewArray :
Literal
ClassLiteral
this
TypeName . this
( Expression )
ClassInstanceCreationExpression
FieldAccess
ArrayAccess
MethodInvocation
MethodReference
2.7.2 Literal
43
2.7 Expression
BooleanLiteral
CharacterLiteral
StringLiteral
NullLiteral
ArgumentList:
Expression { , Expression}
44
2.7 Expression
45
2.7 Expression
K Chapter 2 Exercise k
The objective of these exercises is to practise analysing the Java programming language
syntax.
1. Use the syntax tree to explain the grammar of the following Java code. Be as
specific as you can about the name of the nonterminal (LHS) that matches each
code element.
46
2.7 Expression
2. Use the grammar syntax tree to explain the grammar of the following Java code.
Be as specific as you can about the name of the nonterminal (LHS) that matches
each code element.
1 static float min(int[] a) {
2 // TODO: implements this
3 }
3. Use the grammar syntax tree to explain the grammar of the following Java code.
Be as specific as you can about the name of the nonterminal (LHS) that matches
each code element.
1 static int nextCount(int i) {
2 int j;
3 { j = i + 1;
4 }
5 return j;
6 }
4. Use the grammar syntax tree to explain the grammar of the following Java code.
Be as specific as you can about the name of the nonterminal (LHS) that matches
each code element.
1 private static float min(float a, float b) {
2 float min;
3 min = a <= b ? a : b;
4 return min;
5 }
5. Use the grammar syntax tree to explain the grammar of the following Java code.
Be as specific as you can about the name of the nonterminal (LHS) that matches
each code element.
1 private static float min(float a, float b) {
2 float min;
3 if (a <= b) {
47
2.7 Expression
4 min = a;
5 } else {
6 min = b;
7 }
8
9 return min;
10 }
6. Use the grammar syntax tree to explain the grammar of the following Java code.
Be as specific as you can about the name of the nonterminal (LHS) that matches
each code element.
1 static int search(int[] a, int x) {
2 for (int i = 0; i < a.length; i++) {
3 if (x == a[i+0]) return i;
4 }
5 return -1;
6 }
7. Use the grammar syntax tree to explain the grammar of the following Java code.
Be as specific as you can about the name of the nonterminal (LHS) that matches
each code element.
1 public static void main(String[] args) {
2 int[] a = {1, 1, 2, 3, 5, 8, 13};
3 int x = TextIO.getInt();
4 int isAt = search(a, x);
5 System.out.printf("%d is in %s at %d", x, a, isAt);
6 }
8. Are the following productions correct? Explain why or why not. If yes, what do
you think is a benefit of this definition? If no, how do you fix them?
MethodDeclaration :
MethodModifiers MethodHeader MethodBody
MethodModifiers :
{MethodModifier}
48
2.7 Expression
1 0B001100010
2 0b001_110_001L
3 1b0_0_1L
4 0B012L
5 1B0L
6 0B0 0 1L
49
Chapter 3
Introduction to Compiler and Virtual Machine
Objectives
" Explain what a compiler is and its basic operations.
" Describe a virtual machine in general and the Java virtual machine, in particular.
" Explain the process involved in executing a Java program.
In this chapter, we will take a brief look at how computer processes programs
that are written to run on it. Conceptually, the computer would automate the task of
analysing the program text, which we manualy performed on the Java programs in the
previous chapter. A key component that is responsible for performing this task in is the
compiler. We will attempt to understand how the compiler works and, in particular,
look at a modern type of compiler called virtual machine – the kind of compiler that is
used for Java.
Compiler is a complex topic, a whole book has been written on it. It is typically
studied in depth in a programming language design course. In the space of this one
chapter, our purpose therefore is simply to undertand what a compiler is and a high-
level description of the compiler operations. These operations employ some of the
fundamental algorithms that are often used in designing complex real-world programs.
3.1 Compiler
known as run time), the target program typically accepts certain inputs and generates
some outputs.
While the abtract compiler view in Figure 3.1 is useful for conceptual understanding,
it does not reflect the actual compiler implementation strategies. This is because, in
practice, it is not often the case that there is a clear separation between the compilation
(compile-time) and execution (run-time) of a program. While this is true for many
traditional languages (e.g. C/C++ and Fortran), the separation is not absolute for more
current languages (e.g. C#, Java, Perl, Python and Ruby). In scripting languages, such
as Perl, Python and Ruby, some if not most of the compilation tasks are delayed until
the program is executed. A more practical view, therefore, is to consider compilation as
being performed at different levels.
Scott [28] suggests that most PLs employ a mixture of the two compilation levels
shown in Figure 3.2. Some PLs place more emphasis on one level than on the other.
Others, such as Java, focus on both levels.
Level 1 – translation: the source program is translated (by a translator compo-
nent) into an intermediate program. This program is written in a machine-independent
language (LI ), which can be run on different machines. The intermediate program is not
51
3.1 Compiler
yet executable. It must be processed by another component called the virtual machine
before it can be executed.
Level 2: interpretation: a virtual machine (VM) takes the intermediate program
and the user input (if any), translates the intermediate program into a target program
(in machine language) and executes it. Note that the target program is not displayed in
Figure 3.2 because it is created as part of the VM’s run-time environment and, as such,
not written out physically to a file (like in traditional compilation).
Question What is a key benefit of the 2-level compilation?
Listing 3.1 shows a simple hello world Java program. This program goes through
two compilation levels as follows:
1. Translation:
input: chap2/Hello.java
translator: javac chap2/Hello.java
intermediate program output: chap2/Hello.class
2. Interpretation:
input: chap2.Hello (the chap2.Hello.class above)
interpreter: java chap2.Hello
output: Hello World!
We will study the two compilation levels of Java later in this chapter.
52
3.1 Compiler
The operations can be organised into two groups: front end and back end. The
front end includes the first 3 operations, namely lexical, syntax and semantic analysis.
The back end includes target code generation and code improvement.
Question Do you see any familiar components (that you have used before in program-
ming) being mentioned in the diagram?
53
3.1 Compiler
then used as input for syntactic analysis. Syntactic analysis, which is performed by the
parser component, checks the program structure for any violation of the grammar rules.
It generates as output a syntax tree (called parse tree or concrete syntax tree in [28]).
This is to be distinguished from another form of syntax tree, called abstract syntax tree,
which is produced by the semantic analysis operation.
Any violations of the lexical and syntax grammar rules that are detected by the
scanner and parser will result in compilation being stopped and error messages being
displayed. A typical lexical error is invalid token; e.g. an identifier includes an invalid
character. A typical syntactic error is invalid token sequence; e.g. no line separator
character ‘;’ to end a statement.
Example 3.3 Lexical analysis
Listing 3.3: Lexical analysis of Gcd (Source: [28])
int main ( ) { int i =
getint ( ) , j = getint
(
) ; while ( i != j )
{ if ( i > j ) i
= i - j ; else j =
j - i ; } putint (
i
) ; }
Listing 3.3 shows the result of lexical analysis for program Gcd. From the character
stream of the program text, namely (‘i’, ‘n’, ‘t’, ‘’, ‘m’, ‘a’, ‘i’, ‘n’,. . . ), the scanner
produces a list of tokens. These include keywords (e.g. int, if, while, etc.), separators
(e.g. ‘(’, ‘)’, etc.), identifiers (e.g. main getint, i and j) and operators (e.g. ‘>’, ‘=’,
‘!=’, etc.).
Example 3.4 Syntactic analysis: Gcd
Figure 3.4 shows the partial syntactic analysis for program Gcd. It displays two
syntax trees for the statement while (i != j) (tree A) and the statement putint (i);
(tree B). The arrow lines in both figures show mappings between the identifiers in both
statements to the corresponding leaf nodes on the trees.
54
3.1 Compiler
Figure 3.4: Partial syntactic analysis for the while and putint statements in Gcd (Adapted
from [28]).
commonly takes the form of an abstract syntax tree (AST). The main difference between
AST and the syntax tree produced by the parser is that all of the grammar-specific internal
nodes are removed and that the leaf nodes are annotated with type information.
Semantic analyser records the data types of identifiers and expressions and ensure
that they are used correctly throughout the program. To achieve this in a way that
would assist the later operations to perform their tasks, the analyser constructs a shared
data structure called symbol table. Each entry in the table maps an identifier to such
information as data type, internal structure, and access scope. Example semantic rules
that are checked for the C language using this table include [28]:
identifier is declared before use
correct use of identifier (e.g. using function name instead of a variable name in a
function invocation)
function call with correct parameter list
a function that has a non-void return type actually returns a value
As discussed in Chapter 2, semantic rules can be checked either at compile time or
at run time. Each alternative has its pros and cons. More compile-time check means
less run-time check and, thus, better execution performance. In contrast, more run-time
check means more execution flexibility but at the expense of a slower performance. In
general, AST represents the intermediate program that is passed from the front end to
the back end. In some specific compilers, other intermediate forms would be generated
from the AST for the back end.
Example 3.5 Semantic analysis: Gcd.
Figure 3.5 shows the semantic analysis of program Gcd. The AST is displayed at
the top and the symbol table is presented at the bottom left corner. The symbol table lists
55
3.1 Compiler
the symbols that appear in the AST together with their type definitions. For example,
symbols #1 and #2 are data types (void and int, respectively), which are used to define
the type definition of other symbols. Symbol #3 (getint) has a function type with one
parameter (2) that has the type int. The AST differs from the syntax tree produced by
the parser in Figure 3.4 in that the grammar-specific internal nodes are removed and that
the leaf nodes are annotated with references to the corresponding identifer entries in the
symbol table.
56
3.2 Virtual Machine
Figure 3.6: Partial assembly code for program Gcd (Adapted from [28]).
Figure 3.5 shows a partial assembly code that is generated for program Gcd. Note
that -8(%ebp) refers to the memory location that appears 8 bytes before the location
whose address is stored in in ebp.
57
3.3 Java Virtual Machine
architecture and necessary shared services for user programs. Among the key services
are I/O, scheduling and memory management.
There are two types of VM: system VM and process VM [28]. System VM emulates
the actual computer hardware and functions as a platform for executing alternative OSes.
It is often used to install ‘guest’ OSes on an existing (host) OS. An example system VM
is the Oracle’s open-source Virtual Box1.
Process VM emulates only a subset of the hardware functionalities, needed to
execute programs at single-user processes. While system VM is tied to OS development,
process VM is linked to PL development. Both state-of-the-art versions of Java and C#
come with process VMs that allow programs to be easily portable to different platforms.
As explained in Section 3.1.2 the Java platform performs a 2-level compilation for
each Java program: compile (through the command javac) and interpretation (through
the command java). Figure 3.8 illustrates these two steps with the simple Hello World
program. Note that the Java’s byte code has been standardised so that the source program
does not even need to be written in the Java language. The only requirement for the
1https://www.virtualbox.org
58
3.3 Java Virtual Machine
program to be executable on the JVM is that it strictly conforms to the byte code file
format.
The initial versions of JVM were purely interpreted and were thus quite slow in
performance. Starting from Java 2 (first released in 1998), JVM implements a just-
in-time (JIT) compilation mechanism, by which the program byte code is interpreted
immediately before each execution. How can that be achieved?
JIT employs a number of techniques to its front and back end operations. First, the
front end operations are simplified because:
lexical analysis is not needed because byte code is binary and not textual.
syntactic analysis is simplified due to the descriptive nature of class file. Important
structural properties (e.g. data types and parameter list) have already been added
to the byte code by the source-to-byte-code translator.
code improvement is simplified because certain improvements may already have
been performed by the source-to-byte-code translator.
Second, performances of the back end operations are enhanced by using the fol-
lowing techniques:
lazy linker: referenced libraries are only loaded and linked into the program when
needed
dynamic (hot spot) compilation: dynamically determines frequently used code
paths and compile them directly into machine code. This is performed in parallel
to executing the program and the compiled code is ready for execution when
needed.
machine code caching: the machine code of a class file may be cached for subse-
quent runs of the program.
59
3.3 Java Virtual Machine
Global storage is shared by all threads of execution and created and destroyed
with the JVM. This includes method area, constant pool and heap
Per-thread storage is created and destroyed with each thread. This includes base
registers, method call stack and (optional) native method call stack.
A Java program potentially consists of one or more threads of execution. Each
thread is an object of the class Thread. We will give a brief overview of the key storage
areas below.
Heap
Heap is a shared memory area for all threads of execution. It is used for holding
objects (including arrays) after they have been created and while they are used by threads.
To conserve memory, objects that are not in use (no variables pointing to it) are removed
from thread automatically by the garbage collection process of the JVM. To ensure
objects have consistent data when they are accessed by different threads, Java provides
a locking mechanism to allow programs manage concurrent accesses to an object.
60
3.3 Java Virtual Machine
constant pool
method table
Example 3.7 Class file of program HelloWorld
Listing 3.4 shows a partial Java bytecode that is generated for the HelloWorld
program. It was generated by the Java deassembler program (javap), which was
invoked as follows:
javap -verbose chap2.Hello
Listing 3.5 shows a partial constant pool that is generated as part of the Java byte
code in Listing 3.4. To ease reading, names of the key sections are highlighted in the
listings. Further, the comments inserted for the key elements should help explain what
they mean.
Listing 3.4: Java bytecode of HelloWorld
Compiled from "Hello.java"
class chap2.Hello
SourceFile: "Hello.java"
minor version: 0
major version: 51
flags: ACC_SUPER
Constant pool:
const #1 = Class #2; // chap2/Hello
...
public static void main(java.lang.String[]);
descriptor: ([Ljava/lang/String;)V
flags: ACC_PUBLIC, ACC_STATIC
Code:
stack=2, locals=1, args_size=1
0: getstatic #16 // Field
java/lang/System.out:Ljava/io/PrintStream;
3: ldc #22 // String Hello, world!
5: invokevirtual #24 // Method
java/io/PrintStream.println:(Ljava/lang/String;)V
8: return
LineNumberTable:
line 5: 0
line 6: 8
LocalVariableTable:
Start Length Slot Name Signature
61
3.4 Java Program Execution
0 9 0 args [Ljava/lang/String;
...
62
3.4 Java Program Execution
Method main may be invoked with command line arguments. If specified, these
arguments are captured in the String[] array parameter of the method. For example,
the following command invokes HelloWorld.main with 3 input strings “say”, “hello”,
“world!”:
java HelloWorld say hello world!
Listing 3.6 explains how to process the input arguments of method main.
Listing 3.6: Processing input arguments
1 class HelloWorld {
2 public static void main(String[] args) {
3 for (int i = 0; i < args.length; i++) {
4 System.out.println(args[i]);
5 }
6 }
7 }
Note that if lazy loading is applied then the linking step may not load the additional
classes immediately. Listing 3.7 shows an example of referencing another class (Student
) within a program. This class is either lazily loaded by the JVM or loaded immediately
as part of linking HelloWorld into the run-time library.
Listing 3.7: Referencing another class
63
3.4 Java Program Execution
1 class HelloWorld {
2 public static void main(String[] args) {
3 Student s = null; // a student
4 // initialise s
5 System.out.println("Hello " + s);
6 }
7 }
The main thread may start additional threads of execution via the Thread objects
that are created in the program. Listing 3.8 shows an example of creating two Thread
objects to display different hello messages.
Listing 3.8: Starting multiple threads with class Thread
1 public class MultithreadHello {
2 public static void main(String[] args) {
3 for (int i = 0; i < 3; i++) { // starts 3 threads
4 final int id = i;
5 new Thread(() -> {
6 System.out.println("Hello thread: " + id);
7 }).start();
8 }
9 }
10 }
K Chapter 3 Exercise k
The objective of these exercises is to practise using the parser component of the Java
compiler to analyse and write Java programs.
1. Given below is a program named Ex1 that uses a java parser tool, named JavaParser
[31], to parse the program text of the class Hello and produce the standard
Java source code text. The in-line comments give information about how to use
JavaParser.
(a). Run this program to produce the source code that is listed immediately below
the program.
Note: You need to:
add to the class path the library file named javaparser-core-3.0.1.
jar (provided in the resources/lib folder)
64
3.4 Java Program Execution
use import statements to import the necessary classes into your program
(b). Change the program text (i.e. value of the variable progText) by removing
the semi-colon (‘;’) at the end of the print statement. Rerun the program
and record what happens.
(c). Change the program text by removing the word “main”. Rerun the program
and record what happens.
1 import com.github.javaparser.JavaParser;
2 import com.github.javaparser.ast.CompilationUnit;
3 public class Ex1 {
4 public static void main(String[] args) {
5 // program text
6 String progText = "class Hello { "
7 + "public static void main(String[] args) { "
8 + " System.out.println(\"Hello world!\"); "
9 + "} "
10 + "}";
11 // parse the program text
12 CompilationUnit codeUnit = JavaParser.parse(progText);
13 // obtain the generated source code
14 System.out.println(codeUnit);
15 }
16 }
2. Based on program Ex1, create a new program named Ex2 which reads the same
program text from a file named Hello.j, parses it and print the source code to the
standard output. Run this program and make sure that it produces the same output
as Ex1.
Hint: import the enhanced TextIOPlus class (provided in the library file resources
/t3-utils.jar) to read a text file. This class requires the class utils.TextIO
(available in the attached source code). For example, to read the file named
65
3.4 Java Program Execution
Hello.j which is located in the same package folder as the class Ex2, you write:
TextIOPlus.readTextFileContent(Ex2.class, "Hello.j").
3. Use the enhanced TextIOPlus to write a new program named Ex3 which reads
the program text from an URL, parses it and print the source code to the standard
output.
The URL of the program text file Hello.j is as follows: https://sites.
google.com/site/lemduc/home/ppl/Hello.j?attredirects=0&d=1
Hint: use the method TextIOPlus.readTextFromURL.
4. Write a program named ProgWriter (abbr. program writer), which simplifies the
process of writing a program using a pre-defined template. This template contains
certain fields, whose values are to be specified by the user from the standard input.
Take a program that you have written and change it into a template to be used
for ProgWriter. You could store the template in a file or simply in a string-
typed constant. For example, the program Hello.java would be turned into
the following template. This template contains two fields: _ClassName_ and
_Greeting_.
public class _ClassName_ {
public static void main(String[] args) {
System.out.println(_Getting_);
}
}
66
3.4 Java Program Execution
MethodDeclaration
VoidType: void
VoidType: void
NameExpr: main
Parameter: String[] args
Parameter: String[] args
ClassOrInterfaceType: String
ClassOrInterfaceType: String
VariableDeclaratorId: args
BlockStmt
ExpressionStmt: System.out.println("Hello world!");
MethodCallExpr: System.out.println("Hello world!")
FieldAccessExpr: System.out
NameExpr: System
NameExpr: out
NameExpr: println
StringLiteralExpr: "Hello world!"
6. Use the Java disassembler tool (javap) to inspect the byte code of one of the
programs that you wrote in the previous tasks. The disassembler is located under
the bin directory of your JDK’s installation directory. Run the disassembler three
times using the following command-line arguments: -c, -verbose. Observe and
compare the outputs. For example, if program Ex1 is created in the package named
t3, you would type:
javap t3.Ex1
javap -c t3.Ex1
67
Chapter 4
Verifiable Program Development
Objectives
" Understand the concept of verifiable program and its development.
" Differentiate and explain the relationship between between design specification
and implementation.
" Create design specification of a verifiable procedure.
" Design a verifiable program from its procedures.
" Implement a verifiable procedure and verifiable program in Java.
In the previous chapters, we studied the basis of the Java programming language
and used it to write programs. In this chapter, we will take a step back to study how to
properly develop a program in Java. We aim to achieve verifiable programs, which are
programs whose behaviours are well-defined and whose implemented codes can later
be checked for correctness. Verifiable programs ease understanding, evaluation and
maintenance.
To develop verifiable programs, we adapt a stream-lined, structured program devel-
opment approach, which involves two basic activities: design and coding. The objective
of design is to identify and specify the procedural abstractions needed to perform the re-
quired tasks. The objective of implementation is then to write code for each abstraction,
as a procedure in a target language such as Java, that satisfies its specification. Although
we only focus in this chapter on developing procedural programs, the approach can also
be applied to the development of object-oriented programs. We will study this in a later
chapter.
The rest of the chapter is structured as follows. First, we introduce the basic
terminology and define the concept of verifiable procedure – a basic building block of
a verifiable program. Next, we explain how to design and implement such verifiable
procedure. After this, we define verifiable program and the program development
approach. In this, we discuss in detail how to design and implement a verifiable program.
We demonstrate the approach with an application example.
4.1 Basic Terminology
4.1.1 Procedure
In Java, procedure is called method. To avoid confusion and to keep the terminology
consistent, we will use the general term ‘procedure’ throughout this note to refer to
Java methods. In the context of this note, we will focus on stand-alone procedures,
i.e. procedures that exist in the context of the class, independently from its objects. A
stand-alone procedure is invoked directly through the class in which it is defined. It
is defined with the keyword static. In a later topic, we will study another type of
procedure, called object procedure (or operation). This procedure must be invoked via
an object of the class.
Example 4.1 Procedures search and sqrt
The mapping between input and output of the procedure search is precisely the
mathematical function IntegerArrays × Z → Z where IntegerArrays represent all
the valid integer arrays and Z is the set of integers.
Similarly, procedure sqrt is defined by the mathematical function R × R → R.
Example 4.2 Procedure sort.
Procedure sort takes an input array a and arranges its elements in ascending order.
What is interesting here is that this procedure does not return any value so we cannot
represent the output in the same way as the two procedures in the Example 4.1. In this
case, mapping is a transformation function that modifies the input.
69
4.1 Basic Terminology
Behaviour
Behaviour of a procedure is a concise description of a single action or task that it
needs to perform. It describes what the procedure does, not how it does it. Thus, the
behaviour of a procedure needs to be made clear before its implementation can begin.
Technically, the behaviour is written using high-level statements (e.g. in natural language
or a form of mathematical logic), which are free from details of how the procedure is
implemented. Behaviour definition is important not only for the client module that uses
the procedure but also for the programmer who implements the procedure. The client
can use the procedure based on its behaviour. The programmer writes the code that
satisfies the behaviour.
Therefore, it is beneficial to write the behaviour definition as part of the procedure
header. Without this, the user would have to read the code to try to work out what the
procedure does. This is generally harder than reading the behaviour definition.
Example 4.3 Procedures search and sqrt with behaviour definition.
The comment lines that appear before the header lines of the two procedures
search and sqrt below describe their behaviours. We will refer to these descriptions as
behaviour descriptions. In both examples, the behaviour states properties of the output
in terms of the input, without giving details about how the properties are achieved.
For example, search’s behaviour states the property x in a but does not say the actual
steps taken to determine this. This allows the programmer to have the flexibility of
choosing the suitable algorithm in the implementation.
70
4.1 Basic Terminology
Implementation
The implementation of a procedure states how the procedure performs its behaviour
in a specific programming language. In general, different implementations exist for the
same behaviour.
Example 4.4 Alternative implementations of procedure search.
The three different implementations of procedure search shown in Listing 4.1
have the same behaviour. The first implementation loops sequentially through the array
from the first index. The second implementation uses a similar loop but starts from
the last index backward. The third implementation uses two loops: one loops over the
even-numbered indices and the other loops over the odd-numbered indices. And so on,
we can construct many other implementation variants in this fashion.
Listing 4.1: Alternative implementations of procedure search
1 // 1st implementation: forward
2 public static int search1(int[] a, int x) {
3 int i = 0;
4 for (int e : a) {
5 if (e == x) {
6 return i;
7 }
8 i++;
9 }
10 }
11
71
4.1 Basic Terminology
24 if (a[i] == x) {
25 return i;
26 }
27 }
28
For example, procedure search in Example 4.1 is a total procedure. It does not
place any constraints on the input array a and the input number x. The behaviour is
specified for both cases: x in a and x not in a.
Definition 4.3. Partial procedure
A partial procedure is a procedure whose behaviour is not specified for some
values in the input domains. ♣
72
4.1 Basic Terminology
property is not explicitly specified. It had to be deduced from the behaviour text. Later
in the chapter, we will study a design specification approach that helps make this more
explicit in the behaviour.
Each type of procedure has its use in practice but not without trade-offs. Total
procedure is safer but requires more effort to construct and generally takes longer to
execute. Total procedures handle all input cases and thus are less likely to be broken by
an invalid input. Partial procedures can make assumptions (constraints) on the input and
thus have simpler and more efficient code. It is suggested therefore that total procedures
should be used in the public contexts, while the partial counterparts be used in more
restrictive contexts or when efficiency has a high priority.
Note that PA is not the only programming abstraction that exists. There are other,
higher-level programming abstractions, that result from other methods of conceptuali-
sation. One abstraction, which we will study later in this module, is data abstraction.
Other abstractions involve some combination of procedural and data abstractions. We
will study them in a more advanced module.
Technically, PA is a culmination of two types of abstraction [20]. The first abstrac-
tion type, named abstraction by parameterisation, is familiar to most programmers
because it is the one used in the Java’s procedure syntax. In this abstraction, a task/action
is viewed in terms of the types of the input and output. The second abstraction type,
named abstraction by specification, views a task/action in terms of the separation of
and the relationship between behaviour and implementation. This is an important type of
abstraction but it is often overlooked. It forms the basis for the procedural and program
design approach that we will study later in this chapter.
73
4.1 Basic Terminology
74
4.2 Verifiable Procedure Design
the behaviour of the procedure (what it does). It states the swap action, which in this
context means to swap the positions of the elements of the input array. However, it does
not give details of how this swapping can be carried out. One way is to use a temporary
array, another way is to use a temporary variable, and many other approaches similar to
these.
75
4.3 Design Specification Language
deliverables of the previous phase. In the coding phase, verification is used to verify
that a module’s code satisfies its design specification. It is therefore important that the
specification is propertly defined and accessible to the programmer. In this section, we
will discuss how to write a well-defined specification for the procedures that make up a
program. In Section 4.4, we will generalise this for program design specification.
Why do we care about well-defined behaviour? Why can not we just write a simple
comment to describe the behaviour as shown in the procedure swap of Example 4.5. In
that example, is the behaviour description “swap two numbers” clear enough for the
programmer to understand to the extent that would prevent them from making logic-
related mistakes in coding it? There are two limitations of that behaviour description:
1. What conditions (if any) do we need to impose on the parameter xy in order for
the behaviour to be valid?
2. What exactly does “swap two numbers” mean in terms of the parameter xy?
A well-defined behaviour description is one that should address these. This descrip-
tion, which is called design specification, makes more explicit and precise the behaviour
so that the client can correctly understand and rely on the behaviour. On the other hand,
the programmer is able to correctly implement the procedure. The correctness of the
written code can be verified with regards to (w.r.t ) the specification. In this book, we
call a procedure that has a well-defined specification a verifiable procedure.
Definition 4.5. Verifiable procedure
Verifiable procedure is a procedure that has a well-defined design specification. ♣
76
4.3 Design Specification Language
Unlike the Liskov’s approach, however, this book uses the block comment format to
write the specification. This format is supported by most modern OOPLs (such as Java,
C#). Further, this book uses text annotations within the comment to more explicitly
mark the specification sections.
77
4.3 Design Specification Language
Listing 4.3 shows the design specification of procedure swap. This specification
overcomes the limitations discussed earlier about the unstructured description in Exam-
ple 4.5. First, the @requires clause states the pre-conditions on the parameter xy, that it
must be defined and contains exactly two elements. Second, the @modifies clause states
clearly that xy is modified and the modification is specified precisely in the @effects
clause.
Note that in this case, the pre- and post-conditions can be written directly and
precisely in logical notation. We will discuss this notation in the next section. The logical
statement in the @effects means that the value of xy after invoking the behaviour is an
array that is constructed from two elements: xy_0[1] and xy_0[0]. Here, xy_0 refers
to the value of xy at entry into the procedure (i.e. before the behaviour is executed).
What this means, therefore, is that the elements of xy are swapped for the two elements
that were in it initially.
Example 4.8 Design specification of procedure intMax.
Listing 4.4: Procedure intMax
1 /**
2 * Determines the greater of two numbers
3 * @effects <pre>
4 * (result = x0 \/ result = y0) /\
5 * (result >= x0 /\ result >= y0)
6 * </pre>
7 */
8 public static int intMax(int x, int y)
Listing 4.4 shows the design specification of the procedure intMax. This spec-
ification has no pre-condition and side-effects and so the annotations @requires and
78
4.3 Design Specification Language
@modifies are omitted. The post-condition describes exactly what the max value is:
one of the two numbers which is greater than or equal to both of them.
To illustrate the use of HTML tags in the Java-style comment, we include in this
specification the HTML tag <pre>, which wraps around the content of @effects. This
means that this content is assumed to be pre-formatted and is presented raw to the user.
This tag is useful for technical content that may contain special characters.
Example 4.9 Behaviour Specification: Sum.main, sum.
In order to prepare for program design specification that will be discussed later,
we introduce here the design specifications of two procedures of a program named Sum.
The design specifications of two procedures are clear enough to understand what they
do without explain what the program does.
Listing 4.5: Two procedures of program Sum
1 /**
2 * the main procedure
3 * @effects
4 * obtain some real numbers from the user
5 * {@link #sum(float[])}: compute the sum
6 * of the numbers
7 * print the sum
8 */
9 public static void main(String[] args)
10
11 /**
12 * Determines the sum of an array of real numbers.
13 * @requires <tt>a is not null</tt>
14 * @effects <pre>
15 * return the sum of the array elements, i.e.
16 * result = a[0]+...+a[a.length-1]
17 * </pre>
18 */
19 public static float sum(float[] a)
Listing 4.5 shows the design specifications of two procedures of program Sum:
main and sum. Procedure sum’s pre-conditions state that the input array must be defined.
This procedure has no side-effects. The post-conditions state what the sum means: the
arithmetic sum of elements of the input array.
79
4.3 Design Specification Language
80
4.4 Verifiable Program Design
81
4.4 Verifiable Program Design
82
4.4 Verifiable Program Design
4.4.1 Preliminaries
At the program level, the design makes use of the following terms:
Procedural program
Program behaviour
Program structure
Functional procedure
Program and functional classes
Definition 4.6. Procedural program
A procedural program is a set of procedures, exactly one of which is the procedure
main, and a set of procedure invocations. Procedure main is used to start the
program. ♣
Because of its special role, procedure main has a fixed syntax in most OOPLs.
Listing 4.6 shows two very similar syntax of this procedure that are used in Java and C#.
In Java, procedure main must be defined using the fixed syntax shown in the listing. The
C#’s syntax requires that the method is named Main but is a bit more flexible in that the
method’s modifier needs not be public and that the method can return an int value.
Listing 4.6: Syntax of procedure main in Java and C#
1 // Java’s syntax
2 public static void main(String[] args)
3 // C#’s syntax
4 static void Main(String[] args)
5 static int Main(String[] args)
In program development, an important step often performed before writing the de-
tailed design specification is analysing the program requirement to construct its structure.
83
4.4 Verifiable Program Design
Note that procedure graph and its context are necessary to make clear the boundary
of each procedure. Without them, it would be possible, for instance, to mistake the
program graph for being owned by just the method main. To visually draw the program
structure, this book adapts the flowchart symbols1 [21] and introduces two new symbols.
The first symbol is a dashed box for procedure context and the second symbol is a
dashed arrow that represents the returned value from a called procedure. Note that for
illustration purpose, we embed the context of a called procedure directly in the program
graph of the calling procedure. In the general case where a procedure may be invoked
by several other procedures, its context is drawn as a separate graph and is linked to the
program graph of the calling procedures.
Example 4.11 Program Sum
Figure 4.3 graphically shows the structure of a program named Sum. We will study
this program design and its code in more detail later in the chapter. What is of interest here
is the result of analysing the program requirement to build the overall program structure.
In this example, we will informally describe the procedures in natural language. As
shown in the figure, the program structure consists in three procedure graphs, one owned
by main, the other two are owned by getNumbers and read (respectively). Nodes
are arranged from top down, in invocation order. This arrangement is intuitive in that
it shows the increasing level of detail. Procedure main is placed at the top (level 0).
1https://en.wikipedia.org/wiki/Flowchart
84
4.4 Verifiable Program Design
Three procedures invoked by main are positioned at level 1. There are three directed
edges connecting main to these procedures. Procedure getNumbers obtains some real
numbers from the user via the standard input. Procedure sum computes the sum of
these numbers. Procedure putln is then invoked to display the result on the standard
output. This last procedure is defined in an external library named TextIO and is thus
represented by a different symbol (a rectangle with 2 vertical lines on two sides).
At levels 2 and 3 of the program structure are two procedures that are used by
getNumbers to perform its task. Procedure read (invoked directly by getNumbers)
reads a real number from the user. Procedure getlnFloat (invoked by read) actually
obtains the real number from the standard input. It is defined in the library TextIO.
Since procedure read returns a value and it only invokes procedure getlnFloat, this
latter node is connected to a border of read’s context via a return edge.
Definition 4.9. Functional procedure
A functional procedure is a procedure other than the procedure main. Functional
procedure thus performs the domain-specific tasks. A internal functional proce-
dure is one that is defined in the program, an external functional procedure is
defined in an external library. ♣
A procedure is defined in a class, which gives rise to two terms used for class.
Definition 4.10. Functional class
Functional class is a class that only contains internal functional procedures. ♣
Note that in an OOPL, only one procedure main can be used to execute a program.
The class that contains this procedure is called the program class.
85
4.4 Verifiable Program Design
Figure 4.4 shows another structure of program Sum that contains three classes. Each
class includes a group of related internal procedures. For example, class MultiSum is the
program class. Two other classes (InputHandler and Numbers) are functional classes,
each of which contains a group of procedures that realise the class’s behaviour.
Finally, we introduce the term verifiable program.
Definition 4.12. Verifiable program.
Verifiable program is a procedural program all of whose procedures are verifiable. ♣
86
4.4 Verifiable Program Design
The design steps are defined based on the OOPL program structure discussed in
Definition 4.8. The subsequent sections will explain these steps in detail.
87
4.4 Verifiable Program Design
(e.g. @author) may also be used to give more information about the class.
Example 4.13 Program class specification
Listing 4.7 gives the specification of the program class Sum. The structure of this
program was described in Example 4.11. In this example, the program name is rather
obvious. The @overview annotation of the header comment describes the expected
program behaviour of this program.
Listing 4.7: Program class Sum
1 /**
2 * @overview a program that computes the sum of real numbers
3 * obtained from the user via standard input
4 */
5 public class Sum {
6 //
7 }
88
4.4 Verifiable Program Design
5 * i.e.
6 * {@link #getNumbers()}: obtain some real numbers from the user
7 * {@link #sum(float[])}: compute the sum of the numbers
8 * {@link TextIO#putln()}: print the sum
9 */
10 public static void main(String[] args)
9 /**
10 * Obtain an array of real numbers from the standard input.
11 * @effects
89
4.5 Implementation in Java
21 /**
22 * Read a real number from the standard input.
23 * @effects
24 * do
25 * f = {@link TextIO#getlnFloat()}:
26 * prompt user to enter a number
27 * while f is invalid
28 * return f
29 */
30 private static float read()
90
4.5 Implementation in Java
Note that coding steps 2 and 3 can also be performed in the reverse invocation
order. The order of these two steps determine the coding strategy. The strategy specified
in Definition 4.15 is the top-down strategy, which conforms to the top-down program
structure. In contrast, the bottom-up strategy involves coding the procedures in reverse
invocation order. Although both strategies arrive at the same outcome, there is a key
point of difference. That is, in the top-down strategy, the invoked procedures are initially
coded as stubs [20]. A stub procedure has a dummy body and is used to satisfy the
invocation requirement of a calling procedure. The body of a stub will eventually be
written when the coding process gets to it.
Example 4.16 Program Sum coding
Listing 4.10 shows the Java code of program Sum. The design specifications of all
but procedure sum are omitted. Refer to Listing 4.7 for the complete design specification
of this program. Procedure sum, in particular, uses a while loop to iterate over the input
array elements and add them to the running total (variable s). Alternatively, we could
easily implement the same loop using the for statement. Although the code of this
procedure is perhaps one of the most basic pieces of code that a beginning programmer
would write, it quite clearly demonstrates the advantage having the design specification.
First, the code is longer than the @effects clause in the specification. This clause
simply writes the sum using the fundamental addition rule. The client can take for
granted that this rule is correct. Second, it is not immediately clear whether the code
is correct. Formally proving the correctness of a loop requires using logical induction,
which is not trivial!
Listing 4.10: The Java code of program Sum
1 package chap4.implement;
2 import utils.TextIO;
3 /**
4 * @overview A program that computes the sum of real numbers
5 * that are obtained from the user via the standard input
6 * @author ducmle
7 */
8 public class Sum {
9 /**
91
4.5 Implementation in Java
10 * (omitted)
11 */
12 public static void main(String[] args) {
13 float s = 0;
14 float[] r = getNumbers();
15 s = sum(r);
16 TextIO.putln("sum = " + s);
17 }
18
19 /**
20 * Determine the sum of array of real numbers
21 * @requires a is not null
22 * @effects return the sum of a’s elements,
23 * i.e. result = a[0] + ... + a[a.length-1]
24 */
25 private static float sum(float[] a) {
26 int n = 0;
27 float s = 0;
28 while (n < a.length) {
29 s = s + a[n];
30 n++;
31 }
32 return s;
33 }
34
35 /**
36 * (omitted)
37 */
38 private static float[] getNumbers() {
39 // ask user for how many numbers she needs
40 // prompt the user for the number of numbers needed
41 TextIO.putln("How many numbers do you need?");
42 int n = TextIO.getlnInt();
43 while (n < 0) {
44 TextIO.putln("Invalid number: " + n + ". Please reenter.");
45 n = TextIO.getlnInt();
92
4.6 Application Example: Coffee Tin Game
46 }
47 // initialise an array whose size is the specified number
48 float[] a = new float[n];
49 // fill a with numbers
50 float f;
51 for (int i = 0; i < n; i++) {
52 f = read();
53 a[i] = f;
54 }
55 return a;
56 }
57
58 /**
59 * (omitted)
60 */
61 private static float read() {
62 TextIO.putln("Enter next real number:");
63 float num = TextIO.getlnFloat();
64 return num;
65 }
66 }
93
4.6 Application Example: Coffee Tin Game
always one bean left in the tin and that its color can be determined regardless of the game
move. The objective of program CoffeeTinGame, therefore, is to execute the game and
to determine its outcome.
Listing 4.11: A high-level algorithm of the Coffee tin game.
// what is the colour of the final bean?
while at least two beans in tin do
take out any two beans
if they are the same colour
throw them both away
put a Blue Mountain bean back in
else
throw away the blue one
put the green one back
4.6.2 Analysis
Let us analyse the game moves to show how the color of the last bean is determined.
The tin’s content (t) at any given time is represented by the numbers of blues (m) and
greens (n): t = m + n. A game move is determined by colours of the two beans taken
out, which can be one of the followings: BB, BG, GG. These game moves change the
tin’s content as follows:
BB: m + n → (m − 1) + n
BG: m + n → (m − 1) + n
GG: m + n → (m + 1) + (n − 2)
Question What do you notice about n and the total number of beans (m + n) ?
94
4.6 Application Example: Coffee Tin Game
two beans are required to perform the move but t is decreased by one, i.e. the game
is stopped when there is one bean left in the tin
The last bean can be either G or B, but which is it? If it is green then it must be that
mod(n, 2) = 1; otherwise mod(n, 2) = 0. Thus, the last bean property (its color) can
be formulated based
on the initial number of greens (n0 ) as follows:
G, if mod(n0 , 2) = 1
last bean =
B, if mod(n , 2) = 0
0
Program Structure
Figure 4.5 shows the structure of program CoffeeTinGame. It has 3 procedure
graphs whose contexts are drawn in the figure. The first graph is owned by procedure
main, the second is owned by tinGame and the third is own by takeTwo.
The procedure graph of tinGame contains a new symbol ( ), which we did not
discuss earlier in this chapter. This symbol represents decision node [21], which has one
incoming edge and two or more outgoing edges. The outgoing edges represent different
decision outcomes. There are two decision nodes in the graph. The first node appears
after the invocation of procedure hasAtLeastTwoBeans. It has two outcomes Y and N.
If Y (i.e. tin has at least 2 beans) then takeTwo is invoked to obtain two beans from tin.
If N then anyBean is invoked, which is followed by a return statement to return any bean
left in tin.
The second decision node appears after takeTwo’s invocation. It has 3 outcomes,
representing the 3 cases of the beans taken out. All three cases cause an invocation of
putIn (using a different input each time). This invocation is to put one bean back into
the tin. After this, execution repeats at the invocation of hasAtLeastTwoBeans.
Last but not least, the procedure graph of takeTwo contains an invocation to
procedure takeOne. The reason we introduce this procedure is because it is performed
twice per game move to get 2 beans needed for the move.
4.6.3 Design
In this step, the design specifications of each procedure and the entire program are
written. Listing 4.12 shows the brief design specification of program CoffeeTinGame.
It lists the procedure headers but omits the behaviour descriptions. These descriptions
will be presented for each procedure in the subsections below.
Listing 4.12: Brief design specification of program CoffeeTinGame
1 package chap4.design;
95
4.6 Application Example: Coffee Tin Game
2 /**
3 * @overview A program that performs the coffee tin game on a
4 * tin of beans and display result on the standard output.
5 */
6 public class CoffeeTinGame {
7 /** (omitted) */
8 public static void main(String[] args)
9
10 /** (omitted) */
11 private static char tinGame(char[] tin)
12
13 /** (omitted) */
14 private static boolean hasAtLeastTwoBeans(char[] tin)
15
16 /** (omitted) */
17 private static char[] takeTwo(char[] tin)
18
19 /** (omitted) */
20 private static char takeOne(char[] tin)
21
22 /** (omitted) */
23 private static void putIn(char[] tin, char bean)
96
4.6 Application Example: Coffee Tin Game
24
25 /** (omitted) */
26 private static char anyBean(char[] tin)
27 }
Procedure main
The basic tasks of procedure main are to initialise a tin of coffee beans, call tinGame
to perform the game and then call and TextIO.putf to display the result. In addition
to these, procedure main contains two calls to TextIO.putf to display the tin content
before and after the game. This is to let the user see the effect of the game on tin. Further,
it uses the property of the last bean to check the value returned from tinGame. Although
this task is not essential to the program, it is used here to test the implementation of the
procedure tinGame.
Procedure tinGame
97
4.6 Application Example: Coffee Tin Game
5 * @modifies tin
6 * @effects <pre>
7 * repeat take out two beans from tin
8 * if same colour
9 * throw both away, put one blue bean back
10 * else
11 * put green bean back
12 * until tin has less than 2 beans left
13 * let p0 = initial number of green beans
14 * if p0 = 1
15 * result = ‘G’
16 * else
17 * result = ‘B’
18 * </pre>
19 */
20 private static char tinGame(char[] tin)
This procedure has a parameter char[] tin, which represents the coffee tin. Each
bean in the tin is represented either by the character ‘B’ (blue) or the character ‘G’ (green).
The return type of the procedure is thus also a char, which represents colour of the last
bean.
The @requires clause states that tin is initialised with at least one bean. In Java,
a variable is null if it is an object-typed variable that has not been initialised. We will
study objects in more detail later. It suffices to know that arrays are objects.
The procedure has a side-effect on tin, which is that it removes beans from the
tin. The exact nature of the modification is described in @effects. This clause consists
in two parts. The first part is basically high-level pseudocode in Listing 4.11, which
describes the behaviour of the game. The second part, which starts with the let
statement, makes precise the expected result of the procedure. This is determined based
on the property of the last bean.
Procedure hasAtLeastTwoBeans
This procedure takes a tin and returns true or false depending on whether or
not it has at least two beans. Listing 4.15 shows the design specification.
Listing 4.15: Design specification of procedure hasAtLeastTwoBeans
1 /**
98
4.6 Application Example: Coffee Tin Game
2 * @effects
3 * if tin has at least two beans
4 * return true
5 * else
6 * return false
7 */
8 private static boolean hasAtLeastTwoBeans(char[] tin)
Procedure takeTwo
This procedure takes out two beans from tin and returns them in a char array.
Listing 4.16 shows the design specification. The @requires clause states a condition
that tin must contain at least two beans. This assumption can be made in the context of
tinGame, at the point after hasAtLeastTwoBeans has been performed. The @effects
clause makes precise the behaviour by showing two invocations on takeOne, which pull
out the two beans.
Listing 4.16: Design specification of procedure takeTwo
1 /**
2 * @requires tin has at least 2 beans left
3 * @modifies tin
4 * @effects
5 * remove any two beans from tin and return them
6 * i.e.
7 * char b1 = {@link takeOne(char[])} on tin
8 * char b2 = {@link takeOne(char[])} on tin
9 * result = [b1, b2]
10 */
11 private static char[] takeTwo(char[] tin)
Procedure takeOne
This procedure takes out any bean from tin and returns it. Listing 4.17 shows the
design specification of the procedure. The @requires clause states a condition that tin
has at least one bean left. This assumption can be made in the context of procedure
takeTwo, which initially assumes that at least two beans are left in tin. As shown
99
4.6 Application Example: Coffee Tin Game
above, procedure takeTwo has two invocations on takeOne, which guarantee that the
condition holds before each invocation.
Listing 4.17: Design specification of procedure takeOne
1 /**
2 * @requires tin has at least one bean
3 * @modifies tin
4 * @effects
5 * remove any bean from tin and return it
6 */
7 private static char takeOne(char[] tin)
Procedure putIn
This procedure puts back bean into tin at any vacant position. Listing 4.18 shows
the design specification of the procedure. The @requires clause states a condition that
tin must have such vacant positions. This assumption can be made in the context of
procedure tinGame, at the point after takeTwo has been invoked.
Listing 4.18: Design specification of procedure putIn
1 /**
2 * @requires tin has vacant positions for new beans
3 * @modifies tin
4 * @effects
5 * place bean into any vacant position in tin
6 */
7 private static void putIn(char[] tin, char bean)
Procedure anyBean
This procedure looks in tin to find any bean left in it and return such bean. If no
beans are found then it returns NULL, which is the Unicode’s null character. Listing 4.19
shows the design specification of the procedure.
Listing 4.19: Design specification of procedure anyBean
1 /**
2 * @effects
3 * if there are beans in tin
4 * return any such bean
100
4.6 Application Example: Coffee Tin Game
5 * else
6 * return NULL
7 */
8 private static char anyBean(char[] tin)
4.6.4 Code
Listing 4.20 shows the Java code of the program CoffeeTinGame.
Listing 4.20: The Java code of program CoffeeTinGame
1 package chap4.implement;
2 import java.util.Arrays;
3 import utils.TextIO;
4 **
5 * @overview A program that performs the coffee tin game on a
6 * tin of beans and display result on the standard output.
7 *
8 * @author dmle
9 */
10 public class CoffeeTinGame {
11 /** constant value for the green bean*/
12 private static final char GREEN = ’G’;
13 /** constant value for the blue bean*/
14 private static final char BLUE = ’B’;
15 /** constant for removed beans */
16 private static final char REMOVED = ’-’;
17 /** the null character*/
18 private static final char NULL = ’\u0000’;
19
20 /**
21 * the main procedure
22 * @effects
23 * initialise a coffee tin
24 * {@link TextIO#putf(String, Object...)}: print the tin
content
25 * {@link @tinGame(char[])}: perform the coffee tin game on
tin
101
4.6 Application Example: Coffee Tin Game
102
4.6 Application Example: Coffee Tin Game
66 /**
67 * Performs the coffee tin game to determine the colour of the
last bean
68 *
69 * @requires tin is not null /\ tin.length > 0
70 * @modifies tin
71 * @effects <pre>
72 * take out two beans from tin
73 * if same colour
74 * throw both away, put one blue bean back
75 * else
76 * put green bean back
77 * let p0 = initial number of green beans
78 * if p0 = 1
79 * result = ‘G’
80 * else
81 * result = ‘B’
82 * </pre>
83 */
84 private static char tinGame(char[] tin) {
85 while (hasAtLeastTwoBeans(tin)) {
86 // take two beans from tin
87 char[] takeTwo = takeTwo(tin);
88 char b1 = takeTwo[0];
89 char b2 = takeTwo[1];
90 // process beans to update tin
91 if (b1 == BLUE && b2 == BLUE) {
92 // put B in bin
93 putIn(tin, BLUE);
103
4.6 Application Example: Coffee Tin Game
105 /**
106 * @effects
107 * if tin has at least two beans
108 * return true
109 * else
110 * return false
111 */
112 private static boolean hasAtLeastTwoBeans(char[] tin) {
113 int count = 0;
114 for (char bean : tin) {
115 if (bean != REMOVED) {
116 count++;
117 }
118 if (count >= 2) // enough beans
119 return true;
120 }
121 // not enough beans
122 return false;
123 }
124
125 /**
126 * @requires tin has at least 2 beans left
127 * @modifies tin
128 * @effects
129 * remove any two beans from tin and return them
104
4.6 Application Example: Coffee Tin Game
130 */
131 private static char[] takeTwo(char[] tin) {
132 char first = takeOne(tin);
133 char second = takeOne(tin);
134 return new char[] {first, second};
135 }
136
137 /**
138 * @requires tin has at least one bean
139 * @modifies tin
140 * @effects
141 * remove any bean from tin and return it
142 */
143 private static char takeOne(char[] tin) {
144 for (int i = 0; i < tin.length; i++) {
145 char bean = tin[i];
146 if (bean != REMOVED) { // found one
147 tin[i] = REMOVED;
148 return bean;
149 }
150 }
151 // no beans left
152 return NULL;
153 }
154
155 /**
156 * @requires tin has vacant positions for new beans
157 * @modifies tin
158 * @effects
159 * place bean into any vacant position in tin
160 */
161 private static void putIn(char[] tin, char bean) {
162 for (int i = 0; i < tin.length; i++) {
163 if (tin[i] == REMOVED) { // vacant position
164 tin[i] = bean;
165 break;
105
4.6 Application Example: Coffee Tin Game
166 }
167 }
168 }
169
170 /**
171 * @effects
172 * if there are beans in tin
173 * return any such bean
174 * else
175 * return ’\u0000’ (null character)
176 */
177 private static char anyBean(char[] tin) {
178 for (char bean : tin) {
179 if (bean != REMOVED) {
180 return bean;
181 }
182 }
183 // no beans left
184 return NULL;
185 }
186 }
106
4.6 Application Example: Coffee Tin Game
that to display an array, the code first invokes procedure Arrays.toString to convert
it into a string literal. This procedure is provided by class java.util.Arrays.
K Chapter 4 Exercise k
These exercises are designed to help practise developing a number of small verifiable
programs. You must use the development method explained in this chapter. You will find
that although most of these programs are familiar and supposedly simple, constructing
a good behaviour specification for them is not trivial!
1. Write the design specification for a Java program called Arrays that contains
procedures for solving the following problems (one procedure per problem). The
procedures must be named as given. The behaviour of procedure main of this
program must be to display a list of the problems and prompt the user to choose
which problem to solve. After the user has selected a problem, the procedure must
prompt the user to enter input data for the selected problem. Finally, it invokes the
procedure defined for the selected problem, passing in the input data, and displays
the result on the standard output.
(a). countNegatives: count the number of elements of an array of integers that
are negative
(b). countEvens: count the number of even elements of an array of positive
integers
(c). divArray: divide the elements of a real number array by a real number
(d). min: find the minimum element in an array of integers
(e). isAscSorted: determine whether an array of integers is in ascending order
(f). length: find the length of an array of CHARs on the understanding that
if it contains the character NUL (the character ‘u0000’ in Java), assumed
predefined as a constant, then that and any characters after it are not to be
counted. In other words, NUL is understood as a terminator
107
4.6 Application Example: Coffee Tin Game
(g). (*) median: find the median of an array of reals, that is the array value
closest to the middle in the sense that as many array elements are smaller
than it as are greater than it. Is the problem any easier if the array is known
to be sorted?
(h). compare: given two arbitrary arrays of reals, a and b, determine if a ⊂ b,
a ⊃ b, a ∩ b, or a = b
(i). freq: compute the frequencies of each element of an array of reals
2. Implement the program Arrays that you designed in Exercise 4.1. Run the
program with some test data to make sure that it works correctly.
3. Write the design specification for a Java program called Math that contains pro-
cedures for solving the following problems. The procedures must be named as
given. The behaviour of the procedure main of this program is similar to that of
program Arrays above.
(a). remainder: determine the remainder after integer division using only sub-
traction. Ignore the possibility of division by zero.
(b). div: determine the integer division using only addition and subtraction.
Ignore division by zero.
(c). middle: determine the middle one of three numbers
(d). isPalindrome: determine whether or not a string is a palindrom (a palin-
drom reads the same backward and forward, e.g. deed)
(e). isPrime: determine if an integer is a prime
4. Implement the program Math that you designed in Exercise 4.3. Run the program
with some test data to make sure that it works correctly.
5. Extend of the programs Arrays and Math so that they run continuously, allowing
the user to perform any number of computations, until (s)he enters a special input
(e.g. character “Q” or “X”) to stop.
108
Chapter 5
Introduction to Object Oriented Program
Objectives
" Understand the concept of object oriented program (OOP) and its benefits.
" Compare and contrast between OOP and procedural program.
" Explain the core concepts of OOP: object, class.
" Describe the object oriented program development process.
This chapter marks the beginning of our treatment of a major topic of this book –
object oriented program development. We shift our focus to the next level of abstraction
in program design: from procedural abstraction to data abstraction [20]. We will study
“object-oriented” data types that describe the information and behaviour of objects.
Conceptually, it is argued that designing a program in terms of objects is easier since
it fits more naturally with the designer’s perception of the problem domain. For example,
instead of considering a greeting conversation between two persons as a procedure that
displays two greeting messages (one from each), it is more natural to think of it as a
conversational situation in which two persons (or speaking more technically two person
objects) greet one another with a message. What is interesting from this view point is
that everything in a program is an object, including the conversation itself.
There are important benefits that can be gained from developing object oriented
programs. But doing so requires support from the programming language in terms of
how to represent objects, and, more generally, class of objects.
The purpose of this chapter is to provide a gentle introduction to object oriented
program and its development. First, we define the basic concepts, including object
oriented program, object and class. Next, we compare between object oriented program
and the procedural counterpart. After that, we give an overview of an object oriented
program development method.
put. The greeting message takes the simple form “Hello, my name is X”, where
X is name of the speaking person. Listing 5.1 shows a procedural program named
GreetingConversationProc1 that implements these requirements. We add a number
prefix to this program because several versions of it will be developed in this chapter.
Listing 5.1: Procedural program: GreetingConversationProc1
1 import utils.TextIO;
2 /**
3 * @overview A program that displays greetings of a person group.
4 */
5 public class GreetingConversationProc1 {
6 /**
7 * @effects a group of persons whose names in args
8 * greet each other;
9 * i.e. for each name n in args
10 * invoke greet(n)
11 */
12 public static void main(String[] args) {
13 if (args == null || args.length < 2) {
14 System.out.println("Requires at least 2 names");
15 System.exit(1);
16 }
17 for (String name: args) {
18 greet(name);
19 }
20 }
21
22 /**
23 * @effects displays "Hello, my name is " + name
24 */
25 private static void greet(String name) {
26 System.out.printf("Hello, my name is %s%n", name);
27 }
28 }
110
5.2 Why Object Oriented Program?
111
5.2 Why Object Oriented Program?
112
5.2 Why Object Oriented Program?
Data hidding is further demontrated in the RHS of Figure 5.1, which shows the
design specification of an OOP version of GreetingConversationProc2. In this
figure the two actions (greet and hand-shaking) are performed via behaviour invocations,
without any direct references to name.
The LHS of Figure 5.2 shows the design specification of an OOP version of
GreetingConversationProc3. It illustrates the ease of support for concurrent de-
sign. The two actions greet and recordName are defined on two different object types
113
5.3 What Is OOP?
(Person and Phone, resp.). Thus, invoking these two behaviours on two threads (th1
and th2) simply amounts to mapping the two object types to the threads. Further, if the
two threads are physically located on two separate devices (such as the situation shown
in the RHS of Figure 5.2) then the object codes can also be written to these devices
accordingly. The object type makes the mapping to real-world objects easy.
114
5.3 What Is OOP?
115
5.3 What Is OOP?
14 gc.greet(args);
15 }
16
17 /**
18 * @effects
19 * Create a person group from specified <tt>names</tt>
20 * and make them greet each other
21 */
22 public void greet(String[] names) {
23 if (names == null || names.length < 2) {
24 System.err.println("Requires at least 2 names");
25 return;
26 }
27
116
5.4 Object and Class
9 /**
10 * @effects initialise this as an object whose name is aName
11 */
12 public Person(String aName) {
13 name = aName;
14 }
15
16 /**
17 * @effects updates name with newName
18 */
19 public void setName(String newName) {
20 name = newName;
21 }
22
23 /**
24 * @effects Prints a greeting message containing name to
25 * the standard console
26 */
27 public void greet() {
28 System.out.printf("Hello, my name is %s%n", name);
29 }
30 }
117
5.4 Object and Class
1As a convention, the first letter of every word of a class name is capitalised.
118
5.5 Class Design Diagram
119
5.6 Information Hiding
2another operation Person(String) is omitted from the figure and will be discussed later.
3to be more precise, since Person.name is non-static, only non-static procedures of class Person can
access it.
120
5.7 Comparing OOP with Procedural Program
operation setName.
121
5.9 OOP Development Process
122
5.9 OOP Development Process
123
5.9 OOP Development Process
software development (e.g. [5, 17]) or on software engineering (e.g. [30]). Steps 6 and
7 will be discussed in detail in the subsequent chapters of this book.
4http://www.visual-paradigm.com
124
5.9 OOP Development Process
Figure 5.4: The activity diagram of the floating buoys management software.
125
5.9 OOP Development Process
Object definitions
Table 5.1 describes the objects that are identified for the example. The identified
objects reflect the distributed nature of the underlying system: objects are deployed
onto different devices that interact with each other, possibly in a concurrent manner, via
communications networks. Note the followings about the table:
“hardware-type” objects: due to the nature of the system, all objects except the
message switch are hardware-based, i.e. software entities that operate inside the
corresponding hardware devices
four types of sensor objects are identified, one for each type of data
126
5.9 OOP Development Process
clock object is created based on the domain knowledge of this kind of system
sensor database is not the actual database, but a software entity that is used by the
program to access the database
Self behaviour
This includes the operations that each object makes available for objects to invoke.
These operations are defined based on the activities performed by the objects identified
in the previous step.
Behaviour definitions. Table 5.2 below describes the self behaviour of the example.
The first column lists the objects and the second column lists the raw names of the
operations performed by the objects. Note that this list is not exactly the same as the list
in [4]. The objects whose behaviours differ from [4] are highlighted in bold:
clock is considered passive (active in [4])
radio receiver has three operations (no operations in [4])
emergency switch has two operations (no operations in [4])
message switch actively generates periodic messages (passively in [4])
Required behaviour
This is the behaviour that an object requires other objects to have in order to handle
the activity flows that originate from it. It includes operations or stimuli that cause the
127
5.9 OOP Development Process
invocations of some behaviour. The stimuli are written in the form “force...”.
Behaviour definitions. Table 5.3 describes the required behaviours of the example.
Note the following differences between this table and the list in [4]:
sensor objects and message switch requires procedure “get pulse” from clock
clock has no required behaviour since it is passive
radio receiver: “set light state” is changed to “force activate”
Class definitions
Table 5.4 describes the classes for the example. As can be seen from the table,
the classes correspond directly with the object types in Table 5.1. Note that reuse can
be enhanced by grouping the sensors into a hierarchy of sensors as described in [4].
However, to simplify the discussion we will not discuss this here.
128
5.9 OOP Development Process
129
5.9 OOP Development Process
Association definitions
Table 5.5 lists the associations for the classes in the example. The first and third
columns list the classes involved in the associations. The second column lists the
behaviours based on which the associations are defined.
5https://www.eclipse.org/modeling/mdt/?project=uml2
130
5.9 OOP Development Process
131
5.9 OOP Development Process
K Chapter 5 Exercise k
The exercises in this chapter are designed to introduce the key concepts of OOP.
Note that the term “design” here refers only to the initial conceptual design of a program.
The concrete design will be studied in later chapters. The main objective is to become
familiar with the key OOP concepts, namely class and object. The key tasks include
identifying class or classes that are needed to describe the concepts, drawing up the
shape of each class using the UML class notation. This diagram need to include any
attributes and operations that the class may have.
1. The greeting conversation program discussed in the lecture now needs to capture
and process data about mobile phones. A mobile phone contains data about
manufacturer name and the phone model. For example, the phone Samsung
Galaxy 3S, GT-55360 has manufacturer name “Samsung” and the model “GT-
55360”. A mobile phone can perform two actions: one is to change the model and
the other is to record the name of a person.
Draw a design diagram for phone.
2. Extend the greeting conversion program further to capture data about which person
owns which phone. For example, the program should be able to capture the fact
that a person named “Duc” owns the Samsung phone mentioned in the previous
task.
Think of at least two ways in which you can design this new requirement. Draw a
suitable design diagram for each.
3. In this task, you will design an object oriented program for the procedural program
Arrays that you wrote in a previous tutorial. In this OOP, which is called Array,
an Array object has its state set to an array of integers. Each object can perform
the following actions upon this array:
(a). count the number of elements that are negative
(b). find the minimum element
(c). determine whether the array is in ascending order
(d). return the length of the array
(e). compute the frequencies of each element of the array
Draw a design diagram for Array.
4. What are the benefits of the OOP Arrays that you designed over the procedural
version?
5. Write the code for the greeting conversation program that you designed in Exer-
cise 5.2.
6. Write the code for the program Array that you designed in Exercise 5.3.
132
Chapter 6
Object Oriented Design Fundamentals
Objectives
" Understand the need for constructing a detailed design specification of class.
" Understand the difference and relationship between abstract and concrete design
levels and how to define both in a specification. Apply the verifiable program
design specification method for class.
" Specify a class to model a domain concept.
" Describe the essential domain constraint rules and the essential operation types.
Explain how to choose suitable operations for a class.
" Apply an essential set of annotations to specify the design of attributes and
operations.
" Explain the advantages and disadvantages of the alternative concrete data types
of an attribute.
" Explain the difference between the design specifications of collection and non-
collection classes.
As we saw in the previous chapter, object oriented program (OOP) relies on a strong
understanding of the conceptual structure of the problem domain. A well-thought-out
OOP design is thus necessary for a successful implementation in a target OOPL. Because
of the particularly important role of OOP design, we devote three chapters of this book
to it. In this chapter, we discuss class design – the fundamental building block of OOP.
In two latter chapters, we will discuss a number of design issues and introduce some
basic but useful OOP design patterns.
In this chapter, we first critically review a number of key concepts introduced in the
literature that are about or related to class. After that we discuss how to apply the design
specification method of procedural programs that we studied to design class. The core
of the design specification language remains the same. However, we will introduce a
number of essential extensions to this language in order to accommodate class and its
members (namely fields and methods).
6.1 Motivation
6.1 Motivation
As we have seen with procedural programs, design takes time and effort, which
would affect the overall development timeline. The more detailed a design, the more
time it would take to complete. So two natural questions to ask are why do it? and how
detailed does the design need to be?
Let us consider the bare design of the class Person shown in Figure 6.1. We
introduced this design in the previous chapter. Is this design sufficient for successful
program implementation?
A closer look at this Person class design can reveal the following questions that
still need to be answered before we can start coding it:
1. Can name be typed StringBuilder1 instead of String?
2. Can id be negative?
3. Can name be uninitialised (i.e. takes null)?
4. How do we create a Person object with a given id and name?
5. How do we obtain the value of name?
6. Should there be an operation to change value of id?
7. Are there any other essential operations of this class?
The first three questions concern the design of the object state (attributes and their
values) while the other four questions concern the essential operations that are needed in
order for a client program to manipulate the objects and their states. These questions are
important not only because they concern the essential design elements but because there
are potentially alternative answers to each of them. Further, it is not always clear which
answer is the best one to use in all situations. For instance, both data types mentioned
in Question 1 are suitable for attribute name. The choice of which one to use depends
on whether or not this attribute’s value is often modified rather than replaced.
To make informed design decisions require capturing in the design model the
necessary design rules from the problem domain. Unfortunately, the design model in
Figure 6.1 does not capture these rules. In this chapter, we will study a design method
134
6.2 Design Terms
for class that helps capture sufficient detail to answer the above and other important
questions about the design.
Design Examples
To illustrate the concepts and techniques presented in this chapter, we will use two
representative design examples. The first example describes a concept, named Customer
, which is commonly found in business-typed software. At the bare minimum, a customer
is characterised in terms of an identifier (abbr. id) and full name (abbr. name). The
second example is an adaption of a collection-typed concept, named IntSet, which
represents a set of intergers. This concept is commonly used as a technical concept in
a program to help organise data objects. IntSet is defined in Chapter 5 of the Liskov
and Guttag’s book [20].
The rest of this section will discuss the following terms that are listed in the figure:
data abstraction
abstract concept
class and abstract data type (ADT)
object
135
6.2 Design Terms
6.2.3 Class
A class, in the object oriented programming terminology, is a particular model of
an abstract concept that is constructed for an object oriented programming solution. In
other words, when we want to develop an OOP to capture and process data about an
abstract concept, we define a class to model that concept. Conversely, we say that the
abstract concept provides meaning for the class.
For instance, we would create in an OOP a class named Poly [20] to model the alge-
braic concept POLYNOMIAL, and class Customer to model the concept CUSTOMER.
136
6.2 Design Terms
IntSet An integer set, denoted by IntSet, is a set of integer numbers. This class
is the tuple: <X,OptsS>, where X is the set of all integer sets and OptsS is a set of
operations on X. OptsS contains the following operations on IntSet objects:
add an element
remove an element
check membership
determine the cardinality
pick an arbitrary element
Customer Class Customer the tuple <C,OptsC>, where C is the set of all customer
objects and OptsC is a set of operations on C. OptsC contains the following operations
on Customer objects:
set id and name
get id and name
place a product order
6.2.5 Object
It follows that object is a realisation of an abstract object in an OOP. That is, for
example, every object of the class Customer (in a commercial OOP) corresponds to an
137
6.3 Design Method
abstract object of CUSTOMER that actually exists in its problem domain. When it is
necessary to differentiate between the two terms, we will use the name concrete object
to refer the objects of an OOP.
We can also use “concrete” to differentiate between two state-specific terms that
are discussed in [20]: concrete state and abstract state. Concrete state is the state of a
concrete object while abstract state is the state of an abstract object.
The first and primary source of inspiration for the design method in this book is
the program specification method presented by Liskov and Guttag [20]. In a previous
chapter, we discussed this method for procedural program design. As discussed in [20],
the method is also applied to OOP. However, this OOP design method focuses only on
the object operations. Although the method discusses object representation (the rep), it
does not formally capture attributes in the design specification, nor does it describe the
transformation steps needed to define the rep from attributes.
Thus, it is necessary to extend the Liskov and Guttag’s method to take into account
both attributes and operations in the design specification. This becomes more pressing
when we place the method in the broader context of object oriented development that
Booch [4] advocated about a decade earlier. A first important extension of the method
that is proposed in this book concerns the state space [18]. In particular, the state space
incorporates a set of essential design rules (called domain constraints) on the attributes.
The constraints are expressed directly in OOPL using the annotation construct. These
constraints are chosen from the commonly cited constraints in both software engineering
and system engineering literatures (e.g. [14, 20]) as well as those used in state-of-the-art
software development frameworks (e.g. JPA [24], Hibernate [27], Bean validation [26]
etc.).
Another important extension of the OOP design method in this book concerns
138
6.3 Design Method
the behaviour space [18]. Specifically, the behaviour space uses annotation to express
the structural design rules concerning the operation behaviours. These rules are also
identified to be essential to the operations that operate on the objects.
In brief, the object oriented design method in this book extends Liskov and Guttag’s
with three extensions:
Objects are characterised by both attributes and operations.
State space: attributes have restrictions on values that they can take, these re-
strictions are formalised as domain constraints. These constraints are expressed
directly in OOPL using annotation.
Behaviour space: essential operations are specified with annotations that make
explicit their behaviours.
2https://spring.io/
3https://www.openxava.org/
4https://angular.io/
139
6.4 Design Specification Language
The diagram on the LHS of this figure is a simple class diagram, which contains
a single class. The top compartment is reserved form class name and, in some cases,
special annotations for class. The attributes and operations are placed in the second and
third compartments, respectively. The diagram on the RHS of the figure is a simple
object diagram, which contains a single object of a class named Customer.
140
6.4 Design Specification Language
141
6.4 Design Specification Language
Wrapper classes
Wrapper classes, or wrapper types, are classes that ’wrap’ the primitive types,
making them suitable for use as object types. Thus, wrapper types can be used as both
formal and concrete types of attributes. Table 6.3 lists the primitive types and their
corresponding wrapper types.
A key benefit of using a wrapper class (e.g. Integer) compared to the corresponding
primitive data type (e.g. int) is that it supports the specification of null value. This
value is needed for integral, optional attributes (i.e. attribute with the property optional
=true. It is not possible to initialise this attribute to null if the primitive data type is
used.
To ease programming with wrapper objects, Java5 supports auto-boxing and auto-
unboxing features. The former allows a primitive data value to be automatically con-
verted to an object of the corresponding wrapper type (e.g. int is converted to Integer).
The latter allows the opposite conversion from a wrapper object to the corresponding
primitive data value.
Example 6.2 Program IntegerWrapper
Listing 6.2 shows a simple IntegerWrapper program that demonstrates the wrap-
per class Integer and how to use it with the auto-boxing and auto-unboxing features.
Similar examples can easily be constructed for other wrapper classes.
1 /**
2 * @overview A program that manipulates Integer objects.
142
6.4 Design Specification Language
3 */
4 public class IntegerWrapper {
5 /**
6 * The run method
7 */
8 public static void main(String[] args) {
9 Integer i;
10 int j, k;
11
143
6.4 Design Specification Language
144
6.5 Header Specification: Specifying the Abstract Concept
Vector or set? Conceptually, vector is similar to set in providing a data structure for
storing a collection of items and the items can be of different types. However, there are
important differences between these two data structures. First, vector works like array
and thus it does not care about whether or not the elements are the same or not. That is, it
is perfectly acceptable to add duplicate elements to a vector (the example in the previous
subsection shows this). Sets, however, do not allow duplicate elements. Second, similar
to array, vector provides an index-based access to its elements. However, set does not
support this type of access (elements in a set are stored in an arbitrary order).
6.5.1 Overview
We first define abstract concept in terms of attributes and then use a typical abstract
object to clarify the definition. Note that abstract concept does not have behaviours.
These are defined for class, which is an object oriented model of the concept. We
will discuss the specification of these behaviours in the next section. The concept
specification is written in the header comment of the class definition. It is referred to in
this note as header specification. The specification includes the following components:
concept name (also used as the class name)
overview
attributes
abstract object
abstract properties
We will explain the design guidelines for these components in this section. We
illustrate our discussion with the two design examples about Customer and IntSet (see
145
6.5 Header Specification: Specifying the Abstract Concept
Section 6.1).
Figure 6.4: Choosing the class name for Customer and IntSet.
Figure 6.4 shows the initial design of Customer and IntSet that show the labelled
class boxes of these two concepts. We will gradually fill details into these boxes as we
progress through this chapter.
Figure 6.5: Writing @overview in a note box and attaching it to the class.
Figure 6.5 shows the two note boxes in the class diagrams of the two concepts
Customer and IntSet. Listing 6.5 lists the header specifications of Customer and
IntSet that have been updated with their @overview components. The content of
@overview is the same as in the note box on the class diagram.
1 /**
2 * @overview Customers are people or organisations
3 * with which we have relationships.
4 */
146
6.5 Header Specification: Specifying the Abstract Concept
7 /**
8 * @overview IntSet are mutable, unbounded sets of integers.
9 */
10 public class IntSet
Figure 6.6 shows an update to the class diagrams of Customer and IntSet that
contain attributes. Listing 6.6 lists the corresponding update to the header specifications
147
6.5 Header Specification: Specifying the Abstract Concept
of Customer and IntSet that have been updated with their @attributes components.
For brevity, we only show in the listing the update content (thus, omitting the @overview
content).
1 /**
2 * @overview ... as before ...
3 * @attributes
4 * id Integer
5 * name String
6 */
7 public class Customer
8
9 /**
10 * @overview ... as before ...
11 * @attributes
12 * elements Set<Integer>
13 */
14 public class IntSet
148
6.5 Header Specification: Specifying the Abstract Concept
otherwise, the typical values of the attribute type are listed; e.g. -2,-1,0,1,2,...
are typical values for integer type
2. if the class has several attributes then the tuple notation is used to write the typical
values of the attributes.
Example 6.7 Abstract object Figure 6.7 shows object diagrams of the three abstract
objects of Customer, IntSet and Integer. Listing 6.7 lists the three abstract object
descriptions in the @object tags of the header specifications of the three classes.
For Customer:
this class has two attributes (id and name) so the tuple notation is used
tuple <d,n>, where d and n are values of the two attributes (resp.)
attributes id and name are treated as predicates
For IntSet:
this class has a single attribute, whose formal type is set-based, so the set notation
is used to list its elements
For Integer:
this class has a single attribute whose type is integral, so its instances are listed
1 /**
2 * @overview ... as before ...
3 * @attributes ... as before ...
4 * @object A typical Customer is c=<d,n>, where id(d), name(n).
5 */
6 public class Customer
7
8 /**
9 * @overview ... as before ...
10 * @attributes ... as before ...
11 * @object A typical IntSet object is s = {x1,...,xn},
12 * where x1,...,xn are elements
13 */
14 public class IntSet
149
6.5 Header Specification: Specifying the Abstract Concept
15
16 /**
17 * @overview Integers are immutable whole numbers (incl. 0) and
their negatives.
18 * @attributes
19 * value Integer
20 * @object Typical integers are ...,-2,-1,0, 1,2,3,...
21 */
22 public class Integer
Overview
An abstract property is a property of the abstract concept. It holds true for all
abstract objects. We are interested in a common set of domain properties that are
used for concepts. We call these properties domain constraints. We use the tag
@abstract_properties in the header specification to specify all the properties.
Domain constraints
A domain constraint is a general statement about what data values an attribute can
take. Our analysis of the frequently-used system and software engineering works [14, 20]
reveal the following basic constraints:
mutable: whether or not the attribute value can be changed
optional: whether or not the attribute value must be defined for each object
length (primarily used for string type): the maxinum length of the values
min (for numeric type): the min value
max (for numberic type): the max value
Each of these properties is defined as a function from the set of attributes into a set
of sets of values. The function ranges are as follows:
mutable, optional: range is the set {true, false}
length: range is the set of natural numbers
min, max: range is the set of real numbers
Example 6.8 Domain constraint
150
6.5 Header Specification: Specifying the Abstract Concept
Customer Table 6.4 shows the design table for the domain constraints of Customer
. Listing 6.2 shows how these properties are written in the @abstract_properties
section of the header specification.
IntSet Table 6.5 shows the design table for the domain constraints of IntSet. List-
ing 6.3 shows how these properties are written in the @abstract_properties section
of the header specification.
151
6.6 Specifying Concrete Attribute Types
Other properties
These are properties that are specific to each abstract concept and are not already
covered by the domain constraints. Examples of these properties include:
elements of a Set are distinct
elements of an Array form a sequence
Example 6.9 IntSet
Listing 6.4 shows how the distinct property of a set is added to the @abstract_properties
specification of IntSet shown in Listing 6.3.
Listing 6.4: IntSet
1 /**
2 * @overview ... as before ...
3 * @attributes ... as before ...
4 * @object ... as before ...
5 * @abstract_properties
6 * mutable(elements)=true /\ optional(elements)=false /\
7 * elements != {} -> (for all x, y in elements. x != y)
8 */
9 public class IntSet
152
6.6 Specifying Concrete Attribute Types
The simplest case is when the formal type is supported by the target language
(which, in the case of Java, includes all the primitive types and String). In this case,
the concrete type is the same as the formal counterpart. A more complex situation arises
when the formal type is not supported by the target language. In this case, choices
can exist among the alternative types provided by the language. For example, suppose
the formal type Set<Integer> is not directly supported by Java6 then two alternative
concrete types exist for it: array of integers (int[]) or Vector<Integer>. This raises
the question of how can one decide to choose one type over others?
A general criteria suggested by Liskov and Guttag [20] is to choose a type that
can balance between productivity and efficiency. This balance is desired since types
usually donot do well in both. Productivity refers to the extent to which it is easier to
program with a type. For example, Vector is preferred to array in terms of productivity
for working with dynamic arrays. This is because Vector can grow and shrink dynam-
ically and it provides operations for adding and removing the elements. However, array
is preferred to Vector for working with arrays of fixed sizes. Efficiency, on the other
hand, refers to the run-time efficiency of the code that uses this type. In this aspect, for
instance, array is preferred to Vector since it provides a faster, constant look-up time of
the elements.
Guidelines
We summarise below the guidelines for specifying the concrete type of an attribute:
must be supported by the target language
may be the same or different from the formal type
need to balance between productivity and efficiency
productivity: ease coding with the type
efficiency: run-time efficiency of the using code
Example 6.10 Customer
Figure 6.8 and Listing 6.5 show the concrete type design and specification of
the two attributes id and name of Customer. For attribute int, the primitive type
int is chosen for efficiency reason. It helps avoid unnecessary boxing and unboxing
conversions at run-time. Although Java directly supports the wrapper type Integer, the
extra operations that this class provides are not needed for client programs that need to
manipulate the id’s value.
For attribute name, the concrete type is the same as the formal one because String
6In fact, Java has this data type; but, for the sake of the discussion we assume that it does not.
153
6.6 Specifying Concrete Attribute Types
is directly supported by Java. In addition, class String provides many useful operations
that make it easier to program with.
Example 6.11 IntSet
Figure 6.9 and Listing 6.6 show the concrete type design and specification of
the attribute elements of IntSet. The chosen concrete type is Vector<Integer>,
although this is not a clear choice in all situations. As discussed above, both int[]
and Vector<Integer> are suitable for use as concrete types. From the productivity
perspective, the latter is preferred because Vector provides useful operations that helps
easily implement most of the essential operations of IntSet. As for efficiency, there
is no clear winner across all the key operations. In our experiment, int[] runs faster
with the element removal and membership test operations but is slower with the element
addition operation. Although the client program’s code that uses Vector is shorter than
that using int[], Vector<Integer> in fact adds another layer of abstraction on top of
array, which would impact the overall code performance.
Therefore, if IntSet either has a fixed size or does not frequently grow and shrink
then int[] is a preferred concrete type. Otherwise, Vector<Integer> should be
chosen as the concrete type.
Listing 6.6: IntSet
1 /**
2 * @overview ...
154
6.7 Specifying the State Space
3 * @attributes
4 * elements Set<Integer> Vector<Integer>
5 * ...
6 */
7 public class IntSet
155
6.7 Specifying the State Space
Example 6.13 IntSet representation
Figure 6.11 and Listing 6.8 show how the IntSet’s rep is defined in terms of the
instance variable elements. Note that the choice of Vector<Integer> helps guarantee
the abstract property that IntSet only contains integers.
Listing 6.8: IntSet
156
6.7 Specifying the State Space
1 /**
2 * @overview ...
3 * @attributes
4 * elements Set<Integer> Vector<Integer>
5 * @object ...
6 * @abstract_properties ...
7 */
8 public class IntSet {
9 private Vector<Integer> elements;
10 }
157
6.7 Specifying the State Space
9 }
158
6.7 Specifying the State Space
15 @DomainConstraint(mutable=true,optional=false,length=50)
16 private String name;
17 }
Example 6.15 IntSet’s domain constraints
Figure 6.13 and Listing 6.11 show how the instance variable elements of class
IntSet is annotated with a @DomainConstraint that realises the abstract properties
of the corresponding attribute. Note that the annotation only captures the domain
constraints, it does not (yet) support the uniqueness property of IntSet. This property
is checked by a special validation operation, which we will discuss later in Section 6.9.
159
6.8 Essential Design Annotations
The ultimate aim of the annotations is to make class design more precise. The
essential annotations (shown in Figure 6.14) are defined in the package named utils
of the attached source code. Annotation @DomainConstraint was discussed in the
previous section. Other annotations are used to annotate object operations, which we
will discuss in the next section. The precise definition of each annotation will be given
when they are used in the text.
Conceptually, the operational annotations help make explicit the behaviour of the
operations in relation to the attributes whose values they manipulate. For example,
attribute Customer.name is manipulated by two operations setName (changing the
value) and getName (accessing the value). To make explicit this connection requires
annotating the two operations with a reference to the attribute.
160
6.9 Specifying the Behaviour Space
161
6.9 Specifying the Behaviour Space
constitute the essential operations of each type for a class. The general guidelines stated
by Liskov and Guttag [20] are as follows:
consider the usage context:
e.g. operation IntSet.size is needed if the cardinality of set is required
define at least one constructor and one observer
In Java, the default (non-parameter) constructor may be omitted
define a mutator for each mutable attribute
define data validation operations for attributes with domain constraints
define operations that can help ease programming with objects:
e.g. define IntSet.isIn to check if a set has a specific element
define helper operations to help other operations:
e.g. IntSet.getIndex
Example 6.16 Customer & IntSet
Figures 6.15 and 6.16 respectively show the essential operations of the two classes
Customer and IntSet. The reasons for choosing these operations will be given in the
subsequent sections.
162
6.9 Specifying the Behaviour Space
Annotation DOpt
This annotation describes a behaviour pattern. It is attached to operation to specify
that the operation’s behaviour has a certain pattern. @DOpt has one property named
type, which specifies the operation type. The data type of this property is an enum
called OptType. The annotation is written before the operation header as follows:
@DOpt(type=t), where t ∈ OptType.
Note that DOpt is usually not required for constructor and helper operations. The
following listing shows the definitions of the essential operation type constants that
are defined by the enum OptType. The comments in the listing briefly describe the
behaviour of each operation type.
163
6.9 Specifying the Behaviour Space
Observer,
/**a specialised type of observer, which is used to annotate an
operation of a collection class that realises its primary
iterator abstraction */
ObserverIterator,
/**a specialised type of observer, which is used to annotate an
operation of a collection class that checks for membership
of an element in a collection */
ObserverContains,
/**a specialised type of observer, which is used to annotate an
operation of a collection class that returns its size*/
ObserverSize,
/**a specialised type of mutator, which is used to annotate an
operation of a collection class that adds a new element to
the collection*/
MutatorAdd,
/**a specialised type of mutator, which is used to annotate an
operation of a collection class that removes an element from
the collection*/
MutatorRemove
;
}
The first two operation types are generic types that are used to annotate the mu-
tator and observer operations. The remaining five operation types are specifically
used to annotate operations of the collection-typed classes (e.g. IntSet). Annota-
tions MutatorAdd and MutatorRemove, in particular, are special forms of Mutator.
Similarly, ObserverContains, ObserverSize and ObserverIterator are the special
forms of Observer. We will not discuss operation ObserverIterator in this book.
Annotation AttrRef
This annotation has one property named value, which specifies the name of the
attribute that is manipulated by (and thus referenced in) the operation’s behaviour. The
data type of this property is String. This annotation can annotate both operation and
operation parameter and is written with the following syntax:
@AttrRef(value=n) or simply @AttrRef(n), where n is the referenced attribute’s
164
6.9 Specifying the Behaviour Space
name.
Note the followings about @AttrRef’s usage:
AttrRef is often (but not always) used with DOpt.
for non-constructor operations: AttrRef is used to annotate the operation (not its
parameter).
for constructor operations: AttrRef is used to annotate the parameters and is
written immediately before the declaration of each parameter.
(AttrRef is usually not required for parameters of non-constructor operations).
6.9.5 Constructor
Let us now begin looking at the design specification of each operation type. This
section starts with the constructor operation. Objects need to be created before they can
be used in the program. Recall that the purpose of constructor is to perform this task.
There are two main methods for defining constructors. The first method is to define a
default constructor that has no parameters. Objects created with this constructor have
a default state, where the attributes are initialised to the default values. After creation,
the desired object state needs to be set by using the mutator operations. The second
method is to define an essential constructor that takes the essential parameters needed
to initialise the attributes. Objects created with this method have the desired state at
creation time and, as such, there is no need to use the mutator operations to update it. In
practice, both methods are often used which result in a class having several constructors
defined.
While the first method is straightforward and is directly supported by the mutator
operations defined in this book, the second method is essential to help ensure that the
created objects are valid objects (a.k.a correct by creation). This section will focus on
explaining the specification guidelines for the essential constructor. In particular, the
specification will use annotation @AttrRef to map the constructor parameters to the
corresponding attributes.
Header
In addition to the standard OOPL’s syntax rules for constructor, the parameter list of
the constructor needs to make explicit the essential parameters. An essential parameter
is a parameter that is defined based on a non-optional, non-collection-typed attribute.
Such an attribute has @DomainConstraint(optional=false) and a non-collection
data type.
165
6.9 Specifying the Behaviour Space
Behaviour
Constructor is usually the total operation (i.e. has no @requires clause). The
@effects clause should state the followings:
initialise an object with the input parameters
validate input parameters against the domain constraints (if any). If a violation oc-
curs then terminates immediately with an error object of the type NotPossibleException
166
6.9 Specifying the Behaviour Space
6.9.6 Mutator
Mutator operations are to update the object state. This is usually performed by
changing the attribute values. This explains why a most common form of mutator
operations are called setters, which directly sets an attribute’s value to a new one. In
this section, we will focus on design specification of this type of operation.
An important rule which must be observed is that setter operations are required for
mutable attributes and forbidden for immutable ones.
Header
In addition to the standard OOPL syntax for operation, the following header rules
need to be observed for the setter of an attribute named A:
is annotated with @DOpt.type=OptType.Mutator and @AttrRef.value=A
operation name has the pattern setA
return type is boolean, which signifies whether or not a behaviour invocation
succeeds (see behaviour description below)
parameter list has one parameter whose type matches A’s type
Behaviour
Mutator is a total operation, whose behaviour description must be as follows:
@modifies clause states that the object state is changed
@effects clause states the update of the referenced attribute and the handling of
input errors by returning false
The client program must check the return value to act accordingly. Note that an
alternative technique for handling the input errors is to throw an exception (similar to
167
6.9 Specifying the Behaviour Space
the constructor’s design). However, this technique will not be used for mutators in this
book.
Example 6.18 Customer
Listing 6.13 shows the design of the setter setName, which updates the value of
attribute Customer.name. Note that there must not be a setter for attribute id because
this attribute is immutable. If the parameter name is valid and attribute name is set to its
value then the operation returns true. Otherwise, the operation returns false.
Listing 6.13: Customer
1 /**
2 * @modifies this
3 * @effects
4 * if name is valid
5 * set this.name to name
6 * return true
7 * else
8 * return false
9 */
10 @DOpt(type=OptType.Mutator) @AttrRef("name")
11 public boolean setName(String name)
6.9.7 Observer
Observers obtain information about the object state. A most common type of
observer is called getter, which directly observes (i.e. gets) the value of an attribute.
Because getter operations generally useful, every class should be defined with one getter
operation for each attribute. This section will focus on the design specification of getter
operations.
Header
In addition to the standard OOPL syntax for operation, the following header rules
need to be observed for the getter of an attribute named A:
is annotated with @DOpt.type=OptType.Observer and @AttrRef.value=A
operation name has the pattern getA
return type matches the A’s data type
168
6.9 Specifying the Behaviour Space
Behaviour
The behaviour description of getter is very simple, which contains an @effects
clause stating the result to be equal to the target attribute.
Example 6.19 Customer
Listing 6.14 shows the design of two getters getId and getName of the class
Customer. These operations observe the attributes id and name, respectively.
Listing 6.14: Customer
1 /**
2 * @effects return id
3 */
4 @DOpt(type=OptType.Observer) @AttrRef("id")
5 public int getId()
6
7 /**
8 * @effects return name
9 */
10 @DOpt(type=OptType.Observer) @AttrRef("name")
11 public String getName()
6.9.8 Default
Default operations are operations that are provided by the OOPL for every class.
They are inherited from a generic Object class that serves as the template for all class
definitions. Although this fact is hidden from the class designer, the operations are
always available for use in each class when needed.
In Java, three common default operations that should be defined for each class
are: toString, equals and hashCode. Although our design specification of these
operations is written for Java, the design guidelines are also applicable to other OOPLs.
A general header rule is that each of these operations should be annotated with the
built-in annotation @Override. This makes explicit the fact that the operation changes
(or overrides) the behaviour of the base operation in class Object. The behaviour
description needs not be specified, because it should conform to the behaviour of the
169
6.9 Specifying the Behaviour Space
toString
This operation has an empty parameter list and returns a string representation of
the object. This string is formatted based on the details specified in the @object section
of the class header specification. The Java header for overriding operation toString is
as follows:
1 @Override
2 public String toString()
equals
1 @Override
2 public boolean equals(Object o)
The default Java implementation of this operation is the most restrictive one, which
compares two objects by their built-in object identifiers. A more practical (less restric-
tive) implementation would compare objects by the (mostly) immutable parts of the
object state.
hashCode
This operation takes no parameters and return an int hash value of the object. This
value is used as key in a hash data structure for storing the object. Common examples
of this type of data structure include Hashtable and HashMap – both are provided by
Java. The Java header for overriding operation hashCode is as follows:
1 @Override
2 public int hashCode()
170
6.9 Specifying the Behaviour Space
Behaviourally, this operation must be consistent with equals. That is, “. . . if two
objects are equal according to the equals(Object) method then calling the hashCode
method on each of the two objects must produce the same integer result.” [23]. Thus,
similar to equals, the parts of the object state that are used to compute the hash code
should be (mostly) immutable.
6.9.9 Helper
A helper operation performs a behaviour that is used by some other operations or
that helps make the objects more useful. Among the commonly useful helper operations
are the followings:
repOK, which is short for “representation OK” [20]
Data validation
Utility
repOK
The primary purpose of this operation is to check the current object representation
to ensure that it satisfies the abstract properties. The idea is that if this check is passed
with every object of the class then the object representation is valid.
Another usage of this operation is to test the validity of an object state against its
abstract properties. Given that the object representation is correct, an object state is
valid (w.r.t to this representation) if all the attribute values satisfy the constraints defined
in the abstract properties. Thus, this operation can be used to identify (and ignore) the
invalid objects in a program. The Java header definition for this operation is as follows:
1 /**
2 * @effects
3 * if this satisfies abstract properties
4 * return true
5 * else
6 * return false
7 */
8 public boolean repOK()
171
6.9 Specifying the Behaviour Space
Data Validation
The purpose of data validation operation is to check that some input data, which are
set for an attribute, are valid w.r.t the attribute’s domain properties. Clearly, if the result
is “No” then the data must not be used to set the attribute. This operation is invoked by
all operations (e.g. constructor, setter, repOK)) that accept and process the input in some
way. Here are the header design guidelines for a data validation operation of an attribute
named A:
operation name has the pattern validateA
access modifier: private
return type is boolean
parameter list contains one parameter, whose type must match the attribute’s data
type
The standard design specification template for this operation should look like this:
1 /**
2 * @effects
3 * if A is valid
4 * return true
5 * else
6 * return false
7 */
8 private boolean validateA(int p)
Note that the @effects does not need to state specifically what the constraints
concerning attribute A are. The statement “A is valid” implies that this it is valid
w.r.t to the constraint properties. A data validation operation of the same class can
invoke some other data validation operations, if neccessary.
Example 6.20 Customer
Listing 6.15 shows the design specification of two data validation of class Customer.
These operations validate the input value for the attributes id and name
Listing 6.15: Customer
1 /**
2 * @effects
3 * if id is valid
4 * return true
5 * else
6 * return false
172
6.9 Specifying the Behaviour Space
7 */
8 private boolean validateId(int id)
9
10 /**
11 * @effects
12 * if name is valid
13 * return true
14 * else
15 * return false
16 */
17 private boolean validateName(String name)
Utility
Utility operations are added to ease the implementation of other operations. They
are determined from the specifications of the existing operations. If the operations are
useful for the general use of objects then they can be defined as public, otherwise they
are defined as private.
An example of a public utility operation is the operation IntSet.isIn, which
checks membership of elements of an integer set. Internally, this method is invoked by
two other essential operations of the class, namely insert and remove. Externally, it is
invoked by the client program to check for set membership.
An example a private utility operation is the operation reduce of a class Rat [20],
which represents rational numbers. This operation reduces a rational number to its basic
form, where the numerator and denominator have no common divisors (e.g. 36 is reduced
to 12 ). This operation is invoked internally by operation equals to check equality of two
irrational numbers.
Example 6.21 IntSet
Listing 6.21 shows the design specification of a private utility operation, named
getIndex, of class IntSet. This operation is used by both insert and remove to
determine whether an element is in the set. Although this can also be achieved by isIn,
operation getIndex can also return the actual index of an element if it is a member of
the set. Operation remove uses this index to remove the element.
1 /**
173
6.10 Specifying the Collection Classes
2 * @effects
3 * if x is in this
4 * return the index where x appears
5 * else
6 * return -1
7 */
8 private int getIndex(int x)
Thus, all three operations isIn, insert and remove of IntSet use operation
getIndex to carry out their behaviours. Note that, unlike isIn, operation getIndex
must not be made public. The main reason is because doing so will make the element
index publicly available, despite that this is not a set property.
174
6.10 Specifying the Collection Classes
6.10.3 Constructor
In the essential design, collection objects are created to be empty and are later
updated with elements via the mutator operations. Thus, the essential constructor of
collection class is the constructor that has an empty parameter list. The header of this
constructor is the same as the default constructor, but its behaviour must state to initialise
an empty object. This involves initialising the elements attribute to be an empty array
175
6.10 Specifying the Collection Classes
6.10.4 Mutator
Two essential operations MutatorAdd and MutatorRemove are responsible for up-
dating a collection with elements. Both operations must preserve the abstract properties
of the collection. For example, operation MutatorRemove must not change the collec-
tion if the input element is not present in the collection. As for operation MutatorAdd,
it must not add the input element if the collection is a set and the element is already a
member of the collection.
Example 6.23 IntSet
Listing 6.18 shows the design specifications of MutatorAdd and MutatorRemove
operations of class IntSet. Both operations contain a @modifies clause which states
that the current collection is updated. The @effects clause uses the notation this_post
to refer to the current IntSet object after it has been modified.
Listing 6.18: IntSet
1 /**
2 * @modifies this
3 * @effects
4 * if x already in this
5 * return false
6 * else
7 * add x to this, i.e., this_post=this+{x}
8 * return true
9 */
10 @DOpt(type=OptType.MutatorAdd)
11 public boolean insert(int x)
12
176
6.10 Specifying the Collection Classes
13 /**
14 * @modifies this
15 * @effects
16 * if x is not in this
17 * return false
18 * else
19 * remove x from this, i.e. this_post=this-{x}
20 * return true
21 */
22 @DOpt(type=OptType.MutatorRemove)
23 public boolean remove(int x)
6.10.5 Observer
As discussed earlier in this section, two essential observer operations ObserverContains
and ObserverSize respectively provide information about the membership of an el-
ement and the number of elements in the collection. Another essential observer that
is also commonly found in a collection class is one that returns the elements in some
fashion. In this book, we will consider a most basic type of such operation. It is a
getter operation that returns an array of the elements. This operation is marked as an
Observer. Again, there is no need to annotate the operation with @AttrRef, because it
operates on the elements attribute.
Besides the above operations, other observers may be added depending on the
specific need of the collection type.
Example 6.24 IntSet
Listing 6.19 shows the design specification of four observer operations of class
IntSet. The first three operations are the essential operations of the class. The fourth
operation is an example of a useful observer operation for IntSet. It returns an arbitrarily
element of the set.
Listing 6.19: IntSet
1 /**
2 * @effects
3 * if x is in this
4 * return true
5 * else
177
6.10 Specifying the Collection Classes
6 * return false
7 */
8 @DOpt(type=OptType.ObserverContains)
9 public boolean isIn(int x)
10
11 /**
12 * @effects return the cardinality of this
13 */
14 @DOpt(type=OptType.ObserverSize)
15 public int size()
16
17 /**
18 * @effects
19 * if this is not empty
20 * return array Integer[] of elements of this
21 * else
22 * return null
23 */
24 @DOpt(type=OptType.Observer)
25 public Integer[] getElements()
26
27 /**
28 * @effects
29 * if this is empty
30 * throw an IllegalStateException
31 * else
32 * return an arbitrary element of this
33 */
34 @DOpt(type=OptType.Observer)
35 public int choose() throws IllegalStateException
178
6.10 Specifying the Collection Classes
K Chapter 6 Exercise k
The exercises in this chapter help practise class design with UML class diagram notation
and design specification. To ease reading, some of the relevant exercises given in [20]
are reproduced here.
1. (Greeting Conversation) Figure 6.17 is an extended design diagram of the greet-
ing conversation program discussed in the previous tutorial. This diagram shows
a few more attributes of the two classes Person and MobilePhone, but it presents
only a partial list of operations.
Figure 6.17: An initial design diagram for the greeting conversation program.
The following table is a partially completed table of the domain constraints that
apply to the attributes of the two classes in Figure 6.17. Note that the “type”
column lists the formal types of the attributes. Attribute MobilePhone.color
takes a character value that denotes a colour of the phones. The characters are: ‘R’
(for red), ‘O’ (for orange), ‘Y’ (for yellow), ‘B’ (for blue), ‘P’ (for purple). Attribute
MobilePhone.guaranteed takes the value true for a mobile phone if this phone
has a guarantee; it takes the value false if otherwise.
(a). Complete the domain constraints in the table, using your practical under-
standing of the application.
(b). Write the header and state space specifications for each class.
(c). Determine a minimum set of operations needed for each class. Justify your
choice of each operation.
(d). Write the behaviour space specification for each class.
179
6.10 Specifying the Collection Classes
2. (Greeting conversation v1.1) Implement an enum named Color that catures the
different colours mentioned in the program requirement. Update class MobilePhone
to use this enum.
3. (Greeting conversation v1.2) Update class MobilePhone to address an additional
constraint that attribute model must be of the form M-ABC−M N P , where ABC
is a 3-letter word and M N P is a 3-digit word. For example, M-SAM-123 is a valid
phone model, but M-S0M-123 is not.
4. (Greeting conversation v1.3) Update class Person to address an additional con-
straint that attribute name must consist of at least two words that are separated by
a white space.
5. Specify a class EvenIntSet that represents a set of even numbers. This is an
integer set that only accepts even numbers as elements.
6. (see [20]) Specify a map class, named StringIntMap, which maps strings to
integers. Maps allow an existing mapping to be looked up. Maps are also mutable:
new pairs can be added to a map, and an existing mapping can be removed. Be
sure that your data type is adequate.
7. (see [20]) Specify a class IntQueue that represents a bounded queue of integers.
A bounded queue is a queue that has an upper bound, established when the queue
is created, on the number of integers that can be stored in the queue. Queues are
mutable and provide access to their elements in first-in/first-out order. IntQueue
operations include:
IntQueue(int n)
enq(int x)
int deq()
The constructor creates a new queue with maximum size n, enq adds an element
to the front of the queue, and deq removes the element from the end of the queue.
You may include extra operations as needed for adequacy.
8. (see [20]) Specify a rational number type, named Rat.
180
6.A Customer
6.A Customer
The complete specification of Customer.
1 import utils.AttrRef;
2 import utils.DOpt;
3 import utils.DomainConstraint;
4 import utils.NotPossibleException;
5 import utils.OptType;
6 /**
7 * @overview Customers are people or organisations with which we
have relationships.
8 * @attributes
9 * id Integer int
10 * name String
11 * @object A typical Customer is c=<d,n>, where id(d), name(n).
12 * @abstract_properties
13 * mutable(id)=false /\ optional(id)=false /\ min(id)=1 /\
14 * mutable(name)=true /\ optional(name)=false /\ length(name)=50
15 * @author dmle
16 */
17 public Customer {
18 @DomainConstraint(mutable = false, optional = false, min =
MIN_ID)
19 private int id;
20
24 // constants
25 private static final int MIN_ID = 1;
26 private static final int LENGTH_NAME = 50;
27
28 /**
29 * @effects
30 * if custID, name are valid
31 * initialise this as <custID,name>
181
6.A Customer
32 * else
33 * throws NotPossibleException
34 */
35 public Customer(@AttrRef("id") int custID, @AttrRef("name")
String name) throws NotPossibleException
36
37 /**
38 * @effects
39 * if name is valid
40 * set this.name to name
41 * return true
42 * else
43 * return false
44 */
45 @DOpt(type=OptType.Mutator) @AttrRef("name")
46 public boolean setName(String name)
47
48 /**
49 * @effects return id
50 */
51 @DOpt(type=OptType.Observer) @AttrRef("id")
52 public void getId()
53
54 /**
55 * @effects return name
56 */
57 @DOpt(type=OptType.Observer) @AttrRef("name")
58 public String getName()
59
60 /**
61 * @effects
62 * if id is valid
63 * return true
64 * else
65 * return false
66 */
182
6.B IntSet
69 /**
70 * @effects
71 * if name is valid
72 * return true
73 * else
74 * return false
75 */
76 private boolean validateName(String name)
77
78 @Override
79 public String toString()
80
81
82 @Override
83 public boolean equals(Object o)
84
85 /**
86 * @effects
87 * if this satisfies abstract properties
88 * return true
89 * else
90 * return false
91 */
92 public boolean repOK()
93 }
6.B IntSet
The complete specification of IntSet.
1 import java.util.Vector;
2 import utils.DOpt;
3 import utils.DomainConstraint;
4 import utils.OptType;
183
6.B IntSet
5 import utils.collections.Collection;
6 /**
7 * @overview IntSet are mutable, unbounded sets of integers.
8 * @attributes
9 * elements Set<Integer> Vector<Integer>
10 * @object A typical IntSet object is c={x1,...,xn}, where x1
,...,xn are
11 * elements.
12 * @abstract_properties
13 * mutable(elements)=true /\ optional(elements)=false /\
14 * elements != {} -> (for all x in elements. x is integer) /\
15 * elements != {} -> (for all x, y in elements. x != y)
16 *
17 * @author dmle
18 */
19 public class IntSet implements Collection {
20 @DomainConstraint(optional = false)
21 private Vector<Integer> elements;
22
23 /**
24 * @effects initialise this to be empty
25 */
26 public IntSet()
27
28 /**
29 * @modifies this
30 * @effects
31 * if x already in this
32 * return false
33 * else
34 * add x to this, i.e., this_post=this+{x}
35 * return true
36 */
37 @DOpt(type=OptType.MutatorAdd)
38 public boolean insert(int x)
39
184
6.B IntSet
40 /**
41 * @modifies this
42 * @effects
43 * if x is not in this
44 * return false
45 * else
46 * remove x from this, i.e. this_post=this-{x}
47 * return true
48 */
49 @DOpt(type=OptType.MutatorRemove)
50 public boolean remove(int x)
51
52 /**
53 * @effects
54 * if x is in this
55 * return true
56 * else
57 * return false
58 */
59 @DOpt(type=OptType.ObserverContains)
60 public boolean isIn(int x)
61
62 /**
63 * @effects
64 * if this is empty
65 * throw an IllegalStateException
66 * else
67 * return an arbitrary element of this
68 */
69 @DOpt(type=OptType.Observer)
70 public int choose() throws IllegalStateException
71
72 /**
73 * @effects return the cardinality of this
74 */
75 @DOpt(type=OptType.ObserverSize)
185
6.B IntSet
78 @Override
79 public String toString()
80
81 @Override
82 public boolean equals(Object o)
83
84 /**
85 * @effects
86 * if this satisfies abstract properties
87 * return true
88 * else
89 * return false
90 */
91 public boolean repOK()
92 }
186
Chapter 7
Design Review and Coding
Objectives
" Appreciate the importance of design review.
" Be able to use a tool for checking the program design.
" Understand the general guidelines and a coding procedure of an OOP.
" Apply the specific coding guidelines for each of the essential operation types
(constructor, multator, observer, default and helper).
" Undertake OOP coding in the Java language.
Before coding can begin, it is necessary to check the design for deffects. Any defects
that are found need to satisfactorily be resolved. Because the review is performed on
the basis of well-defined design rules, it would be useful to develop these rules into
a program and use this program to help automate the review tasks. Once the review
has been completed, coding can proceed. The general coding guidelines for procedural
programs are applicable but should be adjusted to suit the design elements of an OOP.
This chapter first presents a design review approach and a Java program named
OOPChecker, which is used to automate the review of OOPs written in Java. After
that, this chapter describes the coding guidelines and a coding procedure for OOP. The
general guidelines are explained first, which are followed by those for each operation
type.
188
7.2 OOPChecker: A Design Validation Tool
7.2.1 Overview
OOPChecker is designed to process an extensible set of design rules, which currently
include the essential design rules that are represented by the set of annotations discussed
in this book. Other design rules can and should be introduced in order to evolve this tool
to support better quality program design.
The design rules concern the following types of program elements: class, field
(attribute), method and a limited set of code elements in the method body. The tool
is executed at compile-time and produces as output the design errors and/or warnings
that the developer can then resolve for the design. To improve productivity, the tool is
integrated into the Eclipse IDE in the form of a plug-in. A benefit of this is that the
tool can leverage the Eclipse’s GUI to detect the input program and to display the output
directly on a designated GUI component.
Figure 7.1 shows how the OOPChecker is used in the Eclipse IDE. The tool can be
invoked via a tool bar button or a menu item. The input program is selected from the
“Project Explorer” tab while the output messages are displayed on the “Problems” tab.
With this, the design errors are treated as compile-time errors which must be resolved
before the program can be executed.
The tool can be used for checking tutorial exercises or assignment programs. Note
that the tool does not validate the correctness of the code, as this requires not only a
formal design specification but a logic evaluator tool. This tool basically treats the code
and the design specification as two logic programs and checks if the former satisfies
189
7.2 OOPChecker: A Design Validation Tool
Toolbar
buttons
Individual
menu
the later. There is a body of work devoted to the study and design of this type of tool.
However, these are outside the scope of this book.
Table 7.1: The essential design rules set that are supported by OOPChecker.
Rule Description
DR1 State space must be specified
DR2 Behaviour space must be specified
DR3 Number-typed domain field should have @DAttr.min and/or max specified
DR4 String-typed domain field should have @DAttr.length specified
A required constructor method must include parameters for all mandatory,
non-auto, non-collection-typed fields. Further, each parameter must be
DR5
attached to an @AttrRef, whose value is set to name of the corresponding
field
An observer method of a field must be attached to an @AttrRef, whose value
DR6
is set to the field’s name
A mutator method of a field must be attached to an @AttrRef, whose value is
DR7
set to the field’s name
Design rule DR5 states the design rule for the essential constructor. It basically
states that if a class has mandatory, non-auto and non-collection-typed fields then the
class must have at least one constructor, whose parameters are mapped to those fields
190
7.3 General Implementation Guidelines
(one parameter is used to initialise the value of one field). For example, Customer
.id and name are mandatory, non-auto and non-collection-typed fields. Thus, class
Customer needs to have at least one essential constructor method of the form Customer
(id: int, name: String). The two parameters id and name are mapped to (i.e. used
to initialise) the fields Student.id and name (respectively).
191
7.4 Constructor
7.4 Constructor
The focus of section is on coding the essential constructor. Coding other construc-
tors would follow similar guidelines. Recall that the general behaviour of the essential
constructor is to validate the input arguments and then either initialise the object state
or throw an exception. Data validation involves invoking the data validation methods,
while throwing an exception follows this syntax: throw new NotPossibleException
(mesg);. Variable mesg represents an error message that contains the constructor name
and the argument value. Another point to note is that in order to specialise the error
message for each argument, separate exception needs to be throwns.
In the case of collection class (e.g. IntSet), the essential constructor simply ini-
tialises the object state to be an empty collection.
Example 7.1 Constructor implementation
Listings 7.1 and 7.2 show the Java code of the essential constructors of the two
classes Customer and IntSet (resp.). To ease reading, the behaviour descriptions
are repeated from the previous chapter. As can be seen from Listing 7.1, constructor
Customer invokes validateId and validateName to validate the arguments custID
and custName. If a violation is found then an exception is thrown immediately. The
fields id and name are initialised to the arguments only after the code has passed both
validations. The constructor code in Listing 7.2 simply initialises elements to an
empty Vector<Integer>. Note that Java allows a short-hand initialisation syntax of
Vector<>, which means to takes the type parameter (Integer) from the declared type
of elements.
Listing 7.1: Customer
1 /**
2 * @effects
3 * if custID, name are valid
4 * initialise this as <custID,name>
5 * else
6 * throws NotPossibleException
7 */
8 public Customer(@AttrRef("id") int custID, @AttrRef("name")
String name) throws NotPossibleException {
9 if (!validateId(custID)) {
10 throw new NotPossibleException("Customer.init(): invalid id:
" + custID);
192
7.5 Mutator
11 }
12 if (!validateName(name)) {
13 throw new NotPossibleException("Customer.init(): invalid name
: " + name);
14 }
15 id = custID;
16 this.name = name;
17 }
7.5 Mutator
Similar to constructor, the mutator’s general behaviour is to update the object state
from some input argument. After validating the argument, it updates the object state (if
appropriate) and returns a boolean value indicating the validation result.
Example 7.2 Mutator implementation
Listings 7.3 and 7.4 show the Java code of the mutator operations of the two classes
Customer and IntSet (resp.). To ease reading, the behaviour descriptions are repeated
from the previous chapter. As can be seen from Listing 7.3, the code invokes method
validateName to check the input argument name. Field name is only initialised to the
argument if the code has passed this validation.
In Listing 7.4, both MutatorAdd and MutatorRemove operations invoke the helper
operation getIndex to retrieve the index of the input element. This index is used to
determine the existence of the element and also to remove it from the set.
Listing 7.3: Customer
1 /**
2 * @modifies this
3 * @effects
193
7.5 Mutator
4 * if name is valid
5 * set this.name=name
6 * return true
7 * else
8 * return false
9 */
10 @DOpt(type=OptType.Mutator) @AttrRef("name")
11 public boolean setName(String name) {
12 if (validateName(name)) {
13 this.name = name;
14 return true;
15 } else {
16 return false;
17 }
18 }
194
7.6 Observer
20 /**
21 * @modifies this
22 * @effects
23 * if x is not in this
24 * return false
25 * else
26 * remove x from this, i.e. this_post = this - {x}
27 * return true
28 */
29 @DOpt(type=OptType.MutatorRemove)
30 public boolean remove(int x) {
31 int i = getIndex(x);
32 if (i < 0) {
33 return false;
34 } else {
35 elements.set(i, elements.lastElement());
36 elements.remove(elements.size() - 1);
37 return true;
38 }
39 }
7.6 Observer
In general, the observer’s code basically returns information obtained from the
relevant object state. In some cases, care should be taken not to expose the object state
to unexpected modifications by the client program. This would involve transforming the
attribute value into a different form before returning it. We will discuss this and other
design issues in a later chapter.
Example 7.3 Observer implementation
Listings 7.5 and 7.6 show the Java code of the observer operations of the two classes
Customer and IntSet (resp.). The observers’ code in Listing 7.5 are basically the same
as their behaviours. The observers in Listing 7.6 make use of the helper operations
(e.g. getIndex) and the relevant Vector’s operations to obtain the necessary state
information. Note that operation getElements does not return elements directly,
195
7.6 Observer
although this is an allowed syntax in Java. Instead, the method transforms elements
into an array (using the Collection.toArray operation) and returns this. The main
reason for this transformation is to completely shield the attribute elements from outside
access by the client program. If the operation returned elements then the client program
has access to the reference to the Vector object pointed to by elements. The program
can modify this Vector directly, without using the IntSet mutator methods.
Listing 7.5: Customer
1 /**
2 * @effects return id
3 */
4 @DOpt(type=OptType.Observer) @AttrRef("id")
5 public int getId() {
6 return id;
7 }
8
9 /**
10 *
11 * @effects return name
12 */
13 @DOpt(type=OptType.Observer) @AttrRef("name")
14 public String getName() {
15 return name;
16 }
196
7.6 Observer
12
13 /**
14 * @effects
15 * if this is empty
16 * throw an IllegalStateException
17 * else
18 * return an arbitrary element of this
19 */
20 @DOpt(type=OptType.Observer)
21 public int choose() throws IllegalStateException {
22 if (size() == 0)
23 throw new IllegalStateException("IntSet.choose: set is empty"
);
24
25 return elements.lastElement();
26 }
27
28 /**
29 * @effects return the cardinality of this
30 */
31 @DOpt(type=OptType.ObserverSize)
32 public int size() {
33 return elements.size();
34 }
35
36 /**
37 * @effects
38 * if this is not empty
39 * return array Integer[] of elements of this
40 * else
41 * return null
42 */
43 @DOpt(type=OptType.Observer)
44 public Integer[] getElements() {
45 if (size() == 0)
46 return null;
197
7.7 Default Operation
47 else
48 return elements.toArray(new Integer[size()]);
49 }
198
7.7 Default Operation
10 .append(elements.elementAt(i).toString());
11 }
12 s.append("}");
13 return s.toString();
14 }
Example 7.5 Customer
Listing 7.8 shows the code of Customer.toString. The code sets up the string
format as specified in the class header specification. This format takes two arguments:
one numeric (%d) and one string (%s). These arguments are replaced by the values of
the two attributes id and name (resp.).
Listing 7.8: Customer
1 @Override
2 public String toString() {
3 return String.format("Customer:<%d,%s>", id, name);
4 }
199
7.7 Default Operation
object o and whether or not it has the expected type. After this, the object is casted into
the target type in order to access state information. For operation Customer.equals
the attribute value id is used as the basis for comparison. This attribute has a primitive
type, so the comparison is simply the equality operator ‘==’.
For operation IntSet.equals, however, the object state is a Vector object (at-
tribute elements). Thus, the comparison is performed using the operation equals of
the Vector class. This operation performs equality based on the collection size and
its elements. More specifically, given that the two Vectors have the same size, the
corresponding pairs of elements in the two collections need to be equal. Each element
pair is compared for equality by using the equals operation of the element type.
Listing 7.9: Customer
1 @Override
2 public boolean equals(Object o) {
3 if ((o == null) || !(o instanceof Customer))
4 return false;
5
200
7.8 Helper
(e.g. IntSet) is more complex and would intuitively involve combining the hash codes
of the elements. The interested reader should read the Java’s API documentations of
these two methods Set.hashCode2 or List.hashCode3 for some insights.
Example 7.7 Implementation of hashCode
Listing 7.11 shows the code of Customer.hashCode. In this case, the code simply
returns id, because this is an integer value that is unique across all the objects. In general,
if Customer.id’s type a non-collection type (e.g. String, Date, a user-defined type,
etc.) then the hash code value should be the one obtained from invoking the operation
hashCode of the type.
Listing 7.11: Customer
1 @Override
2 public int hashCode() {
3 return id;
4 }
7.8 Helper
Recall that there are three types of helper operations that need to be implemented:
(1) repOK, (2) data validation and (3) utility. This section will briefly discuss the
implementation of each operation type.
2https://docs.oracle.com/javase/8/docs/api/java/util/Set.html#hashCode--
3https://docs.oracle.com/javase/8/docs/api/java/util/List.html#hashCode--
201
7.8 Helper
16 /**
17 * @effects
18 * if name is valid
19 * return true
20 * else
21 * return false
22 */
23 private boolean validateName(String name) {
24 return (name != null &&
25 name.length() > 0 &&
26 name.length() <= LENGTH_NAME);
27 }
202
7.8 Helper
Example 7.10 IntSet
Listing 7.14 shows the code of the operation IntSet.repOK. In this case, because
no data validation operation against the attribute elements is available, the code needs
to implement the abstract properties by itself. The three abstract properties of IntSet
203
7.8 Helper
are marked P1, P2 and P3 in the code comments. This helps easily identify the code
sections check these properties. Briefly, property P1 involves a null check. Property
P2 is automatically satisfied because of the use of Vector<Integer>. Property P3 is
checked by a nested loop that searches for duplicate elements. If a duplicate is found
then the code returns false immediately.
Listing 7.14: IntSet
1 /**
2 * @effects
3 * if this satisfies abstract properties
4 * return true
5 * else
6 * return false
7 */
8 public boolean repOK() {
9 // P1: optional(elements) = false
10 if (elements == null)
11 return false;
12
204
7.9 Implementing the main method
7.8.3 Utility
Apart from the general guidelines discussed in Section 7.3, it is difficult to state
any concrete coding guidelines for a utility operation without being specific about its
behaviour. Listing 7.15 shows the code of the utility operation IntSet.getIndex.
The code uses a loop over the elements to find and return the position of a matching
element. An alternative and much simpler code is to take advantage of the method
Vector.indexOf, which performs exactly the same behaviour. This alternative consists
in a single line of code, which is written in the comment ‘// ALT’ at the top of the
method body.
Listing 7.15: IntSet
1 /**
2 * @effects
3 * if x is in this
4 * return the index where x appears
5 * else
6 * return -1
7 */
8 private int getIndex(int x) {
9 // ALT: return elements.indexOf(x);
10 for (int i = 0; i < elements.size(); i++) {
11 if (x == elements.get(i))
12 return i;
13 }
14 return -1;
15 }
205
7.9 Implementing the main method
We consider two main programs: one program, named CRM, is to work with
Customer and the other, named Integers, is to work with IntSet. We conclude
this section with a program that demonstrates the use of wrapper classes.
206
7.9 Implementing the main method
22 /**
23 * @effects create some valid and invalid customer objects and
24 * display their details
25 */
26 public static void main(String[] args) {
27 CRM bp = new CRM();
28 String[] names = {"Nguyen Van A", null, "Tran Van Tuan"};
29 Customer c;
30 for (String name: names) {
31 try {
32 c = bp.createCustomer(name);
33 System.out.println("Created customer: " + c);
34 } catch (NotPossibleException e) {
35 System.err.println("Could not create a customer with name:
" + name);
36 e.printStackTrace();
37 }
38 }
39 }
40 } // end CRM
7.9.2 Integers
Integers is a simple program for IntSet class that creates an object of this class
and invokes some operations on this object to update or display its elements. The
program code is shown in Listing 7.17. The code uses the method Arrays.toString
to conveniently obtain a string representation of an array’s elements.
Listing 7.17: Program Integers
1 import java.util.Arrays;
2 /**
3 * @overview A program that creates a set of integers and
207
7.9 Implementing the main method
208
7.9 Implementing the main method
7 */
8 public static void main(String[] args) {
9 // create using constructor
10 Integer i = new Integer(10); /* i = 10 */
11 // create object using parse operation
12 i = Integer.parseInt("10"); /* i = 10 */
13 // create object using auto-boxing
14 i = 5; /* i = 5 */
15 // unboxing in expression
16 int e = i + 10; /* e = 15 */
17 // convert back to primitive using intValue
18 int p = i.intValue(); /* p = 15 */
19 // convert using unboxing
20 p = i; /* p = 5 */
21 }
22 }
209
7.9 Implementing the main method
K Chapter 7 Exercise k
The exercises in this chapter continue from those in Chapter 6 with two main objectivies:
(1) review the design and (2) implement the design in Java. Note that some exercises
were reproduced from [20].
1. (Greeting Conversation) Review the design of and implement the GreetingConversation
program of Exercise 6.1:
(a). Review the design of and implement class Person.
(b). Review the design of and implement class MobilePhone.
(c). Create an program class named GreetingConversation, whose main
method performs the following basic object manipulation tasks:
create a MobilePhone object.
create a Person object.
check that the objects are valid and if so display information about them,
else display suitable error messages.
2. (Greeting Conversation v1.1–1.3) Review the design of and implement the three
improvements to GreetingConversation discussed in Exercise 6.2-Exercise 6.4.
Update method GreetingConversation.main to make use of the improved de-
sign.
3. Review the design of and implement class EvenIntSet of Exercise 6.5. Create
an program class named EvenIntegers, whose main method performs the basic
object manipulation of EvenIntSet.
4. Review the design of and implement class StringIntMap Exercise 6.6. Create an
program class named MixedMaps, whose main method performs the basic object
manipulation of StringIntMap.
5. Review the design of and implement class IntQueue Exercise 6.7. Create an
program class named NumQueue, whose main method performs the basic object
manipulation of IntQueue.
6. Review the design of and implement class Rat Exercise 6.8. Create an program
class named Rationals, whose main method performs the basic object manipu-
lation of Rat.
210
7.A Customer
7.A Customer
The complete Java code of Customer.
1 import utils.AttrRef;
2 import utils.DOpt;
3 import utils.DomainConstraint;
4 import utils.NotPossibleException;
5 import utils.OptType;
6 /**
7 * @overview Customers are people or organisations with which we
have relationships.
8 * @attributes
9 * id Integer
10 * name String
11 * @object A typical Customer is c=<d,n>, where id(d), name(n).
12 * @abstract_properties
13 * mutable(id)=false /\ optional(id)=false /\ min(id)=1 /\
14 * mutable(name)=true /\ optional(name)=false /\ length(name)
=50
15 * @author dmle
16 */
17 public class Customer {
18 @DomainConstraint(type = "Integer", mutable = false,
19 optional = false, min = MIN_ID)
20 private int id;
21
25 // constants
26 private static final int MIN_ID = 1;
27 private static final int LENGTH_NAME = 50;
28
29 // constructor methods
30 /**
211
7.A Customer
31 * @effects <pre>
32 * if custID, name are valid
33 * initialise this as <custID,name>
34 * else
35 * throws NotPossibleException
36 */
37 //@DOpt(type=OptType.Constructor)
38 public Customer(@AttrRef("id") int custID, @AttrRef("name")
String name)
39 throws NotPossibleException {
40 // if custID, name are valid
41 if (!validateId(custID)) {
42 throw new NotPossibleException("Customer.init: Invalid
customer id: " + custID);
43 }
44
45 if (!validateName(name)) {
46 throw new NotPossibleException("Customer.init: Invalid
customer name: " + name);
47 }
48
54 /**
55 * @effects <pre>
56 * if name is valid
57 * set this.name=name
58 * return true
59 * else
60 * return false</pre>
61 */
62 @DOpt(type=OptType.Mutator) @AttrRef("names")
63 public boolean setName(String name) {
212
7.A Customer
64 if (validateName(name)) {
65 this.name = name;
66 return true;
67 } else {
68 return false;
69 }
70 }
71
72 /**
73 * @effects return <tt>id</tt>
74 */
75 @DOpt(type=OptType.Observer) @AttrRef("id")
76 public int getId() {
77 return id;
78 }
79
80 /**
81 * @effects return <tt>name</tt>
82 */
83 @DOpt(type=OptType.Observer)
84 @AttrRef("name")
85 public String getName() {
86 return name;
87 }
88
89 /**
90 * @effects <pre>
91 * if id is valid
92 * return true
93 * else
94 * return false
95 * </pre>
96 */
97 private boolean validateId(int id) {
98 return id >= MIN_ID;
99 }
213
7.A Customer
100
101 /**
102 * @effects <pre>
103 * if name is valid
104 * return true
105 * else
106 * return false</pre>
107 */
108 private boolean validateName(String name) {
109 return (name != null &&
110 name.length() > 0 &&
111 name.length() <= LENGTH_NAME);
112 }
113
114 @Override
115 public String toString() {
116 return String.format("Customer:<%d,%s>", id, name);
117 }
118
119 @Override
120 public boolean equals(Object o) {
121 if (o == null || !(o instanceof Customer))
122 return false;
123
128 @Override
129 public int hashCode() {
130 return id;
131 }
132
133 /**
134 * @effects <pre>
135 * if this satisfies abstract properties
214
7.B IntSet
7.B IntSet
The complete Java code of IntSet.
Listing 7.19: IntSet
1 import java.util.Vector;
2 import utils.DOpt;
3 import utils.DomainConstraint;
4 import utils.OptType;
5 import utils.collections.Collection;
6 /**
7 * @overview IntSet are mutable, unbounded sets of integers.
8 * @attributes
9 * elements Set<Integer> Vector<Integer>
10 * @object A typical IntSet object is c={x1,...,xn}, where x1
,...,xn are
11 * elements.
12 * @abstract_properties
13 * optional(elements) = false /\
14 * for all x in elements. x is integer /\
15 * for all x, y in elements. x neq y
16 * @author dmle
17 */
18 public class IntSet implements Collection {
19 @DomainConstraint(optional = false)
20 private Vector<Integer> elements;
21
215
7.B IntSet
22 // constructor methods
23 /**
24 * @effects initialise <tt>this</tt> to be empty
25 */
26 public IntSet() {
27 elements = new Vector<>();
28 }
29
30 /**
31 * @modifies <tt>this</tt>
32 * @effects <pre>
33 * if x is already in this
34 * return false
35 * else
36 * add x to this, i.e., this_post = this + {x}
37 * return true
38 * </pre>
39 */
40 @DOpt(type=OptType.MutatorAdd)
41 public boolean insert(int x) {
42 if (getIndex(x) < 0) {
43 elements.add(x); // auto-boxing
44 return true;
45 } else {
46 return false;
47 }
48 }
49
50 /**
51 * @modifies <tt>this</tt>
52 * @effects <pre>
53 * if x is not in this
54 * return false
55 * else
56 * remove x from this, i.e. this_post = this - {x}
57 * return true
216
7.B IntSet
58 * </pre>
59 */
60 @DOpt(type=OptType.MutatorRemove)
61 public boolean remove(int x) {
62 int i = getIndex(x);
63 if (i < 0) {
64 return false;
65 } else {
66 elements.set(i, elements.lastElement());
67 elements.remove(elements.size() - 1);
68 return true;
69 }
70 }
71
72 /**
73 * @effects <pre>
74 * if x is in this
75 * return true
76 * else
77 * return false</pre>
78 */
79 @DOpt(type=OptType.ObserverContains)
80 public boolean isIn(int x) {
81 return (getIndex(x) >= 0);
82 }
83
84
85 /**
86 * @effects return the cardinality of <tt>this</tt>
87 */
88 @DOpt(type=OptType.ObserverSize)
89 public int size() {
90 return elements.size();
91 }
92
93 /**
217
7.B IntSet
94 * @effects
95 * if this is not empty
96 * return array Integer[] of elements of this
97 * else
98 * return null
99 */
100 @DOpt(type=OptType.Observer)
101 public Integer[] getElements() {
102 if (size() == 0)
103 return null;
104 else
105 return elements.toArray(new Integer[size()]);
106 }
107
108 /**
109 * @effects <pre>
110 * if this is empty
111 * throw an IllegalStateException
112 * else
113 * return an arbitrary element of this</pre>
114 */
115 public int choose() throws IllegalStateException {
116 if (size() == 0)
117 throw new IllegalStateException("IntSet.choose: set is empty
");
118 return elements.lastElement();
119 }
120
121 /**
122 * @effects <pre>
123 * if x is in this
124 * return the index where x appears
125 * else
126 * return -1</pre>
127 */
128 private int getIndex(int x) {
218
7.B IntSet
137 @Override
138 public String toString() {
139 if (size() == 0)
140 return "IntSet:{}";
141
152 @Override
153 public boolean equals(Object o) {
154 if (o == null && !(o instanceof IntSet))
155 return false;
156
161 /**
162 * @effects <pre>
163 * if this satisfies abstract properties
164 * return true
219
7.B IntSet
165 * else
166 * return false</pre>
167 */
168 public boolean repOK() {
169 // P1: optional(elements) = false
170 if (elements == null)
171 return false;
172
220
Chapter 8
Design Issues
Objectives
" Understand the four basic class design issues.
" Explain an object’s lifecycle, object initialisation and reference, stack and heap
memory and how object is passed in a method call.
" Be able to create private constructors of a class.
" Be able to clone an object.
" Be able to design an inner class when needed.
" Be able to create a generic class.
Having discussed the class design fundamentals, let us discuss in this chapter the
complete set of class design issues. First, we review the basic class design issues in the
context of the design approach presented in the previous chapter. Second, we discuss a
number of additional issues concerning objects. Third, we explain private constructors
and when they should be designed in a class. Fourth, we discuss the default method for
cloning objects and how to design this method. Last but not least, we present the design
of inner class and generic class. Some of the design features presented in this chapter
will be used in a later chapter to define design patterns and abstract data types.
object-typed, mutable attributes from either being set directly in or being returned
from public methods
The first technique was already discussed in the previous chapter. The second
technique will be discussed in the context of encapsulation.
8.1.2 Encapsulation
An orthogonal issue to information hiding is encapsulation, which is to design
suitable public operations to allow objects of other classes to interact with its objects.
Which operations to use and how to design them are the concern of encapsulation. The
class design method discussed in the previous chapter helps answer these questions at
the fundamental level. There is one additional subtle issue that needs to be addressed,
which concerns public operations that operate on mutable attributes. Let us explain what
this issue is and how to resolve it.
222
8.1 Basic Design Issues
9 }
Thus, both innocent-looking operations in this example potentially breaks the class
encapsulation by allowing the using code to directly modify the value of attribute IntSet
.elements. To avoid object reference leakings such as this, extra care should be taken
to:
not directly assign attribute to an argument of a public operation, and
not return the attribute value directly from a public operation
Let us discuss how to implement each of these rules in the context of collection-
typed classes. We will use IntSet to demonstrate.
223
8.1 Basic Design Issues
224
8.1 Basic Design Issues
225
8.2 Example: Customer
14 sb.append(",").
15 append(dob);
16 }
17 sb.append(">");
18
19 return sb.toString();
20 }
21
22 /**
23 * @effects
24 * return Customer:<id,name>
25 */
26 @Override
27 public String toString() {
28 return toString(true);
29 }
226
8.3 Object Life Cycle
Figure 8.2: The object life cycle showing the high-level states and the transitions between them.
Unused objects may or may not be removed immediately from memory. For safety
reasons, both Java and C# automatically manage the removal of unused objects. The
run time environment maintains a separate schedule (named garbage collection) that
is responsible for removing unused objects from memory. The arrow labelled “garbage
collect” in the figure demonstrates garbage collection, showing the transition from the
state unused to the final (terminated) state.
227
8.3 Object Life Cycle
228
8.3 Object Life Cycle
Figure 8.3 illustrates object reference with a Customer object. When this object
is created with the new keyword, the object reference (not the object) is assigned to the
variable cust. This reference is illustrated in the figure by an arrow connecting the
variable to the object. Note that the figure actually shows two other object references,
which point to two objects of the types String and Date. These objects were created
and used as input for initialising the attributes name and dob (resp.) of the Customer
object.
In both Java and C#, a program creates objects and works with their references dur-
ing execution. However, as discussed earlier, the object life time is managed separately
by the run-time environment (through garbage collection). A program can declare an
object to be no longer in use, but it can not control when the object is actually removed
from memory. Let us then discuss the memory arrangement for the objects and their
references.
229
8.3 Object Life Cycle
manage data values and objects. Although the discussion here focuses on the Java VM,
a similar understanding also exists for the C# counterpart.
Recall that stack memory stores data associated with an operation invocation. The
data include input arguments and local variables. On the other hand, heap memory is
a shared memory area that holds objects. Although an object is typically created during
the execution of an operation, the object itself is not placed in the stack. The object is
placed in the heap, while its reference (which is assigned to a local variable) is kept in
the stack. Conceptually, the variables in the stack, the objects and the heap and their
references form a directed graph. To help visualise this graph and the impacts of the state
changes that occur during program execution, we introduce stack and heap diagram.
This is basically a directed graph that consists of two sets of nodes: one set is located
in the stack and the other is located in the heap. Let us illustrate this diagram with two
examples.
Example 8.3 Stack and heap (1)
Listing 8.3 shows a class StackAndHeap, which demonstrates the stack and heap
diagram. It implements a code segment given in [20]. To understand the effect of
the code on stack and heap, let us divide it into two segments. Figure 8.4 shows two
snapshots of the stack-and-heap diagram, which maps out the contents of stack and heap
for each code segment. The first segment consists in the lines 3-8, which initialise two
primitive-typed variables i, j and four object-typed variables a, b, s and t. The second
segment consists in lines 9-11, which are variable assignments involving these variables.
1 public class StackAndHeap {
2 public void op() {
3 int i = 6;
4 int j; // uninitialised
5 int[] a = {1,3,5,7,9}; // creates a 5-element array
6 int[] b = new int[3];
7 String s = "hello"; // creates a new string
8 String t = null;
9 j = i;
10 b = a;
11 t = s;
12 }
13 }
The left-hand-side snapshot in Figure 8.4 shows the stack of the operation op and
230
8.3 Object Life Cycle
the heap containing three objects. The stack lists six variables and their values. Variable
i’s value is 6, while j is uninitialised (illustrated as an empty box). Variable t is null.
The values of a, b, and s are references that point to three objects in the heap. These
references are illustrated by three arrows that connect the variables to the objects. Note
that b’s elements are initialised to the default values of 0.
The right-hand-side snapshot in the figure shows updates to the variable values
after the second segment is executed. Specifically, variable b now contains a copy of the
reference to the same array object as variable a. Both variables point to the same object.
Similarly, t now contains a copy of the reference to the same String object as s.
The array object [0,0,0] that b initially pointed to is now unused and is subject to
be garbage collected.
Example 8.4 Stack and heap (2)
Let us consider another example of stack and heap diagram which more clearly
shows the graph-based nature of the objects and their references. The diagram in Fig-
ure 8.5 represents a partial snapshot of stack and heap after executing the CustomerAppSimple
program shown in Listing 8.6. This code creates a Customer object, which takes a
String and an Date object as input.
To ease reading, variable cal is omitted from the figure. The first variable is the
input argument args, which contains a reference to an empty String[] object in the
heap. This object is created automatically by the run-time when the method main is
invoked. The second variable is is a reference to a Customer object. This object consists
in three values: id, name and dob. The value of id is 1, because this is the first customer
object that is created. The value of name is a reference to the String object ‘‘Duc Le”
in the heap, while the value of dob is a reference to the Date object 2/1/1970 in the
heap.
As far as coding is concerned, the program uses the built-in class Calendar in
231
8.3 Object Life Cycle
order to generate a desired Date1 object representing the date of birth ‘2/1/1970’ of
the customer. Line 2 is to obtain the system-specific object of the Calendar class and
to assign it to a variable cal. This object is created by the Calendar class itself, using
system’s specific calendar settings. The class procedure Calendar.getInstance is
used for this purpose. Line 3 then invokes the operation set on the object cal, passing in
three arguments: 1970, 0 and 2. The first argument is the value of the year, the second
is the month index (0 to 11) and the third is the value of the day. These have the effect
of pointing the current date of the calendar to 2/1/1970. When the customer object
is created at line 4, we invoke the getTime operation on the object cal to obtain the
desired Date object.
Listing 8.6: CustomerAppSimple
1 public static void main(String[] args) {
2 Calendar cal = Calendar.getInstance();
3 cal.set(1970,0,2);
4 Customer cust = new Customer("Duc Le", cal.getTime());
5 }
232
8.3 Object Life Cycle
access to the object and, thus, can manipulate the object by invoking its operations.
Any changes to the object state that are performed by the procedure also affect other
procedures that depend on that state. This is a key point to remember when working
with procedure invocations that involve objects!
Example 8.5 Procedural invocation involving objects.
Let us illustrate using a program, named CustomerApp, whose code is shown in
Listing 8.7. In addition to demonstrating procedure invocation with objects, this program
shows how to construct and display a formatted report from objects. Procedure main
basically contains the code explained earlier in Example 8.4 plus a call to a procedure
named report. This invocation passes a copy of the object reference of the variable
cust as argument. Procedure report then uses this reference to obtain information
about the Customer object and displays a formatted report on the standard output.
Lines 28-33, in particular, show how to use the procedure String.format to generate
formatted string fragments that are components of a larger String. The format pattern
is exactly the same as that used by System.out.printf. The only difference here is
that String.format produces a formatted string as output, without displaying it on the
standard output. The string fragments are combined with the help of a StringBuilder
object.
Listing 8.7: Program CustomerApp
1 import java.util.Calendar;
2 import java.util.Date;
3 /**
4 * @effects
5 * Represents a simple application that uses Customer.
6 * @author dmle
7 */
8 public class CustomerApp {
9 /**
10 * @requires c neq null
11 * @effects
12 * generate and display to the terminal console a formatted
report about c
13 */
14 private static void report(Customer c) {
15 StringBuilder rept = new StringBuilder();
16 Date d = c.getDob();
233
8.3 Object Life Cycle
37 /**
38 * @effects
39 * create a Customer object and display a formatted report.
40 */
41 public static void main(String[] args) {
42 Calendar cal = Calendar.getInstance();
43 cal.set(1970,0,2);
44 Date date = cal.getTime();
45 Customer cust = new Customer("Duc Le", date);
46 // report
47 report(cust);
48 }
49 }
Figure 8.6 shows a partial stack and heap diagram for the procedures main and
report. Similar to Figure 8.5 of Example 8.4, the argument args of procedure main
234
8.4 Private Constructor
points to an empty String[] object, while variable cust points to a Customer object. A
difference shown in Figure 8.6, however, is the stack variables concerning the invocation
of procedure report. These include the argument c, which contains a copy of the
object reference kept in cust, and variable rept. This second variable refers to a
StringBuilder object, whose content is the output of the report that is displayed to the
user.
Hidden Initialisation
A class should have a private constructor if this constructor is used only by code
within the class. Certain operations, e.g. object cloning (discussed later in Section 8.5),
require a behaviour that creates default objects. However, the abstract property speci-
235
8.5 Object Cloning
fication may prevent such a behaviour from being made public. In this case, the only
plausible solution for the behaviour is a private default constructor.
Example 8.6 Customer’s private default constructor
Listing 8.8 shows the definition of a private default constructor of class Customer.
It is basically a default constructor that is defined with the access modifier private.
Listing 8.8: Customer
1 /**
2 * An empty constructor used to clone (i.e. copy) objects
3 * @effects
4 * initialise this as Customer:<0,null,null>
5 */
6 private Customer() {
7 // do nothing
8 }
(1-different) o.clone() != o
(2-typing) o.clone().getClass() == o.getClass()
(3-equals) o.clone().equals(o) == true (equality)
2https://docs.oracle.com/javase/8/docs/api/java/lang/Object.html#clone--
236
8.6 Inner Class
Question Implement operation IntSet.clone that performs a deep clone of IntSet
objects.
237
8.6 Inner Class
238
8.6 Inner Class
239
8.7 Generic Class
240
8.7 Generic Class
6 /** (omitted) */
3https://docs.oracle.com/javase/8/docs/api/java/util/Set.html
241
8.7 Generic Class
7 @DOpt(type=OptType.MutatorAdd)
8 public void insert(T x) {
9 if (getIndex(x) < 0)
10 elements.add(x);
11 }
12
13 @DOpt(type=OptType.MutatorRemove)
14 public void remove(T x) {
15 int i = getIndex(x);
16 if (i < 0)
17 return;
18 elements.set(i, elements.lastElement());
19 elements.remove(elements.size() - 1);
20 }
21 // (omitted)
22 }
K Chapter 8 Exercise k
The exercises in this chapter help practise applying the solutions of the class design
issues to improve a class’s design.
242
8.7 Generic Class
7 * id Integer int
8 * name String
9 * students Student[] Vector<Student>
10 *
11 * @object
12 * A typical SClass is <i,n,s>, where id(i), name(n),
students(s). For example, <1,1c10,[]> is an SClass
representing the student class whose id is 1, whose name
is 1c10, and whose student list is empty.
13 *
14 * @abstract_properties
15 * mutable(id)=true /\ optional(id)=false /\ min(id)=1 /\
16 * mutable(name)=true /\ optional(name)=false /\
17 * length(name)=20 /\
18 * mutable(students)=true /\ optional(students)=false
19 */
20 public class SClass {
21 @DomainConstraint(type="Integer",mutable=true,optional=
false,min=1)
22 public int id;
23 @DomainConstraint(type="String",mutable=true,optional=
false,length=20)
24 public String name;
25 @DomainConstraint(type="Vector",mutable=true,optional=
false)
26 public Vector students;
27 /**
28 * @effects
29 * if name and students are valid
30 * initialise this as <0,name,students>
31 * else
32 * print error message "Invalid input"
33 */
34 public SClass(String name, Vector students) {
35 this.name = name;
36 this.students = students;
243
8.7 Generic Class
37 }
38
39 /**
40 * @effects
41 * return id
42 */
43 public int getId() {
44 return id;
45 }
46
47 /**
48 * @effects
49 * return name
50 */
51 public String getName() {
52 return name;
53 }
54
55 /**
56 * @effects
57 * return students
58 */
59 public Vector getStudents() {
60 return students;
61 }
62
63 @Override
64 public String toString() {
65 return "SClass:<"+id+","+name+","+students+">";
66 }
67 }
3. Below is the code of a program that performs some computation on integer arrays.
Answer the following questions about this program:
(a). What are the program states in the stack and heap memories when the code
is run?
244
8.7 Generic Class
6 int[] z = y;
7 int j;
8 for (int i = 0; i < x.length; i++) {
9 for (j = 1; j < z.length; j++) {
10 z[j] = z[j] + z[j - 1];
11 }
12 x[i] = x[i] * z[j-1];
13
14 System.out.println(x[i]);
15 }
16
4. Design and code at least one overloading constructor operation for class Person
of the GreetingConversation program of Exercise 6.1. Justify your design.
5. Design and code at least one overloading constructor operation for class MobilePhone
of the GreetingConversation program of Exercise 6.1. Justify your design.
6. Design and code at least one overloading constructor operation for class StringIntMap
of Exercise 6.6. Justify your design.
7. Design and code at least one overloading operation for the MutatorAdd and
MutatorRemove operations of the class IntSet of Chapter 6. Justify your design.
8. Change the design and code of the class StringIntMap of Exercise 6.6 to use an
inner class named Entry to represent an entry in the map.
245
Chapter 9
Introduction to Design Patterns
Objectives
" Understand design pattern and the pattern definition format.
" Apply a set of basic class design patterns.
" Derived attribute pattern: to construct a class with a derived attribute.
" Singleton pattern: to construct a singleton class.
" Factory pattern: to construct a factory class.
" Recursive class pattern: to construct a recursive class.
“each pattern describes a problem which occurs over and over again in our environment,
and then describes the core of the solution to that problem, in such a way that you can
use this solution a million times over, without ever doing it the same way twice”
Adapting this term to OOP design, Gamma et al. [10] characterises design pattern
as a construct that “. . . names, abstracts, and identifies the key aspects of a common
design structure that make it useful for creating a reusable object-oriented design.”
Gamma et al. also describe a pattern definition format and a presents a catalog of
generic design patterns. The definition format, in particular, provides a uniform and
structural means for documenting the patterns. This in turn makes it easy for designers
to study and evaluate the suitability of a pattern to a problem at hand. Gamma et al. uses
a pattern definition format as the documentation language for the patterns in the catalog.
Designers need to understand this language in order to read the catalog. The catalog
is organised along these three main class design dimensions: creational, structural and
behavioural.
Within the scope of this book, four design patterns are chosen for presentation in
this chapter. Two of these patterns are taken from the creational pattern type in [10].
The other two patterns are patterns that can be considered to be of the structural type.
They are useful enough to be included here for presentation. The first pattern concerns
derived attribute, while the second pattern concerns recursive class.
247
9.3 Class Design Patterns
of applying the pattern. This helps adopters evaluate the pattern against other
alternative design solutions.
9.4 Singleton
Singleton pattern concerns classes that have only one object. Explicitly designing
these classes to limit the number of valid objects helps improve performance and, in
some cases, protect the domain integrity.
9.4.1 Problem
Let’s discuss the intent and motivation for singleton.
Intent
To restrict the number of valid objects of a class to one and to provide a shared
reference to this object.
248
9.4 Singleton
Motivation
In practice, software requirements typically prescribe rules on the number of objects
of a class (called the subject) that can be associated to an object of another class. A
special case of these rules is when a subject class can have at most one and the same
object in any associations with other objects. In this case, the subject class has at most
one object created in the software. This type of class, called singleton, is often found
representing the key subsystems of a software system. For example, the accounting
subsystem [10] of a software system has one common object that serves accounting
requests from all other subsystems.
The key design questions facing singleton are:
1. How to design a singleton class such that at most one object can be created?
2. How to make this object easily accessible by other software components?
A simple design solution, which is often found in traditional non-object-oriented
software, is to use a global (public) variable for the object. This variable is initialised
once (possibly at loading time) and is then globally available for use by any components
that need it. However, this solution breaks the encapsulation principle by making
the variable vulnerable to modification by the using components. A better solution,
therefore, is needed that follows the standard object oriented design principles.
9.4.2 Solution
To answer design question 1 requires enforcing that the singleton class has complete
control over object creation. A simple solution for this is to hide the class constructor
(using the private constructor feature) behind a public operation. This operation is the
single service point for all object creation requests and that its behaviour must always
produce the same object of the class. Because this operation creates an object, it needs
to be defined as static. To keep the object created by this operation, the class needs to
have a static variable, which is assigned to the object the first time it is created.
To answer question 2 requires making the above operation the point of reference for
the object. This is achieved by simply returning the object reference when it is invoked.
249
9.4 Singleton
Figure 9.1 shows the design of the singleton class and how it is used by ClientProg.
The design elements of the class are summarised as follows:
a static variable (named instance) that points to the object.
a single private constructor that initialise the object.
a public static operation (named getInstance) that creates the object (when
invoked the first time) and returns the object.
9.4.3 Example
Listing 9.1 shows the design specification and code of a class named CustomerMan.
This class represents a customer management component of software. It references the
Customer class that was defined in a previous chapter. It makes sense to restrict the
number of CustomerMan objects to one, because only one such object is ever needed.
The UML design of CustomerMan is summarised in Figure 9.2.
Listing 9.1: Singleton class CustomerMan
1 import java.util.Calendar;
2 import java.util.Date;
3 /**
4 * @overview
5 * A simple class uses Customer and has only one instance.
6 * @author dmle
7 */
8 public class CustomerMan {
9 /** a single object of this class */
10 private static CustomerMan instance;
11 /**
12 * @effects
13 * initialise this to be an empty object
14 */
15 private CustomerMan() {
250
9.4 Singleton
16 //
17 }
18
19 /**
20 * @effects
21 * if instance = null
22 * initialise it
23 * return instance
24 */
25 public static CustomerMan getInstance() {
26 if (instance == null) {
27 instance = new CustomerMan();
28 }
29 return instance;
30 }
31
32 /**
33 * @effects
34 * create a Customer and display some info about it
35 */
36 public void run() {
37 Calendar cal = Calendar.getInstance();
38 cal.set(1970,0,2);
39 Date date = cal.getTime();
40 Customer cust = new Customer("Duc Le", date);
41 System.out.println(cust);
42 System.out.println(cust.toString(false));
43 System.out.println("age: " + cust.getAge());
44 }
45 }
251
9.5 Factory Method
state with them. The class operation getInstance initialises instance to an object
of CustomerMan, if this has not been created, and returns this object. This guarantees
at most one object of the class is created. The object operation run demonstrates the
execution of CustomerMan, which, for illustration purpose, simply creates a Customer
object and displays some information about it. The following code demonstrates a simple
client program that uses CustomerMan:
9.4.4 Consequences
The singleton pattern brings the following benefits to class design:
simple enforcement of a single object without the need to use a separate object
management class. This helps simplify the design and use.
conserves memory by preventing unnecessary objects from being created. Creat-
ing several identifical objects of the singleton class is not wrong but doing so is a
waste of run-time memory.
extensible to support a predetermined number of instances [10]. This can be
achieved by adding to the class a limit on the number of instances that can be
created and updating the getInstance operation to use this limit.
However, the pattern has the following disadvantage:
life cycle dependency: the object is recorded as part of the class and thus its life
cycle is attached to that of the class. The object is not garbage collected unless the
class is unloaded.
9.5.1 Problem
Let’s discuss the intent and motivation for factory method.
252
9.5 Factory Method
Intent
To define a method that is responsible for creating objects of a class, whose actual
type may not be known at compile time.
Motivation
When an instance variable is declared in a program its type, called the declared
type [20], may represent a group of compatible types. Objects of these types can all be
assigned to the variable, making them the actual types (of the variable). The declared
type is referred to as the abstract type. To illustrate let us consider the simple client
program example below. In this program, Object is the declared type of variable v,
while String and StringBuilder are the actual types of the v.
Now, consider a realistic situation where only one of the two objects (String or
StringBuilder) is needed by the program and that which object gets created depends
on a run-time condition that is not within the control of the program. Liskov and
Guttag [20] gives two examples of these conditions. The first example is to remove the
unnecessary dependency between the client program and the actual type. The client
program only knows the abstract type and so when the actual types are changed (or
by adding a new one), it is not affected. The second example is the platform type on
which the program is executed. This occurs when multiple versions of the program are
developed for different platforms.
The presence of a run-time condition means that the actual type is not known at
compile-time. This calls for a design solution that separates the object creation logic
from the client program that uses the objects. To this end, two basic design questions
can be raised:
1. What abstraction should we use to represent the object creation logic, such that it
hides knowledge about the actual object type from the client program?
2. How does this abstraction easily support multiple object types?
9.5.2 Solution
The answer to design question 1 is an operation, called factory method, that is
defined in a separate class and that its return type is the abstract type. Although it is
253
9.5 Factory Method
technically possible to define a factory method in each of the actual type class, doing so
will make the client program dependent on the actual types.
The factory method can be an object or class operation. Object operation is suitable
when the factory class needs to be instantiated for use in the client program. On the other
hand, class operation is used when the factory method can be invoked directly through
the factory class. If this is the case then it may also be useful to prevent factory class’s
objects from being created. This is achieved by making the factory class constructor
private.
Both Liskov and Guttag [20] and Gammar et al. [10] suggest several design alter-
natives to answer design question 2. A simple alternative, which is discussed in [20]
and is suitable for our study scope of this book, is to define several factory methods in a
factory class, one for each object type.
Figure 9.3 shows the abstract design of the factory class and how it references
some object types (SomeClass1 and SomeClass2) and how it is used by ClientProg
. FactoryClass has a private constructor and two class operations acting as factory
methods for objects of someClass1 and SomeClass2.
9.5.3 Example
Listing 9.2 is a factory class called CustomerFactory. The UML design of this
class is shown in Figure 9.4. The factory method, named createCustomer, creates
a Customer object from two input arguments and returns it. CustomerFactory’s
constructor is declared as private, because no objects of this class are needed.
Listing 9.2: Factory class CustomerFactory
1 /**
254
9.5 Factory Method
2 * @overview
3 * A factory class to create Customer objects
4 * @author dmle
5 */
6 public class CustomerFactory {
7 /**
8 * No objects are needed
9 */
10 private CustomerFactory() {
11 //
12 }
13
14 /**
15 * @effects
16 * create and return new Customer:<name,dob>
17 */
18 public static Customer createCustomer(String name, Date dob) {
19 Customer cust = new Customer(name, dob);
20 return cust;
21 }
22 }
The following code demonstrates a simple client program that uses CustomerFactory
:
9.5.4 Consequences
The factory method pattern brings the following benefits to class design:
separation of concerns, which leads to modular design and better code reuse.
Client program can use an extensible set of object types, without having any prior
knowledge about them.
255
9.6 Derived Attribute
9.6.1 Problem
Let’s discuss the intent and motivation for derived attribute.
Intent
To define an attribute whose value in each object state is automatically derived from
one or more attributes of the same class.
9.6.1.1 Motivation
In principle, derived attributes capture information about some parts of the object
state (called the observed parts). For example, two pieces of information about Customer
objects that are of frequent interest to the client program are surname and age. Surname
is derived from attribute Customer.name, while age is derived from attribute Customer
.dob. Surname would be used to perform sorting of the objects, while the age would
be used in different parts of the program to determine the suitability of a Customer to a
service.
To provide these information, a familiar solution is to define suitable observer
operations, whose behaviours compute and return the desired values. In the above
example, for instance, class Customer would be updated with two observers named
getSurame() and getAge(), whose behaviours extract the surname and compute the
age, respectively.
256
9.6 Derived Attribute
The issue here is that there are cases where the computation of the information
is nontrivial (and is thus time consuming) and/or the information is frequenly used in
the program and the observed parts rarely change. In these cases, it is beneficial to
design the observer operations in order to avoid computing the information every time
an operation is invoked. Ideally, the computation is only performed once in the first
invocation and is repeated when the observed parts have been updated. To this end, two
key design questions can be raised:
1. How to record the computed information and save it for subsequent use?
2. How to update the recorded information when the observed parts are changed?
9.6.2 Solution
The natural answer to design question 1 is to use an instance variable, whose value
is assigned to the computed information. This variable is called derived attribute. This
can not be a static variable, because the variable value is set differently for each object.
It can not be a local variable of the observer operation either, because this variable is
not retained between subsequent invocations of the operation. Note, in particular, that
the derived attribute must be immutable (i.e. property DomainConstraint.mutable=
false). This prevents the attribute from being set through a mutator operation.
The answer to design question 2 consists of two parts. First, because the update
would be invoked multiple times, it should be defined in a helper operation. Second, this
helper operation needs to be invoked at the points where the observed parts are changed.
These points include the constructor and mutator operations that update the observed
parts.
The solution is made clear in design diagram of Figure 9.5. Class SomeClass has
an attribute named part, which represents the observed part, and a derived attribute
named aDerived. This attribute is derived from part. Operationwise, SomeClass
consists of a constructor and a setter operation, both of which have a parameter named
part. These are the update points for the attribute part. The observer operation
getADerived is the getter for aDerived. It simply returns the value of this attribute.
257
9.6 Derived Attribute
9.6.3 Example
Figure 9.6 shows the UML design of the class Customer that has been updated
with the pattern solution for the derived attribute age. The solution for derived attribute
surname is defined in a similar manner. Listing 9.3 is a partial code of the class Customer
, which realises the design in Figure 9.6. The listing includes the declaration of the
attribute age and how it is computed by the helper operation updateAge. This operation
is invoked by the constructor and setDob, after the value of attribute dob has been set.
Note, in particular, that attribute age is defined with property DomainConstraint.
mutable=false.
Listing 9.3: Derived attribute Customer.age
1 public class Customer {
2 // code omitted
3 /** a derived attribute */
4 @DomainConstraint(mutable=false)
5 private int age;
6 /**
7 * @effects
8 * initialise this as Customer:<id,name,dob>
9 * update age
10 */
11 public Customer(int id, String name, Date dob) {
258
9.6 Derived Attribute
12 // code omitted
13 this.dob=dob;
14 updateAge();
15 }
16
17 /**
18 * @effects
19 * (omitted)
20 * update age
21 */
22 public boolean setDob(Date dob) {
23 // code omitted
24 this.dob = dob;
25 updateAge();
26 }
27
28 /**
29 * @requires dob != null
30 * @effects
31 * set age = currentYear - year(dob)
32 */
33 private void updateAge() {
34 Calendar cal = Calendar.getInstance();
35 int currYear = cal.get(Calendar.YEAR);
36 cal.setTime(dob);
37 int yob = cal.get(Calendar.YEAR);
38 age = currYear - yob;
39 }
40 }
Question Apply the derived attribute pattern to class IntSet.
The following code demonstrates a simple client program that uses Customer and
its derived attribute age:
259
9.7 Recursive Class
9.6.4 Consequences
The derived attribute pattern has the following benefits:
enhanced encapsulation through making the derived attribute a part of the object
state.
increased efficiency through minimising the computation time of the derived
attribute value.
However, the pattern has the following disadvantage(s):
increased object state complexity by the introduction of the derived attributes. If
not managed well, these attributes would overwhelm the observed parts.
260
9.7 Recursive Class
BASIS.
1! = 1.
INDUCTION.
n! = n × (n - 1)!.
9.7.2 Problem
Let’s discuss the intent and motivation for recursive class pattern.
Intent
To design a class whose objects that are constructed through a recursive definition.
This class, called recursive class, realises the recursive definition such that it becomes
the template for creating the objects.
Motivation
Recursive definition is one of the key constructs used in computer science and
software engineering. It is used to define sets, whose elements have some structural
relationship. Well-known examples of these sets include data types, strings and grammar
rules. For instance, all the strings that are defined based on a given alphabet can
recursively be constructed. Many commonly-used natural number subsets are recursive;
e.g. even numbers, factorial numbers, fibonacci numbers, prime numbers, and so on.
Some important data types that are used in most software, such as list and tree, are
recursive in nature. The context-free grammar [28] that is commonly used to define
programming language syntax consists of a set of recursively-defined rules.
There are different techniques used to design a recursive definition in a program. A
common technique is to use recursive function, which is a function that invokes itself on
261
9.7 Recursive Class
some pre-defined parameter values. While this design is generally efficient, it arguably
does not fully capture the nature of recursive definition. Recursive function merely
focuses on computing the final result; it forgets the state structure consisting of all the
smaller (intermediate) elements that take part in that computation. This state structure
is inherent in the recursive definition, due to the repeated application of the inductive
clauses. For example, to compute the factorial number 5!, a recursive function would
return the computed result of 120, without recording all the smaller factorials (1!, 2!, 3!
and 4!) that take part in the computation.
To fully capture the recursive definition requires a design that takes into account
not only the objects but the state structure that defines them.
9.7.3 Solution
Three features of recursive definition that make it suitable for class design. First,
the definition concerns a set of objects of a given type. This description fits that of a
class. Second, the state structure that needs to be captured is a natural fit for object state.
Third, the definition involves constructing objects according to some pre-defined rules.
This fits the behaviour of the constructor operation.
The class that realises a recursive definition is called recursive class. This class
implements the aforementioned features as follows:
@object section of header specification: presents the recursive definition. This
definition is what defines the objects.
object representation: includes attributes that capture not only the current object
value but also the state structure.
private constructor operation(s) that implement the basis and induction clauses
of the recursive definition.
static getter operation that computes and returns an object. This operation looks
up in state structure for pre-computed objects and only invokes the constructor if
the object is not there.
private look-up operation, which is a helper operation that looks up in the state
structure for an object given its index.
An important observation is that since the state structure records all the intermediate
objects, it can be used to provide the objects that the client program needs, without cre-
ating new ones. This observation is implemented in the design by hiding the constructor
operation (making it private) and introducing a static getter operation. This operation
invokes the helper look-up operation to determine whether or not the desired object has
262
9.7 Recursive Class
already been created. If so, it immediately returns the object reference; otherwise, it
invokes the constructor to create the object before returning it. The constructor realises
the recursive definition by creating the current object and recording it into the state
structure. It uses the helper look-up operation to determine if smaller objects have been
created. If not, it recursively invokes the constructor(s) to create those objects. These in
turn place these smaller objects into the state structure.
Figure 9.7 shows the design diagram of recursive class. To enhance reuse, the class
is designed as a generic class, whose type parameter is the data type of object value. The
object representation consists of the attribute value which records value of the current
object. The state structure is represented by a static variable stateStruc and is used
as a shared buffer for all objects. The data type of this variable is the parameterised
Vector<RecursiveClass>. Note that both attributes are immutable (i.e. has property
DomainConstraint.mutable = false), because they cannot be changed directly by
the client program. The private constructor operation RecursiveClass takes a param-
eter named index. This parameter specifies the index of the object to be constructed.
In practice, other constructors may be added to suit the recursive definition, if needed.
Last but not least, the observer operation getValue is a minimum that this class needs
which provides the object value.
Design alternatives
The inclusion of the state structure in the recursive class is based on an assumption
that a single instance of the basis and inductive clauses is shared among all the objects.
In practice, however, multiple instances of a clause may exist, which lead to different
alternative objects for the same application of this clause. For example, the inductive
clause of the recursive definition of string may be applied to any character of the base
alphabet and to any of the existing intermediate objects that have been created. Each
application thus requires an input character and an intermediate object. This is different
263
9.7 Recursive Class
from the behaviour of the solution above, where the intermediate objects are created
automatically from the same application of the inductive clause and are thus not required
as input.
In these cases, the solution should be changed as follows:
update the constructor operation to take the smaller objects as input
update the static getter operation to match the constructor parameters
9.7.4 Example
Figure 9.8 shows the design of the recursive class named Fact. This class realises
the recursive definition of factorial numbers presented in Example 9.1. The Fact object
value is captured by the attribute value: Integer. The state structure is captured by
the static attribute stateStruc: Vector<Fact>. To increase utility, class Fact also
records the factorial number index in the attribute index. This is useful if the client
program needs to ascertain the position of a Fact object in the sequence. The constructor
operation realises both clauses of the recursive definition. It is a recursive function that
computes the factorial number specified by index.
Listing 9.5 shows the Java code of the class Fact. Note how the constructor records
all the smaller Facts in stateStruc. For testing purposes, the look-up operation
includes an if statement that prints to the standard output the Fact object if it is found
in stateStruc. This is used to test that stateStruc actually works by returning a
precomputed object. In production, this debug statement should be commented out.
Listing 9.5: Recursive class Fact
1 import java.util.Vector;
2 import utils.DomainConstraint;
3 /**
4 * @overview
5 * Represents a factorial number.
264
9.7 Recursive Class
6 * @attributes
7 * val Integer
8 * stateStruc Vector<Fact>
9 * @object
10 * A typical factorial is n!, which is defined as follows:
11 * BASIS.
12 * 1! = 1.
13 * INDUCTION.
14 * n! = n x (n - 1)!
15 * @abstract_properties
16 * mutable(val)=false /\ optional(val)=false /\ min(val) = 1 /\
17 * mutable(stateStruc)=false /\
18 * stateStruc.size() > 0
19 * -> for all e1, e2 in stateStruc. e1 neq e2
20 * @author dmle
21 */
22 public class Fact {
23 private static final int MIN_INDEX = 1;
24 @DomainConstraint(mutable=false, optional=false, min=MIN_INDEX)
25 private Integer index;
26 @DomainConstraint(mutable=false, optional=false, min=1)
27 private Integer val;
28 @DomainConstraint(mutable=false, min=1)
29 private static Vector<Fact> stateStruc;
30
31 /**
32 * @requires n >= 1 /\ stateStruc != null
33 * @effects constructs this to be the nth factorial number
34 */
35 private Fact(int n) {
36 this.index = n;
37 if (n == 1) {
38 val = 1;
39 } else {
40 // get/compute previous objects
41 Fact prev = lookUp(n-1);
265
9.7 Recursive Class
50 /**
51 * @effects
52 * if index is valid
53 * create (if not already) and return the factorial number at
that index
54 * else
55 * return null
56 */
57 public static Fact get(int index) {
58 if (index < MIN_INDEX) return null;
59 // get/compute the nth object
60 if (stateStruc == null) stateStruc = new Vector<>();
61 // determine if this number been computed
62 Fact me = lookUp(index);
63 if (me == null) // not yet computed...
64 me = new Fact(index);
65 return me;
66 }
67
68 /**
69 * @effects
70 * if the nth Fact is found in stateStruc
71 * return it
72 * else
73 * return null
74 */
75 private static Fact lookUp(int n) {
76 Fact f = null;
266
9.7 Recursive Class
77 if (n <= stateStruc.size()) {
78 f = stateStruc.get(n-1);
79 }
80 // debug
81 if (f != null) System.out.printf("--> Found: %s%n",f);
82 return f;
83 }
84
85 /**
86 * @effects
87 * return val
88 */
89 public int getValue() {
90 return val;
91 }
92
93 @Override
94 public String toString() {
95 return String.format("Fact(%d!,%d)", index, val);
96 }
97 }
Question Design and code recursive classes for the recursive definition examples dis-
cussed at the beginning of Section 9.7.1.
The following code demonstrates a simple client program that uses the Fact class
to compute some factorial numbers. To test the use of state structure, the numbers are
computed in reverse order. The smaller numbers should have already been computed
and provided immediately from the state structure.
267
9.7 Recursive Class
9.7.5 Consequences
Recursive class pattern has the following benefits:
captures the state structure of recursive definition. This state structure holds the
components that make up each object state and thus needs to be made explicit in
the design.
improved performance in computing the objects, thanks to the shared state struc-
ture. Every object is computed only once, either when it is first created or when it
is computed as part of a larger object.
However, the pattern has the following disadvantage(s):
requires more memory space to hold the state structure. The memory usage is also
higher than that of recursive function, because every data element is represented
as object.
K Chapter 9 Exercise k
The exercises in this chapter help practise applying the solutions of the class design
patterns to improve a class’s design.
268
Chapter 10
Abstract Data Type:
Object Oriented Design and Implementation
Objectives
" Understand abstract data type (ADT) and two common ADTs (list and tree).
" Explain the recursive nature of list and tree and how this helps inform their
design.
" Apply the recursive class design technique to design tree and list.
" Implement the tree and list designs in Java.
document, which helps illustrate list, tree and the relationship between them. One
or the other abstraction applies depending on how one views a document. Skimming
through the document, it appears as a list of section headers, one after another in
sequence. However, when looking at the document more thoroughly, it appears as a
hierarchical structure of headers: the level-1 section headers, the level-2 sub-section
headers appearing underneath each level-1 header, the level-3 sub-sub-section headers
appearing underneath each level-2 header, and so on. This hierarchical structure is called
a tree. At the top level (called level 0) of the document tree in the figure is a node which
10.1 Overview
represents the document. This is the root node of the tree and is also the only node at
this level. This node is linked to four level-1 nodes that are labelled 1, 2, 3, and 4. These
represent the four level-1 section headers of the document. Each level-1 node is in turn
linked to one or more level-2 nodes and so on.
This chapter first gives an overview of list and tree, emphasising the recursive nature
of both abstractions. After that, it applies the recursive class design pattern to define the
design of each data type.
10.1 Overview
This section gives an overview of abstract data type and discusses list and tree from
the perspective of recursion. It also briefly discusses Java’s support for list and tree and
the design approach of this book.
270
10.1 Overview
As shown earlier in the document structure example of Figure 10.1, a list represent a
sequence of items, while a tree represents a hierarchical structure of items. Further, there
is a relationship between list and tree. Each level of the tree consists of lists of nodes.
Conceptually, therefore, a tree can be viewed as a ‘recursive’ list, elements of which are
themselves lists. A list can be represented as a binary tree as shown in Figure 10.2. The
2 C
3 C
5 C
7 C
figure demonstrates with a sample list (2,3,5,7). The filled circles labelled ‘C’ represent
constructor nodes, which are artificial nodes added to construct the overall tree structure.
The effect of this structure is that the list elements are arranged in the same sequential
order of the list. Each constructor nodes has two branches: the left branch contains
just an element, the right branch is another constructor node. The last constructor node
terminates the tree with no further elements to have.
1https://docs.oracle.com/javase/8/docs/api/java/util/package-summary.html
271
10.2 Overall Design Approach
272
10.3 Tree
10.3 Tree
We focus on a common type of tree called rooted tree [1].
Figure 10.3 shows an example of a rooted tree with seven nodes. For the sake of
the example, each node is labelled with a node id. In practice, each node can represent
an object of any type; the node id becomes the object id. As shown in the figure, node 1
is the root node. The tree has 6 edges. For instance, (2,5) is a binary edge that connects
node 2 to node 5. Node 2 is the parent node and node 5 is its child. Besides node 5,
node 2 also has node 6 as its child.
273
10.3 Tree
Tree-Related Terms
Among the common tree-related terms [1] are sibling, path, ancestor, descendant,
subtree, leaf and interior nodes, height and depth.
Definition 10.2. Sibling
Nodes that have the same parent are called siblings. ♣
For example, in Figure 10.3, nodes 1, 3, and 4 are siblings; so are nodes 5 and 6.
Definition 10.3. Path
A sequence of nodes of a tree is a path if every node in the sequence, except the
last node, is the parent of the subsequent node.
A path’s length is the number of edges in the path. ♣
For example, In Figure 10.3, node sequence (1, 2, 6) form a path of length 2 from
the root 1 to node 6. Node sequence (1) is a path of length 0 from 1 to itself.
The parent-child relationship can be extended naturally to ancestors and descen-
dants.
Definition 10.4. Ancestor and descendant
The ancestors of a node are found by following the unique path from the
node to its parent, to its parent’s parent, and so on.
The descendant relationship is the inverse of the ancestor relationship. That
is, a node is a descendant of another node if and only if this node is an
ancestor the node. ♣
It easily follows from Definition 10.4 that a node is also its own ancestor. Further,
the root is an ancestor of every node in a tree and every node is a descendant of the root.
Definition 10.5. Subtree
In a tree T , a node n, together with all of its proper descendants (if any) is called
a subtree of T . Node n is the root of this subtree. ♣
For example, in Figure 10.3, node 3 is a single-node subtree, because this node has
itself as a decendant. Nodes 2, 5, and 6 together with the edges connecting them form
a subtree. Node 2 is the root of this subtree; nodes 5, 6 are all the descendants of 2.
The entire tree of Figure 10.3 is a subtree of itself. Note, however, that nodes 2 and 6
and the binary edge (2,6) cannot form a subtree, because this does not include another
descendant of node 2 (node 5).
274
10.3 Tree
Thus, the root of a tree that has more than two nodes is an interior node. The root
of a single-node tree is both the root and a leaf, but not an interior node. Generally,
every node of a tree is either a leaf or an interior node, but not both.
For example, in Figure 10.3, leave nodes are 5, 6, 3, and 7. Interior nodes are 1, 2,
and 4.
Definition 10.7. Height and Depth
The height of a node is the length of a longest path from it to a leaf. The
height of the tree is the height of the root.
The depth, or level, of a node is the length of the path from the root to it. ♣
For example, in Figure 10.3, node 1 has height 2, node 2 has height 1, and the leaf
node 3 has height 0. The tree’s height is 2. The depth of node 1 is 0, the depth of node
2 is 1, and the depth of node 5 is 2.
Recursive Definition
There are two recursive definitions for rooted tree. Each definition gives rise to a
different tree design:
bottom-up: tree is formed from the sub-trees
top-down: tree is formed by extending out from the root
In the bottom-up view, a new (larger) tree is constructed from two more more
smaller ones by adding suitable edges that connect them. In the top-down view, a new
tree is constructed from an existing tree by adding new edges that connect a node of
this tree to some other new nodes. Let us attempt to formalise the two definitions. The
definitions use the tree notation introduced in Definition 10.8.
Definition 10.8. Tree
A tree, denoted by T, is a triple hr, nodes, edgesi, where:
nodes is the set of nodes
edges is the set of edges
r is the root (r ∈ nodes)
To ease notation, we denote:
T.root = r, T.nodes = nodes, T.edges = edges.
edge(p, n) is an edge that connects the parent node p to the child node n.
♣
275
10.3 Tree
Bottom-Up Definition
Figure 10.4: Constructing the tree in Figure 10.3 from the bottom up.
Figure 10.4 demonstrates how to construct the tree in Figure 10.3 by applying the
bottom-up recursive definition. First the basis clause is applied to create the four single-
node trees T3 = h3, {3} , ∅i, T5 = h5, {5} , ∅i, T6 = h6, {6} , ∅i and T7 = h7, {7} , ∅i. Then
the induction clause is applied three times to result in the final tree. First, is applied to
node 2 and trees T5 , T6 to create a new tree T2 . Second, it is applied to node 4 and tree
T7 to create another new tree T4 . Third, it is applied to node 1 and the three trees T2 , T3
and T4 to produce the target tree.
276
10.3 Tree
Top-Down Definition
Figure 10.5: Constructing the tree in Figure 10.3 from the top down.
Figure 10.5 demonstrates how to construct the tree in Figure 10.3 by applying the
top-down recursive definition. The application consists in following sequence of steps:
1. basis clause on node 1 creates tree T1 = h1, {1} , ∅i
2. induction clause on T 0 = T1 , n = 2, p = 1
3. induction clause on T 0 , n = 3, p = 1
4. induction clause on T 0 , n = 4, p = 1
5. induction clause on T 0 , n = 5, p = 2
6. induction clause on T 0 , n = 6, p = 2
7. induction clause on T 0 , n = 7, p = 4
277
10.3 Tree
Abstract Properties
First, a rooted tree must have exactly one node that serves as the root. Secondly,
a rooted tree shares a general property of a tree, which is an acyclic, connected graph.
This means that there exists exactly one path that connects any two nodes of the tree.
Putting these together give us three rooted tree properties [1]. These properties form the
abstract properties of the tree design.
Definition 10.11. Tree properties
Rooted tree has the following properties:
1. root node must be specified.
2. (connectedness) there exists a path from root to every non-root node.
3. (acyclicity) every non-root node has exactly one parent. ♣
10.3.2 Operations
Since tree is recursive, the operations performed on tree are inherently recursive. In
general, the behaviour of an operation consists of two parts. The first part is a recursion
and the second part is the actual computation that is performed against the recursion.
The recursion part helps traverses the tree in a top-down manner, one node at a
time, until it reaches the leafs. The basis case is applied at the leaf nodes while the
induction is applied at the non-leaf ones.
The computation part defines what to do at each node. The logic the this computa-
tion depends on the application. Below is a list of the computations, adapted from [1],
that are believed to be common to all trees:
height: returns the height of the tree or a subtree
countif: counts the number of nodes of the tree or a subtree that satisfy a
condition
count: (a special form of countif) counts the number of nodes of the tree or a
subtree
eval: evaluates the expression that is represented by the tree
toString: turns a tree or a subtree into a structured string
This section will focus on two operations count and toString. Details of the
other operations are given in [1].
278
10.3 Tree
Operation count
Example 10.4
Let us consider a bigger tree in Figure 10.6 which has 12 nodes and 11 edges. In
this tree, it is clear that count(7) = 3, which covers node 7 itself and its two children.
As another example, count(2) = 8, which covers all the nodes of the subtree rooted at
node 2.
Operation toString
A structured string representation of a tree involves using a number of separator
symbols and some utility oprerations on these symbols. These are described as follows:
NIL is the empty string (‘’)
NL is the next line character
VER is the vertical bar character
(‘|’)
if l = 0
NIL
operation spaceMarkers(l) =
if l > 0
“-
. . . -”
279
10.3 Tree
if l = 0
NIL
operation bol(l) =
NL + VER
if l > 0
operation nodeLine(n) = bol(n.level) + spaceMarkers(n.level) + n.toString
Definition 10.13. Operation toString
Operation toString, invoked on some node n at some level l (0 ≤ l ∈ N) that
, . . . ck (k ≥ 0), is defined as follows:
has k children c1
nodeLine(n) if n is leaf
toString(n) = nodeLine(n) + if n is not leaf
toString(c1 ) + · · · + toString(ck )
♣
Example 10.5
1
|-2
|--3
|---4
|---5
|--6
|---7
|----8
|----9
|-10
|--11
|--12
Listing 10.5 shows the result of performing toString(1) on the tree in Figure 10.6.
It displays the structured string representation of the entire tree.
280
10.3 Tree
Nodes are objects of a generic class named Node<T>. The type parameter T
represents the data type of the node label. Figure 10.7 shows the design of this class. It
is the most basic form, which contains one attribute called label. Other attributes can
easily be added to capture more complex node data if needed. Appendix 10.A presents
the design specification and Java code of class Node.
Edges are objects of a general class named Edge. Figure 10.8 shows the design of
this class. It is in its most basic form, which has two attributes: src and tgt. The former
more represents the source node (which is a parent) and the latter represents the target
node (which is a child). Similar to Node, class Edge can easily be extended with other
281
10.3 Tree
attributes to capture more complex edge data (e.g. label, weight, etc.). Appendix 10.B
presents the design specification and Java code of class Node.
Constructors
Class Tree in Figure 10.9 has two constructors which realise the two clauses of the
recursive definition (Definition 10.9). The one-argument constructor realises the basis
clause, while the other constructor realises the inductive one.
Operation count
This operation realises the recursive Definition 10.12 by traversing the subtree
rooted at the input node and counting the number of visited nodes.
Operation toString
This operation realises the recursive Definition 10.13 by recursively traversing the
tree starting at the input node and constructs a string consisting of all the nodes that are
282
10.3 Tree
visited.
Design Specification
Listing 10.2 shows the design specification of the bottom-up class Tree.
Listing 10.2: Design specification of bottom-up Tree
1 import java.util.Vector;
2 import chap10.tree.Edge;
3 import chap10.tree.Node;
4 import utils.DomainConstraint;
5
6 /**
7 * @overview A tree is a set of nodes that are connected to to
each other by
8 * edges such that one node, called the root, is connected to
some nodes,
9 * each of these nodes is connected to some other nodes that
have not been
10 * connected, and so on.
11 *
12 * <p>The following is a <b>bottom-up</b> recursive tree design
that incrementally
13 * builds a new tree by adding roots.
14 *
15 * @attributes
16 * root Node
17 * nodes Set<Node> Vector<Node>
18 * edges Set<Edge> Vector<Edge>
19 *
20 * @object A typical tree T is the tuple <r,N,E>, where
21 * root(r), nodes(N), and edges(E).
22 *
23 * <p>Trees are defined recursively as follows:
24 * Basis
25 * For any node r, T = <r,{r},{}> is a tree.
26 * Induction
283
10.3 Tree
58 // constructors
59 /**
60 * @requires r != null
284
10.3 Tree
65 /**
66 * @requires r != null /\ trees.length >= 1 /\
67 * for all t in trees. r not in t.nodes
68 *
69 * @effects initialise this as a tree T =
70 * <r,
71 * T1.nodes+...+Tk.nodes+{r},
72 * {edge(r,T1.root),...,edge(r,Tk.root)} +T1.edges+...+Tk.
edges>,
73 * where Tis are in <tt>trees</tt>
74 */
75 public Tree(Node r, Tree...trees)
76
77 /**
78 * A recursive procedure to count the number of nodes in a
subtree
79 * rooted at n.
80 *
81 * @effects
82 * if n is a leaf
83 * return 1
84 * else
85 * return the number of nodes in the sub-tree rooted at n
86 */
87 public int count(Node n)
88
89 /**
90 * @effects
91 * return a structured textual representation of this
92 */
93 @Override
94 public String toString()
285
10.3 Tree
95
96 /**
97 * @effects
98 * if this satisfies abstract properties
99 * return true
100 * else
101 * return false
102 */
103 public boolean repOK()
104 } // end Tree
As shown in Defintion 10.10, the general form of the inductive rule of the top-down
definition appends one or more trees to an existing node of an existing tree. This could
be translated directly into the design, resulting in a constructor shown in Listing 10.3.
This constructor is similar to the second constructor of the bottom-up design shown in
Listing 10.2.
286
10.3 Tree
However, a draw-back of the above design is that tree objects need to be created
before hand and passed in as argument. This is rather cumbersome and not efficient. We
thus propose an alternative design that overcomes this draw-back.
Figure 10.10 shows the recursive, top-down design of class Tree. In this design, the
second constructor is replaced by an operation named addNode. This operation adds a
new node n as a child of an existing node parent in a tree. Listing 10.4 shows the partial
design specification of class Tree that contains the operation addNode. Compared to
the pure design in Listing 10.3, this design basically treats the current tree object as
the first parameter and the parameter parent as the second parameter. As for the third
parameter, which is a Tree array, it is replaced by a single node, n, which serves as the
root node of each of the Tree objects in the array. This is because one tree can be added
at a time to the existing tree by creating an edge to its root node.
Listing 10.4: Partial specification of the recursive, top-down Tree with operation addNode
1 import java.util.Vector;
2 import chap10.tree.Edge;
3 import chap10.tree.Node;
4 import utils.DomainConstraint;
5
6 /**
7 * @overview A tree is a set of nodes that are connected to to
each other by
8 * edges such that one node, called the root, is connected to
some nodes,
9 * each of these nodes is connected to some other nodes that
have not been
287
10.3 Tree
288
10.3 Tree
43 @DomainConstraint(type="Node",mutable=false,optional=false)
44 private Node root;
45 @DomainConstraint(type="Vector",mutable=true,optional=false)
46 private Vector<Node> nodes;
47 @DomainConstraint(type="Vector",mutable=true,optional=true)
48 private Vector<Edge> edges;
49
50 // constructors
51 /**
52 * @requires r != null
53 * @effects initialise this as <r,{r},{}>
54 */
55 public Tree(Node r)
56
57 /**
58 * @requires <tt>n != null /\ parent != null</tt>
59 * @effects
60 * if <tt>parent</tt> is in <tt>nodes</tt>
61 * add <tt>n</tt> as a child of <tt>parent</tt>, i.e. <tt>
edge(parent,n)</tt>
62 * return true
63 * else
64 * return false
65 */
66 public boolean addNode(Node parent, Node n)
67
10.3.6 Implementation
Bottom-up Design
Listing 10.5 shows the Java implementation of the bottom-up class Tree.
Listing 10.5: Java implementation of bottom-up Tree
1 import java.util.Vector;
289
10.3 Tree
2 import chap10.tree.Edge;
3 import chap10.tree.Node;
4 import utils.DomainConstraint;
5 /**
6 * @overview ...
7 *
8 * @attributes
9 * root Node
10 * nodes Set<Node> Vector<Node>
11 * edges Set<Edge> Vector<Edge>
12 *
13 * @object ...
14 *
15 * @abstract_properties ...
16 *
17 * @author dmle
18 */
19 public class Tree {
20 @DomainConstraint(type="Node",mutable=false,optional=false)
21 private Node root;
22 @DomainConstraint(type="Vector",mutable=true,optional=false)
23 private Vector<Node> nodes;
24 @DomainConstraint(type="Vector",mutable=true,optional=true)
25 private Vector<Edge> edges;
26
27 // constructors
28 /**
29 * @requires r != null
30 * @effects initialise this as <r,{r},{}>
31 */
32 public Tree(Node r) {
33 // single-node tree
34 this.root = r;
35 nodes = new Vector<>();
36 nodes.add(r);
37 }
290
10.3 Tree
38
39 /**
40 * @requires r != null /\ trees.length >= 1 /\
41 * for all t in trees. r not in t.nodes
42 *
43 * @effects initialise this as a tree T =
44 * <r,
45 * T1.nodes+...+Tk.nodes+{r},
46 * {edge(r,T1.root),...,edge(r,Tk.root)} +T1.edges+...+Tk.
edges>,
47 * where Tis are in <tt>trees</tt>
48 */
49 public Tree(Node r, Tree...trees) {
50 this(r);
51 edges = new Vector<>();
52 // this.r = r /\ this.nodes = {r} /\ this.edges = {}
53 Edge e;
54 for (Tree t: trees) {
55 nodes.addAll(t.nodes);
56 // this.nodes = this.nodes + t.nodes
57 e = new Edge(r,t.root);
58 edges.add(e);
59 // this.edges = this.edges + {edge(r,t.root)}
60 if (t.edges != null)
61 edges.addAll(t.edges);
62 }
63 }
64
65 /**
66 * A recursive procedure to count the number of nodes in a
subtree
67 * rooted at n.
68 *
69 * @effects
70 * if n is a leaf
71 * return 1
291
10.3 Tree
72 * else
73 * return the number of nodes in the sub-tree rooted at n
74 */
75 public int count(Node n) {
76 int count = 1; // includes n
77 if (edges != null) {
78 for (Edge e : edges) {
79 if (e.hasSrc(n)) { // e[0] is parent
80 count += count(e.getTgt()); // e[1]: child of n (
recursive call)
81 }
82 }
83 }
84 return count;
85 }
86
87 /**
88 * @effects
89 * return a structured textual representation of this
90 */
91 @Override
92 public String toString() {
93 StringBuffer sb = new StringBuffer();
94 toString(sb, 0, root);
95 return sb.toString();
96 }
97
98 /**
99 * This is a recursive operation that incrementally constructs
the string representation of the
100 * tree/subtree rooted at n.
101 *
102 * @modifies sb
103 *
104 * @effects
105 * update <tt>sb</tt> with the string representation of the sub
292
10.3 Tree
-tree
106 * rooted at <tt>n</tt>.
107 */
108 private void toString(StringBuffer sb, int level, Node n) {
109 // append next line
110 if (level > 0) {
111 sb.append("\n");
112 sb.append("|");
113 }
114 for (int i = 0; i < level; i++) {
115 sb.append("-");
116 }
117 sb.append(n);
118 if (edges != null) {
119 int thisLevel = level;
120 for (Edge e : edges) {
121 if (e.hasSrc(n)) { // append this child of n
122 if (thisLevel == level)
123 level++;
124 toString(sb, level, e.getTgt()); // recursive call to
next level
125 }
126 }
127 }
128 }
129
130 /**
131 * @effects
132 * if this satisfies abstract properties
133 * return true
134 * else
135 * return false
136 */
137 public boolean repOK() {
138 // root != null
139 if (root == null) {
293
10.3 Tree
294
10.3 Tree
295
10.3 Tree
208 }
209
The program class that uses the bottom-up Tree class is chap10.test.tree.
BottomUpTreeTest in the attached source code. Listing 10.6 shows the code of this
class.
Listing 10.6: An example program class for the bottom-up Tree
1 import chap10.tree.Node;
2 import chap10.tree.bottomup.Tree;
3 public class BottomUpTreeTest {
4 public static void main(String[] args) {
5 Tree t4 = new Tree(new Node(4)), t5 = new Tree(new Node(5));
6 Tree t8 = new Tree(new Node(8)), t9 = new Tree(new Node(9)),
7 t7 = new Tree(new Node(7),t8,t9);
8 Tree t11 = new Tree(new Node(11)),
9 t12 = new Tree(new Node(12)),
10 t10 = new Tree(new Node(10),t11,t12);
11 Tree t3 = new Tree(new Node(3),t4,t5),
12 t6 = new Tree(new Node(6),t7),
13 t2 = new Tree(new Node(2), t3, t6),
14 t1 = new Tree(new Node(1), t2,t10);
15 boolean repOk = t1.repOK();
16 if (repOk)
17 System.out.println(t1);
296
10.3 Tree
Top-Down Design
Listing 10.7 shows the Java implementation of the top-down class Tree. To con-
serve space, we only show the attributes, the constructor and the operation addNode.
The code of other operations is the same as in the bottom-up Tree class (shown in
Listing 10.5).
Listing 10.7: Java implementation of top-down Tree
1 import java.util.Vector;
2 import chap10.tree.Edge;
3 import chap10.tree.Node;
4 import utils.DomainConstraint;
5 /**
6 * @overview ...
7 *
8 * @attributes
9 * root Node
10 * nodes Set<Node> Vector<Node>
11 * edges Set<Edge> Vector<Edge>
12 *
13 * @object ...
14 *
15 * @abstract_properties ...
16 *
17 * @author dmle
18 */
19 public class Tree {
20 @DomainConstraint(type="Node",mutable=false,optional=false)
21 private Node root;
297
10.3 Tree
22 @DomainConstraint(type="Vector",mutable=true,optional=false)
23 private Vector<Node> nodes;
24 @DomainConstraint(type="Vector",mutable=true,optional=true)
25 private Vector<Edge> edges;
26
27 // constructors
28 /**
29 * @requires r != null
30 * @effects initialise this as <r,{r},{}>
31 */
32 public Tree(Node r) {
33 // single-node tree
34 this.root = r;
35 nodes = new Vector<>();
36 nodes.add(r);
37 }
38
39 /**
40 * @requires <tt>n != null /\ parent != null</tt>
41 * @effects
42 * if <tt>parent</tt> is in <tt>nodes</tt>
43 * add <tt>n</tt> as a child of <tt>parent</tt>, i.e. <tt>
edge(parent,n)</tt>
44 * return true
45 * else
46 * return false
47 */
48 public boolean addNode(Node parent, Node n) {
49 // check that parent is in nodes
50 boolean found = false;
51 for (Node node : nodes) {
52 if (node.equals(parent)) {
53 found = true;
54 break;
55 }
56 }
298
10.3 Tree
57 if (!found) {
58 return false;
59 }
60 // add node
61 nodes.add(n);
62
The program class that uses the top-down Tree class is chap10.test.tree.
TopDownTreeTest in the attached source code. Listing 10.8 shows the code of this
class.
Listing 10.8: An example program class for the top-down Tree
1 import chap10.tree.Node;
2 import chap10.tree.topdown.Tree;
3 public class TopDownTreeTest {
4 public static void main(String[] args) {
5 Node n1 = new Node(1), n2 = new Node(2),
6 n3 = new Node(3), n4 = new Node(4),
7 n5 = new Node(5), n6 = new Node(6),
8 n7 = new Node(7), n8 = new Node(8),
9 n9 = new Node(9), n10 = new Node(10),
10 n11 = new Node(11), n12 = new Node(12);
11 Tree t = new Tree(n1);
12 System.out.printf("tree(1): %n%s%n%n",t);
13 boolean aok = false;
14 aok = t.addNode(n1,n2);
15 System.out.printf("addNode(1,2): %b%n",aok);
299
10.4 List
16 t.addNode(n2,n3); t.addNode(n2,n6);
17 System.out.printf("after adding 2, 3, 6: %n%s%n%n",t);
18 t.addNode(n1,n10); t.addNode(n10,n11); t.addNode(n10,n12);
19 t.addNode(n3,n4); t.addNode(n3,n5);
20 t.addNode(n6,n7); t.addNode(n7,n8); t.addNode(n7,n9);
21 boolean repOk = t.repOK();
22 if (repOk)
23 System.out.printf("complete tree: %n%s%n%n",t);
24 System.out.println("valid: " + repOk);
25 }
26 }
10.4 List
List-Related Terms
The common list-related terms are: length, head, tail, sublist and subsequence [1].
Definition 10.14. Length
The length of a list is number of occurrences of its elements. ♣
For example, the list L = (2, 3, 5, 7, 11, 13, 17, 19) has length = 8.
Definition 10.15. Sublist
A sublist of a list is a list that contains zero or more consecutive elements. ♣
300
10.4 List
For example, 2 is the head and (3, 5, 7, 11, 13, 17, 19) is the tail of the list L above.
Recursive Definition
List can be defined recursively in terms of head and tail [9].
Definition 10.19. List
Basis.
() is a list.
Induction.
∀x, ∀L ∈ List.(x, L.elements) is a list.
(L.elements is the sequence of elements of L) ♣
Abstract Properties
List’s properties are relatively straight-forward and are captured in Definition 10.20.
Definition 10.20. List properties
List has the following properties:
1. list is a sequence of elements
2. a non-empty list must have a head, tail may be empty ♣
10.4.2 Operations
The following essential list operations are adapted from [1].
301
10.4 List
Operation insert
To insert an element an element into an arbitrary position in the list. A special case
is to push an element x into the first position of a list (a1 , ..., an ) to become its new head.
This creates a new list (x, a1 , ..., an ).
Operation push
To insert an element at the front of the list (pushing the existing elements to the
right).
Operation add
To add an element to the end of the list.
Operation remove
To remove an occurrence of an element from a list. If element is not in the list, the
operation should not change the list. Otherwise, only the first occurrence of the element
is removed.
Operation lookup
To return true or false depending on whether or not an element is in the list.
Operation concatenate
To form a new list from concatenating two lists. The new list begins with elements
of the first list and continues with the elements the second list. Note that the empty list
is the identity for concatenation. That is, for any list L, we have L = L = L.
Operation head
To return the head of the list.
Operation tail
To return the tail of the list.
302
10.4 List
Operation get
To return an element at a given position of the list. This operation is called
retrieve in [1].
Operation size
To return the length of the list. This operation is called length in [1].
Operation isEmpty
To return true or false depending on whether or not the list is empty.
303
10.4 List
It may appear at first that attribute tail does not exactly match the inductive rule,
which requires that only the elements of the existing list (not the list itself) are used to
construct the new list. However, a closer look reveals that it logically is the same. The
fact that the elements of a list becomes part of another list means that the list itself also
belongs to that list. Further in object-oriented design, the fact that tail references a
List object is an internal design detail, and is hidden from code that uses the class List.
As far as the using code is concerned, List still represents a sequence of elements.
Derived attribute
Because operation size() involves recursively counting the number of occurrences
of all the tail sub-lists of a list, invoking it many times may affect the overall performance
of the program. The derived attribute pattern is applied to overcome this. This involves
creating a derived attribute named sz and using it to record the current number of
elements of the list. To keep this attribute current, it is updated when a new element is
inserted to or removed from the list.
304
10.4 List
Note that since derived attributes are not essential to the abstract concept, they need
not be listed in the @attributes section of the header specification.
Constructors
Class List has three constructors: one public and two private. The public con-
structor implements the basis rule of the recursive definition. The one-argument private
constructor together with the operation push implements the inductive rule of the def-
inition. The two-argument private constructor is used by the operation clone to copy
the tail before returning it.
Operation size
For performance reasons, this operation returns the value of the derived attribute
sz, instead of computing it using recursion.
Operation tail
This operation does not return tail directly. Instead it makes a copy of the List
object that is referenced by this attribute and returns a reference to it. This helps protect
this attribute from modifications outside of class.
Operation clone
This operation returns a copy of the current list object. It is used by the tail()
operation mentioned above. The copy is another List object that has the same content
as the current object.
Design Specification
Listing 10.9 shows the design specification of the recursive design of List. Note
the followings:
the recursive definition is inserted in the @object section
attribute head has the same type as the List’s type variable T
attribute tail has the type List<T>
the @abstract_properties section states the two List’s properties in terms of
the two attributes head, tail
305
10.4 List
306
10.4 List
40 /**
41 * @effects initialises this to be ()
42 */
43 public List()
44 /**
45 * This constructor together with operation <tt>push</tt>
implement the inductive rule.
46 *
47 * @requires x != null
48 * @effects initialises this to be (x)
49 */
50 private List(T x)
51 /**
52 * This constructor is used to clone a list.
53 *
54 * @requires h != null
55 * @effects initialise this to be (h,x1,...,xn) where t = (x1
,...,xn)
56 */
57 private List(T h, List<T> t)
58 /**
59 * This operation implements the inductive rule.
60 *
61 * @requires x != null
62 * @modifies this
63 * @effects
64 * if this is empty
307
10.4 List
65 * head = x
66 * else
67 * inserts x into the first position of this (pushing
68 * the element at the current position to the right)
69 */
70 public void push(T x)
71 /**
72 * This operation implements the inductive rule.
73 *
74 * @requires x != null
75 * @modifies this
76 * @effects
77 * if this is empty
78 * head = x
79 * else
80 * adds x to the end of this
81 */
82 @DOpt(type=OptType.MutatorAdd)
83 public void add(T x)
84 /**
85 * @requires x != null
86 * @modifies this
87 *
88 * @effects
89 * if this is empty or x is not in this
90 * do nothing
91 * else
92 * remove the first occurrence of x from this
93 *
94 * i.e. (recursive)
95 * ...
96 */
97 @DOpt(type=OptType.MutatorRemove)
98 public void remove(T x)
99 /**
100 * @requires x != null
308
10.4 List
101 * @effects
102 * if x is in this
103 * return true
104 * else
105 * return false
106 */
107 @DOpt(type=OptType.ObserverContains)
108 public boolean lookUp(T x)
109 /**
110 * @effects
111 * return head
112 */
113 @DOpt(type=OptType.Observer) @AttrRef("head")
114 public T head()
115 /**
116 * @effects
117 * if this is empty or a single-element list
118 * return null
119 * else
120 * return tail as a new list
121 */
122 @DOpt(type=OptType.Observer) @AttrRef("tail")
123 public List<T> tail()
124 /**
125 * @requires index >= 0
126 * @effects
127 * if this is empty or index is out of range
128 * return null
129 * else
130 * return the element at the position index
131 */
132 @DOpt(type=OptType.Observer)
133 public T get(int index)
134 /**
135 * @effects
136 * return the number of occurrences of the elements of this
309
10.4 List
137 */
138 @DOpt(type=OptType.ObserverSize)
139 public int size()
140 /**
141 * @effects
142 * if this is empty
143 * return true
144 * else
145 * return false
146 */
147 @DOpt(type=OptType.Observer)
148 public boolean isEmpty()
149 @Override
150 public String toString()
151 /**
152 * @effects
153 * return a copy of this
154 */
155 @Override
156 public List<T> clone()
157 /**
158 * @effects
159 * if this satisfies abstract properties
160 * return true
161 * else
162 * return false
163 */
164 public boolean repOK()
165 } /** end {@link List} */
310
10.4 List
null, since the list terminates here. The head of each cell contains the value of each
element.
Design specification
Listing 10.10 shows the partial specification of class LinkedList. In this, we
highlight the differences between this specification and the specification of the recursive
design in Section 10.4.4. The operational specification is omitted as it is the same as the
specification of that design.
Note the followings about the design specification:
@object section is defined in terms of cell.head and cell.tail
the abstract properties regarding head and tail is moved to class Cell
311
10.4 List
312
10.4 List
30 @DomainConstraint(type="Cell<T>",mutable=true,optional=true)
31 private Cell<T> cell;
32 // derived attribute
33 @DomainConstraint(type="Integer",mutable=false,optional=true)
34 private int sz;
35 // constructors
36 /**
37 * @effects initialises this to be ()
38 */
39 public LinkedList() {
40 // empty list
41 }
42 /**
43 * @requires n != null
44 * @effects initialises this to be a list (n.head)
45 */
46 private LinkedList(Cell<T> n) {
47 cell = n;
48 }
49
52 /**
53 * @overview Represents a linked cell that contains a head
value of the current list and a nullable
54 * reference pointer to another cell representing the
tail of the current list.
55 *
56 * @attributes
57 * head Object
58 * tail Cell
59 *
60 * @object
61 * A typical cell is <v,r>, where head(v) and tail(r).
62 *
63 * @abstract_properties
313
10.4 List
64 * mutable(head)=false /\ optional(head)=false /\
65 * mutable(tail)=false /\ optional(tail)=true
66 *
67 * @author dmle
68 */
69 private class Cell<T> {
70 private T head;
71 private Cell<T> tail;
72
73 // constructors
74 /**
75 * @requires v != null
76 * @effects
77 * initialise this to be <v,r>
78 */
79 public Cell(T v, Cell<T> r)
80 /**
81 * @requires v != null
82 * @effects
83 * initialise this to be <v,null>
84 */
85 public Cell(T v)
86 /**
87 * @effects
88 * sets this.{@link #tail} = tail
89 */
90 public void setTail(Cell<T> tail)
91 /**
92 * @effects
93 * return {@link #tail}
94 */
95 public Cell<T> getTail()
96 /**
97 * @effects
98 * return a deep copy of this
99 */
314
10.4 List
100 @Override
101 public Cell<T> clone()
102 /**
103 * @effects
104 * if this satisfies abstract properties
105 * return true
106 * else
107 * return false
108 */
109 public boolean repOK()
110 } /** end {@link LinkedList.Cell} */
111 } /** end {@link LinkedList} */
10.4.6 Implementation
315
10.4 List
18 @DomainConstraint(type="Integer",mutable=false,optional=true)
19 private int sz;
20
21 /**
22 * @effects initialises this to be ()
23 */
24 public List() {
25 // empty list
26 }
27
28 /**
29 * This constructor together with operation <tt>push</tt>
implement the inductive rule.
30 *
31 * @requires x != null
32 * @effects initialises this to be (x)
33 */
34 private List(T x) {
35 // make x the head
36 head = x;
37
38 // update length
39 sz++;
40 }
41
42 /**
43 * This constructor is used to clone a list.
44 *
45 * @requires h != null
46 * @effects initialise this to be (h,x1,...,xn) where t = (x1
,...,xn)
47 */
48 private List(T h, List<T> t) {
49 head = h;
50 tail = t;
51 }
316
10.4 List
52
53 /**
54 * This operation implements the inductive rule.
55 *
56 * @requires x != null
57 * @modifies this
58 * @effects
59 * if this is empty
60 * head = x
61 * else
62 * inserts x into the first position of this (pushing
63 * the element at the current position to the right)
64 */
65 public void push(T x) {
66 if (head == null) {
67 // make x the head
68 head = x;
69 } else {
70 // push head into tail
71 if (tail == null) {
72 tail = new List<>(head);
73 } else {
74 tail.push(head);
75 }
76
81 // update length
82 sz++;
83 }
84
85 /**
86 * This operation implements the inductive rule.
87 *
317
10.4 List
88 * @requires x != null
89 * @modifies this
90 * @effects
91 * if this is empty
92 * head = x
93 * else
94 * adds x to the end of this
95 */
96 @DOpt(type=OptType.MutatorAdd)
97 public void add(T x) {
98 if (head == null) {
99 // make x the head
100 head = x;
101 } else {
102 // keep head the same, add x to tail
103 if (tail == null) {
104 tail = new List<>(x);
105 } else {
106 tail.add(x);
107 }
108 }
109
114 /**
115 * @requires x != null
116 * @modifies this
117 *
118 * @effects
119 * if this is empty or x is not in this
120 * do nothing
121 * else
122 * remove the first occurrence of x from this
123 *
318
10.4 List
132
133 if (head.equals(x)) {
134 // x is head
135 if (tail != null) {
136 // has tail: make tail.head the head
137 head = tail.head;
138 tail.remove(head);
139 } else {
140 // no tail: nullify head
141 head = null;
142 }
143 } else if (tail != null) {
144 // x is not head /\ has tail: recursively remove x in tail
145 tail.remove(x);
146 }
147
157 /**
158 * @requires x != null
159 * @effects
319
10.4 List
160 * if x is in this
161 * return true
162 * else
163 * return false
164 */
165 @DOpt(type=OptType.ObserverContains)
166 public boolean lookUp(T x) {
167 if (head == null)
168 return false;
169
170 if (head.equals(x)) {
171 return true;
172 } else if (tail != null) {
173 return tail.lookUp(x);
174 } else {
175 return false;
176 }
177 }
178
179 /**
180 * @effects
181 * return head
182 */
183 @DOpt(type=OptType.Observer) @AttrRef("head")
184 public T head() {
185 return head;
186 }
187
188 /**
189 * @effects
190 * if this is empty or a single-element list
191 * return null
192 * else
193 * return tail as a new list
194 */
195 @DOpt(type=OptType.Observer) @AttrRef("tail")
320
10.4 List
204 /**
205 * @requires index >= 0
206 * @effects
207 * if this is empty or index is out of range
208 * return null
209 * else
210 * return the element at the position index
211 */
212 @DOpt(type=OptType.Observer)
213 public T get(int index) {
214 T h = head;
215 List<T> t = tail;
216
228 return h;
229 }
230
231 /**
321
10.4 List
232 * @effects
233 * return the number of occurrences of the elements of this
234 */
235 @DOpt(type=OptType.ObserverSize)
236 public int size() {
237 return sz;
238 }
239
240 /**
241 * @effects
242 * if this is empty
243 * return true
244 * else
245 * return false
246 */
247 @DOpt(type=OptType.Observer)
248 public boolean isEmpty() {
249 if (head == null) // empty
250 return true;
251 else
252 return false;
253 }
254
255 @Override
256 public String toString() {
257 StringBuffer sb = new StringBuffer();
258 if (head == null) { // empty
259 sb.append("()");
260 } else {
261 sb.append("(");
262 T h = head;
263 List<T> t = tail;
264 sb.append(h);
265 while (t != null) {
266 sb.append(",");
267 sb.append(t.head);
322
10.4 List
268 t = t.tail;
269 }
270 sb.append(")");
271 }
272
276 /**
277 * @effects
278 * return a copy of this
279 */
280 @Override
281 public List<T> clone() {
282 if (head == null)
283 return null;
284
285 T h = head;
286 List<T> t;
287 if (tail != null) {
288 t = tail.clone();
289 } else {
290 t = null;
291 }
292
296 /**
297 * @effects
298 * if this is valid
299 * return true
300 * else
301 * return false
302 */
303 public boolean repOK() {
323
10.4 List
19 // push
20 System.out.println("push:\n=====================");
21 for (Object o : objs) {
22 l.push(o);
23 System.out.printf("push(%s) -> %s%n", o,l);
24 }
25
324
10.4 List
32 // add
33 System.out.println("add:\n=====================");
34 for (Object o : objs) {
35 l.add(o);
36 System.out.printf("add(%s) -> %s%n", o,l);
37 }
38
45 // look up
46 System.out.println("lookup:\n=====================");
47 boolean tf;
48 for (Object o : objs) {
49 tf = l.lookUp(o);
50 System.out.printf("lookUp(%s) -> %b%n", o,tf);
51 }
52
58 // get
59 System.out.println("get:\n=====================");
60 int size = l.size();
61 for (int i = 0; i < size; i++) {
62 Object o = l.get(i);
325
10.4 List
66 index = 5;
67 a = l.get(index);
68 System.out.printf("get(%d) -> %s%n", index,a);
69
70 // remove
71 System.out.println("remove:\n=====================");
72 for (Object o : objs) {
73 l.remove(o);
74 System.out.printf("remove(%s) -> %s%n", o,l);
75 }
76 System.out.printf("after: %s%n", l);
77
326
10.4 List
11 */
12 public class LinkedList<T> implements Collection<T> {
13 @DomainConstraint(type="Cell<T>",mutable=true,optional=true)
14 private Cell<T> cell;
15
16 // derived attribute
17 @DomainConstraint(type="Integer",mutable=false,optional=true)
18 private int sz;
19
20 // constructors
21 /**
22 * @effects initialises this to be ()
23 */
24 public LinkedList() {
25 // empty list
26 }
27
28 /**
29 * @requires n != null
30 * @effects initialises this to be a list (n.head)
31 */
32 private LinkedList(Cell<T> n) {
33 cell = n;
34 }
35
36 /**
37 * @requires x != null
38 * @effects initialises this to be (x)
39 */
40 public LinkedList(T x) {
41 cell = new Cell<>(x);
42 sz++;
43 }
44
45 /**
46 * @requires x != null
327
10.4 List
47 * @modifies this
48 * @effects
49 * if this is empty
50 * initialise cell such that cell.head = x
51 * else
52 * inserts x into the first position of this (pushing
53 * the element at the current position to the right)
54 */
55 public void push(T x) {
56 if (cell == null) {
57 cell = new Cell<>(x);
58 } else {
59 // push x
60 cell = new Cell<>(x, cell);
61 }
62 sz++;
63 }
64
65 /**
66 * @requires x != null
67 * @modifies this
68 * @effects
69 * if this is empty
70 * initialise cell such that cell.head = x
71 * else
72 * adds x to the end of this
73 */
74 @DOpt(type=OptType.MutatorAdd)
75 public void add(T x) {
76 if (cell == null) {
77 cell = new Cell<>(x);
78 } else {
79 // add x to the tail of the last cell
80 Cell<T> tail = cell.getTail(), last = null;
81 while (tail != null) {
82 last = tail;
328
10.4 List
83 tail = last.getTail();
84 }
85
95 /**
96 * @requires x != null
97 * @modifies this
98 *
99 * @effects
100 * if this is empty or x is not in this
101 * do nothing
102 * else
103 * remove the first occurrence of x from this
104 */
105 @DOpt(type=OptType.MutatorRemove)
106 public void remove(T x) {
107 boolean found = false;
108 Cell<T> n = cell;
109 Cell<T> prev = null;
110 while (!found && n != null) {
111 Cell<T> tail = n.tail;
112 if (n.head.equals(x)) { // compare using equals
113 if (prev != null)
114 prev.tail = tail;
115 else
116 cell = tail;
117 found = true;
118 sz--;
329
10.4 List
119 } else {
120 prev = n;
121 n = tail;
122 }
123 }
124 }
125
126 /**
127 * @requires x != null
128 * @effects
129 * if x is in this
130 * return true
131 * else
132 * return false
133 */
134 @DOpt(type=OptType.ObserverContains)
135 public boolean lookUp(T x) {
136 boolean found = false;
137 Cell<T> n = cell;
138 while (!found && n != null) {
139 if (n.head.equals(x)) { // compare using equals
140 found = true;
141 }
142 n = n.tail;
143 }
144
148 /**
149 * @effects
150 * return head
151 */
152 @DOpt(type=OptType.Observer) @AttrRef("head")
153 public T head() {
154 if (cell != null)
330
10.4 List
160 /**
161 * @effects
162 * if this is empty or a single-element list
163 * return null
164 * else
165 * return tail as a new list
166 */
167 @DOpt(type=OptType.Observer) @AttrRef("tail")
168 public LinkedList<T> tail() {
169 if (cell != null) { /* this is not empty */
170 Cell<T> tail = cell.tail;
171 if (tail != null) {
172 // return as a new list
173 Cell<T> ctail = tail.clone();
174 LinkedList<T> l = new LinkedList<>(ctail);
175 return l;
176 } else {
177 return null;
178 }
179 } else {
180 return null;
181 }
182 }
183
184 /**
185 * @requires index >= 0
186 * @effects
187 * if this is empty or index is out of range
188 * return null
189 * else
190 * return the element at the position index
331
10.4 List
191 */
192 @DOpt(type=OptType.Observer)
193 public T get(int index) {
194 if (cell == null) {
195 return null;
196 } else {
197 int count = 0;
198 Cell<T> n = cell;
199 while (n != null) {
200 if (count == index) {
201 return n.head;
202 } else {
203 count++;
204 n = n.tail;
205 }
206 }
207
212 /**
213 * @effects
214 * returns the number of occurrences of the elements of this
215 */
216 @DOpt(type=OptType.ObserverSize)
217 public int size() {
218 return sz;
219 }
220
221 /**
222 * @effects
223 * if this is empty
224 * return true
225 * else
226 * return false
332
10.4 List
227 */
228 @DOpt(type=OptType.Observer)
229 public boolean isEmpty() {
230 if (cell == null) // empty
231 return true;
232 else
233 return false;
234 }
235
236
237 @Override
238 public String toString() {
239 StringBuffer sb = new StringBuffer();
240 if (cell == null) { // empty
241 sb.append("()");
242 } else {
243 sb.append("(");
244 Cell<T> n = cell;
245 while (n != null) {
246 sb.append(n.head);
247 n = n.tail;
248 if (n != null)
249 sb.append(",");
250 }
251 sb.append(")");
252 }
253
257 /**
258 * @overview Represents a linked cell that contains a head
value of the current list and a nullable
259 * reference pointer to another cell representing the
tail of the current list.
260 *
333
10.4 List
261 * @attributes
262 * head Object
263 * tail Cell
264 *
265 * @object
266 * A typical cell is <v,r>, where head(v) and tail(r).
267 *
268 * @abstract_properties
269 * mutable(head)=false /\ optional(head)=false /\
270 * mutable(tail)=false /\ optional(tail)=true
271 *
272 * @rep_invariant
273 * head != null
274 *
275 * @author dmle
276 */
277 private class Cell<T> {
278 private T head;
279 private Cell<T> tail;
280
281 // constructors
282 /**
283 * @requires v != null
284 * @effects
285 * initialise this to be <v,r>
286 */
287 public Cell(T v, Cell<T> r) {
288 head = v;
289 tail = r;
290 }
291
292 /**
293 * @requires v != null
294 * @effects
295 * initialise this to be <v,null>
296 */
334
10.4 List
301 /**
302 * @effects
303 * sets this.{@link #tail} = tail
304 */
305 public void setTail(Cell<T> tail) {
306 this.tail = tail;
307 }
308
309 /**
310 * @effects
311 * return {@link #tail}
312 */
313 public Cell<T> getTail() {
314 return tail;
315 }
316
317 /**
318 * @effects
319 * return a deep copy of this
320 */
321 @Override
322 public Cell<T> clone() {
323 // deep clone
324 T v = head;
325
335
10.4 List
333 /**
334 * @effects
335 * if this satisfies abstract properties
336 * return true
337 * else
338 * return false
339 */
340 public boolean repOK() {
341 if (head == null)
342 return false;
343
13 Object a = 1;
14 int index = 1;
15 System.out.printf("lookUp(%s) -> %b%n", a, l.lookUp(a));
16 System.out.printf("get(%d) -> %s%n", index, l.get(index));
17 System.out.printf("size() -> %d%n", l.size());
336
10.4 List
22 // insert
23 System.out.println("push:\n=====================");
24 for (Object o : objs) {
25 l.push(o);
26 System.out.printf("push(%s) -> %s%n", o,l);
27 }
28
35 // add
36 System.out.println("add:\n=====================");
37 for (Object o : objs) {
38 l.add(o);
39 System.out.printf("add(%s) -> %s%n", o,l);
40 }
41
48 // look up
49 System.out.println("lookup:\n=====================");
50 boolean tf;
51 for (Object o : objs) {
52 tf = l.lookUp(o);
53 System.out.printf("lookUp(%s) -> %b%n", o,tf);
337
10.4 List
54 }
55
61 // get
62 System.out.println("get:\n=====================");
63 int length = l.size();
64 for (int i = 0; i < length; i++) {
65 Object o = l.get(i);
66 System.out.printf("get(%d) -> %s%n", i,o);
67 }
68
69 index = length+1;
70 a = l.get(index);
71 System.out.printf("get(%d) -> %s%n", index,a);
72
73 // remove
74 System.out.println("remove:\n=====================");
75 for (Object o : objs) {
76 l.remove(o);
77 System.out.printf("remove(%s) -> %s%n", o,l);
78 }
79 System.out.printf("after: %s%n", l);
80
K Chapter 10 Exercise k
338
10.4 List
The exercises in this chapter help practise using and extending the design of list and tree.
Some exercises are adopted from [1].
Tree.
1. Design and implement another recursive version of the operation Tree.toString
which produces a horizontal, textual representation of the tree, as shown in the
illustration below:
2. (Ex 5.2.1 [1]) For the the tree below, identify the following elements:
339
10.4 List
List.
7. (Ex 6.2.1 [1]) Answer the following questions about the list (2, 7, 1, 8, 2).
(a). What is the head?
(b). What is the tail?
(c). What is the size?
(d). What are all the sublists?
(e). How many subsequences are there?
8. (Adapted from Ex 6.2.3 [1])): In a list of size n ≥ 0, what are all the possible
subsequences?
9. The code of recursive List class shows that operations get and toString follows
an iterative not recursive implementation. How would you change these operations
to follow the recursive implementation?
10. All the operations of class LinkedList followed the iterative implementation.
Discuss the possibility of changing these operations to follow the recursive imple-
mentation.
11. Compare and contrast the implementations of the two operations List.push and
LinkedList.push.
12. Design and implement a class named DoubleLinkedList [1] that represents
linked list in which each cell maintains a reference to the previous cell.
340
10.A Node
10.A Node
The design and Java code of class Node.
Listing 10.15: Class Node
1 package chap10.tree;
2 import utils.DomainConstraint;
3 /**
4 * @overview
5 * Represents a labelled node.
6 * @attributes
7 * label T
8 * @abstract_properties
9 * mutable(label)=true /\ optional(label) = false
10 * @author Duc Minh Le (ducmle)
11 */
12 public class Node<T> {
13 @DomainConstraint(mutable=true,optional=false)
14 private T label;
15
16 /**
17 * @requires label != null /\ label.length() > 0
18 * @effects
19 * initialise this as Node(label)
20 */
21 public Node(T label) {
22 this.label = label;
23 }
24
25 /**
26 * @effects
27 * return label
28 */
29 public T getLabel() {
30 return label;
31 }
32
341
10.B Edge
33 /**
34 * @requires label != null /\ label.length() > 0
35 * @effects
36 * sets this.label = label
37 */
38 public void setLabel(T label) {
39 this.label = label;
40 }
41
42 @Override
43 public String toString() {
44 return toString(false);
45 }
46
54 @Override
55 public boolean equals(Object o) {
56 if (o == null || !(o instanceof Node))
57 return false;
58
59 return ((Node)o).label.equals(label);
60 }
61 }
10.B Edge
The design and Java code of class Edge.
Listing 10.16: Class Edge
1 package chap10.tree;
342
10.B Edge
2 import utils.DomainConstraint;
3 /**
4 * @overview
5 * Represents a binary, directed edge.
6 * @attributes
7 * src Node
8 * tgt Node
9 * @abstract_properties
10 * mutable(src)=true /\ optional(src) = false /\
11 * mutable(tgt)=true /\ optional(tgt) = false
12 * @author Duc Minh Le (ducmle)
13 */
14 public class Edge {
15 @DomainConstraint(type="Node",mutable=true,optional=false)
16 private Node src;
17 @DomainConstraint(type="Node",mutable=true,optional=false)
18 private Node tgt;
19
20 /**
21 * @requires src != null /\ tgt != null
22 * @effects
23 * initialise this as Edge(src,tgt)
24 */
25 public Edge(Node src, Node tgt) {
26 this.src = src;
27 this.tgt = tgt;
28 }
29
30 /**
31 * @requires src != null
32 * @effects
33 * sets this.src = src
34 */
35 public void setSrc(Node src) {
36 if (src != null) {
37 this.src = src;
343
10.B Edge
38 }
39 }
40
41 /**
42 * @effects
43 * return src
44 */
45 public Node getSrc() {
46 return src;
47 }
48
49 /**
50 * @requires tgt != null
51 * @effects
52 * sets this.tgt = tgt
53 */
54 public void setTgt(Node tgt) {
55 if (tgt != null) {
56 this.tgt = tgt;
57 }
58 }
59
60 /**
61 * @effects
62 * return tgt;
63 */
64 public Node getTgt() {
65 return tgt;
66 }
67
68 /**
69 * @effects
70 * if n.equals(src)
71 * return true
72 * else
73 * return false
344
10.B Edge
74 */
75 public boolean hasSrc(Node n) {
76 if (n == null) return false;
77
78 return (src.equals(n));
79 }
80
81 /**
82 * @effects
83 * if n.equals(tgt)
84 * return true
85 * else
86 * return false
87 */
88 public boolean hasTgt(Node n) {
89 if (n == null) return false;
90
91 return (tgt.equals(n));
92 }
93
94 @Override
95 public String toString() {
96 return toString(false);
97 }
98
106 @Override
107 public boolean equals(Object o) {
108 if (o == null || !(o instanceof Edge))
109 return false;
345
10.B Edge
110
346
Bibliography
[1] Aho, A. V. and Ullman, J. D. (1994). Foundations of Computer Science: C Edition. W. H. Freeman,
New York, 2nd edition.
[2] Alexander, C., Alexander, P. i. t. D. o. A. C., Ishikawa, S., Silverstein, M., Jacobson, M., Fiksdahl-
King, I., and Shlomo, A. (1977). A Pattern Language: Towns, Buildings, Construction. Oxford
University Press.
[3] Boer, F. D., Serbanescu, V., Hähnle, R., Henrio, L., Rochas, J., Din, C. C., Johnsen, E. B., Sirjani,
M., Khamespanah, E., Fernandez-Reyes, K., and Yang, A. M. (2017). A Survey of Active Object
Languages. ACM Comput. Surv., 50(5):76:1–76:39.
[4] Booch, G. (1986). Object-Oriented Development. IEEE Transactions on Software Engineering,
SE-12(2):211–221.
[5] Booch, G., Maksimchuk, R. A., Engle, M. W., Young, B. J., Conallen, J., and Houston, K. A. (2007).
Object-Oriented Analysis and Design with Applications. Addison-Wesley Professional, Upper Saddle
River, NJ, 3rd edition.
[6] David J. Eck (2020). Introduction to Programming Using Java. Hobart and William Smith Colleges,
8th edition.
[7] Dijkstra, E. (1979a). Programming considered as a human activity. In Classics in software engineer-
ing, pages 1–9. Yourdon Press, USA.
[8] Dijkstra, E. (1979b). Structured programming. In Classics in software engineering, pages 41–48.
Yourdon Press, USA.
[9] Eisenbach, S., Khoshnevisan, H., and Vickers, S. (1994). Reasoned Programming. Prentice Hall
Trade, New York.
[10] Gamma, E., Helm, R., Johnson, R., Vlissides, J., and Booch, G. (1994). Design Patterns: Elements
of Reusable Object-Oriented Software. Addison-Wesley Professional, Reading, Mass, 1st edition.
[11] Gosling, J., Joy, B., Jr, G. L. S., Bracha, G., and Buckley, A. (2014). The Java Language Specification,
Java SE 8 Edition. Addison-Wesley Professional, Upper Saddle River, NJ, 1st edition.
[12] Guttag, J. (1980). Notes on Type Abstraction (Version 2). IEEE Transactions on Software Engi-
neering, SE-6(1):13–23.
[13] Guttag, J. V. (2002). Algebraic Specification of Abstract Data Types. Broy, M., Definert. E.,(eds.):
Software Pioneers, Springer.
[14] Hoffer, J. A., George, J., and Valacich, J. A. (2013). Modern Systems Analysis and Design. Prentice
Hall, Boston, 7th edition.
[15] Kleppe, A. (2008). Software Language Engineering: Creating Domain-Specific Languages Using
Metamodels. Addison-Wesley Professional, Upper Saddle River, NJ, 1st edition.
[16] Knuth, D. E. (1984). Literate programming. Comput. J., 27(2):97–111.
[17] Larman, C. (2004). Applying UML and Patterns: An Introduction to Object-Oriented Analysis and
Design and Iterative Development. Prentice Hall PTR, Upper Saddle River, NJ, USA, 3rd edition.
[18] Le, D. M., Dang, D.-H., and Nguyen, V.-H. (2018). On Domain Driven Design Using Annotation-
Based Domain Specific Language. Journal of Computer Languages, Systems & Structures, 54:199–235.
[19] Lilis, Y. and Savidis, A. (2019). A Survey of Metaprogramming Languages. ACM Comput. Surv.,
BIBLIOGRAPHY
52(6):113:1–113:39.
[20] Liskov, B. and Guttag, J. (2000). Program Development in Java: Abstraction, Specification, and
Object-Oriented Design. Pearson Education.
[21] Nassi, I. and Shneiderman, B. (1973). Flowchart techniques for structured programming. SIGPLAN
Not., 8(8):12–26.
[22] OMG (2015). Unified Modeling Language version 2.5. Technical Report formal/2015-03-01, OMG.
[23] Oracle (2016). Java Platform Standard Edition 8 API Specification.
[24] Oracle (2018). Java Persistence API Specification.
[25] Ray, P. P. (2017). A Survey on Visual Programming Languages in Internet of Things. Scientific
Programming, 2017:1231430. Publisher: Hindawi.
[26] Red Hat (2017a). Bean Validation 2.0 (JSR 380).
[27] Red Hat (2017b). Hibernate Validator.
[28] Scott, M. L. (2009). Programming Language Pragmatics. Morgan Kaufmann, Amsterdam ; Boston,
3rd edition.
[29] Sebesta, R. (2015). Concepts of Programming Languages. Pearson, 11th edition.
[30] Sommerville, I. (2011). Software Engineering. Pearson, 9th edition.
[31] Tomassetti, F., Bruggen, D. v., and Smith, N. (2016). JavaParser: Visited. Leanpub.
[32] Trois, C., Del Fabro, M. D., de Bona, L. C. E., and Martinello, M. (2016). A Survey on SDN
Programming Languages: Toward a Taxonomy. IEEE Communications Surveys Tutorials, 18(4):2687–
2712. Conference Name: IEEE Communications Surveys Tutorials.
[33] Wallace, D. and Fujii, R. (1989). Software verification and validation: an overview. IEEE Software,
6(3):10–17. Conference Name: IEEE Software.
348