6.1 Overview

We show the application of this pattern in one example. Consider a simple type for representing arithmetic expressions:

For example, the expression $x+1$ is encoded as . Suppose that we want to match an expression with some property, e.g., the expression is a variable, regardless of whether it occurs. First, we define a function, withSub, that takes an expression $t$ and non-deterministically generates some expression with $t$ as subexpression.

For example, if , then withSub $t$ evaluates, among other possibilities, to an expression matching the expression $e$ discussed earlier. Thus, using functional patterns, Sect. 3.5.5, we can pattern match a subexpression $t$ anywhere in an expression $e$.

To see this in action, consider the function varOf defined below. This function takes an expression $e$ and returns the identifier of a variable occurring anywhere in $e$. With ordinary pattern matching, only a variable at a fixed position, e.g., the root or the left argument of an expression, can be matched. With withSub we match any variable anywhere:

For example, the set of the identifiers of all the variables of occurring in an expression $e$ is simply obtained with the set function of varOf, i.e., varOf$\mathrm{\_}\mathtt{}𝒮$ $e$ [Browse Program][Download Program].

The signature of a functional logic program is partitioned into defined operations and data constructors. They differ in that operations manipulate data by means of rewrite rules, whereas constructors create data and have no associated rewrite rules. Therefore, a constructor symbol cannot perform any checks on the arguments to which it is applied. If a constructor is invoked with arguments of the correct types, but inappropriate values, conceptually invalid data is created. We use an example to clarify this point.

The Missionaries and Cannibals puzzle is stated as follows. Three missionaries and three cannibals want to cross a river with a boat that holds up to two people. Furthermore, the missionaries, if any, on either bank of the river cannot be outnumbered by the cannibals (otherwise, as the intuition hints, they would be eaten by the cannibals).

A state of this puzzle is represented by the number of missionaries and cannibals and the presence of the boat on an arbitrarily chosen bank of the river, by convention the initial one:

For example, with suitable conventions, (State 3 3 True) represents the initial state. The simplicity of this representation has the drawback that invalid states, e.g., those with more than 6 people, can be created as well. Unless complex and possibly inefficient types for the state are defined, it is not possible to avoid the creation of invalid states using constructors alone.

The Constrained Constructor pattern avoids the creation of invalid states. The programmer invokes the constructor indirectly through the following function:

Function makeState invokes the constructor only after checking that only states that are consistent with the physical conditions of the puzzle and are safe for the missionaries will be created. For example, (State 2 1 -) is not safe since on one bank of the river the cannibals outnumber the missionaries and therefore should not be created. In fact, the call makeState 2 1 _ fails because the rule’s condition is not satisfied. In a suitable non-deterministic program, this failure can be simply and silently ignored.

Operation makeState eases the definition of an operation, say move, to move people and boat across the river:

since “undesirable” states are never produced [Browse Program][Download Program].

Specifications are often non-deterministic because in many cases non-determinism defines the desired results of a computation more easily than by other means. We have seen this practice in several previous examples. Thus, it is not unusual for programmers to initially code a non-deterministic prototype even for deterministic problems because this approach produces correct programs quickly.

In some cases, a non-deterministic program is not efficient enough to solve a problem of interesting size. Reducing the non-determinism of the program, e.g., by taking advantage of domain knowledge, may improve the efficiency of execution. Below, is an example. The “blocks world” [24] consists of 3 possibly empty piles, labeled $p$, $q$ and $r$, of unique blocks labeled A, B, C, etc. “Start” and “Final” below are two examples of blocks worlds from [10].

A blocks world “problem” consists of two worlds, like Start and Final above. Its solution consists in the moves that produce the second world from the first one. A “move” transfers the block on top of a pile to the top of another pile. No other blocks are affected by the move. Below is an example of a solution from Start to Final.

In our prototype, blocks are encoded as an enumerated type. A world is three stacks of blocks. A solution is a sequence of worlds. A problem is a pair of words.

We define two functions to solve a blocks world problem. Function move moves the block at the top of a pile to the top of another different pile. Both the origin and the destination pile of a move are non-deterministically selected. Function extend takes a sequence of blocks world states, that we call a trace, that when reversed satisfies the following invariant: (1) the first block is the start state, (2) any other block is obtained from the previous one by a move, and (3) no element, with the possible exception of the last one, is repeated.

Function extend performs the following tests and corresponding actions on the last element, $t$, of the trace (the first element actually, since the trace is reversed): (1) if $t$ is the final world, the trace is a solution, (2) if $t$ is repeated in the trace, the computation is aborted, otherwise (3) the trace is extended with a move from $t$:

The PAKCS interpreter produces 40 solutions of simpleProblem in which the number of moves ranges from 3 to 10, in a fraction of a second. However, it does not produce any solution of difficultProblem in over an hour. We are guessing that the reason is that the non-determinism of move is too “unfocused.” [Browse Program][Download Program].

We reduce the non-determinism of the previous program using two strategies. We favor moves that put a block in its final place and by we avoid moves that take a block away from its final place. Function moveToGoal is quite similar to function move of the previous program, but it moves a block only if the block ends up into its final place. If such a move is not available, the move is computed by function noMoveFromGoal. This function is again quite similar to move, but a block that is already in its final place is never moved.

Observe that noMoveFromGoal would fail if called on the final state of a blocks world problem. An invariant of this and the previous program is that no move is attempted on any final state.

The PAKCS interpreter produces 6 solutions of simpleProblem in which the number of moves ranges from 3 to 7, in a fraction of a second. It also produces a solution of difficultProblem in a few seconds, but this solution is 170 moves long. There exists a solution of this problem which is only 12 moves long. [Browse Program][Download Program].

The previous example and discussion shows that reducing the non-determinism of a program may increase its efficiency. Often, it also increases its complexity. This patter comes in a dual form. In some situations, e.g., if a program is producing unexpected results, it may be useful to increase the program non-determinism. This change will likely decrease the program efficiency, but increase its simplicity. With a simpler program it may be easier to assess or verify whether a result of a computation is expected.