Lists
- 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.
Contents
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(t_{1} ... t_{m}), where m≥0 and t_{1} , ..., t_{m} are terms.
- An open list is of the form List(t_{1} ... t_{m} | t), where m>0 and t_{1} , ..., t_{m}, 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:
- I_{list} : D_{ind}^{*} → D_{ind}
- I_{tail} : D_{ind}^{+}×D_{ind} → D_{ind}
These functions are required to satisfy the following:
- I_{list} is an injective one-to-one function.
- I_{list}(D_{ind}) is disjoint from the value spaces of all data types in DTS.
- I_{tail}(a_{1}, ..., a_{k}, I_{list}(a_{k+1}, ..., a_{k+m})) = I_{list}(a_{1}, ..., a_{k}, a_{k+1}, ..., a_{k+m}).
Note that the last condition above restricts I_{tail} only when its last argument is in I_{list}(D_{ind}), the image of I_{list}. If the last argument of I_{tail} is not in I_{list}(D_{ind}), then the list is malformed and there are no restrictions on the value of I_{tail} except that it must be in D_{ind}.
We interpret list terms as follows:
- I(List( )) = I_{list}(<>).
- Note that the domain of I_{list} is D_{ind}^{*}, so D_{ind}^{0} is an empty list of elements of D_{ind}, which we denote by <>.
- I(List(t_{1} ... t_{n})) = I_{list}(I(t_{1}), ..., I(t_{n})), if n>0.
- I(List(t_{1} ... t_{n} | t)) = I_{tail}(I(t_{1}), ..., I(t_{n}), 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 ( element_{1} . . . element_{m} ) |
<List> element_{1} . . . element_{m} </List> |
List ( element_{1} . . . element_{n} | remainder ) |
<List> element_{1} . . . element_{n} <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)