Premium
Correcting a widespread error in unification algorithms
Author(s) -
Norvig Peter
Publication year - 1991
Publication title -
software: practice and experience
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.437
H-Index - 70
eISSN - 1097-024X
pISSN - 0038-0644
DOI - 10.1002/spe.4380210208
Subject(s) - unification , computer science , variable (mathematics) , implementation , algorithm , logic programming , error detection and correction , theoretical computer science , programming language , mathematics , mathematical analysis
The unification of two patterns both containing variables is a ubiquitous operation in logic programming and in many artificial intelligence applications. Thus, many texts present unification algorithms. Unfortunately, at least seven of these presentations are incorrect. The common error occurs when logic variables are represented as binding lists; implementations that destructively update variable cells do not manifest the error. This note gives the examples that uncover the error and presents a correction.