ASP RuleML
ASP RuleML is an approach to accommodate the RuleML language to express answer-set programs. It consists of a layered family of XML schemas, derived from the RuleML Datalog dialect, extending it in order to capture a variety of ASP-related language features.
The framework presented here is supposed to be a starting point that prompts both the Semantic Web and the ASP community to discuss and achieve a comprehensive RuleML interchange format for the ASP semantics. It is work in progress which, as we believe, will attract other participants after initial dissemination.
The Language
The new sublanguage currently consists of two layers:
- ASP Base
- ASP Oracle
ASP Base encapsulates the syntax of traditional answer-set programs. ASP Oracle facilitates the expression of a number of advanced constructs which are provided by current ASP solvers, such as aggregates, built-ins or external atoms, by a general syntactical element.
ASP Base
The language that underlies the ASP semantics described in the seminal
paper of Gelfond and Lifschitz [1] can be regarded as
the core language of answer-set programming and constitutes the
language variant we call ASP Base. It corresponds to disjunctive
Datalog, extended with strong negation and constraints (i.e., rules
with empty head). The language is defined in aspbase.xsd
and
derives from the schema nafnegdatalog with the following main
modifications:
- restricting rule bodies to be the conjunction of (poss. weakly negated) literals, and
- allowing disjunction of literals in rule heads.
This defines the core dialect that serves as a base for various ASP extensions.
ASP Oracle
Several state-of-the-art answer-set solvers such as DLV or Smodels provide specific language extensions. Such extensions either represent a special kind of atom, like custom built-in predicates or aggregate atoms, or constructs that aim at adding qualitative information to the result, like weak constraints. Although each of these extensions has a well-defined semantics, they mostly remain specific to a particular reasoner and are not portable in the sense of a universal ASP syntax. We propose a syntactic entity, called oracle atom, offering a general and versatile as a most general representation for such sophisticated, ASP-related language features.
Informally, an oracle atom consists of
- a predicate (relation) name,
- an input list, and
- an output list,
where the elements of both lists are terms and literals. An oracle atom can occur wherever an ordinary atom is allowed; it has an input list and an output list of either terms or literals.
The process of giving semantics to oracles is up to the specific reasoners, respectively translators which convert the ASP program from RuleML to a textual representation tailored to such a reasoner. We emphasize the fact that an oracle atom is a pure syntactic instrument to express any language feature which goes beyond the traditional elements of answer-set programming, i.e., (possibly weakly negated) Literals. Considering the substantial number of such features which are provided by DLV and Smodels alone, a separate RuleML syntax for each of them would result in a complex and unmanageable set of highly specific language elements. Permitting the usage of string terms in input and output lists of the oracle eventually allows for arbitrarily complex functionalities.
By adding the oracle atom to ASP Base, we define the schema ASP oracle, which is capable of syntactically embracing most of these features.
Implementation
ASP Base is defined by aspbase.xsd
and derives from the RuleML variant nafnegdatalog, adding head
disjunction and constraints. ASP Oracle is defined by asporacle.xsd
, building on ASP Base and
adding the oracle atom.
Examples
Consider a rule with a comparative predicate, such as
The sign >
is intuitive, but cannot be translated into an
XML syntax in a straightforward way. However, since Y > X
stands for an atom, we can represent it by the following XML construct,
which can be used wherever an <Atom>
element is allowed:
<Oracle> <Rel>greaterThan</Rel> <Input> <Var>Y</Var> <Var>X</Var> </Input> </Oracle>
Another example illustrates the expression of a more sophisticated construct. Smodels allows for the specification of so-called cardinality constraints, that filters the models by occurence of specific combination of literals (cf. [2]). This cardinality constraint
could be represented by the following oracle:
<Oracle> <Rel>cardCons</Rel> <Input> <Data xsi:type="xs:integer">1</Data> <Atom> <Rel>a</Rel> <Atom> <Atom> <Rel>b</Rel> <Atom> <Naf> <Atom> <Rel>c</Rel> <Atom> <Naf> <Data xsi:type="xs:integer">2</Data> </Input> </Oracle>
Instead of specifying fixed bounds, also variables can be given, like
<Var>X</Var>
. At least one bound must be specified
- if both are given, their position within the input-list determines whether the
respective value is a lower or an upper bound.
Another construct of Smodels, the weight constraint, which assigns weights to literals inside a constraint, such as
could be realized by nesting oracles:
<Oracle> <Rel>weightCons</Rel> <Input> <Data xsi:type="xs:double">1.2</Data> <Oracle> <Rel>assign</Rel> <Input> <Atom> <Rel>a</Rel> <Ind>p</Ind> <Atom> <Data xsi:type="xs:double">1.0</Data> </Input> </Oracle> <Oracle> <Rel>assign</Rel> <Input> <Atom> <Rel>b</Rel> <Ind>p</Ind> <Ind>z</Ind> <Atom> <Data xsi:type="xs:double">0.02</Data> </Input> </Oracle> <Oracle> <Rel>assign</Rel> <Input> <Naf> <Atom> <Rel>c</Rel> <Ind>q</Ind> <Atom> <Naf> <Data xsi:type="xs:double">0.04</Data> </Input> </Oracle> <Data xsi:type="xs:double">1.03</Data> </Input> </Oracle>
Here, the assignment of numerical values to specific literal is realized through oracles, which are then specified in the input list of the weight constraint oracle.
Further dialects
A type of program which needs a further schema extension are
HEX-programs [3], which also allow for variable predicate
symbols, facilitating a simple higher-order syntax. The distinctive feature of
HEX-programs are external atoms, providing an interface to an arbitrary
external source of computation under well-defined semantics. The characteristic
feature of HEX-atoms is to foster a loose coupling between the logic program
and the external source, while facilitating a bidirectional flow of information.
External atoms can be accomodated by oracle atoms in a straighforward way, their
semantics is determined by the respective external evaluation function.
The asphex.xsd
schema modifies ASP Oracle by allowing variable predicate
symbols. The intuition behind oracle atoms used in ASP HEX is to interpret them
as external atoms.
For instance, the external atom
<Oracle> <Rel>rdf</Rel> <Input> <Var>A</Var> </Input> <Output> <Var>X</Var> <Var>Y</Var> <Var>Z</Var> </Output> </Oracle>
Translators
We implemented translators to convert answer-set programs from classical datalog-syntax into ASP RuleML and back. Try it!
ASP:References
[1] M. Gelfond and V. Lifschitz. Classical Negation in Logic Programs and Disjunctive Databases. New Generation Computing, 9:365--385, 1991.[2] I. Niemelä, P. Simons, and Tommi Syrjänen. Smodels: A System for Answer Set Programming. CoRR, cs.AI/0003033, 2000. http://arxiv.org/abs/cs.AI/0003033
[3] T. Eiter, G. Ianni, R. Schindlauer, and H. Tompits. A Uniform Integration of Higher-Order Reasoning and External Evaluations in Answer Set Programming. In Proc. IJCAI-05, pp. 90--96, 2005.