Warning:
This wiki has been archived and is now read-only.
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(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+×Dind → Dind
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)