centaur selections and typol paths

[Thierry.Despeyroux@sophia.inria.fr (Thierry Despeyroux)]

=> From: Thomas Kuehne <kuehne@isa.informatik.th-darmstadt.de>
=> 
=> Up to now I did want to highlight just on subject in the ctedit.
=> 
=> The final step now is to highlight multiple subjects.
=> In my TYPOL program there are rules yielding just one subject and
=> others, that will have to combine the subjects of the subgoals.
=> 
=> The two ways to do this I see are:
=> 
=>   o Instead of returning a subject from TYPOL, one returns a list of
=>     subjects.
=>     These will be 'merged' in the Lisp world to form a selection.
=>     
=>     Drawback: merging the lists of subjects in TYPOL is expensive.
=> 
=> 
=>   o One builds the multi-set of subjects in TYPOL.
=>     Your conversion function should also handle this, does it?
=> 
=> Do you have another, better idea?
=> How can i 'merge' to TYPOL subjects to a multi-subject containing both?

The only possible solution (now) is the first one.

The problem is that Typol paths and selections are different things even if
their goals are close.

A selection is a lisp (not VTP) structure that is a sequence of moves
from the top of a VTP object (a Centaur tree) to a subtree.
If we want to designate B in f(A, g(B, C)), we may write top.2.1.
If we want to designate a subtree inside B, we have to append some moves
at the end of the list (relatively not efficient if you dont have an
appropriate implementation). It is possible to designate multiple points
in a subtree using "crossroad". For example top.2.(1 2) designates
B and C. A selection is in fact a structure isomorphic to a scheme in
which the names of the nodes are omitted. You cannot designate with a
selection two occurences that are not in the same tree (in two different
ctedit for exemple). A selection must always designate an existing object.

Typol paths are anterior to selections. The idea was that paths are functions
that, when applied to a tree, give you a tree. This function is represented
as a VTP tree in Typol. And the funtion #:PSP:interp_with_root does
exactly that: it applies a path to a root, giving a tree (In fact, in most
places in the code in the interface between Lisp and Prolog, Typol paths are
coerced into lisp expressions that are directly evaluated,
with the same behaviour but more efficiently as the (big) VTP tree is
never constructed). Taking the same example, the path that designates
B is \top.s1(s2(top)). In the prolog implementation it is in fact only
s1(s2(top)). Designating a subtree of B is easy and is done by unification.
If k is a path to h(X), s1(k) is a path to X. A path may designate a tree
that does not exist. For example, in the non-structural rule
|- f(Y,X)
---------
|- g(X,Y); that construct a new term f(Y,X), we denotate f(Y,X) by
the path u[s2(k),s1(k)] where k is a path to g(X,Y). In this new term, 
Y may be designated by s1(u[s2(k),s1(k)]) which is equivalent to
s2(k) (that is what the normalize predicate does). So path construction
is done only by unification on top of a structure (not at the end of a list)
and must be sometime reduced to something smaller and equivalent. It is
possible to designate occurences coming from different ctedit. This is
is what happens with "export |- f(A, B) as foo(A,B) =..." for example,
if A and B are not in the same centaur editor. In this case a path
is a function taking two arguments. It is also possible to
say that one object comes from different places. For example if
we takes f(X,X) with path k, both s1(k) and s2(k) are valid paths to
designate X, and we can write x[s1(k),s2(k)] (But this is not implemented!).
This may be useful if want to show where and identifier come from, both in
the source, and the environment for example.
It is not possible to designate two different objects in a unique Typol path.

Having a Typol normalized path it should be possible to get a selection by
reversing it: s1(s2(top)) -> top.2.1. The only problem is that selections
are not VTP trees and cannot be manipulated now in Typol.

Do you think it should be useful to have a VTP definition for selections
and procedures to coerce selections into VTP (and the reverse) to be able
to manipulate selections in a Typol program ?

Thierry

Send contributions and compliments to centaur@sophia.inria.fr. Registration
and administrative matters should be sent to centaur-request@sophia.inria.fr.
+---------------------------------------------------------------------------+
|     Thierry Despeyroux      | email: Thierry.Despeyroux@sophia.inria.fr   |
| I.N.R.I.A. Sophia-Antipolis | phone: +33 93 65 77 07 fax: +33 93 65 77 66 |
+---------------------------------------------------------------------------+