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

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

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

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

Reаd и write

6. 2. 1.    reаd  и write

Встроенный предикат read используется для чтения термов из текущего входного потока. Цель

        read( X)

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

Если read( X) вычисляется в тот момент, когда достигнут конец текущего входного файла, тогда Х конкретизируется атомом end_of_file

(конец файла).

Встроенный предикат write выводит терм. Поэтому цель

        write( X)

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

Существуют дополнительные встроенные предикаты для форматирования вывода. Они вставляют пробелы в дополнительные строки в выходной поток. Цель

        tab( N)

выводит N пробелов. Предикат nl (без аргументов) приводит к переходу на новую строку.

Следующие примеры иллюстрируют использование этих процедур.

Предположим, у нас есть процедура для вычисления кубов чисел:

        куб( N, С) :-
             С is N * N * N.

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

        ?-  куб( 2, X).
        Х = 8

        ?-  ку6( 5, Y).
        Y = 125

        ?-  куб( 12, Z).
        Z = 1728

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

        куб :-
                read( X),
                обработать( X).

        обработать( стоп) :-   !.

        обработать( N) :-
                С is N * N * N,
                write( С),
                куб.

Это был пример программы, декларативный смысл которой трудно сформулировать. В то же время ее процедурный смысл совершенно ясен: чтобы вычислить куб, сначала нужно считать X, а затем его обработать; если Х = стоп, то все сделано, иначе вывести Х3 и рекурсивно запустить процедуру куб для обработки остальных чисел.

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

        ?-  куб.

        2.
        8
        5.
        125
        12.
        1728
        стоп.
        yes

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

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

        куб :-
              read( стоп),   !.

        куб :-
              read( N),
              С is N * N * N,
              write( С),
              куб.

Причина, по которой эта процедура работает неправильно, станет очевидной, если проследить, какие действия она выполняет с входным аргументом, скажем с числом 5. Цель read( стоп) потерпит неудачу при чтении этого числа, и оно будет потеряно навсегда. Следующая цель read введет следующий терм. С другой стороны может случиться, что сигнал стоп будет считан целью read( N), что приведет к попытке перемножить нечисловую информацию.

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

        куб :-
              write( 'Следующее число, пожалуйста:'),
              read( X),
              обработать( X).

        о6работать( стоп) :-   !.

        обработать( N) :-
              С is N * N * N,
              write( 'Куб'),  write( N),  write( 'равен').
              write( С), nl,
              куб.

Разговор с новой версией мог бы быть, например, таким:

        ?-  куб.

        Следующее число, пожалуйста: 5.
        Куб 5 равен 125

        Следующее число, пожалуйста: 12.
        Куб 12 равен 1728

        Следующее число, пожалуйста: стоп.
        yes

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

В последующих разделах мы увидим некоторые типичные примеры операций, в которых участвуют чтение и запись.

Вывод списков

6. 2. 2.    Вывод списков

Кроме стандартного прологовского формата для списков существуют несколько других естественных форм их внешнего представления, которые в некоторых ситуациях являются более предпочтительными. Следующая процедура

        вывспис( L)

выводит список L так, что каждый его элемент занимает отдельную строку:

        вывспис( [ ]).

        вывспис( [X | L) :-
                write( X), n1.
                вывспис( L).

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

        ?-  вывспис2( [ [а, b, с], [d, e, f], [g, h, i] ] ).

        а   b   с
        d   e   f
        g   h   i

Процедура, выполняющая эту работу, такова:

        вывспис2( [ ]).

        вывспис2( [L | LL] ) :-
                строка( L), n1,
                вывспис1( LL).

        строка( [ ]).

        строка( [X | L] ) :-
                write( X), tab( 1),
                строка( L).

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

        ?- диагр( [3, 4, 6, 5] ).

        ***
        ****
        ******
        *****

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

                диагр( [N | L]) :-
                    звездочки( N), n1,
                    диагр( L).

                звеэдочки( N) :-
                    N > 0,
                    write( *),
                    Nl is N - 1,
                    звездочки( Nl).

                звездочки( N) :-
                    N =< 80.

Формирование термов

6. 2. 3.    Формирование термов

Предположим, наша программа имеет дело с семьями, которые представлены в виде термов так, как это сделано в гл. 4 (Рисунок 4.1). Тогда, если, перемен-

line();

        родители
                том фокс, датарожд 7 май 1950, работает bbс,
                                                                        оклад 15200
                энн фокс, датарожд 9 май 1951, неработает
        дети
                пат фокс, датарожд 5 май 1973, неработает
                джим фокс, датарожд 5 май 1973, неработает

line();

Обработка произвольного файла термов

6. 2. 4.    Обработка произвольного файла термов

Типичная последовательность целей для обработки файла F от начала до конца будет выглядеть примерно так:

        . . . , see( F), обработкафайла, sеe( user), . . .

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

        обработкафайла:
                обработкафайла :-
                        read( Терм),
                        обработка( Терм).

        обработка( end_of_file) :-   !.
                                    % Все сделано

        обработка( Терм) :-
                обраб( Терм),
                                    % Обработать текущий элемент
                обработкафайла.
                                    % Обработать оставшуюся часть файла

Здесь обраб( Терм) представляет процедуру обработки отдельного терма. В качестве примера такой обработки рассмотрим процедуру, которая выдает на терминал каждый терм вместе с его порядковым номером. Назовем эту процедуру показфайла. У нее должен быть дополнительный аргумент для подсчета прочитанных термов:

        показфайла( N) :-
                read( Терм),
                показ( Терм, N).

        показ( Терм, N) :-  !
                write( N), tab( 2), write( Терм),
                Nl is N + 1,
                показфайла( Nl).

Вот другой пример программы обработки файлов, построенной по подобной схеме. Пусть есть файл с именем файл1, термы которого имеют форму

        изделие( НомерИзд, Описание, Цена, ИмяПоставщика)

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

        создатьфайл( Поставщик)

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

        ?-  seе( файл1), tеll( файл2), создатьфайл( гаррисон),
                  see( user), tell( user).

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

        создатьфайл( Поставщик) :-
                write( Поставщик), write( '.'), nl,
                создатьостальное( Поставщик).

        создатьостальное( Поставщик) :-
                read( Изделие),
                обработать( Изделие, Поставщик).

        обработать( end_ot_file) :-  !.

        обработать( Изделие( Ном, Опис, Цена, Поставщик),
                                Поставщик) :-  !,
                write( Изделие( Ном, Опис, Цена) ),
                write( '.'), nl,
                создатьостальное( Поставщик).

            обработать ( _, Поставщик) :-
                создатьостальное( Поставщик).

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

Обработка файлов термов

6. 2.    Обработка файлов термов

Обработка символов

6. 3.    Обработка символов

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

        put( С)

где С - символ, который нужно вывести, в кодировке ASCII (число от 0 до 127), например, вопрос

        ?- put( 65), put( 66), put( 67).

породит следующий вывод:

        АВС

65 - ASCII-код 'А', 66 - 'В', 67 - 'С'.

Одиночный символ можно считать из текущего входного потока при помощи цели

        get0( С)

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

        get( С)

вызовет пропуск всех непечатаемых символов (в частности пробелов) от текущей позиции во входном потоке до первого печатаемого символа. Этот символ затем тоже считывается и С конкретизируется его ASCII-кодом.

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

        Робот    пытался     налить    вина    из     бутылки.

Цель сжатие выведет его в таком виде:

        Робот пытался налить вина из бутылки.

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

        сжатие :-
                get0( С),
                put( С).
                сделатьостальное( С).

        сделатьостальное( 46) :-  !.
                                    % 46 -АSСII-код точки, Все сделано

        сделатьостальное( 32) :-  !,
                                    % 32 - ASCII-код пробела

                get( С),
                put( С),
                сделатьостальное( С).

        сделатьостальное( Буква) :-
                сжатие.

Создание и декомпозиция атомов

6. 4.    Создание и декомпозиция атомов

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

        name( A, L)

истинно, если L - список кодов ASCII, кодирующих атом. Например,

        name( zx232, [122, 120, 50, 51, 50] )

истинно. Существуют два типичных способа использования name:

(1)        дан атом, разбить его на отдельные символы;

(2)        дан список символов, объединить их в один атом.

Примером первого случая применения предиката является программа, которая имеет дело с заказами такси и водителями. Все это представлено в программе атомами

        заказ1, заказ2, водитель1, водитель2, такси1, таксилюкс

Предикат

        такси( X)

проверяет, относится ли атом Х к тем атомам, которые представляют такси:

        такси( Х) :-
              name( X, Хспис),
              nаmе( такси, Тспис),
              конк( Тспис, _, Хспис).

        конк( [ ], L, L).

        конк( [А | L1], L2, [А | L3] ) :-
              конк( L1, L2, L3).

Предикаты заказ и водитель можно определить аналогично.

Наш следующий пример иллюстрирует применение объединения отдельных символов в один атом. Мы определим предикат

        читпредложение( Списслов)

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

        Мэри было приятно видеть неудачу робота.

то цель читпредложение( Предложение) вызовет конкретизацию

        Предложение=['Мэри', было, приятно, видеть, неудачу, робота]

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

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

(1)        Симв - точка, тогда все сделано.

(2)        Симв - пробел, - игнорировать его и читпредложение от остального ввода.

(3)        Симв - буква, - сначала считать слово Слово, которое начинается с Симв, а затем запустить читпредложение, чтобы считать оставшуюся часть предложения, породив при этом Списслов. Общим результатом этого будет список [Слово | Списслов].

Процедура, считывающая символы одного слова, такова:

        читбуквы( Буква, Буквы, Сделсимв)

Ее три аргумента:

(1)        Буква - текущая буква (уже считанная) читаемого слова.

(2)        Буквы - список букв (начинающийся с буквы Буква), оставшихся до конца слова.

(3)        Следсимв - входной символ, непосредственно следующий за читаемым словом. Следсимв не должен быть буквой.

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

line();

/*
Процедура читпредложение считывает предложение и из его слов создает список атомов. Например,
        читпредложение( Списслов)
порождает
        Списслов=['Мэри', было, приятно, видеть, неудачу, робота]
если входным было предложение
        Мэри было приятно видеть неудачу робота.

*/

        читпредложение( Списслов) :-
                gеt0( Симв),
                читостальное( Симв, Списслов).

        читостальное( 46, [ ]) :-  !.
                                    % Конец предложения: 46 = ASCII-код для ' '

        читостальное( 32, Списслов) :-  !,
                                    % 32 = ASCII-код для пробела
        читпредложение( Списслов).
                                    % Пропустить пробел

        читостальное( Буква, [Слово | Списслов]) :-
                читбуквы( Буква, Буквы, Следсимв),
                                    % Считать буквы текущего слова
                nаmе( Слово, Буквы),
                читостальное( Следсимв, Списслов).

        читбуквы( 46, [ ], 46) :-   !.
                                    % Конец слова: 46 = точка
        читбуквы( 32, [ ], 32) :-   !.
                                    % Конец слова: 32 = пробел

        читбуквы( Бкв, [Бкв | Буквы], Следсимв) :-
                get0( Симв),
                читбуквы( Симв, Буквы, Следсимв).

line();

Ввод программ consult reconsult

6. 5.    Ввод программ:    consult, reconsult

Передавать программы пролог-системе можно при помощи двух встроенных предикатов:    consult     и    reconsult.     Чтобы система считала программу из файла F, нужно поставить цель

        ?-  consult( F).

В результате все предложения программы, содержащейся в F, будут использованы пролог-системой при ответе на дальнейшие вопросы пользователя. Если позже в том же сеансе произойдет "консультация" с другим файлом, предложения этого нового файла будут просто добавлены в конец текущего множества предложений.

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

        ?-  consult( user).

После этого система будет ожидать ввода предложений программы с терминала.

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

        ?-  [файл1, файл2, файл3].

Это в точности эквивалентно следующим трем целям:

        ?-  соnsult( файл1), соnsult( файл2), соnsult( файл3).

Встроенный предикат reconsult аналогичен consult. Цель

        ?-  reconsult( F).

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

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

к программе) осуществляется посредством встроенных

Резюме

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

    sее( Файл)                 Файл становится текущим входным потоком
    tell( Файл)                  Файл становится текущим выходным потоком
    seen                             закрывается текущий входной поток
    told                              закрывается текущий выходной поток
Файлы читаются и записываются двумя способами:

    как последовательности символов
    как последовательности термов

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

    rеad( Терм)
                            вводит следующий терм
    write( Терм)
                            выводит Терм
    put( КодСимвола)
                            выводит символ с заданным ASCII - кодом
    get0( КодСимвола)
                            вводит следующий символ
    gеt( КодСимвола)
                            вводит ближайший следующий "печатаемый" символ
Две процедуры облегчают форматирование:

    nl                       начинает новую строку
    tab( N)              выводит N пробелов
Процедура nаmе( Атом, СписокКодов) осуществляет синтез и декомпозицию атомов. СписокКодов - список ASCII кодов символов, образующих Атом.

Связь между прологпрограммой и различными файлами

Рисунок 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 (читать и писать). В этом случае информация в файле должна, конечно, по форме соответствовать синтаксису термов.

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

Улучшенный формат вывода термов представляющих семью

Рисунок 6. 2.  Улучшенный формат вывода термов, представляющих семью.

ная F конкретизирована термом, изображенный на Рисунок 4.1, то цель

        write( F)

вызовет вывод этого терма в стандартной форме примерно так:

        семья( членсемьи( том, фокс, дата( 7, май,1950),
                         работает( bbс, 15200)),
                членсемьи( энн, фокс, дата( 9, май, 1951),
                         неработает),
                [членсемьи( пат, фокс, дата( 5, май, 1973),
                         неработает),
                членсемьи( джим, фокс, дата( 5, май, 1973),
                         неработает)])

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

        вывсемью( F)

с помощью которой это достигается, приведена на Рисунок 6.3.

line();

        вывсемью( семья ( Муж, Жена, Дети) :-
                nl, write( родители), nl, nl,
                вывчленсемьи( Муж), nl,
                вывчленсемьи( Жена), nl, nl,
                write( дети), nl, nl,
                вывчленсемьи( Дети).

        вывчленсемьи( членсемьи( Имя, Фамилия, дата( Д, М, Г), Работа) ) :-
                tab(4), write( Имя),
                tab(1), write( Фамилия),
                write( ', дата рождения'),
                write( Д), tab( 1),
                write( M), tab( 1),
                write( Г), write( ','),
                вывработу( Работа).

        вывсписчлсемьи( [ ]).

        вывсписчлсемьи( [Р | L]) :-
                вывчленсемьи( Р), nl,
                вывсписчлсемьи( L),
        вывработу( неработает) :-
                write( неработает).

        вывработу( работает Место, Оклад) ) :-
                write(' работает '), write( Место),
                write( ', оклад '), write( Оклад).

line();

в формате, представленном на Рисунок

Рисунок 6. 3.  Программа, обеспечивающая вывод в формате, представленном на Рисунок 6.2.

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

Рисунок 6. 4.  Процедура для преобразования предложения в список атомов.

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

Обобщите процедуру сжатие на случай

Упражнение

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

которая выводит на терминал новый

Упражнения

6. 1.    Пусть f  -   файл термов. Определите процедуру
        найтитерм( Терм)
которая выводит на терминал новый терм из f, сопоставимый с Терм'ом.
Посмотреть ответ
6. 2.    Пусть f  -   файл термов. Напишите процедуру
        найтивсетермы( Терм)
которая выводит на экран все термы из f, сопоставимые с Tepм'ом. Обеспечьте при этом, чтобы во время поиска Терм не конкретизировался (это могло бы помешать ему сопоставиться с другими термами дальше по файлу).
Посмотреть ответ


Упражнения

6. 4.    Определите отношение
        начинается( Атом, Символ)
для проверки, начинается ли Атом с символа Символ.
Посмотреть ответ
6. 5.    Определите процедуру plural, которая преобразует английские существительные из единственного числа во множественное, добавляя к слову окончание s. Например:
        ?-  plural( table, X).
        Х  =  tables
Посмотреть ответ
6. 6.    Напишите процедуру
        поиск( Ключслово, Предложение)
которая при каждом вызове находит в текущем входном файле предложение, содержащее заданное ключевое слово Ключслово. Предложение в своей исходной форме должно быть представлено в виде последовательности символов или в виде атома (процедуру читпредложение из данного раздела можно соответственно модифицировать).

Предикаты var nоnvar atom integer atomic

7. 1. 1.    Предикаты   var,  nоnvar,  atom,  integer,  atomic

Термы бывают разных типов: переменные, целые числа, атомы и т.д. Если терм - переменная, то в некоторый момент выполнения программы он может оказаться конкретизированным или не конкретизированным. Далее, если он конкретизирован, то его значение может быть атомом, структурой и т. п. Иногда бывает полезно узнать, каков тип этого значения. Например, пусть мы хотим сложить значения двух переменных Х и Y:

        Z  is  X + Y

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

Для этого следует воспользоваться встроенным предикатом integer (целое). Предикат integer( X) принимает значение истина, если Х - целое или если Х - переменная, имеющая целое значение. Будем говорить в этом случае, что Х "обозначает" целое. Цель для сложения Х и Y можно тогда "защитить" такой проверкой переменных Х и Y:

        . . ., integer( X), integer( Y), Z is X + Y, . . .

Если неверно, что X и Y оба являются целыми, то система и не будет пытаться их сложить. Таким образом, цели integer "охраняют" цель Z is Х + Y от бессмысленного вычисления.

Встроенные предикаты этого типа таковы: var (переменная), nonvar (непеременная), atom (атом), integer (целое), atomic (атомарный). Они имеют следующий смысл:

        var( X)

Эта цель успешна, если Х в текущий момент - не конкретизированная переменная.

        nonvar( X)

Эта цель успешна, если Х - терм, отличный от переменной, или если Х - уже конкретизированная переменная.

        atom( X)

Эта цель истинна, если Х обозначает атом.

        integer( X)

Цель истинна, если Х обозначает целое.

        atomic( X)

Цель истинна, если Х обозначает целое или атом.

Следующие примеры вопросов к пролог-системе иллюстрируют применение этих встроенных предикатов:

        ?-  var( Z),  Z = 2.
        Z = 2

        ?-  Z = 2, var( Z).
        no

        ?-  integer( Z), Z = 2.
        no

        ?-  Z = 2, integer( Z), nonvar( Z).
        Z = 2

        ?-  atom( 22).
        no

        ?-  atomic( 22).
        yes

        ?-  atom( ==>).
        yes

        ?-  atom( p( 1) ).
        no

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

        счетчик( А, L, N)

где А - атом, L - список и N - количество вхождений этого атома. В качестве первой попытки можно было бы определить счетчик так:

        счетчик( _, [ ], 0).

        счетчик( A, [A | L], N) :-  !,
                счетчик( A, L, N1),
                                    % N1 - число вхождений атома в хвост
                N is N1 + 1.

        счетчик( А, [ _ | L], N) :-
                счетчик( A, L, N).

Теперь на нескольких примерах посмотрим, как эта процедура работает:

        ?-  счетчик( а, [а, b, а, а], N).
        N = 3

        ?-  счетчик( a, [a, b, X, Y], Na).
        Na = 3
        . . .

        ?-  счетчик( b, [a, b, X, Y], Nb).
        Nb = 3
        . . .

        ?-  L=[a, b, Х, Y], счетчик( а, L, Na), счетчик( b, L, Nb).
        Na = 3
        Nb = 1
        X = a
        Y = a
        . . .

В последнем примере как X, так и Y после конкретизации получили значение а, и поэтому Nb оказалось равным только 1, однако мы хотели не этого. Нас интересовало количество реальных появлений конкретного атома, а вовсе не число термов, сопоставимых с этим атомом. В соответствии с этим более точным определением отношения счетчик мы должны теперь проверять, является ли голова списка атомом. Усовершенствованная программа выглядит так:

        счетчик( _, [ ], 0).

        счетчик( А, [В | L], N) :-
                atom( В), А = В,  !,                       % B равно атому А?
                счетчик( A, L, N1),                     % Подсчет в хвосте
                N is N1 + 1;
                счетчик( А, L, N).
                                % Иначе - подсчитать только в хвосте

В следующем более сложном упражнении по программированию числовых ребусов используется предикат nonvar.

Решение числового ребуса с использованием nonvar

7. 1. 2.    Решение числового ребуса с использованием   nonvar

Известным примером числового ребуса является

+	D O N A L D
G E  R A L D
	R O B  E R T

Задача состоит в том. чтобы заменить буквы D, О, N и т.д. на цифры таким образом, чтобы вышеприведенная сумма была правильной. Разным буквам должны соответствовать разные цифры, иначе возможно тривиальное решение, например, все буквы можно заменить на нули.

Определим отношение

        сумма( Nl, N2, N)

где Nl, N2 и N представляют три числа данного ребуса. Цель cyммa(Nl, N2, N) достигается, если существует такая замена букв цифрами, что N1+N2 = N.

Первым шагом к решению будет выбор представления чисел Nl, N2 и N в программе. Один из способов - представить каждое число в виде списка его цифр. Например, число 255 будет тогда представляться списком [2, 2, 5]. Поскольку значения цифр нам не известны заранее, каждая цифра будет обозначаться соответствующей неинициализированной переменной. Используя это представление, мы можем сформулировать задачу так:

        [ D, O, N, A, L, D ]
  +    [ G,  E, R, A, L, D ]
  =    [ R, О, B,  E, R, T ]

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

        ?-  сумма( [D, O, N, A, L, D], [G, E, R, A, L, D],
                           [R, O, В, Е, R, T ).

       

Проверка типов термов

7. 1.    Проверка типов термов

Создание и декомпозиция термов = functor arg name

7. 2.    Создание и декомпозиция термов:   =..,  functor,  arg,  name

Имеются три встроенные предиката для декомпозиции и синтеза термов: functor, arg и =.. . Рассмотрим сначала отношение =.. , которое записывается как инфиксный оператор. Цель

        Терм =.. L

истинна, если L - список, начинающийся с главного функтора терма Терм, вслед за которым идут его аргументы. Вот примеры:

        ?-  f( а, b) =.. L.
        L = [f, а, b]

        ?-  Т =.. [прямоугольник, 3, 5].
        Т = прямоугольник( 3, 5)

        ?-  Z =.. [р, X, f( X,Y) ].
        Z = p( X, f( X,Y) )

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

Рассмотрим программу, которая манипулирует геометрическими фигурами. Фигуры - это квадраты, прямоугольники, треугольники, окружности в т.д. В программе их можно представлять в виде термов, функтор которых указывает на тип фигуры, а аргументы задают ее размеры:

        квадрат( Сторона)
        треугольник( Сторона1, Сторона2, Сторона3)
        окружность( R)

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

        увел( Фиг, Коэффициент, Фиг1)

где Фиг и Фиг1 - геометрические фигуры одного типа (с одним в тем же функтором), причем параметры Фиг1 равны параметрам Фиг, умноженным на Коэффициент. Для простоты будем считать, что все параметры Фиг, а также Коэффициент уже известны, т. е. конкретизированы числами. Один из способов программирования отношения увел таков:

        увел( квадрат( A), F, квадрат( А1) ) :-
                A1 is F*A

        увел( окружность( R), F, окружность( R1) ) :-
                R1 is F*R1

        увел( прямоугольник( А, В), F, прямоугольник( А1, В1)) :-
                A1 is F*A, B1 is F*B.

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

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

        увел( Тип( Пар), F, Тип( Пар1) ):-
                Пар1 is F*Пар.

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

        увел( Фиг, F, Фиг1):-
                Фиг =.. [Тип | Параметры],
                умножспис( Параметры, F, Параметры1),
                Фиг1 =.. [Тип | Параметры)].

        умножспис( [ ], _, [ ]).

        умножспис( [X | L], F, [X1 | L1] ) :-
                X1 is F*X, умножспис( L, F, L1).

Наш следующий пример использования предиката '=..' связан с обработкой символьных выражений (формул), где часто приходится подставлять вместо некоторого подвыражения другое выражение. Мы определим отношение

        подставить( Подтерм, Терм, Подтерм1, Терм1)

следующим образом: если все вхождения Подтерм'а в Терм заменить на Подтерм1, то получится Терм1. Например:

        ?-  подставить( sin( x), 2*sin( x)*f( sin( x)), t, F ).
        F = 2*t*f( t)

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

        ?-  подставить( а+b, f( а, А+В), v, F).

даст результат

        F = f( а, v)                                                 F = f( a, v+v)
        А = а                         а не                         А = а+b
        В = b                                                         В = а+b

При определении отношения подставить нам нужно рассмотреть несколько случаев и для каждого принять свое решение:

        если Подтерм = Терм, то Терм1 = Подтерм1;
        иначе если Терм - "атомарный" (не структура),
                    то Терм1 = Терм (подставлять нечего),
                    иначе подстановку нужно выполнить над
                                аргументами Tерм'a.

Эти правила можно превратить в программу, показанную на Рисунок 7.3.

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

        получить( Функтор),
        вычислить( Списарг),
        Цель =.. [Функтор | Списарг],
        Цель

Здесь получить и вычислить - некоторые определенные пользователем процедуры, предназначенные для вычисления компонент цели. После этого цель порождается предикатом '=..', а затем активизируется при помощи простого указания ее имени Цель.

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

line();

%    Отношение
%
%    подставить( Подтерм, Терм, Подтерм1, Терм1)
%
%    состоит в следующем: если все вхождения Подтерм'а в Терм
%    заменить на Подтерм1, то получится Терм1.

%    Случай 1: Заменить весь терм

        подставить( Терм, Терм, Терм1, Терм1) :-  !.

%    Случай 2: нечего подставлять

        подставить( _, Терм, _, Терм) :-
                atomic( Терм),  !.

%    Случай 3: Проделать подстановку в аргументах

        подставить( Под, Терм, Под1, Терм1) :-
                Терм =.. [F | Арги],
                                        % Выделить аргументы
        подспис( Под, Арги, Под1, Арги1),
                                        % Выполнить над ними подстановку
        Терм1 =.. [F | Арги1].

        подспис( Под, [Терм | Термы], Под1, [Терм1 | Термы1]) :-
                 подставить( Под, Терм, Под1, Терм1),
                 подспис( Под, Термы, Под1, Термы1).

line();

Различные виды равенства

7. 3.    Различные виды равенства

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

        Х = Y

Это равенство верно, если Х и Y сопоставимы. Следующий вид равенства записывался в виде

        Х  is  E

Такое равенство выполняется, если Х сопоставим со значением арифметического выражения E. Мы также рассматривали равенства вида

        Е1 =:= Е2

которые верны, если равны значения арифметических выражений  Е1  и  Е2.   Наоборот, если значения двух арифметических выражений не равны, мы пишем

        Е1 =/= Е2

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

        Т1 == Т2

Это равенство выполняется, если термы   Т1    и   Т2   идентичны, т. е. имеют в точности одинаковую структуру, причем все соответствующие компоненты совпадают. В частности, должны совпадать и имена переменных. Отношение "не идентичны", дополнительное к данному, записывается так:

        Tl \== T2

Приведем несколько примеров:

        ?-  f( a, b) == f( а, b).
        yes

        ?-  f( a, b) == f( a, X).
        nо

        ?-  f( a, X) == f( a, Y).
        no

        ?-  X \== Y.
        yes

        ?-  t( X, f( a, Y) ) == t( X, f( a, Y) ).
        yes

Давайте в качестве примера переопределим отношение

        счетчик( Терм, Список, N)

из разд. 7.1. Пусть на этот раз N будет числом буквальных вхождений Терм'а в Список:

        счетчик( _, [ ], 0).

        счетчик( Терм, [Голова | L], N) :-
                Терм == Голова,  !,
                счетчик( Терм, L, N1),
                N is N1 + 1;
                счетчик( Терм, L, N).

Работа с базой данных

7. 4.    Работа с базой данных

Реляционная модель предполагает, что база данных - это описание некоторого множества отношений. Пролог-программу можно рассматривать как именно такую базу данных: описание отношений частично присутствует в ней в явном виде (факты), а частично - в неявном (правила). Более того, встроенные предикаты дают возможность корректировать эту базу данных в процессе выполнения программ. Это делается добавлением к программе (в процессе вычисления) новых предложений или же вычеркиванием из нее уже существующих. Предикаты, используемые для этой цели, таковы: assert (добавить), asserta, assertz и retract (удалить).

Цель

        assert( С)

всегда успешна, а в качестве своего побочного эффекта вызывает "констатацию" предложения   С,  т. е. добавление его к базе данных. Цель

        retract( С)

приводит к противоположному эффекту: удаляет предложение, сопоставимое с  С. Следующий диалог иллюстрирует их работу:

        ?-  кризис.
        no

        ? -  assert( кризис).
        yes

        ?-  кризис.
        yes

        ? -  retract( кризис).
        yes

        ?-  кризис.
        no

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

        хорошая :-
                солнечно, not дождь.

        необычная :-
                солнечно, дождь.

        отвратительная :-
                дождь, туман.

        дождь.

        туман.

Ниже приводится пример диалога с этой программой, во время которого база данных постепенно изменяется:

        ?-  хорошая.
        no

        ?-   отвратительная.
        yes

        ?-  retract( туман).
        yes

        ?-   отвратительная.
        no

        ?-  assert( солнечно).
        yes

        ?-  необычная.
        yes

        ?-  retract( дождь).
        уes

        ?-  хорошая.
        yes

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

        быстр( энн).
        медл( том).
        медл( пат).

К этой программе можно добавить правило:

        ?-  assert(
                         ( быстрее( X, Y) :-
                              быстр( X), медл( Y) ) ).

        yes

        ?-  быстрее( А, В).
        А = энн
        В = том

        ?-  retract( медл( X) ).
        Х = том;
        X = пат;
        nо

        ?-  быстрее( энн, _ ).
        nо

Заметьте, что при добавлении нового правила синтаксис требует, чтобы оно (как аргумент assert) было заключено в скобки.

При добавлении нового предложения может возникнуть желание указать, на какое место в базе данных его следует поместить. Такую возможность обеспечивают предикаты asserta и assertz. Цель

        asserta( С)

помещает С в начале базы данных. Цель

        assertz( С)

- в конце. Вот пример, иллюстрирующий работу этих предикатов:

        ?-  assеrt( р( a)), assertz( р( b) ), asserta( p( c) ).

        yes

        ?-  p( X).

        Х = с;
        Х = а;
        Х = b

Между consult и assertz существует связь. Обращение к файлу при помощи consult можно в терминах assertz определить так: считать все термы (предложения) файла и добавить их в конец базы данных.

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

        решить( Задача, Решение)

Мы можем теперь задать вопрос и потребовать, чтобы ответ на него был запомнен, с тем чтобы облегчить получение ответов на будущие вопросы:

        ?-  решить( задача1, решение),
             asserta( решить( Задача1, Решение) ).

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

Развитие этой идеи состоит в использовании assert для порождения всех решений в виде таблицы фактов. Например, создать таблицу произведений всех чисел от 0 до 9 можно так: породить пару чисел Х и Y, вычислить Z, равное Х * Y, добавить эти три числа в виде строки в таблицу произведений, а затем создать искусственно неуспех. Неуспех вызовет возврат, в результате которого будет найдена новая пара чисел, и в таблицу добавится новая строка и т.д. Эта идея реализована в процедуре

        таблица :-
                L = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9],
                принадлежит( X, L),            % Выбрать первый сомножитель
                принадлежит( Y, L),            % Выбрать второй сомножитель
                Z is X*Y,
                assert( произв( X,Y,Z) ),
                fail.

Вопрос

            ?-   таблица.

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

        ?-  произв( А, В, 8).

        А = 1
        В = 8;

        А = 2
        В = 4;

        . . .

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

Средства управления

7. 5.    Средства управления

К настоящему моменту мы познакомились с большинством дополнительных средств управления, за исключением repeat (повторение). Здесь мы для полноты приводим список всех таких средств. отсечение, записывается как  '!',   предотвращает перебор, введено в гл. 5. fail - цель, которая всегда терпит неудачу. true - цель, которая всегда успешна. not( P) - вид отрицания, который всегда ведет себя в точном соответствии со следующим определением:

        not( P) :- P,  !,  fail;   true.

Некоторые проблемы, связанные с отсечением и not детально обсуждались в гл. 5. саll( P) активизирует цель Р. Обращение к саll имеет успех, если имеет успех Р. repeat - цель, которая всегда успешна. Ее особое свойство состоит в том, что она недетерминирована, поэтому всякий раз, как до нее доходит перебор, она порождает новую ветвь вычислений. Цель repeat ведет себя так, как если бы она была определена следующим образом:

        repeat.
        repeat :- repeat.

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

        квадраты :-
                repeat,
                read( X),
                ( X = стоп,  !;
                  Y   is  X*X,  write( Y),  fail ).

Bagof setof и findall

7. 6.    bagof , setof  и findall

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

Цель

        bagof( X, P, L)

порождает список L всех объектов X, удовлетворяющих цели Р. Обычно bagof имеет смысл применять только тогда, когда Х и Р содержат общие переменные. Например, допустим, что мы включили в программу следующую группу предложений для разбиения букв (из некоторого множества) на два класса - гласные и согласные:

        класс( а, глас).
        класс( b, согл).
        класс( с, согл).
        класс( d, согл).
        класс( е, глас).
        класс( f, согл).

Тогда мы можем получить список всех согласных, упомянутых в этих предложениях, при помощи цели:

        ?-  bagof( Буква, класс( Буква, согл), Буквы).

        Буквы = [d, c, d, f]

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

        ?-  bagof( Буква, класс( Буква, Класс), Буквы).

        Класс = глас
        Буквы = [а,е]

        Класс = согл
        Буквы = [b, c, d, f]

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

Предикат setof работает аналогично предикату bagof. Цель

        setof( X, P, L)

как и раньше, порождает список  L  объектов   X,  удовлетворяющих  Р.  Только на этот раз список  L  будет упорядочен, а из всех повторяющихся элементов, если таковые есть, в него попадет только один. Упорядочение происходит по алфавиту или по отношению '<', если элементы списка - числа. Если элементы списка - структуры, то они упорядочиваются по своим главным функторам. Если же главные функторы совпадают, то решение о порядке таких термов принимается по их первым несовпадающим функторам, расположенным выше и левее других (по дереву). На вид объектов, собираемых в список, ограничения нет. Поэтому можно, например, составить список пар вида

        Класс / Буква

при этом гласные будут расположены в списке первыми ("глас" по алфавиту раньше "согл"):

        ?-  setof( Класс/Буква, класс( Буква, Класс), Спис).

        Спис = [глас/а, глас/е, согл/b, согл/с, согл/d, согл/f]

Еще одним предикатом этого семейства, аналогичным bagof, является findall.

        findall( X, P, L)

тоже порождает список объектов, удовлетворяющих Р. Он отличается от bagof тем, что собирает в список все объекты X, не обращая внимание на (возможно) отличающиеся для них конкретизации тех переменных из P, которых нет в X. Это различие видно из следующего примера:

        ?-  findall( Буква, класс( Буква, Класс), Буквы).

        Буквы= [a, b, c, d, e, f]

Если не существует ни одного объекта X, удовлетворяющего P, то findall все равно имеет успех и выдает L = [ ].

Если в используемой реализации Пролога отсутствует встроенный предикат findall, то его легко запрограммировать следующим образом. Все решения для Р порождаются искусственно вызываемыми возвратами. Каждое решение, как только оно получено, немедленно добавляется к базе данных, чтобы не потерять его после нахождения следующего решения. После того, как будут получены и сохранены все решения, их нужно собрать в список, а затем удалить из базы данных при помощи retract. Весь процесс можно представлять себе как построение очереди из порождаемых решений. Каждое вновь порождаемое решение добавляется в конец этой очереди при помощи assert. Когда все решения собраны, очередь расформировывается. Заметим также, что конец очереди надо пометить, например, атомом "дно" (который, конечно, должен отличаться от любого ожидаемого решения). Реализация findall в соответствии с описанным методом показана на Рисунок 7.4.

line();

findall( X, Цель, ХСпис) :-
    саll( Цель),                                 % Найти решение
    assert( очередь( X) ),                % Добавить егo
    fail;                 % Попытаться найти еще решения
    assertz( очередь( дно) ),
                         % Пометить конец решений
    собрать( ХСпис).                     % Собрать решения в список

собрать( L) :-
     retract( очередь(Х) ),  !,
                         % Удалить следующее решение
    ( Х == дно,  !,  L = [ ];
                         % Конец решений?
    L = [X | Остальные], собрать( Остальные) ).
                         % Иначе собрать остальные

line();

В любой реализации Пролога обычно

Резюме

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

        var( X)                     Х - (неконкретизированная) переменная
        nonvar( X)               Х - не переменная
        atom( X)                  Х - атом
        integer( X)               Х - целое
        atomic( X)               Х - или атом, или целое
Термы можно синтезировать или разбирать на части:

        Терм =.. [Функтор [ СписокАргументов]
        functor( Терм, Функтор, Арность)
        arg( N, Терм, Аргумент)
        name( атом, КодыСимволов)
Программу на Прологе можно рассматривать как реляционную базу данных, которую можно изменять при помощи следующих процедур:

        аssert( Предл)                 добавляет предложение Предл к программе
        аssегtа( Предл)               добавляет в начало
        asserfz( Предл)               добавляет в конец
        rеtrасt( Предл)                удаляет предложение,
                                                  сопоставимое с предложением Предл
Все объекты, отвечающие некоторому заданному условию, можно собрать в список при помощи предикатов:

        bagof( X, Р, L)         L - список всех X, удовлетворяющих условию Р

        setof( X, Р, L)          L - отсортированный список всех X,
                                         удовлетворяющих условию Р

        findall( X, Р, L)        аналогичен bagof
repeat - средство управления, позволяющее порождать неограниченное число альтернатив для автоматического перебора.

Поразрядное сложение

Рисунок 7. 1.  Поразрядное сложение.    Отношения в показанном i-м
разряде такие:    D3i = (C1 + D1i + D2i)     mod    10;    C = (C1 + D1i + D2i)
div  10  (div - целочисленное деление,   mod - остаток от деления).

Для определения отношения сумма над списками цифр нам нужно запрограммировать реальные правила суммирования в десятичной системе счисления. Суммирование производится цифра за цифрой, начиная с младших цифр в сторону старших, всякий раз учитывая цифру переноса справа. Необходимо также сохранять множество допустимых цифр, т.е. цифр, которые еще не были использованы для конкретизации уже встретившихся переменных. Поэтому, вообще говоря, кроме трех чисел Nl, N2 и N в рассмотрении должна участвовать некоторая дополнительная информация, как показано на Рисунок 7.1: перенос перед сложением перенос после сложения множество цифр, доступных перед сложением оставшиеся цифры, не использованные при сложении

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

        сумма1( Nl, N2, N, C1, С, Цифры1, Цифры)

Здесь Nl, N2 и N - наши три числа, как и в отношении сумма, С1 - перенос справа (до сложения Nl и N2), а С - перенос влево (после сложения). Пример:

        ?-  сумма1( [H, E], [6, E], [U, S], l, l,
                            [1, 3, 4, 7, 8, 9], Цифры ).
        Н = 8
        Е = 3
        S = 7
        U = 4
        Цифры = [1, 9]

Если Nl и N удовлетворяют отношению сумма, то, как показано на Рисунок 7.1, С1 и С должны быть равны 0. Цифры1 - список цифр, которые не были использованы для конкретизации переменных. Поскольку мы допускаем использование в отношении сумма любых цифр, ее определение в терминах отношения сумма1 выглядит так:

        сумма( Nl, N2, N) :-
                cyммa1( Nl, N2, N, 0, 0, [0, l, 2, 3, 4, 5, 6, 7, 8, 9], _ ).

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

Определение отношения сумма1 можно разбить на два случая:

(1)        Все три числа представляются пустыми списками. Тогда

        сумма1( [ ], [ ], [ ], 0, 0, Циф, Циф).

(2)        Все три числа имеют какую-то самую левую цифру и справа от нее - остальные цифры. То есть, они имеют вид:

        [D1 | Nl],         [D2 | N2],         [D | N]

В этом случае должны выполняться два условия:

(а)        Оставшиеся цифры, рассматриваемые как три числа Nl, N2 и N, сами должны удовлетворять отношению сумма1, выдавая влево некоторый перенос С2 и оставляя некоторое подмножество неиспользованных цифр Циф2.

(b)        Крайние левые цифры D1, D2 и D, а также перенос С2 должны удовлетворять отношению, показанному на Рисунок 7.1: С2, D1 и D2 складываются, давая в результате D и перенос влево. Это условие в нашей программе формулируется в виде отношения суммацифр.

Переводя это на Пролог, получаем:

        сумма1( [D1 | N1], [D2 | N2], [D | N], С1, С, Циф1, Циф) :-
                сумма1( Nl, N2, N, С1, С2, Циф1, Циф2),
                суммацифр( D1, D2, С2, D, С, Циф2, Циф).

Осталось только описать на Прологе отношение суммацифр. В его определении есть одна тонкая деталь, касающаяся применения металогического предиката nonvar. D1, D2 и D должны быть десятичными цифрами. Если хоть одна из этих переменных еще не конкретизирована, ее нужно конкретизировать какой-нибудь цифрой из списка Циф2. Как только такая конкретизация произошла, эту цифру нужно удалить из множества доступных цифр. Если D1, D2 и D уже конкретизированы, тогда, конечно, ни одна из доступных цифр "потрачена" не будет. В программе эти действия реализуются при помощи недетерминированного вычеркивания элемента списка. Если этот элемент - не переменная, ничего не вычеркивается (конкретизации не было). Вот эта программа:

        удалить( Элемент, Список, Список) :-
                nonvar( Элемент),  !.

        удалить( Элемент, [Элемент | Список ], Список).

        удалить(Элемент, [А | Список], [А | Список1]) :-
                удалить( Элемент, Список, Список1).

Полная программа для решения арифметических ребусов приводится на Рисунок 7.2. В программу включены также определения двух ребусов. Вопрос к пролог-системе для ребуса про DONALD'a, GERALD'a и ROBERT'a с использованием этой программы выглядит так:

        ?-  ребус1( N1, N2, N), сумма( N1, N2, N).

line();

%  Решение числовых ребусов

сумма( N1, N2, N) :-
                            % Числа представлены в виде списков цифр
сумма1( N1, N2, N,
                0, 0,
                            % Перенос справа и перенос влево равны 0
                [0, 1, 2, 3, 4, 5, 6, 7, 8, 9], _ ).
                            % Все цифры доступны

сумма1( [ ], [ ], [ ], 0, 0, Цифры, Цифры).

сумма1( [D1 | N1], [D2 | N2], [D | N], C1, С, Циф1, Циф) :-
        сумма1( Nl, N2, N, C1, C2, Циф1, Циф2),
        суммацифр( Dl, D2, C2, С, Циф2, Циф).

суммацифр( Dl, D2, C1, D, С, Циф1, Циф) :-
        удалить( D1, Циф1, Циф2),
                                    % Выбор доступной цифры для D1
        удалить( D2, Циф2, Циф3),
                                    % Выбор доступной цифры для D2
        удалить( D, Циф3, Циф),
                                    % Выбор доступной цифры для D
        S is D1 + D2 + C1,
        D is S mod 10,
        С is S div 10.

удалить( A, L, L) :-
        nonvar( A),  !.
                                % Переменная А уже конкретизирована

удалить( А, [А | L], L).

удалить( А, [В | L], [В | L1]) :-
        удалить( A, L, L1).

% Примеры ребусов

ребус1( [D, O, N, A, L, D],
              [G, E, R, A, L, D],
              [R, O, B, E, R, T].

ребус2( [0, S, E, N, D],
              [0, M, O, R, E],
              [M, O, N, E, Y].

line();

Программа для арифметических ребусов

Рисунок 7. 2.  Программа для арифметических ребусов.

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

        ? -  сумма1( [5, O, N, A, L, 5],
                              [G, E, R, A, L, 5],
                              [R, O, B, E, R, T],
                              0, 0, [0, 1, 2, 3, 4, 6, 7, 8, 9], _ ).

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

Процедура подстановки в терм вместо одного из его подтермов некоторого другого подтерма

Рисунок 7. 3.  Процедура подстановки в терм вместо одного из его
подтермов некоторого другого подтерма.

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

        . . .
        Цель = [Функтор | Списарг],
        саll( Цель)

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

        functor( Терм, F, N)

истинна, если F - главный функтор Tepм'a, а N -арность F. Цель

        arg( N, Терм, А)

истинна, если А - N-й аргумент в Терм'е, в предположении, что нумерация аргументов идет слева направо и начинается с 1. Примеры для иллюстрации:

        ?-  functor( t( f( x), X, t), Фун, Арность).

        Фун = t
        Арность = 3

        ?-  аrg( 2, f( X, t( a), t( b) ), Y).

        Y = t( a)

        ?-  functor( D, дата, 3),
                arg( 1, D, 29),
                arg( 2, D, июнь),
                arg( 3, D, 1982).

        D = дата( 29, июнь, 1982)

Последний пример иллюстрирует особый случай применения предиката functor. Цель functor( D, дата, 3) создает "обобщенный" терм с главным функтором дата и тремя аргументами. Этот терм обобщенный, так как все три его аргумента - не конкретизированные переменные, чья имена генерируются пролог - системой. Например:

        D = дата( _5, _6, _7)

Затем эти три переменные конкретизируются при помощи трех целей аrg.

К рассматриваемому множеству встроенных предикатов относится также и введенный в гл. 6 предикат name, предназначенный для синтеза и декомпозиция атомов. Для полноты изложения мы здесь напомним его смысл. Цель

        name( A, L)

истинна, если L - список кодов (в кодировке ASCII) символов, входящих в состав атома А.

Реализация отношения findall

Рисунок 7. 4.  Реализация отношения findall.

Пусть эта процедура переупорядочивает слагаемые

Упражнения

7. 1.    Напишите процедуру упростить для упрощения алгебраических сумм, в которых участвуют числа и символы (строчные буквы). Пусть эта процедура переупорядочивает слагаемые так, чтобы символы предшествовали числам. Вот примеры ее использования:
        ?-  упростить( 1 + 1 + а, Е).
        Е = а + 2
        ?-  упростить( l + a + 4 + 2 + b + с, E).
        Е = а + b + с + 7
        ?-  упростить( 3 + х + х, Е).
        Е = 2*х + 3
7. 2.  Определите процедуру
        добавить( Элемент, Список)
для добавления нового элемента в список. Предполагается, что все элементы, хранящиеся в списке, - атомы. Список состоит из всех хранящихся в нем элементов, а за ними следует хвост, который не конкретизирован и служит для принятия новых элементов. Пусть, например, в списке уже хранятся а, b и с, тогда
        Список = [а, b, с | Хвост]
где Хвост - переменная. Цель
        добавить( d, Список)
вызовет конкретизацию
        Xвoст = [d | НовыйХвост] и
        Список = [а, b, с, d | НовыйХвост]
Таким способом структура может наращиваться, включая в себя новые элементы. Определите также соответствующее отношение принадлежности.
Посмотреть ответ


Упражнения

7. 3.    Определите предикат конкрет(Терм) так, чтобы он принимал значение истина, когда в Tepм'e нет ни одной неконкретизированной переменной.
7. 4.    Процедура подставить из данного раздела производит, при наличии разных вариантов, лишь самую "внешнюю" подстановку.
Модифицируйте эту процедуру так, чтобы она находила все возможные варианты при помощи автоматического перебора. Например:
        ?-  подставить( a+b, f( A+B), новый, НовыйТерм).
        А = а
        В = b
        НовыйТерм = f( новый);
        А = а+b
        В = а+b
        НовыйТерм = f( новый + новый)
Наша исходная версия нашла бы только первый из этих двух ответов.
7. 5.    Определите отношение
        включает( Tepмl, Терм2)
которое выполняется, если Терм1 является более общим, чем Терм2. Например:
        ?-  включает( X, с).
        yes
        ?-  включает( g( X), g( t( Y))).
        yes
        ?-  включает f( X,X), f( a,b)).
        no

Упражнения

7. 6.   (а)         Напишите вопрос к пролог-системе, который удаляет из базы данных всю таблицу произв.
           (b)         Измените этот вопрос так, чтобы он удалил из таблицы только те строки, в которых произведение равно 0.
7. 7.        Определите отношение
        копия( Терм, Копия)
которое порождает такую копию Терм'а Копия, в которой все переменные переименованы. Это легко сделать, используя assert и retract.

Упражнения

7. 8. Используя bagof, определите отношение
        множподмножеств( Мн, Подмн)
для вычисления множества всех подмножеств данного множества (все множества представлены списками).
7. 9.    Используя bagof, определите отношение
        копия( Терм, Копия)
чтобы Копия представляла собой Терм, в котором все переменные переименованы.

Общие принципы хорошего программирования

8. 1.    Общие принципы хорошего программирования

Главный вопрос, касающийся хорошего программирования, - это вопрос о том, что такое хорошая программа. Ответ на этот вопрос не тривиален, поскольку существуют разные критерии качества программ.

Следующие критерии общеприняты: Правильность. Хорошая программа в первую очередь должна быть правильной, т. е. она должна делать именно то, для чего предназначалась. Это требование может показаться тривиальным и самоочевидным. Однако в случае сложных программ правильность достигается не так часто. Распространенной ошибкой при написании программ является пренебрежение этим очевидным критерием, когда большее внимание уделяется другим критериям - таким, как эффективность. Эффективность. Хорошая программа не должна попусту тратить компьютерное время и память. Простота, читабельность. Хорошая, программа должна быть легка для чтения и понимания. Она не должна быть более сложной, чем это необходимо. Следует избегать хитроумных программистских трюков, затемняющих смысл программы. Общая организация программы и расположение ее текста должны облегчать ее понимание. Удобство модификации. Хорошая программа должна быть легко модифицируема и расширяема. Простота и модульная организация программы облегчают внесение в нее изменений. Живучесть. Хорошая программа должна быть живучей. Она не должна сразу "ломаться", если пользователь введет в нее неправильные или непредусмотренные данные. В случае подобных ошибок программа должна сохранять работоспособность и вести себя разумно (сообщать об ошибках). Документированность. Хорошая программа должна быть хорошо документирована. Минимальная документация - листинг с достаточно подробными комментариями.

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

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

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

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

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

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

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

Для того, чтобы удачно сформулировать решение на некотором уровне детализации и придумать полезные понятия для следующего, более низкого уровня, нужны идеи. Поэтому программирование - это творческий процесс, что верно в особенности, когда речь идет о начинающих программистах. По мере накопления опыта работа программиста постепенно становится все менее искусством и все более ремеслом. И все же главным остается вопрос: как возникают идеи? Большинство идей приходит из опыта, из тех задач, решения которых уже известны. Если мы не знаем прямого решения задачи, то нам может помочь уже решенная задача, похожая на нашу. Другим источником идей является повседневная жизнь. Например, если необходимо запрограммировать сортировку списка, то можно догадаться, как это сделать, если задать себе вопрос: "А как бы я сам стал действовать, чтобы расположить экзаменационные листы студентов по их фамилиям в алфавитном порядке?"

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

Использование рекурсии

8. 2. 1.    Использование рекурсии

Этот принцип состоит в том, чтобы разбить задачу на случаи, относящиеся к двум группам:

(1)        тривиальные, или "граничные" случаи;
(2)        "общие" случаи, в которых решение получается из решений для (более простых) вариантов самой исходной задачи.

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

        преобрспис( Спис, F, НовСпиc)

где Спис - исходный список, F - правило преобразования (бинарное отношение), а НовСпиc - список всех преобразованных элементов. Задачу преобразования списка Спис можно разбить на два случая:

(1)        Граничный случай: Спис = [ ]

            Если Спис = [ ], то НовСпиc = [ ], независимо от F

(2)        Общий случай: Спис = [X | Хвост]

            Чтобы преобразовать список вида [X | Хвост], необходимо:

                        преобразовать список Хвост; результат - НовХвост;
                        преобразовать элемент Х по правилу F; результат - НовХ;
                        результат преобразования всего списка - [НовХ | НовХвост].

Тот же алгоритм, изложенный на Прологе:

        преобрспис( [ ], _, [ ]).

        преобрспис( [Х | Хвост], F, [НовХ | НовХвост] :-
                G =.. [F, X, НовХ],
                саll( G),
                пpeoбpcпиc( Хвост, F, НовХвост).

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

Обобщение

8. 2. 2.    Обобщение

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

        восемьферзей( Поз)

Оно выполняется (истинно), если Поз - представленная тем или иным способом позиция, удовлетворяющая условию задачи. Можно предложить следующую полезную идею: обобщить задачу, перейдя от 8 ферзей к произвольному количеству - N. Количество ферзей станет дополнительным аргументом:

        n_ферзей( Поз, N)

Преимущество такого обобщения состоит в том, что отношение n_ферзей допускает непосредственную рекурсивную формулировку:

(1)        Граничный случай: N = 0
             Разместить 0 ферзей - тривиальная задача.

(2)        Общий случай: N > 0
             Для "безопасного" размещения N ферзей необходимо:

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

Как только мы научимся решать более общую задачу, решить исходную уже не составит труда:

        восемьферзей( Поз) :- n_ферзей( Поз, 8)

Использование рисунков

8. 2. 3.    Использование рисунков

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

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

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

(2)        Естественным наглядным изображением структурных объектов Пролога являются деревья.

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

Как представлять себе программы на Прологе

8. 2.    Как представлять себе программы на Прологе

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

Некоторые правила хорошего стиля

8. 3. 1.    Некоторые правила хорошего стиля

Предложения программы должны быть короткими. Их тела, как правило, должны содержать только несколько целей. Процедуры должны быть короткими, поскольку длинные процедуры трудны для понимания. Тем не менее длинные процедуры вполне допустимы в том случае, когда они имеют регулярную структуру (этот вопрос еще будет обсуждаться в данной главе). Следует применять мнемонические имена процедур и переменных. Они должны отражать смысл отношений и роль объектов данных. Существенное значение имеет расположение текста программы. Для улучшения читабельности программы нужно постоянно применять пробелы, пустые строки и отступы. Предложения, относящиеся к одной процедуре, следует размещать вместе в виде отдельной группы строк; между предложениями нужно вставлять пустую строку (этого не нужно делать, возможно, только в случае перечисления большого количества фактов, касающихся одного отношения); каждую цель можно размещать на отдельной строке. Пролог-программы иной раз напоминают стихи по эстетической привлекательности своих идей и формы. Стилистические соглашения такого рода могут варьироваться от программы к программе, так как они зависят от задачи и от личного вкуса. Важно, однако, чтобы на протяжении одной программы постоянно применялись одни и те же соглашения. Оператор отсечения следует применять с осторожностью. Если легко можно обойтись без него - не пользуйтесь им. Всегда, когда это возможно, предпочтение следует отдавать "зеленым отсечениям" перед "красными". Как говорилось в гл. 5, отсечение называется "зеленым", если его можно убрать, на затрагивая декларативный смысл предложения. Использование "красных отсечений" должно ограничиваться четко определенными конструкциями, такими как оператор not или конструкция выбора между альтернативами. Примером последней может служить

        если Условие то Цель1 иначе Цель2

С использованием отсечения эта конструкция переводится на Пролог так:

        Условие,  !.             % Условие выполнено?
       
        Цель1;                     % Если да, то Цель1

        Цель2                      % Иначе - Цель2
Из-за того, что оператор not связан с отсечением, он тоже может привести к неожиданностям. Поэтому, применяя его, следует всегда помнить точное прологовское определение этого оператора. Тем не менее, если приходится выбирать между not и отсечением, то лучше использовать not, чем какую-нибудь туманную конструкцию с отсечением. Внесение изменений в программу при помощи assert и retract может сделать поведение программы значительно менее понятным. В частности, одна и та же программа на одни н те же вопросы будет отвечать по-разному в разные моменты времени. В таких случаях, если мы захотим повторно воспроизвести исходное поведение программы, нам придется предварительно убедиться в том, что ее исходное состояние, нарушенное при обращении к assert и retract, полностью восстановлено. Применение точек с запятой может затемнять смысл предложений. Читабельность можно иногда улучшить, разбивая предложения, содержащие точки с запятой, на несколько новых предложений, однако за это, возможно, придется заплатить увеличенном длины программы и потерей в ее эффективности.

Для иллюстрации некоторых положений данного раздела рассмотрим отношение

        слить( Спис1, Спис2, Спис3)

где Спис1 и Спис2 - упорядоченные списки, а Спис3 -результат их слияния (тоже упорядоченный). Например:

        слить( [2, 4, 7], [1, 3, 4, 8], [1, 2, 3, 4, 4, 7, 8] )

Вот стилистически неудачная реализация этого отношения:

        слить( Спис1, Спис2, Спис3) :-
                Спис1 = [ ],  !,  Спис3 = Спис2;
                                                    % Первый список пуст
                Спис2 = [ ],  !,  Спис3 = Спис1;
                                                    % Второй список пуст
                Спис1 = [X | Остальные],
                Спис2 = [Y | Остальные],
                ( Х < Y,  !,
                Z = X,                           % Z - голова Спис3
                слить( Остальные1, Спис2, Остальные3 );
                Z = Y,
                слить( Спис1, Остальные2, Остальные3 ) ),
                Спис3 = [Z | Остальные3].

Вот более предпочтительный вариант, не использующий точек с запятой:

        слить( [ ], Спис, Спис).

        слить( Спис, [ ], Спис).

                слить( [X | Остальные1], [Y | Остальные2], [X | Остальные3] ) :-
                Х < Y,  !,
                слить(Остальные1, [Y | Остальные2], Остальные3).

                слить( Спис1, [Y | Остальные2], [Y | Остальные3]): -
                слить( Спис1, Остальные2, Остальные3 ).

Табличная организация длинных процедур

8. 3. 2.    Табличная организация длинных процедур

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

8. 3. 3.    Комментирование

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

Длинные фрагменты комментариев следует располагать перед текстом, к которому они относятся, в то время как короткие комментарии должны быть вкраплены в сам текст. Информация, которую в самом общем случае следует включать в комментарии, должна схватывать следующие вопросы: Что программа делает, как ею пользоваться (например, какую цель следует активизировать и каков вид ожидаемых результатов), примеры ее применения. Какие предикаты относятся к верхнему уровню? Как представлены основные понятия (объекты)? Время выполнения и требования по объему памяти. Каковы ограничения на программу? Использует ли она какие-либо средства, связанные с конкретной операционной системой? Каков смысл предикатов программы? Каковы их аргументы? Какие аргументы являются "входными" и какие - "выходными", если это известно? (В момент запуска предиката входные аргументы имеют полностью определенные значения, не содержащие не конкретизированных переменных.) Алгоритмические и реализационные детали.

Стиль программирования

8. 3.    Стиль программирования

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

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

Отладка

8. 4.    Отладка

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

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

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

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

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

        trace

запускает полную трассировку всех целей, следующих за trace.

        notrace

прекращает дальнейшее трассирование.

        spy( P)                             (следи за Р)

устанавливает режим трассировки предиката Р. Обращение к spy применяют, когда хотят получить информацию только об указанном предикате и избежать трассировочной информации от других целей (как выше, так и ниже уровня запуска Р). "Следить" можно сразу за несколькими предикатами.

        nospy( Р)

прекращает "слежку" за Р.

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

Повышение эффективности решения задачи о восьми ферзях

8. 5. 1.    Повышение эффективности решения задачи о восьми ферзях

В качестве простого примера повышения эффективности давайте вернемся к задаче о восьми ферзях (см. Рисунок 4.7). В этой программе Y-координаты ферзей перебираются последовательно - для каждого ферзя пробуются числа от 1 до 8. Этот процесс был запрограммирован в виде цели

        принадлежит( Y, [1, 2, 3, 4, 5, 6, 7, 8] )

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

        принадлежит( Y, [1, 5, 2, 6, 3, 7, 4, 8] )

Это маленькое изменение уменьшит время, необходимое для нахождения первого решения, в 3-4 раза.

В следующем примере такая же простая идея, связанная с изменением порядка, превращает практически неприемлемую временную сложность в тривиальную.

Повышение эффективности программы раскраски карты

8. 5. 2.    Повышение эффективности программы раскраски карты

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

Пусть карта задана отношением соседства

        соседи( Страна, Соседи)

где Соседи - список стран, граничащих со страной Страна. При помощи этого отношения карта Европы с 20-ю странами будет представлена (в алфавитном порядке) так:

        соседи( австрия, [венгрия, запгермания, италия,
                                        лихтенштейн, чехословакия,
                                        швейцария, югославия]),

        соседи( албания, [греция, югославия]).

        соседи( андорра, [испания, франция]).

        . . .

Решение представим в виде списка пар вида

        Страна / Цвет

которые устанавливают цвет для каждой страны на данной карте. Для каждой карты названия стран всегда известны заранее, так что задача состоит в нахождении цветов. Таким образом, для Европы задача сводится к отысканию подходящей конкретизации переменных C1, C2, СЗ и т.д. в списке

        [австрия/C1, албания/С2, андорра/С3, . . .]

Теперь определим предикат

        цвета( СписЦветСтран)

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

        цвета( [ ]).

        цвета( [Страна/Цвет | Остальные] ) :-
        цвета( Остальные),
            принадлежит( Цвет, [желтый, синий, красный, зеленый]),
            not( принадлежит( Страна1/Цвет, Остальные),
                                                        сосед( Страна, Страна1) ).

        сосед( Страна, Страна1) :-
                соседи( Страна, Соседи),
                принадлежит( Страна1, Соседи).

Здесь принадлежит( X, L) - как всегда, отношение принадлежности к списку. Для простых карт с небольшим числом стран такая программа будет работать. Что же касается Европы, то здесь результат проблематичен. Если считать, что мы располагаем встроенным предикатом setof, то можно попытаться раскрасить карту Европы следующим образом. Определим сначала вспомогательное отношение:

        страна( С) :- соседи( С, _ ).

Тогда вопрос для раскраски карты Европы можно сформулировать так:

        ?-  sеtоf( Стр/Цвет, страна( Стр), СписЦветСтран),
             цвета( СписЦветСтран).

Цель setof - построить "шаблон" списка СписЦветСтран, в котором в элементах вида страна/ цвет вместо цветов будут стоять неконкретизированные переменные. Предполагается, что после этого цель цвета конкретизирует их. Такая попытка скорее всего потерпит неудачу вследствие неэффективности работы программы.

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

Ясно поэтому, что эффективность зависит от порядка раскраски стран. Интуиция подсказывает простую стратегию раскраски, которая должна быть лучше, чем случайная: начать со страны, имеющей иного соседей, затем перейти к ее соседям, затем - к соседям соседей и т.д. В случае Европы хорошим кандидатом для начальной страны является Западная Германия (как имеющая наибольшее количество соседей - 9). Понятно, что при построении шаблона списка элементов вида страна/цвет Западную Германию следует поместить в конец этого списка, а остальные страны - добавлять со стороны его начала. Таким образом, алгоритм раскраски, который начинает работу с конца списка, в начале займется Западной Германией и продолжит работу, переходя от соседа к соседу.

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

Можно было бы построить такой правильно упорядоченный список стран вручную, но в этом нет необходимости. Эту работу выполнит процедура создспис. Она начинает построение с некоторой указанной страны (в нашем случае - с Западной Германии) и собирает затем остальные страны в список под названием Закрытый. Каждая страна сначала попадает в другой список, названный Открытый, а потом переносится в Закрытый. Всякий раз, когда страна переносится из Открытый в Закрытый, ее соседи добавляются в Открытый.

        создспис( Спис) :-
                собрать( [запгермания], [ ], Спис ).
                собрать( [ ], Закрытый, Закрытый).
                                    % Кандидатов в Закрытый больше нет

        собрать( [X | Открытый], Закрытый, Спис) :-
                    принадлежит( Х | Закрытый),  !,
                                        % Х уже собран ?

        собрaть( Открытый, Закрытый, Спис).
                            % Отказаться от Х

        собрать( [X | Открытый], Закрытый, Спис) :-
                соседи( X, Соседи),
                                % Найти соседей Х
                конк( Соседи, Открытый, Открытый1),
                                % Поместить их в Открытый
                собрать( Открытый1, [X | Закрытый], Спис).
                                % Собрать остальные

Отношение конк - как всегда - отношение конкатенации списков.

Повышение эффективности конкатенации списков за счет совершенствования структуры данных

8. 5. 3.    Повышение эффективности конкатенации списков за счет совершенствования структуры данных

До сих пор в наших программах конкатенация была определена так:

        конк( [ ], L, L).

        конк( [X | L1], L2, [X | L3] ) :-
                конк( L1, L2, L3 ).

Эта процедура неэффективна, если первый список - длинный. Следующий пример объясняет, почему это так:

        ?-  конк( [а, b, с], [d, e], L).

Этот вопрос порождает следующую последовательность целей:

        конк( [а, b, с], [d, e], L)

            конк( [b, с], [d, e], L')                 где L = [a | L']

                конк( [с], [d, e], L")                    где L' = [b | L"]

                    конк( [ ], [d, e], L'")                   где L" = [c | L''']

                        true             (истина)                   где L'" = [d, е]

Ясно, что программа фактически сканирует весь первый список, пока не обнаружит его конец.

А нельзя ли было бы проскочить весь первый список за один шаг и сразу подсоединить к нему второй список, вместо того, чтобы постепенно продвигаться вдоль него? Но для этого необходимо знать, где расположен конец списка, а следовательно, мы нуждаемся в другом его представлении. Один из вариантов - представлять список парой списков. Например, список

        [а, b, с]

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

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

Подобная пара списков, записанная для краткости как L1-L2, представляет собой "разность" между L1 и L2. Это представление работает только при том условии, что L2 - "конечный участок" списка L1. Заметим, что один и тот же список может быть представлен несколькими "разностными парами". Поэтому список [а, b, с] можно представить как

        [а, b, с]-[ ]
или
        [a, b, c, d, e]-[d, e]
или
        [a, b, c, d, e | T]-[d, e | T]
или
        [а, b, с | Т]-Т

где Т - произвольный список, и т.п. Пустой список представляется любой парой L-L.

Поскольку второй член пары указывает на конец списка, этот конец доступен сразу. Это можно использовать для эффективной реализации конкатенации. Метод показан на Рисунок 8.1. Соответствующее отношение конкатенации записывается на Прологе в виде факта

        конкат( A1-Z1, Z1-Z2, A1-Z2).

Давайте используем конкат для конкатенации двух списков: списка [а, b, с], представленного парой [а, b, с | Т1]-Т1, и списка [d, e], представленного парой [d, e |  Т2]-Т2 :

        ?-  конкат( [а, b, с | Т1]-T1, [d, е | Т2]-Т2, L ).

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

        T1 = [d, e | Т2]
        L = [a, b, c, d, e | T2]-T2

Повышение эффективности зa счет добавления вычисленных фактов к базе данных

8. 5. 4.    Повышение эффективности зa счет добавления вычисленных фактов к базе данных

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

В качестве примера рассмотрим программу вычисления N-го числа Фибоначчи для некоторого заданного N. Последовательность Фибоначчи имеет вид:

        1,  1,  2,  3,  5,   8,  13,  ...

Каждый член последовательности, за исключением первых двух, представляет собой сумму предыдущих двух членов. Для вычисления N-гo числа Фибоначчи F определим предикат

        фиб( N, F)

Нумерацию чисел последовательности начнем с N = 1. Программа для фиб обрабатывает сначала первые два числа Фибоначчи как два особых случая, а затем определяет общее правило построения последовательности Фибоначчи:

        фиб( 1, 1).                             % 1-е число Фибоначчи

        фиб( 2, 1).                             % 2-е число Фибоначчи

        фиб( N, F) :-                         % N-е число Фиб., N > 2
                N > 2,
                N1 is N - 1, фиб( N1, F1),
                N2 is N - 2, фиб( N2, F2),
                F is F1 + F2.                % N-e число есть сумма двух
                                                    % предыдущих

Процедура фиб имеет тенденцию к повторению вычислений. Это легко увидеть, если трассировать цель

        ?-  фиб( 6, F).

На Рисунок 8.2 показано, как протекает этот вычислительный процесс. Например, третье число Фибоначчи f( 3) понадобилось в трех местах, и были повторены три раза одни и те же вычисления.

Этого легко избежать, если запоминать каждое вновь вычисленное число. Идея состоит в применении встроенной процедуры assert для добавления этих (промежуточных) результатов в базу данных в виде фактов. Эти факты должны предшествовать другим предложениям, чтобы предотвратить применение общего правила в случаях, для которых результат уже известен. Усовершенствованная процедура фиб2 отличается от фиб только этим добавлением:

        фиб2( 1, 1).                         % 1-е число Фибоначчи

        фиб2( 2, 1).                         % 2-е число Фибоначчи

        фиб2( N, F) :-                      % N-e число Фиб., N > 2
                N > 2,
                Nl is N - 1, фиб2( N1, F1),
                N2 is N - 2, фиб2( N2, F2),
                F is F1 + F2,                        % N-e число есть сумма
                                                            % двух предыдущих
                asserta( фиб2( N, F) ).      % Запоминание N-го числа

Эта программа, при попытке достичь какую-либо цель, будет смотреть сперва на накопленные об этом отношении факты и только после этого применять общее правило. В результате, после вычисления цели фиб2( N, F), все числа Фибоначчи вплоть до N-го будут сохранены. На Рисунок 8.3 показан процесс вычислении 6-го числа при помощи фиб2. Сравнение этого рисунка с Рисунок 8.2. показывает, на сколько уменьшилась вычислительная сложность. Для больших N такое уменьшение еще более ощутимо.

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

Эффективность

8. 5.    Эффективность

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

Традиционная архитектура вычислительных машин не очень хорошо приспособлена для реализации прологовского способа выполнения программ, предусматривающего достижение целей из некоторого списка. Поэтому ограниченность ресурсов по времени и пространству сказывается в Прологе, пожалуй, в большей степени, чем в большинстве других языков программирования. Вызовет ли это трудности в практических приложениях, зависит от задачи. Фактор времени практически не имеет значения, если пролог-программа, которую запускают по несколько раз в день, занимает 1 секунду процессорного времени, а соответствующая программа на каком-либо другом языке, скажем на Фортране, - 0.1 секунды. Разница в эффективности становится существенной, если эти две программы требуют 50 и 5 минут соответственно.

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

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

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

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

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

Помогает понять отношение фибвперед

Рисунок 8.4 помогает понять отношение фибвперед. В соответствии с этим рисунком фибвперед находит последовательность преобразований для достижения конечной конфигурации (в которой М = N) из некоторой заданной начальной конфигурации. При запуске фибвперед все его аргументы, кроме F, должны быть конкретизированы, а М должно быть меньше или равно N. Вот эта программа:

фиб3( N, F) :-
                фибвперед( 2, N, 1, 1, F).
                                    % Первые два числа Фиб. равны 1

        фибвперед( М, N, F1, F2, F2) :-
                М >= N.     % N-e число достигнуто

        фибвперед( M, N, F1, F2, F) :-
                M < N,       % N-e число еще не достигнуто
                СледМ is М + 1,
                СледF2 is F1 + F2,
                фибвперед( СледМ, N, F2, СледF2, F).

Для оценки качества программы существует

Резюме

Для оценки качества программы существует несколько критериев:

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

Применение рекурсии:  выявить граничные и общие случаи рекурсивного определения.

Обобщение:  рассмотреть такую более общую задачу, которую проще решить, чем исходную.

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

изменение порядка целей и предложений

управляемый перебор при помощи введения отсечений

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

Конкатенация списков

Рисунок 8. 1.  Конкатенация списков, представленных в виде разностных пар.
L1 представляется как A1-Z1, L2 как A2-Z2 и результат L3 - как A1-Z2.
При этом должно выполняться равенство Z1 = А2.

Вычисление 6го числа Фибоначчи процедурой фиб

Рисунок 8. 2.  Вычисление 6-го числа Фибоначчи процедурой фиб.

Вычисление 6го числа

Рисунок 8. 3.  Вычисление 6-го числа Фибоначчи при помощи процедуры фиб2, которая запоминает предыдущие результаты. По сравнению с процедурой фиб здесь вычислений меньше (см. Рисунок 8.2).

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

        фибвперед( М, N, F1, F2, F)

Здесь F1 и F2 - (М - 1)-е и М-е числа, а F - N-e число Фибоначчи.

Отношения в последовательности

Рисунок 8. 4.  Отношения в последовательности Фибоначчи. "Конфигурация" изображается
здесь в виде большого круга и определяется тремя параметрами: индексом М и двумя
последовательными числами f( M-1) и f( М).

Все показанные ниже процедуры подсп1,

Упражнения

8. 1. Все показанные ниже процедуры подсп1, подсп2 и подсп3 реализуют отношение взятия подсписка. Отношение подсп1 имеет в значительной мере процедурное определение, тогда как подсп2 и подсп3 написаны в декларативном стиле. Изучите поведение этих процедур на примерах нескольких списков, обращая внимание на эффективность работы. Две из них ведут себя одинаково и имеют одинаковую эффективность. Какие? Почему оставшаяся процедура менее эффективна?
        подсп1( Спис, Подспис) :-
                начало( Спис, Подспис).
        подсп1( [ _ | Хвост], Подспис) :-
                                                % Подспис - подсписок хвоста
                подсп1( Хвост, Подспис).
        начало( _, [ ]).
        начало( [X | Спис1], [X | Спис2] ) :-
                начало( Спис1, Спис2).
        подсп2( Спис, Подспис) :-
                конк( Спис1, Спис2, Спис),
                конк( Спис3, Подспис, Cпис1).
        подсп3( Спис, Подспис) :-
                конк( Спис1, Спис2, Спис),
                конк( Подспис, _, Спис2).
8. 2.    Определите отношение
        добавить_в_конец( Список, Элемент, НовыйСписок)
добавляющее Элемент в конец списка Список; результат - НовыйСписок. Оба списка представляйте разностными парами.
Посмотреть ответ
8. 3.    Определите отношение
        обратить( Список, ОбращенныйСписок)
где оба списка представлены разностными парами.
Посмотреть ответ
8. 4.    Перепищите процедуру собрать из разд. 8.5.2, используя разностное представление списков, чтобы конкатенация выполнялась эффективнее.

---

---