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

From: Graham Klyne <[email-masked]>
Date: Thu, 16 Sep 1999 22:33:15 +0100

Ted,

I don't know if my response is gpoing to help any, but at least I'll try
and keep it brief this time.

[Well, I tried, but...]

At 10:24 16/09/99 -0700, [email-masked] wrote:
>... I also apologize for introducing some confusion
>here, because I believe the term "recognize" was not clear enough to
>get across exactly where in the predicate comparison process I saw the
>problem.

Hmmm... I did not perceive a problem with your use of "recognize", but
rather with your use of "possible".

>gk writes, quoting me:
>> So, the non-recognition of a feature tag is taken to mean that its value is
>> not important.  This leaves us with no way to express "mandatory features",
>> a problem that has been documented elsewhere, and one that I was assuming
>> we were prepared to defer for further study.
>> 
>> >With composite feature sets, the assumption that unrecognized feature
>> >tags do constrain the set creates a problem, because the conneg
>> >predicate alone can no longer tell you what feature tags are present.
>
>Here is the nut of the problem.  With a feature tag present in only
>one of the two predicates being compared, the assumption is that the
>value of the tag does not constrain the match.  With a feature tag
>present in both of the predicates, the assumption is that the values
>of the tags must be considered when determining a match.  From a
>participant point of view, that means that unknown tags do not
>constrain matching, but unknown values do.  ("know", it strikes me, is
>a synonmym for recognize, so I don't think I've gotten far past my
>terminology problem.  More exact terms are welcome).

I am confortable with "know" or "recognize" here.  I think that maybe we
need to be clearer about what we actually mean by "match".

Intuitively, a sender or resource matches a receiver if the receiver can
process what it receives from the resource/sender.

The predicate algebra expresses this idea by testing sender/resource and
receiver feature expressions to see if they are consistent with each other.
 That is, is the expression:
   (& (sender-features) (receiver-features) )
or
   (& (resource-features) (receiver-features) )
a contradiction?  In predicate algebra, a logical contradiction occurs when
a predicate is identically FALSE for all possible values of its variables
(i.e. for a CONNEG axpression, is FALSE for all possible combinations of
feature tag values).

Now, this concept is perfectly well defined, and as I tried to explain in
my previous message behaves consistently under the concept of unknown
composite feature expressions.

But, and I think this is the heart of debate here, does this model
reasonably reflect the intuitive idea of matching stated above.   I think
it does for a useful range of sender/receiver compatibility tests.

[But see PS comments below]

>Composites aren't composite values or composite tags, however, they
>are composite predicates.  So if composites don't match, we don't know
>whether we have a bunch of unknown tags (which *would not* constrain
>matching) or a bunch of known tags with unknown values (which *would*
>constrain matching).

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.

>> >You must have a dereferencing method for either the URI or the hash to
>> >determine the feature tags and values.  Fundamentally, I believe that
>> >that has made me uneasy because it seems to shift us to the opposite
>> >assumption, that we must presume that something is constrained until
>> >it has been shown to be possible.
>> 
>> I do not recognize this shift.  Rather, I think the original presumption of
>> possible until known to be constrained is applied here at a much coarser
>> level.  Ultimately, in the absence of full information, the system as
>> defined tends to err on the side of being permissive.
>
>I think it is really the note in 3.3.2 that caused me to see a shift
>here.  It describes a scenario in which the recipient of a composite
>replies that it does not understand h.1234567890 and gets the
>composite broken back out for it.  I think I read into that statement
>that the application would treat h.1234567890 as something it could
>not handle if it did not get the original predicate.

OK, I think I understand your perception here...

>  This may well
>have been derived from my own presumptions of use, rather than
>something you intended in the draft.  My presumption made me believe,
>however, that the application would treat the composite as if it were
>a bunch of known tags with unknown values.

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).

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'm trying to come up with some other way of describing the problem,
>but all I've come up with is:
[...]
>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.

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 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
--

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.

ZZZzzz...

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

---

From: [email-masked]
Date: Thu, 16 Sep 1999 17:01:18 -0700 (PDT)

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>
> 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.

> 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.
 
> 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.

> 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.

> 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.  
 
> issue (if not the solution) is converging?

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)

> 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