Lists

From RIF
Jump to: navigation, search


Document title:
Proposal for Lists in RIF BLD (Second Edition)



Abstract

This document extends RIF-BLD terms with lists, which are sequences of terms. To make it possible to manipulate lists with ease, as in Prolog, we also introduce open lists.

Syntax of Lists

The alphabet of the language is extended with the symbols List and |, and the language of [[BLD|RIF-BLD] is extended with list terms.

List Terms

List terms. A list term has one of these forms:

  • A closed list is of the form List(t1 ... tm), where m≥0 and t1 , ..., tm are terms.
  • An open list is of the form List(t1 ... tm | t), where m>0 and t1 , ..., tm, t are terms.

A closed list with m=0 is called the empty list.

Note that the syntax allows malformed lists, like List(1 2 | 3).


EBNF Syntax

We now extend the syntax of terms in RIF-BLD by adding one additional alternative, lists:


EBNF grammar

  TERM     ::= IRIMETA? (Const | Var | Expr | 'External' '(' Expr ')' | LIST)
  LIST     ::= 'List(' TERM* ')' | 'List(' TERM+ '|' TERM ')'


Example 1 (An empty, closed, and an open list)

a. Empty list
   List( )

b. Closed list with variable inside
   List(a ?Y c)

c. Open list with variables
   List(a ?Y c | ?Z)

d. Equality of lists
   List(Head | Tail) = List(a ?Y c)

e. Nested list
   List(a List(?X b) c)

Semantics

We add the following functions to semantic structures:

  • Ilist : Dind*Dind
  • Itail : Dind+×DindDind

These functions are required to satisfy the following:

  • Ilist is an injective one-to-one function.
  • Ilist(Dind) is disjoint from the value spaces of all data types in DTS.
  • Itail(a1, ..., ak, Ilist(ak+1, ..., ak+m)) = Ilist(a1, ..., ak, ak+1, ..., ak+m).

Note that the last condition above restricts Itail only when its last argument is in Ilist(Dind), the image of Ilist. If the last argument of Itail is not in Ilist(Dind), then the list is malformed and there are no restrictions on the value of Itail except that it must be in Dind.

We interpret list terms as follows:

  • I(List( )) = Ilist(<>).
    • Note that the domain of Ilist is Dind*, so Dind0 is an empty list of elements of Dind, which we denote by <>.
  • I(List(t1 ... tn)) = Ilist(I(t1), ..., I(tn)), if n>0.
  • I(List(t1 ... tn | t)) = Itail(I(t1), ..., I(tn), I(t)), if n>0.

XML Serialization

      • TBD: Harold check

Preliminaries

The following is the XML-serializing mapping of the presentation syntax for lists in RIF.


Classes, roles and their intended meaning

- List       (list)
- rest      (rest role)


Example 2 presents a serialization of the terms of Example 1.


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

a.
<List/>

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

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

d.
<Equal>
  <List>
    <Var>head</Var>
    <rest><Var>tail</Var></rest>
  </List>
  <List>
    <Const>a</Const>
    <Var>Y</Var>
    <Const>c</Const>
  </List>
</Equal>

e.
<List>
  <Const>a</Const>
  <List>
    <Var>X</Var>
    <Const>b</Const>
  </List>
  <Const>c</Const>
</List>


Mapping of the Presentation to XML

The translation from the presentation syntax to the XML syntax is given by a table, below, which extends the translation table of [/2005/rules/wg/wiki/Core/Positive_Conditions Positive Conditions].


Presentation Syntax XML Syntax
List (
  element1
  . . .
  elementm
    )
<List>
  element1
  . . .
  elementm
</List>
List (
  element1
  . . .
  elementn
  |
  remainder
    )
<List>
  element1
  . . .
  elementn
  <rest>remainder</rest>
</List>

List Builtins

These are modeled after xpath functions and operators. Abbreviations for arguments and results:

  • L, L1, L2 are lists
  • X is any individual (including a list)
  • I, I1, I2 are integers
  • N is a numeric
  • C is a literal that has a total order
  • -> means "returns"

Predicates

  • is-list(L) (guard)
  • contains(L, X)

Functions

  • concatenate(L1, L2) -> L
  • index-of(L1, X) -> L2 (L2 is a list of integers i where get(L1,i)=X)
  • insert-before(L1, I, X) -> L2
  • remove(L1, I) -> L2
  • reverse(L1) -> L2
  • sublist(L1, I1, I2) -> L2
  • sublist(L1, I) -> L2
  • union(L1, L2) -> L (removes dups)
  • intersect(L1, L2) -> L (removes dups)
  • except(L1, L2) -> L (difference; removes dups)
  • count(L) -> I
  • distinct-values(L1) -> L2
  • get(L, I) -> X
  • flatten(L1) -> L2
  • delete(L1, X) -> L2 (return the list without any/all occurances of X)
Retrieved from "http://www.w3.org/2005/rules/wiki/index.php?title=Lists&oldid=8399"