ali

Book Review: Program Development in Java

In Uncategorized on February 23, 2010 at 9:00 pm

Title: Program Development in Java

Author: Barbara Liskov, John Guttag

Publisher: Addison-Wesley

Year: 2001

I read this book because of Barbara Liskov. I first heard of Liskov via the Liskov substitution principle (also see 1 2). The book has a very academic flavor: there is discussion of a representation invariant, the meaning of subtypes, and the Alloy specification language is used, along with a novel notation for depicting dependencies between modules.

Weighing in at 400 pages, this is a large book. This review will cover the parts I found interesting.

Abstraction

The book talks a lot about abstraction.

  1. Abstraction by parameterization abstracts from the identity of the data by replacing them parameters.
  2. Abstraction by specification abstracts from the implementation details to the behavior users can depend on.

This reminds me of the recent paper On Understanding Data Abstraction. The book primary talks about data abstraction (objects), and iteration abstraction (iterators).

Exceptions

The book has an interesting take on exceptions. Say you have a function:

int search (Object elem);
  • If this is a binary search, then you should checkPrecondition (this.isSorted()) at the beginning. However, this would take too long, so you should throw an exception if you discover the array isn’t sorted. Essentially, check all preconditions at the beginning unless it isn’t feasible, and throw an exception if there is cause.
  • In any search, you should throw an exception when the element isn’t found (don’t return -1). Don’t change the function’s range from <index> to <index, or -1 if not found>. The author argues that returning -1 is more error prone, as the caller may forget to check for this special case.
  • The authors recommend unchecked exceptions only if you expect that users will usually write code that ensures the exception will not happen. They cites indexing into an array as an example.

Data Abstraction

From what I understand, here’s the recommended way of using equals, clone, and toString:

  • Should implement for immutable objects, must leave alone for mutable objects. The only concept of equality for mutable objects is identity.
  • Don’t ever, ever use mutable objects when you expect immutable objects (for instance, keys in a hash table).
  • Mutable objects must implement clone.
  • toString should be implemented by all.

Equality is defined as such:

Two objects should be equals if they are behaviorally equivalent. This means that it is not possible to distinguish between them using any sequence of calls to the objects’ methods.

Type Hierarchy

Of course, the book talks about the substitution principle 1. Subtypes must:

  • Have all the methods of the supertype, and the signatures of these methods must be compatible 1.
  • Behave like the supertype methods. A subtype method can weaken the precondition, and strengthen the postcondition:
    • presuper → presub
    • (presuper && postsub) → postsuper
  • Preserve all properties that can be proved about the supertype (all the preconditions and postconditions).

The book notes that Java’s notion of compatibility is too strict. Given Foo x, we should be allowed to write Foo y = x.clone() instead of having to write Foo y = (Foo) x.clone().

Specification

I liked the distinction between definitional versus operational specifications. The discussion on specifications was brief.

Testing

From the book:

  • Validation increases our confidence that the program works as intended (through verification or testing).
  • Verification is a formal or informal argument that a program works on all possible inputs.
  • Testing is the process of running a program, and comparing the output to what was expected.

The book has some hints on glass-box testing (aka white-box testing):

  • For loops with fixed amount of iteration: include one and two iterations.
  • For loops with variable amount of iteration: include zero, one, and two iterations.
  • For recursion: no recursion, and one recursive call.

This reminds me of some program (I can’t recall the name) for selecting test inputs. It was based on pairwise testing 34.

The exercises at the end of the chapter on testing are interesting.

Requirements Specification

I found the notation confusing. I hadn’t seen the UML-like notation the authors used for specifying relations. They used the Alloy specification language, which doesn’t have many users. I don’t know what the graphical notation, or the Alloy language added to the book. I also wonder if Alloy would’ve been used had it originated at some other university.

Still, the taxonomy of relations was interesting:

  • Each relationship has a source and destination,
  • multiplicity (N:M), and
  • mutability.

Design

The design chapter offered a fresh perspective: library and helper routines as “virtual machines.”

The Java Virtual Machine is every where. When you program for a virtual machine, you program against some useful abstraction. Perhaps memory is abstracted away, or I/O. In that respect, each library offering a high level API is a virtual machine of sorts, and so is each helper routine.

Design progresses by modular decomposition based on the recognition of useful abstractions.


1. http://www.objectmentor.com/resources/articles/lsp.pdf

2. http://en.wikipedia.org/wiki/Circle-ellipse_problem

3. http://en.wikipedia.org/wiki/All-pairs_testing

4. http://csrc.nist.gov/groups/SNS/acts/index.html

Advertisements
%d bloggers like this: