**Things to remember when reading this pseudocode/algorithm:**

- This UNIFY procedure is not the same
as the one you have been asked to implement in Unify.java

- This should be implmented as a private
function possibly in Unify.java with a name of your choice (say
myUnify()).

- E1 and E2 here are more like lists.
For example knows(John, ?X) would be (knows John ?X). Since you only unify when
the predicates match you can choose to not have predicates. Hence using list of
elements returned by the getElements() function of
the AtomicExpression class can be possibly passed to
this procedure UNIFY.

- From an implementation perspective you
may want to implement myUnify(List l1, List l2,
VariableSubstitutions v), so that you can put substitutions to the same VariableSubstitutions
object even when making recursive calls.

Recursive Procedure **UNIFY**(E1, E2)

1 **if** either E1 or E2 is an atom (that is, a predicate symbol, a function symbol, a constant symbol, a negation symbol or a variable), interchange the arguments E1 and E2 (is necessary) so that E1 is an atom, and **do:**

2 **begin**

3 **if** E1 and E2 are identical, **return** NIL

4 **if** E1 is a variable, **do:**

5 **begin**

6 **if** E1 occurs in E2, **return** FAIL

7 **return** {E1/E2}

8 **end**

9 **if** E2 is a variable, **return** {E1/E2}

10 **return** FAIL

11 **end**

12 F1 <- the first element of E1, T1 <- the rest of E1

13 F2 <- the first element of E2, T2 <- the rest of E2

14 Z1 <- **UNIFY**(F1,F2)

15 **if** Z1 = FAIL, **return** FAIL

16 G1 <- result of applying Z1 to T1

17 G2 <- result of applying Z1 to T2

18 Z2 <- **UNIFY**(G1, G2)

19 **if** Z2 = FAIL, **return** FAIL

20 **return** the composition of Z1 and Z2