1 Scope

This specification defines a concrete syntax for the FIPA Semantic Language (SL) content language. This syntax and its associated semantics are suggested as a candidate content language for use in conjunction with the FIPA Agent Communication Language (see [FIPA00037]). In particular, the syntax is defined to be a sub-grammar of the very general s-expression syntax.

2 Grammar FIPA SL Concrete Syntax

This content language is denoted by the normative constant fipa-sl in the :language parameter of an ACL message. See Section 6 for an explanation of the used syntactic notation.

Content = "(" ContentExpression+ ")".

ContentExpression = IdentifyingExpression

| ActionExpression

| Proposition.

Proposition = Wff.

Wff = AtomicFormula

| "(" UnaryLogicalOp Wff ")"

| "(" BinaryLogicalOp Wff Wff ")"

| "(" Quantifier Variable Wff ")"

| "(" ModalOp Agent Wff ")"

| "(" ActionOp ActionExpression ")"

| "(" ActionOp ActionExpression Wff ")".

UnaryLogicalOp = "not".

BinaryLogicalOp = "and"

| "or"

| "implies"

| "equiv".

AtomicFormula = PropositionSymbol

| "(" BinaryTermOp TermOrIE TermOrIE ")"

| "(" PredicateSymbol TermOrIE+ ")"

| "true"

| "false".

BinaryTermOp = "="

| "result".

Quantifier = "forall"

| "exists".

ModalOp = "B"

| "U"

| "PG"

| "I".

ActionOp = "feasible"

| "done".

TermOrIE[1] = Term

| IdentifyingExpression.

Term = Variable

| FunctionalTerm

| ActionExpression

| Constant

| Sequence

| Set.

IdentifyingExpression = "(" ReferentialOperator TermOrIE Wff ")".

ReferentialOperator = "iota"

| "any"

| "all".

FunctionalTerm = "(" FunctionSymbol TermOrIE* ")"

| "(" FunctionSymbol Parameter* ")".

Constant = NumericalConstant

| String

| DateTime.

NumericalConstant = Integer

| Float.

Variable = VariableIdentifier.

ActionExpression = "(" "action" Agent TermOrIE ")"

| "(" "|" ActionExpression ActionExpression ")"

| "(" ";" ActionExpression ActionExpression ")".

PropositionSymbol = String.

PredicateSymbol = String.

FunctionSymbol = String.

Agent = TermOrIE.

Sequence = "(" "sequence" TermOrIE* ")".

Set = "(" "set" TermOrIE* ")".

Parameter = ParameterName ParameterValue.

ParameterValue = TermOrIE.

2.1 Lexical Definitions

All white space, tabs, carriage returns and line feeds between tokens should be skipped by the lexical analyser. See Section 6 for an explanation of the used notation.

String = Word

| ByteLengthEncodedString

| StringLiteral.

ByteLengthEncodedString = "#" DecimalLiteral+ "\"" <byte sequence>.

Word = [~ "\0x00" - "\0x20", "(", ")", "#", "0" - "9", ":", "-", "?"]

[~ "\0x00" - "\0x20", "(", ")"]*.

ParameterName = ":" String.

VariableIdentifier = "?" String.

Sign = [ "+" , "-" ].

Integer = Sign? DecimalLiteral+

| Sign? "0" ["x", "X"] HexLiteral+.

Dot = "."

Float = Sign? FloatMantissa FloatExponent?

| Sign? DecimalLiteral+ FloatExponent.

FloatMantissa = DecimalLiteral+ Dot DecimalLiteral*

| DecimalLiteral* Dot DecimalLiteral+.

FloatExponent = Exponent Sign? DecimalLiteral+.

Exponent = ["e","E"].

DecimalLiteral = ["0" - "9"].

HexLiteral = ["0" - "9", "A" - "F", "a" - "f"].

StringLiteral = "\""( [~ "\""]

| "\\\"" )*"\"".

DateTime = Sign? Year Month Day "T" Hour Minute

Second MilliSecond TypeDesignator?.

Year = DecimalLiteral DecimalLiteral DecimalLiteral DecimalLiteral.

Month = DecimalLiteral DecimalLiteral.

Day = DecimalLiteral DecimalLiteral.

Hour = DecimalLiteral DecimalLiteral.

Minute = DecimalLiteral DecimalLiteral.

Second = DecimalLiteral DecimalLiteral.

MilliSecond = DecimalLiteral DecimalLiteral DecimalLiteral.

TypeDesignator = ["a" - "z" , "A" – "Z"].

3 Notes on FIPA SL Semantics

This section contains explanatory notes on the intended semantics of the constructs introduced in above.

3.1 Grammar Entry Point: FIPA SL Content Expression

An FIPA SL content expression may be used as the content of an ACL message. There are three cases:

· A proposition, which may be assigned a truth value in a given context. Precisely, it is a well-formed formula (Wff) using the rules described in the Wff production. A proposition is used in the inform communicative act (CA) and other CAs derived from it.

· An action, which can be performed. An action may be a single action or a composite action built using the sequencing and alternative operators. An action is used as a content expression when the act is request and other CAs derived from it.

· An identifying reference expression (IRE), which identifies an object in the domain. This is the Referential operator and is used in the inform-ref macro act and other CAs derived from it.

Other valid content expressions may result from the composition of the above basic cases. For instance, an action-condition pair (represented by an ActionExpression followed by a Wff) is used in the propose act; an action-condition-reason triplet (represented by an ActionExpression followed by two Wffs) is used in the reject-proposal act. These are used as arguments to some ACL CAs in [FIPA00037].

3.2 Well-Formed Formulas

A well-formed formula is constructed from an atomic formula, whose meaning will be determined by the semantics of the underlying domain representation or recursively by applying one of the construction operators or logical connectives described in the Wff grammar rule. These are:

· (not <Wff>)

Negation. The truth value of this expression is false if Wff is true. Otherwise it is true.

· (and <Wff0> <Wff1>)

Conjunction. This expression is true iff[2] well-formed formulae Wff0 and Wff1 are both true, otherwise it is false.

· (or <Wff0> <Wff1>)

Disjunction. This expression is false iff well-formed formulae Wff0 and Wff1 are both false, otherwise it is true.

· (implies <Wff0> <Wff1>)

Implication. This expression is true if either Wff0 is false or alternatively if Wff0 is true and Wff1 is true. Otherwise it is false. The expression corresponds to the standard material implication connective Wff0 Þ Wff1.

· (equiv <Wff0> <Wff1>)

Equivalence. This expression is true if either Wff0 is true and Wff1 is true, or alternatively if Wff0 is false and Wff1 is false. Otherwise it is false.

· (forall <variable> <Wff>)

Universal quantification. The quantified expression is true if Wff is true for every value of value of the quantified variable.

· (exists <variable> <Wff>)

Existential quantification. The quantified expression is true if there is at least one value for the variable for which Wff is true.

· (B <agent> <expression>)

Belief. It is true that agent believes that expression is true.

· (U <agent> <expression>)

Uncertainty. It is true that agent is uncertain of the truth of expression. Agent neither believes expression nor its negation, but believes that expression is more likely to be true than its negation.

· (I <agent> <expression>)

Intention. It is true that agent intends that expression becomes true and will plan to bring it about.

· (PG <agent> <expression>)

Persistent goal. It is true that agent holds a persistent goal that expression becomes true, but will not necessarily plan to bring it about.

· (feasible <ActionExpression> <Wff>)

It is true that ActionExpression (or, equivalently, some event) can take place and just afterwards Wff will be true.

· (feasible <ActionExpression>)

Same as (feasible <ActionExpression> true).

· (done <ActionExpression> <Wff>)

It is true that ActionExpression (or, equivalently, some event) has just taken place and just before that Wff was true.

· (done <ActionExpression>)

Same as (done <ActionExpression> true).

3.3 Atomic Formula

The atomic formula represents an expression which has a truth value in the language of the domain of discourse. Three forms are defined:

· A given propositional symbol may be defined in the domain language, which is either true or false,

· Two terms may or may not be equal under the semantics of the domain language, or,

· Some predicate is defined over a set of zero or more arguments, each of which is a term.

The FIPA SL representation does not define a meaning for the symbols in atomic formulae: this is the responsibility of the domain language representation and ontology. Several forms are defined:

· true false

These symbols represent the true proposition and the false proposition.

· (= Term1 Term2)

Term1 and Term2 denote the same object under the semantics of the domain.

Other predicates may be defined over a set of arguments, each of which is a term, by using the (PredicateSymbol Term+) production.

The FIPA SL representation does not define a meaning for other symbols in atomic formulae: this is the responsibility of the domain language representation and the relative ontology.

3.4 Terms

Terms are either themselves atomic (constants and variables) or recursively constructed as a functional term in which a functor is applied to zero or more arguments. Again, FIPA SL only mandates a syntactic form for these terms. With small number of exceptions (see below), the meanings of the symbols used to define the terms are determined by the underlying domain representation.

Note that, as mentioned above, no legal well-formed expression contains a free variable, that is, a variable not declared in any scope within the expression. Scope introducing formulae are the quantifiers (forall, exists) and the reference operators iota, any and all. Variables may only denote terms, not well-formed formulae.

3.5 Referential Operators

3.5.1 Iota

· (iota <term> <formula>)

The iota operator introduces a scope for the given expression (which denotes a term), in which the given identifier, which would otherwise be free, is defined. An expression containing a free variable is not a well-formed FIPA SL expression. The expression (iota x (P x)) may be read as “the x such that P [is true] of x”. The iota operator is a constructor for terms which denote objects in the domain of discourse.

Notice that, unlike a term, an identifying expression can have different interpretations by different agents because its formal definition depends on the KB.

· Formal Definition

A iota expression can only be evaluated with respect to a given theory. Suppose KB is a knowledge base such that T (KB) is the theory generated from KB by a given reasoning mechanism. Formally, i(t, f)=qt iff qt is a term that belongs to the set S={qt: qfÎT (KB)} and S is a singleton; or i(t, f) is undefined if S is not a singleton. In this definition q is a most general variable substitution, qt is the result of applying q to t, and qf is the result of applying q to f. This implies that a failure occurs if no object or more than one object satisfies the condition specified in the iota operator.

If i(t, f) is undefined then any term, identifying expression or well-formed formula containing i(t, f) is also undefined.

· Example 1

This example depicts an interaction between agent A and B that makes use of the iota operator, where agent A is supposed to have the following knowledge base KB={P(A), Q(1, A), Q(1, B)}.

(query‑ref

:sender (agent-identifier :name B)

:receiver (set (agent-identifier :name A))

:content

"((iota ?x (p ?x)))"

:language fipa-sl

:reply‑with query1)

(inform

:sender (agent-identifier :name A)

:receiver (set (agent-identifier :name B)

:content

" ((= (iota ?x (p ?x)) a)) "

:language fipa-sl

:in‑reply‑to query1)

The only object that satisfies proposition P(x) is a, therefore, the query‑ref message is replied by the inform message as shown.

· Example 2

This example shows another successful interaction but more complex than the previous one.

(query‑ref

:sender (agent-identifier :name B)

:receiver (set (agent-identifier :name A))

:content

"((iota ?x (q ?x ?y)))"

:language fipa-sl

:reply‑with query2)

(inform

:sender (agent-identifier :name A)

:receiver (set (agent-identifier :name B))

:content

"((= (iota ?x (q ?x ?y)) 1))"

:language fipa-sl

:in‑reply‑to query2)

The most general substitutions q such that qQ(x, y) can be derived from KB are q₁={x/1, y/A} and q₂={x/1, y/B}. Therefore, the set S={qt: qfÎT(KB)}={{x/1, y/A}x, {x/1, y/B}x }={1} is a singleton and hence (iota ?x (q ?x ?y)) represents the object 1.

· Example 3

Finally, this example shows an unsuccessful interaction using the iota operator. In this case, agent A cannot evaluate the iota expression and therefore a failure message is returned to agent B

(query‑ref

:sender (agent-identifier :name B)

:receiver (set (agent-identifier :name A))

:content

"((iota ?y (q ?x ?y)))"

:language fipa-sl

:reply‑with query3)

(failure

:sender (agent-identifier :name A)

:receiver (set (agent-identifier :name B))

:content

"((action (agent-identifier :name A)

(inform‑ref

:sender (agent-identifier :name A)

:receiver (set (agent-identifier :name B))

:content

\"((iota ?y (q ?x ?y)))\"

:language fipa-sl

:in‑reply‑to query3))"

more‑than‑one‑answer)

:language fipa-sl

:in‑reply‑to query3)

The most general substitutions that satisfy Q(x, y) are q₁={x/1, y/a} and q₂={x/1, y/b}, therefore, the set S={qt: qfÎT(KB)}={{x/1, y/A}y, {x/1, y/B}y}={A, B}, which is not a singleton. This means that the iota expression used in this interaction is not defined.

3.5.2 Any

· (any <term> <formula>)

The any operator is used to denote any object that satisfies the proposition represented by formula.

Notice that, unlike a term, an identifying expression can have different interpretations by different agents because its formal definition depends on the KB.

· Formal Definition

An any expression can only be evaluated with respect to a given theory. Suppose KB is a knowledge base such that T(KB) is the theory generated from KB by a given reasoning mechanism. Formally, any(t, f)=qt iff qt is a term that belongs to the set S={qt: qfÎT(KB)}; or any(t, f) is undefined if S is the empty set. In this definition q is a most general variable substitution, qt is the result of applying q to t, and qf is the result of applying q to f.

If the set S is empty then any term, identifying expression or well-formed formula containing any(t, f) is undefined.

If the set S is not empty, then for any formula y containing any(t, f) let y' be the formula obtained from y by replacing any(t, f) with a variable x (not occurring in y) and let s_k be a new Skolem constant. Then y is true when {x/s_k}y' element_of T(KB union {t/s_k}f), y is false when {x/s_k}not(y’) element_of T(KB union {t/s_k}f), and otherwise y is undefined.

In other words if y contains any(t, f), y is true if a modified form of y obtained by replacing the any expression in it with a new constant s_k can be inferred based on the assumption that phi holds of s_k. y is false if not(y) inferred in a similar way. This definition is needed to avoid the following contradiction:

(implies

(and (= Stephen (any ?x (fipa-member ?x)))

(= Farooq (any ?x (fipa-member ?x))))

(= Stephen Farooq))

This definition implies that failures only occur if there are no objects satisfying the condition specified as the second argument of the any operator.

If any(t, f) is undefined then any term, identifying expression or well-formed formula containing any(t, f) is also undefined.

· Example 4

Assuming that agent A has the following knowledge base KB={P(A), Q(1, A), Q(1, B)}, this example shows a successful interaction with agent A using the any operator.

(query‑ref

:sender (agent-identifier :name B)

:receiver (set (agent-identifier :name A))

:content

"((any (sequence ?x ?y) (q ?x ?y)))"

:language fipa-sl

:reply‑with query1)

(inform

:sender (agent-identifier :name A)

:receiver (set (agent-identifier :name B))

:content

"((= (any (sequence ?x ?y) (q ?x ?y)) (sequence 1 a)))"

:language fipa-sl

:in‑reply‑to query1)

The most general substitutions q such that qQ(x, y) can be derived from KB are {x/1, y/A} and {x/1, y/B}, therefore S={qSequence(x, y): qQ(x, y)ÎT(KB)}={Sequence(1, A), Sequence(1, B)}. Using this set, agent A chooses the first element of S as the appropriate answer to agent B.

· Example 5

This example shows an unsuccessful interaction with agent A, using the any operator.

(query‑ref

:sender (agent-identifier :name B)

:receiver (set (agent-identifier :name A))

:content

"((any ?x (r ?x)))"

:language fipa-sl

:reply‑with query2)

(failure

:sender (agent-identifier :name A)

:receiver (set (agent-identifier :name B))

:content

"((action (agent-identifier :name A)

(inform‑ref

:sender (agent-identifier :name A)

:receiver (set (agent-identifier :name B))

:content

\"((any ?x (r ?x)))\"

:language fipa-sl

:in‑reply‑to query2))

(unknown‑predicate r))"

:language fipa-sl

:in‑reply‑to query2)

Since agent A does not know the r predicate, the answer to the query that had been sent by agent B cannot be determined, therefore a failure message is sent to agent B from agent A. The failure message specifies the failure’s reason (that is, unknown‑predicate r)

3.5.3 All

· (all <term> <formula>)

The all operator is used to denote the set of all objects that satisfy the proposition represented by formula.

Notice that, unlike a term, an identifying expression can have different interpretations by different agents because its formal definition depends on the KB.

· Formal Definition

An all expression can only be evaluated with respect to a given theory. Suppose KB is a knowledge base such that T(KB) is the theory generated from KB by a given reasoning mechanism. Formally, all(t, f)={qt: qfÎT(KB)}. Notice that all(t, f) may be a singleton or even an empty set. In this definition q is a most general variable substitution, qt is the result of applying q to t, and qf is the result of applying q to f.

If no objects satisfy the condition specified as the second argument of the all operator, then the identifying expression denotes an empty set.

· Example 6

Suppose agent A has the following knowledge base KB={P(A), Q(1, A), Q(1, B)}. This example shows a successful interaction between agent A and B that make use of the all operator.

(query‑ref

:sender (agent-identifier :name B)

:receiver (set (agent-identifier :name A))

:content

"((all (sequence ?x ?y) (q ?x ?y)))"

:language fipa-sl

:reply‑with query1)

(inform

:sender (agent-identifier :name A)

:receiver (set (agent-identifier :name B))

:content

"(( = (all (sequence ?x ?y) (q ?x ?y)) (set(sequence 1 a)(sequence 1 b))))"

:language fipa-sl

:in‑reply‑to query1)

The set of the most general substitutions q such that qQ(x, y) can be derived from KB is {{x/1, y/A}, {x/1, y/B}}, therefore all(Sequence(x, y), Q(x, y))={Sequence(1, A), Sequence(1, B)}.

· Example 7

Following Example 6, if there is no possible answer to a query making use of the all operator, then the agent should return the empty set.

(query‑ref

:sender (agent-identifier :name B)

:receiver (set (agent-identifier :name A))

:content

"((all ?x (q ?x c)))"

:language fipa-sl

:reply‑with query2)

(inform

:sender (agent-identifier :name A)

:receiver (set (agent-identifier :name B))

:content

"((= (all ?x (q ?x c))(set)))"

:language fipa-sl

:in‑reply‑to query2)

Since there is no possible substitution for x such that Q(x, C) can be derived from KB, then all(x, Q(x, c))={}. In this interaction the term (set) represents the empty set.

3.6 Functional Terms

A functional term refers to an object via a functional relation (referred by the FunctionSymbol) with other objects (that is, the terms or parameters), rather than using the direct name of that object, for example, (fatherOf Jesus) rather than God.

Two syntactical forms can be used to express a functional term. In the first form the functional symbol is followed by a list of terms that are the arguments of the function symbol. The semantics of the arguments is position-dependent, for example, (divide 10 2) where 10 is the dividend and 2 is the divisor. In the second form each argument is preceded by its name, for example, (divide :dividend 10 :divisor 2). The encoder is required to adopt the following criteria to select which form to use in order to represent a functional term. The first form, that is, the position-dependent form, should be used to encode all those functional terms for which the ontology does not specify the names of the parameters (for example, all the functions of the fipa-agent-management ontology). The second form, that is, the parameter-name dependent form, must be used to encode all those functional terms for which the ontology does specify the names of the parameters but not their position (for example, all the object descriptions of the fipa-agent-management ontology). This second form is particularly appropriate to represent descriptions where the function symbol should be interpreted as the constructor of an object, while the parameters represent the attributes of the object.

The following is an example of an object, instance of a vehicle class:

(vehicle

:colour red

:max-speed 100

:owner (Person

:name Luis

:nationality Portuguese))

Some ontologies may decide to give a description of some concepts only in one or both of these two forms, that is by specifying, or not, a default order to the arguments of each function in the domain of discourse. How this order is specified is outside the scope of this specification.

Functional terms can be constructed by a domain functor applied to zero or more terms.

3.7 Result Predicate

A common need is to determine the result of performing an action or evaluating a term. To facilitate this operation, a standard predicate result, of arity two, is introduced to the language. result/2 has the declarative meaning that the result of evaluating a term, or equivalently of performing an action, encoded by the first argument term, is the second argument term. However, it is expected that this declarative semantics will be implemented in a more efficient, operational way in any given FIPA SL interpreter.

A typical use of the result predicate is with a variable scoped by iota, giving an expression whose meaning is, for example, ”the x which is the result of agent i performing act”:

(iota x (result (action i act) x)))

3.8 Actions and Action Expressions

Action expressions are a special subset of terms. An action itself is introduced by the keyword action and comprises the agent of the action (that is, an identifier representing the agent performing the action) and a term denoting the action which is [to be] performed.

Notice that a specific type of action is an ACL communicative act (CA). When expressed in FIPA SL, syntactically an ACL communicative act is an action where the agent of the action is the sender of the CA, and the term denotes the CA including all its parameters where the performative should be used as a function symbol, as referred by the used ontology. Example 5 includes an example of an ACL CA, encoded as a String, whose content embeds another CA.

Two operators are used to build terms denoting composite CAs:

· The sequencing operator (;) denotes a composite act in which the first action (represented by the first operand) is followed by the second action, and,

· The alternative operator (|) denotes a composite act in which either the first action occurs, or the second, but not both.

3.9 Notes on the Grammar Rules

1. The standard definitions for integers and floating point are assumed. However, due to the necessarily unpredictable nature of cross-platform dependencies, agents should not make strong assumptions about the precision with which another agent is able to represent a given numerical value. FIPA SL assumes only 32-bit representations of both integers and floating point numbers. Agents should not exchange message contents containing numerical values requiring more than 32 bits to encode precisely, unless some prior arrangement is made to ensure that this is valid.

2. All keywords are case-insensitive.

3. A length encoded string is a context sensitive lexical token. Its meaning is as follows: the message envelope of the token is everything from the leading # to the separator " (inclusive). Between the markers of the message envelope is a decimal number with at least one digit. This digit then determines that exactly that number of 8-bit bytes are to be consumed as part of the token, without restriction. It is a lexical error for less than that number of bytes to be available.

4. Note that not all implementations of the ACC (see [FIPA00067]) will support the transparent transmission of 8-bit characters. It is the responsibility of the agent to ensure, by reference to internal API of the ACC, that a given channel is able to faithfully transmit the chosen message encoding.

5. Strings encoded in accordance w

Document title	FIPA SL Content Language Specification
Document number	SC00008I	Document source	FIPA TC Communication
Document status	Standard	Date of this status	2002/12/03
Supersedes	FIPA00003
Contact	fab@fipa.org
Change history	See Informative Annex B — ChangeLog