Path: utzoo!utgpu!water!watmath!clyde!att-cb!att-ih!pacbell!ames!ucsd!sdcsvax!ucsdhub!hp-sdd!hplabs!hpcea!hpfcdc!hpldola!patch
From: patch@hpldola.HP.COM (Pat Chkoreff)
Newsgroups: comp.lang.prolog
Subject: Difference Structures for Different Folks
Message-ID: <11500002@hpldola.HP.COM>
Date: 2 Apr 88 04:37:32 GMT
Organization: HP Elec. Design Div. -ColoSpgs
Lines: 137

I have recently been dealing with directed graphs having labelled edges,
and have devised a difference-structure representation for paths through
these graphs.  They work great, but the ghost of Herbrand is haunting me
now.  But I'll get to that later.

A path is represented by the difference-structure:

	path(Length,P,Px)

where P and Px are the `inner' and `outer' parts of the difference
structure representing the path.  Because the `outer part' is not
considered as part of the intended `contents' of the path, I prefer to
denote it with an arid name like 'Px' instead of something like 'Back'
or 'Tail', which (for me) have confusing connotations.  The Length is a
natural number representing the number of edges traversed along the
path.

The inner part of the path is a term:

	vertex(Label,Exit)

where Label is a vertex label and Exit represents the remainder of the
path exiting this vertex.  The Exit is a term:

	edge(Label,Tail)

where Label is an edge label (the one along which the exit is made) and
Tail represents the destination node and the subsequent path from there.
The Tail, appropriately enough, is another vertex/2 term.

The outer part of the path (Px) is a (possibly variable) edge/2 term,
and is a tail of the inner part (P).  Everything from P down to but not
including Px is the intended `contents' of the path.  So, when we reach
some vertex/2 node whose Exit is Px, this means that the path ends at
that vertex.

(Whew.)  Anyway, the formulation is:

|	%-------------------------------------------------------------------
|	% path_null(Vertex, Path)
|	%
|	%     Path is a null (empty) path consisting of only the given
|	%     Vertex.
|	%
|	% path_head(Vertex, Edge, Suffix, Path)
|	%
|	%     Path is a path from Vertex along Edge followed by the
|	%     Suffix.
|	%
|	% path_tail(Prefix, Edge, Vertex, Path)
|	%
|	%     Path is the Prefix followed by an arc along Edge leading to
|	%     Vertex.
|	%
|	% Pictorial mnemonic:
|	%
|	%     path_null:  (Vertex)
|	%     path_head:  (Vertex)--Edge-->|Suffix|
|	%     path_tail:  |Prefix|--Edge-->(Vertex)
|	%
|	% ** Does anyone find this parameter ordering confusing or overly
|	%    cutesy?
|	%-------------------------------------------------------------------
|
|	path_null(V, path(0,vertex(V,Px),Px)).
|
|	path_head(V, E, path(N,P,Px), path(s(N),vertex(V,edge(E,P)),Px)).
|
|	path_tail(path(N,P,edge(E,vertex(V,Px))), E, V, path(s(N),P,Px)).

You may notice the similarity with the `queue' formulation posted by Dr.
O'Keefe back in March.  (That was a helpful `meme'.  Thanks.)  That
formulation cued me in on the use of the Length argument (a natural
number) in a difference structure.  Without this argument, there are
useful predicates on the difference structure which could not be written
logically (viz. without using var/1).

** (DIGRESS)

By the way, if you remove the Length from the path representation, you
can get interesting things like `negative' paths!  Hint:

	| ?- path_null(v0,P0),
	     path_tail(P1,e1,v1,P0),    % whoa!
	     path_head(v2,e2,P1,P2),
	     path_tail(P2,X,Y,_).

	...
	X = e1
	Y = v1
	yes

Same thing goes for queues (see _The_Art_of_Prolog_).

** (RETURN)

This reminded me of the painful fact, put so bluntly by Thomas Sj|land,
that:

> More bluntly put: A D-list is not an object in the Herbrand domain.

"YOW!," I thought, "my `paths' are second-class citizens!  In fact,
they're not citizens at all.  How can they make their debut as full-
fledged members of Herbrand society?"  That's simple.  Make them ground
(grind 'em?).  To terminate the recursion along the alternating vertex
and edge terms, introduce []/0 as a new 'Exit' term (in addition to
edge/2):

|	%-------------------------------------------------------------------
|	% path_ground(Path)
|	%-------------------------------------------------------------------
|
|	path_ground(path(0,vertex(V,[]),[])).
|	path_ground(path(s(N),vertex(V,edge(E,Tail)),Px)) :-
|		path_ground(path(N,Tail,Px)).

But wait: there's a problem.  You'll notice that I didn't give any
interpretation for this relation.  That's because I *couldn't*.  The
best I could come up with was:

	"Path is a ground term representing a path if and only if ...
		... nothing has EVER been ADDED to its tail."

This is not a logical interpretation!  What's that stuff about TIME and
MODIFICATION?  So it seems that (some of) my `paths' make their debut
into the Herbrand universe, but on dubious credentials.  Is there some
theoretician out there (Sj|land?) who can devise a _logical_
interpretation for path_ground/1, or else show me why it's impossible?

+-----------------------------------------------------------------------
| DISCLAIMER:  The author assumes no responsibility for any loss of life
| or limb which may occur as the result of errors in the predicates
| path_null/2, path_head/4, or path_tail/4 as presented above during
| their use in any setting, commercial or private.  The predicate
| path_ground/1 has no specification, and thus cannot be said to have
| errors :-)
+-----------------------------------------------------------------------