From lamping@parc.xerox.com Tue Aug  8 13:25:32 1995
Sender: John Lamping <lamping@parc.xerox.com>
From: John Lamping <lamping@parc.xerox.com>
To: lieber@ccs.neu.edu
Cc: boaz@ccs.neu.edu, crista@ccs.neu.edu, huersch@ccs.neu.edu,
        ivbaev@ccs.neu.edu, lamping@parc.xerox.com, Gregor@parc.xerox.com,
        palsberg@theory.lcs.mit.edu, salil@ccs.neu.edu, seiter@ccs.neu.edu,
        yangl@ccs.neu.edu
Subject: Re: communication with Xerox
Date: Tue, 8 Aug 1995 10:23:54 PDT

Karl writes

  When is a set of operations complete at the adaptive level?

A case which Crista has convinced me is useful is all non-recursive paths
from A to B.  That is, all paths that go from A to B with no intermediary
A'a and B's.  

 ...

Second, I strongly feel that an ability to talk about links and properties
of links could increase the adaptivity of programs.

Suppose I have Car class, and I want to traverse to the Tire class to get
to its tires.  Seems straightforward, but now suppose I add some historical
links that can connect me with all the tires that were ever on the car.  Or
suppose that I have a link from Tire to Manufacturer, from which I can then
get to huge numbers of Tire objects.  Or suppose I have a link from Car to
Driver, who could have links to Tire through innumerable paths: CreditCard,
Employeer, Hobby, Owns, ...

But, suppose, instead, that links come in their own hierarchy, and one of
the components of the hierarchy is PartOf.  Then I could say "Traverse from
Car to Tire only through PartOf", and be confident that my program would
correctly adapt to all of the above situations.

In the calculus, if you introduced the link hierarchy, union and
intersection on the link hierarchy, and a * operator to give all paths that
involve only specified links, then you could write

[Car,Tire] \cap PartOf*


From lamping@parc.xerox.com Tue Aug  8 14:00:31 1995
From: John Lamping <lamping@parc.xerox.com>
To: lieber@ccs.neu.edu
Cc: boaz@ccs.neu.edu, crista@ccs.neu.edu, huersch@ccs.neu.edu,
        ivbaev@ccs.neu.edu, lamping@parc.xerox.com, Gregor@parc.xerox.com,
        palsberg@theory.lcs.mit.edu, salil@ccs.neu.edu, seiter@ccs.neu.edu,
        yangl@ccs.neu.edu
Date: Tue, 8 Aug 1995 10:59:13 PDT

Thinking about my previous post, it seems like regular expressions might be
a good level of descriptive power for traversals.  They guarantee both a
fair level of expressibility and the possibility of simple implementation.

It's not exactly regular expressions, because traversals involve both
classes and links, but that doesn't seem to be an essential difference.
It looks like the underlying thing is a monoid.

The basic language would look something like:

Atomic expressions:

   A    The empty traversal at class A
   lnk  a link of type lnk ("any" is a special case of any link type)


For combining expressions, the usual regular expression crowd:

   .     concatenation
   \cap  intersection
   \cup  union
   *     repetition
   not   negation


Note that as with all empty strings, A.A = A

Paths from A to B become

  A.(any*).B

Non-recursive paths from A to B become

  A.(any*).B \cap not(A.any.(any*).(A \cup B).(any*).any.B)