Path: utzoo!mnetor!uunet!mcvax!enea!ttds!draken!kth!sics!alf
From: alf@sics.se (Thomas Sj|land)
Newsgroups: comp.lang.prolog
Subject: Re: Difference Structures for Different Folks
Message-ID: <1831@sics.se>
Date: 18 Apr 88 15:56:45 GMT
References: <11500002@hpldola.HP.COM>
Reply-To: alf@sics.se (Thomas Sj|land)
Organization: Swedish Institute of Computer Science, Kista
Lines: 56
Keywords: PROLOG, coding, semantics

In <11500002@hpldola.HP.COM> patch@hpldola.HP.COM writes:

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

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

> This is not a logical interpretation !

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


I don't really know how I should view the epithet "theoretician"..., but I 
guess I have to answer since I stuck my neck out already. 

Anyway, my earlier comment about D-lists not being members of the Herbrand 
Domain was introduced to show that Logic Programming in PROLOG often 
involves CODING of objects and algoritms on these objects in terms of Horn 
Clauses and objects of the Herbrand domain. The problems involved in having 
another INTENSION for the identity of objects than the underlying theory for 
PROLOG gives, will of course show up when we try to use '='/2 or unification 
to determine equality of our intended objects, be they ground or not. 

( Consider the arithmetic truth "2+2+2=2*3", which can be CODED using some of
the Peano axioms, or the equality of the D-lists [1,2,3]-[3] and [1,2]-[]. )

So, the "_logical_ interpretation" for your program is fairly trivial if we
intend what we normally do when we use the phrase
"_logical_ interpretation". The predicate "path_ground" corresponds to a
relation over objects in the Herbrand domain with the main functor 'path/2'.

Whether this interpretation makes sense when we view your INTENSION of the
use of your program or if further more or less intricate explanations are 
needed is your responsibility as a "logic programmer". 

I guess that the search for "_logical_ interpretations" has to do with the
urge to achieve a program with verifiable , but not necessarily OPERATIONAL
semantics.

A nice feature of logic programming is that you CAN write programs which are
given a non-operational understanding, but it is not obvious that the
_logical_ interpretation of an optimal program has anything to do with the
intended semantics. 

Note that you write:

> A path is represented by the difference-structure:
	    ^^^^^^^^^^^
This shows that you are involved with the coding I talk about. Of course,
you cannot expect the Prolog system to know anything about your intended
interpretation of the objects you use to code your "paths" and "vertices".