[SCL] Representing constraints that go beyond EBNF

[pat hayes]

>Murray,
>
>EBNF has been designed to represent ordered context-free languages,
>which include many important computer languages.  But we also have
>to represent languages that may have unordered constituents (graphs)
>and languages with context-sensitive constraints (first-order logic
>and all Algol-like languages).
>
>MA> ... Without boring you all with the details, a Topic Map is
>>  not a linear sequence; it's very much a complex, unordered graph.
>>We were still able to use EBNF to specify the XML syntax, and I'm
>>sure that the graph theoretic model behind that (which is called
>>the Reference Model, a current ISO project) is also capable of
>>being expressed in EBNF. So I'm really not certain where you'd
>>have to rely on "tricks" to get EBNF to do what you want with the
>>SCL abstract syntax, or XCL/CLML for that matter.
>
>In mathematics, a common representation for a graph consists of
>a set of nodes and a set of arcs.  Since sets are by definition
>unordered, no further comment is needed.

That kind of an answer isn't going to be acceptable to the Perl 
hackers, though. They want a machine-readable syntax for specifying 
it, which is what I was also looking for.

>If EBNF is used to specify graphs, some additional statement is
>necessary to ensure that some (perhas not all) of the ordering
>imposed by EBNF is ignored.  One appraoch is to say "The implicit
>ordering in the following sequence has no semantic relevance"
>or "All permutations of the following sequence are considered
>equivalent."  I noticed that the ISO EBNF document does not have
>such a provision, and we may need to add one.

Well, but then we need to be very careful what we say. A grammar 
written in ISO EBNF *with some additions* is not written in ISO EBNF.

>For common programming languages, the most important context
>sensitive constraint is the association between the declaration
>of a name (of a variable, constant, relation, or other entity)
>and the use of that name in some subsequent statement.  That
>constraint is usually enforced by means of symbol tables.
>
>For first-order logic (in KIF, CG, or predicate calculus notation),
>the quantifiers have an effect that is similar to the declarations
>in a programming language.  And the rules for scope of quantifiers
>happen to create a nested structure that is isomorphic to the
>rules for scope of variables in Algol-like languages.  Similar
>problems arise in both kinds of languages, and similar techniques,
>such as symbol tables, can be used to address them.
>
>When a compiler finds a declaration (implicit or explicit) for
>any named entity, it adds the name and associated information
>about the type of entity to a symbol table, which is tied to
>the current level of nesting.  On each subsequent occurrence
>of the name within the scope defined by the nesting, it checks
>the symbol table to ensure that the current use is consistent
>with the declaration.
>
>Since EBNF does not make provision for a symbol table, we can adopt
>the same approach that is used to define programming languages:
>
>  1. Use EBNF to specify the constext-free constraints.
>
>  2. State additional context-sensitive constraints in statements
>     that are outside the EBNF specifications.
>
>These issues are very similar to the problems that came up when
>we were talking about defining an XML version of CGIF.  There is
>no problem with defining the context-free issues, but CGIF has
>the same context-sensitive constraints as FOL and Algol.  Those
>issues arise in relating the defining occurrence of a coreference
>label to the bound occurrences of that label.
>
>Since XSLT, like EBNF, does not make any provision for enforcing
>or even specifying such constraints, the same issues come up
>in MathML.  Following is a web page that discusses them:
>
>    http://www.w3.org/TR/2003/NOTE-mathml-bvar-20031110/
>    Bound Variables in MathML

Interesting. That seems mostly concerned with issues which arise from 
using XML to identify display properties which are totally orthogonal 
to the logical form. That is a real issue in the XML world where XML 
serves both as textual markup and as a structural description (we met 
this issue in a small form in the RDF spec), but I think this is a 
slightly different issue to ours.
(But I take your point that the use of URIs to bind variables to 
their binder is a general trick that we could adopt.)

Take a look at Schematron, part of the forthcoming DSDL ISO standard: see
http://xml.com/pub/a/2003/11/12/schematron.html
particularly the 'abstract patterns' on page 2 of the article. I 
think we can make use of this to write the abstract syntax of SCL 
directly as a set of schemas which would check on any suitably 
marked-up SCL concrete text. That is, suppose D is a textual document 
purporting to be a text of an SCL language, and define XD to be the 
same document with SCL/XML markup added surrounding all the SCL 
constructions, then D is SCL-well-formed just when our ISO schematron 
pattern matches XD successfully. The nice thing about this is that we 
can abstract away from things like order of the elements in the 
document (tricky in Xpath or XSLT).  And this is all ISO stuff ;-)

Pat

>John
>
>_______________________________________________
>SCL mailing list
>SCL at philebus.tamu.edu
>http://philebus.tamu.edu/mailman/listinfo/scl


-- 
---------------------------------------------------------------------
IHMC	(850)434 8903 or (650)494 3973   home
40 South Alcaniz St.	(850)202 4416   office
Pensacola			(850)202 4440   fax
FL 32501			(850)291 0667    cell
phayes at ihmc.us       http://www.ihmc.us/users/phayes