A WAM IMPLEMENTATION FOR FLEXIBLE QUERY ANSWERING^{1}

Pascual Julián-Iranzo Department of Information Technologies and Systems, University of Castilla-La Mancha. email: Pascual.Julian@uclm.es

Clemente Rubio-Manzano Department of Information Technologies and Systems, University of Castilla-La Mancha. email: Clemente.Rubio@uclm.es

ABSTRACT In [7] Maria I. Sessa extended the SLD resolution principle with the ability of performing approximate reasoning and flexible query answering. The operational mechanism of similarity-based SLD resolution can be used as the basis for a new logic language that allows to manage uncertain and imprecise information in a declarative framework, hence its importance. Similarity-based SLD resolution can be seen as an extension of the classical SLD resolution procedure where the syntactic unification algorithm has been replaced by a fuzzy unification algorithm.

In this paper we address the problem of adapting the implementation of a WAM to incorporate fuzzy unification. As a result, we obtain a Prolog implementation based on similarity relations that we call S-Prolog. To the best of our knowledge this is the first WAM implementation that supports similarity-based SLD resolution.

KEY WORDS Fuzzy Logic and Systems, Logic Programming, Fuzzy Prolog, Unification by Similarity, Warren Abstract Machine.

1 Introduction

Fuzzy Logic Programming integrates fuzzy logic and pure logic programming [3], in order to provide these languages with the ability of dealing with uncertainty and approximated reasoning. One of the main advantages of this combination is the construction of programming languages that allow us to deal with imprecise information by using declarative techniques. It is important to say that there is no common method for introducing fuzzy concepts into logic programming. In this paper we follow the conceptual approach introduced in [7] where the notion of “approximation” is managed at a syntactic level by means of similarity relations. A similarity relation is an extension of the crisp notion of equivalence relation and it can be useful in any context where the concept of equality must be weakened. In [7] a new modified version of the SLD resolution procedure, named similarity-based SLD, is defined. Roughly speaking the similarity-based SLD resolution principle works as it is shown by the following example (adapted from [7]).

Example 1 Assume a database storing information on books, including readers preferences and some subjective information concerning the similarity between some syntactic entities. Then it is possible to perform an inference reasoning step where the antecedent of a conditional formula is allowed to match with some premise only approximately.

if x is a mystery book then x is a good one;

                                                       dracula is a horror book;

horror is similar to mystery with degree 0.9 dracula is a good book with degree 0.9

Since horror is similar to mystery with a certainty/truth degree of 0.9, also the conclusion will be affected by the similarity degree assigned to the relation be-

                                                    tween horror and mystery.

In this paper we are interested in the implementation of a fuzzy logic language that follows this inference scheme. More precisely, our goal is to incorporate the Sessa’s similarity-based SLD resolution principle into the core of a Warren Abstract Machine (WAM) [8]. As a result, we obtain a Prolog implementation based on similarity relations that we call S-Prolog. The WAM is a virtual computer that aids in the compilation and implementation of the Prolog programming language and offers techniques for compiling symbolic languages that can be generalized beyond Prolog. A tutorial reconstruction for the WAM can be found in [1].

A prototype implementation of the Similarity WAM Machine can be found in the URL address

                                                                 http://www.inf-cr.uclm.es/www/pjulian/swam.html.

In the following, we assume familiarity with the theory and practice of logic programming [2].

2 Similarity Relations and Unification by Similarity

A similarity relation on a set U is a fuzzy binary relation on U × U, that is, a mapping R : U × U → [0, 1], holding the following properties: i) (Reflexive) R(x, x) = 1 for any x ∈ U; ii) (Symmetric) R(x, y) = R(y, x) for any x, y ∈ U; iii) (Transitive) R(x, z) ≥ R(x, y)△R(y, z) for any x, y, z ∈ U; where the operator ‘△’ is an arbitrary t-norm.

1This work has been partially supported by the EU, under FEDER, and the Spanish Science and Education Ministry (MEC) under grant TIN 2004-07943-C04-03.

In [6] when the operator △ = ∧ (that is, it is the minimum of two elements), similarity relations are called fuzzy equivalence relations. Following [7], in the sequel, we restrict ourself to fuzzy equivalence relations on a syntactic domain.

Usually, in classical Logic Programming, different syntactic symbols represent distinct information. This restriction can be relaxed by introducing a similarity relation R on the alphabet of a first order language, allowing R to provide a possible non-zero value for function/predicate symbols with the same arity, whereas it is the identity relation for variables. The similarity relation R on the alphabet of a first order language can be extended to terms and atomic formulas by structural induction in the usual way: Let P and Q be metavariables representing two n-ary function symbols or two n-ary predicate symbols and let t_{1}, …, t_{n}, s_{1}, …, s_{n} be terms. Then, R(P (t_{1}, …, t_{n}), Q(s_{1}, …, s_{n})) = R(P, Q) ∧ (⋀_{i=1}^{n} R(t_{i}, s_{i})).

In presence of similarity relations on syntactic domains, it is possible to define an extended notion of a more general unifier of two expressions^{1}. The weak unification algorithm introduced by [7] is an extension of Martelli and Montanari’s unification algorithm for syntactic unification [4] and it is based in the following observation: The task of obtaining a weak more general unifier (w.m.g.u.) of two expressions E_{1} = f(t_{1}, …, t_{n}) and E_{2} = g(s_{1}, …, s_{n}) with R(f, g) = α > 0, where R is a similarity relation, is not a failure but it is equivalent to solve the (initial) set of equations G = {t_{1} ∼ s_{1}, …, t_{n} ∼ s_{n}} coupled with the similarity degree α. Here, the symbol “∼” represents the possibility that the arguments in E_{1} and E_{2} be equals by similarity.

The weak unification algorithm can be formalized as a transition system based on a similarity-based unification relation “⇒”. The unification of the expressions E_{1} and E_{2} is obtained by a state transformation sequence starting from an initial state ⟨G, id, α⟩, where id is the identity substitution:

⟨G, id, α⟩ ⇒ ⟨G1, θ_{1}, α_{1}⟩ ⇒ … ⇒ ⟨G_{n}, θ_{n}, α_{n}⟩.

When the final state ⟨G_{n}, θ_{n}, α_{n}⟩, with G_{n} = ∅, is reached (i.e., the equations in the initial state have been solved), the expressions E_{1} and E_{2} are unifiable by similarity with w.m.g.u. θ_{n} and unification degree α_{n}. Therefore, the final state ⟨∅, θ_{n}, α_{n}⟩ signals out the unification success. On the other hand, when expressions E_{1} and E_{2} are not unifiable, the state transformation sequence ends with failure (i.e., G_{n} = F ail).

The similarity-based unification relation “⇒” is defined as the smallest relation derived by a set of transition rules that behave as in the classical unification algorithm, except for the rules:

Term decomposition by similarity:

\frac{⟨\{f(t_{1}, …, t_{n}) ∼ g(s_{1}, …, s_{n})\} ∪ E, θ, α⟩ , R(f, g) = β > 0}{⟨\{t_{1} ∼ s_{1}, …, t_{n} ∼ s_{n}\} ∪ E, θ, (α ∧ β)⟩}

                                                    Failure:

\frac{⟨\{f(t_{1}, …, t_{n}) ∼ g(s_{1}, …, s_{n})\} ∪ E, θ, α⟩ , R(f, g) = 0}{⟨F ail, θ, α⟩}

In the rules above, E denotes a set of (remaining) equational goals.

In general, the weak unification algorithm allows us to check if a set of expressions S = {E_{1} ∼ E′_{1}, …, E_{n} ∼ E′_{n}} is weak unifiable. The w.m.g.u. of the set S is denoted by wmgu(S).

3 Similarity-Based SLD Resolution

Let Π be a set of Horn clauses and R a similarity relation on the first order alphabet induced by Π. We define Weak SLD (WSLD) resolution as a transition system ⟨E, ⟹_{W SLD}⟩ where E is a set of triples ⟨G, θ, α⟩ (goal, substitution, approximation degree), that we call the state of a computation, and whose transition relation ⟹_{W SLD}⊆ (E × E) is the smallest relation which satisfies:

C = (A ←Q) < < Π,

σ = wmgu(A,A′) ≠ fail, λ = R(σ(A),σ(A′))

⟨(←A′,Q′), θ, α⟩ ⟹_{W SLD} ⟨← σ(Q, Q′), σ ∘ θ, λ ∧ α⟩

where Q, Q′ are conjunctions of atoms and the notation “C << Π” is representing that C is a standardized apart clause in Π.

A WSLD derivation for Π ∪ {G_{0}} is a sequence of steps

⟨G_{0}, id, 1⟩ ⟹_{W SLD} … ⟹_{W SLD} ⟨G_{n}, θ_{n}, λ_{n}⟩.

And a WSLD refutation is a WSLD derivation ⟨G_{0}, id, 1⟩ ⟹_{W SLD}^{∗} ⟨□, σ, λ⟩, where σ is a computed answer and λ is its approximation degree. Certainly, a WSLD refutation computes a family of answers, in the sense that, if σ = {x_{1}/t_{1}, …, x_{n}/t_{n}} then whatever substitution θ′ = {x_{1}/s_{1}, …, x_{n}/s_{n}}, holding that s_{i} ≡_{R,λ} t_{i} (i.e., R(s_{i}, t_{i}) ≥ λ), for any 1 ≤ i ≤ n, is also a computed answer with approximation degree λ.

4 S-Prolog: Syntax and Semantics

The language we call S-Prolog is an extension of the pure Prolog language with a similarity relation defined on a syntactic domain. Therefore, the syntax of the extended language is easy. It is just the Prolog syntax but enriched with a built-in symbol “∼” used for describing similarity relations by means of similarity equations of the form:

                                                          <symbol> ~ <symbol> = <similarity degree>

meaning that two constants, n-ary function symbols or nary predicate symbols are similar with a certain degree. More precisely, we use the built-in symbol “∼” as a compressed notation for the symmetric closure of an arbitrary fuzzy binary relation R (that is, a similarity equation a ∼ b = α can be understood in both directions: a is similar to b and b is similar to a with degree α). The user can supply an initial subset of similarity equations and then, the system generates a reflexive and transitive closure to obtain a similarity relation. Hence, a S-Prolog program is a sequence of Prolog facts and rules followed by a sequence of similarity equations.

1We mean by “expression” a first order term or an atomic formula.

Example 2 This S-Prolog program fragment specify features and preferences on books stored in a data base. The preferences are specified by means of similarity equations^{2}:

% FACTS
adventures(treasure_island).
adventures(the_call_of_the_wild).
mystery(murders_in_the_rue_morgue).
horror(dracula).
science_fiction(the_city_and_the_stars).
science_fiction(the_martian_chronicles).
% RULES
good(X) :- interesting(X).
% SIMILARITY EQUATIONS
% Direct connections
adventures ~ mystery = 0.5
adventures ~ science_fiction = 0.8
adventures ~ interesting = 0.9
mystery ~ horror = 0.9
mystery ~ science_fiction = 0.5
science_fiction ~ horror = 0.5
% Transitive connections
adventures ~ horror = 0.5
mystery ~ interesting = 0.5
interesting ~ horror = 0.5
science_fiction ~ interesting = 0.8

The operational semantics of S-Prolog conforms with the similarity-based SLD principle [7] as it is defined in Section 3. Therefore, S-Prolog computes answers as well as approximation degrees.

5 The Similarity WAM Machine

In this section we present the main features of the Similarity WAM machine (SWAM), a virtual machine for executing S-Prolog programs. As we shall show, the SWAM uses an operational mechanism that conforms the weak SLD principle.

The structure of the S-Prolog compiler has three main parts, being the SWAM machine the basis for the compiler implementation: i) given a source program, the Analyzer performs a syntactical analysis and, at the same time, it translates the source program into an internal representation; ii) the Adapter takes that internal representation and it obtains some auxiliary representations that facilitate the code generation task; iii) finally, the Code Generator produces the machine code associated to the source program. All these phases, except the one related with the Adapter, have been implemented following standard techniques described in [1].

Once the machine code is generated, it is stored in the Code Area, an addressable array of memory words. One or more memory words may contain a possibly labeled instruction consisting of an operation code followed by operands. Labels are symbolic entry points into the Code Area which are used by control instructions to alter the standard sequential execution order of machine instructions. Additionally, multi-labels are also used with other purposes, such as to guide some stages of the weak unification process (see below in the next section and Section 5.3). On the other hand, the similarity relation is stored into the Similarity Matrix memory area and its information is used:

i) at compilation time, by the Adapter (see Section 5.2). ii) at execution time, when it is necessary during the unification process.

In the sequel, we shall comment more deeply the main points where the SWAM design diverges from the standard WAM, but before doing that it is necessary to introduce a note about how syntactical unification of expressions is performed.

5.1 Standard versus weak unification

It is noteworthy that the syntactical unification algorithm is implemented into the WAM as a distributed procedure which includes two phases:

Ph 1 Unification of the predicate symbol rooting a (sub)goal and the heads of the clauses defining that predicate. This unification stage is immediate and produces a choice point. From the code generation point of view, it mainly produces the following set of machine instructions: try me else,

    retry me else and trust me (when the program

clauses are compiled).

Ph 2 Unification of the corresponding arguments of the (sub)goal and the clause heads being unified. From the code generation point of view, the visible effect is a set of machine instruc-

    tions: get structure, unify variable and

unify value (when the program clauses are compiled). However, in this phase, the argument unification is not tested immediately, but at execution time by specific code portions inside the get structure instruction and the procedure unify which is called by the unify value instruction.

Therefore, if we want to introduce weak unification into a WAM context, it is necessary to modify both phases of the distributed unification procedure above described.

Ph 1 This phase controls the “flexible” matching of predicate symbols during the unification process when programs are augmented with similarity relations. This is a critical phase, since it is not obvious at a first glance how to proceed. We see that it requires the introduction of a program transformation step, which transforms the original program into a set of “clauses” whose bodies contain information about the similarity degree between predicate symbols. The Adapter carry out the transformation and manages the transformed program in order to facilitate the code generation. Section 5.2 describes the main features of the transformation.

2In order to facilitate later discussions, we explicitly give the similarity equations that complete the transitive closure of the initial fuzzy binary relation.

Ph 2 The adaptation of this phase is easy. It only requires the modification of some portions of the machine instruction get structure and the procedure unify, in order to perform a “flexible” matching of function and constant symbols which is guided by the similarity equations.

Finally, note that, when unifying expressions in presence of similarity relations it is necessary to store, as a part of the computation state, the current computed approximation degree. To cover this task, we use a specific global register in the SWAM which works as an accumulator register. We call this, the AD register.

5.2 The Adapter and the first phase of the weak unification procedure

In a logic program, a predicate p is defined by the set of clauses whose head is rooted by p. However, in a logic program extended with a similarity relation, a clause defining the predicate p can also be considered as defining each predicate q which is similar to p. On the other hand, as it was commented, the structure of the WAM is designed to test a “crisp” matching of predicate symbols. Therefore, if we want a “flexible” matching of predicate symbols without forcing the structure of the WAM, given a clause defining a predicate p, we need to introduce a new clause for each predicate q which is similar to p. We do it in order to simulate a “flexible” matching with a “crisp” technique.

The following definition formalizes the program transformation performed by the Adapter. We need to introduce an extended language obtained by adding to the object language alphabet the elements of the lattice [0, 1] (of similarity degrees). Clauses in this extended language contain bodies with literals which are similarity degrees. We call these clauses ‘e-clauses’. Also e-clauses with an empty head are called ‘e-goals’.

Definition 1 Let Π be a logic program and R a similarity relation on the syntactic domain generated by Π. Let p(t_{1}, …, t_{n}) ← Q be a clause in Π defining the n-ary predicate p. Then, for each R(p, q) = α > 0 add to the transformed program Π′ the new e-clause q(t_{1}, …, t_{n}) ← α, Q. Hence, the transformed program Π′ = {q(t_{1}, …, t_{n}) ← α, Q | (p(t_{1}, …, t_{n}) ← Q) ∈ Π and R(p, q) = α > 0}.

Observe that, since R(p, p) = 1 for any symbol p, if p(t_{1}, …, t_{n}) ← Q is in the original program, the e-clause p(t_{1}, …, t_{n}) ← 1, Q will be in the transformed program. Thus we give an uniform treatment for all clauses in the transformed program.

We give an example reproducing the effect of the transformation on a program fragment.

Example 3 A fragment of the transformed program showing the clauses defining the predicate adventures:

                                                         adventures(treasure_island):-1.0.
                                                         adventures(the_call_of_the_wild):-1.0.
                                                         adventures(murders_in_the_rue_morge):-0.5.
                                                         adventures(dracula):-0.5.
                                                         adventures(the_city_and_the_stars):-0.8.
                                                         adventures(the_martian_chronicles):-0.8.

5.3 Compilation of S-Prolog Programs

The compilation of the transformed program to machine code is done using standard techniques. In essence, clauses of a transformed program are translated into the same machine instruction set a standard implementation would have produced. The only difference is that similarity degrees, in the body of transformed clauses, are “stored” in a multi-

                                                    label field of the try me else, retry me else and

trust me machine instructions. The values in the multilabel field will be used during the computation of the unification degree in a WSDL resolution step.

Example 4 The following shows the compiled code for the program fragment of Example 3:

                                                                 0  : adventures/1 [ 1.0 ] :try_me_else 3
                                                                 1  : get_structure treasure_island 0,1
                                                                 2  : proceed
                                                                 3  : [ 1.0 ] :retry_me_else 6
                                                                 4  : get_structure the_call_of_the_wild 0,1
                                                                 5  : proceed
                                                                 6  : [ 0.5 ] :retry_me_else 9
                                                                 7  : get_structure murders_in_the_rue_morge 0,1
                                                                 8  : proceed
                                                                 9  : [ 0.5 ] :retry_me_else 12
                                                                 10 : get_structure dracula/0,1
                                                                 11 : proceed
                                                                 12 : [ 0.8 ] :retry_me_else 15
                                                                 13 : get_structure the_city_and_the_stars 0,1
                                                                 14 : proceed
                                                                 15 : [ 0.8 ] :trust_me
                                                                 16 : get_structure the_martian_chronicles 0,1
                                                                 17 : proceed

In general, given an adapted program, defining a predicate p:

                                                         p :- 1.0, Q_1
                                                         p :- alpha_j, Q_j
                                                         .
                                                         .
                                                         p :- alpha_m, Q_m
                                                         p :- alpha_n, Q_n

where the alpha i are similarity degrees and the Q i are conjunction of atoms, it is translated into the following set of machine instructions:

Li  : adventures/1 [ 1.0 ] :try_me_else Lj
% code for the arguments in the
% head atom p
% code for the body atoms in Q_1
proceed
Lj  : [ alpha_j ] :retry_me_else Lk
% code for the arguments in the
% head atom p
% code for the body atoms in Q_j
proceed
Lk  :  . . .
.
.
Lm : [ alpha_m ] :retry_me_else Ln
% code for the arguments in the
% head atom p
% code for the body atoms in Q_m
proceed
Ln : [ alpha_n ] :trust_me
% code for the arguments in the
% head atom p
% code for the body atoms in Q_n
proceed

5.4 Specific machine instructions for approximation degree control

In this section we describe how the SWAM controls the computation of the approximation degree when a choice point is created. In order to accomplish this task properly, we need:

1. to introduce a global register, called the AD register, to store the approximation degree computed at each WSLD resolution step;

2. to modify the standard choice point frame ^{3} structure by adding a new field to save the value stored in the AD register, prior to the creation of a choice point; this is because, when the computation backtracks and the next clause in an alternative is taken, we need to restart the computation (of the approximation degree) at the point it was left before the former clause was try.

As the choice point frame structure has been modified, the machine instructions that work in combination with it need also to be modified. In the following we briefly comment the functionality of these instructions, specially, regarding with the control of the approximation degree.

The try me else machine instruction builds a new choice point frame on top of the stack, setting its fields according to the current context. Certainly, it stores the current value of the AD register.

When the computation backtracks, the retry me else instruction resets all the necessary informations from the current choice point frame. Specifically, the value which the AD register had, at the time the choice point frame was created, is restored. Then it is set as the minimum of its value and the similarity degree “stored” at the multi-label field of the retry me else instruction.

The trust me instruction behaves in a similar way as the retry me else instruction does. The only difference is that the former discards the current choice point frame after the context (including the AD register) have been restored.

Finally, note that, since we have altered the size of a choice point frame, by adding a new field to save the AD register, the machine instruction allocate must be slightly modified. This is because allocate builds a new environment frame on the top of the stack and the top of the stack is computed differently depending on whether an environment or choice point frame is the last pushed structure on the stack. On the other hand the machine instruction deallocate remains unchanged.

5.5 Specific machine instructions for argument weak unification

Before ending this section, we comment the main features of machine instructions involved in the process of argument unification.

    The get structure(f,n,A) machine instruc-

tion tests the similarity of constant and function symbols of terms in predicate arguments. More precisely, it acts as follows (we explain the cases directly related with the weak unification process): if the heap cell referenced by the argument register A contains a structure (a STR tag) pointing to a function symbol f with arity n we are in the classical case. This signals out a successful unification step where the unification degree remains unchanged. However, when the heap cell referenced by the argument register A is pointing to a function symbol which is not syntactically equal to f but is similar to f with degree alpha, the unification degree is recomputed (as the minimum of its previous value and alpha) and stored into the AD register. Otherwise, the unification process fails and the procedure backtrack is called.

Finally, the machine instruction unify value calls the procedure unify, which carries out the other part of the argument unification process. The procedure unify implements the weak unification algorithm defined in Section 2.

6 SWAM Operational Semantics

This section formally describes the operational semantics of the SWAM, which is an adaptation of the WSLD resolution rule aiming to preserve the architecture of a standard WAM.

In the remainder of this section we shall work inside the framework of the extended language built by e-clauses and e-goals. Π′ denotes a transformed program obtained by applying Definition 1 on a logic program Π equipped with a similarity relation R.

3A choice point frame is a data structure used to save the computation state, that is, all the information required to continue the computation upon backtracking.

Definition 2 We define the SWAM operational semantics as a transition system ⟨E, ⟹_{SW AM}⟩ where E is a set of triples ⟨G, θ, α⟩ (e-goal, substitution, approximation degree), and whose transition relation ⟹_{SW AM}⊆ (E × E) is the smallest relation which satisfies:

Rule 1:

\frac{β ∈ (0, 1]}{⟨(←β,Q′), θ, α⟩ ⟹_{SW AM} ⟨← σ(Q′), θ, β ∧ α⟩}

Rule 2:

(p(t_{1}, …, t_{n}) ←Q) < < Π′,

σ = wmgu(p(t_{1}, …, t_{n}),p(s_{1}, …, s_{n})) ≠ fail,

λ_{i} = ν_{R}(σ(t_{i}),σ(s_{i}))
⟨(←p(s_{1}, …, s_{n}),Q′), θ, α⟩

⟹_{SW AM} ⟨← σ(Q, Q′), σ ∘ θ, (⋀_{i=1}^{n} λ_{i}) ∧ α⟩

where Q, Q′ are conjunctions of atoms.

The following proposition establishes the semantic equivalence between the WSLD rule and the operational mechanism of Definition 2 and therefore the correctness of our implementation.

Proposition 1 Given a logic program Π with a similarity relation R, let Π′ be the transformed program obtained by applying Definition 1. There exists a derivation D = (⟨(← Q′_{0}), θ_{0}, α_{0}⟩ ⟹_{W SLD}^{∗} ⟨← Q′_{n}, θ_{n}, α_{n}⟩) in Π, if and only if there exists a derivation D′ = (⟨(← Q′_{0}), θ_{0}, α_{0}⟩ ⟹_{SW AM}^{∗} ⟨← Q′_{n}, θ_{n}, α_{n}⟩) in Π′, which computes the same state.

Proof. By induction on the length of the derivations. □

Although derivations in Π′ have more steps than equivalent derivations in Π, observe that the unification effort is reduced when executing a goal in the transformed program Π′. Hence, the SWAM operational mechanism is more efficient than a naive, direct implementation of the WSLD resolution rule.

7 Conclusions and Future Work

In this paper we have investigated how to incorporate the weak unification algorithm of [7] into the WAM, leading to a system well suited to be used for approximate reasoning and flexible query answering. We have presented the technical details that allow us to solve this problem:

1. We have designed a new pre-compilation phase, called the Adapter, which introduces some adaptations into the source code to facilitate the translation task. Also, the Adapter translates the original program into a transformed program, with explicit information about the similarity degree of predicates, that helps us to manage similarity relations properly.

2. We have appropriately modified some machine instructions to carry out the weak unification pro-

                                                       cess. Mainly: try me else, retry me else,
                                                       trust me, get structure and the procedure

unify. A global register, the AD register, stores the result of computing the current approximation degree step by step.

As a result, we obtain a Prolog implementation based on similarity relations that we call S-Prolog. To the best of our knowledge this is the first WAM implementation that supports similarity-based SLD resolution.

At the present time, the SWAM is a prototype implementation useful to essay new compilation techniques. We have introduced algorithms to manage similarity relations, although this was not an objective of this work and we did not present them in this paper. However, the treatment of similarity relations is rather naive and it is necessary to implement more efficient algorithms to solve the transitive closure problem, what is left as a future work. Also we want to study how to combine, in our setting, the WSLD resolution rule with a concrete instance of the multi-adjoint logic programming framework described in [5].

References

[1] H. Aït-Kaci. Warren’s Abstract Machine: A Tutorial Reconstruction. The MIT Press, Cambridge, MA, 1991.

[2] K. R. Apt. From Logic Programming to Prolog. Prentice Hall, Englewood Cliffs, NJ, 1997.

[3] J.W. Lloyd. Foundations of Logic Programming. Springer-Verlag, Berlin, 1987. Second edition.

[4] A. Martelli and U. Montanari. An Efficient Unification Algorithm. ACM Transactions on Programming Languages and Systems, 4:258–282, 1982.

[5] J. Medina, M. Ojeda-Aciego, and P. Vojtáš. Similaritybased unification: a multi-adjoint approach. Fuzzy Sets and Systems, 146(1):43–62, 2004.

[6] H.T. Nguyen and E.A. Walker. A First Course in Fuzzy Logic. Chapman & Hall/CRC, Boca Ratón, Florida, 2000.

[7] Maria I. Sessa. Approximate reasoning by similaritybased sld resolution. Theoretical Computer Science, 275(1-2):389–426, 2002.

[8] David H. D. Warren. An Abstract Prolog Instruction Set. Technical note 309, SRI International, Menlo Park, CA., October, 1983.