This is an archive of an inactive wiki and cannot be modified.

 *** MK: the list constructor with a better semantics ***

## 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.

 ***TBD: In BLD/Syntax, permit polyadic signature for Seq or equivalent mechanism.

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

• A non-extended sequence is of the form Seq(t1 ... tm), where t1 , ..., tm are terms.

• An extended sequence is of the form Seq(t1 ... tn | t), where n>0 and t1 , ..., tn, 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>
<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.

Presentation SyntaxXML Syntax
```Seq (
element1
. . .
elementm
)```
```<Seq>
element1
. . .
elementm
</Seq>```
```Seq (
element1
. . .
elementn
|
remainder
)```
```<Seq>
element1
. . .
elementn
<rest>remainder</rest>
</Seq>```

## Semantics

Add the following functions to the interpretations:

• Iseq : D*D

• Itail : D+×DD

These functions are required to satisfy the following: Itail(a1, ..., ak, Iseq(ak+1, ..., ak+m)) = Iseq(a1, ..., ak, ak+1, ..., ak+m).

Then interpret lists as follows:

• I(Seq( )) = Iseq(<>).

• Note that the domain of Iseq is D*, so D0 is an empty sequence of elements of D, which we denote by <>. (MK: This is what Harold's nil should have been.)

• I(Seq(t1 ... tn)) = Iseq(I(t1), ..., I(tn)), if n>0.

• I(Seq(t1 ... tn | t)) = Itail(I(t1), ..., I(tn), I(t)), if n>0.

 *** MK: Note that this definition readily interprets malformed lists, like Seq(1 2 | 3), but so does the original definition. Also note that such malformed lists are also allowed in LISP. However, this is not a problem if we declare things like Seq(1 2 | 3) to be not in the language ("syntactic errors"). I do not know, however, if it is worth doing. ***