PROLOG-REQUEST@SU-SCORE.ARPA (Chuck Restivo, The Moderator) (06/18/86)
PROLOG Digest Thursday, 19 Jun 1986 Volume 4 : Issue 23
Today's Topics:
Implementation - DFID & Assert & LIPS
----------------------------------------------------------------------
Date: Tue, 17 Jun 86 9:24:00 BST
From: William Clocksin <wfc%computer-lab.cambridge@Cs.Ucl>
Subject: DFID
Several correspondents have discussed DFID and have
suggested some connections with parallel processing of
Prolog. I have been working on a method, which although
not DFID, comes close to what people are discussing. A
few weeks ago a colleague and I decided to write it up;
I attach the Abstract, and we have submitted the paper
for publication.
The multiprocessor design is called the "DelPhi" machine,
because it works by generating oracles. By the way, we
did this work before reading the DIFD paper in AI journal,
so we shall need to tidy up any possible correspondences
between DIFD and the DelPhi Machine.
A Method for Efficiently Executing Horn Clause Programs
Using Multiple Processors
W F Clocksin and H Alshawi
Computer Laboratory, University of Cambridge
28 May 1986
Abstract:
Previous investigations have suggested the use of communicating
multiprocessors for executing logic programs. However, this
strategy lacks efficiency due to competition for memory and
communication bandwidth, and this problem has been largely
neglected. In this paper we propose a realistic model for
executing logic programs with low overhead on multiple
processors. Our proposal does not involve shared memory or
copying computation state between processors. The model
organises computations over the nondeterministic proof tree
so that different processors explore unique deterministic
computation paths independently. We discuss certain
advantages of this approach not enjoyed by other
approaches.
------------------------------
Date: 12 Jun 86 05:16:04 GMT
From: !watmath!utzoo!utcs!mnetor!lsuc!dave@ucbvax.berkeley.edu
Subject: "assert" considered harmful?
Jamie Andrews writes:
>
> It should be of little concern to applications programmers
> that these features destroy the declarative reading of the
> program, unless they have to prove to their bosses that
> their applications are rigorously correct.
Interesting issue. What happens if I succeed in designing a
tool which can be used for corporate tax planning, and I
want to make it a commercial product? Should it be "provably"
correct before lawyers use it?
What I've done with the problem, incidentally, is do some
initial "setup" work which analyses all of the relationships
stated in the facts and asserts the things it determines to
be true. So, for example, I have the definition of control
(>50% of voting power, etc.) in a predicate called
controls_rule, and the predicate "controls" either exists
as a stated fact (set up by the user) or is asserted at
setup time. Thereafter all tests refer simply to "controls".
Same thing for "related_rule" and "related", which
incidentally solves the thorny problem of circularity caused
by definitions which define related taxpayers in terms of
other related taxpayers - I simply call the setup routine
enough times to make sure all derivative relationships are
asserted. (Hope that isn't too obscure.)
Of course, the thing will get a lot more difficult when I
properly implement time, which is crucial to the system.
But I think it's still reasonable to determine what each
time interval is that's relevant, and make the assertions
relative to those time intervals.
As long as I limit my assertions by restricting the time
interval, then I don't really have to worry about the
difference between "assert" and "assume" which was
mentioned by Anand Rao, do I?
-- Dave Sherman
The Law Society of Upper Canada
------------------------------
Date: 13 Jun 86 18:54:12 GMT
From: Micha Meier
Subject: LIPS
Some people seem to have a wrong idea about the speed
of the programs compiled by the up-to-date Prolog
compilers. The following might help to determine the
performance of a good Prolog compiler on a given machine
(measuring naive reverse). The C program simulates the
output of the compiler using many optimizations (not all)
and with no restrictions on Prolog syntax. If your system
is better, congratulations; if it is significantly slower,
you can certainly find a system for your machine which has
a similar performance.
-- Micha
ECRC, D-8000 Muenchen 81,
W. Germany
----cut here----
/*
Measure possible LIPS on the naive reverse example.
LENGTH is the maximal length of the list to reverse
which also determines the stack size (b).
*/
#include <stdio.h>
#include <sys/types.h>
#include <sys/times.h>
#define HZ 60.0 /* might need to change this */
#define LENGTH 300
#define a (LENGTH+2)*(LENGTH+2)
#define b a + 6*LENGTH
#define c ((unsigned) 0)
#define d ((unsigned) 0x10000000)
#define e ((unsigned) 0x20000000)
#define f(X) ((unsigned) (X & 0xf0000000))
#define g(X) ((unsigned) (X & 0xfffffff))
#define h(X) ((unsigned) (X | 0x30000000))
#define i(X) ((unsigned) (X | d))
#define j(k, l) {l = k; while (f(l) == c) {l = m[l];}}
#define n(k, o, l) {l = k; if ((o = f(l)) == c){l = m[l]; o = f(l);} l = g(l);}
#define p(q) if (q < t || (q < u && q > a)) r[v++] = q;
#define s if (w > b) {fprintf(stderr,"something went wrong\n"); exit(2);}
#define z if (y > a) {fprintf(stderr,"something went wrong\n"); exit(2);}
unsigned m[b], r[1];
main()
{
register unsigned aa, y, ab, ac, ae, x, ag, t,af, u, w, v, ad;
int ah, length, t0;
struct tms Time;
float Lips;
y = 1, t = 0, u = af = 0, w = a;
printf("List length: ");
scanf("%d", &length);
if (length > LENGTH) {
fprintf(stderr, "\nSorry, this is too much\n");
exit(2);
}
for (ah = 1; ah < length; ah++) {
m[y++] = h(ah), m[y] = i(y+1), y++;
}
m[y++] = h(ah), m[y++] = e;
m[0] = 0, x = i(1), ag = 0;
times(&Time);
t0 = Time.tms_utime;
goto aj;
ai: times(&Time);
t0 = Time.tms_utime - t0;
if (t0 == 0) {
fprintf(stderr, "The time is too short
to measure, sorry\n");
exit(1);
}
Lips = ((length * (length + 3))/2 + 1) / (t0/HZ);
printf("\nLips = %.1f\n", Lips);
exit(0);
aj: n(x, ab, aa);
if (ab != d) {
n(ag, ab, aa);
p(aa);
m[aa] = e;
}
else {
m[w] = af, af = w++, m[w++] = ad, w += 3;
s;
m[af+4] = aa++, x = aa++, m[af+3] = ag;
ab = af+2, m[ab] = ag = ab;
goto aj;
}
ak: ag = i(y);
j(m[af+4], aa);
m[y++] = aa, m[y++] = e;
z;
if (u < af) {
j(m[af+2], aa);
if (f(aa) == c) {} else x = aa;
}
ac = m[af+3], ad = m[af+1], af = m[af];
if (af > u) w = af; else w = u;
for(;;) {
n(x, ab, aa);
if (ab != d) {
n(ac, ab, aa);
p(aa);
m[aa] = ag;
if (af == 0) goto ai; else goto ak;
}
ae = m[aa++], x = m[aa++];
n(ac, ab, aa);
p(aa);
m[aa] = i(y), m[y++] = ae, m[y] = y, ac = y++;
z;
}
}
------------------------------
End of PROLOG Digest
********************PROLOG-REQUEST@SU-SCORE.ARPA (Chuck Restivo, The Moderator) (06/19/86)
PROLOG Digest Thursday, 19 Jun 1986 Volume 4 : Issue 23
Today's Topics:
DFID
"assert" considered harmful?
LIPS
----------------------------------------------------------------------
Date: Tue, 17 Jun 86 9:24:00 BST
From: William Clocksin <wfc%computer-lab.cambridge@Cs.Ucl>
Subject: DFID
Several correspondents have discussed DFID and have
suggested some connections with parallel processing of
Prolog. I have been working on a method, which although
not DFID, comes close to what people are discussing. A
few weeks ago a colleague and I decided to write it up;
I attach the Abstract, and we have submitted the paper
for publication.
The multiprocessor design is called the "DelPhi" machine,
because it works by generating oracles. By the way, we
did this work before reading the DIFD paper in AI journal,
so we shall need to tidy up any possible correspondences
between DIFD and the DelPhi Machine.
A Method for Efficiently Executing Horn Clause Programs
Using Multiple Processors
W F Clocksin and H Alshawi
Computer Laboratory, University of Cambridge
28 May 1986
Abstract:
Previous investigations have suggested the use of communicating
multiprocessors for executing logic programs. However, this
strategy lacks efficiency due to competition for memory and
communication bandwidth, and this problem has been largely
neglected. In this paper we propose a realistic model for
executing logic programs with low overhead on multiple
processors. Our proposal does not involve shared memory or
copying computation state between processors. The model
organises computations over the nondeterministic proof tree
so that different processors explore unique deterministic
computation paths independently. We discuss certain
advantages of this approach not enjoyed by other
approaches.
------------------------------
Date: 12 Jun 86 05:16:04 GMT
From: !watmath!utzoo!utcs!mnetor!lsuc!dave@ucbvax.berkeley.edu
Subject: "assert" considered harmful?
Jamie Andrews writes:
>
> It should be of little concern to applications programmers
> that these features destroy the declarative reading of the
> program, unless they have to prove to their bosses that
> their applications are rigorously correct.
Interesting issue. What happens if I succeed in designing a
tool which can be used for corporate tax planning, and I
want to make it a commercial product? Should it be "provably"
correct before lawyers use it?
What I've done with the problem, incidentally, is do some
initial "setup" work which analyses all of the relationships
stated in the facts and asserts the things it determines to
be true. So, for example, I have the definition of control
(>50% of voting power, etc.) in a predicate called
controls_rule, and the predicate "controls" either exists
as a stated fact (set up by the user) or is asserted at
setup time. Thereafter all tests refer simply to "controls".
Same thing for "related_rule" and "related", which
incidentally solves the thorny problem of circularity caused
by definitions which define related taxpayers in terms of
other related taxpayers - I simply call the setup routine
enough times to make sure all derivative relationships are
asserted. (Hope that isn't too obscure.)
Of course, the thing will get a lot more difficult when I
properly implement time, which is crucial to the system.
But I think it's still reasonable to determine what each
time interval is that's relevant, and make the assertions
relative to those time intervals.
As long as I limit my assertions by restricting the time
interval, then I don't really have to worry about the
difference between "assert" and "assume" which was
mentioned by Anand Rao, do I?
-- Dave Sherman
The Law Society of Upper Canada
------------------------------
Date: 13 Jun 86 18:54:12 GMT
From: Micha Meier
Subject: LIPS
Some people seem to have a wrong idea about the speed
of the programs compiled by the up-to-date Prolog
compilers. The following might help to determine the
performance of a good Prolog compiler on a given machine
(measuring naive reverse). The C program simulates the
output of the compiler using many optimizations (not all)
and with no restrictions on Prolog syntax. If your system
is better, congratulations; if it is significantly slower,
you can certainly find a system for your machine which has
a similar performance.
-- Micha
ECRC, D-8000 Muenchen 81,
W. Germany
----cut here----
/*
Measure possible LIPS on the naive reverse example.
LENGTH is the maximal length of the list to reverse
which also determines the stack size (b).
*/
#include <stdio.h>
#include <sys/types.h>
#include <sys/times.h>
#define HZ 60.0 /* might need to change this */
#define LENGTH 300
#define a (LENGTH+2)*(LENGTH+2)
#define b a + 6*LENGTH
#define c ((unsigned) 0)
#define d ((unsigned) 0x10000000)
#define e ((unsigned) 0x20000000)
#define f(X) ((unsigned) (X & 0xf0000000))
#define g(X) ((unsigned) (X & 0xfffffff))
#define h(X) ((unsigned) (X | 0x30000000))
#define i(X) ((unsigned) (X | d))
#define j(k, l) {l = k; while (f(l) == c) {l = m[l];}}
#define n(k, o, l) {l = k; if ((o = f(l)) == c)
{l = m[l]; o = f(l);} l = g(l);}
#define p(q) if (q < t || (q < u && q > a)) r[v++] = q;
#define s if (w > b) {fprintf(stderr,
"something went wrong\n"); exit(2);}
#define z if (y > a) {fprintf(stderr,
"something went wrong\n"); exit(2);}
unsigned m[b], r[1];
main()
{
register unsigned aa, y, ab, ac, ae, x, ag, t,
af, u, w, v, ad;
int ah, length, t0;
struct tms Time;
float Lips;
y = 1, t = 0, u = af = 0, w = a;
printf("List length: ");
scanf("%d", &length);
if (length > LENGTH) {
fprintf(stderr, "\nSorry, this is too much\n");
exit(2);
}
for (ah = 1; ah < length; ah++) {
m[y++] = h(ah), m[y] = i(y+1), y++;
}
m[y++] = h(ah), m[y++] = e;
m[0] = 0, x = i(1), ag = 0;
times(&Time);
t0 = Time.tms_utime;
goto aj;
ai: times(&Time);
t0 = Time.tms_utime - t0;
if (t0 == 0) {
fprintf(stderr, "The time is too short
to measure, sorry\n");
exit(1);
}
Lips = ((length * (length + 3))/2 + 1) / (t0/HZ);
printf("\nLips = %.1f\n", Lips);
exit(0);
aj: n(x, ab, aa);
if (ab != d) {
n(ag, ab, aa);
p(aa);
m[aa] = e;
}
else {
m[w] = af, af = w++, m[w++] = ad, w += 3;
s;
m[af+4] = aa++, x = aa++, m[af+3] = ag;
ab = af+2, m[ab] = ag = ab;
goto aj;
}
ak: ag = i(y);
j(m[af+4], aa);
m[y++] = aa, m[y++] = e;
z;
if (u < af) {
j(m[af+2], aa);
if (f(aa) == c) {} else x = aa;
}
ac = m[af+3], ad = m[af+1], af = m[af];
if (af > u) w = af; else w = u;
for(;;) {
n(x, ab, aa);
if (ab != d) {
n(ac, ab, aa);
p(aa);
m[aa] = ag;
if (af == 0) goto ai; else goto ak;
}
ae = m[aa++], x = m[aa++];
n(ac, ab, aa);
p(aa);
m[aa] = i(y), m[y++] = ae, m[y] = y, ac = y++;
z;
}
}
------------------------------
End of PROLOG Digest
********************PROLOG-REQUEST@SU-SCORE.ARPA (Chuck Restivo, The Moderator) (06/19/86)
PROLOG Digest Thursday, 19 Jun 1986 Volume 4 : Issue 23
Today's Topics:
Implementation - DFID & Assert & LIPS
----------------------------------------------------------------------
Date: Tue, 17 Jun 86 9:24:00 BST
From: William Clocksin <wfc%computer-lab.cambridge@Cs.Ucl>
Subject: DFID
Several correspondents have discussed DFID and have
suggested some connections with parallel processing of
Prolog. I have been working on a method, which although
not DFID, comes close to what people are discussing. A
few weeks ago a colleague and I decided to write it up;
I attach the Abstract, and we have submitted the paper
for publication.
The multiprocessor design is called the "DelPhi" machine,
because it works by generating oracles. By the way, we
did this work before reading the DIFD paper in AI journal,
so we shall need to tidy up any possible correspondences
between DIFD and the DelPhi Machine.
A Method for Efficiently Executing Horn Clause Programs
Using Multiple Processors
W F Clocksin and H Alshawi
Computer Laboratory, University of Cambridge
28 May 1986
Abstract:
Previous investigations have suggested the use of communicating
multiprocessors for executing logic programs. However, this
strategy lacks efficiency due to competition for memory and
communication bandwidth, and this problem has been largely
neglected. In this paper we propose a realistic model for
executing logic programs with low overhead on multiple
processors. Our proposal does not involve shared memory or
copying computation state between processors. The model
organises computations over the nondeterministic proof tree
so that different processors explore unique deterministic
computation paths independently. We discuss certain
advantages of this approach not enjoyed by other
approaches.
------------------------------
Date: 12 Jun 86 05:16:04 GMT
From: !watmath!utzoo!utcs!mnetor!lsuc!dave@ucbvax.berkeley.edu
Subject: "assert" considered harmful?
Jamie Andrews writes:
>
> It should be of little concern to applications programmers
> that these features destroy the declarative reading of the
> program, unless they have to prove to their bosses that
> their applications are rigorously correct.
Interesting issue. What happens if I succeed in designing a
tool which can be used for corporate tax planning, and I
want to make it a commercial product? Should it be "provably"
correct before lawyers use it?
What I've done with the problem, incidentally, is do some
initial "setup" work which analyses all of the relationships
stated in the facts and asserts the things it determines to
be true. So, for example, I have the definition of control
(>50% of voting power, etc.) in a predicate called
controls_rule, and the predicate "controls" either exists
as a stated fact (set up by the user) or is asserted at
setup time. Thereafter all tests refer simply to "controls".
Same thing for "related_rule" and "related", which
incidentally solves the thorny problem of circularity caused
by definitions which define related taxpayers in terms of
other related taxpayers - I simply call the setup routine
enough times to make sure all derivative relationships are
asserted. (Hope that isn't too obscure.)
Of course, the thing will get a lot more difficult when I
properly implement time, which is crucial to the system.
But I think it's still reasonable to determine what each
time interval is that's relevant, and make the assertions
relative to those time intervals.
As long as I limit my assertions by restricting the time
interval, then I don't really have to worry about the
difference between "assert" and "assume" which was
mentioned by Anand Rao, do I?
-- Dave Sherman
The Law Society of Upper Canada
------------------------------
Date: 13 Jun 86 18:54:12 GMT
From: Micha Meier
Subject: LIPS
Some people seem to have a wrong idea about the speed
of the programs compiled by the up-to-date Prolog
compilers. The following might help to determine the
performance of a good Prolog compiler on a given machine
(measuring naive reverse). The C program simulates the
output of the compiler using many optimizations (not all)
and with no restrictions on Prolog syntax. If your system
is better, congratulations; if it is significantly slower,
you can certainly find a system for your machine which has
a similar performance.
-- Micha
ECRC, D-8000 Muenchen 81,
W. Germany
----cut here----
/*
Measure possible LIPS on the naive reverse example.
LENGTH is the maximal length of the list to reverse
which also determines the stack size (b).
*/
#include <stdio.h>
#include <sys/types.h>
#include <sys/times.h>
#define HZ 60.0 /* might need to change this */
#define LENGTH 300
#define a (LENGTH+2)*(LENGTH+2)
#define b a + 6*LENGTH
#define c ((unsigned) 0)
#define d ((unsigned) 0x10000000)
#define e ((unsigned) 0x20000000)
#define f(X) ((unsigned) (X & 0xf0000000))
#define g(X) ((unsigned) (X & 0xfffffff))
#define h(X) ((unsigned) (X | 0x30000000))
#define i(X) ((unsigned) (X | d))
#define j(k, l) {l = k; while (f(l) == c) {l = m[l];}}
#define n(k, o, l) {l = k; if ((o = f(l)) == c)
{l = m[l]; o = f(l);} l = g(l);}
#define p(q) if (q < t || (q < u && q > a)) r[v++] = q;
#define s if (w > b) {fprintf(stderr,
"something went wrong\n"); exit(2);}
#define z if (y > a) {fprintf(stderr,
"something went wrong\n"); exit(2);}
unsigned m[b], r[1];
main()
{
register unsigned aa, y, ab, ac, ae, x, ag, t,
af, u, w, v, ad;
int ah, length, t0;
struct tms Time;
float Lips;
y = 1, t = 0, u = af = 0, w = a;
printf("List length: ");
scanf("%d", &length);
if (length > LENGTH) {
fprintf(stderr, "\nSorry, this is too much\n");
exit(2);
}
for (ah = 1; ah < length; ah++) {
m[y++] = h(ah), m[y] = i(y+1), y++;
}
m[y++] = h(ah), m[y++] = e;
m[0] = 0, x = i(1), ag = 0;
times(&Time);
t0 = Time.tms_utime;
goto aj;
ai: times(&Time);
t0 = Time.tms_utime - t0;
if (t0 == 0) {
fprintf(stderr, "The time is too short
to measure, sorry\n");
exit(1);
}
Lips = ((length * (length + 3))/2 + 1) / (t0/HZ);
printf("\nLips = %.1f\n", Lips);
exit(0);
aj: n(x, ab, aa);
if (ab != d) {
n(ag, ab, aa);
p(aa);
m[aa] = e;
}
else {
m[w] = af, af = w++, m[w++] = ad, w += 3;
s;
m[af+4] = aa++, x = aa++, m[af+3] = ag;
ab = af+2, m[ab] = ag = ab;
goto aj;
}
ak: ag = i(y);
j(m[af+4], aa);
m[y++] = aa, m[y++] = e;
z;
if (u < af) {
j(m[af+2], aa);
if (f(aa) == c) {} else x = aa;
}
ac = m[af+3], ad = m[af+1], af = m[af];
if (af > u) w = af; else w = u;
for(;;) {
n(x, ab, aa);
if (ab != d) {
n(ac, ab, aa);
p(aa);
m[aa] = ag;
if (af == 0) goto ai; else goto ak;
}
ae = m[aa++], x = m[aa++];
n(ac, ab, aa);
p(aa);
m[aa] = i(y), m[y++] = ae, m[y] = y, ac = y++;
z;
}
}
------------------------------
End of PROLOG Digest
********************