patch@hpldola.HP.COM (Pat Chkoreff) (04/02/88)
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 :-) +-----------------------------------------------------------------------
alf@sics.se (Thomas Sj|land) (04/18/88)
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".
patch@hpldola.HP.COM (Pat Chkoreff) (04/20/88)
> I don't really know how I should view the epithet "theoretician".... Don't view it as abusive or exclusive. > ... The predicate "path_ground" corresponds to a relation over objects > in the Herbrand domain with the main functor 'path/2'. You're right on the money. In light of my intentions, this is the best possible interpretation. This was a (deliberate) case of writing a predicate and then asking: what could it possibly mean? The answer is: nothing that is useful to me. I was fishing for a philosophical exposition, and I got one. Thanks.