Re: draft-ietf-conneg-feature-hash-03.txt

Graham,
	I think part of the problem here is that my limited brain
tends to think in terms of the simple Venn diagram set theory of my
youth, rather than in terms of the logical structures of predicate
algebra.  This, I suspect, is why such a simple term as "match" is
causing a problem.

In those simplified terms, what I am saying is this:

A sender presents a set of features.

A recipient has a set of features.

To test for a match, the recipient first eliminates any feature
tag/value pairs presented by the sender for which it has no equivalent
feature tags.

It then constructs a set of the sender's features and compares it
against the set of its own features.  If the intersection of those two
sets is not empty, life is good.  If the intersection of those two is
empty, life is at least clear.

If a composite is mentioned by the sender and known by the recipient,
it can be treated just as if it were a standard feature.

The question on the table is what to do when the composite is
mentioned by the sender and unknown to the recipient.  If it can be
dereferenced, we know we can get to "life is clear".  What do we do if
it cannot be dereferenced? 

A few further comments inline.

<big snip>
> 
> This is all true.  My thesis here is that this lack of information reduces
> our ability to detect a contradiction, but that the results we obtain using
> the algebra are otherwise correct.  That is, a valid expression can be
> deduced that does not indicate a contradiction, but provision of additional
> information can make a contradiction apparent in that expression.

I agree.  The algebra produces a valid expression if we treat the composite
as if it were a single feature tag/value.  That expression may be later
shown to be wrong after dereferencing, but it was never syntactically
invalid.

> Actually, I did not really have an intent when I wrote that.  My present
> arguments are being constructed in response to your comments, rather than
> coming from some original grand design.
> 
> But, I would say (now) that it is not a case of "the application treating
> h.1234567890 as something it could not handle" so much as treating
> h.1234567890 as a piece of incomplete information, and using a
> dereferencing mechanism to obtain more complete information (hence a more
> reliable indication of sender/receiver compatibility).

This expresses well what the example actually says, but I believed that
the implication was that you need to dereference in order to construct
a *meaningful* (rather than *valid*) expression.

> Or, to put it another way, dereferencing a composite feature reference can
> be compared to learning the meaning of a previously unrecognized feature tag.

I don't agree.  It may be comparable to learning the meaning of a
previously unrecognized tag, or it may be comparable to learning the
value assigned to a previously known tag; as we have discussed, these
are different.

> >Should we retain external pointers (hash, URI), and make brutally
> >clear how to handle the predicate matching in the presence of
> >composites?  If so, is the handling the same for both types of
> >pointers?  
> >
> >Or should we shift the field to in-place compression, or some other
> >composite method for which the problem does not arise?
> 
> Aha!  My immediate reaction is that in-place compression is not going to
> yield benefits worth the effort.

Quite possible.  Part of the reason that I started down this whole
rat-hole was that I was totting up the benfits of hashing vs. URIs and
realized not only that URIs might well be very significantly longer
than hashes, but that you could not really tell in advance how big
they were going to be, meaning you need a fairly complex memory
storage and lookup mechanism (at least compared to a hash).

I wrote a perl script to generate fake feature expressions out of
dictionary entries, just so I could do a few quick tests of in-line
compression.  For feature expressions under five lines, it's only on
the magnitude of a 2 for 1 gain over including the original feature
expression (269 chars orig; 177 compressed).  For feature sets in the
fifty line range it was closer to 4 to 1 (2720 vs 687).  For feature
expressions in the five-hundred line range, it gets to 6 to 1, but the
set comparison would have long since killed you.

In all of the cases above, the compressed text is much longer than a
hash, and longer than a typical product URI.

> I think the original assumption underlying this work was that a processor
> would be able to dereference a composite feature reference when this was
> needed (without knowing or specifying how that might be achieved).  And
> under those circumstances, I think how to handle predicate matching is
> indeed quite clear.
>
> What our debate has added is:  what can we do if a composite cannot be
> dereferenced?  I think you are saying "don't know" => "can't match", which
> is at odds with the way feature tags are handled.
> 
> Faced with the same question, I am saying "don't know" => "leave compsite
> reference untouched in the resulting feature expression".  What this
> probably needs is a statement of some processing rules for handling
> unexpanded predicates in feature expressions.  (I did start down this path
> in an earlier draft, but was persuaded not to go there.)

I would rather not have this be decided on an application specific basis,
because the feature expressions may well cross application and protocol
boundaries.  

> 
> I did mean to keep this short, but somehow there always seems to be so much
> to say.  Do you sense yet, as I do, that at least our understanding of the
> issue (if not the solution) is converging?
> 
> #g

Yes, I do.  I'm also sensing that I need to by you a beer when I see you,
luckily soon.  It's too bad the Study group 8 meeting isn't going to let
you arrive a day earlier, or we could thrash this out there.

(Still a litle something below)

> 
> 
> PS:  there is a tangential development arising from my comments above about
> the nature of the matching process, and what it means.  I have argued that
> detecting a match is the same as testing for the absense of a
> contradiction.  This is not the only possible test for a "match".
> 
> I have been thinking about this, on-and-off over a period of several
> months, with respect to mandatory options (the "font problem").  Using
> exactly the same algebra, syntax and processing rules I can conceive a
> different matching test that fails if required features are not present:
> 
> The current matching test is effectively:
>    (& E1 E2 ) NOTEQUIV (FALSE)
> 
> But another test might be:
>    (& E1 E2 ) EQUIV E1
> 
> This second matching test effectively says that feature set E2 must contain
> all of the features in E1.
> 
> So matching is effectively a metalogical process, and different matching
> (meta-) expressions can have different properties -- that is, they can
> describe different sender/receiver compatibility requirements.

I do suspect that solving the mandatory options problem would allow us
to make the handling of composites application-specific, because we could
include the presumed behavior in the feature expression.  We would, however,
have to make including that piece of syntax in a composite a severe and
absolute no-no.

			regards,
				Ted