Как работает интерпретатор пролога?

Процесс нахождения решения в Прологе заключается в сопоставлении предиката цели с предикатами базы знаний. Этот процесс называется унификацией. Пусть Пролог-системе предъявлена цель из предыдущего подраздела (мы хотим найти, чьей внучкой является Кристина):

parent (X, kristina), parent (Y, X).

Пролог выделяет из нее первую подцель parent (X, kristina) и начинает сопоставлять ее с базой знаний (проводить унификацию). База знаний повторена ниже.

parent (boris, alia).

parent (bedros, filipp).

parent (edmuntas, kristina).

parent (alia, kristina).

parent (kristina, denis).

Вначале сопоставляются первый предикат и подцель:

parent (boris, alia) и parent (X, kristina)

Первый аргумент boris сопоставляется с переменной X.

Следует иметь в виду, что в Прологе различаются состояния переменных free (свободные) и bound (связанные). Если обе переменные связаны, то при унификации происходит их сравнение. Если одна из них свободна, то происходит присвоение. Переприсвоение значений переменным не допускается. Это существенно отличает Пролог от прочих языков.

Таким образом, переменной X, которая пока является свободной, присваивается значение boris. После этого унифицируются вторые аргументы, alia и kristina. Поскольку это константы, и alia не равно kristina, то унификация предиката parent (boris, alia) и подцели parent (X, kristina) заканчивается неудачей (fail).

Поскольку в базе знаний несколько экземпляров предиката parent, такой предикат называется неоднозначным (поп- derministic). Если предикат один, то он называется однозначным (deterministic).

В случае неоднозначного предиката после неудачи выполняется откат — переход к следующему экземпляру предиката. При этом отменяется также присвоение значение переменным, если таковое имело место. Затем выполняется унификация предикатов

parent (bedros, filipp) и parent (X, kristina)

Очевидно, что результат унификации будет тот же, неудача (fail). При откате на следующий предикат parent (edmuntas, kristina) картина будет иная: X присвоится значение edmuntas, а сопоставление вторых аргументов будет также успешным, так как kristina = kristina. Таким образом, первая подцель окажется выполненной. Пролог запоминает, какой экземпляр предиката сработал и устанавливает на следующий предикат указатель отката:

parent (boris, alia), parent (bedros, filipp). parent (edmuntas, kristina).

> parent (alia, kristina). parent (kristina, denis).

после чего перейдет ко второй подцели parent (Y, X), где X = edmuntas, т. е. Пролог ставит себе такую подцель:

parent (Y, edmuntas).

В поисках родителя Эдмунтаса Пролог снова начинает унифицировать этот предикат с начала базы знаний, начиная с parent (boris, alia). Нетрудно видеть, что на этот раз перебор всех предикатов закончится неудачей, т. е. подцель

parent (Y, edmuntas)

не дала положительного решения. В этом случае Пролог откатывается к предыдущей подцели (продвигается назад по списку подцелей) и пытается найти альтернативное решение для parent (X, kristina). При этом X опять становится свободной переменной, а Пролог возвращается к точке отката:

parent (boris, alia), parent (bedros, filipp). parent (edmuntas, kristina).

> parent (alia, kristina). parent (kristina, denis).

то есть к предикату parent (alia, kristina), сопоставляя его с подцелью parent (X, kristina).

Теперь X присваивается значение alia, указатель отката устанавливается на предикат parent (kristina, denis) и опять выполняется переход к следующей подцели parent (Y, X), где X = alia. Пролог снова начинает унификацию подцели parent (Y, alia) с базой знаний, начиная с первого предиката. В первом предикате происходит унификация константы boris и свободной переменной Y. Происходит присвоение Y = boris, затем сопоставляются вторые аргументы. Так как alia = alia, сопоставление завершается успешно.

Таким образом, решение найдено: Кристина является внучкой Бориса. Заметим, что неудача, которая постигла нас в поисках деда Кристины по отцовской линии, связана только с неполнотой базы знаний.

Итак, интерпретатор Пролога автоматически выполняет поиск решения. Механизм поиска реализован с помощью отката после неудачи. Откат происходит на следующий экземпляр неоднозначного предиката. Выполнение программы на Прологе (резолюция цели) заключается в унификации цели с базой знаний.

 
Посмотреть оригинал
< Пред   СОДЕРЖАНИЕ   ОРИГИНАЛ     След >