• Core
• List Constructor

Syntax

In this section we extend terms, as defined in Section Positive Conditions, with lists formalized as sequences.

Sequences

The alphabet of the language is extended with the symbols Seq and |, and the language of positive conditions in Section Symbols and Signatures is extended with list terms, essentially sequences.

Sequence terms. A sequence term has one of these forms:

• A non-extended sequence is of the form Seq ( t₁ ... t_m ), where t₁ , ..., t_m are terms.

• An extended sequence is of the form Seq ( t₁ ... t_n | t ), where n>0 and t₁ , ..., t_n, t are terms.

For m=0, the non-extended sequence Seq ( ) is called the empty sequence.

EBNF for the Presentation Syntax

We now extend the presentation syntax of Positive Conditions to a presentation syntax for sequences.

EBNF grammar

  TERM           ::= Const | Var | Uniterm | LIST
  LIST           ::= 'Seq' '(' TERM* ')' | 'Seq' '(' TERM+ ` | ` TERM ')'

For example, three Prolog lists can be represented as follows.

Example 1 (presentation syntax of empty, non-extended, and extended lists)

Prolog:
a. []
b. [a,Y,c]
c. [a,Y,c|Z]

RIF:
a. Seq ( )
b. Seq ( a ?Y c )
c. Seq ( a ?Y c | ?Z )

XML Syntax

The following is an XML-serializing mapping of the presentation syntax in Section EBNF for the Presentation Syntax, extending the one in Section Positive Conditions.

Classes, roles and their intended meaning

- Seq       (sequence)
- rest      (rest role)

Example 2 shows the serialization of the three lists of Example 1.

Example 2 (XML syntax of empty, non-extended, and extended lists)

a.
<Seq/>

b.
<Seq>
  <Const>a</Const>
  <Var>Y</Var>
  <Const>c</Const>
</Seq>

c.
<Seq>
  <Const>a</Const>
  <Var>Y</Var>
  <Const>c</Const>
  <rest><Var>Z</Var></rest>
</Seq>

Lists can be decomposed, e.g. in conditions using explicit equality as shown in Example 3.

Example 3 (List equality)

a. Presentation syntax:
Seq ( Head | Tail ) = Seq ( a Y c )

b. XML syntax:
<Equal>
  <Seq>
    <Var>head</Var>
    <rest><Var>tail</Var></rest>
  </Seq>
  <Seq>
    <Const>a</Const>
    <Var>Y</Var>
    <Const>c</Const>
  </Seq>
</Equal>

This equality is true since <Var>head</Var> can be equated to <Const>a</Const> and <Var>tail</Var> can be equated to <Seq><Var>Y</Var><Const>c</Const></Seq>.

Nested lists as allowed by the grammar are illustrated in Example 4.

Example 4 (Nested list)

a. Presentation syntax:
Seq ( a Seq ( X b ) c )

b. XML syntax:
<Seq>
  <Const>a</Const>
  <Seq>
    <Var>X</Var>
    <Const>b</Const>
  </Seq>
  <Const>c</Const>
</Seq>

Translation Between the Presentation and the XML Syntaxes

The translation from the presentation syntax to the XML syntax is given by a table, below, which extends the translation table of Positive Conditions.

Seq (
  element1
  . . .
  elementm
    )

<Seq>
  element1
  . . .
  elementm
</Seq>

Seq (
  element1
  . . .
  elementn
  |
  remainder
    )

<Seq>
  element1
  . . .
  elementn
  <rest>remainder</rest>
</Seq>

Semantics

A sequence is interpreted through a nesting of pairs. The interpretation of a sequence with a top-level | leads to an innermost pair with the term after the | as its second argument. For illustration,

Seq ( a ?Y c | ?R)

is interpreted through

pair(a,pair(?Y,pair(c,?R))).

A sequence without a top-level |, equivalent to having a top-level | followed by Seq ( ), leads to an innermost pair with nil as its second argument. For illustration,

Seq ( a ?Y c )

is equivalent to

Seq ( a ?Y c | Seq ( )),

which is interpreted through

pair(a,pair(?Y,pair(c,nil))).

Generally, for the semantics of lists we refine the mapping I, defined in Section Positive Conditions, as follows:

• I(f ( t₁ ... t_n )) = I_F(f)(I(t₁),...,I(t_n)), if f is not equal to Seq

• I(Seq ( )) = nil

• I(Seq ( t₁ ... t_n )) = pair(I(t₁),...pair(I(t_n),nil)...)

• I(Seq ( t₁ ... t_n | t)) = pair(I(t₁),...pair(I(t_n),I(t))...)

The resulting binary nestings are given a fixed interpretation by a binary pairing function pair, where pair(a,b) can be thought of as denoting the domain element pair(a,b). For non-extended sequences, the second arguments of innermost pairs are given a fixed interpretation by the empty-list element nil, added to the domain.

The mapping to RDF lists via pair-like nestings can be done as in OWL 1.1.