Subject: ABNF sets and sequences

From: Dave Crocker <[email-masked]>
Date: Sat, 08 Jul 2000 03:19:59 +0100

Folks,

Some issues just won't go away.

The fact that some parameter lists are ordered and others are not is 
problematic for ABNF-based specifications.  We end up relying on obscure 
text in the prose and/or on community memory.

We hassled this within Drums quite a bit but I want to raise it again.

Simply put, the goal is to permit "concatenation" -- ie, lists -- to be 
labeled as unordered sets or ordered sequences.  The default would be 
ordered, as it is now.  The modification to ABNF would be from:

         group          =  "(" *c-wsp alternation *c-wsp ")"

         option         =  "[" *c-wsp alternation *c-wsp "]"

to:

         group          =  order "(" *c-wsp alternation *c-wsp ")"

         option         =  order "[" *c-wsp alternation *c-wsp "]"

         order           = "SET" / "SEQ"
				; unordered vs. ordered, default SEQ

It would be interpreted somewhat like <repeat> construct, in that it only 
affects the specification rule it is defined in.

OK?

Start shooting...

d/

         group          =  "(" *c-wsp alternation *c-wsp ")"

         option         =  "[" *c-wsp alternation *c-wsp "]"

=-=-=-=-=
Dave Crocker  <[email-masked]>
Brandenburg Consulting  <www.brandenburg.com>
Tel: +1.408.246.8253,  Fax: +1.408.273.6464
675 Spruce Drive,  Sunnyvale, CA 94086 USA

---

From: Robert Elz <[email-masked]>
Date: Sat, 08 Jul 2000 14:13:04 +1000

Date:        Sat, 08 Jul 2000 03:19:59 +0100
    From:        Dave Crocker <[email-masked]>
    Message-ID:  <[email-masked]>

Just on the trivial parts of this for now, I need to go back
and re-remember what difficulties with this were last time (as
I reall there were some specification problems that got real hard).

But...

  |          order           = "SET" / "SEQ"
  | 				; unordered vs. ordered, default SEQ

The "default SEQ" there makes no sense unless you change it to

		order = "SET" / "SEQ" / ;

  |          group          =  order "(" *c-wsp alternation *c-wsp ")"
  |          option         =  order "[" *c-wsp alternation *c-wsp "]"

These mean
		stuff = SET( a / b / c )
is legal, but

		stuff = SET ( a / b / c )
is not?

Was that the intent, or should there be *c-wsp added somewhere?

  | It would be interpreted somewhat like <repeat> construct, in that it only 
  | affects the specification rule it is defined in.

That I think was one of the problems with the earlier attempt, I'm
not sure it was the only one, was it?

With this, there is still no way to (using the stuff above) to say
that any of

	a b c
	b c a
	c a b

are legal, but

	a b

is not (ie: to require all the elements at least once) and

	a a b c

is not (ie: no repeated elements), etc.

If all that is to continue to require text, then I'm not sure
that adding this adds enough to be worth the bother.

And OK, now I remember the real problem with this.  That was, if
we augment stuff with

	a = SET( x / y )

then we now allow

	x y b c
	y x b c
	b x y c

(etc, but not)

	x b y c

which is, in practical applications, what is needed.  That is, for
rfc822bis you want to have a selection of header types, each of which
contains a selection of headers, but without imposing any constraints
upon the ordering at all.  The header-types are needed as sometimes
constraints need to be applied to those, and in any case it is just
convenient to be able to refer to them as a group.

Solving that one was what was so hard it made the whole idea
not worth the effort - it was certainly never the syntax by which
the notions were written, which is all that seems to have changed here.

kre

---

From: Keith Moore <[email-masked]>
Date: Sat, 08 Jul 2000 09:02:21 -0400

> OK?

uh, no.  

a) it's too late in the DRUMS process to consider changing the ABNF,
at least for this version of DRUMS.  if this is really important then
it might be good to revise the ABNF document, but this should not delay
the other work that DRUMS is doing.  my guess is that the ADs want to 
close DRUMS down ASAP, so any changes to ABNF would be a post-DRUMS 
activity.

b) there's more than one kind of ordering.  I'm not sure which
you're talking about:

- things are required to appear in some order if they do appear
  this can already be represented in ABNF, e.g.:  

  [ thing1 ] [ thing2 ] [ thing3 ]

- things can appear in any order but the order of things is significant.
  this is not a matter of syntax, but of interpretation of the syntax -
  so it doesn't belong in ABNF.

Keith

---

From: Pete Resnick <[email-masked]>
Date: Sat, 8 Jul 2000 11:36:00 -0500

On 7/8/00 at 9:02 AM -0400, Keith Moore wrote:

>a) it's too late in the DRUMS process to consider changing the ABNF

This I agree with, but there's no harm discussing it on this list.

>[...]

It's neither of those. It's:

- things can appear in any order and the order of things is not significant.

However, addressing the issues in Robert's message is really the big problem.

pr
-- 
Pete Resnick <mailto:[email-masked]>
Eudora Engineering - QUALCOMM Incorporated
Ph: (217)337-6377 or (858)651-4478, Fax: (858)651-1102

---

From: Keith Moore <[email-masked]>
Date: Sat, 08 Jul 2000 13:02:27 -0400

> - things can appear in any order and the order of things is not significant.

but no more than one of those things can appear at any time?

otherwise you just say  *( thing1 / thing2 / thing3 )

why would this be needed?

---

From: Pete Resnick <[email-masked]>
Date: Sat, 8 Jul 2000 12:18:36 -0500

>but no more than one of those things can appear at any time?

Right.

>why would this be needed?

From: [email-masked]
To: [email-masked]

or even the items in:

Received: from astro.cs.utk.edu (LOCALHOST [127.0.0.1])
         by astro.cs.utk.edu (cf 8.9.3) with ESMTP id NAA02698;
         Sat, 8 Jul 2000 13:02:27 -0400 (EDT)

We don't care if "by" comes before or after "with", but we do care 
how many of them there are.

pr

---

From: Keith Moore <[email-masked]>
Date: Sat, 08 Jul 2000 13:42:32 -0400

I don't think it's reasonable to try to represent the rules for
header fields fully in ABNF.  reasons:

1. there are a lot more cases than "no more than once" - there
are fields that must occur once, other fields that may occur
at most once, and still other fields that may occur any number
of times.  so the syntax to represent this gets a lot more moby.

2. unlike the rest of ABNF, such a syntax would not easily be
translated into something that a parser generator could 
understand. in other words, changing ABNF in this way impairs
its ability to be read by machines.

3. notation that isn't used very often actually hinders readability 
to humans also - it is like using too many levels of 
function/subroutine/method/abstraction when writing code. 

4. if you're writing a parser for mail and you encounter multiple
use of the same "at most once" header field (or whatever),
chances are that you *don't* want the parser to handle this 
error by itself - you want to look at the field that is duplicated
and see whether it makes more sense to flag the error, ignore it, 
whatever.  e.g. for some reason a lot of mail that I receive
has multiple content-transfer-encoding fields, but it's not a problem
as long as the fields have the same value.  this isn't the sort
of thing you can encode into syntax.

so to me it makes more sense to specify these rules outside of the ABNF
ideally, the implementor can translate the ABNF into the parser and
the prose rules into additional error checking code.  if the implementor
has to rewrite the ABNF significantly in order to build a parser from
it, and has to extract out error checking rules in the process, this
is a pessimal result.

Keith

---

From: Dave Crocker <[email-masked]>
Date: Sat, 08 Jul 2000 22:55:47 +0900

>Was that the intent, or should there be *c-wsp added somewhere?

probably both sides of <order>,  never meant to prohibit typical use of 
white space.

I'll be ecstatic if that is the level of problem the proposal has...

>not sure it was the only one, was it?

I think we all got seduced into looking at a horribly complicated effect of 
apply the (non)ordering to subordinate rules.  The interpretation needs to 
be exactly the way we apply the repetition construct.

>With this, there is still no way to (using the stuff above) to say

perhaps.

I am frankly worried only about having labeled parameter lists (e.g., a=b, 
or c:d) specified in ABNF in a way that makes explicit IN THE SYNTAX that 
the paramaters may occur in any order

>is not (ie: to require all the elements at least once) and

Hmm.  What is wrong with:

         rule = SET ( a b c )

>that adding this adds enough to be worth the bother.

Just fixing the problem for labeled parameter lists (like RFC822-derived 
header lists...) would be enough for me.

Nothing wrong with also handling the extra scenarios you suggest.

>And OK, now I remember the real problem with this.  That was, if

         (x / y) means x or y (but not both.)  That is a single-element 
result.

         Set constructs are not meaningful for it.  Need to produce at 
least two elements.

>a) it's too late in the DRUMS process to consider changing the ABNF,

Procedurally, I'd suggest issuing the enhancement as a new Proposed Draft 
and then merging it when the whole thing can go to Draft.

Alternately, ABNF has been at Proposed long enough to make it minimal 
impact to recycle the whole thing, with the revision.

>the other work that DRUMS is doing.  my guess is that the ADs want to

Ahh.  Status dependency.  Sigh, yes.

In  that case, advancing the current spec to Draft and issuing the 
enhancement separately, merging it as possible.

>- things can appear in any order but the order of things is significant.

I don't know exactly what that means, but it is not what I was thinking or 
suggest.  SEQ is what we have now.  SET just takes away the ordering 
requirement of the CURRENT, implied seq.

d/

=-=-=-=-=

---

From: Dave Crocker <[email-masked]>
Date: Sun, 09 Jul 2000 11:58:24 +0900

>1. there are a lot more cases than "no more than once" - there

handling every possible case is rarely a goal.  handling the important and 
popular cases is.  that's what the proposal attempts.

>translated into something that a parser generator could

ASN.1 parsers handle it just fine.

>3. notation that isn't used very often actually hinders readability

The motivation for this is that it IS needed with regularity, namely for 
every list of labeled parameters.  Such lists are ALWAYS unordered.  That's 
the reason for the labels.

>and see whether it makes more sense to flag the error, ignore it,

Email has a history of very poor conformance.  The more that things are 
caught up-front, the better.

d/

ps.  For everyone:

         The goal of my original posting was to re-raise an issue and 
explore pursuing it.  The note was not attempting to provide a complete 
proposal, but rather an exemplar of the type of solution that seemed close 
to the right answer.  Frankly I do not care how the details are achieved, 
including use of an entirely different approach.  Solving the requirement 
-- for being able to specify unordered lists -- is the concern.

=-=-=-=-=

---

From: Keith Moore <[email-masked]>
Date: Sun, 09 Jul 2000 00:56:56 -0400

> popular cases is.  that's what the proposal attempts.

okay, maybe I should reword my statement more specifically.

having this notation will not significantly simplify or clarify
the specification for Internet mail.

now it may be that there is some other justification for this
notation.  I just don't know what it is..  

> ASN.1 parsers handle it just fine.

I fail to see how this is relevant.

ASN.1 is a language for describing the structure of data
(BER maps that structure onto a presentation), but ASN.1
is not a language for writing a parser for some already-defined
presentation of data.  You can write an RFC 822 parser in yacc,
but you can't write one in ASN.1

and even though ASN.1 has a construct similar to what you are
describing, this is hardly an argument for providing it.
ASN.1 is not widely regarded as a particularly good notation for 
describing protocols.   one of ASN.1's many mistakes is trying 
to do too much verification at the presentation layer.  another
is having too rich a notation- too many constructs of dubious utility.

> the reason for the labels.

in many of these cases (e.g. any time the list of labels is extensible)
it's a bad idea to specify the parameter labels as literals anyway.

in other words, it's bad style to write

	list = *( "thing1" / "thing2" / "thing3" / extension-thing )

when you could instead write 

	list =  *elem

	elem = token 

	; the same token MUST NOT be generated twice in a list
	; initially defined elems are "thing1", "thing2", and "thing3".

because if you write the former then the programer has to recode
the grammar into the latter format anyway.   you've just made
his job harder.

and you really do want to separate parsing of the list elements
from semantic processing of the list elements, and handling of
duplicate elements (even if this is a protocol violation) 
tends to involve semantic interpretation.

and even if you had the list-of-items-no-more-than-once notation,  
it doesn't extend well to handle new items.   consider the case
above - if a list is allowed to include 'extension-thing' in
addition to "thing1" "thing2" and "thing3" then it can contain
at most one 'extension-thing' rather than an arbitrary number of them.

> caught up-front, the better.

if we could catch things before they are sent, I'd agree with you.
but I don't know of any incentive that is likely to get mailers
to be very conservative about messages that they send (and do
rigid syntax checks on them beforehand), while on the other hand 
there appear to be plenty of incentives  for receivers to make
sense of whatever garbage they receive.

Keith

---

From: Dave Crocker <[email-masked]>
Date: Mon, 10 Jul 2000 11:42:21 +0900

>the specification for Internet mail.

1.  The construct that is at issue cannot reasonably be specified in 
current ABNF.

2.  The construct occurs regularly, such as for 822-like headers, labeled 
parameters in Received headers, etc.  This is not a small or occasional issue.

3.  Putting the qualifier in the prose is a good way a) to get missed, or 
b) not to get specified.

Absence of this, for in RFC 1894, is what re-triggered my interest in this 
topic.  One might argue that misunderstanding this relaxation of the 
apparent syntactic requirement for ordering is "merely" a matter of 
acculturation -- one must be fully plugged in to the protocol development 
community.  That is a requirement that has scaling problems.

While few implementation errors can be documented by this unfair 
requirement, growth of the Internet should encourage us to make common 
constructs easier to specify and harder to miss.

>Now it may be that there is some other justification for this notation.  I 
>just don't know what it is..

The working group felt it was worth adding earlier.  We just couldn't 
figure out how.  I now believe that was because we tied it to alternation 
(a / b) rather than concatenation (a b) and repetition, where it belongs.

In any event, the point you raise reduces to whether the community thinks 
it is useful to have the construct in ABNF.  I do; you don't.  Others will 
decide.

>I fail to see how this is relevant.

See below.

>ASN.1 is a language for describing the structure of data

as is ABNF.

>presentation of data.  You can write an RFC 822 parser in yacc,

yacc is the programming language, not ASN.1.

>but you can't write one in ASN.1

asymmetric comparison:

         <822 headers, or whatever> : abnf : yacc

should be compared with:

         <822> : asn.1 : <???>

>describing protocols.   one of ASN.1's many mistakes is trying

It is used.  It works.  Some like it; some don't.  That's all fine, but 
entirely irrelevant.

You made a specific claim of non-implementability.  I cited an existence 
proof to contradict your specific claim.

I was not making a wholesale statement of support for ASN.1 and a wholesale 
attack on it is not relevant.  Nor are other issues about ASN.1 relevant.

>         list = *( "thing1" / "thing2" / "thing3" / extension-thing )

You keep using the alternation construct.

Let's get specific about how the construct probably should be used:

RFC 1894:

>2.2 Per-Message DSN Fields
>
>    Some fields of a DSN apply to all of the delivery attempts described
>    by that DSN.  These fields may appear at most once in any DSN.  These
>    fields are used to correlate the DSN with the original message
>    transaction and to provide additional information which may be useful
>    to gateways.
>
>      per-message-fields =

         SET (

>           [ original-envelope-id-field CRLF ]
>           reporting-mta-field CRLF
>           [ dsn-gateway-field CRLF ]
>           [ received-from-mta-field CRLF ]
>           [ arrival-date-field CRLF ]
>           *( extension-field CRLF )

         )

and in draft-ietf-drums-msg-fmt-07.txt:

>name-val-list   =       [CFWS] [name-val-pair *(CFWS name-val-pair)]

becomes

>name-val-list   =       [CFWS]  SET [name-val-pair *(CFWS name-val-pair)]

and

>fields          =       *(trace
>                           *(resent-date /
>                            resent-from /
>                            resent-sender /
>                            resent-to /
>                            resent-cc /
>                            resent-bcc /
>                            resent-id))
>                         *(orig-date /
>                         from /
>                         sender /
>                         reply-to /
>                         to /
>                         cc /
>                         bcc /
>                         message-id /
>                         in-reply-to /
>                         references /
>                         subject /
>                         comments /
>                         keywords /
>                         optional-field)

becomes something like:

>fields          =

                 SET (
>                           *(trace
>                           *(resent-date /
>                            resent-from /
>                            resent-sender /
>                            resent-to /
>                            resent-cc /
>                            resent-bcc /
>                            resent-id))
                 )
                 SET (
>                         *(orig-date /
>                         from /
>                         sender /
>                         reply-to /
>                         to /
>                         cc /
>                         bcc /
>                         message-id /
>                         in-reply-to /
>                         references /
>                         subject /
>                         comments /
>                         keywords /
>                         optional-field)
                 )

(small point of curiosity, for Pete or whoever:  the current syntax for 
<message> seems to mean that message headers are either fields or 
obs-fields, but not a combination?)

Anyhow, folks, I would appreciate some technical feedback on this. The 
philosophical line of debate is probably played out.

d/

=-=-=-=-=

---

From: Philip Guenther <[email-masked]>
Date: Sun, 09 Jul 2000 22:43:52 -0500

Dave Crocker <[email-masked]> writes:
...
>>name-val-list   =       [CFWS]  SET [name-val-pair *(CFWS name-val-pair)]

That syntax makes no separation between the 'tag' that cannot be
repeated and what is being repeated.  That is, it would appear to ban
the following:

    To: [email-masked]
    To: [email-masked]

But not this:
    To: [email-masked]
    To: [email-masked]

Or even:
    To: [email-masked]
    To:     [email-masked]

Such an ABNF operator would have to explicitly specify what part of the
repeated content is required to be unique.  The uniqueness constraint
also has be made on the semantic value of the token, no?
    To: [email-masked]
    tO: [email-masked]

How about obsolete syntax:
    To: [email-masked]
    To : [email-masked]

Philip Guenther

----------------------------------------------------------------------
[email-masked]		UNIX Systems and Network Administrator
Gustavus Adolphus College	St. Peter, MN 56082-1498
Source code never lies: it just misleads (Programming by Purloined Letter?)

---

From: Keith Moore <[email-masked]>
Date: Mon, 10 Jul 2000 00:39:30 -0400

> 1.  The construct that is at issue cannot reasonably be specified in 

correct.  languages like ABNF have limitations.  they don't specify
semantics either, but that doesn't prevent them from being useful.

> parameters in Received headers, etc.  This is not a small or occasional issue.

the construct you suggest will not allow ABNF to specify the rules for
822 headers with any greater deal of precision.

you're trying to make a grammar do a job that it cannot do well.
language specialists have understood for years that replacement grammars
have inherent limitations - they cannot fully describe arbitrary languages.
such limitations are well documented in the literature.  this doesn't 
prevent grammars from being useful as part of specification languages, 
but it's a mistake to try to get them to do things that they cannot do well.

for instance -and this is a fairly classic example - most programming
languages require that a variable be declared before it can be used.
it turns out that (if there are arbitrary number of possible variable
names) it is impossible to write a replacement grammar that enforces 
this rule.

the problem you are trying to solve with ABNF is essentialy the same problem 
if the list of valid tokens that can appear "at most once" is extensible.

now, can you design a notation that says "you can specify each of these
tokens at most once"?  of course you can.  but it's not a simple change
to ABNF - it doesn't mesh well with ABNF-style notation.  

> 3.  Putting the qualifier in the prose is a good way a) to get missed, or 

understood.  but trying to do it in ABNF is an even worse fit.

> community.  That is a requirement that has scaling problems.

in hindsight, 822 should have used 

* ( thing )

thing = (thing1 / thing2 / thing3 )

rather than

[ thing1 ] [ thing2 ][ thing3 ]

822 tried to specify things with ABNF that ABNF (and any replacement grammar)
really cannot specify well.

> constructs easier to specify and harder to miss.

I'm all for trying to reduce the number of misunderstandings in a 
specification, but we cannot do this if we misunderstand the limitations
of our specification language.

> (a / b) rather than concatenation (a b) and repetition, where it belongs.

I now believe that it's because you are trying to do something with ABNF 
that it cannot do well.

if you really want to specify this more formally than in prose, you need
a different kind of notation than a replacement grammar.

> it is useful to have the construct in ABNF.  I do; you don't.  Others will 

what seems useful may still not be feasible.
a perpetual motion machine would presumably be useful also.

> >ASN.1 is a language for describing the structure of data

yes, but you were responding to my comment that the ABNF extension
you proposed would not be easily translated to a parser generator.
so your comment about ASN.1 in that context was a red herring.

> yacc is the programming language, not ASN.1.

yacc is a programming language for writing parsers.
you can more-or-less translate ABNF into yacc, or similar languages.
you cannot translate ABNF into ASN.1
 
>          <822 headers, or whatever> : abnf : yacc

doesn't make sense.  you can't describe 822 with asn.1

> proof to contradict your specific claim.

uh, no.  you cited a red herring.

> You keep using the alternation construct.

yes, because that's the best way to describe this in a grammar.

> >           *( extension-field CRLF )

no, this doesn't work, because you want to be able to have more than
one extension-field, and you want to be able to freely mix these
fields in any order with the other fields.  

you're notation tries to change the meaning of * and [ ] within the SET
construct.  this is a lot more confusing than just writing
"can occur at most once" in prose.

> >name-val-list   =       [CFWS]  SET [name-val-pair *(CFWS name-val-pair)]

you're still enforcing ordering here that shouldn't be there; you're 
insisting that trace and resent fields occur before other fields.
(or did you intend this?  it's not consistent with current usage)

and the above notation would still allow arbitrary numbers of
each field to appear - because SET  ( *(foo) )  means that
*(foo) can occur at most once - but *(foo) means that foo can 
occur zero or more times.  so SET ( *(foo) ) is equivalent to *(foo). 

so no, in addition to this notation being incompatible with rewrite
grammars, it doesn't do what you think it does either.

> Anyhow, folks, I would appreciate some technical feedback on this. 

you've gotten some.  

Keith

---

From: Robert Elz <[email-masked]>
Date: Mon, 10 Jul 2000 13:19:09 +1000

Date:        Sat, 08 Jul 2000 22:55:47 +0900
    From:        Dave Crocker <[email-masked]>
    Message-ID:  <[email-masked]>

  | Hmm.  What is wrong with:
  | 
  |          rule = SET ( a b c )

OK, if that is what it is to mean (your original message was rather
slim on semantic detail).

So it is possible to require each of N elements once, in any order.
But how does one allow any of the elements to occur more than once,
and still be in any order.

	rule = SET ( *a *b *c )

cannot be it, as that would allow

	*a *b *c   or   *b *a *c   or   *c *b *a   (etc)

but then when the *a is expanded, all the a's need to occur
next to each other, and a b a c cannot be generated.

  | Just fixing the problem for labeled parameter lists (like RFC822-derived 
  | header lists...) would be enough for me.

Does this really fix that - would you care to actually send in the
grammar for something this would actually properly solve in 822?

  |          (x / y) means x or y (but not both.)  That is a single-element 
  | result.
  | 
  |          Set constructs are not meaningful for it.  Need to produce at 
  | least two elements.

Ah, I see, I was confused by ...

in your original message.  "alternation" is  a / b

But now I also see that in the accompanying text, you said concatenation
rather than alternation, so I guess some revision went on during the
composition of that message, but didn't get applied everywhere...

I still don't think this does enough to actually be useful.  And making it
do more, starts making things get horribly complex - there was a reason
we started down towards that "horribly complicated effect of 
apply the (non)ordering to subordinate rules" ...

kre

---

From: Robert Elz <[email-masked]>
Date: Mon, 10 Jul 2000 13:47:03 +1000

Date:        Mon, 10 Jul 2000 11:42:21 +0900
    From:        Dave Crocker <[email-masked]>
    Message-ID:  <[email-masked]>

  | The working group felt it was worth adding earlier.  We just couldn't 
  | figure out how.  I now believe that was because we tied it to alternation 
  | (a / b) rather than concatenation (a b) and repetition, where it belongs.

I'm not sure that makes much of a difference, ABNF is recursive, everything
includes everything else.  One possibility for an alternation is a single
concatenation, and a concatenation can be a single repetition, which can
be just an unadorned element, which can be a group, which is just an
alternation inside parentheses.

  | In any event, the point you raise reduces to whether the community thinks 
  | it is useful to have the construct in ABNF.  I do; you don't.  Others will 
  | decide.

I think it might be useful if it can be fully defined, and demonstrated.

  | Let's get specific about how the construct probably should be used:

  | >      per-message-fields =
  | 
  |          SET (
  | 
  | >           [ original-envelope-id-field CRLF ]
  | >           reporting-mta-field CRLF
  | >           [ dsn-gateway-field CRLF ]
  | >           [ received-from-mta-field CRLF ]
  | >           [ arrival-date-field CRLF ]
  | >           *( extension-field CRLF )
  | 
  |          )

Which looks fine, until someone reads it and says "see, all the extension
fields included need to be adjacent to each other" as the SET construct
only affects the objects directly in the group, not those one level
further down.  To avoid this, a more complex operator definition is
needed for SET, or text is needed to explain that no, it is after all legal
to have an extension field, then one of the defined fields, and then
another extension field.

  | and in draft-ietf-drums-msg-fmt-07.txt:
  | 
  | >name-val-list   =       [CFWS] [name-val-pair *(CFWS name-val-pair)]
  | 
  | becomes
  | 
  | >name-val-list   =       [CFWS]  SET [name-val-pair *(CFWS name-val-pair)]

Which makes exactly what difference???

I think Keith's point was that as written, name-val-list already allows
the name-val-pairs to occur in any order (because which particular name-val-pair
is the first, and which is the second, isn't defined.

  | and

  | becomes something like:
  | 
  | >fields          =
  | 
  |                  SET (
  | >                           *(trace
  | >                           *(resent-date /
  | >                            resent-from /
  | >                            resent-sender /
  | >                            resent-to /
  | >                            resent-cc /
  | >                            resent-bcc /
  | >                            resent-id))
  |                  )

This isn't achieving what you'd hope - it as it was without the
SET will generate exactly the same as it does with the SET.  There
is no SET covering the resent-* headers included, they're just one
element in the included concatenation.  On the other hand, the *( / / /)
allows the elements included to appear any number of times in any
order.

  |                  SET (
  | >                         *(orig-date /
  | >                         from /
  | >                         sender /
  | >                         reply-to /
  | >                         to /
  | >                         cc /
  | >                         bcc /
  | >                         message-id /
  | >                         in-reply-to /
  | >                         references /
  | >                         subject /
  | >                         comments /
  | >                         keywords /
  | >                         optional-field)
  |                  )

Again there, the SET adds nothing, the fields can already occur any
number of times in any order.   The problem that Pete's current grammar
has, if it has one, is that it doesn't include "Only one From:" header,
it allows any number of the things (and all those other headers as well).
If you remove the *() from that, and include [ ] around all the elements
that are optional, yu get closer to what you intended, but even that
doesn't correctly allow the relationship between From and Sender to be
included, nor the "must have one destination field" (though I forget if
we decided to keep that rule - but for ABNF purposes, assume we did).

And since "optional-field" would need to become *optional-field rather
than [optional-field] you get back to the same problem that all the
optional-fields that are included would have to be adjacent.

  | Anyhow, folks, I would appreciate some technical feedback on this. The 
  | philosophical line of debate is probably played out.

If you want a proper technical debate I think we'd need a proper technical
specification to review.  As it is now, philosophy is about all that can
be debated, there aren't enough details for anything else.

kre

---

From: Graham Klyne <[email-masked]>
Date: Mon, 10 Jul 2000 17:31:49 +0100

>text in the prose and/or on community memory.

It's a long time since I studied this stuff formally, but in the murky 
recesses of my memory I think there are some fundamental reasons why "these 
constructs in any order" is a tricky issue to tackle at the level of 
"grammar definition by syntax productions".

Most work on syntax definition in this way is focused on "context free" 
languages, in which it is possible to define the parse structure of a 
language in a way that has certain well-defined properties -- I think the 
general class of such languages is sometimes known as "Chomsky type 2".

ABNF is one of many variants of this basic framework for syntax description.

The problem with introducing a definition of "allow in any order" is that, 
in its more general cases, it breaks the "context free" language form, and 
the attendant well-understood properties.

It is quite possible to introduce a limited form of "allow in any order", 
but these limited forms can be expressed anyway; e.g.

     sentence = a b | b a

     sentence = a b c | a c b | b a c | b c a | c a b | a b a

Clearly, as the number of options increases, this approach becomes 
unwieldy.  (For n options, n! alternatives are needed.)

When the number of options to "allow in any order" are not known in 
advance, then the result cannot be described within the constraints of a 
context free language description.  (This happens when arbitrary 
re-occurrences are allowed.)

Of course, one is not forced to stick to the "context free approach".  The 
Algol 68 language specification attempted to overcome the limitations of 
context free grammars, and introduced a two-level definition structure that 
allowed some of the context dependencies to be captured in the formalism 
used.  That scheme was, IIRC, quite difficult to understand and I don't 
believe it has been attempted since.

My point is this:  while I have great sympathy for your goal, I think the 
pain of capturing "allow in any order" in the syntax formalism may end up 
exceeding the gain.

In his response, I think Nick Shelness touches an important point:

>1. Do Dave's two new proposed constructs (if defined with enough rigor)
>allow a human being to more easily distinguish whether an arbitrary string
>is legal or not? My gut feeling is that they do, though clearly there are
>some nasty problems to be solved. For example, under Dave's proposed
>notation, are the two grammars
>
>   foo = SET ( "a" "b" *("c"))
>
>and
>
>    foo = SET ( "a" "b" c)
>    c = *("c")
>
>equivalent?

I could easily define an "allow in any order" structure that does not 
interact with repetition.  But it wouldn't meet your goals.  e.g.

    foo = BAG ( "a", "b", *("c") )

or

    foo = BAG ( "a", "b", c )
    c   = *("c")

Here, the commas are used to make it clear what is "in scope" of the BAG 
construct, and what is internal to the set members.  But but still doesn't 
allow me to express that

    c b a c

is a valid sentence.  According to the formalism, the repeated "c"s must be 
contiguous.

To meet (my understanding of) your goal, a construct is needed that 
combines the SET and repetition options.  I could imagine such a construct; 
e.g.

    BAG ( ("a") ("b") *("c") )

where the parentheses surrounding "a", "b", "c", and any applied 
repetition, are part of the SET construct.  One might find a more 
comfortable syntax, but great care would be needed to ensure that it is 
clear whether any repetition of part of the BAG or part of a contained 
element.  Compare the above with:

    BAG ( ("a") ("b") (*("c")) )

SO:  I think what you propose is possible, but is it really helpful?

Programming languages have long lived with the idea that formal syntax is a 
useful tool for describing the structure of a program, but that it is not 
possible to define _exactly_ what constitutes a valid program with formal 
syntax alone.  Normally, we have the requirement that any valid program 
MUST satisfy the formal syntax, and in addition must satisfy additional 
semantic constraints (variables must be declared, a variable appears only 
once in a lexical scope, etc.).

One problem with the current approach to using ABNF in the e-mail documents 
is that a valid sentence is not required to conform to the formal 
syntax.  The formal syntax is stated, and then, in the text, is a "semantic 
escape clause" that says that the ordering of headers is relaxed.  Maybe 
this is the real source of the confusion or oversight you sense.

To define a syntax that is valid for all email messages, in a fashion more 
consistent with typical programming language definitions, the concatenation 
could be replaced by a global repeat construct containing alternatives, and 
semantic statements in the text used to indicate whether or not any given 
header may be repeated:

     headers = *header
     header  = from-header /
               to-header   /
               cc-header   /
               bcc-header  /
                :
               etc.

I would also assert that this leads to a structure that is much closer to 
how many programmers would actually implement message format validation.

#g

------------
Graham Klyne
([email-masked])

---

From: Chris Newman <[email-masked]>
Date: Mon, 10 Jul 2000 14:18:44 -0700

The underlying problem with 822, DSN and similar drafts was that the formal 
syntax was incorrect -- it gave a specific order for the headers.  Then 
obscure prose retroactively changed the rules for the incorrect formal 
syntax.

822bis has fixed the problem by specifying correct formal syntax and then 
adding a table for additional restrictions on the correct syntax.  This 
uses the existing syntax ABNF supports for unordered lists: *(a / b / c). 
Furthermore, when I wrote my message lint utility:
	<http://www3.innosoft.com/~cnewman/msglint.html>
which strictly validates 822 content, the structure that made sense for the 
code was to have formal syntax for generic headers in the code and a table 
of headers and the various restrictions on those headers (including 
header-specific formal syntax) in a separate (extensible) table.  So from a 
programmer viewpoint 822bis is heading in exactly the right direction -- 
combine the *(a / b / c) unordered-list syntax with a table of additional 
restrictions.  I'd actually be inclined to consider moving more into the 
table (including which headers are mandatory and header-specific syntax).

I'm also unclear what the proposed addition to ABNF is.  Options include:

(1) Syntax for unordered lists.  But since we already have *(a / b / c), we 
don't need to add anything.

(2) Syntax for a list of attribute-value pairs where each attribute can 
occur only once.  This isn't useful in the message format case since the 
rules are far more complex.  Furthermore, I don't believe it's possible for 
a formal syntax to express this clearly since it implies the formal syntax 
has explicit knowledge of the attribute-value concept, and since 
attribute-value lists can be represented by many different syntaxes, I 
suspect this would have problems similar to the # construct, only much 
worse.

(3) Syntax to generally support complex restrictions on attributes within 
an attribute-value construct.  Similar to (2), but will be both more useful 
and vastly more complex and unintuitive.

		- Chris

---

From: Robert Elz <[email-masked]>
Date: Mon, 10 Jul 2000 15:07:14 +1000

Date:        Mon, 10 Jul 2000 13:19:09 +1000
    From:        Robert Elz <[email-masked]>
    Message-ID:  <[email-masked]>

  | Ah, I see, I was confused by ...
  | 
  |          group          =  "(" *c-wsp alternation *c-wsp ")"
  | 
  | in your original message.  "alternation" is  a / b

And I cut/pasted the wrong line, that was the "used to be", I should
have included the "would become" line, which was ...

but the point doesn't change.

kre

---

From: Dave Crocker <[email-masked]>
Date: Tue, 11 Jul 2000 18:26:27 +0900

PRIMARY COMMENT:

At 02:18 PM 7/10/00 -0700, Chris Newman wrote:
>(1) Syntax for unordered lists.  But since we already have *(a / b / c), 
>we don't need to add anything.

While I would like to explore my original concerns and proposal further, I 
frankly will consider this thread adequately productive for having surfaced 
the above sentence sufficiently to give me guidance for some additional 
text in the ABNF specification, so IT can give guidance to users of ABNF.

FURTHER DISCUSSION

The thin edge of the wedge I will use to keep the door open is RFC 1894, as 
an example of the above insight not making it into a specification  -- and 
please note the use of the word "example", which means that there is no 
criticism of 1894 itself, just interest in it as representative of ABNF 
writing style.  Also there is the question of *( a / b / c )'s adequacy.

RFC1894 was written in 1996.  Perhaps the insight is more recent?

Will adding advisory "usage" text to the ABNF specification be sufficient 
to help future writers use the *(a / b / c) construct?

Is the *(a/b/c) construct sufficient for 1894?  My effort at re-formulation 
produces:

     per-message-fields = *(
           ( original-envelope-id-field CRLF )
           / ( reporting-mta-field CRLF )
           / ( dsn-gateway-field CRLF )
           / (received-from-mta-field CRLF )
           / ( arrival-date-field CRLF )
           / ( extension-field CRLF ) )

The main point is that the distinction between optional and required is 
entirely removed from the syntax, as well as multiple occurrences, for 
extension-field.

DRUMS EXEMPLAR

With respect to draft-ietf-drums-msg-fmt-07.txt , there seems to be a problem:

>message         =       (fields / obs-fields)   [CRLF body]
>
>fields          =       *(trace
>                           *(resent-date /
>                            resent-from /
>                            resent-sender /
>                            resent-to /
>                            resent-cc /
>                            resent-bcc /
>                            resent-id))
>                         *(orig-date /
>                         from /
>                         sender /
>                         reply-to /
>                         to /
>                         cc /
>                         bcc /
>                         message-id /
>                         in-reply-to /
>                         references /
>                         subject /
>                         comments /
>                         keywords /
>                         optional-field)

does NOT fully show the non-ordering that is cited in:

>....  So from a programmer viewpoint 822bis is heading in exactly the 
>right direction -- combine the *(a / b / c) unordered-list syntax with a 
>table of additional restrictions.

or did I miss something?

It looks as if, for example, the syntax requires trace information to 
precede the From field.

PRECISE NUMBER OF OCCURRENCES

>rules are far more complex.

0.  "only once"... or any specified number of times.

1.  In fact, the *( a/b/c ) construct guarantees loss of all syntactic 
control over the number of times.

         *** Specification of number of permitted/required occurrences
         *** must be placed into the prose.

2.  Can we get some elaboration on the "far more complex" assessment?  The 
formal rules in RFC822 permit zero or one header in most cases, requiring 
only a few.  With respect to generic multiple occurrences of the same 
header RFC822 states

>      4.1.  SYNTAX
>...
>             This specification permits multiple  occurrences  of  most
>             fields.   Except  as  noted,  their  interpretation is not
>             specified here, and their use is discouraged.

However most implementations treat them as a concatenation of a single header.

My own feeling is that the rules pertaining to number of occurrences of 
list members tend to be pretty simple, along the lines of:

         1.  Exactly once
         2.  At most once
         3.  Zero or more
         4.  1 or more

and that other rules are very rare indeed.

>Furthermore, I don't believe it's possible for a formal syntax to express 
>this clearly since it implies the formal syntax has explicit knowledge of 
>the attribute-value concept, and since attribute-value lists can be 
>represented by many different syntaxes, I suspect this would have problems 
>similar to the # construct, only much worse.

Not clear to me that explicit knowledge of the attribute-value concept is 
at all required.  I believe the focus on "number of occurrences" fits the 
issue adequately.  The fact that the occurrences are of things that are 
attribute/value does not seem relevant.

>an attribute-value construct.  Similar to (2), but will be both more 
>useful and vastly more complex and unintuitive.

I agree entirely.

At 09:29 AM 7/10/00 +0100, [email-masked] wrote:
>equivalent? Everything I know about BNF would imply they are. My sense of
>what Dave is saying is that they are not, and that "cabc" is legal under

Classic BNF is strictly ordered, so, yes, the two forms yield the same 
result.  And, yes, I am suggesting something that does not.  And, yes, 
that's a problem if only for clarity of understanding.

However, like defining the difference between URLs that are part of a web 
page set, versus URLs that are just external references, there needs to be 
a boundary on the un-ordering.

I'd be perfectly happy exploring a variation on *(a/b/c) for unordering, if 
it results in something more clear.  At base, focus on concatenation seemed 
better than alternation because unordering is messing with the 
combinatorials of items, rather than with what items are 'selected'.

d/

=-=-=-=-=

---

From: Keith Moore <[email-masked]>
Date: Tue, 11 Jul 2000 15:55:13 -0400

Dave,

what makes you think that RFC 1894 intended to allow the per-message or
per-recipient fields to be in any order?

granted, the interpretation of the fields is obvious if they are presented
in a different order than that specified in the document, but I don't recall 
putting anything in RFC 1894 which allows senders to relax the ordering...
and I can't find it now.  

Keith

---

From: [email-masked] (Kai Henningsen)
Date: 12 Jul 2000 19:39:00 +0200

> >table of additional restrictions.

Yes. You missed the enclosing *( ), or at least the implications thereof.

> It looks as if, for example, the syntax requires trace information to

No.

MfG Kai

---

From: [email-masked] (Kai Henningsen)
Date: 12 Jul 2000 19:33:00 +0200

> you're trying to make a grammar do a job that it cannot do well.

If you want to see what you have to do to the grammar concept to get stuff  
like that to work, have a look at the Algol68 report.

I liked it, but it's not for the average reader, and it's hard to convert  
into a parser. And it is *a lot* more involved than the current proposal.

OTOH, it can describe ordering constraints, uniqueness constraints,  
necessity of definition before reference, and so on.

There's probably a reason why, to my knowledge, no language since has  
taken this approach.

> names) it is impossible to write a replacement grammar that enforces

That's not quite true, because the above did exactly that. It is however  
true if you mention the usual assumption that this is an 1:n replacement  
grammar, not an n:m replacement grammar. The latter is a much larger  
class. (And the above example goes against another implicit assumption,  
too - that the number of grammar rules is finite. In essence, A68 contains  
a grammar for constructing a grammar.)

> doesn't make sense.  you can't describe 822 with asn.1

You might try that with X.400, of course. <shudder>

MfG Kai