Skip to content Skip to navigation Skip to collection information

Connexions

You are here: Home » Content » Principles of Object-Oriented Programming » List Structure and the Interpreter Design Pattern

Navigation

Lenses

What is a lens?

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.

This content is ...

Affiliated with (What does "Affiliated with" mean?)

This content is either by members of the organizations listed or about topics related to the organizations listed. Click each link to see a list of all content affiliated with the organization.
  • OrangeGrove display tagshide tags

    This collection is included inLens: Florida Orange Grove Textbooks
    By: Florida Orange Grove

    Click the "OrangeGrove" link to see all content affiliated with them.

    Click the tag icon tag icon to display tags associated with this content.

  • Rice Digital Scholarship

    This collection is included in aLens by: Digital Scholarship at Rice University

    Click the "Rice Digital Scholarship" link to see all content affiliated with them.

  • Bookshare

    This collection is included inLens: Bookshare's Lens
    By: Bookshare - A Benetech Initiative

    Comments:

    "Accessible versions of this collection are available at Bookshare. DAISY and BRF provided."

    Click the "Bookshare" link to see all content affiliated with them.

Also in these lenses

  • Busbee's Compter Science display tagshide tags

    This collection is included inLens: Busbee's Computer Science Lens
    By: Kenneth Leroy Busbee

    Comments:

    "Texas Common Course Numbering: COSC1337 or COSC1437"

    Click the "Busbee's Compter Science" link to see all content selected in this lens.

    Click the tag icon tag icon to display tags associated with this content.

  • eScience, eResearch and Computational Problem Solving

    This collection is included inLens: eScience, eResearch and Computational Problem Solving
    By: Jan E. Odegard

    Click the "eScience, eResearch and Computational Problem Solving" link to see all content selected in this lens.

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, Stephen Wong. E-mail the authors

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

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: Top-level abstract list definition 

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

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 3: Interpreter Pattern coding template for lists
interface IList 

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


MTList
 // no data


NEList  
  Object _first;
  IList _rest;


public returnType methodName(param list) { 
/*
This is in general the base case of a 
recursive call.  Write the (non-recursive) 
code to solve the problem.
*/
}


public returnType methodName(param 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.

Collection Navigation

Content actions

Download:

Collection as:

PDF | More downloads ...

Module as:

PDF | EPUB (?)

What is an EPUB file?

EPUB is an electronic book format that can be read on a variety of mobile devices.

Downloading to a reading device

For detailed instructions on how to download this content's EPUB to your specific device, click the "(?)" link.

| More downloads ...

Add:

Collection 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

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