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

This document extends RIFBLD 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 [[BLDRIFBLD] 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 RIFBLD 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 onetoone 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 XMLserializing 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, nonextended, 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
 islist(L) (guard)
 contains(L, X)
Functions
 concatenate(L1, L2) > L
 indexof(L1, X) > L2 (L2 is a list of integers i where get(L1,i)=X)
 insertbefore(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
 distinctvalues(L1) > L2
 get(L, I) > X
 flatten(L1) > L2
 delete(L1, X) > L2 (return the list without any/all occurances of X)