Программирование в Логике. Чанышев О.Г. - 28 стр.

UptoLike

ВУЗ: 

ОмГУ | Омск

Составители: 

Рубрика: 

55
5.2. Внутренние дела Пролога
Работу пролог-программы можно сравнить с поиском пути
на разветвленной дороге (коей является последовательность и се-
мантика утверждений), когда известны все или часть характери-
стик искомого объекта, но не неизвестно, где следует свернуть.
Если у нескольких объектов совпадают характеристики, то будет
найден первый объект на этой дороге.
Пролог ищет "первую исти-
ну".
Бэктрекинг. Основной механизм доказательства теоремы –
это бэктрекинг, или перебор с возвратами. Возвраты (или отка-
ты) происходят в случае неистинности рассматриваемого утвер-
ждения (цели, подцели, вспомогательной теоремы) с целью нахо-
ждения иного пути (способа доказательства).
Как Пролог убеждается, что цель достигнута?
Основной механизм проверки истинности утверждений
за-
ключается в подстановке.
Подстановкой, или конкретизацией, Θ называется всякое
множество присваиваний вида x = t, где x – переменная, а t – терм.
Каждой переменной присваевается только одно значение.
Результат подстановки иногда называют подстановочным
примером. Если применение подстановки Θ к утверждениям (вы-
ражениям) E1, E2 дает один и тот же подстановочный пример, та-
кая подстановка называется унификатором, сам
подстановочный
процесс – унификацией, а утверждения (предикаты) – унифици-
руемыми.
5.3. Что такое шаблоны?
Шаблон на поток параметров – шаблон, формирующийся в
зависимости от того, используются ли параметры в предикатном
вызове для ввода данных (т. е. данные известны), либо для вывода
данных (т. е. данные неизвестны).
Поточный вариант: если предикат ассоциируется с несколь-
кими различными шаблонами, то для каждого шаблона будет реа-
лизована самостоятельная внутренняя программа, относящаяся к
56
данному предикату. Эти различные действия получили название
поточных вариантов предиката.
Множественные описания предиката: отдельно взятый пре-
дикат может иметь несколько описаний, каждое из которых со-
держит различные доменовые спецификации для аргумента (аргу-
ментов) релевантного отношения.
5.4. Управление поиском
Для того чтобы найти все возможные решения, а также для
управления поиском, существует
ограниченный, но мощный на-
бор явных средств:
1. Операторы сравнения и альтернатива (или: or|;).
2. Множественность правил для одного предиката.
3. Встроенные предикаты fail, (cut | !), которые порождают
искусственный откат и отсечение возможных переборов соответ-
ственно.
4. Рекурсия, или самовызов, предиката.
5. Комбинация отсечения и искусственного отката.
6. Использование предиката типа repeat. repeat:-repeat
Пример
predicates
search2
search
search3
f1(integer,string)
f2(integer,string)
goal
% Если search3 успешен, то write
и выполнить search,
% search2, иначе выполнить search, search2.
% используется метод ОО – отсечение и откат.
search3,!,write("Два первых факта удовлетворяют усло-
вию"),fail;
search,
search2;
!.
clauses 
     5.2. Внутренние дела Пролога                                    данному предикату. Эти различные действия получили название
                                                                     поточных вариантов предиката.
      Работу пролог-программы можно сравнить с поиском пути
                                                                          Множественные описания предиката: отдельно взятый пре-
на разветвленной дороге (коей является последовательность и се-
                                                                     дикат может иметь несколько описаний, каждое из которых со-
мантика утверждений), когда известны все или часть характери-
                                                                     держит различные доменовые спецификации для аргумента (аргу-
стик искомого объекта, но не неизвестно, где следует свернуть.
                                                                     ментов) релевантного отношения.
Если у нескольких объектов совпадают характеристики, то будет
найден первый объект на этой дороге. Пролог ищет "первую исти-
                                                                          5.4. Управление поиском
ну".
      Бэктрекинг. Основной механизм доказательства теоремы –               Для того чтобы найти все возможные решения, а также для
это бэктрекинг, или перебор с возвратами. Возвраты (или отка-        управления поиском, существует ограниченный, но мощный на-
ты) происходят в случае неистинности рассматриваемого утвер-         бор явных средств:
ждения (цели, подцели, вспомогательной теоремы) с целью нахо-              1. Операторы сравнения и альтернатива (или: or|;).
ждения иного пути (способа доказательства).                                2. Множественность правил для одного предиката.
                                                                           3. Встроенные предикаты fail, (cut | !), которые порождают
        Как Пролог убеждается, что цель достигнута?                  искусственный откат и отсечение возможных переборов соответ-
                                                                     ственно.
      Основной механизм проверки истинности утверждений за-                4. Рекурсия, или самовызов, предиката.
ключается в подстановке.                                                   5. Комбинация отсечения и искусственного отката.
      Подстановкой, или конкретизацией, Θ называется всякое                6. Использование предиката типа repeat. repeat:-repeat
множество присваиваний вида x = t, где x – переменная, а t – терм.
Каждой переменной присваевается только одно значение.                     Пример
      Результат подстановки иногда называют подстановочным                predicates
примером. Если применение подстановки Θ к утверждениям (вы-               search2
ражениям) E1, E2 дает один и тот же подстановочный пример, та-            search
кая подстановка называется унификатором, сам подстановочный               search3
процесс – унификацией, а утверждения (предикаты) – унифици-               f1(integer,string)
руемыми.                                                                  f2(integer,string)
                                                                          goal
     5.3. Что такое шаблоны?                                              % Если search3 успешен, то write и выполнить search,
                                                                          % search2, иначе выполнить search, search2.
      Шаблон на поток параметров – шаблон, формирующийся в
                                                                          % используется метод ОО – отсечение и откат.
зависимости от того, используются ли параметры в предикатном
                                                                          search3,!,write("Два первых факта удовлетворяют усло-
вызове для ввода данных (т. е. данные известны), либо для вывода
                                                                     вию"),fail;
данных (т. е. данные неизвестны).
                                                                          search,
      Поточный вариант: если предикат ассоциируется с несколь-
                                                                          search2;
кими различными шаблонами, то для каждого шаблона будет реа-
                                                                          !.
лизована самостоятельная внутренняя программа, относящаяся к
                                                                          clauses

                               55                                                                   56

Страницы