An Abstract Machine for the Execution of DeLP Programs

A. G. Stankevicius  A. J. García

Laboratorio de Investigación y Desarrollo en Inteligencia Artificial Departamento de Ciencias de la Computación Universidad Nacional del Sur Bahía Blanca - Buenos Aires - ARGENTINA

                  e-mail: {ags,ajg}@cs.uns.edu.ar

Abstract

Defeasible Logic Programming (DeLP) is a knowledge representation and reasoning formalism that by combining Logic Programming with Defeasible Argumentation is able to represent incomplete and potentially contradictory information.

Within the field of Logic Programming, most of the implementations of Prolog and its variants are based on an abstract machine defined by D. Warren (nowadays known as WAM, standing for Warren’s Abstract Machine), that sits between the program and the actual hardware executing it. This separation of concerns allows the developer to focus mainly on the aspects related to the language being implemented, and not on the distinctive characteristics of the available hardware.

In this paper we summarize how an abstract machine can also help in the context of DeLP, exploring the points of contact between WAM and a particular abstract machine defined for this theory called JAM.

Keywords: knowledge representation and reasoning, defeasible argumentation, abstract machines.

1 Motivations

In the past few years, research in Logic Programming has striven to capture nonmonotonic features, seeking to develop more powerful tools for knowledge representation and reasoning. Defeasible Logic Programming (DeLP) is one of those formalism, that by combining Logic Programming with Defeasible Argumentation is able to represent incomplete and potentially contradictory information. Ideas borrowed from Defeasible Argumentation [8] such as representing defeasible reasons as arguments or performing a full dialectical analysis before returning the answer of queries are carefully added to a knowledge representation language featuring Prolog-like rules.

Within the field of Logic Programming, most of the implementations of Prolog and its variants are based on an abstract machine defined by D. Warren [11] (nowadays known as WAM, standing for Warren’s Abstract Machine), that sits between the program and the actual hardware executing it. The possibility of setting aside secondary aspects of the compiler/interpreter design has compelled many developers to adopt this approach, making it the de-facto standard for implementing Prolog [1]. Moreover, the most efficient implementations seldom translate Prolog code directly into native code, taking advantage instead of an intermediary WAM-like abstract machine.

The situation is analogous in the context of DeLP: it would be useful to have an intermediary abstract machine sitting half way between a DeLP program and the hardware executing the actual queries. The work reported in [4] defined an abstract machine suitable for this language, which due to historical reasons was called Justification Abstract Machine, or JAM for short. Unfortunately, this abstract machine specifically designed for an earlier revision of the theory [2, 6] lacks the recent updates made to the syntax and semantics of the system in [3, 5].

In this paper we summarize how this abstract machine can be adapted to the context of the latest revision of the system [5], exploring the points of contact between WAM and JAM, and emphasizing the changes introduced to reflect this new semantics. It is structured as follows: the next section introduces the essential concepts of DeLP. Section 3, discusses the actual JAM operation, covering what aspects of the original JAM have been updated. Finally, Section 4 presents the conclusions reached in this work.

2 Defeasible Logic Programming

This section briefly introduces DeLP’s essentials following its most recent formulation [5], referring the reader looking for a comprehensive presentation to [3].

The DeLP language is defined in terms of three disjoint sets: facts, strict rules, and defeasible rules. Following the standard nomenclature, a literal L can either be a ground atom A or its strong negation ^{∼}A. In this context, a fact is just a literal; a strict rule is an ordered pair Head ← Body whose first component, Head, is a literal, and whose second component, Body, is a finite non-empty set of literals. A strict rule with head L_{0} and body {L_{1}, …, L_{n}} can also be written as L_{0} ← L_{1}, …, L_{n}. In a like manner, a defeasible rule is an ordered pair Head ← Body whose first component, Head, is a literal, and whose second component, Body, is a finite non-empty set of literals. In this case, a defeasible rule with head L_{0} and body {L_{1}, …, L_{n}} can also be written as L_{0} ^{−≺} L_{1}, …, L_{n}. Syntactically, the symbol ‘^{−≺}’ is all that distinguishes a defeasible rule from a strict one. This distinction is important because strict rules represent undisputed information while, in contrast, defeasible rules represent tentative information, good until we find one or more reasons challenging it.

In this formalism, the state of the world we are interested in modelling is captured as a Defeasible Logic Program (de.l.p), essentially a possibly infinite set of facts, strict rules and defeasible rules. In a given de.l.p P, the subset of facts and strict rules is referred as Π, and the subset of defeasible rules as Δ. When required, the de.l.p P can also be noted as (Π, Δ). Considering that the set Π is used to represent non-defeasible information, it must express certain internal coherence: it is assumed that the set Π of every de.l.p P is non-contradictory, in the sense that no two complementary literals (such as fly(fred) and^{∼}fly(fred)) be derivable at the same time. As usual, the literals that can be derived are obtained chaining as many rules as required:

Definition 1. (defeasible derivation) [5] Let P = (Π, Δ) be a de.l.p and L a ground literal. A defeasible derivation of L from P, noted P ^{|∼} L, consists of a finite sequence L_{1}, L_{2}, …, L_{n} = L of ground literals, where each L_{i}, 1 ≤ i ≤ n, satisfy that:

1. L_{i} is a fact, or

2. there exists a rule in P (either strict or defeasible) with a head L_{i} and body B_{1}, B_{2}, …, B_{k} such that every literal B_{j}, 1 ≤ j ≤ k, already appears in the sequence before L_{i}.

■

Note that although the set Π must be non-contradictory, the set Δ, and hence P itself (i.e., Π ∪ Δ), may be contradictory, as shown in the following example.

Example 1. The following is a valid de.l.p:

        Π = \{ \begin{matrix}bird(X) <- penguin(X). \\ ^{∼}fly(X) <- penguin(X). \\ bird(tweety). \\ bird(fred). \\ sick(fred). \\ penguin(pengo). \end{matrix} \}  Δ = \{ \begin{matrix}fly(X) -< bird(X). \\ ^{∼}fly(X) -< weak(X). \\ weak(X) -< sick(X). \end{matrix} \}

In the previous example, it is possible to defeasible derive both fly(fred) and ^{∼}fly(fred). However, out of the literals that can be defeasible derived in a given de.l.p, only those able to stand the dialectical analysis are entailed. This procedure is borrowed from the field of Defeasible Argumentation, where people speak in terms arguments instead of derivations. An argument is a tentative piece of reasoning supporting a given conclusion, formally defined in this theory as follows:

Definition 2. (argument structure) [5] Let P = (Π, Δ) be a de.l.p and h a literal. We say that ⟨A, h⟩ is an argument structure for h, if A is a set of defeasible rules of Δ, satisfying that:

1. there exists a defeasible derivation for h from Π ∪ A,

2. the set Π ∪ A is non-contradictory, and

3. A is minimal, in the sense that there is no proper subset A′ of A satisfying the previous conditions.

Also, an argument structure ⟨B, q⟩ is a sub-argument structure of ⟨A, h⟩ when B ⊆ A. ■

For instance, there exists defeasible derivations for fly(tweety) and fly(pengo) in the program shown in the Example 1. However, only fly(tweety) is backed up by an argument, since the set of ground rules used in the derivation of fly(pengo) are inconsistent with Π and therefore no valid argument structure sanctions it. Yet, in the same program is still possible to build the argument structures ⟨A, fly(fred)⟩ and ⟨B,^{∼}fly(fred)⟩, where:

\begin{matrix}A = \{fly(fred) ^{−≺} bird(fred)\} \\ B = \{^{∼}fly(fred) ^{−≺} weak(fred), weak(fred) ^{−≺} sick(fred)\} \end{matrix}

In DeLP, this kind of conflict arising between argument structures is settled defining under which conditions one argument structure has enough strength to warrant its conclusion. In short, a given literal is warranted if we are able to find an argument structure for that literal that remains undefeated.

Definition 3. (counter-argument) [5] We say that ⟨A_{1}, h_{1}⟩ counter-argues (also rebuts or attacks) ⟨A_{2}, h_{2}⟩ at the literal h, if and only if there exists a sub-argument structure ⟨A, h⟩ of ⟨A_{2}, h_{2}⟩ such that the set Π ∪ {h, h_{1}} is contradictory. ■

Definition 4. (defeater) [5] The argument structure ⟨A_{1}, h_{1}⟩ is a defeater for ⟨A_{2}, h_{2}⟩, if and only if there exists a subargument structure ⟨A, h⟩ of ⟨A_{2}, h_{2}⟩ such that ⟨A_{1}, h_{1}⟩ counter-argues ⟨A_{2}, h_{2}⟩ at h, and either:

• ⟨A_{1}, h_{1}⟩ is preferred^{1} over ⟨A, h⟩ (proper defeat), or

• ⟨A_{1}, h_{1}⟩ is unrelated by the preference criterion to ⟨A, h⟩ (blocking defeat)

■

Since defeaters are in turn argument structures, there may exists defeaters for the defeaters, and so on. This sequence of argument structures, each one defeating the previous one, is called argumentation line, in the sense that this exchange of reasons is actually exploring a given topic of the controversy.

Definition 5. (argumentation line) [5] Let P be a de.l.p and ⟨A_{0}, h_{0}⟩ an argument structure from P. An argumentation line for ⟨A_{0}, h_{0}⟩ is a sequence of argument structures from P, noted λ = [⟨A_{0}, h_{0}⟩, ⟨A_{1}, h_{1}⟩, ⟨A_{2}, h_{2}⟩, …], where each ⟨A_{i}, h_{i}⟩, i > 0, is a defeater of its predecessor ⟨A_{i−1}, h_{i−1}⟩. ■

As it has been shown elsewhere [7], not every exchange of counter-arguments actually constitutes a valid pattern of reasoning. For instance, circular argumentation is a particular case of fallacious reasoning which should be avoided. The occurrence of cycles and other undesired situations are prevented imposing the following conditions over the potential argumentation lines, where λ_{S} denotes the set of argument structures occupying even positions in the line λ, and λ_{I} the set of argument structures occupying its odd positions.

Definition 6. (acceptable argumentation line) [5] Let λ = [⟨A_{0}, h_{0}⟩, ⟨A_{1}, h_{1}⟩, …, ⟨A_{n}, h_{n}⟩] be an argumentation line. We say that λ is an acceptable argumentation line if and only if the following conditions are met:

• λ is a finite sequence.

• The set λ_{S} of argument structures supporting ⟨A_{0}, h_{0}⟩ and the set λ_{I} of argument structures interfering with ⟨A_{0}, h_{0}⟩ are concordant.^{2}

• No argument ⟨A_{k}, h_{k}⟩ in λ is a sub-argument structure of an ⟨A_{i}, h_{i}⟩ appearing before in λ (i.e., i < k).

• For all i such that the argument structure ⟨A_{i}, h_{i}⟩ is a blocking defeater for ⟨A_{i−1}, h_{i−1}⟩, whenever ⟨A_{i+1}, h_{i+1}⟩ exists, then ⟨A_{i+1}, h_{i+1}⟩ must be a proper defeater of ⟨A_{i}, h_{i}⟩.

■

1according to the preference criterion being applied (e.g., specificity).

2a set {⟨B_{1}, q_{1}⟩, ⟨B_{2}, q_{2}⟩, …, ⟨B_{m}, q_{m}⟩} is said to be concordant if Π ∪ B_{1} ∪ … ∪ B_{m} is non-contradictory.

Finally, the following definition captures the essence of the procedure that decides whether an argument structure warrants its conclusion. Once again, an argument structure becomes a warrant only if it is not defeated. This prompts for a complete dialectical analysis.

Definition 7. (dialectical tree) [5] Let ⟨A_{0}, h_{0}⟩ be an argument structure of a de.l.p P. A dialectical tree for ⟨A_{0}, h_{0}⟩, noted T_{⟨A_{0},h_{0}⟩}, is recursively defined as follows:

1. The root of the tree is labeled with ⟨A_{0}, h_{0}⟩.

2. Let N be an inner node of the tree labeled ⟨A_{n}, h_{n}⟩, and λ = [⟨A_{0}, h_{0}⟩, ⟨A_{1}, h_{1}⟩, …, ⟨A_{n}, h_{n}⟩] be the sequence of labels in the path from the root to N. Let ⟨B_{1}, q_{1}⟩, ⟨B_{2}, q_{2}⟩, …, ⟨B_{k}, q_{k}⟩ be all the defeaters of ⟨A_{n}, h_{n}⟩. For each defeater ⟨B_{i}, q_{i}⟩, 1 ≤ i ≤ k, such that the argumentation line λ′ = [⟨A_{0}, h_{0}⟩, ⟨A_{0}, h_{0}⟩, …, ⟨A_{n}, h_{n}⟩, ⟨B_{i}, q_{i}⟩] is acceptable, then the node N must have a child labeled ⟨B_{i}, q_{i}⟩. If there is no defeater for ⟨A_{n}, h_{n}⟩ or there is no ⟨B_{i}, q_{i}⟩ such that λ′ is acceptable, then N is a leaf.

■

The outcome of this tree-structured dialectical analysis (i.e., whether a certain argument structure is able to warrant its conclusion), can be easily determined following a simple recursive, bottom-up labeling:

Definition 8. (marking of a dialectical tree) [5] Let ⟨A, h⟩ be an argument structure and T_{⟨A,h⟩} its dialectical tree. The corresponding marked dialectical tree, noted T_{⟨A,h⟩}^{⋆}, is obtained marking every node in T_{⟨A,h⟩} as follows:

1. All the leaves in T_{⟨A,h⟩} are marked U in T_{⟨A,h⟩}^{⋆}.

2. Let ⟨B, q⟩ be an inner node of T_{⟨A,h⟩}. Then ⟨B, q⟩ should be marked U in T_{⟨A,h⟩}^{⋆} if and only if every child of ⟨B, q⟩ is marked D in T_{⟨A,h⟩}^{⋆}. Conversely, the node ⟨B, q⟩ should be marked D in T_{⟨A,h⟩}^{⋆} if and only if it has at least one child marked U.

■

Definition 9. (warrant) [5] Let ⟨A, h⟩ be an argument structure and T_{⟨A,h⟩}^{⋆} its associated marked dialectical tree. The literal h is warranted if and only if the root node of T_{⟨A,h⟩}^{⋆} is marked U. ■

Although the notion of warrant characterizes a set of literals that could be interpreted as the semantic of given de.l.p, this formalism takes into account more possibilities as answers to a given query −≺ h:

• YES, if h is warranted.

• NO, if \overline{h} is warranted, where \overline{h} denotes the complement of h with respect to strong negation.

• UNDECIDED, if neither h nor \overline{h} are warranted.

• UNKNOWN, if h is not present in the signature of the de.l.p under consideration.

On the one hand, the query fly(tweety) is warranted in the de.l.p of the Example 1, therefore it succeeds and gets a YES answer. On the other hand, the query fly(coco) is not present in the program signature, hence it does not succeeds and gets an UNKNOWN answer. In addition, the query fly(fred) gets an UNDECIDED answer (recall the competing arguments constructed above), and the query ^{∼}fly(tweety) gets a NO answer, since its complement is actually warranted.

After this succinct introduction to DeLP, the next section reviews the abstract machine proposed for executing its programs, upon which several implementations are based.

3 An Abstract Machine suitable for DeLP

In this section we review the particular abstract machine defined for DeLP called JAM [4], showing how it can be updated to the reflect the changes introduced along the DeLP evolution. Recall that the original JAM was specifically designed for an earlier revision of the formal theory, whose syntax and semantics is slightly different with respect to the formalism briefly stated in the previous section. To begin with, the changes introduced at the syntax level should be accounted for in the compiler, thus requiring no updates on the abstract machine. For instance, although JAM is able to deal with defeasible rules with an empty body (these rules are known as presumptions), the compiler should inform the user that no rule can have an empty body under the new syntax.

In contrast, the changes introduced at the semantic level do require further consideration. Since JAM was conceived as an extension of WAM, we first cover the conventional WAM operation, and then address the features only available in JAM. Notably, both execution models are based on the observation that any rule can be considered as a set of queries (its body) that, when satisfied, entails a new fact (its head). Under this conception, the whole operation of WAM, and its extension JAM, can be analyzed in terms of facts and queries.

Example 2. Consider the following Prolog program:

                            a(X) <- b(X), c(X).     b(q).
                            a(X) <- d(X).           c(r).

                                                    d(s).

This simple program can be translated into the WAM code shown in Figure 1, along with the translation of an arbitrary query ?- a(X)., whose code starts in the label ?:.

The execution model of WAM starts with the query that must be solved. The program counter register (P) holds the address of the instruction about to be executed. This register is incremented after its execution in order to refer the next instruction, unless the instruction just executed were a control transference. For instance, a control transference takes place when a call instruction gets executed: this instruction loads the address of the predicate to be called in the register P and also stores the return address in the continuation register (CP). The address where the code associated with each predicate begins is stored in a permanent symbol table.

The WAM instructions allocate and deallocate are responsible for storing and recovering environments from the STACK. These environments hold the local variables that should be preserved between predicate invocations. A distinctive feature in logic programming is the possibility of defining the same predicate through several independent rules. When a particular

     a/1:  try me else E1:      b/1:  just me            ?:  allocate 1
           allocate 1                allocate 0             put variable X_{1} A_{1}
           get variable X_{1} A_{1}  get constant q A_{1}  call a/1
           put value X_{1} A_{1}  deallocate             deallocate
            call b/1                  proceed                proceed
           put value X_{1} A_{1}  c/1:  just me
            call c/1                  allocate 0
           deallocate                get constant r A_{1}
            proceed                   deallocate
      E1:  just me                   proceed
            allocate 0          d/1:  just me
           get variable X_{1} A_{1}  allocate 0
           put value X_{1} A_{1}  get constant s A_{1}
            call d/1                  deallocate
            deallocate                proceed

            proceed

Figure 1: An example of actual WAM code

definition for a predicate is chosen, the remaining alternatives are stored inside a choice-point. These choice-points are maintained by the WAM’s special instructions implementing backtracking: try me else, retry me else, and trust me. For instance, the query in the Example 2 only succeeds when the second definition of the predicate a/1 is chosen.

Regarding the memory architecture, even though JAM includes additional regions not present in the original WAM, its structuring remains straightforward. The memory architecture is composed of several independent regions, each associated with a set of special registers. These regions and their corresponding registers are sketched in Figure 2. In the first place, the CODE region keeps the compiled code of the rules that made the program. The region HEAP is a stack which stores all the structures dynamically created throughout execution, mostly in the unifications. The region STACK is also a stack which stores two types of objects: the environments and the choice-points, already mentioned above. The region T-HEAP (temporary heap) is analogous to HEAP, but for storing the terms of the temporary facts (whose use within JAM is discussed further bellow in Section 3.1). The next region, LINE, stores the current argumentation line being explored. Note that the last two memory regions are not present in WAM, since they deal with aspects of the dialectical analysis not required for solving Prolog queries. Finally, the region TRAIL stores references to the variables binded during those unifications that should be unbinded when backtracking.

In addition to those registers shown in Figure 2, there are two other families of registers: parameter registers and term registers. In the one hand, the parameter registers, denoted as A_{i},

low memory  high memory
CODE  HEAP  STACK  T-HEAP  LINE  TRAIL
P^{↑} CP^{↑}  H^{↑} HB^{↑} S^{↑} E^{↑} B^{↑} B0^{↑}  T^{↑}  L^{↑}  TR^{↑}

Figure 2: JAM memory architecture are used to communicate the location of the parameters of a certain goal in the current query to the head of the clause with whom it will be unified. On the other hand, the term registers, denoted as X_{i}, are used in the construction of terms in the HEAP.

The HEAP is the memory region holding all the terms referred through the execution. Each cell in the HEAP contains a pair (type, content), where type describes what is stored in content. The valid types are the usual ones: reference, constant, structure, and list. Since variables can either be binded to a term or unbinded, they are represented by the pair (reference, address), where address denotes the location of the term binded to it and assuming that a self reference denotes an unbinded variable. Constants are easily represented by the pair (constant, token), where token is the actual constant being stored. Finally, a structure of the form f(t_{1}, …, t_{n}) is represented by the pair (structure, address), where address denotes the location of the pair (constant, f) which holds the functor name, and the following n cells contain the representation of its n subterms.

Insofar, the topics covered were common to both WAM and JAM. In what follows, we focus our attention on those aspects of JAM not present in WAM.

3.1 Finding argument structures

The construction of an argument for a query involves two main tasks: to find a defeasible derivation for that query, and then to check its consistency. The defeasible derivation can be obtained applying the same mechanism used in WAM when solving Prolog queries (i.e., the backward-chaining of rules). However, the consistency check requires some additional effort. Within JAM, the consistency of defeasible derivations is checked while the derivation is being built, making a clever use of backward-chaining. When a rule c ^{−≺} L is about to be used, it is first confirmed whether Π ∪ {c} remains consistent. Naturally, no rule should be used in a derivation when its current bindings make it inconsistent with Π (recall the consistency requirement in argument structures imposed in Definition 2).

Let cons(A) be the set of ground literals appearing as the consequences of the defeasible rules in an argument structure ⟨A, h⟩. Any defeasible rule c ^{−≺} L can be used in the construction of a given argument structure ⟨A, h⟩ if and only if Π ∪ cons(A′) ∪ {c} is consistent, where A′ is the set of defeasible rules used up to this point in the construction of that argument structure (also note that Π ∪ cons(A′) is already consistent). These elements in cons(A′) are what we call temporary facts. They are called facts because while being used they behave exactly like facts, and they are called temporary because their lifespan is restricted only to the construction of the current argument structure.

To sum up, JAM implements its consistency checks using the same machinery that finds defeasible derivations, also the very same procedure used for solving Prolog queries within WAM. The correctness of this approach has been established in [2], from where we adapted the following lemma:

Lemma 1. Let Π be a consistent set of strict rules, and h be a literal. Then, the set Π ∪ {h} is inconsistent if and only if there exists a derivation of \overline{h} from Π ∪ \{h\}, allowing the use of some inverted rules.

The inverted rules are a third kind of rule that JAM uses internally for consistency checks (note that the knowledge engineer does not need to be aware of their existence). To distinguish inverted rules from the strict and defeasible ones, they are denoted as L_{0} @— L_{1}, L_{2}, …, L_{n}. This kind of rules play a key role within JAM, as shown in the next theorem, also adapted from [2].

Theorem 2. Let P = (Π, Δ) be a de.l.p. In this context, a defeasible rule h ^{−≺} L can be used in the construction of an argument structure ⟨B, q⟩ if and only if \overline{h} cannot be derived from Π ∪ cons(B′) ∪ {h}.

Demonstration. The rule h ^{−≺} L can be used in the construction of ⟨B, q⟩ if and only if Π ∪ cons(A′) ∪ {h} is consistent, and by virtue of Lemma 1, Π ∪ cons(A′) ∪ {h} is consistent if and only if \overline{h} can not be derived from Π ∪ cons(A′) ∪ \{h\}. □

Even though consistency checks within JAM are analogous to defeasible derivations, no inverted rules should be used in the construction of an argument structure. For this reason, two instructions, prove consistency else and end consistency proof, delimit the boundaries of the consistency check. These instructions set and clear the internal flags called defeasibleProof and allowInvertedRules that control the kind of rule that are allowed to be used in a given state. Within JAM, it is quite easy to identify the different types of rules by looking into the compiled code initially loaded in the CODE region, since different types of rules are compiled using a different sets of instructions, as shown in the following table:

Strict Rules  Defeasible Rules  Inverted Rules

      just me        defeasible just me        just me checking consistency
      try me else    defeasible try me else    try me else checking consistency
      retry me else  defeasible retry me else  retry me else checking consistency
      trust me       defeasible trust me       trust me checking consistency

Since temporary facts (i.e., the head of every defeasible rules used up to this point) are indeed temporary, lasting only until the current argument structure is completed, they are stored in a separate structure called temporary fact table. In a like manner, the terms in these temporary facts are stored in a separate region (the T-HEAP), apart from the regular

terms. The JAM instructions save srule terms, save drule terms and save fact generate

these temporary facts. Finally, as an example of the role of these concepts, Figure 3 depicts the JAM code associated with the rules fly(X) ^{−≺} bird(X) and ^{∼}hen(X) @—^{∼}bird(X).

3.2 Computing answers

Since determining whether a given literal h is warranted is essential in order to answer queries about h, JAM must implement the dialectical analysis structured as a tree mentioned in Definition 7. The construction of this dialectical tree can be described in terms of the following standard Prolog predicates:

                warranted(Q)  :-  find argument(A), /+ defeated(A).
                defeated(A)   :-  find defeater(A,D), /+ defeated(D).

Putting it into words, a literal Q is warranted when an argument structure for this literal can be constructed, provided that it is not defeated. In turn, an argument structure is defeated if we found a defeater for it, such that this new defeater is not defeated by another argument structure. Note that the goal /+ defeated(A) in the first clause is defined in terms of Prolog’s standard negation as failure. It succeeds when there are no defeaters for the argument structure A, and it fails when there exists at least one of those defeaters. Figure 4 shows how this procedure is implemented within JAM. First, an argument structure for the current query is constructed (following the procedures discussed in the previous section). Then, if the construction succeeds

      fly/1:

               defeasible just me

                                         ∼hen/1:

                                                  just me checking consistency

               allocate 2                          allocate 0
             get variable X_{2} A_{1}  get variable X_{1} A_{1}
             save drule terms fly/1 X_{1}  put value X_{1} A_{1}
               forbid inv                          call ^{∼}bird/1
             put value X_{2} A_{1}  forbid inv
               call bird/1                         only strong

               set defeasible

                                                  stop only strong
               prove consistency else L:

                                                  deallocate

             put structure ^{∼}fly/1 A_{1}  proceed

             set value X_{2}
               call naf/1
          L:

               end consistency proof
             save fact X_{1}
               deallocate
               proceed

Figure 3: JAM code for the rules fly(X) -< bird(X) and ∼hen(X) @- ∼bird(X)

(it could be case that no argument structure support that literal), JAM looks for level one defeaters. If one of such defeaters is found, then JAM looks for level two defeaters, and so on.

In this example, the instruction prepare to defeat k dynamically generates the JAM code for the predicates DefeatK/0, exactly as if it were part of the original program loaded into the machine. In a sense, we are using the same JAM to execute the aforementioned piece of Prolog code, a task it can easily achieve since the strict part of DeLP programs behaves almost like standard Prolog. The purpose of these dynamic predicates is to find defeaters of the most recently constructed argument structure. When a defeater is found, it must be verified whether this defeater is in turn defeated, hence DefeatK/0 is almost performing a parallel dialectical analysis. The predicate DefeatK/0 follows the same strategy as before, trying to find an argument structure that defeats the one just constructed and then verifying that this defeater is not also defeated, this time considering defeaters in the next level, using the instruction prepare to defeat K+1 and attempting the goal /+ DefeatK+1/0, and so on.

Throughout this process, the memory region called LINE holds the current argumentation line, containing every support and every interfering argument structure in the path from the

?:  allocate  ; start of the query.
⋮  ; query code.
call q/n  ; builds an argument.
prepare to defeat 1  ; considers all its possible defeaters.
put constant Defeat1/0 A_{1} ; attempts to prove that...
call naf/1  ; ...no defeater can be found.

             deallocate  ;

end query  ; end of the query.

Figure 4: JAM’s code for a query q/n current node to the root of the dialectical tree. This information is used during the execution of those JAM instructions that verify whether the argumentation line under consideration

is acceptable, namely not circular, not less specific, proper defeat and blocking defeat.

According to Definition 6, there are four conditions that characterize an acceptable argumentation line. The first condition is trivially met by any algorithm that returns an answer, like this one. For the second condition, the concordance check over the set of supporting and interfering argument structures present in the current argumentation line was also verified in the former theory, thus JAM already check this condition using the information stored in the temporary fact table. The same applies to the third condition, since circular argumentation, a long standing form of fallacious argumentation, was already averted in the previous formalization. Al last, the fourth condition can be asserted updating the semantic of the instructions proper defeat and blocking defeat. In the original JAM, blocking defeaters were only accepted as a defeater of the argument structure labeling the root of the dialectical tree, but in the new formulation they are allowed anywhere but as response of another blocking defeater.

It should be noted that the dialectical tree being constructed never gets represented as a complete tree, only the argument structures present in the current argumentation line are kept. However, when an argumentation line is exhausted, some of its argument structures might not be part of the new argumentation line about to be explored. This is implemented within JAM accessing LINE like as a stack, storing the register that holds the current top of this stack (called L) inside the choice-points, and restoring its value whenever backtracking.

Finally, being able to determine whether a given literal is warranted allows JAM to compute the right answer. For instance, given a literal h, just attempt to warrant both h and \overline{h}, and then return the answer shown in the following table:

h  \overline{h}  right answer
warranted not warranted  YES
not warranted warranted  NO
not warranted not warranted UNDECIDED
warranted  warranted  (impossible)

4 Conclusions

Defeasible Logic Programming provides an attractive framework for knowledge representation and reasoning, mainly due to its ability to represent incomplete and potentially contradictory information. Having an adequate implementation of this theory leads not only towards developing robust applications but also allowing the fine tuning of the formalism itself. To that end, in this papers we have shown how can an approach proved successful within Logic Programming, namely having an abstract machine sitting half way between the logic program and the hardware actually executing it, could also be adapted to context of DeLP.

An abstract machine suitable for DeLP was already introduced in a previous work, although it was specifically designed for an earlier revision of the theory, that lacks the recent updates to its syntax and semantics. The purpose of this paper was to highlight the main features of the internal operation of this abstract machine, clearly stating as well what must be changed in order to make it suitable for the newest revision of DeLP. In fact, this updated abstract machine actually underpins the DeLP implementation reported in [9, 10], which is available for

download at http://cs.uns.edu.ar/∼ags/DLP.

Acknowledgments

This research was partially supported by Secretaría General de Ciencia y Tecnología de la Universidad Nacional del Sur (24/N016) and by Agencia Nacional de Promoción Científica y Tecnológica (PICT 2002 No. 13096). The first author is also partially supported by a fellowship from Comisión de Investigaciones Científicas (CIC).

References

[1] Aït-Kaci, H. Warren’s Abstract Machine, a tutorial reconstruction. MIT Press, 1991.

[2] García, A. J. La Programación en Lógica Rebatible: su definición teórica y computacional. Master’s thesis, Departamento de Ciencias de la Computación, Universidad Nacional del Sur, Bahía Blanca, Argentina, June 1997.

[3] García, A. J. Programación en Lógica Rebatible: Lenguaje, Semántica Operacional, y Paralelismo. PhD thesis, Departamento de Ciencias de la Computación, Universidad Nacional del Sur, Bahía Blanca, Argentina, Dec. 2000.

[4] García, A. J., and Simari, G. R. Una extensión de la máquina abstracta de Warren para la argumentación rebatible. In Proceedings of the III Congreso Argentino de Ciencias de la Computación (La Plata, Oct. 1997), Universidad Nacional de La Plata.

[5] García, A. J., and Simari, G. R. Defeasible Logic Programming: An Argumentative Approach. Journal of Theory and Practice of Logic Programming 4, 1–2 (2004), 95–138.

[6] García, A. J., Simari, G. R., and Chesñevar, C. I. An Argumentative Framework for Reasoning with Inconsistent and Incomplete Information. In Proceedings of the Workshop on Practical Reasoning and Rationality (Brighton, Reino Unido, Aug. 1998), 13th European Conference on Artificial Intelligence, pp. 13–19.

[7] Simari, G. R., Chesñevar, C. I., and García, A. J. The Role of Dialectics in Defeasible Argumentation. In Proceedings of the XIV Conferencia Internacional de la Sociedad Chilena para Ciencias de la Computación (Concepción, Chile, Nov. 1994), Universidad de Concepción, pp. 111–121.

[8] Simari, G. R., and Loui, R. P. A Mathematical Treatment of Defeasible Reasoning and its Implementation. Artificial Intelligence 53, 1–2 (1992), 125–157.

[9] Stankevicius, A. G., García, A. J., and Simari, G. R. Una arquitectura para la ejecución de Programas Lógicos Rebatibles. In Proceedings of the 5th International Congress on Informatics Engineering (Capital Federal, Argentina, Aug. 1999), Universidad de Buenos Aires, pp. 450–461.

[10] Stankevicius, A. G., García, A. J., and Simari, G. R. Compilation Techniques for Defeasible Logic Programs. In Proceedings of the 6th International Congress on Informatics Engineering (Capital Federal, Argentina, Apr. 2000), Universidad de Buenos Aires.

[11] Warren, D. H. An Abstract Prolog Instruction Set. Technical Note 309, SRI International, Menlo Park, CA, Oct. 1983.