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 = TERMfor each variable that received a binding, sorted by name, with every binding applied fully and no spaces in terms; printno bindingsif the terms are already identical, orfail.
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
knows(john, X) knows(Y, mother(Y))
X = mother(john) Y = john
f(X, X) f(a, b)
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)}")