Categorizing new feature proposals: a meta-proposal!

Hi, everyone,

I took an action a while ago to write up a response to the proposal that we should create an "ambiguity umbrella topic" which would draw together any feature proposals that deal with managing ambiguity in iXML.

I've attached my response as a pdf, which is the version I recommend you actually read. I'll also copy it (in a much-less reader-friendly format) into the body of this email so that it is preserved and discoverable in the mailing list's archives.

Best,

BTW.


********

Invisible XML: categorizing feature proposals

There has been a suggestion that we should group a number of proposed new features for iXML under an "ambiguity umbrella topic".  

There are some advantages to this thematic approach to features that allow users to manage ambiguity more effectively. In particular, it would mean that proposals that seem to address similar types of ambiguity could be considered together, streamlining discussion and design decisions.  

However, I would argue that grouping together all proposals that address some aspect of managing ambiguity is not the most useful choice we could make.  
In the first place, it seems likely that many (if not most) proposals for changes to iXML will have some effect on the management of ambiguity. Just about anything you can express with iXML can be part of an ambiguous grammar. Changing what you can express, or how easily or efficiently you can express it, is quite likely to have some impact on how easily you can write an unambiguous grammar. It's therefore unclear to me that a proposal's effect on managing ambiguity is particularly useful as a way of categorizing it.  

Secondly, I think that there are other ways of categorizing proposals, which have important technical implications. Putting proposals into any thematic umbrella topic may obscure these technical issues. 

This doesn't mean that we can't also use thematic tags like "ambiguity" to help organize proposals; but I would argue against using thematic labels as a top-level organizational principle. Iwould like to propose instead that we start categorizing proposals using two primary dimensions:

    • the scope of their effects, belonging either to the parse or to the construction of the output;

    • whether they are "syntactic sugar" or represent substantive changes to the language.

I'll briefly outline these dimensions and explain why I think they're important.  
Affecting the parse or affecting the output?

Language features in iXML have their effects (broadly speaking) during either one of two main phases during processing: the parse; and the construction of the XML output (including serialization).  

The second dimension I propose, discussed below, separates out iXML's behaviour as a recognizer from its behaviour during parsing. It therefore isn't necessary to consider recognizing and parsing as separate steps for this first dimension, which talks about "parsing" as though it means both recognizing and parsing.

This first dimension therefore categorizes proposals as either:

1. features whose effects apply during the construction of the output, which don't need to make any difference to parsing. They have no effect until after the parse is complete, when they modify some aspect of the XML that results from the parse, such as element or attribute names (e.g. renaming) or text nodes or attribute values (e.g. insertions);

2. features that have an effect during parsing, which are the nuts and bolts of a grammar. They affect whether an input string will be recognized or not, and how the parse tree(s) are constructed for a valid input.

Clarifying whether a proposal belongs to type 1 or type 2 on this dimension is useful because it will help us understand how the proposal might affect both users and implementers of iXML.  

A proposal whose effects only apply after parsing is complete may help users refine the XML to their specifications, and is unlikely to require implementers to make large changes to their parsing algorithms. It is therefore perhaps a safer change than one that affects some aspect of parsing.  

The second proposed dimension discusses proposals that have their main affect during parsing, taking a more in-depth look at the kinds of impact any such proposals might have on the language and on implementations of iXML.

Changing the syntax, changing the parse forest, or changing the language?

iXML, as defined by the specification grammar, is a context-free formalism. This means that it can be used to recognize and parse some kinds of languages (including anything that could be matched with a standard regular expression, and more), but not others (context-sensitive languages, or anything more complicated). The first two types of proposal defined below would retain the context-free nature of iXML. The third type would extend iXML in some way so that it is no longer context-free.

This dimension therefore categorizes proposals as either

1. Features introducing new syntax for behaviours that were already possible in iXML v1:

        • E.g. adding min and max counts for repetition (the following syntax is one of many possibilities):

   "cat"[0:1]
   "cat"[0:]
   "cat"[1:]
    "cat"[2:5]

        might mean the same as:

   "cat"?
   "cat"*
   "cat"+
   "cat", "cat", ("cat", ("cat", "cat"?)?)?

        • As the last of these example shows, doing this with the current syntax can quickly become very annoying and difficult to read, but it is theoretically possible. This new feature would therefore not actually change what can be expressed using iXML. It would have its effect during recognizing, in the sense that it is a way of expressing what should be matched. But it would neither change how the parse forest is constructed nor affect what can be recognized by an iXML grammar.

2. Features introducing new behaviours that affect how many (and/or which) parse trees are generated for an input string.

        • E.g. a priority operator to select a particular branch from alternatives that are ambiguous for the current input. This doesn't  change whether the input is recognized or not. It only prevents it from creating ambiguity by stating a preference for how the string is assigned to one of its multiple possible parses.
 
3. Features introducing new behaviours that affect the sets of strings recognized by an iXML grammar:

        • E.g. some ways of implementing negation. Context-free languages are not guaranteed to remain context-free if they are negated, so allowing negation of entire nonterminals without any other constraints would make iXML context-sensitive.
        • For example, assume that the operator ! could be used to negate a nonterminal, so that !Y means 'anything that does not match Y'. Now consider this grammar.

   ABC: !not_ABC.
   not_ABC: !a_BC; !AB_c.
   AB_c: AB, "c"*.
   AB: "a", AB?, "b".
   a_BC: "a"*, BC.
   BC: "b", BC, "c".

            • The nonterminal AB_c matches all strings with a matching (non-zero) number of "a"s and "b"s, followed by any (non-zero) number of "c"s, like "aabbc" or "abccccc" or "aabbcc".
            • The nonterminal a_BC matches all strings with any number of "a"s followed by a  matching number of "b"s and "c"s, like "abbbbcccc" or "aaabc" or "aabbcc".
            • Anything that matches both a_BC and AB_c must be a string with a matching number of "a"s, "b"s and "c"s, like "aabbcc".
            • We can't match the language containing only strings of equal numbers of all three characters using a context-free language. But, by adding negation to iXML, we introduce this ability. The negation of a_BC includes all the strings in AB_c that don't have an equal number of "a", "b", and "c"; the negation of a_BC contains all the strings in AB_c that don't have an equal number of "a", "b", and "c". So the only strings excluded from not_ABC are those with an equal number of "a", "b", and "c". By negating not_ABC, the root ABC therefore actually succeeds in matching only strings with an equal number of all three characters.

Because of the fundamental changes to the language that are possible by adding fairly basic features like negation, it is important to know whether a proposal is of type 1, 2, or 3 on this dimension.  

A new iXML specification grammar with various type 1 and/or type 2 changes would still be able to accept and reject exactly the same families of inputs.  
A new iXML with type 2 changes should be achievable by manipulating the parse forest after parsing. This may be difficult or expensive, so such changes shouldn't be made lightly. But they should be possible to implement without changing parsing algorithms, and without changing what can be recognized by an iXML grammar.  

On the other hand, adding totally new behaviours that affect what can be recognized could drastically alter what kind of language iXML is by introducing context-sensitivity, which has implications for how iXML parsers do their job. Anything that might require implementers to start using different parsing algorithms in their iXML processors, for example, should be treated with caution. 

___________________________________________________ 
Dr. Bethan Tovey-Walsh 

linguacelta.com

Golygydd | Editor geirfan.cymru

Croeso i chi ysgrifennu ataf yn y Gymraeg.