PROLOG-REQUEST@SU-SCORE.ARPA (Chuck Restivo, The Moderator) (03/07/86)
PROLOG Digest Monday, 10 Mar 1986 Volume 4 : Issue 11
Today's Topics:
Implementation - Predicate behavior & LIPS
----------------------------------------------------------------------
Date: 18 Feb 86 15:37:35 PST (Tue)
From: TSung@Aero
Subject: behavior of recorda, recorded, erase
Yes, I tried on CProlog 1.5, and what you said was true.
Here's what I found.
First, define:
t1(Key,T) :- recorda(Key,T,R), erase(R).
t2(Key,T) :- recordz(Key,T,R), erase(R).
trying with different predefined predicates, I found that:
a) recorda and recordz behaves the same in this respect.
b) if you write out the key fully, e.g.
Key = arg(A,B,C)
listing,
atom(A),
true,
then there is a problem with erasing as stated.
c) if the built-in predicate takes arguments, and you only
write the principal functor, e.g.
Key = arg,
atom,
assert,
then CProlog1.5 will erase ok. (The 1.5 manual specifically
says that, in recorda and recordz, only the principal functor
of the Key is significant (p.32). This shows that there is
a difference).
d) After trying to erase unsuccessfully thus, the interpreter
turns on the debug switch. e.g.
?- t1(arg(A,B,C),a).
! Attempt to erase a system object.
?- nodebug.
?- Debug mode switched off.
(if debug switch were not on, it would just say "yes")
I found this out when trying to do a second unsuccessful
t1(...), it goes into debugger after the error message.
But then, I think debug is switch on after every system error
message.
In short, it seems definitely a bug in the CProlog interpreter.
-- Fu-Sheng
------------------------------
Date: 14 Feb 86 17:28:45 GMT
From: Sundar R. Lyengar <Sundar@ucbvax.berkeley.edu>
Subject: recorda,recorded,erase--behavior
I tested the problem in our Cprolog_1.5 on Vax (bsd4.2).
Yes, the erase does fail if the key used in a corresponding
'recorda' is an evaluable predicate. However, the erase works
just fine if the Key is a simple atom. Since the key used is
only the functor of the first argument to 'recorda', you don't
have to use the entire term. So a temporary fix for your
problem would be,
recorda(arg,...,R),
recorded(arg,...X),
erase(R).
However, I don't what is causing the problem. I hope this
helps.
-- Sundar R. Iyengar
------------------------------
Date: Wed, 5 Mar 86 14:23:09 -0100
From: Micha Meier <unido!ecrcvax!Micha@seismo.CSS.GOV>
Subject: LIPS again
The speed of the current Prolog systems is still measured
using the naive reverse example with a list of 30 elements. I
guess that anybody who has tried this with a system that runs
over 10 kLIPS has seen the inconvenience - the time spent in
executing this example is too short to be measured correctly.
The other drawback is that many implementors concentrate on
optimizing this very example and the like, i.e. deterministic
procedures processing lists and the results for other types of
programs may be totally different (e.g. there is a Prolog system
running 'quicksort' 20 times slower than 'nreverse').
Below, I include the listing of a test program which tries
to solve these problems: first, it includes a procedure which
measures LIPS on naive reverse of an arbitrary list. Second, a
procedure that measures LIPS on quicksort of a list in descending
order; third, measuring of LIPS by quicksort of an ordered list.
I suppose that indexing prevents choices in concatenate and in
partition([], _, _, _).
The first case is purely deterministic - no choice points and
no failures.
In the second case, the number of inferences is o(n*n/2) and
the same for choice points created. In the last example, the
number of inferencesis o(n*n), for choices and failures it is
o(n*n/2).
The quicksort example better reflects the speed of a Prolog
system: it creates some choice points, uses the cut and calls an
evaluable predicate. When the implementors try to optimize the
first clause for 'partition/4' to yield something like
partition([X|L], Y, [X|L1], L2) :- X < Y, !, partition(L, Y, L1, L2).
get list A1
unify variable X5
unify variable X1
get list A3
unify value X5
unify variable A3
put value X5, A1
escape </2
neckcut
execute partition/4
then the whole system is likely to run fast even on
nondeterministic examples with some arithmetic.
-- Micha
% File : LIPS.PL
% Author : Micha Meier
% Purpose : Testing the speed of naive reverse and quicksort of
% an arbitrary long list.
% On systems without reals it is necessary to multiply I
% (inferences no.) by the time unit, e.g. 1000 if cputime
% is in miliseconds.
test :- write('list length : '),
read(X),
conslist(X, List),
T1 is cputime,
nreverse(List, _),
T2 is cputime,
T is T2 - T1,
I is (X*(X+3))/2 + 1,
LIPS is I/T,
write(' LIPS of naive reverse: '),
write(LIPS),
nl,
T3 is cputime,
qsort(List, _, []),
T4 is cputime,
TT is T4 - T3,
II is (X*(X+5))/2 + 1,
LIPS1 is II/TT,
write(' LIPS of quicksort (reverse order): '),
write(LIPS1),
nl,
T5 is cputime,
qsort1(List, _, []),
T6 is cputime,
TTT is T6 - T5,
III is (X+1)*(X+1),
LIPS2 is III/TTT,
write(' LIPS of quicksort (ordered): '),
write(LIPS2),
nl.
nreverse([], []).
nreverse([X|L0],L) :- nreverse(L0, L1),
concatenate(L1, [X], L).
concatenate([], L, L).
concatenate([X|L1], L2, [X|L3]) :- concatenate(L1, L2, L3).
conslist(0, []) :- !.
conslist(N, [N|L]) :-
N1 is N-1,
conslist(N1, L).
qsort([X|L], R, R0) :-
partition(L, X, L1, L2),
qsort(L2, R1, R0),
qsort(L1, R, [X|R1]).
qsort([], R, R).
partition([X|L], Y, [X|L1], L2) :-
X < Y,
!,
partition(L, Y, L1, L2).
partition([X|L], Y, L1, [X|L2]) :-
partition(L, Y, L1, L2).
partition([], _, [], []).
qsort1([X|L], R, R0) :-
partition1(L, X, L1, L2),
qsort1(L2, R1, R0),
qsort1(L1, R, [X|R1]).
qsort1([], R, R).
partition1([X|L], Y, [X|L1], L2) :-
X > Y,
!,
partition(L, Y, L1, L2).
partition1([X|L], Y, L1, [X|L2]) :-
partition1(L, Y, L1, L2).
partition1([], _, [], []).
------------------------------
End of PROLOG Digest
********************PROLOG-REQUEST@SU-SCORE.ARPA (Chuck Restivo, The Moderator) (03/10/86)
PROLOG Digest Monday, 10 Mar 1986 Volume 4 : Issue 11
Today's Topics:
Implementation - Predicate behavior,
Performance - LIPS
----------------------------------------------------------------------
Date: 18 Feb 86 15:37:35 PST (Tue)
From: TSung@Aero
Subject: Behavior of recorda, recorded, erase
Yes, I tried on CProlog 1.5, and what you said was true.
Here's what I found.
First, define:
t1(Key,T) :- recorda(Key,T,R), erase(R).
t2(Key,T) :- recordz(Key,T,R), erase(R).
trying with different predefined predicates, I found that:
a) recorda and recordz behaves the same in this respect.
b) if you write out the key fully, e.g.
Key = arg(A,B,C)
listing,
atom(A),
true,
then there is a problem with erasing as stated.
c) if the built-in predicate takes arguments, and you only
write the principal functor, e.g.
Key = arg,
atom,
assert,
then CProlog1.5 will erase ok. (The 1.5 manual specifically
says that, in recorda and recordz, only the principal functor
of the Key is significant (p.32). This shows that there is
a difference).
d) After trying to erase unsuccessfully thus, the interpreter
turns on the debug switch. e.g.
?- t1(arg(A,B,C),a).
! Attempt to erase a system object.
?- nodebug.
?- Debug mode switched off.
(if debug switch were not on, it would just say "yes")
I found this out when trying to do a second unsuccessful
t1(...), it goes into debugger after the error message.
But then, I think debug is switch on after every system error
message.
In short, it seems definitely a bug in the CProlog interpreter.
-- Fu-Sheng
------------------------------
Date: 14 Feb 86 17:28:45 GMT
From: Sundar R. Lyengar <Sundar@ucbvax.berkeley.edu>
Subject: recorda,recorded,erase--behavior
I tested the problem in our Cprolog_1.5 on Vax (bsd4.2).
Yes, the erase does fail if the key used in a corresponding
'recorda' is an evaluable predicate. However, the erase works
just fine if the Key is a simple atom. Since the key used is
only the functor of the first argument to 'recorda', you don't
have to use the entire term. So a temporary fix for your
problem would be,
recorda(arg,...,R),
recorded(arg,...X),
erase(R).
However, I don't what is causing the problem. I hope this
helps.
-- Sundar R. Iyengar
------------------------------
Date: Wed, 5 Mar 86 14:23:09 -0100
From: "Micha Meier" <unido!ecrcvax!micha@seismo.CSS.GOV>
Subject: LIPS again
The speed of the current Prolog systems is still measured
using the naive reverse example with a list of 30 elements. I
guess that anybody who has tried this with a system that runs
over 10 kLIPS has seen the inconvenience - the time spent in
executing this example is too short to be measured correctly.
The other drawback is that many implementors concentrate on
optimizing this very example and the like, i.e. deterministic
procedures processing lists and the results for other types of
programs may be totally different (e.g. there is a Prolog system
running 'quicksort' 20 times slower than 'nreverse').
Below, I include the listing of a test program which tries
to solve these problems: first, it includes a procedure which
measures LIPS on naive reverse of an arbitrary list. Second, a
procedure that measures LIPS on quicksort of a list in descending
order; third, measuring of LIPS by quicksort of an ordered list.
I suppose that indexing prevents choices in concatenate and in
partition([], _, _, _).
The first case is purely deterministic - no choice points and
no failures.
In the second case, the number of inferences is o(n*n/2) and
the same for choice points created. In the last example, the
number of inferencesis o(n*n), for choices and failures it is
o(n*n/2).
The quicksort example better reflects the speed of a Prolog
system: it creates some choice points, uses the cut and calls an
evaluable predicate. When the implementors try to optimize the
first clause for 'partition/4' to yield something like
partition([X|L], Y, [X|L1], L2) :- X < Y, !, partition(L, Y, L1, L2).
get list A1
unify variable X5
unify variable X1
get list A3
unify value X5
unify variable A3
put value X5, A1
escape </2
neckcut
execute partition/4
then the whole system is likely to run fast even on
nondeterministic examples with some arithmetic.
-- Micha
% File : LIPS.PL
% Author : Micha Meier
% Purpose : Testing the speed of naive reverse and quicksort of
% an arbitrary long list.
% On systems without reals it is necessary to multiply I
% (inferences no.) by the time unit, e.g. 1000 if cputime
% is in miliseconds.
test :- write('list length : '),
read(X),
conslist(X, List),
T1 is cputime,
nreverse(List, _),
T2 is cputime,
T is T2 - T1,
I is (X*(X+3))/2 + 1,
LIPS is I/T,
write(' LIPS of naive reverse: '),
write(LIPS),
nl,
T3 is cputime,
qsort(List, _, []),
T4 is cputime,
TT is T4 - T3,
II is (X*(X+5))/2 + 1,
LIPS1 is II/TT,
write(' LIPS of quicksort (reverse order): '),
write(LIPS1),
nl,
T5 is cputime,
qsort1(List, _, []),
T6 is cputime,
TTT is T6 - T5,
III is (X+1)*(X+1),
LIPS2 is III/TTT,
write(' LIPS of quicksort (ordered): '),
write(LIPS2),
nl.
nreverse([], []).
nreverse([X|L0],L) :- nreverse(L0, L1),
concatenate(L1, [X], L).
concatenate([], L, L).
concatenate([X|L1], L2, [X|L3]) :- concatenate(L1, L2, L3).
conslist(0, []) :- !.
conslist(N, [N|L]) :-
N1 is N-1,
conslist(N1, L).
qsort([X|L], R, R0) :-
partition(L, X, L1, L2),
qsort(L2, R1, R0),
qsort(L1, R, [X|R1]).
qsort([], R, R).
partition([X|L], Y, [X|L1], L2) :-
X < Y,
!,
partition(L, Y, L1, L2).
partition([X|L], Y, L1, [X|L2]) :-
partition(L, Y, L1, L2).
partition([], _, [], []).
qsort1([X|L], R, R0) :-
partition1(L, X, L1, L2),
qsort1(L2, R1, R0),
qsort1(L1, R, [X|R1]).
qsort1([], R, R).
partition1([X|L], Y, [X|L1], L2) :-
X > Y,
!,
partition(L, Y, L1, L2).
partition1([X|L], Y, L1, [X|L2]) :-
partition1(L, Y, L1, L2).
partition1([], _, [], []).
------------------------------
End of PROLOG Digest
********************