Re: Hashing, and Ted's concerns about wastefulness

Ted,

(long-ish message -- sorry)

At 12:35 01/02/99 -0800, Ted Hardie wrote (quoting me, quoting Larry,
quoting Ted...)
[...]
>> #   (h.<URI>="<hash>")
>> 
>> within a capability expression (this conforms to current syntax rules),
>> where <hash> is calculated over the body of a notional auxiliary predicate:
>> 
>> #   (h.<URI>) :- 
>> #       (| (& (pix-x=640) ...)
>
>I think this is workable, but we will need to be very careful in presenting
>this to ensure that there is no confusion between g.<URI> h.<URI>;

After debating with myself whether this really matters, I agree.

>... we also
>need to specify exactly what you get if you retrieve h.<URI>.

I think that what you get is a copy of the hashed feature expression.

>> >> I suppose we can create a feature that is, in fact, a request for fh
>> >> to be disaggregated.  
>> >
>> >I think that's mixing descriptive information and protocol in
>> >an unfortunate way. I think disaggregation is likely to be
>> >protocol dependent, even though the semantics of "fh" is
>> >protocol independent.
>> 
>> Again, I agree.
>> 
>> If two expressions contain the same sub-expression:
>> 
>> #    (h.<hash>
>> or
>> #    (h.<URI>="<hash>")
>> 
>> then they are known to match at that point without disaggregation.  OTOH,
>> if they have different hash values then disaggregation is needed to
>> determine whether or not they truly match.  No additional "feature" is
>> required to trigger the disaggregation mechanism;  simply some kind of
>> "lazy evaluation" component in the feature set matching process.

>I think that we have a problem here related to the "directionality" issue
>Larry brought up with my previous message.

I'm not so sure... one reason is that I don't really agree with your later
statement:

>[...] I mean simply
>that we have to have some idea of what the disaggregation mechanisms are
>to get a solution that will work across protocols.

In this context, I regard "disagregation" as the process whereby the
feature set reference is replaced by the feature set expression;  i.e.
dereferencing.

I think the specific disaggregation mechanism is properly specified by the
application/protocol specification that uses the feature expressions.  The
feature set expressions have a defined meaning:  in the case of
(h.<URI>="<hash">), the meaning is identical to the equivalent feature
expression that hashes to <hash>.  How that substitution is performed does
not affect the meaning.

As for the directionality issue:  the feature set matching process is not
directional.  In order to establish communication between parties A and B,
then one of the parties must get a feature set expression from the other
and compare with what it has to hand.  The outcome of feature set matching
is not affected by which party does the matching (and any associated
fetching that may be required).  Thus, an application can choose how and
where feature matching is finalized:

For internet fax, current proposals have the recipient capabilities
presented to the sender who then selects an appropriate document format for
transmission.  HTTP has models that can work either way (client Accept-*
headers, server Vary headers, if I recall correctly).

>Think about it this way: This system works based on set intersection.
>If either party presents information about their set using a hash, the
>other party must be able to either recognize the predicates implied or
>disaggregate the hash in order to determine whether the sets
>intersect.  There are a couple of ways to do this, and they loosely
>fit different scenarios.

But, I submit, they both/all work with the feature set matching model.

>...  Send along the hash with the predicates, and
>you can use the hash in place of repeating elements without worrying
>that the other party won't understand it.

This is easy, and can just about be done with the current spec:  simply
carry an auxiliary predicate:

    ( <feature expression using sub-expression (h.<URI>=<hash>) )
    WHERE
        (h.<URI>) :- ( <expression> )
    END

>...  Refer to the hash with a
>URI that contains the disaggregated form, and the parties will
>sometimes be able to retrieve the disaggregated forms.

That would be the above case, omitting the WHERE clause.

>...  Indicate a
>failure to recognize and rely on in-bound communication to carry the
>disaggregated forms from the other party to the party expressing the
>failure.

I see cases 2 and 3 being essentially the same, in that they would rely
upon some application-specific "mechanism" to dereference unknown feature
expression tags.

>I strongly believe that we need to do 1 if we do anything at all.  I
>believe that 2 has value, but that the value is limited unless we
>specify pretty strictly how the disaggregated predicates are
>represented at the URI;

Sure.  I would say the -feature-syntax- does most of the work there.  Some
small amount of profiling would be needed, I think.

>... I am also worried that there are problems both
>with specifying a particular URL scheme for this and with not
>specifying one.  For 3, Larry and I seem to disagree on the utility of
>specifying a method for naming the failure as an "understanding the
>hash" issue, and I think we need to hear other voices on that part of
>the problem.

I don't think the method here is a one size fits all type of solution.  Any
given application would need to indicate an appropriate method.  For
example:  in WWW, retreive the resource indicated by the URI;   in e-mail
use the tag in a directory search or RESCAP (aka MAILCAP) resolution.

>None of this is to say that lazy evaluation isn't a good thing; I mean simply
>that we have to have some idea of what the disaggregation mechanisms are
>to get a solution that will work across protocols.

I think my comment about "lazy evaluation" may have been slightly at
cross-purposes.  I was saying that I did not think a specific feature to
trigger dereferencing was required.  I think you are discussing the
mechanism used to perform dereferencing.

>> Further, using my second proposal, two different tags:
>> 
>> #    (h.<URI1>="<hash>")
>> #    (h.<URI2>="<hash>")
>> 
>> can be assumed to match if the hash values are the same (e.g. for rebadged
>> versions of the same mobile phone).
>> 
>> An attractive property of this approach is that it can be used with the
>> current specification (with registration of the 'h.' facet), in many cases
>> will yield the correct result, and will never yield a false feature set
>> match.  Agents with additional knowledge can reconcile the apparently
>> different feature tags (this is also behaviour consistent with the current
>> specification.)
>> 
>
>Can someone (Bill, Graham, Larry) write up one of these proposals as
>an ID, so we can have something to discuss concretely?

I'd be happy to have a go at the (h.<URI2>="<hash>") proposal, if that
doesn't pre-empt anything that Bill is planning.  I would be more
comfortable if we had some consensus on scenarios and goals so that it can
be seen to address the perceived problem.

#g

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