3.1 Frames and inheritance

Figure 3 shows two $\mathcal{E}$ rgoAI frames, each with an object-id, such as person(’Bunky Muntner’) or claim(13355), followed by a list of attribute–value pairs of the form $\langle attr \rangle$ $\texttt{->}$ $\langle val \rangle$ . For instance, the types of the claim attribute values include atoms, an RDF XSD date type instance, another frame expression representing the semantic frame of a statement, and even the reference to a Python object. Figure 3 also shows a fragment of the classification hierarchy for the program, where the infix operator ::/2 represents the subclass relation and :/2 indicates that an instance is a member of a class. Since their object-ids identify instances, these frames are called instance frames. Both ::/2 and :/2 can be specified either by facts or rules. For instance, the non-ground fact on line 14 indicates that any frame with an object-id that unifies with claim(?) belongs to the class Claim.Footnote ¹⁴

Figure 4 shows $\mathcal{E}$ rgoAI class frames that specify signatures for subclasses and instances, default values for instance attributes, as well as attribute values of the class itself. When an attribute value is a type, the attribute–value relation is designated via $\texttt{=>}$ /2 and the inheritance is termed structural; otherwise $\texttt{->}$ /2 is used to designate default object values, and the inheritance is termed behavioral. Both type and object values are inheritable if they occur within $[|\ldots.|]$ . but otherwise are non-inheritable. For instance, in the Claim frame in Figure 4, all attribute values are inherited except for author, which pertains to the Claim class itself, and has the object Ingrid B. Baird as its value. Also in the frame for Claim the attribute dateTime is specified to be required and functional through a cardinality constraint, which indicates the minimum and maximum number of values an instance may have for a given attribute. The Claim frame also denotes the default object value X for the attribute medium. Finally, an $\mathcal{E}$ rgoAI rule on line 12 propagates to person instances values of claimed from claimer attributes of claims.

Fig. 4.

$\mathcal{E}$ rgoAI class signatures.

The instances in Figure 3 inherit these attributes in various ways:

• • Direct behavioral inheritance. Because the instance ’Bunky Muntner’ is a Person, it directly inherits politAffil $\texttt{->}$ Independent.

• • Behavioral overriding. The claim object claim(13355) states explicitly that medium $\texttt{->}$ NewsSite (in Figure 3), overriding the default medium $\texttt{->}$ X inherited from the class Claim.

• • Monotonic structural inheritance. claim(13355) is a member of both the class Claim, from which it inherits the default documentType as PublicWebDocument, and of class NewsReport where documentType has the type WebNewsArticle. Unlike behavioral inheritance of attribute values, structural type inheritance is not overridable. Instead, it works monotonically, by accumulation. In our example, the class WebNewsArticle is said to be a subclass of PublicWebDocument in Figure 4, so the two types would be considered consistent for nearly all applications. In general, if $\mathcal{E}$ rgoAI derives different types for an attribute of an object, the types are not taken to be contradictory. This viewpoint is similar to that of formal ontologies in which two concepts are not taken to be disjoint unless a relevant exclusion axiom causes them to be. In $\mathcal{E}$ rgoAI, similar constraints can be enforced either by type checking or by integrity constraints (see Section 7). The paper Yang and Kifer (Reference Yang and Kifer2003) gives rigorous treatment to the semantics of inheritance in $\mathcal{E}$ rgoAI.

• • Monotonic behavioral inheritance. While behavioral inheritance is defeasible by default in $\mathcal{E}$ rgoAI, there are cases when monotonic inheritance is preferred. In our example the people described by the knowledge base are assumed to speak English, but they may speak other languages as well. $\mathcal{E}$ rgoAI allows behavioral inheritance to be set as either monotonic or non-monotonic at the module level. Figures 3 and 4 and the attribute language illustrate this point. The default strategy for behavioral inheritance is non-monotonic and thus the language (or languages) stated at Bunky Muntner’s object level in Figure 3 overrides the inheritance of language from class Person specified in Figure 4. If, however, the module were told to use the monotonic semantics for behavioral inheritance (say, by inserting the directive :- setsemantics{inheritance=monotonic} then language $\texttt{->}$ English would be inherited monotonically from class Person: that isit would be added to the statement language $\texttt{->}$ Spanish specified directly inside the object for Bunky Muntner. Thus a query such as

  
  would unify ?Language with both English and Spanish, as desired.

3.2 Attributes defined via rules

Attributes can be defined by $\mathcal{E}$ rgoAI rules, facts, or both. As an example we show how $\mathcal{E}$ rgoAI can represent and maintain contemporary knowledge sources such as statement embeddings used by language models (LMs).

Both LLMs and small LMs such as Phi-3 (2024) and Google’s Universal Sentence Encoder Cer et al. (Reference Cer, Yang, Kong, Hua, Limtiaco, John, Constant, Guajardo-Cespedes, Yuan, Tar, Strope and Kurzweil2018) are usually written in Python and C $^{++}$ and so are easily accessible by $\mathcal{E}$ rgoAI through the Janus interface Swift and Andersen (Reference Swift and Andersen2023). For instance, suppose embeddings were obtained using a version of Universal Sentence Encoder, whose Python API loads a model, and then calls it with different textual inputs. The model object is created by the goal.

The predicate Py_func/3 allows $\mathcal{E}$ rgoAI to call a Python function, in this case

The return of this call unifies the $\mathcal{E}$ rgoAI variable ?PyObj with a Python object reference of the form pyObj(ObjectReference). After asserting the object reference as a currentModel/1 fact, a rule for Claim objects can be written as

where ?Vector will be instantiated to a list of floating point numbers. Unlike this explanatory example, in practice it is usually best to keep information such as embedding vectors as attributes of Python objects, which can be accessed and manipulated through Janus in much the same manner as $\mathcal{E}$ rgoAI objects.

3.3 Type checking

A type in $\mathcal{E}$ rgoAI can be any class in the classification hierarchy. Remembering that the class membership (the :/2 relationship), the class hierarchy (the ::/2 relationship), and the properties (the $\texttt{->}$ /2 relationships) can be defined via logic rules, it is no wonder that $\mathcal{E}$ rgoAI types are powerful and expressive but also that fully static type checking is not possible. Dynamic type checking is possible. While dynamic type checking cannot be guaranteed to terminate and may be slow in complex cases, it is often a highly useful aid to program development. To perform dynamic type checks, one can easily express different type violation as queries that return type violations as counterexamples to type correctness.

Although the semantics needed for signatures is sometimes program-specific, many type inconsistencies are common, including (1) that an object has an attribute value inconsistent with the inferred type for that value; (2) an object has an attribute that is not in any of its inherited signatures; or (3) the number of values for a given object and attribute are not consistent with cardinality constraints declared in an inherited signature. Type checking can be particularly important when complex objects are inserted in a dynamic setting, as will be discussed in Section 8.

Here is an example of type violations expressed as a query that identifies attributes and values for instances that violate properties 1 and 2 above.

To save the user the trouble of writing type constraints for common cases of type violations, $\mathcal{E}$ rgoAI provides the ∖typecheck module that supports the above type checkers so that the user can simply query:

Details can be found in the $\mathcal{E}$ rgoAI user’s manual.

3.4 $\mathcal{E}$ rgoAI frame compilation

The compilation of $\mathcal{E}$ rgoAI frames into Prolog predicates follows the general design of Kifer et al. (Reference Kifer, Lausen and Wu1995) and consists of two parts: (1) frames are translated into Prologs; and (2) closure rules are added to support the object-oriented semantics of frames. In this section, we describe a few aspects of $\mathcal{E}$ rgoAI compilation to give the reader an idea of the compilation process.

Both instance and class frames are translated into Prolog in a similar manner, so we take as an example the following instance frame, which is to be added to $\mathcal{E}$ rgoAI’s knowledge base. The frame is complex because it has multiple attribute–value pairs, because its identifier includes an inheritance predicate (: /2), and because it has a set-valued attribute.

As described in Kifer et al. (Reference Kifer, Lausen and Wu1995), frame compilation begins with translating complex frames (like the above) into a conjunction of atomic frames. As part of this process, attribute values that are sets are split into a conjunction of singletons, and the membership statement for Mary is factored out of the frame:

These atomic frames are then translated to Prolog facts that are asserted to the XSB database as tries Ramakrishnan et al. (Reference Ramakrishnan, Rao, Sagonas, Swift and Warren1999).

The wrapper predicate mvd/3 (which stands for multi-valued data) is used for the translation of attributes with behavioral inheritance. Query frames must undergo the same translation as program frames for resolution to work properly. For instance the query

would be translated to

yielding two solutions, one with {?Class=employee,?Kid=Leo} and another with {?Class=employee,?Kid=Tim}. $\mathcal{E}$ rgoAI’s compiler mangles the names of the wrapper predicates to include the module of the file or query.

$\mathcal{E}$ rgoAI rule frames must be encoded in a more complex manner than fact frames and require generation of closure rules to:

• • Compute the transitive closure of :: /2 in a manner that supports runtime warnings about cycles in the subclass hierarchy.

• • Compute the closure of : /2 with respect to :: /2, that is if X : C and C :: D then X : D.

• • Perform inheritance. In particular, monotonic inheritance must detect and propagate multiple type values while non-monotonic inheritance must detect and override object value conflicts.

• • Provide an infrastructure to treat undefined methods as exceptions. Unlike Prolog, undefined predicates in $\mathcal{E}$ rgoAI do not throw errors by default. However when checks for undefinedness are turned on, code to raise appropriate errors is injected into the closure rules.

The above closure rules are specified statically in special files that get included in the compiled Prolog code after the appropriate preprocessing that makes the files compliant with $\mathcal{E}$ rgoAI’s dynamic module system.

5.1 Module-aware salting

Thus, the basic idea underlying the implementation of $\mathcal{E}$ rgoAI modules is that in the end, all HiLog and F-logic wrapper predicates are translated with respect to a particular module, and the module symbol is used only in the outermost functor of the translated wrapper predicates. This restriction is made because ultimately the system determines the truth values of the instances of the wrapper predicates only. For instance, the module-specific version of HiLog’s apply/n is ’ salt^modname^apply’ /n + 1. Functors at inner levels become arguments to the outer wrappers – after the HiLog and F-logic transforms, inner functors are no longer treated as predicates, have no truth values, and their salting does not involve modules. As a result, the arguments conceptually play the role of shared object identifiers about which logical assertions (facts and rules) are being made. Assertions made in one module about a set of objects do not interact with the assertions about that same set of objects in another module unless one module explicitly queries the other.

For example: suppose a database table named p/1 exists both in module foo and module bar. A priori we do not know of any relationship between these two tables so their contents should be considered to be unrelated. However, if we learn that module foo has a rule of the form

then the version of p/1 in foo must necessarily have all the tuples that the version of p/1 in bar has.

Admittedly, salting only the outer functor of a term means that we distinguish between p(?X) that appears as a call and p(?X) that appears as an argument, which makes meta-programming noticeably less elegant. This trade-off is well known and analogous to choosing between a Prolog with a predicate-based module system and a Prolog with a functor-based module system (e.g., Ciao Prolog vs. XSB).

Because assertions are module-specific, queries are issued from a particular module, although they may involve querying another module. For instance,

translates into a query of the form

Similarly, the wrapper predicates ’ salt^modname^mvd’, ’salt^modname^isa’, etc. are used to separate translations of the frame statements into different modules. For rules, the translation is similar:

becomes

Note that after the compilation of the above query, the module-part of the first outermost wrapper predicate, salt^modname^apply’/4, remains generic, that is, it is not replaced with a real module name. Similarly, in the above rule, the module parts of the wrappers salt^modname^apply’/2 and ’salt^modname^sub’/2 remain generic. As may be guessed, this happens because the above goal p(?X)(….) does not have any module reference (@mod); likewise, neither hd(…) nor foo::?Y in the above rule has such references. So, what is the module in those cases and how would the compiler obtain that module’s name? In $\mathcal{E}$ rgoAI, the answer is that the module in question is the “current” module, a concept closely tied to the dynamic manner in which rules and modules are created and associated with each other during the course of a computation.

5.2 Loading versus adding

Normally the user creates a file that includes facts, rules, and queries. Then the user loads or adds that file to a module (the module may or may not exist at the time), which causes the file to be compiled for that module and the queries executed. The user might pose additional queries, load, or add additional files into new or existing modules, or perform other operations.

For concreteness, suppose we have a file called myProgram.ergo that contains the query and the rule just discussed plus some data facts (i.e., bodiless rules). We can load the file into some explicit module, for example mainRules, or into the current module:

The first form will create the empty module mainRules, if it did not exist before, compile myProgram.ergo for the module mainRules causing compiled salted Prolog rules to appear in XSB’s memory. (If the module existed prior to the command, it is emptied out of its old contents first.) In the second version of the load command, myProgram.ergo will be compiled for the current module but the rest is the same as we just explained.

The current module dynamically changes during an $\mathcal{E}$ rgoAI session. When $\mathcal{E}$ rgoAI starts up, it automatically creates the module main which is the first current module. If either of the above load commands executes next, it executes with main as the current module. During the compilation of myProgram.ergo using the first option, the current module will be mainRules rather than main. With the second version of the load command, the current module will not change, of course, and will still be main. If myProgram.ergo includes another loading command, like ?- [myStuff $\;\;\texttt{>>}\;\;$ miscRules], then when this command is executed, myStuff.ergo will be compiled with miscRules as the current module.

Loading wipes out any existing contents of the target module, so loading two different sets of rules into the same module is rarely meaningful unless the first set of rules and data has become obsolete. Such scenarios arise when dealing with streaming data, but are unlikely in cases where working knowledge of an application evolves. For such applications, $\mathcal{E}$ rgoAI provides the add command, for example,

Using the add command resembles loading except that it does not erase beforehand the contents of the module (mainRules in the first form, the current module if the second form). The overall result of $\mathcal{E}$ rgoAI’s dynamic creation of modules, loading, and adding is that any given file can either be loaded into any module or added at any time.Footnote ¹⁵

5.3 Compiling dynamic module references

Until now, we remained silent about how the placeholder for the current module, modname, gets replaced with the actual name of that module within the context of a given execution. This is accomplished with the help of the GPP preprocessorFootnote ¹⁶ a core program used by XSB as well. GPP is similar to the CPP preprocessor used by C and C++, but includes features needed by $\mathcal{E}$ rgoAI that CPP does not support such as the ability to change syntax on the fly and to perform macro evaluations inside quoted strings.

Because code files may be dynamically loaded or added into modules, $\mathcal{E}$ rgoAI does not compile into the XSB Prolog syntax directly but rather into a syntax where HiLog and frame wrappers are enveloped with suitable GPP macros. For example, instead of compiling the apply/n wrapper into ’salt^bar^apply’(q,_X) and

‘salt^modname^apply’(’salt^apply’(p,_X),a,’salt^ apply’(f,b),[3,_X]) directly, we could use these GPP macros:

and compile our HiLog terms into these more structured and compact expressions:

There are several interesting things to note about these macros. First, the last three macro definitions refer to other macros such as #PREFIX, and these referenced macros appear inside quoted strings.Footnote ¹⁷ The #mode save/restore commands above order GPP to temporarily stop interpreting single quotes as string delimiters, which enables GPP to compute all those macros as we intended. Second, notice that CRNT_MODULE is undefined as a macro, but it is clear from the name that we somehow want it to evaluate to the current module name (which recall, changes depending on the context where the reference to the current module appears). In our example, the current module can be main or mainRules and this becomes known only at the time of loading. Fortunately, GPP can be forked from its parent process and can take a directive to add a new macro

where module-being-loaded is the module name known to the loader. In other words, the problem of passing the name of the current module is solved because we can pass that name to GPP under the guise of the CRNT_MODULE macro.

As a final point, $\mathcal{E}$ rgoAI’s module system also extends so that Prolog modules are called in a manner similar to $\mathcal{E}$ rgoAI modules. For instance, the $\mathcal{E}$ rgoAI goal that invokes the Prolog predicate member/2, which lives in the XSB module basics, is:

This is implemented simply by compiling member/2 without any salting whatsoever. Since the core of XSB is written in C, C routines appear as regular Prolog calsl, so in $\mathcal{E}$ rgoAI they also can be accessed the same way, via the @ $\mathtt {\backslash }$ prolog idiom. In principle, this idiom could also be extended to other languages so that, for example, Python modules would be accessible via @ $\mathtt {\backslash }$ python or @ $\mathtt {\backslash }$ janus, if Janus is used.

6.1 The GCLP argumentation theory

Pseudo-code for GCLP, $\mathcal{E}$ rgoAI’s default argumentation theory is shown in Figure 6. The actual code in $\mathcal{E}$ rgoAI is more complex due to optimizations and debugging support.Footnote ²⁰ That code also exports a number of query points that let the user investigate why certain rules were defeated, refuted, or rebutted; why there is a conflict between some rules; etc. As mentioned, $\mathcal{E}$ rgoAI supports several argumentation theories other than GCLP that differ in how rules are defeated, and in the generality of opposition. For instance, some argumentation theories allow ∖opposes /2 rules to specify when a set of three or more different rules must succeed for opposition to happen.

Regardless of the argumentation theory, a defeasible rule:

is translated to

where AT is the $\mathcal{E}$ rgoAI module that contains the desired argumentation theory. Observe that this simple cross-module calling scheme enables different $\mathcal{E}$ rgoAI modules to use different argumentation theories at the same time. A defeasible rule with variable bindings for which Body succeeds is called a candidate.

It can be seen from Figure 6 that a given rule, say $R_{t}$ with tag Tag (denoted $R_{t}/Tag$ , is defeated if it is refuted or rebutted by some non-defeated rule, or if $R_{t}/Tag$ is disqualified. Rebuttal requires that an opposing rule, say $R_{o}$ , with tag OppTag (denoted $R_{o}/OppTag$ ) succeeds as a candidate, and that $R_{o}/OppTag$ is neither canceled nor refuted. Refutation, on the other hand, also requires an appropriate ∖overrides /2 statement to be present. Thus in GCLP if two undefeated rules rebut each other but neither is overridden, both fail. Otherwise the overrides statement causes either one rule to succeed and the other to fail, or both to succeed with truth value $u$ in the case of mutual overriding. Rule sets like that in Figure 6, when optimized for performance, implement $\mathcal{E}$ rgoAI’s argumentation theories.

We should note that the literature is rife with flavors of defeasible logic Prakken (Reference Prakken1993); Nute (Reference Nute1994); Gelfond and Son (Reference Gelfond and Son1998); Brewka and Eiter (Reference Brewka and Eiter2000); Sakama and Inoue (Reference Sakama and Inoue2000); Wang et al. (Reference Wang, Zhou and Lin2000); Dung and Tran (Reference Dung and Tran2001); Zhang et al. (Reference Zhang, Wu and Bai2001); Delgrande et al. (Reference Delgrande, Schaub and Tompits2003); Eiter et al. (Reference Eiter, Faber, Leone and Pfeifer2003), each slightly different from the next. It is argued in Wan et al. (Reference Wan, Grosof, Kifer, Fodor and Liang2009, Reference Wan, Kifer and Grosof2014) that argumentation theories, like those in $\mathcal{E}$ rgoAI, can simulate and approximate a number of other approaches, and the dozen or so argumentation theories supplied with $\mathcal{E}$ rgoAI testifies to the power and flexibility of that approach.

6.2 Argumentation and paraconsistency in $\mathcal{E}$ rgoAI

The following example highlights a property of $\mathcal{E}$ rgoAI’s GCLP argumentation theory: the failure of rebutted rules.

Fig. 6.

Simplified pseudo-code for GCLP, $\mathcal{E}$ rgoAI’s default argumentation theory.

GCLP’s \treatment of explicit negation is the same as most of $\mathcal{E}$ rgoAI’s argumentation theories, but it differs from approaches like WFSX Alferes et al. (Reference Alferes, Damásio and Pereira1994) in which both A and $\mathtt {\backslash }$ neg A would have the truth value undefined. The fact that GCLP sets their truth value to false makes it arguably more useful for paraconsistent reasoning based on frame logic with argumentation. If the truth value of opposing literals were set to undefined then the truth values of literals that depend on these opposing literals would also be set to undefined.

Although some logics use a four-valued lattice to distinguish unknown from incompatible truth values, like those in $P_{eneg}$ , handling inconsistency purely within WFS requires mapping inconsistency to an existing truth value: true, false, or undefined. Viewed in this way, WFSX conflates the inconsistency of a literal with a literal’s being undefined/unknown (u) while GCLP conflates it with false. In fact, $\mathcal{E}$ rgoAI users have suggested a way to support a four-valued truth lattice semantics based on an argumentation theory that acts like GCLP except that it has no concept of rebuttal. This argumentation theory, RefuteCLP, is included with $\mathcal{E}$ rgoAI. In RefuteCLP, if one rule refutes another, any inferences drawn by the second rule are defeated. However, if two rules rebut (but do not override) each other then neither inference is defeated and it is possible to infer that, in a pair of opposing facts, both are true. Therefore, if $P_{eneg}$ in Example1 used RefuteCLP instead of GCLP, both A and $\mathtt {\backslash }$ neg A would have been true. $\mathcal{E}$ rgoAI does not provide direct support for the fourth truth value, inconsistent, but user-built rulebases can treat such situations as localized inconsistency. Localized inconsistency is similar to paraconsistency in Annotated Logic Blair and Subrahmanian (Reference Blair and Subrahmanian1989); Kifer and Lozinskii (Reference Kifer and Lozinskii1992), and sophisticated users can employ meta-interpreters or similar techniques to detect and take advantage of paraconsistency in $\mathcal{E}$ rgoAI knowledge bases.

7.1 Unsafe negation in $\mathcal{E}$ rgoAI

Consider the resolution of the goal p(?X) using the set of rules and facts in Figure 7. Since by default $\mathcal{E}$ rgoAI uses a left-to-right literal selection strategy, the literal selected in Step 1 of the resolution is q(?X), which is then resolved using a program rule to produce the subgoal $\mathtt {\backslash }$ naf q2(?X). Since $\mathtt {\backslash }$ naf q2(?X) is an unsafe literal, $\mathcal{E}$ rgoAI attempts to delay the literal’s evaluation in the hope that ?X will be grounded later on in the evaluation – for example, the grounding of ?X might happen after resolving r(?X) later in the rule for p(?X).

Fig. 7.

Schematic evaluation of non-ground default negation.

The postponement is done using a modified version of the when/2 predicate found in XSB and other Prologs, which in this case delays the goal $\mathtt {\backslash }$ naf q2(?X) until ?X becomes ground. This is shown on line 3 of the evaluation. The predicate when/2 is based on attributed variables, which underlie the evaluation of logical constraints in Prolog systems. In the next step, $\mathtt {\backslash }$ naf s(?Y) is selected and postponed, as shown on lines 4–5. Next, r/1 is resolved with the third rule and then with r2(2), which finally binds ?X to 2, grounding the negative subgoal $\mathtt {\backslash }$ naf q2(?X) to $\mathtt {\backslash }$ naf q2(2). This is shown on lines 6–8. Since $\mathtt {\backslash }$ naf q2(2) is true, we remove it, reaching line 9. Note that grounding of $\mathtt {\backslash }$ naf q2(?X) was requested on line 3 but did not happen until line 8, after r2(?X) was resolved. The two terms involved in this interaction, $\mathtt {\backslash }$ naf q2(?X) and r2(?X), do not even occur in the same rule. Moreover, when $\mathtt {\backslash }$ naf q2(?X) was delayed, it was not known whether ?X would ever become ground. The point is that the algorithm for subgoal delay is automatic and involves inter-rule interaction and run-time analysis.

Resolving t(?Z,?Y) leaves a non-ground subgoal

∖

naf s(?Y), which cannot be grounded later because the variable ?Y does not appear outside of that subgoal. How should one proceed? In our experience, in most such cases, the user wants to check whether no grounding of ?Y would ever make s(?Y) true. This can be efficiently verified using the XSB predicate not_exists/1, as shown on lines 10 and 11 in Figure 7. Roughly, XSB defines not_exists(G) as (TG, fail; tnot(TG)), where TG is a tabled version of G, and tnot/1 is XSB’s ground well-founded negation. In certain cases, the user might want to assign the truth value u to non-ground ∖naf literals, such as

∖

naf s(?Y). This option can be selected in $\mathcal{E}$ rgoAI via a runtime switch.

Our discussion above considerably simplifies $\mathcal{E}$ rgoAI’s actions; for instance the ∖naf operator also handles variables in quantified subgoals, based on extensions of Lloyd and Topor (Reference Lloyd and Topor1984). Furthermore, it is generally accepted that

∖

neg G implies

∖

naf G Alferes et al. (Reference Alferes, Damásio and Pereira1994), and $\mathcal{E}$ rgoAI also uses this inference when grounding ∖naf -negated subgoals. We note that many aspects of $\mathcal{E}$ rgoAI’s approach to ∖naf could be adopted by Prologs that implement WFS, such as SWI and XSB itself. In fact, nu-Prolog Naish et al. (Reference Naish, Dart and Zobel1989) implements subgoal reordering for Prolog negation, although it does not assign the truth value undefined to non-ground negative subgoals, nor does it handle explicit negation or quantifiers.

7.2 Delay quantifiers

The delay quantifiers wish/1 and must/1 cause dynamic reordering of subgoals that do not fulfill argument binding requirements. These quantifiers check conditions on variables in a subgoal and delay that subgoal if these conditions fail. For example, the subgoal

contains the delay quantifier must/1, and evaluation of the subgoal delays evaluation of ?X[foo $\texttt{->}$ ?Y] until either ?X is ground or ?Y is partially instantiated. If the desired instantiation is unachievable, a runtime error results. The wish/1 quantifier delays its subgoal in the same manner as must/1, but the subgoal is executed after no more delay is possible, and no error is raised.

9.1 Termination on programs with finite models

Section 2 provided examples of SCCs of mutually dependent subgoals that correspond to unfounded sets in WFS. Another type of unfounded set is an unfounded chain, which can be illustrated by the simple $\mathcal{E}$ rgoAI program:

Using $\mathcal{E}$ rgoAI’s default resolution method, SLGR, the goal p(a) to $P_{FinModel}$ produces an infinite chain of goals, p(f(a)), p(f(f(a))), p(f(f(f(a)))), and so on. This is because SLGR creates a new table entry for any goal that is not a variant of a goal already in the table (cf. Section 2). $\mathcal{E}$ rgoAI can address such situations via subgoal abstraction, in which subgoals are abstracted once they reach a maximum size. In $P_{FinModel}$ , abstraction with subgoal depth 2 or more would rewrite any goal that unified with p(f(f(?X))) to p(f(?X)), ensuring that the evaluation will create only a finite number of subgoals.

The use of subgoal abstraction guarantees powerful semantic properties. Let us represent a three-valued well-founded model $M$ in terms of two sets: the set of atoms that are true in $M$ and the set of atoms that have truth value u in $M$ . Since the well-founded model of $P_{FinModel}$ has no atoms with truth value true or u, its three-valued model is finite. In Riguzzi and Swift (Reference Riguzzi and Swift2014), it is shown that if SLG is extended with subgoal abstraction then it correctly terminates for any program with a well-founded model that is finite under the above definition.

In $\mathcal{E}$ rgoAI, subgoal abstraction can be requested with the help of the goalsize restraint in the setruntime directive. Loading into $\mathcal{E}$ rgoAI the small fragment below,

produces the following answers and terminates:

Without subgoal abstraction (i.e., if the directive

is commented out) the above program will not terminate and will return no answers. In our case, however, the goalsize parameter tells the query subsystem to abstract subgoals larger than size 4, which forces termination.Footnote ²⁵ Subgoal abstraction is implemented by XSB’s tabling subsystem. Whenever a tabled goal is encountered, a ’subgoal check/insert’ operation traverses the goal in order to determine whether an existing table may be used or a new table must be created. The declaration for subgoal abstraction activates an engine-level hook that abstracts the goal as part of the traversal Riguzzi and Swift (Reference Riguzzi and Swift2014).

9.2 Sound termination on programs with infinite models

A different source of non-termination arises from programs with infinite three-valued models, as when the query p(?X) is made to the following program.

Sound termination for WFS is possible using restraint Grosof and Swift (Reference Grosof and Swift2013) a type of answer abstraction that sets the truth value of abstracted answers to u. For instance, when using restraint at term depth greater than or equal to two, the query p(?Y) posed to $P_{InfModel}$ would produce p(a) and p(f(a)) both as true answers, along with p(f(f(?X))) with truth value u. In this way, an informationally sound approximation to the goal p(?Y) is provided. Specifically, when using restraint to evaluate a query to a program $P$ , all atoms proved true or false by $\mathcal{E}$ rgoAI are true or false in the well-founded model of $P$ . However some atoms that are true or false in the well-founded model may be u in $\mathcal{E}$ rgoAI. Through restraint, $\mathcal{E}$ rgoAI supports a fully semantic approach to bounded rationality.

Answer abstraction can be requested with the help of the answersize restraint in the setruntime directive. Loading into $\mathcal{E}$ rgoAI the small program below,

produces the following answers:

Without the answer abstraction (i.e., without the setruntime directive), the above query does not terminate.

9.3 Tripwires

From the viewpoint of $\mathcal{E}$ rgoAI, both subgoal abstraction and restraint based on answer abstraction are instances of tripwires. A tripwire allows a developer to specify that a property of an evaluation should cause some intervention from the system. The intervention may be an automatic change in the resolution method, such as with call abstraction or restraint; or the intervention could throw an error; or suspend the computation for debugging. $\mathcal{E}$ rgoAI also supports a max answers tripwire that allows a user to set a limit on the number of answers a given subgoal $S$ may have. If this limit is reached, a new answer $A_S$ is added that is a variant of $S$ , the truth value of $A_S$ is set to u and $S$ is completed. Afterward, queries to $S$ will return all of the derived answers for $S$ , as well as $A_S$ . The effect is to change the closed-world assumption for $S$ from using false as default to using u as default. Another kind of tripwire is the ability to time out a goal $G_{costly}$ that may either call $\mathcal{E}$ rgoAI or an external system. The tripwire can be set either to add an answer $A$ that is a variant of $G_{costly}$ with truth value u, or to throw an exception. Finally, as mentioned in Section 7, a negative subgoal that cannot be ground via delaying its execution can be given the truth value u instead of throwing an error.

In each of these types of tripwire a developer can weigh the benefit of a bounded execution time against the possibility of deriving a set of answers that are informationally sound but not complete. It is because of such uses that we denote the third WFS truth value as u, since it can mean unknown in addition to undefined.Footnote ²⁶

11.1 Performance comparison for petri net reachability

Our first benchmark addresses the problem of reachability in 1-safe Petri Nets, to which the central problems of liveness, deadlock-freedom, and the existence of home states can be reduced (cf. Rozenberg and Engelfriet (Reference Rozenberg and Engelfriet1998)). The benchmark, from Marques et al. (Reference Marques, Swift and Cunha2008), combines tabled and non-tabled code,Footnote ²⁸

A 1-safe Petri Net is a digraph of places and transitions: in Figure 9 the set of places is {p1,p2,b1,b2,c1,c2} while the set of transitions is {t1,t2,t3,t4}. Transitions are represented as facts such as:

indicating that if tokens are in places b1 and c1, then transition t1 can fire, placing tokens in b2 and c2. The state of a given Petri Net is represented as a list of the places that contain a token: for example, in Figure 9 the state is represented as [b1,c1,p1].

Fig. 9.

Illustration of a 1-safe petri net.

Figure 10 compares $\mathcal{E}$ rgoAI and XSB for reachability queries to various sizes of generated Petri Nets. Note that both the time and space for $\mathcal{E}$ rgoAI scale nearly linearly to a net with 8 million states, after which point RAM contention becomes an issue. XSB’s elapsed times are 4.7–6.0 times faster than $\mathcal{E}$ rgoAI’s, while XSB’s space is 4.0–4.7 times smaller than $\mathcal{E}$ rgoAI’s.

Fig. 10.

$\mathcal{E}$ rgoAI /XSB elapsed time and space for petri net reachability.

11.2 Performance comparison for tabled resolution

Left-recursive transitive closure is a good benchmark for tabling, since tabling performs nearly all computation apart from accessing the graph edges. Figure 11 shows tests over a chain, a cycle, and a chain in which all vertices have a self-loop. For $\mathcal{E}$ rgoAI, measurements are performed for left-recursion over both HiLog predicates and frames. In these evaluations, left-recursion in frames incurs a 20–40% time overhead over predicates in $\mathcal{E}$ rgoAI. This is because a frame query Id[Attr->?Val] must check for answers through inheritance in addition to those obtained through transitive closure. For predicates, $\mathcal{E}$ rgoAI’s speed is consistently 3–4 times slower than XSB. The reason is that the table space used by $\mathcal{E}$ rgoAI is itself 3–4 times that of XSB due to $\mathcal{E}$ rgoAI’s explanation structures.Footnote ²⁹ CPU time scales linearly up to graphs with 100–200 million edges on this platform. Elapsed time has more variance, especially when the memory needed for table space by $\mathcal{E}$ rgoAI becomes nearly the size of RAM (e.g., 14.5 Gbytes required out of 16 Gbytes available).

Fig. 11.

CPU time/elapsed time in seconds, and space for left-recursive transitive closure.

Fig. 12.

Test predicates to compare non-tabled resolution.

11.3 Performance comparison for non-tabled resolution

General programming in $\mathcal{E}$ rgoAI supports an open approach to knowledge formats, communicates with other components in a software stack, drives user interfaces, and enables much other functionality. $\mathcal{E}$ rgoAI is well equipped to support general programming because it does not need to ground the entire program to evaluate a query and because it supports data structures through logical terms. We use two simple predicates to benchmark general programming: makelist/2 to construct a list, and iter/2 to iterate through a loop (Figure 12). Both predicates perform structural recursion and do not need tabling.

The $\mathcal{E}$ rgoAI declaration :- prolog{f/n} causes a predicate to be compiled without tabling, although f/n is compiled with $\mathcal{E}$ rgoAI features such as the ability to be disabled (Section 8) and with two explanation arguments.

We call such rules quasi-Prolog rules. As noted previously $\mathcal{E}$ rgoAI can also call and be called from XSB Prolog, which provides another means to execute gemeral programming tasks.

Figures 13 and 14 compare these $\mathcal{E}$ rgoAI execution methods with both static and dynamic Prolog code, where static code undergoes a deeper compilation process than dynamic code, but unlike dynamic code cannot be modified. Figure 13 compares these execution methods on makelist/2. All methods are able to scale to lists with ten million elements. $\mathcal{E}$ rgoAI calling static XSB code takes about the same time as XSB calling static XSB code. These methods are faster than both $\mathcal{E}$ rgoAI quasi-Prolog rules and XSB dynamic code. However $\mathcal{E}$ rgoAI quasi-Prolog rules do not scale linearly for makelist/2. Analysis showed that non-linearity is due to the creation on the heap of explanation structures that contain large lists. Indeed, when XSB’s heap garbage collection is turned off, $\mathcal{E}$ rgoAI quasi-Prolog rules scale in a nearly linear manner. As confirmation, Figure 14 shows linear scaling for quasi-Prolog rules on iter/1 which does not create large structures.

Fig. 13.

Elapsed times in seconds to create lists of varying lengths using makelist/2.

Fig. 14.

Elapsed times in seconds for varying iterations using iter/1 in $\mathcal{E}$ rgoAI and/or XSB.

11.4 Comparison of internal data stores

$\mathcal{E}$ rgoAI can access large factual knowledge bases in several ways, including:

• • As full HiLog facts, loaded directly into $\mathcal{E}$ rgoAI’s internal knowledge store or accessed from external databases; or

• • As Prolog facts, loaded into XSB’s internal knowledge store; or

• • As Prolog terms, accessed via Python connectors through Janus

As a scalability experiment, a KG of 11,847,275 triples from the DARPA AIDA project (cf. Section 6) was loaded into the knowledge stores of $\mathcal{E}$ rgoAI and XSB.

• • Loading the KG as $\mathcal{E}$ rgoAI HiLog facts. Using $\mathcal{E}$ rgoAI’s fastload the KG was loaded at a rate of about 59,000 facts per second of elapsed time. $\mathcal{E}$ rgoAI’s fastload uses trie indexing Ramakrishnan et al. (Reference Ramakrishnan, Rao, Sagonas, Swift and Warren1999).

• • Loading the KG directly into Prolog. Using XSB’s dynamic loading, the KG was loaded with full indexing on each fact (7 indexes) at a rate of about 137,000 facts per second of elapsed time.

Of course, $\mathcal{E}$ rgoAI also has its own interfaces for SQL, SPARQL, XML, RDF, and other data sources. For knowledge in virtually any other format, $\mathcal{E}$ rgoAI can access Python libraries through the high-speed Janus interface (Section 3.2).

To summarize the overall performance and scalability results, $\mathcal{E}$ rgoAI is nearly as fast and scalable as tabled Prolog, while providing numerous sophisticated KRR features. For many applications these features are well worth the cost in terms of expressiveness, ease of maintenance, and updatability. Put another way, $\mathcal{E}$ rgoAI is a KRR system with scalability and performance similar to a programming system.