Date: Nov 20, 2012 3:59 AM
Author: Graham Cooper
Subject: PROLOG ENGINES ARE REALLLLLLY SLOW!   ((SQL-UNIFY))

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