# [TED] ACTION-294: Propose a treatment of sequences

From: Boley, Harold <Harold.Boley@nrc-cnrc.gc.ca>
Date: Tue, 12 Jun 2007 14:31:33 -0400
Message-ID: <E4D07AB09F5F044299333C8D0FEB45E903BA1459@nrccenexb1.nrc.ca>
To: "RIF WG" <public-rif-wg@w3.org>
```
This is about my ACTION-294: Actually, two proposals for treating
sequences.

In the EBNF of
http://www.w3.org/2005/rules/wg/wiki/Core/Positive_Conditions

Uniterm ::= Const '(' TERM* ')'

could be used to represent Lisp's dotted pairs (head . tail) and
Prolog's lists
[head | tail] by employing a distinguished binary function symbol, say
Pair, and
a distinguished constant symbol, say Nil, so the Prolog list [a,Y,c]
would become
the Pair nesting

<Pair>
<Const>a</Const>
<Pair>
<Var>Y</Var>
<Pair>
<Const>c</Const>
Nil
</Pair>
</Pair>
</Pair>

Besides dealing with these two distinguished symbols, nothing else would
need
to be changed (especially, in the semantics).

Alternatively, n-ary sequences could be directly represented via an
n-ary list constructor, so Prolog's [a,Y,c] would remain a flat

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

For this, TERMs, currently defined as

TERM ::= Const | Var | Uniterm

could be extended to

TERM ::= Const | Var | Uniterm | LIST

with

LIST ::= 'List' '(' TERM* ')'

The latter EBNF rule is structurally identical to, e.g.,
CONJUNCTION ::= 'And' '(' CONDITION* ')'.

To accommodate a Prolog-like vertical bar, "|", in Lists, we could allow
a single optional rest element somehow like this:

LIST ::= 'List' '(' TERM* [rest] ')'  % OK if nothing to the left of "|"
rest ::= TERM   % normally TERM is just a Var

Such a <rest> element can be used to express the human-readable
syntactic equality [?head | ?tail] = [a ?Y c]:

<List>
<rest><Var>tail</Var></rest>
</List>

unifies with

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

by binding

and

<Var>tail</Var> to <List><Var>Y</Var><Const>c</Const></List>

Nested Prolog Lists such as [a,[X,b],c] are allowed:

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

This n-ary List notation can be regarded as syntactic sugar for
the above Pair notation by statically rewriting each List to a Pair
nesting, as suggested by the [a,Y,c] examples. So, besides the
resulting distinguished Pair and Nil symbols, the semantics could
again be kept unchanged.

-- Harold
```
Received on Tuesday, 12 June 2007 18:31:43 UTC

This archive was generated by hypermail 2.3.1 : Tuesday, 6 January 2015 21:47:46 UTC