Xy)(xb)).

В контексте данного окружения Y должно бы быть областью определения для b, поскольку Х служит для Y, но это не так. Кроме того, Х является областью определения более чем для одной переменной. А чтобы получить окружение вида ((Х Y) (Y b)) вместо переменной в сопоставлении должна участвовать её напарница по связке. Тогда переменная Х окажется связанной с Y, и при сравнении третьих элементов сопоставляться с b будет напарница Х по связке, в результате чего получится (Y b).

Первый предприни­маемый шаг - замещение X и Y их связками. Затем, если X ока­зывается переменной, она сцепляется с Y и такая пара добавляется к окружению О, которое и возвращается в виде результата. Если же переменной будет Y, то X и Y меняются местами, поскольку первым элементом пары в связке должна быть переменная. Далее пара помещается в О. Несмотря на то что в реализации списков не используется механизм ячеек связи, при следующем обращении к лиспоподобному слову СПИСОК(X Y) создается ячейка связи (или точечная пара) с головой X и хвостом Y.

Предполагается, что переменные могут входить в предикат только один раз.

В том случае, когда Х и Y не являются переменными, осуществляется их проверка на атомы. Если один из них ока­зывается атомом, то другой должен быть сопоставимым атомом. Иначе не получится новой связки, поскольку нет переменной b, если же выясняется, что X и Y - не атомы и не переменные, зна­чит, они должны быть списками, используемыми для представле­ния предикатов. В такой ситуации унификация вызывается ре­курсивно по первым двум элементам списков X и Y.

Быстрота выполнения алгоритмов унификации достигается ценой следующих огра­ничений:

1. Переменная должна входить в некоторую функцию не более одного раза.

2. Переменная не должна входить в функцию, по отношению к которой сама является границей.

Как правило, эти ограничения не столь существенны, но позволяют достигать большой скорости вычислений.

Существует еще одно осложнение, с которым необходимо счи­таться при включении алгоритма унификации в поиск: на различных уровнях дерева вывода для одних и тех же имен пе­ременных связки будут различными. Отслеживать различные связки одной и той же переменной можно двумя способами - копированием структур и совместным использованием структур. Первый способ состоитв копировании граничных выражений на каждом уровне вывода, второй - в том, что каждая переменная в связке снабжается индексом, отражающим уровень. При таком подходе связки имеют вид (Xi), где i - индекс X, отражающий номер использования X.

1. Рассмотрим программу, используя внешние цели:

written_by(X, Y).

Когда Visual Prolog пытается выполнить цель written_by(X, Y), он проверяет все written_by предложения в программе для соответствия. Для поиска соответствия параметров X и Y с параметрами, найденными в каждом written_by предложении, Visual Prolog перебирает все предложения с начала до конца. Когда находится предложение, соответствующие цели, Пролог связывает значения со свободными переменными так, чтобы цель и предложение были идентичны; говорят, что цель унифицирована с предложением. Эту операцию нахождения соответствий называют унификацией.