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 at cc.gatech.edu
> http://www.cc.gatech.edu/gvu/people/Faculty/Mark.Guzdial.html
>


--
Roel Wuyts                    Programming Technology Lab
rwuyts at vub.ac.be              Vrije Universiteit Brussel
http://prog.vub.ac.be/~rwuyts
Webmaster of European Smalltalk User Group: www.esug.org