Unification is a two-way, generalized form of pattern matching between two terms. If you have two terms (say A and B), and an environemt E, then unifying A and B means comparing A and B (filling in the results in the environment) in such a way that, after unification, substituting what was found in A and B shoud give an equal term. I think it originated in logic programming, so I'll give some examples to clarify this explanation (I use Smalltalk comments, and variables are denoted with question marks):
1. A = ?var "a variable", B = john "a constant" E = [] "an empty environment"
unifying A and B will give an environment E = [?var -> john], where ?var is bound to john. substituting the environment E in A yields: john. substituting the environment E in B also yiels: john.
2. A = foo(bar, fi(john)) B = foo(?one, fi(?two)) E = []
will yield E = [?one -> bar,?two->john]
3. A = foo(?one, fi(john)) B = foo(bar, fo(?two))
will yield the same as above. Note however that the pattern matching happens in two ways: bindings for variables are found in such a way as to making the terms equal after substitution, regardless where they occur.
More information about unification (including algorythms) can be found in most Logic Programming or Prolog books. Since I implemented a logic programming languages, we implemented some of these (which is simple to do).
Thanks, Mark. I'll dig into it. Perhaps there will be something about unification. I've never heard of that term before.
I'll attempt a definition: Unification is the process of mapping two forms (e.g., equations) onto one another such that variables (in the form) are set to appropriate values and constraints are maintained. The process may involve backtracking, and can also end in failure (if no match is possible).
I did some web-hunting and this page seems like a reasonable intro to unification:
http://www.ccs.neu.edu/home/arthur/unif.html
I first learned about it reading Patrick Winston's first book on Lisp -- I remember typing in the code and poking at it forever trying to figure out how it was working. I think that the best description of the algorithm, though, is in Brian Harvey's "Computer Science Logo Style" series (Volume 3, I think). (In general, next to "Structure and Interpretation of Computer Programs," Harvey's books are my favorite CS texts.)
Mark
Mark Guzdial : Georgia Tech : College of Computing : Atlanta, GA 30332-0280 Associate Professor - Learning Sciences & Technologies. Collaborative Software Lab - http://coweb.cc.gatech.edu/csl/ (404) 894-5618 : Fax (404) 894-0673 : guzdial@cc.gatech.edu http://www.cc.gatech.edu/gvu/people/Faculty/Mark.Guzdial.html
-- Roel Wuyts Programming Technology Lab rwuyts@vub.ac.be Vrije Universiteit Brussel http://prog.vub.ac.be/~rwuyts Webmaster of European Smalltalk User Group: www.esug.org
squeak-dev@lists.squeakfoundation.org