Skip to content Skip to navigation

Connexions

You are here: Home » Content » List Structure and the Interpreter Design Pattern

Navigation

Recently Viewed

This feature requires Javascript to be enabled.

Tags

(What is a tag?)

These tags come from the endorsement, affiliation, and other lenses that include this content.
 

List Structure and the Interpreter Design Pattern

Module by: Dung Nguyen. E-mail the author

Summary: Operations of the composite list structure are implemented using the Interpreter Design Pattern.

Note: You are viewing an old version of this document. The latest version is available here.

List Processing

In the previous lecture, we define what a list is and implement it using the composite design pattern. This list structure is fully encapsulated and does not expose any of its internal components. In order to manipulate such a list without having to make public its internals, we need to add methods to the structure. This lecture discusses the structure of the algorithms on the list.

What can a list do?

Length of a list

Suppose we are given a list L and asked to find out how many elements it has. What should we do? The temptation here is to start thinking about "traversing" the list and keep a count as we go along, and when we encounter the "end" of the list, the count should be the number of elements in the list. But how do we know that that's the right answer? In order to determine whether or not the result obtained by counting as one traverses the list from beginning to end is correct, we have to define what it means to be the number of elements in the list. The number of elements in a list is an abstract notion, isn't it? In order to define such a quantity, we need to go back to the definition of what a list is.

  • A list is an abstract notion of a container structure.
  • An empty list is a list that has no element
  • A non-empty list is a list that has an element called first and a list called rest.

To define the notion of the number of elements in a list, we need to define what we mean by the number of elements in an empty list and what we mean by the number of elements in a non-empty list.

  • The number of elements in a list is an abstract notion because the list is an abstract notion.
  • The number of elements of an empty list is 0.
  • The number of elements in a non-empty list that contains first and rest is 1 plus the number of elements in rest.

The definition of the number of elements in a list is thus recursive. The recursive characteristic of this definition arises naturally from the recursive characteristic of the list structure. What ever approach we use to compute the number of elements in a list, in order to prove correctness, we must show that the result satisfies the above definition.

Here is the code for the above computation.

Table 1 

package listFW;
/**
 * Represents the abstract list structure.
 */
public interface IList {
    /**
     * Abstract notion of the number of elements in this IList.
     */
    public int getLength();
}



package listFW;
/**
 * Represents empty lists.
 */
public class MTList implements IList {
    /**
     * The number of elements in an empty list is zero.
     */
    public int getLength() {
        return 0;
    }
}


package listFW;
/**
 * Represents non-empty lists.
 */
public class NEList implements IList {
   private Object _first;
   private IList _rest;
   // Constructor ommitted.

   /**
    * The number of elements in a non-empty list is 
    * the number of elements of its rest plus 1.
    */
   public int getLength() {
       return 1 + _rest.getLength();
   }
}

The above coding pattern is an example of what 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 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. The interpreter pattern is usually applied to coding methods in a composite structure. 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.

Code Template

Whenever we want the IList to perform a task, we add a method to IList and write appropriate concrete implementations in MTList and NEList. The following table illustrates the code template for writing the concrete code in MTList and NEList.

Table 2
interface IList 

public abstract returnType methodName(parameter list); 
// returnType may be 'void'


MTList
 // no data


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).
*/
}

In Class Exercises (Role-Acting)

  • Find a number in a list and return "Found it!" if the number is in the list otherwise return "Not found!"
  • Append a list B to a given list A and return a new list consisting of A and B concatenated together.

Content actions

Download module as:

PDF | More downloads ...

Add module to:

My Favorites (?)

'My Favorites' is a special kind of lens which you can use to bookmark modules and collections. 'My Favorites' can only be seen by you, and collections saved in 'My Favorites' can remember the last module you were on. You need an account to use 'My Favorites'.

| A lens I own (?)

Definition of a lens

Lenses

A lens is a custom view of the content in the repository. You can think of it as a fancy kind of list that will let you see content through the eyes of organizations and people you trust.

What is in a lens?

Lens makers point to materials (modules and collections), creating a guide that includes their own comments and descriptive tags about the content.

Who can create a lens?

Any individual member, a community, or a respected organization.

What are tags? tag icon

Tags are descriptors added by lens makers to help label content, attaching a vocabulary that is meaningful in the context of the lens.

| External bookmarks