February 2001 and April 2011

- Constrained Constructor
- Concurrent Distinct Choices
- Incremental Solution
- Locally Defined Global Identifier
- Opaque Type
- Composite-Visitor-Interpreter
- Fused Generate and Test
- Call-by-reference
- Many-to-many
- Quantification
- Deep selection
- Non-determinism introduction and elimination

- Wikipedia Design Pattern page
- Ward Cunningham's Portland Pattern Repository
- FLP homepage
- Slides of talk
- Contact homepage

Constrained Constructor |

Intent Prevent invoking a constructor that might create invalid data Applicability A type is too general for a problem Structure Replace a call to a constructor with a call to a function with the same signature. The function checks the validity of the arguments and either invokes the constructor or fails Consequences Invalid instances of a type are not created

TheMissionaries and Cannibalspuzzle deals with 3 missionaries and 3 cannibals that cross forth and back a river on a boat. A state of the puzzle is likely defined by the following type:where the two integers define the number of missionaries and cannibals, respectively, on the initial bank of the river and the boolean tells whether the boat is on the initial bank.

data State = State Int Int Bool

Unfortunately, this representation allows the construction of states, e.g.,, that are inconsistent with the logic of the problem.State 5 -2 True

mission.curry

queens.curry

waterjug.curry

knight.curry

Concurrent Distinct Choices |

Intent Ensure that a mapping from indices to values is injective Applicability Index-value pairs are computed concurrently Structure A valueof the problem is used as anindexin the representation of the mapping (the roles are reversed). Initially, the values in the representation of the mapping are free variables. During the computation, the variable at a given index of the representation is bound to a token which is unique for that indexConsequences The index-value relation is an injective mapping

Acryptarithmetic puzzlepresents an arithmetic computation in which the digits are replaced by letters. The problem is to find a correspondence from letters to digits that satisfies the computation. For example:A solution is an injective mapping representing the correspondence from letters to digits. In an efficient implementation, the equations for the units, tens, hundreds, etc., residuate in no predefined order and are computed concurrently.

SEND + MORE = MONEY

9567 + 1085 = 10652

send_more.curry

queens.curry

Variations of this pattern and more application can be found here.

Incremental Solution |

Intent Compute the solutions of a problem incrementally Applicability A solution consists of a sequence of steps Structure Compute a solution of a problem from an initial partial solution that contains no steps. Non-deterministically extend the partial solution step by step until the solution is complete Consequences Avoid the explicit representation of the search space

The solutions of many popular puzzles and common problems can be modeled as sequences of steps. For example, the solution of thestagecoachproblem, which consists in finding a route between two cities in a network of connections, is a sequence of legs; the solution of the N-queens puzzle is a sequence of queen placements on the board; the solution of the missionaries and cannibals puzzles is a sequence of river crossing, etc.

inc_search.curry

mission.curry

queens.curry

stagecoach.curry

waterjug.curry

knight.curry

Locally Defined Global Identifier |

Intent Ensure that a locally defined identifier is globally distinct Applicability A global identifier is declared in a local scope Structure Globally distinct identifiers are declared as local unbound variables possibly to be bound later Consequences Local identifiers are globally distinct

A graphical user interface is assembled from components. Some component, e.g., a slidebar, must refer to some other component, e.g., a textfield, which is not defined in the same scope.

This and other similar problems, e.g., dynamically generated HTML pages, are abstracted by the composition of graphs independently defined. A graph may need to refer to a node of another graph which is defined by a local identifier, but must be unique among all the graphs of a composition.

Graph.curry (library)

examples.curry (examples of use of the library)

thompson.curry (NFA construction for accepting regular expressions)

Variations of this pattern and more application can be found here.

Opaque Type |

Intent Ensure that the values of a public type are private Applicability The values of a type must be internally/automatically computed by an application Structure Use only unbound variables to define instances of a type. Enforce this policy by wrapping the values with a private constructor Consequences Literal values of a type are not accessible to the programmer

Some data structures express the relations between elements that are not expressive or interesting by themselves. For example, in a graphical user interface the name of a textfield is interesting only because a slidebar must refer to it. A similar situation occurs in HTML documents. A generalization of this situation is a graph where the nodes must be defined only to define the edges. In these situations it is more general and flexible to avoid a specific representation of nodes as, e.g., integers or strings.

Graph.curry (library)

examples.curry (examples of use of the library)

thompson.curry (NFA construction for accepting regular expressions)

Composite-Visitor-Interpreter |

These patterns are popular and important in Object Oriented programming languages. Declarative languages trivialize these patterns. For example, a hierarchy of classes in an OO language is replaced by a single type declaration in a functional language, and a visitor is replaced by a single function that uses pattern matching.

Below are the links to some simple programs that show how the features of a declarative language simplify the use of these patterns.

Expr.curry

Statement.curry

Store.curry

Tests.curry

Fused Generate and Test |

Intent Merge together the generator and tester of a search problem Applicability Search problems implemented with a generate-and-test architecture Structure Generate the elements of a search space with a function that simultaneously tests, as much as possible for the problem at hand, the generated elements. Consequences Elements of the search space are not passed from generator to tester. Sometimes, the code is simpler, clearer and more efficient. Partially constructed elements can be eliminated before completion.

Many search problems are solved by generating each element of a search space an testing whether the element is a goal. Lazy evaluation is a useful or essential for the efficiency of execution. However, using strict equality may decrease the effectiveness of lazy evaluation. Merging together generator and tester may improve the efficiency. In particular it reduces the control needed to pass elements from the generator to the tester and it may allow earlier testing and consequently pruning of the search space.

24.curry

queens.curry

Call-by-reference |

Intent Return multiple values from a function without defining a containing structure Applicability A function must return more than one value Structure An argument passed to a function is an unbound variable. The function binds a value to this variable before returning. Consequences Avoid constructing a structure to hold multiple values

When a function must returns multiple values, a standard technique is to return a structure that holds all the values to be returned. For example, if functionfmust return both a value of typeAand a value of typeB, the return type could be(A,B), a pair with components of typeAandB, respectively. The client offextracts the components of the returned structure and uses them as appropriate. Although straightforward, this approach quickly becomes tedious and produces longer and less readable code. This pattern, instead, suggests to pass unbound variables to the function which both returns a value and binds other values to the unbound variables.

state.curry

maybe.curry

bitexpr.curry

Many-to-many |

Intent Encode a many-to-many relation with a single simple function Applicability A relation is computed in both directions Structure A non-deterministic function defines a one-to-many relation; a functional pattern defines the inverse relation. Consequences Avoid structures to define a relation

We consider a many-to-many relationRbetween two setsAandB. Some element ofAis related to distinct elements ofBand, vice versa, distinct elements ofAare related to some element ofB. In a declarative program, such a relation is typically abstracted by a functionffromAto subsets ofB, such thatb ∈ f(a)iffa R b. We will call this function thecore functionof the relation. Relations are dual to graphs and, accordingly, the core function can be defined, e.g., by an adjacency list. The relationRimplicitly defines an inverse relation which, when appropriate, is encoded in the program by a function fromBto subsets ofA, the core function of the inverse relation.In this pattern, the core function is encoded as a non-deterministic function that maps every

a ∈ Ato everyb ∈ Bsuch thata R b. The rest of the abstraction is obtained nearly automatically using standard functional logic features and libraries. In particular, the core function of the inverse relation, when needed, is automatically obtained through a functional pattern. The sets of elements related to a given element are automatically obtained using the set functions of the core function.

blood.curry

call_funct.curry

Quantification |

Intent Encode first-order logic formula in programs Applicability Problems specified in a first-order logic language Structure Apply " there exists" and "for all" library functions.Consequences Programs are encoded specifications

First-order logic is a common and powerful language for the specification of problems. The ability to execute even some approximation of this language enables us to directly translate many specifications into programs. A consequence of this approach is that the logic of the resulting program is correct by definition and the code is obtained with very little effort. The main hurdle is existential quantification, since specifications of this kind are often not constructive. However, narrowing, which is the most characterizing feature of functional logic languages, supports this approach.Narrowing evaluates expressions, such as a constrains, containing free variables. The evaluation computes some instantiations of the variables that lead to the value of the expression, e.g., the satisfaction of the constrain. Hence, it solves the problem of existential quantification.

Universal quantification is more straightforward. Mapping and/or folding operations on sets are sufficient to verify whether all the elements of the set satisfy some condition. In particular, set functions can be a convenient mean to compute the sets required by an abstraction.

mapcolor.curry

min.curry

queens.curry

itinerary.curry

Deep selection |

Intent Pattern matching at arbitrary depth in recursive types Applicability Select an element with given properties in a structure Structure Combine a type generator with a functional pattern. Consequences Separate structure traversal from pattern matching

Pattern matching allows us to easily retrieve the components of a data structure such as a tuple. Recursively defined types, such as lists and trees, have components at arbitrary depths that cannot be selected by pattern matching because pattern matching selects components only at predetermined positions. For recursively defined types, the selection of some element with a given property in a data structure typically requires code for the traversal of the structure which is intertwined with the code for using the element. The combination of functional patterns with type generators allows us to select elements arbitrarily nested in a structure in a pattern matching-like fashion without explicit traversal of the structure and mingling of different functionalities of a problem.

addresses.curry

exp.curry

exp_withposition.curry

Non-determinism introduction and elimination |

Intent Use different algorithms for the same problem Applicability Some algorithm is either too slow or it may be incorrect Structure Either replace non-deterministic code with deterministic one or vice versa. Consequences Improve speed or verify correctness of algorithms

Specifications of problems are often non-deterministic because in many cases non-determinism defines the desired results of a computation more easily than by other means. Thus, it is not unusual for programmers to initially code non-deterministic programs even for deterministic problems because this approach produces correct programs quickly. We call aprototypical implementationthis direct encoding of a specification. For some problems, prototypical implementations are not as efficient as an application requires. In these cases, the prototypical implementation, often non-deterministic, should be replaced by a more efficient implementation, often deterministic, that produces the same result. We call the latterproduction implementation. The investment that went into the prototypical implementation is not wasted because the specification of the problem is better understood and it has been tested through the input/output behavior of the prototypical implementation and possibly debugged and corrected. Furthermore, the prototypical implementation can be used as a testing oracle of the production implementation. Testing can be largely automated, which both reduces effort and improves reliability.

min.curry

test.curry

uniq.curry

Work supported in part by the NSF grants INT-9981317 and CCR-0110496 |
Contact antoy@cs.pdx.edu Last updated: Mon Apr 18 09:03:37 PDT 2011 |