AI: Unification

Implement the matching step at the heart of Prolog and type inference.

What to build

A program that finds the most general unifier of two first-order terms.

Requirements

  • Variables start with an uppercase letter; constants and function names start with a lowercase letter; a compound term is name(arg, …). Unify left to right: follow existing bindings first; if both sides are the same, succeed; if the left is a variable, bind it to the right (when both are variables, the left one is bound to the right one); else if the right is a variable, bind it to the left; compound terms unify if they have the same name and number of arguments and their arguments unify in order. A variable may not be bound to a term containing it.
  • Print VAR = TERM for each variable that received a binding, sorted by name, with every binding applied fully and no spaces in terms; print no bindings if the terms are already identical, or fail.

Input

Two lines: the two terms.

Output

The bindings, no bindings or fail.

Constraints

Each term has at most 60 characters.

Example

Input:

knows(john, X)
knows(Y, mother(Y))

Output:

X = mother(john)
Y = john

Why it works

Each step either finds the two terms already equal, makes them equal by binding a variable, or splits the problem into arguments, so the result is the most general substitution that makes them identical.

Examples

Example 1 · Input
knows(john, X)
knows(Y, mother(Y))
Expected output
X = mother(john)
Y = john
Example 2 · Input
f(X, X)
f(a, b)
Expected output
fail

Prompts inside input() are ignored when checking, so input("n: ") is fine.

Hints

Hint 1

Represent a term as a string (a variable or constant) or a tuple (functor, arguments…); follow a variable's binding before comparing it.

Hint 2

Before binding a variable to a term, check that the variable does not occur inside that term.

Solution

Show one correct solution (try it yourself first)
import re


def parse(text):
    tokens = re.findall(r"[A-Za-z_]\w*|[(),]", text)
    pos = 0

    def term():
        nonlocal pos
        name = tokens[pos]
        pos += 1
        if pos < len(tokens) and tokens[pos] == "(":
            pos += 1
            args = [term()]
            while tokens[pos] == ",":
                pos += 1
                args.append(term())
            pos += 1
            return (name, *args)
        return name

    return term()


def is_var(t):
    return isinstance(t, str) and t[0].isupper()


def walk(t, s):
    while is_var(t) and t in s:
        t = s[t]
    return t


def occurs(v, t, s):
    t = walk(t, s)
    if t == v:
        return True
    return isinstance(t, tuple) and any(occurs(v, arg, s) for arg in t[1:])


def unify(a, b, s):
    a, b = walk(a, s), walk(b, s)
    if a == b:
        return s
    if is_var(a):
        return None if occurs(a, b, s) else {**s, a: b}
    if is_var(b):
        return None if occurs(b, a, s) else {**s, b: a}
    if isinstance(a, tuple) and isinstance(b, tuple) and a[0] == b[0] and len(a) == len(b):
        for x, y in zip(a[1:], b[1:]):
            s = unify(x, y, s)
            if s is None:
                return None
        return s
    return None


def show(t, s):
    t = walk(t, s)
    if isinstance(t, tuple):
        return t[0] + "(" + ",".join(show(arg, s) for arg in t[1:]) + ")"
    return t


result = unify(parse(input()), parse(input()), {})
if result is None:
    print("fail")
elif not result:
    print("no bindings")
else:
    for var in sorted(result):
        print(f"{var} = {show(var, result)}")

Lesson: Inference: chaining, resolution and unification →