The Quantification pattern addresses the problem of how to construct an object-oriented program to solve a problem modelled as a quantification [3, 6, 11].

Also Known As

Quantifier, Decrease and Conquer Algorithm [12], Linear Algorithm. Many apparently different problems are versions of the same one actually if they are observed abstractly.

Consider these two problems:

"Apply a function object f to each element in a range [first, last]."

"Return the first iterator i in the range [first, last] such that pred(*i) is true."

Both of them are in fact two instances of a more general problem that can be stated as:

“Apply function object Expression to each element in a collection of data such that function object Filter is true and combine them with the operator op .”

This abstract statement models a wide range of problems known as quantification problems. This model captures their analogies and their specific differences in two orthogonal directions:

• From the data point of view: the collection of data can be viewed as an abstract domain traversed by an iterator. This way, problems on particular data domains, like arrays, linked lists, files, etc., can be approached under the same guidelines.

• From the algorithmic point of view: all the quantification problems have a common behaviour, that consists of the traversal of a domain, taking each item, validating it (with the Filter function), applying Expression on it and relating it with the rest of the domain (by means of the operator op bound by the quantification).

Applicability

The Quantification pattern can be used to solve, by means of an object oriented program, a problem that requires a linear traversal over a collection of data. The pattern does not impose any constraint neither on the type of the result nor on the kind of the computation nor on the type of the collection of data.

Structure

Participants

• Quantification

• Implements the operation Solve, a template method defining the skeleton of the generic algorithm that solves any ptoblem modelled as a quantification problem.
 
• Implements the methods ApplyExp and ApplyFilter, that act as  invokers on the object functions Function (the Expression) and Predicate (the Filter).

• AbstractPredicate (Predicate)

• Defines an interface for the filter predicate application.
 
• ConcretePredicate (IsEven)

• Implements the abstract operation defined on the AbstractPredicate interface for a specific filter predicate.

• AbstractFunction (Function)

• Defines an interface for the expression function application.
 
• ConcreteFunction  (Square)
 
• Implements the abstract operation defined on the AbstractFunction interface for a specific expression function.

• AbstractInputDomain (Iterator)

• Defines an iterator interface for the traversal of the collection of data.

• ConcreteInputDomain (List)

• Implements the abstract operations defined on the AbstractInputDomain interface for a specific quantification problem.

• OutputDomain (Output)

 
• Defines an interface that represents  the output data domain, with the operations Base and Op.

 
• ConcreteOutputDomain (Number)
 
• Implements the abstract operations defined on the AbstractOutputDomain interface for a specific quantificatin problem.

Consequences

The huge diversity of quantification problems can be organized as a taxonomy depending on the nature of the computation [3, 5, 13, 15] i.e., on their functionality analogies. This taxonomy of problems lets you talk about families of problems, useful to find solutions to new problems by the search of isomorphic problems already solved [Grogono].

Quantification is a behaviour pattern taken from the formal specification languages [6] and from the functional programming context, useful for the systematic approach to the development of programs. As its structure relies on the structure of less complex behaviour patterns (Template Method, Iterator and Strategy [4]), Quantification inherits many of their consequences though adapted to this context.
 

A solution designed using the Quantification pattern may be composed with another quantification solution for a subproblem. The composition mechanism is provided by the object function pattern [9].

Implementation

The method Solve could be done using recursion, returning the call to Base when the collection traversal is ended and a recursive call to Solve (with the iterator advanced to the next element) combined by means of the Op function with the call to the Expression function on the current item.

Sample Code

class Quantification
{
   public static boolean ApplyFilter (Predicate f, Object arg)
   {
        return f.application (arg);
   }

   public static Output ApplyExp (Function f, Object arg)
   {
        return f.application (arg);
   }

   public static Output Solve (Iterator collection,
                               Output od,
                               Predicate filter,
                               Function expression)
   {
        Output result = od.Base();
        while (!collection.IsDone())
        {
            Item thisItem = collection.Next();
            if (ApplyFilter (filter, thisItem))
                result.Op (ApplyExp (expression, thisItem));
        };
        return result;
   }
}

Known Uses

The list comprehension mechanism of functional languages like Haskell [8] is a reduced version of the quantification pattern. For the construction quantification, Haskell has the syntax

    [Expression (x) | x <- seq , Filter (x)]

where seq is a Haskell list.

The Standard Template Library [5], which was adopted as part of the standard C++ library, has a nice set of examples of the quantification pattern in the non-mutating, minimum and maximum and generalized numeric algorithms sections. In the Iterator pattern [4] the operation Traverse that appears in the template class ListTraverser can be modelled as a Construction  quantification with an Expression named ProcessItem and without Filter. The operation Traverse in the class FilteredListTraverser can be modelled as a Map quantification with an Expression named ProcessItem and a Filter named TestItem. The Process Filters of the Booch's catalog of reusable software components in Ada [1]  are examples of quantifications. In [15], we find an example of the quantification pattern with his chunks of programming knowledge named plans [14]. Soloway proposes an introductory Lisp programming course structure and a taxonomy of programming problems relying on this concept.

Related Patterns

Template Method, Iterator, Strategy, Object Function.

Conclusions

---TBD

References

[1] G. Booch. Software Components With Ada: Structures, Tools and Subsystems. Bejamin-Cummings, 1987.
[2] J.M. Burgos, J.Galve, J. García, M. Sutil: An Approach to Algorithm Design by Patterns, Proceedings of the 3rd European Conference on Patterns Languages of Programming and Computing 1998 (EuroPLoP´98), 63-76.
[3] Burgos et al. Abstract Solution Design by Specification Refinement, Innovation and Technology  in Computer Science Education (ITICSE'2000) Helsinki, Finland  July 11-13, 2000 (accepted paper).
[4] Erich Gamma, Richard Helm, Ralph Johnson, John Vlissides. Design Patterns. Elements of reusable object-oriented software. Addison-Wesley, Reading, MA, 1995.
[5] The Standard Template Library URL: http://www.sgi.com/Technology/STL/ [5] P. Grogono, S.H.Nelson: Problem Solving and Computer Programming, Prentice-Hall, 1982.
[6] C. Morgan: Programming from Specifications, Prentice-Hall, 1994.
[7] D. A. Schmidt: A Return to Elegance: The Reapplication of Declarative Notations to Sofware Design. G. Gupta (Ed.): PADL’99, pp. 360-364,  Springer-Verlag, 1999.
[8] S. Thompson. Haskell: The Craft of Functional Programming. 2nd ed. Addison Wesley, 1999.
[9] T. Kuehne. A Functional Pattern System for Object-Oriented Design. (PhD) University of KaisersLutern. URL: http://www.agce.informatik.uni-kl.de/~kuehne
[10] Clancy, M.J. and Linn, M.C. The Case for Case Studies of Programming Problems. Communications of the ACM, March 1992, 3, 3, pp. 121-132.
[11] Gries, D. The Science of Programming. Springer-Verlag, Texts and Monographs in Computer Science, 1981.
[12] Levitin, A. Do We Teach the Right Algorithm Design Techniques?  SIGCSE Bulletin and Proceedings, March 1999, pp.179-183.
[13] Schmidt, D.R. Towards a classification approach to design. In Proceedings of the Fifth International Conference on Algebraic Methodology and Software Technology, AMAST’96 (1996), vol. LNCS 1101, Springer-Verlag, pp. 62-84.
[14] Soloway, E. Learning to Program = Learning to Construct Mechanisms and Explanations. Communications of the ACM, 29, 9 (Sept. 1986), pp. 850-858.
[15] Soloway, E. From Problems to Programs Via Plans: The Content and Structure of Knowledge for Introductory Lisp Programming. J. Educational Computing Research, vol. 1(2), 1985, pp. 157-172.