Предотвращение поиска с возвратом к предыдущей подцели в правиле

rl:-
  а, b,
       !,
         c.

Такая запись является способом сообщить Прологу о том, что вас удовлетворит первое решение, найденное им для подцелей a и b. Имея возможность найти множественные решения при обращении к с путем поиска с возвратом, Пролог при этом не может произнести откат (поиск с возвратом) через отсечение и найти альтернативное решение для обращений а и b. Он также не может возвратиться к другому предложению, определяющему предикат r1.

46. Детерминизм и отсечение.

В Прологе существует директива компилятора check_determ. Если вставить эту директиву в самое начало программы, то Пролог будет выдавать предупреждение в случае обнаружения недетерминированных предложений в процессе компиляции.

Вы можете превратить недетерминированные предложения в детерминированные, вставляя отсечения в тело правил, определяющих данный предикат. Например, помещение отсечений в предложения, определяющие предикат friend, делает этот предикат детерминированным, поскольку в данном случае обращение к friend может возвратить одно и только одно решение.

47. Управление поиском решений.

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

Пролог обеспечивает два инструментальных средства, которые дают возможность управлять механизмом поиска с возвратом: предикат fail, который используется для инициализации поиска с возвратом, и cut или отсечение (обозначается!) - для запрета возможности возврата.

Использование предиката fail

Пролог начинает поиск с возвратом, когда вызов завершается неудачно. В определенных ситуациях бывает необходимо инициализировать выполнение поиска с возвратом, чтобы найти другие решения. Пролог поддерживает специальный предикат fail, вызывающий неуспешное завершение, и, следовательно, инициализирует возврат. Действие предиката fail равносильно эффекту от сравнения 2 = 3 или другой невозможной подцели.

Пусть необходимо найти все решения цели father (X,Y). Цель можно записать как

father (X,Y).

Пролог найдет все решения цели father (X,Y) и отобразит значения всех переменных следующим образом:

X=leonard,Y=katherine

X=carl,Y=jason

X=carl,Y=marilyn

Нo если вы скомпилируете эту программу и запустите ее (командой меню Run), то Пролог найдет только первое подходящее решение для father (X,Y). После того как целевое утверждение, определенное в разделе goal, выполнено впервые, ничто не говорит Прологу о необходимости продолжения поиска с возвратом. Поэтому обращение к father приведет только к одному решению. Как же найти все возможные решения? Предикат everybody в программе использует fail для поддержки поиска с возвратом.

48. Рекурсия и рекурсивные объекты.

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

Список, содержащий числа 1, 2 и 3, записывается так:

[1,2,3]

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

[ dog, cat, canary ]

Объявление списков

Чтобы объявить домен для списка целых, надо использовать декларацию домена, такую как:

domains integerlist=integer*

Символ (*) означает "список чего-либо"; таким образом, integer* означает "список целых".

Обратите внимание, что у слова "список" нет специального значения в Прологе. С тем же успехом можно назвать список "занзибаром". Именно обозначение * (а не название), говорит компилятору, что это список.

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

elementlist=elements* % функторы здесь i,r и s elements=i(integer); r(real); s(symbol)

Головы и хвосты

Список является рекурсивным составным объектом. Он состоит из двух частей - головы, которая является первым элементом, и хвоста, который является списком, включающим все последующие элементы. Хвост списка - всегда список, голова списка - всегда элемент. Например:

голова [а,b,с] есть а хвост [а,b,с] есть [b,с]

Что происходит, когда вы доходите до одноэлементного списка? Ответ таков:

голова[с] есть с    хвост [с] есть [ ]

49. Работа со списками.

В Прологе есть способ явно отделить голову от хвоста. Вместо разделения элементов запятыми, это можно сделать вертикальной чертой "|". Например:

[а,b,с] эквивалентно [а| [b,с]]

и, продолжая процесс,

[а| [b,с]] эквивалентно [а | [b| [с]]], что эквивалентно [а| [b| [с| [] ]]]

Можно использовать оба вида разделителей в одном и том же списке при условии, что вертикальная черта есть последний разделитель. При желании можно набрать [а,b,с,d] как [a,b| [c,d]]. В таблице 1 вы найдете другие примеры.

Таблица 1. Головы и хвосты списков
Список	Голова	Хвост
['a','b','с']	'a'	['b','с']
['a']	'a'	[] % пустой список
[ ]	Не определена	Не определен
[[1,2,3], [2,3,4],[ ]]	[1,2,3]	[[2,3,4],[ ]]

В таблице 2 приведены несколько примеров на присвоение в списках.

Таблица 2. Присвоение в списках
Список 1	Список 2	Присвоение переменным
[X,Y,Z]	[эгберт, ест,мороженое]	Х=эгберг, У=ест, Z=мороженое
[7]	[X | Y]	Х=7,Y=[ ]
[1,2,3,4]	[X, Y | Z]	X=1, Y = 2, Z = [3,4]
[1,2]	[3|X]	fail % неудача

50. Использование списков.

Список является рекурсивной составной структурой данных, поэтому нужны алгоритмы для его обработки. Главный способ обработки списка - это просмотр и обработка каждого его элемента, пока не будет достигнут конец.

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

Печать списков

Если нужно напечатать элементы списка, это делается так, как показано ниже.

domains

list = integer* % Или любой тип, какой вы хотите

predicates

write_a_list(list)

clauses

write_a_list([]). % Если список пустой - ничего не делать

write_a_list([H |T]):- % Присвоить Н-голова,Т-хвост, затем...

write(H),nl,

write_a_list(T).

goal

write_a_list([1,2,3]).

 

Вот два целевых утверждения write_a_list, описанные на обычном языке:

Печатать пустой список - значит ничего не делать.
     Иначе, печатать список - означает печатать его голову (которая является одним элементом), затем печатать его хвост (список).

 

Подсчет элементов списка

Рассмотрим, как можно определить число элементов в списке. Что такое длина списка? Вот простое логическое определение:

Длина [ ] - 0.

Длина любого другого списка - 1 плюс длина его хвоста.

Можно ли применить это? В Прологе - да. Для этого нужны два предложения.

domains

list = integer* % или любой другой тип

predicates

length_of(list,integer)

clauses

length_of([],0).

length_of([_|T],L):-

    length_of(T,TailLength),

    L=TailLength + 1.

51. Основные предикаты управления строкой.

Предикаты, описываемые на этом шаге, являются основой обработки в Прологе; они служат для нескольких целей:

· разделение строки на подстроки и лексемы;

· построение строки из определенных подстрок и лексем;

· проверка, состоит ли строка из определенных подстрок или лексем;

· возврат лексемы или списка лексем из данной строки;

· проверка или определение длины строки;

· создание пустой строки определенной длины;

· проверка, является ли строка термином, определенным в Прологе;

· форматирование переменного числа аргументов в строковую переменную.

Предикат frontchar/3

Предикат frontchar действует согласно равенству:

String1 = объединение Char и String2

Предикат fronttoken/3

Предикат fronttoken выполняет три взаимосвязанные функции, в зависимости от типа аргументов, который используется для обращения к нему.

fronttoken(String1,Token,Rest) %(i, о, о) (i,i, о) (i,o,i) (i,i,i) (o,i,i)

Предикат frontstr/4

Предикат frontstr расщепляет String1 на две части. Синтаксис предиката:

frontstr(NumberOfChars,String1,StartStr,EndStr) % (i,i,o,o)

где StartStr содержит NumberOfChars первых символов из String1, a EndStr содержит остаток. При обращении к frontstr первые два параметра должны быть связанными, а последние два - свободными.

Предикат concat/3

Предикат concat устанавливает, что строка String3 является результатом сцепления String1 и String2. Он имеет форму:

concat(String1,Sring2,String3) % (i,i,o), (i,o,i), (o,i,i), (i,i,i)

Предикат isname/1

Предикат isname проверяет, является ли аргумент допустимым именем согласно синтаксису Пролога, и имеет формат:

isname(String) % (i)

Имя начинается с буквы алфавита или символа подчеркивания, за которым следует любое число букв, цифр и символов подчеркивания. Предыдущие и последующие пробелы игнорируются.

Предикат format/*

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

format(OutputString,FormatString,Arg1,Arg2,Arg3,..., ArgN) %(o,i,i,i,...,i)

52. Преобразования типов.

На этом шаге мы рассмотрим стандартные предикаты, предназначенные для преобразования типов. Это предикаты char_int, str_char, str_int, str_real, upper_lower.

Предикат char_int/2

Предикат char_int преобразует символ в целое число или целое в символ и имеет формат:

char_int(Char,Integer) % (i,o), (o,i), (i,i)

Предикат str_char/2

Предикат str_char преобразует строку, содержащую один и только один символ, в символ или символ в строку из одного символа; предикат имеет формат:

str_char(String,Char) % (i,o), (o,i), (i,i)

Предикат str_int/2

Предикат str_int преобразует строку, содержащую целое число, в его текстовое представление и имеет формат:

str_int(String,Integer) % (i,o), (o,i), (i,i)

Предикат str_real/2

Предикат str_real преобразует строку в вещественное число или вещественное число в строку и имеет формат:

str_real(String,Real) % (i,o), (o,i), (i,i)

Предикат upper_lower/2

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

upper_lower(Upper,Lower) % (i,o), (o,i), (i,i)

53. Множества.

Список, который не содержит повторных вхождений элементов называется множеством.

Начнем с написания предиката, превращающего произвольный список во множество. Для этого нужно удалить все повторные вхождения элементов. При этом мы воспользуемся предикатом delete_all. Предикат будет иметь два аргумента: первый – исходный список (возможно, содержащий повторные вхождения элементов), второй – выходной (то, что остается от первого аргумента после удаления повторных вхождений элементов).

Предикат будет реализован посредством рекурсии. Базисом рекурсии является очевидный факт: в пустом списке никакой элемент не встречается более одного раза.

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

Закодируем наши рассуждения.

list_set([],[]). /* пустой список является списком

в нашем понимании */

list_set ([H|T],[H|T1]):–

delete_all(H,T,T2),

/* T2 — результат удаления

вхождений первого элемента

исходного списка H из хвоста T */

list_set (T2,T1).

/* T1 — результат удаления повторных вхождений элементов из списка T2*/

Например, если применить этот предикат к списку [1,2,1,2,3, 2,1], то результатом будет список [1,2,3].

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

54. Раздел предложений.

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

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

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

55. Раздел предикатов.

Если в разделе clauses программы на Прологе вы описали собственный предикат, то вы обязаны объявить его в разделе predicates (предикатов); в противном случае Пролог не поймет, о чем вы ему "говорите". В результате объявления предиката вы сообщаете, к каким доменам (типам) принадлежат аргументы этого предиката.

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