Implement recursive unify(e1, e2) on list-form expressions with the occurs check; print the mgu of p(X,f(Y)) vs p(a,f(b)) and FAIL for p(X,X) vs p(a,b).

Answer

def is_var(x): return isinstance(x, str) and x[:1].isupper() def is_const(x): return isinstance(x, str) and not x[:1].isupper() def occurs(var, expr): if var == expr: return True if isinstance(expr, list): return any(occurs(var, e) for e in expr) return False def apply_sub(expr, sub): if isinstance(expr, list): return [apply_sub(e, sub) for e in expr] return sub.get(expr, expr) def compose(s1, s2): out = {v: apply_sub(t, s2) for v, t in s1.items()} out.update(s2) return out def unify(e1, e2): if e1 == e2: return {} if is_var(e1): return 'FAIL' if occurs(e1, e2) else {e1: e2} if is_var(e2): return 'FAIL' if occurs(e2, e1) else {e2: e1} if is_const(e1) or is_const(e2): return 'FAIL' if len(e1) != len(e2): return 'FAIL' sub = {} for a, b in zip(e1, e2): s = unify(apply_sub(a, sub), apply_sub(b, sub)) if s == 'FAIL': return 'FAIL' sub = compose(sub, s) return sub def show(sub): if sub == 'FAIL': return 'FAIL' return '{' + ', '.join(f'{k}: {v}' for k, v in sorted(sub.items())) + '}' print(show(unify(['p', 'X', ['f', 'Y']], ['p', 'a', ['f', 'b']]))) print(show(unify(['p', 'X', 'X'], ['p', 'a', 'b'])))