PROLOG-REQUEST@SU-SCORE.ARPA (Chuck Restivo, The Moderator) (06/10/86)
PROLOG Digest Tuesday, 10 Jun 1986 Volume 4 : Issue 18
Today's Topics:
Review - Turbo-P,
Implementations - Assert & KBES Tools,
LP Library - Update
----------------------------------------------------------------------
Date: Thu Jun 5 21:45:42 1986
From: Herm Fischer <hermix!fischer@rand-unix.ARPA>
Reply-to: HFischer@ada20
Subject: Borland Turbo Prolog
I received a copy of Borland Turbo Prolog, and have
a few initial impressions to convey. (I presently
have been mostly using UNSW prolog under Xenix on
the PC/AT.)
It is a true compiler, and code executes quite fast.
Some examples of LIPS (logical inferences per second)
of test programs (from the net):
TEST PC-AT* PC-CONVERTABLE
FUNCTION UNSW** TURBO TURBO
naive reverse (30 items list) 550 9920 4509
quicksort (reverse order list) 385 8760*** 2390
quicksort (ordered list) 495 8736 3559
---------------
* - PC/AT has 14.6 MHz crystal installed
PC Convertable (new laptop) is unmodified
** - UNSW interpreter timings under Xenix 3.0 version, huge
mem. model Turbo-Prolog timings under MSDOS 3.2
*** - seems inconsistant, but that's the empirical number
>From the speed, and the presence of a full set of features,
I'd say this is one of the first Prolog compilers which is
truly usable for real applications. (It is a bit amazing to
me to have 4500 lips running in a laptop battery powered
computer!)
Features include a very nice user interface (multi-window
system); debugging is done with a trace in one window, the
printed dialog output in another, and the source code in a
third window... the source code steps thru as the trace
progresses, allowing reediting and recompiling from the
middle of a trace without loosing the contents of the
screen windows. The window system is also usable by
applications.
The language is typed, leading to some conversion
difficulties for old Prolog programs with sloppy naming
habits. Ada programmers will love it; Prolog hackers
may have to learn new habits. Typing allows defining
types, weak subtypes, and enforced rules of parameter
checks. This should be a real benefit to developers of
code which must be maintained by crews of programmers
other than the original authors... (though a bit of a
pain for quick and dirty work or conversion of old code)
The syntax is true Clocksin & Mellish.
Some features missing in the first release include arg
and functor (said to be comming out "real soon maybe"),
parentheses nesting of subgoals (hardly ever used
anyway), and findall/bagof restricted to simple atoms
and lists of elements.
I expect this product to legitimize Prolog for the semi
mass market!
-- Herm Fischer
------------------------------
Date: Sun, 8 Jun 86 11:15:18 EST
From: munnari!basser.oz!anand@seismo.CSS.GOV
Subject: 'assert' considered harmful
People tend to use 'assert' as caching mechanism
for inferences because of the absence of a built-in
predicate, say, 'assume', which can perform the task
which David Sherman wants. 'assume' can be seen as a
default rule. As long as you have no information that
will invalidate rule X, you can assume(X). In this
case it is equivalent to saying that as long as the
year is 1986, assume(control(Taxpayer1,Taxpayer2)).
If the year is 1987 and Taxpayer1 no longer controls
Taxpayer2 then some of the inferences drawn earlier
may no longer be valid in the new context. The necessary
changes which have to be done to the knowledge-base is
precisely what TMS or ATMS(Assumption based Truth
Maintenance System) does. Of course, assert cannot be
used instead of assume, because what is asserted is a
THEOREM(true at all times) and not an assumption.
By the way, is anyone over the net aware of a Prolog
implementation with a built-in TMS or ATMS like mechanism,
which provides facilities for 'assuming' and 'retracting'
assumptions.
PS: Let us remember that GOTO was given up(more or less)
because of the availability of better control structures
like FOR & WHILE loops. So if we want 'assert' not to be
misused, let us assert that we need 'assume' and not
assume that 'assert' will do the job for us.
-- Anand S.Rao
------------------------------
Date: 4 Jun 86 18:20:54 GMT
From: hplabs!hao!seismo!mcvax!ukc!icdoc!cdsm@ucbvax.berkeley
Subject: Monkeys & bananas
>From: VERACSD@USC-ISI.ARPA
>Subject: Benchmarking KBES-Toools
>
>I have come across some recent benchmarks from NASA (U.S.
>Gov't MEMORANDUM from the FM7/AI Section, April 3, 1986)
>which compared various KBES tools' (ART, OP, KEE & CLIPS)
>times for solving the MONKEY-AND-BANANA problem. (This
>toy problem is explained in detail along with OPS source
>in Brownston et. al.'s "Programming Expert Systems in OPS5".)
>
>Although the benchmarks include backward-chaining solutions
>to the problem in both KEE and ART (along with forward
>chaining counterparts), there is no PROLOG implementation
>in the comparison. I am very interested in a PROLOG
>comparison, and am in the process of implementing one.
Here is a Prolog solution. It uses much the same logic
as the Brownston book (i.e. forward chaining), though
I've only used "working memory" (the State variables)
for states not goals - this makes it much easier to
incorporate subgoals, which is the reason there are
basically 6 rules (equivalent to 14 Horn Clauses)
rather than 26 in the OPS5 version (though there are
also 21 subsidiary clauses). I've also removed the
"state independent assertions" (light & heavy) from
state, though they could be there. The Prolog solution
takes 92 lines compared with 201 (non-comment) lines
for OPS5. This includes the code for "modify" etc.
which is not included in the OPS5 total. There are
various packages on the market which are implemented
in Prolog but provide the same kind of facilities.
>(By the way, the time to beat is 1.2 secs. for a
>forward-chaining implementation using ART on a
>3640 with 4MB main-memory.)
That's pretty easy. The code below runs in about
0.32 secs on a VAX 750 using the CProlog
interpreter. With a compiler on the DEC 20
you should be able to do an order of magnitude
faster (most of the time is probably spent in i/o
anyway).
I've included the timing routines at the end. You
may have to alter the "cputime" routine to fit your
local Prolog system.
-- Chris Moss
Imperial College
/*
monkey & bananas problem from Brownston & al:
Programming Expert Systems in OPS5 (Addison
Wesley 1985)
*/
test(X) :-
problem(X, Goal, State),
(goal(Goal,State,NewS) ->
writeline(['Congratulations, the goals are satisfied'])
; writeline(['Impossible, the goal',Goal,'cannot be achieved']),fail).
problem(general, hold(bananas),
[monkey([7,7],couch,blanket),
obj(bananas,[9,9],ceiling),
obj(couch,[7,7],floor),
obj(ladder,[4,3],floor),
obj(blanket,[7,7],_)]).
light(bananas).
light(ladder).
light(blanket).
heavy(couch).
/* goal(X,State,New) :-
writeline([goal,X,in,State]), fail.
*/
goal(hold(Object), State,NewS) :-
hold(Object, State) ->
NewS=State
; light(Object) ->
approach(Object, State, State2),
goal(hold(nil), State2,State3),
modify(hold(Object),State3,State4),
modify(on(Object,monkey),State4,NewS),
writeline([monkey,grabs,Object])
; Object=nil,
hold(Obj,State),
modify(hold(nil),State,State2),
modify(on(Obj,floor),State2,NewS),
writeline([monkey,drops,Obj]).
goal(at(Loc), State, NewS) :-
at(Loc,State) ->
NewS=State
; goal(on(floor), State, State2),
goal(hold(nil), State2, State3),
modify(at(Loc),State3,NewS),
writeline([monkey,walks,to,Loc]).
goal(at(Object,Loc), State,NewS) :-
at(Object,Loc,State) ->
NewS=State
; goal(hold(Object),State,State2),
goal(on(floor),State2,State3),
modify(at(Loc),State3,State4),
modify(at(Object,Loc),State4,NewS),
writeline([monkey,carries,Object,to,Loc]).
goal(on(Object), State, NewS) :-
ison(Object, State) ->
NewS=State
; Object=floor ->
modify(on(floor),State,NewS),
writeline([monkey,jumps,to,floor])
; object(Object),
goal(hold(nil),State,State2),
at(Object, Loc, State2),
goal(at(Loc),State2,State3),
modify(on(Obj),State3,NewS),
writeline([monkey,climbs,on,Object]).
/* goal(X,State,New) :-
writeline(['** fail goal',X,in,State]),
fail.
*/
approach(Object, State, NewS) :-
ison(Object,ceiling,State) ->
at(Object,Loc,State),
goal(at(ladder,Loc),State,State2),
goal(on(ladder), State2, NewS)
; at(Object,Loc,State),
/* window : support routines */
goal(at(Loc),State,NewS).
at(Loc,State) :-
inn(monkey(Loc,_,_),State).
at(Object,Loc,State) :-
inn(obj(Object,Loc,_),State).
hold(Object,State) :-
inn(monkey(_,_,Object),State).
ison(On,State) :-
inn(monkey(_,On,_),State).
ison(Object,On,State) :-
inn(obj(Object,_,On),State).
modify(at(Loc),State,NewS) :-
change(monkey(_,On,Holds),monkey(Loc,On,Holds),State,NewS).
modify(at(Object,Loc), State,NewS) :-
change(obj(Object,_,On),obj(Object,Loc,On),State,NewS).
modify(hold(Object),State,NewS) :-
change(monkey(At,On,_), monkey(At,On,Object),State, NewS).
modify(on(Object), State,NewS) :-
change(monkey(At,_,Holds), monkey(At,Object,Holds),State, NewS).
modify(on(Object,On), State, NewS) :-
change(obj(Object,At,_), obj(Object,At,On),State, NewS).
object(X) :- heavy(X) ; light(X).
inn(X, [X|_]).
inn(X, [_|Y]) :- inn(X,Y).
change(Old,New,[Old|List], [New|List]).
change(Old,New, [Other|List], [Other|Newlist]) :-
change(Old,New, List, Newlist).
writeline([]) :- nl.
writeline([A|B]) :-
write(A), write(' '),
writeline(B).
/* timing code */
testit(X) :- cputime(S1), test,
cputime(S2), test2,
cputime(S3),
X is (S2-S1-S3+S2)/10.
/* this works for Cprolog but maybe not for others */
cputime(X) :- X is cputime.
for(X,X,Y).
for(X,Y,Z) :- Y < Z, Y1 is Y+1, for(X,Y1,Z).
test :- for(X,1,10), test1, fail.
test.
test1 :- test(general), !.
test2 :- for(X,1,10), dummy, fail.
test2.
dummy.
------------------------------
Date: 5 Jun 86 08:12:00 EST
From: "CUGINI, JOHN" <cugini@nbs-vms.ARPA>
Subject: C-Prolog manual enhancements
For what it's worth, here are some things we've developed to
enhance/correct the C-Prolog manual for version 1.5. I haven't
seen anything like this around, so here's hoping this will
save everyone from doing the same work. There are four chunks:
1. a table of contents
2. an errata sheet
3. an improved summary of evaluable predicates, including several
ones missing from the original, and page references
4. a syntax summary
Feel free to copy/improve, etc.
John Cugini <Cugini@nbs-vms>
Institute for Computer Sciences and Technology
National Bureau of Standards
Table of Contents
C-Prolog User's Manual, Version 1.5
1 Using C-Prolog . . . . . . . . . . . . . . . . . . . . . . 1
1.1 Preface . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Using C-Prolog -- Overview . . . . . . . . . . . . . . . 1
1.3 Access to C-Prolog . . . . . . . . . . . . . . . . . . . 2
1.4 Reading-in Programs . . . . . . . . . . . . . . . . . . . 2
1.5 Directives: Questions and Commands . . . . . . . . . . . 3
1.6 Saving A Program . . . . . . . . . . . . . . . . . . . . 5
1.7 Restoring A Saved Program . . . . . . . . . . . . . . . . 5
1.8 Program Execution And Interruption . . . . . . . . . . . 5
1.9 Nested Executions -- Break and Abort . . . . . . . . . . 5
1.10 Exiting From The Interpreter . . . . . . . . . . . . . . 6
2 Prolog Syntax . . . . . . . . . . . . . . . . . . . . . . . 6
2.1 Terms . . . . . . . . . . . . . . . . . . . . . . . . . . 6
2.2 Operators . . . . . . . . . . . . . . . . . . . . . . . . 8
2.3 Syntax Errors . . . . . . . . . . . . . . . . . . . . . . 10
2.4 Using a Terminal without Lower-Case . . . . . . . . . . . 10
3 The Meaning of Prolog Programs . . . . . . . . . . . . . . 11
3.1 Programs . . . . . . . . . . . . . . . . . . . . . . . . 11
3.2 Declarative and Procedural Semantics . . . . . . . . . . 13
3.3 Occurs Check . . . . . . . . . . . . . . . . . . . . . . 14
3.4 The Cut Symbol . . . . . . . . . . . . . . . . . . . . . 14
4 Debugging Facilities . . . . . . . . . . . . . . . . . . . 15
4.1 The Procedure Box Control Flow Model . . . . . . . . . . 15
4.2 Basic Debugging Predicates . . . . . . . . . . . . . . . 17
4.3 Tracing . . . . . . . . . . . . . . . . . . . . . . . . . 17
4.4 Spy Points . . . . . . . . . . . . . . . . . . . . . . . 17
4.5 Format of Debugging Messages . . . . . . . . . . . . . . 18
4.6 Options Available during Debugging . . . . . . . . . . . 19
4.7 Reconsulting during Debugging . . . . . . . . . . . . . . 20
5 Evaluable Predicates . . . . . . . . . . . . . . . . . . . 21
5.1 Input and Output . . . . . . . . . . . . . . . . . . . . 21
5.1.1 Reading-in Programs . . . . . . . . . . . . . . . . . . 22
5.1.2 File Handling . . . . . . . . . . . . . . . . . . . . . 22
5.1.3 Input and Output of Terms . . . . . . . . . . . . . . . 23
5.1.4 Character Input/Output . . . . . . . . . . . . . . . . 23
5.2 Arithmetic . . . . . . . . . . . . . . . . . . . . . . . 24
5.3 Convenience . . . . . . . . . . . . . . . . . . . . . . . 26
5.4 Extra Control . . . . . . . . . . . . . . . . . . . . . . 26
5.5 Meta-Logical . . . . . . . . . . . . . . . . . . . . . . 27
5.6 Sets . . . . . . . . . . . . . . . . . . . . . . . . . . 28
5.7 Comparison of Terms . . . . . . . . . . . . . . . . . . . 29
5.8 Modification of the Program . . . . . . . . . . . . . . . 31
5.9 Information about the State of the Program . . . . . . . 32
5.10 Internal Database . . . . . . . . . . . . . . . . . . . . 32
5.11 Debugging . . . . . . . . . . . . . . . . . . . . . . . . 33
5.12 Environmental . . . . . . . . . . . . . . . . . . . . . . 34
5.13 Preprocessing . . . . . . . . . . . . . . . . . . . . . . 35
Appendix I -- Summary of Evaluable Predicates . . . . . . . . . 36
Errata for C-Prolog User's Manual, Version 1.5
Page Description
---- -----------
23 Undocumented predicate "append(F)" for appending to files
should appear here.
24 Example should be X = 3, not X = 5.
25 Symbol for integer bitwise disjunction is "\/".
25 Note left-shift is zero-fill, right-shift is fill with
value of leading bit.
26 Symbol for X numerically not equal to Y is "=\="
32 Undocumented predicate current_op(Priority, Type, Name)
should appear here.
36 atomic(T) true for atom, number or DB reference.
-- There are two more undocumented evaluable predicates:
c([Head | Tail], Head, Tail) (like Lisp cons) and
length (List, N) to get length of list.
C-Prolog Predicate Index
Predicate Page Description
--------- ---- -----------
abolish(F,N) 31 Abolish the procedure named F arity N.
abort 6, 34 Abort execution of the current directive.
* append(F) 23 open file F to be appended to.
arg(N,T,A) 28 The Nth argument of term T is A.
assert(C) 31 Assert clause C.
assert(C,R) 31 Assert clause C, ref. R.
asserta(C) 31 Assert C as first clause.
asserta(C,R) 31 Assert C as first clause, ref. R.
assertz(C) 31 Assert C as last clause.
assertz(C,R) 31 Assert C as last clause, ref. R.
atom(T) 27 Term T is an atom.
atomic(T) 27 Term T is an atom, number, or DB reference.
bagof(X,P,B) 29 The bag of Xs such that P is provable is B.
break 6, 34 Break at the next procedure call.
* c(L,H,T) 26 List L has head H and tail T (Lisp cons).
call(P) 28 Execute the procedure call P.
clause(P,Q) 31 There is a clause, head P, body Q.
clause(P,Q,R) 31 There is an clause, head P, body Q, ref R.
close(F) 22 Close file F.
compare(C,X,Y) 30 C is the result of comparing terms X and Y.
consult(F) 22 Extend the program with clauses from file F.
cputime 25 CPU time since C-Prolog was started, in seconds.
current_atom(A) 32 One of the currently defined atoms is A.
current_functor(A,T) 32 A current functor is named A, m.g. term T.
* current_op(P,T,A) 8, 32 A current op is named A, of type T, priority P.
current_predicate(A,P) 32 A current predicate is named A, m.g. goal P.
db_reference(T) 27 T is a database reference.
debug 17, 33 Switch on debugging.
debugging 17, 34 Output debugging status information.
display(T) 23 Display term T on the terminal.
erase(R) 32 Erase the clause or record, ref. R.
erased(R) 33 The object with ref. R has been erased.
expanded_exprs(O,N) 26 Expression expansion if N=on.
expand_term(T,X) 35 Term T is a shorthand which expands to term X.
exists(F) 22 The file F exists.
fail 27 Backtrack immediately.
fileerrors 22 Enable reporting of file errors.
functor(T,F,N) 27 The top functor of term T has name F, arity N.
get(C) 23 The next non-blank character input is C.
get0(C) 23 The next character input is C.
halt 6 Halt Prolog, exit to the monitor.
heapused 25 Heap space in use, in bytes.
instance(R,T) 33 A m.g. instance of the record ref. R is T.
integer(T) 27 Term T is an integer.
Y is X 26 Y is the value of arithmetic expression X.
keysort(L,S) 30 The list L sorted by key yields S.
leash(M) 17, 33 Set leashing mode to M.
* length(L,N) 26 List L is of length N.
listing 32 List the current program.
listing(P) 32 List the procedure(s) P.
* undocumented
Predicate Page Description
--------- ---- -----------
name(A,L) 28 The name of atom or number A is string L.
nl 23 Output a new line.
nodebug 17, 33 Switch off debugging.
nofileerrors 22 Disable reporting of file errors.
nonvar(T) 27 Term T is a non-variable.
nospy Spec 18, 33 Remove spy-points from the procedure(s) P.
not(P) 26 see \+ P, below.
number(T) 27 Term T is a number.
op(P,T,A) 8, 34 Make atom A an operator of type T precedence P.
primitive(T) 27 T is a number or a database reference
print(T) 23 Portray or else write the term T.
prompt(A,B) 34 Change the prompt from A to B.
put(C) 23 The next character output is C.
read(T) 23 Read term T.
reconsult(F) 22 Update the program with procedures from file F.
recorda(K,T,R) 32 Make term T the first record under key K, ref. R.
recorded(K,T,R) 32 Term T is recorded under key K, ref. R.
recordz(K,T,R) 32 Make term T the last record under key K, ref. R.
rename(F,G) 23 Rename file F to G.
repeat 27 Succeed repeatedly.
retract(C) 31 Erase the first clause of form C.
save(F) 5, 34 Save the current state of Prolog in file F.
save(F,When) 34 Like save(F), but When says how returned.
see(F) 22 Make file F the current input stream.
seeing(F) 22 The current input stream is named F.
seen 22 Close the current input stream.
setof(X,P,B) 29 The set of Xs such that P is provable is B.
sh 35 Start a recursive shell
skip(C) 23 Skip input characters until after character C.
sort(L,S) 30 The list L sorted into order yields S.
spy Spec 18, 33 Set spy-points on the procedure(s) P.
statistics 35 Display execution statistics.
system(S) 34 Execute command S.
tab(N) 23 Output N spaces.
tell(F) 22 Make file F the current output stream.
telling(F) 22 The current output stream is named F.
told 22 Close the current output stream.
trace 17, 33 Switch on debugging and start tracing.
true 26 Succeed.
var(T) 27 Term T is a variable.
write(T) 23 Write the term T.
writeq(T) 23 Write the term T, quoting names if necessary.
Predicate Page Description
--------- ---- -----------
'LC' 11, 34 The following Prolog text uses lower case.
'NOLC' 11, 34 The following Prolog text uses upper case only.
P,Q 26 P and (then) Q.
P;Q 26 P or (else) Q.
P -> Q ; R 27 if P then Q else R.
P -> Q 27 if P then Q else fail.
! 14, 26 Cut any choices taken in the current procedure.
\+ P 26 Goal P is not provable. (i.e., not(P) ).
X^P 29 There exists an X, such that P is provable.
X+Y, X-Y, X*Y, X/Y 24 Addition, subtraction, multiplication, division.
X//Y 24 Integer division
X mod Y 24 X (integer) modulo Y
-X 25 Unary minus
X^Y 25 Involution
X/\Y 25 Integer bitwise conjunction
X\/Y 25 Integer bitwise disjunction
X<<Y 25 Integer bitwise left shift of X by Y places
X>>Y 25 Integer bitwise right shift of X by Y places
\X 25 Integer bitwise negation
mathematical functions: 25 exp,log,log10,sqrt,sin,cos,tan,asin,acos,atan,floor
X<Y 26 As numbers, X is less than Y.
X=<Y 26 As numbers, X is less than or equal to Y.
X>Y 26 As numbers, X is greater than Y.
X>=Y 26 As numbers, X is greater than or equal to Y.
X=:=Y 26 As numbers, the values of X and Y are equal.
X=\=Y 26 As numbers, the values of X and Y are not equal.
X=Y 26 Terms X and Y are equal (i.e. unified).
T=..L 28 The functor and args. of term T comprise list L.
X==Y 30 Terms X and Y are strictly identical.
X\==Y 30 Terms X and Y are not strictly identical.
X@<Y 30 Term X precedes term Y.
X@=<Y 30 Term X precedes or is identical Y.
X@>Y 30 Term X follows term Y.
X@>=Y 30 Term X follows or is identical to term Y.
[Car|Cdr] or [1,2,3] 7 As a term, a list ( [] is the null list.)
.(Car, Cdr) 7 As a term, a list, de-sugared
[F1,F2,...] 3, 22 Perform the consult(s) for files F1, F2,..
[-F1,-F2,...] 3, 22 Perform the reconsult(s) for files F1, F2,..
[X] 26 Evaluates to X, if X is an integer.
C-Prolog syntax
Meta-symbols:
{} for grouping, | for "or", /* for comments */
* for 0-n occurences, ? for 0-1, + for 1-n
----- micro-level -----
term = constant | variable | compound-term
constant = number | atom
number = sign? digit+ rest-of-number
sign = plus | minus
atom = atom-character character*
| single-quote character+ single-quote
atom-character = lowercase-letter | most-special-characters
variable = named-variable | anon-variable
named-variable = uppercase-letter character*
| underline character+
anon-variable = underline
compound-term = functor arg-list | operator-expr
/* User-defined or built-in.
Some of the built-ins are
arithmetic, not logical. */
functor = atom
arg-list = (argument {, argument}* )
argument = term
operator-expr = prefix-op | postfix-op | infix-op
prefix-op = operator argument
postfix-op = argument operator
infix-op = argument operator argument
operator = functor /* see page 9 for built-ins */
----- macro-level -----
program = clause+
clause = {positive-clause | negative-clause} period
positive-clause = unit-clause | nonunit-clause
unit-clause = head
head = literal
literal = predicate arg-list?
predicate = functor
nonunit-clause = head body
body = :- disjunct {; disjunct}*
disjunct = conjunct {, conjunct}*
conjunct = goal
goal = literal | (clause) /* can nest with parens */
negative-clause = query
query = body
(or directive)
procedure for P = set of clauses for whose head the functor is P
Prolog data types form a half-lattice:
term
/ \
/ \
/ \
/ \
/ \
/ \
/ \
nonvar simple
/ \ / \
/ \ / \
/ \ / \
/ \ / \
/ \ / \
/ \ / \
/ \ / \
literal atomic var
/ \ (constant) |\
/ \ / | \ | \
/ \ / | \ | \
/ \ / | \ | \
compound \ / | \ | \
term \ / | \ | \
\ / | \ | \
atom number DB-ref named anonymous
/ \
/ \
/ \
/ \
integer float
-------------------------------
End of PROLOG Digest
********************