Subject: RE: [Ltru] Re: non-terminal names

From: "Kent Karlsson" <[email-masked]>
Date: Fri, 10 Feb 2006 11:09:38 +0100 (CET)

Frank Ellermann wrote:
> Thinking about the issue of the stars for some time I'd say we
> can radically simplify this.  In chapter 2.1:
>
> | basic-range   = basic-tag / "*"
> | basic-tag     = 1*8ALPHA *( "-" 1*8alphanum )
>
> In chapter 2.2:
>
> | language-range = langtag-range
> |                / privateuse
> |                / grandfathered
>
> | langtag-range  = (( language / "*" )
> |                   ["-" script]
> |                   ["-" region]
> |                   *("-" variant)
> |                   *("-" extension)
> |                   ["-" privateuse])
>
> We only need the cases "lone star" and "leading star", other
> stars are always redundant / implicit:

While this at first glance seems like a great simplification, it also
emphasises problems.

I don't have much qualms about approaches that essentially
say "one or more wildcards in a row is equivalent to one wildcard",
I find approaches that essentially say "**zero** or more wildcards
is equivalent to one wildcard"; one would expect *some* essential
difference (from experience with other uses of "wildcards").
And we not only have the latter in many cases here, but we also
have at least three different interpretations of what these
language tag patterns really mean.

It's like defining a programming language and then say
"this one syntax means three different things, depending on
which mode you have". While that happens also for programming
languages, it's far from ideal.

I'd like to keep the correspondence between patterns and their
semantics as simple as possible, without too many special cases
(like inserting "implicit stars" where they are "missing"). Further,
the stars mean different things and it is not entirely clear what
each occurrence means, some mean "any script", some mean
"any variant", etc. and may even be combinations of several
such "any"s.

It's far from as simple and straighforward as I'd like it to be...

		/kent k

_______________________________________________
Ltru mailing list
[email-masked]
https://www1.ietf.org/mailman/listinfo/ltru

---

From: Frank Ellermann <[email-masked]>
Date: Fri, 10 Feb 2006 23:27:55 +0100

> It's far from as simple and straighforward as I'd like

At least we're in the good position to heve four complete
ABNF proposals for the relevant scenarios:

1 - only lone or leading star is relevant for the special
    case "any language", the simple ABNF is in the article
    you've quoted.

2 - like (1) additionally allowing future "wildcard
    extensions".  Semantics to be defined in the document
    for the extension registry, proposed ABNF posted in
    <http://permalink.gmane.org/gmane.ietf.ltru/4397>

3 - Single embedded stars roughly as in -09 (after fixing
    an error in 2.1 and the -09 <extension> in 2.2).  For
    that "single embedded stars" must have some meaning,
    they can't be simply the same as "unspecified subtag".

4 - like (3) but using your *-pat syntax for most ranges.
    <http://permalink.gmane.org/gmane.ietf.ltru/4382> with
    | language-range = language / "*" / extlang-wild
    | extlang-wild   = 2*3ALPHA *2("-" 3ALPHA) "-*"
    and s/-range/-pat/g adding line breaks as necessary.

Same issue for (4) as for (3), if "embedded stars" outside
of <extension-pat> have no meaning they are useless.

There was still an issue for more than one <variant-pat>
resulting in arbitrary numbers of "embedded stars", also
affecting (3).  But it's possible to fix this by allowing
at most one <variant-pat> star in addition to <variant>s.

                          Bye, Frank

---

From: Mark Davis <[email-masked]>
Date: Mon, 13 Feb 2006 08:35:52 -0800

1. Can someone sum up all the proposed changes to 09, so that we can see 
a complete picture? I know you're trying to do that below, but it'd help 
to get a "change this text to that text" list.

2. Can someone familiar with the procedures comment on what the upcoming 
deadlines are? I know in the past we've been hit by the "miss by one 
day, wait for weeks" problems, so if we know what the upcoming process 
would be that would help to plan around our day jobs.

Mark

---

From: "Scott Hollenbeck" <[email-masked]>
Date: Mon, 13 Feb 2006 12:15:00 -0500

> -----Original Message-----
> From: Mark Davis [mailto:[email-masked]] 
> Sent: Monday, February 13, 2006 11:36 AM
> To: Frank Ellermann
> Cc: [email-masked]
> Subject: Re: [Ltru] Re: non-terminal names
> 

http://www1.ietf.org/mail-archive/web/ietf-announce/current/msg02155.html

-Scott-

---

From: Frank Ellermann <[email-masked]>
Date: Mon, 13 Feb 2006 20:34:51 +0100

Mark Davis wrote:

> it'd help to get a "change this text to that text" list.

Not yet clear with four proposals for the ABNF.  Nobody
commented on "allow future wildcard extensions", so that
was probably a bad idea.

Many wanted "whatever the ABNF is, let's reuse the 3066bis
productions".  For the "allow embedded stars everywhere"
many wanted <old-pat> for productions derived from <old>
in 3066bis.  But not for <extlang-pat> if it is only the
<extlang-wild> case unlike other <old-pat>.

So far nobody proposed a meaning for the "embedded stars",
they are apparently always redundant.  Therefore another
syntactical alternative is to allow only a leading / lone
star for the language.  Otherwise unspecified subtags
mean "any value".

The 2.1 ABNF has to be renamed and fixed as proposed for
compatibility with 3066 and the outsourced http-errata.
We could say "updates 2616" or reference its errata by
<http://purl.org/NET/http-errata>.

I recall a debate about the necessary difference between
"matching" and "filtering".  A simple example explaining
that would be nice.  But if we get rid of the hapless
stars that probably needs many minor editorial changes,
maybe it's better to decide / do that first.

;;; Last rough state of a terse "embedded stars" syntax
;;; (Kent prefers a style with one alternative per line):

basic-range   = basic-range / "*"
basic-tag     = 1*8ALPHA *( "-" 1*8alphanum )

language-range = langtag-pat
              / privateuse       ; private-use tag
              / grandfathered    ; grandfathered registrations

langtag-pat   = (language-pat
                 ["-" script-pat]
                 ["-" region-pat]
                 *("-" variant) ["-*"]
                 *("-" extension-pat)
                 ["-" privateuse])

language-pat  = language / "*" / extlang-wild
extlang-wild  = 2*3ALPHA *2("-" 3ALPHA) "-*"

script-pat    = script  / "*"
region-pat    = region  / "*"

extension-pat = extension
              / ( singleton *( "-" 2*8alphanum ) "-*" )

;;; Last known state of a "leading star" syntax:

basic-range   = basic-range / "*"
basic-tag     = 1*8ALPHA *( "-" 1*8alphanum )

language-range = langtag-range
              / privateuse       ; private-use tag
              / grandfathered    ; grandfathered registrations

langtag-range = (( language / "*" )
                 ["-" script]
                 ["-" region]
                 *("-" variant)
                 *("-" extension)
                 ["-" privateuse])

;;; either variant merged with the 3066bis ABNF is "valid"

---

From: Frank Ellermann <[email-masked]>
Date: Mon, 13 Feb 2006 20:52:48 +0100

> basic-range   = basic-range / "*"
  basic-range   = basic-tag / "*"
> basic-tag     = 1*8ALPHA *( "-" 1*8alphanum )

Sorry, Bill's validator is a bit weak with "do what I mean" ;-)

---

From: "Kent Karlsson" <[email-masked]>
Date: Mon, 13 Feb 2006 23:11:08 +0100 (CET)

Frank Ellermann wrote:
> they are apparently always redundant.

Really?

>  Therefore another

One could do it that way, but is that really the intent
for the -matching document? I.e. have them be redundant.
(If that is really the intent, they should be removed
from the syntax, as Frank suggests.)

I've been thinking a little bit about the semantics for
the pattern expressions. So here is some of my thoughts
about this so far.

--------------------------

Let's define a partial ordering relation among (language) tags.

Let
	'tag' be a non-empty sequence of subtags (that forms
		 a language tag, but that is not important for
		 defining the ordering relation)
	'-subtag': a subtag (legal to have after 'tag', but that is
		 not important for defining the ordering relation)

Then we define the partial order thus:

tag < tag-subtag

This defines the well established prefix matching as a partual order:
a tag is less specific than tag-subtag.

Sometimes it is convenient to have a smallest element in the ordering
relation, so we add * as that smallest element, turning the partial
order (p.o.) into a complete partial order (c.p.o.):

* < tag

The smallest element is sometimes referred to as bottom; it is the
least specific extended language tag (that i-default, in the IETF
language tag world, may be another name for * is another issue).

3066bis introduces a small complication: "suppress-script".
I guess primary language subtags that have a "suppress-script",
should have that script subtag inserted, if there is no explicit
script subtag, before comparisons.

--------------------

The matching draft introduces another set of extended values, and
another way of doing matching than the prefix matching. Let's try
to formulate that other kind of matching as a c.p.o.:

Let
	'tagp' be a non-empty sequence of subtags, allowing *
		as a subtag, but that isn't just *
	'-subtagps' be sequence of subtags, may be empty, allowing *
		 as a subtag, but that isn't just *
	'-sbtgps' be like '-subtagps' but another instance

We still want * to be the smallest element, and more generally we want
*-subtagps be less specific than tagp-subtagps:

*-subtagps < tagp-subtagps

If a * occurs in the middle or end of the tag pattern that is less
specific than having something (including empty?) in place of the *:

tagp-*-subtagps < tagp-sbtgps-subtagps

Is it reasonable to require -sbtgps to be non-empty? Should -sbtgps
really be allowed to be more than one subtag (incl. *)?

One could include the old prefix matching rule here:

tagp < tagp-subtag

but we already have the more explicit tagp-* < tagp-subtag as a
consequence of rule tagp-*-subtagps < tagp-sbtgps-subtagps.

With the prefix matching rule here we have e.g.:

	ln-* < ln < ln-Srpt

but without it we still have (e.g.):

	ln-* < ln  and ln-* < ln-Srpt

but not
	ln < ln-Srpt

Should we really include the prefix matching rule for the
case where there is a more explicit way of saying "prefix match"
(star at the end)?

Again I guess primary language subtags that have a "suppress-script",
should have that script subtag inserted, if there is no explicit
script subtag, before comparisons.

What about the "types of matching" in section 3?

For either the "basic" or "extended" c.p.o. as above (ignoring
the question marks for the extended one for the moment), and just
considering one "pattern" (extending to a priority list is not
the interesting part just now):

Let p be a language tag pattern (basic or extended), S a set
of language tags (no pattern). Define

	Lookup(S, p) = sup({x in S | x <= p})

where sup(Q) for an upwardly closed set Q, returns the smallest
element in the c.p.o. that is larger than all elements in Q.
Note that the result need not be in Q. In particular sup({})
is *. Note that the argument to sup is upwardly closed (by p).
For the "basic" c.p.o. Lookup will only return * or a language tag.
For the "extended" c.p.o. Lookup now may also return a "pattern"
other than * (in case of several maching elements that aren't
comparable). Or... we may modify the definition of Lookup to
return the set of "largest" elements, in S, that match p.
(I don't really like the suggestion to "take the first one
in (lowercase?) ASCII order...)

For a nonempty priority list of patterns, [p1, p2, ..., pn],
define

	Lookup(S, [p1, p2, ..., pn]) =
		Lookup(S, p1) # Lookup(S, p2) # ... # Lookup(S, pn)

where
	* # p = p
	p # q = p   if p is not *

Also for either the "basic" or "extended" c.p.o. as above (ignoring
the question marks for the extended one for the moment), and just
considering one "pattern" (extending to a priority list is not
the interesting part just now):

Define

	Filter(S, p) = {x in S | x >= p}

For a nonempty list of patterns, [p1, p2, ..., pn], define

	Filter(S, [p1, p2, ..., pn]) =
		Filter(S, p1) U Filter(S, p2) U ... U Filter(S, pn)

where U is set union.

---------------------

Scored filtering seems to be an entirely different beast. Not
sure what to do with that one (other than leave it alone).

		/kent k

---

From: John Cowan <[email-masked]>
Date: Mon, 13 Feb 2006 17:45:47 -0500

> specific than having something (including empty?) in place of the *:

Lacking a subtag has always been equivalent to being least specific:
if "country" is missing, then there is no specific country.  
Thus there is no distinction between a '*' subtag and an empty or missing
subtag.  Syntactically, we need the ability to write '*' in the first
(language) position for two reasons:

	the tag (not subtag) "" means "no language", not "totally unspecific
	language" (this is an extension to RFC 3066bis used in XML)

	two-letter tags mean different things depending on whether they
	are initial or not -- "uk" is unrelated to "en-uk".

> really be allowed to be more than one subtag (incl. *)?

Once the above ambiguity is dealt with, one can take apart any valid tag
into its four components (or more in later RFCs) unambiguously.

> 	ln-* < ln  and ln-* < ln-Srpt

If "ln-*" is dropped in favor of just "ln", then the two rules agree nicely.

> case where there is a more explicit way of saying "prefix match"

Yes, for backward compatibility (it is the rule of HTTP 1.1).

> script subtag, before comparisons.

That's not required for prefix-matching, fortunately.

-- 
You let them out again, Old Man Willow!                 John Cowan
What you be a-thinking of?  You should not be waking!   [email-masked]
Eat earth!  Dig deep!  Drink water!  Go to sleep!       www.ap.org
Bombadil is talking.                                    www.ccil.org/~cowan