Previous Page
An exchange format
Next Page

ELAN - Interpreter

The interpreter takes a well-formed program and a well-formed query (both checked by the parser) and applies the rules and strategies defined in the program to the query. In order to find which rules can apply, the selection is guided by the top symbol of the rules: only those rules whose left-hand side has the same top symbol as the term to be reduced are selected. They are then tried in the order given in the program. Another kind of choices arbitrarily made by the interpreter is made for the strategy dc(S1,...,Sn) that should select randomly a non-failing strategy among S1,...,Sn. In practice, the interpreter selects the first one, so implements dcand firstin the same way. Note however that there exists a version of ELAN which concurrently executes the n strategies and selects the first one which terminates without failure [32].

Once a set of rules is selected, a many-to-one matching algorithm is applied. When associative and commutative (AC for short) operators are involved, an external one-to-one AC-matching algorithm described by S. Eker (in Computer Journal, 38(5):381-399, 1995. Associative-Commutative matching via bipartite graph matching) is called. This algorithm is not fully integrated in the interpreter, so data structure conversions are required and lower the efficiency of the AC-matching, already quite complex. Once a match is found, local evaluations are performed and if all succeed, the result term is built, taking advantage of the right-hand side of the rule and of term sharing.