Switches for Making Prolog a more Dynamic Programming Language

Appeared in Volume 7/1, February 1994

Keywords: coding techniques.

Zygmunt Vetulani

The technique described here makes it possible to write Prolog programs which modify themselves at run time in a simple manner. The modification may be independent of the external data (hence deterministic) or it may depend on data supplied to the system during the execution (nondeterministic modification). In both cases two situations are possible: 1) the declarative meaning of the program changes, or 2) the declarative meaning of the program does not change. From the programmer point of view, any of these situations may be desirable.

A typical self-modifying program dynamically changes the order of clauses which define a procedure. If the execution of the program is considered as a process of hypothesis verification, then such a rearrangement may cause some (sub)hypothesis, initially taken into account at a late stage, now to be verified at the very beginning. In the best case, with additional information provided by a "oracle" that knows which procedure variants are successful, linear efficiency might be obtained for an algorithm which is basically exponential.

The information obtained from the "oracle" is normally used to rearrange clauses by means of asserts and retracts.What we propose here is a method of obtaining the dynamic effect without changing the order of clauses in Prolog predicates. Instead, we add an additional predicate, called switch/1 whose role is to control the order in which clauses are selected (activated) by the goal reduction algorithm (the Prolog interpreter).

Let us consider the following problem which may be decomposed into a sequence of several subproblems: subproblem-1, subproblem-2, etc. Let us assume that subproblem-1 consists of a verification of some hypothesis and that the hypothesis has several variants: variant-1, variant-2, variant-3, variant-4, etc. This situation can be encoded in Prolog as follows:

problem :- subproblem-1, subproblem-2, ...

subproblem-1 :- variant(1).
subproblem-1 :- variant(2).
subproblem-1 :- variant(3).
subproblem-1 :- variant(4).

variant(1) :- ... .
variant(2) :- ... .
variant(3) :- ... .
variant(4) :- ... .

In order to solve "?-problem", first subproblem-1 will be processed, so that the "variants" will be tried in the order 1,2,3,4,... (through backtracking). We can redefine subproblem-1 to make this execution order more flexible. To do this we introduce a new predicate which plays the role of a switch.

subproblem-1 :- switch(N),variant(N).

We may set the switch to force a required execution order of variants. For example, defining switch/1 as follows:

switch(2).
switch(1).
switch(4).

will result in the execution order 2, 1, 4, with version 3 of the hypothesis being omitted (instead of 1, 2, 3, 4). Alternatively, asserting switch(_) would not affect the execution order at all. In practice, the switch can be used to give the highest priority to the most probable variant.

Applications

We have used the switch technique in a parser for Polish which is part of a natural language question answering system (POLINT, an interface to the EXPAERT system [2]). The basic top down depth first parsing algorithm of Prolog analyzes the sentence by generating and verifying hypothesis about its syntax. The parsing is preceded by morphological preanalysis combined with dictionary consultation. This plays the role of "oracle" with respect to the main algorithms and permits the generation of hypotheses about the structure of the sentence (e.g. the number of arguments and their positioning with respect to the predicate). Such predictions permit us to set switches to select hypothesis in an appropriate order. Recent experiments [1] show the efficiency of this technique applied to highly inflectional languages (such as Polish).

References

1. Vetulani, Z.; Martinek, J.; Bartoszek, J., Tronowski, P.; Zawiasa-Staniszewska, K.: Man-machine communication in the system EXPAERT, in: Darski, J. Vetulani, Z. (eds.), Sprache-Kommunikation-Informatik. Akten des 26 Linguistischen Kolloquiums, Poznan 1991. (Linguistische Arbeiten 294), pp. 219-224,

2. Jassem, K., Vetulani, Z.: Linguistically Based Optimisation of a TDDF Parsing Algorithm of the NL system POLINT, (to appear) in: Dieter W. Halwachs (ed.), Akten des 28 Linguistischen Kolloquiums, Graz, 1993

Zygmunt Vetulani
Adam Mickiewicz Univ., Poznan, Poland
Email: vetulani@plpuam11.amu.edu.pl
or 
vetulani%plpuam11.bitnet@searn.sunet.se