Rice University - Comp 212 - Intermediate Programming

Spring 2005

Lecture #06 - List algorithms and The Interpreter Design Pattern 

0. Design Patterns

Design patterns are tried-and-true design solutions to recurring problems in software construction.  Design patterns provide ways to structure software components into systems that are flexible, extensible, and have a high degree of reusability.  They also form a pattern language which is used to communicate software design.

Design patterns are often misconstrued as applicable only to programming in the large.  In reality, they can be applied to solving problems in programming in the small such as implementing data structures. The list structure shown in lecture #5 is an example of what is called the composite design pattern.

1. Composite Pattern

The composite pattern is a structural pattern that prescribes how to build a container object that is composed of other objects whose structure is isomorphic to that of the container itself.  In this pattern, the container is called a composite.  The composite pattern also prescribes a coding pattern for the container's methods: when a container is called to perform an operation, it traverses through its list of composed objects and call on them to perform the same operation.  It allows the client to treat the container and what it contains uniformly by making use of polymorphism.  The following UML diagram illustrates the general composite pattern.

composite.gif (7317 bytes)

 

2. Interpreting the List Structure: the Interpreter Design Pattern 

Recall the list structure given in lecture #5.

 

Instead of writing static methods to operate on lists, as we do in ListOps, we encapsulate these operations inside of the list structure by making them (abstract) methods of IList.  Automatically, IEmptyList, and INEList inherit these methods and force EmptyList and NEList to have concrete implementation code for these methods. 

This coding pattern is called the interpreter design pattern: we are interpreting the abstract behavior of a class (or interface) in each of the concrete subclasses (or implementations).  The coding pattern prescribed by the composite pattern as described in the above is a special application of the interpreter pattern.  The composite pattern is a pattern to express the structure of a system, while the interpreter pattern is used to express the behaviors (i.e. methods) of the system.  In a later lecture, we shall see another way of expressing the behavior of a composite structure without having to add new methods and interpret them.

Below is the UML class diagram depicting the interpreter pattern applied to the composite list structure to compute its length (getLength()), concatenate with another list (concatenate(IList L), and compute an appropriate String representation when the list is the rest of another list (toStringHelp()).

 

Click here to see the full documentation of the above design.

 

Code Template

Whenever we want the IList to perform a task, we add a method to IList and write appropriate concrete implementations in EmptyList and NEList.  The following table illustrates the code template for writing the concrete code in EmptyList and NEList.  This code template is analogous to the Comp 210 "design recipe template".

interface IList
public abstract returnType methodName(parameter list);

// returnType may be 'void'

EmtpyList NEList 

Object _first;
IList _rest;

public returnType methodName(parameter list) {

/*
This is in general the base case of a recursive call.
Write the (non-recursive) code to solve the problem.
*/

}

public returnType methodName(parameter list) {

/*
This is in general a recursive method.
The code here can refer to _first and _rest, and all the methods in NEList
When referencing _rest, one usually makes the recursive call:
_rest.methodName(appropriate parameters).
*/

}

 

Compute the length

interface IList
public abstract int  getLength();

 

EmtpyList NEList 

Object _first;

IList _rest;

public int getLength() {
    return 0;
}
public int getLength() {
    return 1 + _rest.getLength(); // recursive call!
}

Note how polymorphism is exploited here: at run-time _rest may be an EmptyList or a NEList, but we do need to check for the type of _rest at all.  The polymorphism machinery guarantees that the method of the correct class will be called.

 

Concatenate with another list

interface IList
public abstract IList concatenate(IList rhs);

// Note that the parameter rhs is an IList and not any lower-level classes.

 

EmtpyList NEList 

Object _first;
IList _rest;

public IList concatenate(IList rhs) {
    return rhs;
}
public IList concatenate(IList rhs){
    return new NEList(_first, _rest.concatenate(rhs)); // recursion again!
}

Note that the code makes use of the actual concrete class NEList to create a new instance of a non-empty IList.  On one hand this is OK since the code need not know anything about any other concrete classes in the IList hierarchy.  On the other hand, this code is tied very specifically to the class NEList. It can only be used with NEList and as a result, its reusability is somewhat limited.  

How can we make the algorithm for concatenating two lists reusable with respect to ANY implementation of IList?

 

 

Click here to see the code for the above classes.

 
D. X. Nguyen, last revised 01/26/2005
Dung X. Nguyen - Copyright 2003 - All rights reserved