Prolog Without Terms

Appeared in Volume 6/2, May 1993

csa09@keele.ac.uk
Paul Singleton
4th December 1992

Is it plausible to regard Prolog as a product of (at least) two independent concepts: the search strategy, and an abstract data type (first order terms plus the operation of unification)?

Could we replace terms with some other ADT, as long as we replace unification with an operation which is:

associative	(A*B)*C = A*(B*C)
symmetric	 A*B	= B*A
idempotent	 A*A	= A

I am toying with time-qualified data, in which each fact or rule is qualified by a set of time-points (or time-intervals: I don't say which, in the (probably futile) hope of avoiding philosophical arguments about the nature of time). Inference is readily meta-programmed by unifying the heads and subgoals of the facts and rules in the usual way, and by intersecting their associated sets of time-points (an empty set prompts failure).

It occurred to me (and probably to others years ago) that what I am doing with the time-point sets is analogous to unification.

Or am I re-inventing elementary constraint programming?

zs@munta.cs.mu.OZ.AU
Zoltan Somogyi
7th December 1992

Your intuition is right; this kind of thing has been investigated, although I am unaware of any temporal database applications. See the following references:

Joxan Jaffar, Jean-Louis Lassez, Michael J. Maher, A LP language scheme, In LP: relations, functions, and equations, D DeGroot, G Lindstrom (eds.), Prentice-Hall, 1985, pp.441-467

Joxan Jaffar, Jean-Louis Lassez, Michael J. Maher, Prolog II as an instance of the LP language scheme, In Preprints of the Workshop on Foundations of Deductive Databases and LP, Washington, D.C., August 1986, J Minker (ed.), pp.689-711

Joxan Jaffar, Jean-Louis Lassez, From unification to constraints, In Proc. of the 6th LP Conf., Tokyo, Japan, June 1987, K. Furukawa, H. Tanaka, T. Fujisaki (eds.), LNCS 315, Springer-Verlag, pp.1-18

miller@cs.rochester.edu
4th December 1992

Essentially, what you are trying to do has been explored in the TEMPOS system. The problem with respecifying unification as I understand your description is that you are destructively changing the time terms themselves, instead of only variables.

If you are interested in a first-order logic language extended with temporal representations (intervals: James Allen's logic); you might want to read more about TIMELOGIC and TEMPOS (and RHET).

There are several relevant TRs available. The list is periodically updated. Send mail to peg@cs.rochester.edu for a recent list. Many of these are available on this FTP server in ftp://cs.rochester.edu/pub/papers/ai/ so you might look there first!

RHET 20.0 is a Knowledge Representation system based on concepts proved with HORNE, and follow James Allen's design for KR in particular, see his book with Pelavin and Kautz). It includes 2 major modes for representing knowledge (as Horn Clauses or as frames), which are interchangable; a type subsystem for typed and type restricted objects (including variables); E-unification; negation; forward and backward chaining; complete proofs (prove, disprove, find the KB inconsistent, or claim a goal is neither provable nor disprovable); contextual reasoning; truth maintenance; intelligent backtracking; full LISP compatibility (can call or be called by LISP); upward compatible with HORNE; Allen & Koomen's TEMPOS time interval reasoning subsystem; frames with KL-1 type features; a separate subsystem providing user-interface facilities, and a ZMACS interface on the lispms.

See TR 326 for a detailed description.

Contact:

Peg Meeker
Computer Science Dept.
Univ. of Rochester
Rochester, NY 14627, USA
Email: peg@cs.rochester.edu