OKeefe.R.A.%EDXA@sri-unix.UUCP (11/15/83)
From: O'Keefe HPS (on ERCC DEC-10) <OKeefe.R.A.@EDXA>
I am currently writing a paper which extends Udi Shapiro's
Logic Programs with uncertainties. The mathematical basis
is finished, I am now writing up how you can interpret it.
If there's any interest I'll send it to {SU-SCORE} when I'm
done. The main points are
1) you can use any complete lattice with a least and
a greatest element as your certainty space
2) you can handle disjunction. It turns out that you
have a lot of freedom in defining the certainty
combination rule for disjunction, but you *must*
use the least upper bound for conjunction. (Since
Shapiro used numbers (0,1] the least upper bound is
always one of the two numbers.)
3) you can have "super-certain" rules, which attribute
greater certainty to their conclusion than to any of
their hypotheses. (You don't have to, but if you
want them they make sense.)
4) the theory lets you have a type tree (or several
type trees), I don't know how to interpret that
efficiently yet.
Shapiro's system can't be extended to handle general negation,
because it is based on the standard formal semantics for logic
programs, which associates a monotone map Tp with a logic program
P. In the presence of negation the map is no longer monotone.
You can write an interpreter for MYCIN's rules or PROSPECTOR's
rules in Prolog. (You can write an interpreter for Fortran if you
try hard enough.) The thing is, Prospector's pseudo-probabilities
are not supposed to be a logic, and don't obey all the laws that
you would expect a logic to follow, so you can't expect to gain
anything from Prolog's origin in logic. There is another big
difference between MYCIN and PROSPECTOR on one side and Shapiro's
formulation on the other: the former two handle uncertain
PROPOSITIONS, Shapiro's system handles uncertain first-order
atoms. Propositional calculus and Horn clauses are both special
cases of 1st-order PC, but they are simple in different ways.
If you try to handle negation in clauses you are going to have
trouble.
The problem with searching through formulae equivalent to a
given formula as a general one. The problem is that rules like
X+Y = Y+X
X = 0+X.
do not, in general terminate. You can handle the first sort by
using a fancy unification algorithm: there is a lot of published
on Unification Algorithms with special equational theories built
in. I have never understood it, but Lincoln Wallen here coded
up an AC-unification algorithm in Prolog. This still doesn't
cope with X=0+X. There is a lot known about rewrite rules,
look under Huet in your library catalogue to start with.
The way to do a breadth-first search in Prolog is to
program it up explicitly. You keep a queue of unexplored
alternatives.
bfs(Start, Soln) :-
bfs([Start|Qtail], Qtail, Soln).
bfs([], [], _, _) :- !, fail.
bfs([Soln|_], _, Soln) :-
solution(Soln).
bfs([Node|Queue], Qtail, Soln) :-
sprout(Node, List),
append(List, NewTail, Qtail), !,
bfs(Queue, NewTail, Soln).
E.g. to search through expressions equivalent to a given
one, where you have a predicate
one_rewrite_step(Expr, Rewritten)
you would define
sprout(Expr, Nexprs) :-
setof(Nexpr, one_rewrite_step(Expr,Nexpr), Nexprs).
This code is a bit of a mess, and has not been tested. It is
meant as a suggestive sketch, that's all. To avoid generating
sorry, exploring, the same node more than once you can keep
the original [Start|Qtail] list and do
bfs(Start, Soln) :-
bfs([Start|Qtail], [Start|Qtail], Soln).
bfs([], _, _) :- !, fail.
bfs([Soln|_], _, Soln) :-
solution(Soln).
bfs([Node|Rest], Explored, Soln) :-
sprout(Node, NewNodes),
join(NewNodes, Explored),
!,
bfs(Rest, Explored, Soln).
join([H|T], L) :-
member(H, L), !,
join(T, L).
join([], _).