Chapter 3 Language definition

3.1 Preliminary definitions and notations

In this implementation, the data are represented as lists of objects. This section defines what we mean here by objects and lists. It then provides definitions of basic functions that will be useful when defining the language in the next section.

3.1.1 Objects

An object can be either nil,atomic or complex. nil is an object that denotes undefined values. The type of nil is Tnil. An atomic object can be of type Tboolean, Tinteger, Tdouble or Tstring, whereas a complex objects represents a DOM Node. O_bj denotes the set of objects, including nil.
O_bj^* denotes the set of non-nil objects.

Atomic objects:

Atomic objects are wrappers for primitive data types. The value of an atomic object is the corresponding basic atomic value. TRUE (resp. FALSE) is the boolean object which value is true (resp. false). B_ool (resp I_nt,D_bl,S_tr) denotes the set of boolean (resp integer, double, string) objects.
A_tom denotes B_ool È I_nt È D_bl È S_tr.
N_um denotes I_nt È D_bl.
atomic is the factory function that can be used to build atomic objects. For instance, atomic(1) returns the integer object i such that value(i)=1. For clarity, we will in the sequel use notation shortcuts. For instance:
"a string" is equivalent to atomic("a string");
1 is equivalent to atomic(1);
1.0 + 4.5 is equivalent to atomic(value(atomic(1.0)) +value(atomic(4.5))).

Complex objects:

Complex objects are wrappers for DOM Nodes. The W3C Recommandation [WG98] defines 12 different types of nodes, but we will consider here only DOM nodes of type Element, Attr (for attributes) and Text. The corresponding complex object types are Telement, Tattr, and Ttext. T_ext (resp A_ttr,E_lt) denotes the set of complex objects of type Ttext (resp Tattr, Telement).
C_plx denotes T_ext È A_ttr È E_lt.
Each complex object has a node attribute. It provides access to the wrapped DOM Node. Each t in T_ext (resp. a in A_ttr, e in E_lt) has a textNode (resp. attrNode, elementNode) attribute. It provides access to the wrapped Text (resp Attr, Element) DOM node.
complex is the factory fonction that can be used to build complex objects. If n is a DOM node, complex(n) returns a complex object of type corresponding to the type of n, or nil otherwise.

3.1.2 Lists

If o₁, ..., o_n are in O_bj^*, á o₁,...,o_n ñ denotes the corresponding ordered list of objects. á ñ denotes the empty list. L denotes the set of lists containing zero or more objects in O_bj^*. L^* denotes the set of lists containing one or more objects in O_bj^*.
Let o₁,...,o_n in O_bj. Then á o₁,...,o_n ñ denotes the list l in L constructed as follows :

l=cons(o₁,cons(o₂,...,cons(o_n,á ñ)...))

where cons is defined on O_bj × L as follows:
let o is O_bj^*, l^'=á o₁^',...,o_m^' ñ in L^*

cons(nil,á ñ)	=	á ñ
cons(nil,l^')	=	l^'
cons(o,á ñ)	=	á o ñ
cons(o,l^')	=	á o,o₁^',...,o_m^' ñ

For instance, á nil,1,nil,"a string" ñ denotes the element á 1,"a string" ñ of L.

union:

The union operator is denoted ||. It is defined on L × L as follows:

let l₁=á o₁₁,...,o_1n ñ in L^* ,l₂=á o₂₁,...,o_2m ñ in L^*.

á ñ FLUnion á ñ = á ñ

l₁ || á ñ = á ñ || l₁ = l₁

l₁ || l₂=á o₁₁,...,o_1n,o₂₁,...,o_2m ñ

3.1.3 Object functions and predicates

A n-ary object function is a function that takes n, with n>0, objects as arguments and returns an object. We will denote Fⁿ the set of n-ary object functions. The set of unary (resp. binary) object functions is F¹ (resp. F²).
A list function is a function that takes one object as argument and returns a list in L. F_l denotes the set of list functions.
An n-ary object predicate is a n-ary object function that returns either TRUE or FALSE. We will denote Pⁿ the set of n-ary object predicates. The set of unary (resp. binary) object predicates is P¹ (resp. P²).

Unary predicates

is:

If cst is in O_bj, is_cst is a unary object predicate. It is defined on O_bj as follows:

let o in O_bj

iscst(o) =

ì
í
î

TRUE	if o is the object cst
FALSE	otherwise

We will in the sequel make use of is_nil,is_TRUE and isFalse.

in:

If set is a set of objects, in_set is a unary object predicate. It is defined on O_bj as follows:

let o in O_bj

in_set(o)=

ì
í
î

TRUE	if o Î set
FALSE	otherwise

We will in the sequel make use of in_{B_ool} ,in_{I_nt} ,in_{D_bl} ,in_{N_um} ,in_{S_tr} ,in_{A_tom} ,in_{T_ext} ,in_{A_ttr} ,in_{E_lt} and in_{C_plx}.

Conversion functions

string:

string is a unary object function that returns a string object or nil. string is defined on O_bj as follows:

let o in O_bj

type(o)	string(o)
Tnil	nil
Tboolean	`"true"` if is_TRUE(o), `"false"` otherwise.
Tstring	o
Tinteger	a string object representing this integer.
Tdouble	a string object representing this double, in the style `[-]ddd.ddd`
Ttext	o.textNode.nodeValue()
Tattr	o.attrNode.nodeValue()
Telement	string(o)=StrElt(o), where StrElt is defined above.

procedure StrElt(TElement e)
begin
	result := nil;
	l := e.elementNode.getChildNodes();
	for each	n in l
		if	n Î T_ext
			result := result + string(n)
		endif
	endfor
	return result;
end

text:

text is a unary object function that returns a string object or nil. It is defined on O_bj as follows:

let o in O_bj

text(o) =

ì
í
î

textElt(o)	if in_{E_lt}(o)
string(o)	otherwise

where TextElt is the following procedure:

procedure TextElt(TElement e)
begin
	result := nil;
	l := e.elementNode.getChildNodes();
	for each	n in l
		if	n Î T_ext
			result := result + string(n)
		endif
		if	in_{E_lt}(n)
			result := result + TextElt(n)
		endif
	endfor
	return result;
end

boolean:

boolean is a unary object function that returns a boolean object or nil. boolean is defined on O_bj as follows:

let o in O_bj

type(o)	boolean(o)
Tnil	FALSE
Tboolean	o
Tstring	TRUE if the lowercased value of o is `"true"`, FALSE otherwise
Tinteger	FALSE if o=0, TRUE otherwise
Tdouble	FALSE
other	boolean(string(o))

integer:

integer is a unary object function that returns an integer object or nil. integer is defined on O_bj as follows:

let o in O_bj

type(o)	integer(o)
Tnil	nil
Tboolean	nil
Tstring	an integer if o is a string representation of an integer, nil otherwise
Tinteger	o
Tdouble	an integer if the decimal part of o equals 0, nil otherwise.
other	integer(string(o))

double:

double is a unary object function that returns a double object or nil. double is defined on O_bj as follows:

let o in O_bj

type(o)	double(o)
Tnil	nil
Tboolean	nil
Tstring	a double if o is a string representation od a double, nil otherwise
Tinteger	a double d such that d=o
Tdouble	o
other	double(string(o))

num:

num is a unary object function that returns an object in N_um or nil. num is defined on O_bj as follows:

let o in O_bj

num(o)=

ì
í
î

integer(o)	if integer(o) ¹ nil
double(o)	otherwise

Comparison functions

less:

less is a binary object function. If its two arguments are coercible into numeric objects, it returns the result of the comparison between them, and nil otherwise. less is defined on O_bj × O_bj as follows:

let o₁ in O_bj, o₂ in O_bj, let n₁=num(o₁), n₂=num(o₂)

less(o₁,o₂)=

ì
í
î

nil	if n₁=nil or n₂=nil
TRUE	if n₁<n₂
FALSE	otherwise

greater,lessEqual and greaterEqual are defined in a similar way.

compare:

compare is a binary object function. It performs a comparison by value between its two arguments. compare is defined on O_bj × O_bj as follows:

Let o₁ in O_bj,o₂ in O_bj

: if o₁=nil or o₂=nil, compare(o₁,o₂) = nil
: if o₁ Î N_um or o₂ Î N_um, compare(o₁,o₂) = less( num(o₁), num(o₂))
: if o₁ Î S_tr È T_ext È Attr or o₂ Î S_tr È T_ext È Att, compare(o₁,o₂) = strcomp(o₁,o₂)
: if o₁ Î E_lt and o₂ Î E_lt, compare(o₁,o₂) = eltcomp(o₁,o₂)

where strcomp is defined on O_bj × O_bj as follows:

let o₁ in O_bj,o₂ in O_bj, let s₁=string(o₁), s₂=string(o₂)

strcomp(o₁,o₂)=

ì
í
î

nil	if s₁=nil or s₂=nil
TRUE	if s₁=s₂
FALSE	otherwise

and eltcomp is defined on E_lt × E_lt as follows:

let e₁ in E_lt,e₂ in E_lt

eltcomp(e₁,e₂)=

ì
í
î

TRUE	if e₁ and e₂ have the same structure (identical names, attributes and children)
FALSE	otherwise

Arithmetic functions

unaryPlus:

unaryPlus is defined on O_bj as follows:

let o in O_bj

unaryPlus(o)=num(o)

unaryMinus:

unaryPlus is defined on O_bj as follows:

let o in O_bj

unaryMinus(o)= -num(o)

plus:

plus is defined on O_bj × O_bj as follows:

let o₁ in O_bj, o₂ in O_bj

plus(o₁,o₂)=

ì
í
î

nil	if num(o₁)=nil or num(o₂)=nil
num(o₁) + num(o₂)	otherwise

minus, mul and div are defined in the same way.

DOM operations

name:

name is an object unary function that returns the name of an object. name is defined on O_bj as follows:

Let o in O_bj.

name(o)=

ì
í
î

o.node.getNodeName()	if o Î C_plx
nil	otherwise

label:

label is an object unary function that returns the label of an object. label is defined on O_bj as follows:

let o in O_bj.

name(o)=

ì
í
î

o.node.getNodeName()	if o Î (A_ttr È E_lt)
nil	otherwise

attributes:

attribute is a list function that returns a list of the attributes nodes of an object. attributes is defined on O_bj as follows:

let o in O_bj

name(o)=

ì
í
î

Attrs(o)	if o Î C_plx
á ñ	otherwise

procedure Attrs(TComplex o)
begin
	result := á ñ;
	attrs := e.node.getAttributes();
	if	attrs == null
		return result;
	for each	attr in attrs
		result := cons(attr,result)
	endfor
	return result;
end

childNodes:

childNodes is a list function that returns a list of the child nodes, at the first level in the DOM tree, of an object. childNodes is defined on O_bj as follows:

let o in O_bj

childNodes(o)=

ì
í
î

Children(o)	if o Î C_plx
á ñ	otherwise

where Children is the following procedure:

procedure Children(TComplex o)
begin
	result := á ñ;
	children := e.node.getChildNodes();
	if	children == null
		return result;
	for each	child in children
		result := result \|\| á child ñ
	endfor
	return result;
end

descNodes:

descNodes is a list function that returns a list of the child nodes, at any depth in the DOM tree, of an object. descNodes is defined on O_bj as follows:

let o in O_bj

descNodes(o)=

ì
í
î

Descendants(o)	if o Î C_plx
á ñ	otherwise

where Descendants is the following procedure:

procedure Descendants(TComplex o)
begin
	result := á ñ;
	children := e.node.getChildNodes();
	if	children == null
		return result;
	for each	child in children
		result := result \|\| cons(child,Descendants(child))
	endfor
	return result;
end

3.1.4 Aggregate functions and predicates

An aggregate function is a function that takes a list in L as argument and returns an object in O_bj.
An aggregate predicate is a list function that returns either TRUE or FALSE.

Aggregate functions

first:

Let l=á o₁,...,o_n ñ in L^*. first is defined on L as follows:

first(á ñ)= nil
first(l)=o₁

last:

Let l=á o₁,...,o_n ñ in L^*. last is defined on L as follows:

last(á ñ)= nil
last(l)=o_n

count:

Let l=á o₁,...,o_n ñ in L^*. count is defined on L as follows:

count(á ñ)= 0
count(l)=n

Aggregate predicates

empty:

empty is an aggregate predicate. It is defined on L as follows:

let l in L

empty(l)=

ì
í
î

TRUE	if count(l)=0
FALSE	otherwise

3.1.5 Selection operator

The selection operator s filters a list according to an object unary predicate.
Let l in L^*, p in P¹. s is defined on L × P¹ as follows:

s(á ñ,p)	=	á ñ
s(l,p)	=	á o, o Î l, p(o) ñ

3.1.6 Mapping operators

We introduce two mapping operators. Map is the classical mapping operator on lists. Map_l is a generalized version of Map, for the case of the mapping function is in F_l.

Let l in L^*, f in F¹. Map is defined on L × F¹ as follows:

Map(á ñ,f)	=	á ñ
Map(l,f)	=	á f(o₁),...,f(o_n) ñ

Let l in L^*, f in F_l. Map_l is defined on L × F_l as follows:

Map_l(á ñ,f)	=	á ñ
Map_l(l,f)	=	f(o₁) \|\| ... \|\| f(o_n)

3.1.7 Existantial quantifier

Let p in P¹, l in L. Exist(l,p) returns TRUE if there exist o in l such that p(o)=TRUE, and FALSE otherwise.

Exist is defined on L × P¹ as follows:

Exist(l,p)=

ì
í
î

TRUE	if empty(Map(l,p))=FALSE
FALSE	otherwise

3.1.8 Universal quantifier

Let p in P¹, l in L^*.

All is defined on L × P¹ as follows:

All(á ñ,p)

FALSE

All(l,p)

ì
í
î

TRUE	if for each o in l, p(o)=TRUE
FALSE	otherwise

3.1.9 Join operator

Let l₁ in L^*,l₂ in L^*, f in F², p in P².

Join(l₁,á ñ,f,p)=Join(á ñ,l₁,f,p)=á ñ
Join(l₁,l₂,f,p)=á f(o₁,o₂), o₁ Î l₁, o₂ Î l₂, p(o₁,po₂) ñ

If the parameter p is omitted, its default value is the object binary predicate that returns always TRUE.

3.2 X-OQL expressions

X-OQL is a functional language. It is defined by a set of basic queries and functions and a way of building new ones through composition.

3.2.1 Definitions

An X-OQL expression is a string of the form query ;. The value of an expression is computed by calling the evaluation function E with the argument query. Given a query q, E(q) returns a list in L.

We will also consider in the boolean evaluation functions E_b. E_b takes as argument a query and returns either TRUE or FALSE.
We will in the sequel provide the syntax of basic queries and functions. For each of them, the corresponding value of E and E_b is given. If, given a query q, only E(q) or E_b(q) is given, then the following rule applies:

if only E(q) is given, then E_b(q)=FALSE if E(q) is an empty collection of objects, TRUE otherwise;
if only E_b(q) is given, then E(q) = á E_b(q) ñ.

3.2.2 Basic queries

Atomic literals

Literals have the usual syntax. For instance, an integer literal is a sequence of digits, a string literal is a double quoted sequence of characters.

true is a query.
E_b(true) = TRUE
false is a query.
E_b(false) = FALSE
If i is an atomic literal, then i is a query.
E(i) = á i ñ

List construction

{} is a query.
E({})= á ñ
If X and Y are queries, then X union Y is a query.
E(X union Y)= E(X) || E(Y)
If X₁,...,X_n are queries, then {X₁,...,X_n} is a query.
E({X1,...,Xn})= E(X1) || ... || E(Xn)

Boolean connectors

If X is a query, then not X is a query.

E_b(not X) = ì
í
î

TRUE if E_b(X)=FALSE

FALSE otherwise
If X and Y are queries, then X and Y is a query.

E_b(X and Y) = ì
í
î

TRUE if E_b(X)=TRUE and E_b(Y)=TRUE

FALSE otherwise
If X and Y are queries, then X or Y is a query.

E_b(X and Y) = ì
í
î

TRUE if E_b(X)=TRUE or E_b(Y)=TRUE

FALSE otherwise

Relational queries

If X and Y are queries, then X=Y is a query. E_b(X=Y) returns TRUE if there exist x in E(X), y in E(Y) such that compare(x,y)=TRUE.
E_b(X=Y)=Exist(Join(E(X),E(Y),compare),is_TRUE)
If X and Y are queries, then X<Y is a query. E_b(X<Y) returns TRUE if there exist x in E(X), y in E(Y) such that x and y can be converted into numerical values n_x, n_y, and n_x<n_y.
E_b(X<Y)=Exist(Join(Map(E(X),num),Map(E(Y),num),less),isTrue)
If X and Y are queries, then X<=Y is a query.
E_b(X<=Y)=Exist(Join(Map(E(X),num),Map(E(Y),num),lessEqual),isTrue)
If X and Y are queries, then X>Y is a query.
E_b(X>Y)=Exist(Join(Map(E(X),num),Map(E(Y),num),greater),isTrue)
If X and Y are queries, then X>=Y is a query.
E_b(X>=Y)=Exist(Join(Map(E(X),num),Map(E(Y),num),greaterEqual),isTrue)

3.2.3 Arithmetic operators

If X is a query, then +X is query.
E(+X) = Map(X,unaryPlus)
If X is a query, then -X is query.
E(+X) = Map(X,unaryMinus)
If X and Y are queries, then X+Y is a query.
E(X+Y)=Join(Map(X,num),Map(Y,num),plus)
If X and Y are queries, then X-Y is a query.
E(X-Y)=Join(Map(X,num),Map(Y,num),minus)
If X and Y are queries, then X*Y is a query.
E(X*Y)=Join(Map(X,num),Map(Y,num),mul)
If X and Y are queries, then X div Y is a query.
E(X div Y)=Join(Map(X,num),Map(Y,num),div)

3.2.4 Path expressions

A path expression is a query of the form [query] [navigation operator] [path constraint expression]. A navigation operator can be @, / or //. Starting from a complex object o, @ allows to reach the attributes of o, whereas / (resp. // provides access to the child (resp. descendant) nodes of o. A path constraint expression can be used to restrict the collection of attributes (resp. child nodes, descendant nodes) that a path expression defines. A path constraint expression P is evaluated as regular expression r using the function R. Definitions of path constraint expressions and the corresponding value of R are given below.

* is a path constraint expression.
R(*)="*"
If X is a query, X is a path constraint expression. Let s = Map(E(X),string)
if 'regex' is a regular expression, 'regex' is path constraint expression.
R('regex')= regex
if P1,...,Pn are path constraint expressions, P1|...|Pn is a path constraint expression.
R(P1|...|Pn)= R(P1)|...|R(Pn)

Let r a regular expression, o₁,o₂ in Object, such that o₂ is a descendant of o₁.

path(o₁,o₂)=

ì
í
î

label(o₂)	if o₂ is a child of o₁
path(o1,parent(o2)) + "/" + label(o2)	otherwise

r_r(o1,o2) =

ì
í
î

TRUE	if r(path(o1,o2),r)
FALSE	otherwise

Accessing attributes

If X is a query, P is path constraint expression, X@P is a query.

E(X@P)=Join(E(X)[x],attributes(x)[y],y,r

R(P)
(x,y))

Accessing child elements

If X is a query, P is path constraint expression, X/P is a query.

E( X/P)=s(Join(E(X)[x],childNodes(x)[y],y,r

R(P)
(x,y)),in E_lt)

Accessing descendant elements

If X is a query, P is path constraint expression, X//P is a query.

E(X//P)=s(Join(E(X)[x],descNodes(x)[y],y,r

R(P)
(x,y)),in E_lt)

3.2.5 Predicates

If X is a query, and p is the name of a unary object predicate, then p(X) and X/p() are queries.
E(p(X)) = map(E(X),p)
E_b(p(X)) = exist(E(p(X)),isTrue)
E(X/p()) = E(p(X))
E_b(X/p()) = E_b(p(X))
If X is a query, and p is the name of a list predicate, then p(X) and X/p() are queries.
E_b(p(X)) = p(E(X))
E_b(X/p()) = E_b(p(X))

3.2.6 Function calls

If X is a query, and f is the name of a unary object function, then f(X) and X/f() are queries.
E(f(X)) = Map(E(X),f)
E(X/f()) = E(f(X))
If X is a query, and f is the name of a list function, then f(X) and X/f() are queries.
E(f(X)) = Map_l(E(X),f)
E(X/f()) = E(f(X))
If X is a query, and f is the name of an aggregate function, then f(X) and X/f() are queries.
E(f(X)) = á E(X) ñ
E(X/f()) = E(f(X))