Упражнения

5.4.  Даны два списка Кандидаты и Исключенные, напишите последовательность целей (используя принадлежит и not), которая, при помощи перебора, найдет все элементы списка Кандидаты, не входящие в список Исключенные.

5.5.  Определите отношение, выполняющее вычитание множеств:

разность( Множ1, Множ2, Разность)

где все три множества представлены в виде списков. Например,

разность( [a, b, c, d], [b, d, e, f], [a, c] )

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

5.6.  Определите предикат

унифицируемые( Спис1, Терм, Спис2)

где Спис2 — список всех элементов Спис1, которые сопоставимы с Терм'ом, но не конкретизируются таким сопоставлением. Например:

?-  унифицируемые( [X, b, t( Y)], t( a), Спис).

Спис = [ X, t( Y)]

Заметьте, что и X и Y должны остаться неконкретизированными, хотя сопоставление с t( a) вызывает их конкретизацию. Указание: используйте not ( Терм1 = Терм2). Если цель Терм1 = Терм2 будет успешна, то not( Терм1 = Tepм2) потерпит неудачу и получившаяся конкретизация будет отменена!

5.4. Трудности с отсечением и отрицанием

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

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

(2) Применяя отсечение, можно описать взаимоисключающие правила, поэтому есть возможность запрограммировать утверждение:

 если условие P, то решение Q,

 иначе решение R

Выразительность языка при этом повышается.

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

p :- а, b.

p :- с.

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

 p <===> (а & b) U с

Можно поменять порядок этих двух предложений, но декларативный смысл останется прежним. Введем теперь отсечение

p :- а, !, b.

p :- с.

Декларативный смысл станет теперь таким:

 p <===> (а & b) U ( ~а & с)

Если предложения поменять местами

p :- с.

p :- а, !, b.

декларативный смысл станет таким:

 p <===> с U ( а & b)

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

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

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

Отсечение часто используется в комбинации со специальной целью fail. В частности, мы определили отрицание какой-либо цели (not), как ее неуспех. Определенное таким образом отрицание представляет собой просто особый (более ограниченный) вид отсечения. Из соображений ясности программ мы предпочтем пользоваться not вместо комбинации отсечение — неуспех (всюду, где возможно), поскольку отрицание является понятием более высокого уровня, чем отсечение — неуспех .

Следует заметить, что использование оператора not также может приводить к неприятностям, и его тоже следует применять с осторожностью. Трудность заключается в том, что тот оператор not, который был нами определен, не в точности соответствует отрицанию в математике. Если спросить

?- not человек( мэри).

система, возможно, ответит "да". Не следует понимать этот ответ как "мэри не человек". Что в действительности пролог-система хочет сказать своим "да", так это то, что программе не хватает информации для доказательства утверждения "Мэри — человек". Это происходит потому, что при обработке цели not система не пытается доказать истинность этой цели впрямую. Вместо этого она пытается доказать противоположное утверждение, и если такое противоположное утверждение доказать не удается, система считает, что цель not — успешна. Такое рассуждение основано на так называемом предположении о замкнутости мира . В соответствии с этим постулатом мир замкнут в том смысле, что все в нем существующее либо указано в программе, либо может быть из нее выведено. И наоборот — если что-либо не содержится в программе (или не может быть из нее выведено), то оно не истинно и, следовательно, истинно его отрицание. Это обстоятельство требует особого внимания, поскольку мы обычно не считаем мир замкнутым: если в программе явно не сказано, что

человек( мэри)

то мы этим обычно вовсе не хотим сказать, что Мэри не человек.

Дальнейшее изучение опасных аспектов использования not проведем на таком примере:

r( а).

g( b).

p( X) :- not r( X).

Если спросить теперь

?-  g( X), p( X).

система ответит

X = b

Если же задать тот же вопрос, но в такой форме

?- p( X), g( X).

система ответит

nо        (нет)

Читателю предлагается проследить работу программы по шагам, чтобы понять, почему получились разные ответы. Основная разница между вопросами состоит в том, что переменная X к моменту вычисления p( X) в первом случае была уже конкретизирована, в то время как во втором случае этого еще не произошло.

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

Резюме

• Отсечение подавляет перебор. Его применяют как для повышения эффективности программ, так и для повышения выразительности языка.

• Эффективность повышается путем прямого указания (при помощи отсечения) пролог — системе не проверять альтернативы, про которые нам заранее известно, что они должны потерпеть неудачу.

• Отсечение дает возможность сформулировать взаимно исключающие утверждения при помощи правил вида:

 если Условие то Утверждение1 иначе Утверждение2

• Отсечение дает возможность ввести отрицание как неуспех : not( Цель) определяется через неуспех цели Цель.

• Иногда бывают полезными две особые цели true и fail. true — всегда успешна и fail — всегда терпит неудачу.

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

• Оператор not, определенный через неуспех, не полностью соответствует отрицанию в математической логике. Поэтому not тоже нужно применять с осторожностью.

Литература

Различать "зеленые и "красные" отсечения предложил ван Эмден (1982).

van Emden M. (1982). Red and green cuts. Logic Programming Newsletter:  2 .

Глава 6

Ввод и вывод

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

6.1. Связь с файлами

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

• ввод данных в форме, отличной от вопроса - например, в виде предложений, написанных на английском языке

• вывод информации в произвольном формате

• обмен информацией с произвольным файлом, а не только с пользовательским терминалом

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

Рис. 6. 1.   Связь между пролог-программой и различными файлами.

Рассмотрим вначале вопрос о том, как обмениваться информацией с файлами, а затем — как можно вводить и выводить данные в разных форматах.

На рис. 6.1 показана общая ситуация, в которой пролог-программа взаимодействует с несколькими файлами. Она может, в принципе, считывать данные из нескольких входных файлов, называемых также входными потоками , и выводить данные в несколько выходных файлов, называемых выходными потоками . Информация, поступающая с пользовательского терминала, рассматривается просто как еще один входной поток. Аналогично информация, выводимая на этот терминал, рассматривается как один из выходных потоков. На оба этих "псевдофайла" ссылаются с помощью имени user (пользователь). Имена остальных файлов программист должен выбирать в соответствии с правилами именования файлов, принятыми в используемой компьютерной системе.

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

see( ИмяФайла)              ( Смотри(ИмяФайла) )

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

...

see( файл1),

читать_из_файла( Информация),

see( user),                  ( user — пользователь)

...

Текущий выходной поток может быть изменен при помощи цели вида

tell( ИмяФайла)              ( сообщить( ИмяФайла) )

Следующая последовательность целей выводит некоторую информацию в файл3, а после этого перенаправляет последующий вывод обратно на терминал:

...

tell( файл3),

записать_в_файл( Информация),

tell( user),

...

Цель

seen                          ( конец чтения)

закрывает текущий входной файл. Цель

told                          ( конец записи)

закрывает текущий выходной файл.

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

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

Все файлы являются "текстовыми", т.е. файлами, состоящими из символов. Символы — это буквы, цифры и специальные знаки. О некоторых из них говорят, что они непечатаемые, поскольку, будучи выведенными на терминал, они не появляются на экране. Однако их присутствие может сказаться каким-либо другим образом, например появятся пробелы или пустые строки.

Существуют два основных способа, с помощью которых файлы рассматриваются в Прологе в зависимости от формы записанной в них информации. Один способ - рассматривать символ как основной элемент файла. Соответственно один запрос на ввод или вывод приведет к чтению или записи одного символа. Для этой цели предназначены встроенные предикаты get, get0 и put (получить, получить0 и выдать).

Другой способ рассматривать файл — считать, что в качестве основных элементов построения файла используются более крупные единицы текста. Такой естественной более крупной единицей является прологовский терм. Поэтому каждый запрос на ввод/вывод такого типа приведет к переносу целого терма из текущего входного потока или в текущий выходной поток соответственно. Предикатами для переноса термов являются предикаты read и write (читать и писать). В этом случае информация в файле должна, конечно, по форме соответствовать синтаксису термов.

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