Search All of the Math Forum:

Views expressed in these public forums are not endorsed by NCTM or The Math Forum.

Topic: PROLOG ENGINES ARE REALLLLLLY SLOW! ((SQL-UNIFY))
Replies: 5   Last Post: Nov 20, 2012 4:40 PM

 Messages: [ Previous | Next ]
 Graham Cooper Posts: 4,495 Registered: 5/20/10
PROLOG ENGINES ARE REALLLLLLY SLOW! ((SQL-UNIFY))
Posted: Nov 20, 2012 3:59 AM

It's a simple algorithm to program,
a simple problem to solve!

f(a,X) <=> f(Q,g) ?

Can these two TREES? be made equivalent?

f(a,g) !!

Haha!

X=g
Q=a

------------

But examine a BIGGER NESTED ATOMIC PREDICATE!

f(A,b(c,d), e(F,g(H,I,j(K,l),m,N),o,p(A,d,F)))).

AND

f(z, Q , e(l(m,n), g(h,i,J,m,w),o,P)).

I'll tell you I've been programming exactly this for 5 months!

It is a debuggers dream if you like bugs!

ALL THE UNIFY(F1,F2) ALGORITHMS ARE RECURSIVE!

1st you unify f(.....) to f(.....)
then 1 argument at a time....
A to z
b(c,d) to Q
....

then some of those terms are predicates that have to be unified
FURTHER!

A lot of variable renaming conventions, trial and error,
backtracking... very tricky and particular code covering dozens of
potential matching scenerios!

----------------

OK here is how it SHOULD BE DONE!

Each term in the predicate is given a REFERENCE NUMBER!

f(A,b(c,d), e(F,g(H,I,j(K,l),m,N),o,p(A,d,F)))).

OK, see that g(H,I).

that 'I" might be ANYTHING, it's a capital VARIABLE.

But it's reference number is:

REF 333

1 2 3
f A e

1 2 3
e F g

1 2 3
g H I

I is at position 333!

------------------

Now all facts, rules and Queries fit into a simple SQL TABLE!

A PROLOG FACT

vert ( pnt( X,Y ) pnt( X,Z ) )

TPRO
ID REF FIELD TYP
=================
21 1 vert H
21 2 pnt P
21 3 pnt P
21 21 X V
21 22 Y V
21 31 X V
21 32 Z V

A PROLOG QUERY

?- vert ( pnt( 1,2 ) pnt( 1,4 ) )

TTAILS
ID REF FIELD TYP
=================
1 1 vert H
1 2 pnt P
1 3 pnt P
1 21 1 T
1 22 2 T
1 31 1 T
1 32 4 T

THIS 1 LINE OF SQL WILL DO 100 LINES OF UNIFY RECURSION!

The ORDER IN WHICH YOU WORK OUT THE TERMS is IRRELEVANT!
No need to do a recursive descent match by match!

SQL-UNIFY

SELECT * FROM TTAILS, TPRO
WHERE TTAILS.REF = TPRO.REF
AND TTAILS.FIELD = TPRO.FIELD
GROUP BY COUNT(ID)
ORDER BY ID DESC

This will put all the MAXIMUM TERMS MATCHED RESULTS
at the top of the Query Result, and UNIFY just has to allocate
variables to terms, then recurse the tail facts of any matched rules.

Slight drawback is program order is lost using the fastest match
method, but PROLOG is overused as a simple FETCH cycle for 3GL style
coding.

Herc

--
www.microPROLOG.com
if( if(t(S),f(R)) , if(t(R),f(S)) ).
if it's sunny then it's not raining
ergo
if it's raining then it's not sunny

Date Subject Author
11/20/12 Graham Cooper
11/20/12 Jan Burse
11/20/12 Ulrich Neumerkel
11/20/12 Graham Cooper
11/20/12 Graham Cooper
11/20/12 Graham Cooper