RE: sbnf (striped BNF)

Visual-oriented languages are often great in expressing a few
distinctions in an intuitive (2D or even 3D) manner, but might
be hard to upgrade when adding more distinctions. Pretty-print
displays of symbolic languages can partially make up for their
lack of immediate visual appeal (see below).

I think you both touch on the fully-striped vs. stripe-skipped
issue and on abstraction issues here. My main considerations
are the following.

In http://www.w3.org/2005/rules/wg/wiki/Core/Horn_Rules, the
Concrete EBNF Syntax of, say, [1] is naturally stripe-skipped,
*for the convenience of readers and the semantics*, where we
do not want to rewrite

[5]   I |= then :- if

into some fully-striped
(the 2nd 'then' and 'if' occurrences are the ones from [5])

[6]   I |= then->then :- if->if

Grammatically, the binary infix operator ':-' of [5] clarifies
the roles of its left and right operands to the effect of [6].

On the other hand, *as a successor to asn06*, we may want an
Abstract EBNF Syntax, inspired by your SBNF rules, which is not
only fully striped but also fully abstract. So, e.g., instead
of the concrete surface token ':-', we should use the abstract
constructor 'Implies', abstracting [3] to 

[7]   Implies ::= 'Implies'
                    '('
                        'then' '->' ATOMIC
                        'if'   '->' CONDITION
                    ')'

where slot names 'then' and 'if' are local to the 'Implies'.
In interpretations, the order between these '->' slots does
not matter. (RIF could then also encode the abstract syntax
of its own rules as slotted Uniterms:
http://www.w3.org/2005/rules/wg/wiki/Core/Slotted_Conditions)

Rather than regarding the '::' or '->' pairs as "in-line
productions", they are now part of the terms defined through
the Abstract EBNF Syntax.

In our Concrete EBNF Syntax, the ':-' / 'Implies' kernel of a
sample rule instance could be given as follows:

discount(?Customer) :- loyal(?Customer)

In the Abstract EBNF Syntax, it could be rewritten like this:

Implies
  (
    then -> Uniterm
              (
                op  -> Const(discount)
                arg -> Var(Customer)
              )
    if   -> Uniterm
              (
                op  -> Const(loyal)
                arg -> Var(Customer)
              )
  )

This will be interpreted equivalently when the slots are
permuted on any level, as after a top-level permutation:

Implies
  (
    if   -> Uniterm
              (
                op  -> Const(loyal)
                arg -> Var(Customer)
              )
    then -> Uniterm
              (
                op  -> Const(discount)
                arg -> Var(Customer)
              )
  )

Given an Abstract EBNF (instead of asn06), with rules
like [7], and a Concrete EBNF (as before), with rules
like [1], there can be mappings in both directions.
For the purpose of our spec, the primary direction of
mapping is again from abstract to concrete.

Both grammars themselves and their instances can be mapped.
The abstract-to-concrete mapping algorithms would basically
'positionalize' the canonically (e.g., lexicographically)
sorted slots, and move certain abstract constructors, e.g.
'Implies', into the position of infix operators, e.g. ':-'.

-- Harold


-----Original Message-----
From: public-rif-wg-request@w3.org [mailto:public-rif-wg-request@w3.org]
On Behalf Of Sandro Hawke
Sent: Thursday, August 30, 2007 4:10 PM
To: public-rif-wg@w3.org
Subject: sbnf (striped BNF)



I've been trying to figure out how to simplify our syntax situation.

I had thought, in November, when I suggested using asn06, that it would
help, but I don't see that happening.  What I'm thinking now is to
have the master grammar be the presentation-syntax BNF, but to make sure
the BNF is written in a style such that we can derive the abstract
syntax from it, for use in generating UML-like diagrams, the XML syntax,
and (in general) the object model.

To do that, the BNF has to be striped, to have property (role, slot)
names.  For example, where the current BLD draft says this:

[1]   Implies  ::= ATOMIC ':-' CONDITION

we need some way to say what the associated property names are.  If we
wanted to be verbose about it and stick with normal BNF, we would write
this:

[2]   Implies ::= then ':-' if
      then ::= ATOMIC
      if ::= CONDITION

That gets pretty tedious pretty quickly, so I suggest we use an "in-line
production" syntax, like this:

[3]   Implies ::= then::ATOMIC ':-' if::CONDITION

The idea here is that the "::" infix operator in BNF is syntactic sugar
for making another production.  Forms [2] and [3] are just about
semantically equivalent.  I'm pretty sure we want them to be not quite
equivalent, though, in that I think in form [3] the property names
should be local -- scoped to "Implies" -- so that grammatically it's
really equivalent to this:

[4]   Implies ::= Implies__then ':-' Implies__if
      Implies__then ::= ATOMIC
      Implies__if ::= CONDITION

This allows us to have things like, where the property "name" is shared:

   Variable ::= '?' name::xs:token
   GlobalConstant ::= name::xs:anyURI

(I'm not suggesting that's the right design for Variable and
GlobalConstant, just that we may want to re-use the same property name
with two different value types.  If so, then [3] has to be equivalent to
[4] and not [2].)  If it turns out we don't want to re-use property
names like this, that would simplify things.

I haven't fully implemented the code for reading SBNF and outputting
asn, graphviz (UML-like diagrams), XML Schema, etc, but I've gotten far
enough along the way that I'm fairly confident it will work, and I
wanted to share this idea.

(There are some details about lists and Kleene operators, but I think
they can be managed.)

Thoughts?

      -- Sandro

Received on Sunday, 2 September 2007 22:25:50 UTC