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

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>
  <Var>head</Var>
  <rest><Var>tail</Var></rest>
</List>

unifies with

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

by binding

<Var>head</Var> to <Const>a</Const>

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