Prolog

Этот пример поучителен, поскольку мы не можем легко запрограммировать "недублирующее добавление", не используя отсечения или какой-либо другой конструкции, полученной из него. Если мы уберем отсечение в только что рассмотренной программе, то отношение добавить будет добавлять дубликаты элементов, уже имеющихся в списке. Например:

        ?-  добавить( a, [a, b, c], L),

        L = [а, b, с]

        L = [а, а, b, с]

Поэтому отсечение требуется здесь для правильного определения отношения, а не только для повышения эффективности. Этот момент иллюстрируется также и следующим примером.

5. 2. 4.    Задача классификации объектов

Предположим, что у нас есть база данных, содержащая результаты теннисных партий, сыгранных членами некоторого клуба. Подбор пар противников для каждой партия не подчинялся какой-либо системе, просто каждый игрок встречался с несколькими противниками. Результаты представлены в программе в виде фактов, таких как

        победил( том, джон).

        победил( энн, том).

        победил( пат, джим).

Мы хотим определить

        отношение класс( Игрок, Категория)

которое распределяет игроков по категориям. У нас будет три категории:

    победитель - любой игрок, победивший во всех сыгранных им играх

    боец - любой игрок, в некоторых играх победивший, а в некоторых проигравший

    спортсмен - любой игрок, проигравший во всех сыгранных им партиях

Например, если в нашем распоряжении есть лишь приведенные выше результаты, то ясно, что Энн и Пат - победители. Том - боец и Джим - спортсмен.

Легко сформулировать правило для бойца:

    Х - боец, если существует некоторый Y, такой, что Х победил

        Y, и

        существует некоторый Z, такой, что Z победил

        X.

Теперь правило для победителя:

    Х - победитель, если

        X победил некоторого Y и

        Х не был побежден никем.

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

        Если Х победил кого-либо и Х был кем-то

                     побежден,

        то Х - боец,

        иначе,    если Х победил кого-либо,

                       то Х - победитель,

                       иначе,     если Х был кем-то побежден,

                                      то Х - спортсмен.

Такую формулировку можно сразу перевести на Пролог. Взаимные исключения трех альтернативных категорий выражаются при помощи отсечений:

        класс( X, боец) :-

             победил( X, _ ),

             победил( _, X),  !.

        класс( X, победитель) :-

             победил( X, _ ),  !.

        класс( X, спортсмен) :-

             победил( _, X).

Заметьте, что использование отсечения в предложении для категории победитель не обязательно, что связано с особенностями наших трех классов.

Упражнения

5. 1.    Пусть есть программа:

        р( 1).

        р( 2) :-  !.

        р( 3).

Напишите все ответы пролог-системы на следующие вопросы:

    (a)        ?-  р( X).

    (b)        ?-  р( X),   p(Y).

    (c)        ?-  р( X),   !,  p(Y).

Посмотреть ответ

5. 2.    Следующие отношения распределяют числа на три класса - положительные, нуль и отрицательные:

        класс( Число, положительные) :- Число > 0.

        класс( 0, нуль).

        класс( Число, отрицательные) :- Число < 0.

Сделайте эту процедуру более эффективной при помощи отсечений.

Посмотреть ответ

5. 3.    Определите процедуру

        разбить( Числа, Положительные, Отрицательные)

которая разбивает список чисел на два списка: список, содержащий положительные числа (и нуль), и список отрицательных чисел. Например,

        разбить( [3, -1, 0, 5, -2], [3, 0, 5], [-1, -2] )

Предложите две версии: одну с отсечением, другую - без.

Посмотреть ответ

Назад | Содержание | Вперёд

Назад | Содержание | Вперёд

5. 3.    Отрицание как неуспех

"Мэри любит всех животных, кроме змей". Как выразить это на Прологе? Одну часть этого утверждения выразить легко: "Мэри любит всякого X, если Х - животное". На Прологе это записывается так:

        любит( мэри, X) :- животное ( X).

Но нужно исключить змей. Это можно сделать, использовав другую формулировку:

        Если Х - змея, то "Мэри любит X" - не есть

              истина,

        иначе, если Х - животное, то Мэри любит X

.