% excerpts of RuleML abstract syntax specification % GBNF intro, and GBNF specification of Situated Courteous LP RuleML. % based on draft *-v12 of that RuleML abstract syntax specification % excerpts from GBNF and SCLP sections. % by Benjamin Grosof. % created 3/28/03, then presented at DAML PI Meeting Rules Breakout % modified 4/22/03 then presented at Joint Committee telecon % (http://www.daml.org/committee) % revised 4/23/03 to fix a few bugs I. Introduction to GBNF Our notation for abstract syntax is called GBNF ("Generalized BNF for semi-structured data" or "Grosof BNF"). GBNF is an extended variant of EBNF. GBNF provides a bit more detail than an EBNF specification, with the aim of helping to specify schemas for semi-structured data, e.g., in XML-Schema and OWL/RDF. It makes more explicit: - the content/children of an element; - unorderedness vs. orderedness; - attributes as a (syntactically) special kind of symbol; and - default values of attributes. GBNF statements are of three kinds: (1) ordinary production (a.k.a. "macro") similar to EBNF, (2) containment production, and (3) attribute-default. A macro production is similar in spirit to an ordinary EBNF production. A containment production specifies the "content" of a symbol viewed as an element in XML. GBNF includes both unordered concatenation and ordered concatenation. Attributes are treated as a kind of element. An attribute-default statement specifies the default values for an attribute. The extensions of GBNF relative to EBNF are the following: 1. containment productions (":"): GBNF defines a special kind of production, called a "containment", which expresses that the rhs of the production is intended to be "content" (essentially, in the XML sense) of the lhs. A containment production uses ":" to separate its lhs and rhs. A non-containment production is called a "macro". 2. explicit indication of whether concatenation is ordered ("\") vs. unordered: "," in GBNF means unordered concatenation. "\" in GBNF means ordered concatentation. 3. attribute-default statements: "myattrib $ myvalue ;" specifies that the default value of the attribute "myattrib" is "myvalue". 4. attribute prefix In "@mysymbol", the "@" prefix indicates that "mysymbol" is an attribute symbol (and thus for example could have a default value). A GBNF specification can simply be read as EBNF, without fear of being misled -- simply: 1. Interpret ":" as "=". (":" is a special "containment" kind of production.) 2. Interpret "\" as ",". Ignore every "\" before "*" or "+". ("\" is the ordered concatenation symbol.) 3. Ignore every "$" statement. (A "$" statement's rhs defines a default value for an attribute.) 4. Ignore every "@" prefix. (The "@" prefix indicates a symbol is an attribute.) ":" defines a containment. "=" defines a macro. "," means unordered concatenation. "\" means ordered concatenation. "|" separates alternatives (disjunctively). "*" means unordered Kleene star -- zero or more repetitions, concatenated. "?" means optional inclusion. "+" means one or more repetitions, concatenated and unordered. "(...)" delimits an expression. ";" delimits the end of a statement. "\*" is the ordered version of "*". "\+" is the ordered version of "+". "@" prefixes an attribute. "$" defines the default value for an attribute. "/* ... */" delimits a comment. II. GBNF specification of SCLP RuleML V0.8 /* GBNF specification of SCLP (Situated Courteous Logic Programs) RuleML V0.8 */ /* The following is the specification of Situated Courteous LP sub-language of RuleML V0.8 -- a very expressive one yet still tractable when the Herbrand universe is polynomial-size. GBNF enables this specification to be quite concise. Upper case below flags some terminals, for convenience. "PCDATA" and "CDATA" and "URI" are intended to mean what they do in XML. Observe that the only usage of ordered concatentation is for tuples of arguments (and similarly sensor binding patterns defined over tuples of arguments). */ rulebase : _rbaselab? , _statements , @direction , @xmlns:xsi, @xsi:noNamespaceSchemaLocation; _statements = (imp | fact | query | mutex | sens | effe)* ; @direction : (forward | backward | bidirectional) ; @direction $ bidirectional ; @xmlns:xsi : URI ; /* this and the next attribute help specify a XML Schema */ @xsi:noNamespaceSchemaLocation : URI ; _rbaselab : ind | cterm ; imp : _rlab? , _head , _body ; fact : _rlab? , _head ; query : _rlab? , _body ; /* "query" element is an EXPERIMENTAL feature: a quick way to specify a query to a RuleML-speaking system */ _rlab : ind | cterm ; _head : (cslit | (atom)) | andh ; _body : bodyexpr ; bodyexpr = (fclit | (cslit | flit | atom)) | ((andb | and) | orb) ; and : (atom)*; andb : (bodyexpr)* ; orb : (bodyexpr)+ ; andh : ((cslit | atom) | andh)+ ; _opr : rel ; _args = (ind | var | cterm | tup | roli)\* ; /* implicitly top-level is an ordered tuple */ /* Benjamin recommends the rhs be changed to simply (tup | roli), and that the _modli containment below be similarly modified */ cslit : _opr , _args , @cneg ; fclit : _opr , _args , @cneg, @fneg ; flit : _opr , _args , @fneg ; atom : _opr , _args ; @cneg : bool ; @cneg $ no; @fneg : bool ; @fneg $ $ no; bool = yes | no ; rel : constname ; ind : constname ; ctor : constname ; constname = PCDATA , @href? ; @href : URI ; URI = CDATA ; var : PCDATA ; cterm : _opc , _args ; _opc : ctor ; tup : (ind | var | cterm | tup | roli)\* ; roli : (_arv)* ; _arv : arole, (ind | var | cterm | tup | roli) ; arole : constname ; /* Note an alternative syntax for roli's (with '<_r n="...">' elements) has been used by Harold Boley in some of his presentations on object-oriented features in RuleML. */ /* courteous features stuff */ mutex : _oppo , _mgiv? ; _oppo : ando ; _mgiv : bodyexpr ; ando : (cslit | atom) , (cslit | atom) ; /* situated features stuff */ sens : _opr , _aproc, _modli? ; effe : _opr , _aproc ; _aproc = jproc | uproc ; uproc : constname ; jproc : clas, meth, path? ; path : constname ; clas : constname ; meth : constname ; _modli : (bmode | bmtup | bmroli)\* ; bmtup : (bmode | bmtup | bmroli)\* ; bmroli : (_arbm)* ; _arbm : arole, (bmode | bmtup | bmroli) ; bmode : @bval ; @bval : bind ; bind = bound | free; @bval $ free ; /* end of GBNF specification */ III. Some Documenting Comments about the GBNF specification /* Explanation of Abbreviations and Expressive Concepts: rulebase = knowledge base of rules. direction = intended direction of inferencing. _rbaselab = rulebase label. Name of a rulebase. imp = implication rule. (Note it does not employ *material* implication cf. classical logic.) fact: Can be viewed logically as an implication rule that has an empty body. _head = head of a rule. A.k.a. the "consequent" or "then" part of the rule. _body = body of a rule. A.k.a. the "antecedent" or "if" part of the rule. _rlab = rule label. Name of a rule. andb = AND'd (i.e., conjunctive) expression permitted in the body. and = AND'd (i.e., conjunctive) expression - a particular kind that is permitted in the body. The "and" of some body atoms. Similar to andb, but simpler. Included for down-compatibility / back-compatibility, esp. with early versions of the Datalog and Hornlog sublanguages. atom = logical atom. An expression formed from a predicate applied to a collection of its (logical) arguments. _opr = relational operator expression. (This is for sake of upward expressive extensibility.) rel = relation. A logical predicate. var = variable. A logical variable. ind = individual. A logical individual. (Can be viewed logically as logical function whose arity is zero.) "Lloyd-Topor And-Or" ("LTAO") feature syntax follows: Lloyd-Topor transformations permit more expressive heads and bodies in LP, by expressively reducing them (with tractable computational effort) to the simpler, more basic LP expressive form in which a head consists of a single literal and a body consists of a conjunction of literals. In particular, it is straightforward to permit "OR" (disjunction) expressions in the body, and to permit "AND" (conjunction) expressions in the head. We call this the "Lloyd-Topor And-Or" ("LTAO") feature. orb = OR'd (i.e., disjunctive) expression permitted in the body. Note that andb's and orb's can be nested. andh = AND'd (i.e., conjunctive) expression permitted in the head. Negation-As-Failure (a.k.a. "Normal" or "Ordinary" LP) feature syntax follows: flit = negation-as-failure literal. A literal with negation-as-failure sign (fneg). fneg = negation-as-failure sign. The sign is either positive or negative. Negative ("YES" value of attribute) means negated. Positive ("NO" value of attribute) means unnegated, i.e., the same as if the negation symbol does not appear. bool = boolean. "Extended" LP feature syntax follows: Note SCLP permits literals to be classically negated, in the manner of "extended" LP originated by Gelfond & Lifschitz. This is a limited sense of classical negation; it is actually expressively inessential. Let "cneg" stand for classical negation. For every predicate P, " cneg P " is essentially treated as if it were rewritten " P' ", where " P' " is a newly introduced predicate symbol. cslit = classically signed literal, a.k.a. classical literal. A literal with classical-negation sign (cneg). fclit = negation-as-failure classically signed literal. A literal with both classical-negation sign (cneg) and negation-as-failure sign (fneg). cneg = classical negation sign. The sign is either positive or negative. Negative ("YES" value of attribute) means negated. Positive ("NO" value of attribute) means unnegated, i.e., the same as if the negation symbol does not appear. URI constants feature syntax follows: constname = (logical-) constant name. In this version, permits a URI. Complex (constructor) terms feature syntax follows: cterm = complex term. A logical term of the form "f(...)" where f is a ctor. _opc = constructor operator expression. (Similar in spirit to _opr.) ctor = constructor. A logical function. Object-oriented argument collections feature syntax follows: tup = tuple of arguments. An ordered collection of arguments. roli = role'd list of arguments. An unordered collection of arguments, with each member of the collecion being distinguished by an argument role name (arole). _arv = argument role-value pair. An argument (value) together with its indicating argument role (arole). arole = argument role. (See roli and _arv above.) "Query element" feature syntax follows: query = stored query specification. An EXPERIMENTAL feature. (If "query" element is indeed included in this version.) Note that in this DTD version, tup's and roli's can be nested. This is an EXPERIMENTAL aspect of the object-oriented argument collections feature. Courteous feature syntax follows: In Courteous LP, rules are treated as defaults, and prioritized conflict handling can be represented. Priorities between rules are represented via a binary predicate "overrides" which takes rule labels as arguments. "overrides" is syntactically reserved, but is otherwise an ordinary predicate - it can appear in general-form rules and be reasoned about, thus "overrides" facts can be inferred. Higher priority rules defeat lower priority rules. The prioritization ordering is a partial ordering. mutex = mutual exclusion statement (a.k.a. "mutex"). A mutex is a kind of integrity constraint, used to specify the scope of conflict in Courteous logic programs. It contains an opposer part and a given-condition part. The opposer part consists of two (classical) literals. The given-condition part is similar to a rule body. The mutex specifies overall that it is a prohibited contradiction for the two literals to be concluded if the given-condition part is concluded (i.e., holds). The semantics of Courteous LP enforces consistency with respect to this integrity constraint. A typical usage of a mutex is to specify that a predicate is (partial-)functional, e.g., that one should not conclude two different values for the price of the same item. OWL (and Description Logic) has the same notion of (partial-) functionality as something one can specify for properties. _oppo = opposer part of mutex. (See mutex above.) _mgiv = given part of mutex. (See mutex above.) ando = AND'd (i.e., conjuctive) expression permitted in the opposer part of a mutex. (See mutex above.) Situated feature syntax follow: sens = sensor link statement. Sensing overall is the obtaining of facts from external attached procedures, during the testing of rules that contain particular kinds of literals. "External" here means external to the LP inferencing engine. A sensor link statement specifies an association of a predicate P to an attached procedure A. "A" is also known as a "sensor procedure". Essentially, A can be viewed as a queryable virtual knowledge base of facts about P. Let R be a rule in which literal L appears in the body, where L's predicate is P. During (situated LP) inferencing, when L's body is tested, A is invoked. A sensor link statement also specifies an optional binding restriction pattern: i.e., for each of P's arguments, it can restrict that argument to be bound (rather than a free variable or cterm containing a free variable) when A is invoked (i.e., queried). effe = effector link statement. Effecting overall is the performing of side-effectful actions, via invoking external attached procedures, triggered by the drawing of particular kinds of conclusions. "External" here means external to the LP inferencing engine. An effector link statement specifies an association of a predicate P to an attached procedure A. "A" is also known as an "effector procedure". Let literal L appear in the head of some rule(s), where L's predicate is P. During (situated LP) inferencing, suppose P(U) is concluded, where U is an instantiation of L's argument terms. Then A is invoked with instantiation U. Note in this version, the sensed or effected literal might not actually be permitted to be classically-negated (i.e., if no cneg is specified in the sens or effe statement). However, such a restriction is expressively inessential. _aproc = attached procedure. (See sens and effe above.) jproc = Java (attached) procedure. In the current EXPERIMENTAL design, a Java attached procedure is specified by its class, method, and (optional) path. uproc = "universal" (attached) procedure. I.e., a procedure specified via some kind of stringname or URI. This is an EXPERIMENTAL design. It is intended to support extensibility towards CGI's and Web services. _modli = binding mode list. A binding restriction pattern for a sensor. (See sens above.) bmode = binding mode. Indicates whether a particular argument is restricted to be bound vs. permitted to be a free variable or contain a free variable. (See sens above.) bval = binding value. (See bmode above.) bmtup = tuple (tup) of binding modes. bmroli = role'd list (roli) of binding modes. */