I am currently trying to unify a list of lisp forms against a list of
patterns, and it is not turning out to be as simple as I thought. (I can't
quite seem to keep track of the recursion in my head right...)
This is the problem:
Say I have a list of forms,
((foo x1 x2)
(bar x2 y)
(blah x1 y))
and I have a list of patterns...
((bar ?a ?b)
(blah ?c ?b)
(foo ?c ?a))
The lists can be arbitrary. I need to find a single set of bindings that
will allow every form in the first list to match with some pattern in the
second list. The match has to be one-to-one between the two lists. In this
case, the single set of bindings would be ((?a . x2) (?b . y) (?c . x1)).
I already have a unifier, and I only need the bindings in the end, and no
information on what pattern matched with what form.
Any ideas would be appreciated. A solution of course would be the best.
Thanks!
Sunil Mishra
Open a copy of Abelson & Sussman (the only really elegant book on
computer science I've seen) and look up "logic programming" in the
index. Translate their page or so of Scheme code into Common Lisp
(doesn't that make you feel great?). Tell your advisor that you
worked for weeks on this...
--
-- Philip Greenspun
-------------------------------------------------------------
MIT Department of Electrical Engineering and Computer Science
545 Technology Square, Rm 433, Cambridge, MA 02139, (617) 253-8574
Personal Web URL: http://www-swiss.ai.mit.edu/~philg/philg.html
summer address: PO Box 952, Los Alamos, NM 87544 (505) 665-0131
An approach of extending List with the WAM unification primitives
is presented in:
G. Attardi, M. Gaspari, F. Saracco, "Interoperability of AI Languages",
In Proceedings of ECAI 90.
The unification primitives described in the paper are availiable in ECL
from ftp.di.unipi.it /pub/lang/lisp. See also the Lisp FAQ for ECL.
Mauro