+    сложение
        -    вычитание
        *    умножение
        /    деление
        mod     модуль, остаток от целочисленного деления

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

        ?-  Х = 1 + 2.

Пролог-система "спокойно" ответит

             Х = 1 + 2

        ?-  Х  is  1 + 2.

Вот теперь ответ будет

             Х = 3

Сложение здесь выполняется специальной процедурой, связанной с оператором   +.    Мы будем называть такие процедуры встроенными.

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

        ?- Х  is  3/2,
            Y  is  3 div 2.

ответ должен быть такой:

            Х = 1.5
            Y = 1

Левым аргументом оператора  is   является простой объект. Правый аргумент - арифметическое выражение, составленное с помощью арифметических операторов, чисел и переменных. Поскольку оператор  is   запускает арифметические вычисления, к моменту начала вычисления этой цели все ее переменные должны быть уже конкретизированы какими-либо числами. Приоритеты этих предопределенных арифметических операторов (см. рис. 3.8) выбраны с таким расчетом, чтобы операторы применялись к аргументам в том порядке, который принят в математике. Чтобы изменить обычный порядок вычислений, применяются скобки (тоже, как в математике). Заметьте, что  +,  -,  *,    /  и  div  определены, как   yfx,  что определяет порядок их выполнения слева направо. Например,

        Х  is  5 - 2 - 1

понимается как

        X  is  (5 - 2) - 1

Арифметические операции используются также и при сравнении числовых величин. Мы можем, например, проверить, что больше - 10000 или результат умножения 277 на 37, с помощью цели

        ?-  277 * 37 > 10000.
        yes             (да)

Заметьте, что точно так же, как и is,   оператор  '>'  вызывает выполнение вычислений.

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

Ниже перечислены операторы сравнения:

        Х    >     Y                    Х больше Y

        Х    <     Y                    Х меньше Y

        Х    >=     Y                  Х больше или равен Y

        Х    =<     Y                  Х меньше или равен Y

        Х    =:=     Y                 величины Х и Y совпадают (равны)

        Х    =\=     Y                 величины Х и Y не равны

Обратите внимание на разницу между операторами сравнения '=' и '=:=', например, в таких целях как X = Y и Х =:= Y. Первая цель вызовет сопоставление объектов Х и Y, и, если Х и Y сопоставимы, возможно, приведет к конкретизации каких-либо переменных в этих объектах. Никаких вычислений при этом производиться не будет. С другой стороны, Х =:= Y вызовет арифметическое вычисление и не может привести к конкретизации переменных. Это различие можно проиллюстрировать следующими примерами:

        ?-    1 + 2 =:= 2 + 1.
        yes

        >-    1 + 2 = 2 + 1.
        no

        ?-    1 + А = В + 2.
        А = 2
        В = 1

Давайте рассмотрим использование арифметических операций на двух простых примерах. В первом примере ищется наибольший общий делитель; во втором - определяется количество элементов в некотором списке.

Если заданы два целых числа Х и Y, то их наибольший общий делитель Д можно найти, руководствуясь следующими тремя правилами:

(1)        Если Х и Y равны, то Д равен X.

На примере легко убедиться, что эти правила действительно позволяют найти наибольший общий делитель. Выбрав, скажем, Х = 20 и Y = 25, мы, руководствуясь приведенными выше правилами, после серии вычитаний получим Д = 5.

Эти правила легко сформулировать в виде прологовской программы, определив трехаргументное отношение, скажем

        нод( X , Y, Д)

Тогда наши три правила можно выразить тремя предложениями так:

        нод( X, X, X).

        нод( X, Y, Д) :-
              Х < Y,
              Y1 is Y - X,
              нод( X, Y1, Д),

        нод( X, Y, Д) :-
              Y < X,
              нод( Y, X, Д).

Разумеется, с таким же успехом можно последнюю цель в третьем предложении заменить двумя:

        X1 is Х - Y,
        нод( X1, Y, Д)

        длина( Список, N)

которая будет подсчитывать элементы списка Список и конкретизировать N полученным числом. Как и раньше, когда речь шла о списках, полезно рассмотреть два случая:

(1)        Если список пуст, то его длина равна 0.

(2)        Если он не пуст, то Список = [Голова1 | Хвост] и его длина равна 1 плюс длина хвоста Хвост.

Эти два случая соответствуют следующей программе:

        длина( [ ], 0).

        длина( [ _ | Хвост], N) :-
              длина( Хвост, N1),
              N is 1 + N1.

Применить процедуру длина можно так:

        ?- длина( [a, b, [c, d], e], N).

        N = 4

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

        N is 1 + N1

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

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

        длина1( [ ], 0).

        длина1( [ _ | Хвост], N) :-
              длина1( Хвост, N1),
              N = 1 + N1.

Теперь уже цель

        ?- длина1( [a, b, [c, d], e], N).

породит ответ:

        N = 1+(1+(1+(1+0)))

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

        длина1( _ | Хвост], N) :-
              N = 1 + N1,
              длина1( Хвост, N1).

Такая версия длина1 будет давать те же результаты, что и исходная. Ее можно записать короче:

        длина1( [ _ | Хвост], 1 + N) :-
              длина1( Хвост, N).

и она и в этом случае будет давать те же результаты. С помощью длина1, впрочем, тоже можно вычислять количество элементов списка:

        ?- длина( [а, b, с], N), Длина is N.

        N = 1+(1+(l+0))
        Длина = 3

        Итак: Для выполнения арифметических действий используются встроенные процедуры. Арифметические операции необходимо явно запускать при помощи встроенной процедуры is. Встроенные процедуры связаны также с предопределенными операторами  +,  -,   *,  /,  div  и   mod. К моменту выполнения операций все их аргументы должны быть конкретизированы числами. Значения арифметических выражений можно сравнивать с помощью таких операторов, как  <,   =<  и т.д. Эти операторы вычисляют значения своих аргументов.

Две интерпретации выражения а-b-с...

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

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

        а-b-с

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

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

        not  not  р

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

        not  (not  р)

:- ор( 1200, xfx, ':-').

:- ор( 1200, fx, [:-, ?-] ).

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

:- ор( 1000, xfy, ',').

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

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

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

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

:- op( 300, xfx, mod).

Списки, операторы, арифметика

Глава 3

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

        ?- конк( L1, L2, [а, b, с] ).

        L1 = [ ]
        L2 = [а, b, c];

        L1 = [а]
        L2 = [b, с];

        L1 = [а, b]
        L2 = [c];

        L1 = [а, b, с]
        L2 = [ ];

        no             (нет)

Список  [а, b, с]  разбивается на два списка четырьмя способами, и все они были обнаружены нашей программой при помощи механизма автоматического перебора.

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

        ?- конк( До, [май | После ],
                  [янв, фев, март, апр, май, июнь,
                        июль, авг, сент, окт, ноябрь, дек]).

        До = [янв, фев, март, апр]

        После = [июнь, июль, авг, сент, окт, ноябрь, дек].

Далее мы сможем найти месяц, непосредственно предшествующий маю, и месяц, непосредственно следующий за ним, задав вопрос:

        ?- конк( _, [Месяц1, май, Месяц2 | _ ],
                   [янв, февр, март, апр, май, июнь,
                        июль, авг, сент, окт, ноябрь, дек]).

        Месяц1 = апр
        Месяц2 = июнь

Более того, мы сможем, например, удалить из некоторого списка L1 все, что следует за тремя последовательными вхождениями элемента z в L1 вместе с этими тремя z. Например, это можно сделать так:

        ?- L1 = [a, b, z, z, c, z, z, z, d, e],
            конк( L2, [z, z, z | _ ], L1).

        L1 = [a, b, z, z, c, z, z, z, d, e]
        L2 = [a, b, z, z, c]

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

    принадлежит1( X, L) :-
           конк( L1, [X | L2], L).

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

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

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

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

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

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

        :- ор( 800, xfx, <===>).

        :- ор( 700, xfy, v).

        :- ор( 600, хfу, &).

        :- ор( 500, fy, ~).

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

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

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

Некоторые операции над списками

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

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

(2)    остальная часть списка, называемая хвостом.

Например, для списка

        [ энн, теннис, том, лыжи ]

энн - это голова, а хвостом является список

        [ теннис, том, лыжи ]

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

        .( Голова, Хвост)

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

        .( энн, .( теннис, .( том, .( лыжи, [ ] ) ) ) )

На рис. 3.1 изображена соответствующая древовидная структура. Заметим, что показанный выше пример содержит пустой список [ ]. Дело в том, что самый последний хвост является одноэлементным списком:

        [ лыжи ]

Хвост этого списка пуст

        [ лыжи ] = .( лыжи, [ ] )

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

        ?-  Список1 = [а, b, с],
             Список2 = (a,  .(b,  .(c,[ ]) ) ).

        Список1 = [а, b, с]
        Список2 = [а, b, с]

        ?-  Увлечения1 = .( теннис, .(музыка, [ ] ) ),
             Увлечения2 = [лыжи, еда],
             L = [энн, Увлечения1, том, Увлечения2].

        Увлечения1 = [теннис, музыка]
        Увлечения2 = [лыжи, еда]
        L = [энн, [теннис, музыка], том, [лыжи, еда]]

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

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

        2*а  +  b*с

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

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

        +( а, *( b, с) )

и как

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

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

        питер имеет информацию.
        пол поддерживает стол.

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

        имеет( питер, информацию).
        поддерживает( пол, стол).

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

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

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

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

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

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

            xfx     xfy    yfx

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

            fx     fy

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

            хf     yf

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

Процедура принадлежит1 находит элемент в заданном

В этом предложении сказано: "X принадлежит L, если список L можно разбить на два списка таким образом, чтобы элемент Х являлся головой второго из них. Разумеется, принадлежит1 определяет то же самое отношение, что и принадлежит. Мы использовали другое имя только для того, чтобы различать таким образом две разные реализации этого отношения, Заметим, что, используя анонимную переменную, можно записать вышеприведенное предложение так:

        принадлежит1( X, L) :-
               конк( _, [X | _ ], L).

Интересно сравнить между собой эти две реализации отношения принадлежности. Принадлежит имеет довольно очевидный процедурный смысл:

    Для проверки, является ли Х элементом списка L, нужно

    (1)    сначала проверить, не совпадает ли голова списка L с X, а затем

    (2)    проверить, не принадлежит ли Х хвосту списка L.

С другой стороны, принадлежит1, наоборот, имеет очевидный декларативный смысл, но его процедурный смысл не столь очевиден.

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

        ?-  принадлежит1( b, [а, b, с] ).

На рис. 3.3 приведена эта запись. Из нее можно заключить, что принадлежит1 ведет себя точно так же, как и принадлежит. Он просматривает список элемент за элементом до тех пор, пока не найдет нужный или пока не кончится список.

часто используемая структура. Он либо

Используя отношение конк, напишите цель,