Упражнения

3.3.  Определите два предиката

четнаядлина( Список) и нечетнаядлина( Список)

таким образом, чтобы они были истинными, если их аргументом является список четной или нечетной длины соответственно. Например, список [а, b, с, d] имеет четную длину, a [a, b, c] — нечетную.

3.4.  Определите отношение

обращение( Список, ОбращенныйСписок),

которое обращает списки. Например,

обращение( [a, b, c, d], [d, c, b, a] ).

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

палиндром( Список).

Список называется палиндромом, если он читается одинаково, как слева направо, так и справа налево. Например, [м, а, д, а, м].

3.6.  Определите отношение

сдвиг( Список1, Список2)

таким образом, чтобы Список2 представлял собой Список1, "циклически сдвинутый" влево на один символ. Например,

?- сдвиг( [1, 2, 3, 4, 5], L1),

 сдвиг1( LI, L2)

дает

L1 = [2, 3, 4, 5, 1]

L2 = [3, 4, 5, 1, 2]

3.7.  Определите отношение

перевод( Список1, Список2)

для перевода списка чисел от 0 до 9 в список соответствующих слов. Например,

перевод( [3, 5, 1, 3], [три, пять, один, три] )

Используйте в качестве вспомогательных следующие отношения:

означает( 0, нуль).

означает( 1, один).

означает( 2, два).

...

3.8.  Определите отношение

подмножество( Множество, Подмножество)

где Множество и Подмножество — два списка представляющие два множества. Желательно иметь возможность использовать это отношение не только для проверки включения одного множества в другое, но и для порождения всех возможных подмножеств заданного множества. Например:

?-  подмножество( [а, b, с], S ).

S = [a, b, c];

S = [b, c];

S = [c];

S = [];

S = [a, c];

S = [a];

...

3.9.  Определите отношение

разбиениесписка( Список, Список1, Список2)

так, чтобы оно распределяло элементы списка между двумя списками Список1 и Список2 и чтобы эти списки были примерно одинаковой длины. Например:

разбиениесписка( [а, b, с, d, e], [a, с, e], [b, d]).

3.10.  Перепишите программу об обезьяне и бананах из главы 2 таким образом, чтобы отношение

можетзавладеть( Состояние, Действия)

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

Действия = [ перейти( дверь, окно),

             передвинуть( окно, середина),

             залезть, схватить ]

3.11.  Определите отношение

линеаризация( Список, ЛинейныйСписок)

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

?- линеаризация( [а, d, [с, d], [], [[[e]]], f, L).

L = [a, b, c, d, e, f]

3.3. Операторная запись (нотация)

В математике мы привыкли записывать выражения в таком виде:

2*a + b*с

где + и * — это операторы, а 2 , а , b , с  — аргументы. В частности, + и * называют инфиксными операторами, поскольку они появляются между своими аргументами. Такие выражения могут быть представлены в виде деревьев, как это сделано на рис. 3.6, и записаны как прологовские термы с + и * в качестве функторов:

+( *( 2, а), *( b, с) )

Рис. 3.6.  Представление выражения 2*а+b*с  в виде дерева.

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

2*а + b*с

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

Выражения рассматриваются Прологом просто как дополнительный способ записи, при котором не вводятся какие-либо новые принципы структуризации объектов данных. Если мы напишем а + b,  Пролог поймет эту запись, как если бы написали +(а, b). Для того, чтобы Пролог правильно воспринимал выражения типа а + b*с, он должен знать, что * связывает сильнее, чем +. Будем говорить, что + имеет более низкий приоритет, чем *. Поэтому верная интерпретация выражений зависит от приоритетов операторов. Например, выражение а + b*с, в принципе можно понимать и как

+( а, *( b, с) )

и как

*( +( а, b), с)

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

Программист может вводить свои собственные операторы. Так, например, можно определить атомы имеет и поддерживает в качестве инфиксных операторов, а затем записывать в программе факты вида:

питер имеет информацию.

пол поддерживает стол.

Эти факты в точности эквивалентны следующим:

имеет( питер, информацию).

поддерживает( пол, стол).

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

:- op( 600, xfx, имеет).

Такая запись сообщит Прологу, что мы хотим использовать "имеет" в качестве оператора с приоритетом 600 и типом 'xfx', обозначающий одну из разновидностей инфиксного оператора. Форма спецификатора 'xfx' указывает на то, что оператор, обозначенный через 'f', располагается между аргументами, обозначенными через 'х'.

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

Имена операторов это атомы, а их приоритеты — точнее, номера их приоритетов — должны находиться в некотором диапазоне, зависящем от реализации. Мы будем считать, что этот диапазон располагается в пределах от 1 до 1200.¹

Существуют три группы типов операторов, обозначаемые спецификаторами, похожими на xfx:

(1) инфиксные операторы трех типов:

xfx xfy yfx

(2) префиксные операторы двух типов:

fx fy

(3) постфиксные операторы двух типов:

хf yf

Спецификаторы выбраны с таким расчетом, чтобы нагляднее отразить структуру выражения, в котором 'f' соответствует оператору, а 'x' и 'y' представляют его аргументы. Расположение 'f' между аргументами указывает на то, что оператор инфиксный. Префиксные и постфиксные спецификаторы содержат только один аргумент, который, соответственно, либо следует за оператором, либо предшествует ему.

Рис. op3.7.   Две интерпретации выражения а-b-с в предположении, что '-' имеет приоритет 500. Если тип '-' есть yfx, то интерпретация 2 неверна, так как приоритет b-с не выше, чем приоритет '-'.

Между 'x' и 'y' есть разница. Для ее объяснения нам потребуется ввести понятие приоритета аргумента . Если аргумент заключен в скобки или не имеет структуры (является простым объектом), тогда его приоритет равен 0; если же он структурный, тогда его приоритет равен приоритету его главного функтора. С помощью 'x' обозначается аргумент, чей приоритет должен быть строго выше приоритета оператора (т e. его номер строго меньше номера приоритета оператора); с помощью 'y' обозначается аргумент, чей приоритет выше или равен приоритету оператора.

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

а-b-с

обычно понимается как (а-b)-с, а не как а-(b-с). Чтобы обеспечить такую обычную интерпретацию, оператор '-' следует определять как yfx. На рис. 3.7 показано, каким образом исключается вторая интерпретация.

В качестве еще одного примера рассмотрим оператор not (логическое отрицание "не"). Если not oпределён как fy, тогда выражение

 not not p

записано верно; однако, если not определен как fx, оно некорректно, потому что аргументом первого not является структура not p, которая имеет тот же приоритет, что и not. В этом случае выражение следует писать со скобками:

not (not p)

:- op( 1200, xfx, ':-').

:- op( 1200, fx, [:-, ?-] ).

:- op( 1100, xfy, ';').

:- op( 1000, xfy, ',').

:- op( 700, xfx, [=, is, <, >, =<, >=, ==, =\=, \==, =:=]).

:- op( 500, yfx, [+, -] ).

:- op( 500, fx, [+, -, not] ).

:- op( 400, yfx, [*, /, div] ).

:- op( 300, xfx, mod).

Рис. 3.8.  Множество предопределенных операторов.

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

~ (А & В) <===> ~А v ~В

Приведем один из способов записи этого утверждения в виде прологовского предложения:

эквивалентно( not( и( А, В)), или( not( A, not( B))).

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

:- op( 800, xfx, <===>).

:- op( 700, xfy, v).

:- op( 600, хfу, &).

:- op( 500, fy, ~).

Теперь правило де Моргана можно записать в виде следующего факта:

~(А & В) <===> ~А v ~В.

В соответствии с нашими определениями операторов этот терм понимается так, как это показано на рис. 3.9.

Рис. 3.9.  Интерпретация терма ~(А & В) <===> ~A v ~В

Подытожим:

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

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

• Программист может вводить свои собственные операторы. Каждый оператор определяется своим именем, приоритетом и типом.

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

• Тип оператора зависит от двух условий: (1) его расположения относительно своих аргументов, (2) приоритета его аргументов по сравнению с его собственным. В спецификаторах, таких, как xfy, x обозначает аргумент, чей номер приоритета строго меньше номера приоритета оператора; y — аргумент с номером приоритета, меньшим или равным номеру приоритета оператора.