PROLOG-REQUEST@SUSHI.STANFORD.EDU (Chuck Restivo, The Moderator) (04/25/87)
PROLOG Digest Monday, 27 Apr 1987 Volume 5 : Issue 31
Today's Topics:
Implementation - Cut & Meta-interpreter,
Programming - Shortest Path
----------------------------------------------------------------------
Date: Mon, 20 Apr 87 09:52:05 PST
From: Fernando Pereira <pereira@stinson.ai.sri.com>
Subject: Cut in metainterpreters
The best published source of a meta-circular interpreter for cut is
Richard O'Keefe's paper ``On the treatment of Cuts in Prolog
Source-Level Cuts'', 1985 IEEE Symposium on Logic Programming, pp.
68-72. For those who don't have access to this paper, here is the
interpreter
do_goal(Goal) :-
system_predicate(Goal), !,
call(Goal).
do_goal(Goal) :-
clause(Goal, Body),
do_body(Body, AfterCut, HadCut),
( HadCut = yes,
!, % cuts the whole do_goal
do_body(AfterCut)
; HadCut = no
).
do_body(Body) :-
do_body(Body, AfterCut, HadCut),
( HadCut = yes,
!, % cuts the whole do_body
do_body(AfterCut)
; HadCut = no
).
do_body((!,AfterCut), AfterCut, yes) :- !.
do_body((Goal,Body), AfterCut, HadCut) :- !,
do_goal(Goal),
do_body(Body, AfterCut, HadCut).
do_body(!, true, yes).
do_body((Disj1;Disj2), AfterCut, HadCut) :-
do_body(Disj1, AfterCut, HadCut).
do_body((Disj1;Disj2), AfterCut, HadCut) :- !,
do_body(Disj2, AfterCut, HadCut).
do_body(Goal, true, no) :-
do_goal(Goal).
Incidentally, the first interpreter of this kind I saw was the first
version of the interpreter in DEC-10 Prolog, written by David H. D. Warren
(more recent versions use something like ancestral cut).
-- Fernando Pereira
------------------------------
Date: 20 Apr 87 21:17:54 GMT
From: MorrisseyKA <ihnp4!drutx!druhi!kam@ucbvax.Berkeley.EDU>
Subject: cut for metainterpreter
One solution is:
execute(true) :- !.
execute((P,Q)) :- !, execute(P), execute(Q).
execute(P) :- clause((P:-Q)), execute(Q).
execute(P) :- P.
It is attributed to Pereira (don't know which one) and can be found on
page 157 of:
HOW TO SOLVE IT WITH PROLOG
4th edition
by H. Coelho, J. Cotta, and L. Pereira
Lisbon, 1985
-- Karen A. Morrissey
------------------------------
Date: 23 Apr 87 00:01:21 GMT
From: Rafail Ostrovsky <raf@bu-cs.bu.edu>
Subject: cut for metainterpreter
In response to my question for meta-circular interpreter which
includes cut (without the use of ancesstor cut in the implementation!)
Karen A. Morrissey proposes the "solution" which is just a regular
meta-interpeter, but DOES NOT incorporate cut!
Here is a possible solution which does incorporate cut and is based on
the assumption (which is true for C-Prolog) that cut cuts the goal
choice-point rather then the disjunctive choice-point:
%-------------------------------------------------------
% /* meta-circular interpreter with cut */
%-------------------------------------------------------
% Author: Rafail Ostrovsky 4/20/1987
%-------------------------------------------------------
%
solve(G) :- solve(G,_).
solve(!,X) :- var(X);X=cut.
solve((A,B),C) :- solve(A,C),solve(B,C).
solve(A,C)
:- C==cut;
(system_pred(A),!,A);
(clause(A,B),solve(B,C1),(var(C1);C1==cut,!,fail)).
%-------------------------------------------------------
I do not know how to implement ancesstor cut (see Shapiro and Sterling
book) without the use of ancesstor cut at the meta-level, and how to
implement meta-circular interpreter with cut without the use of the
above assumption.
-- raf
------------------------------
Date: 22 Apr 87 14:52:00 EST
From: John Cugini <cugini@icst-ecf.arpa>
Subject: shortest path algorithm for graphs
Although this is a fairly classic algorithm, (from Baase, Computer
Algorithms) I thought it might be worth broadcasting. The essential
idea is that you progress outward from a source node, always taking
the shortest path available, until you stumble across the Target - so
it's a kind of breadth-first search, with the understanding that
length is as measured by the arcs traversed, not simply the number of
nodes.
-- John Cugini
%% Shortest path algorithm
% edges are bi-directional in this example. For uni-directional
% edges, just put in edge(From, To, Dist) facts, like eg:
/*
edge(c, a, 4).
edge(a, b, 2).
edge(b, c, 3).
edge(b, d, 5).
edge(d, e, 6).
edge(e, a, 1).
*/
edge(N1, N2, Dist) :-
bi_edge(N1, N2, Dist);
bi_edge(N2, N1, Dist).
bi_edge(a, b, 2).
bi_edge(b, c, 10).
bi_edge(b, d, 3).
bi_edge(d, c, 4).
bi_edge(d, e, 18).
bi_edge(d, f, 6).
bi_edge(e, f, 7).
% shortpath(N1, N2, Path, Tot_dist) iff Path is the shortest path from
% N1 to N2 (expressed as a list of nodes), with a total distance of
% Tot_dist. This is the user's top-level predicate. Only N1 must be
% instantiated. If N2 is var, shortpaths to all other nodes will be
% found in order of increasing length.
shortpath(N1, N2, Path, Tot_dist) :-
nonvar(N1),
seek_next(N1, N2, [node_state(N1, reached, 0, [])], 0, Path, Tot_dist).
% seek_next(From, Target, State_list, Dist_so_far, Path, Tot_dist) seeks the next
% closest node to the source, searching out from From.
seek_next(Target, Target, State_list, Tot_dist, Path, Tot_dist) :-
build_path(Target, State_list, R_path),
reverse(R_path, Path).
seek_next(Here, Target, State_list, Dist_so_far, Path, Tot_dist) :-
(setof(Next-This_dist, edge(Here, Next, This_dist), Adj_list) ->
process_all_adj(Here, Adj_list, State_list, Dist_so_far, Mid_list);
Mid_list = State_list
),
% blithe assumption here that no valid path will exceed 1e38 in length.
get_best_nearby(Mid_list, 1e38, dummy, Best_name, Best_dist, New_list),
seek_next(Best_name, Target, New_list, Best_dist, Path, Tot_dist).
% process_all_adj(Here, Adj_list, State_list, Dist_so_far, New_list) checks all
% nodes adjacent to Here, and updates their status and distance in the State_list,
% generating a New_list of states. Each entry in the state-list is of the form:
%
% node_state(Name, % unique identifier of node
% Status, % reached, nearby (adjacent to a reached node), or unseen
% Distance % shortest distance from source found so far.
% predecessor % predecessor node in best-so-far path
% )
process_all_adj(Here, [Next-This_dist | Rest_adj], State_list, Dist_so_far, New_list) :-
(get_state(Next, State_list, Status, Dist_next, Predecessor) ->
true;
Status = unseen
),
!,
Poss_dist is Dist_so_far + This_dist,
adjust_state_list(Status, Poss_dist, Dist_next, Next, Here, State_list, Inter_list),
process_all_adj(Here, Rest_adj, Inter_list, Dist_so_far, New_list).
process_all_adj(Here, [], State_list, Dist_so_far, State_list).
% adjust_state_list(Status, Poss_dist, Dist_next, Next, Here, State_list, Inter_list)
% updates the single entry for the Next node in the State_list, producing a partially
% updated list, Inter_list.
adjust_state_list(unseen, Poss_dist, Prev_dist, Next, Here, State_list,
[node_state(Next, nearby, Poss_dist, Here) | State_list]).
adjust_state_list(reached, Poss_dist, Prev_dist, Next, Here, State_list, State_list).
adjust_state_list(nearby, Poss_dist, Prev_dist, Next, Here, State_list, Inter_list) :-
Poss_dist < Prev_dist ->
change_state(Next, nearby, Poss_dist, Here, State_list, Inter_list);
Inter_list = State_list.
% get_best_nearby(State_list, BSF_dist, BSF_name, Best_name, Best_dist,
% New_list) scans the State_list and finds the nearby (but unreached)
% node with the lowest distance from the source, and marks it as
% reached. BSF distance and name are the Best So Far, as the list is
% scanned. If this fails, then there are no nearby nodes and the whole
% shortpath predicate fails, indicating that no path exists between the
% requested nodes.
% handle nearby nodes
get_best_nearby([node_state(Name, nearby, Dist, Pred) | Old_rest],
BSF_dist, BSF_name, Best_name, Best_dist, [New_elem | New_rest]) :-
(Dist < BSF_dist ->
(New_dist = Dist, New_name = Name);
(New_dist = BSF_dist, New_name = BSF_name)
),
!,
get_best_nearby(Old_rest, New_dist, New_name, Best_name, Best_dist, New_rest),
(Name = Best_name ->
New_elem = node_state(Name, reached, Dist, Pred);
New_elem = node_state(Name, nearby, Dist, Pred)
).
% handle reached nodes
get_best_nearby([Elem | Old_rest], BSF_dist, BSF_name, Best_name, Best_dist,
[Elem | New_rest]) :-
get_best_nearby(Old_rest, BSF_dist, BSF_name, Best_name, Best_dist, New_rest).
get_best_nearby([], BSF_dist, BSF_name, BSF_name, BSF_dist, []) :-
% again, blithe assumption here that no valid path will exceed 1e38 in length.
BSF_dist < 0.99e38.
% build_path(This, State_list, Path) constructs Path backwards from This by
% using the Predecessor field in the node_states of State_list.
build_path(This, State_list, [This | Rest]) :-
get_state(This, State_list, _, _, Pred),
(Pred = [] ->
Rest = [];
build_path(Pred, State_list, Rest)
).
% get_state(Name, State_list, Status, Dist, Predecessor) finds the node_state
% entry in State_list with Name as its name, and returns its Status,
% Distance and Predecessor.
get_state(From, [node_state(From, Status, Dist, Predecessor) | Rest],
Status, Dist, Predecessor) :- !.
get_state(From, [Elem | Rest], Status, Dist, Predecessor) :-
get_state(From, Rest, Status, Dist, Predecessor).
% change_state(Name, Status, Distance, Predecessor, Old_list, New_list) changes
% the existing entry for Node in the Old_list, to produce the New_list.
change_state(Name, Status, Distance, Predecessor,
[node_state(Name, _, _, _) | Rest],
[node_state(Name, Status, Distance, Predecessor) | Rest]) :- !.
change_state(Name, Status, Distance, Predecessor, [Elem | Old_Rest], [Elem | New_Rest]) :-
change_state(Name, Status, Distance, Predecessor, Old_Rest, New_Rest).
% Standard utilities here
reverse(List1,List2) :- reverse_1(List1, [], List2).
reverse_1([], List2, List2) :- !.
reverse_1([Head | Tail], So_far, List2) :-
reverse_1(Tail, [Head | So_far], List2).
------------------------------
End of PROLOG Digest
********************