Основы программирования на языке Turbo Prolog

/* составного  объекта                         */

domains

/* персональная  библиотека  =  книга (название, автор, издательство,год издания) */

   personal_library = book(title, author,  

                           publisher,  year)

   name, title, author, publisher = symbol

   year = integer

 

predicates

/* коллекция (имя коллекционера, библиотека) */

   collection(name,personal_library)

clauses

collection(kahn, book("The Computer and the Brain", "von Neumann", "Yale University Press",1958)).

 

collection(kahn, book("Symbolic Logic", 
"Lewis Carroll", "Dower Publications", 1958)).

 

collection(johnson, book("Database: A Primer", 
          "C.J.Date", "Addison-Wesley", 1983)).

 

collection(johnson, 
book("Problem-Solving Methods in AI", "Nils Nilsson", 
"McGraw Hill", 1971)).

 

collection(smith, book("Alice in Wonderland", "Lewis Carroll", "The New American Library", 1960)).

collection(smith, book("Fables of Aesop", 
        "Aesop-Calder", "Dover Publications", 1967)).

/*        Конец программы                    */

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

collection(smith,Books).

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

collection(Collector,book(Title,_,_,1967)).

Здесь свободными переменными являются уже Collector и Title. Подчерки (_) указывают на то, что нас не интересуют объекты с типами author и publisher.

Задайте вопрос:

как зовут коллекционера, которому принадлежит книга «Database.A Primer."?

collection(Collector,book("Database:A Primer", _,_,_)).

Каковы названия книг, опубликованных после 1980 года?

collection(_,book(Title,_,_,Year)), Year > 1980.

5. ИСПОЛЬЗОВАНИЕ АЛЬТЕРНАТИВНЫХ ДОМЕНОВ

Представление данных часто требует наличия большого числа структур, и все они должны быть описаны. Чтобы один и тот же предикат мог работать с объектами разных типов, Турбо-Пролог предлагает альтернативные описания доменов. Программа 3.2 «Предметы» использует эти альтернативные описания:

/* Программа 3.2 «Коллекция». Назначение:      */

/* демонстрация  использования конструкций      */

/* альтернативных  доменов.                     */

domains

 

   thing = book(author,title) ;

          record(artist,album,type)

   name, author, title, artist, album = symbol

 

predicates

   owns(name, thing)

 

clauses

 

   owns("Bill", book("J.R.R. Tolkein", "Return of the Ring")).

   owns("Bill", record("Elton John", "Ice Fair")).

/*           Конец программы                 */

Для разделения альтернативных доменов здесь применена точка с запятой (;). Использование альтернативных доменов позволяет писать в утверждениях предикат owns применительно к различным классам вещей. В отсутствие этой конструкции требовалось бы ввести два разных предиката owns.

Упражнение 3.1.

Сформулируйте сокращенные внутренние запросы

1) перечислить  названия всех книг;

show_books :-

2) перечислить  все записии и их владельцев;

show_records :-

3) перечислить все предметы коллекции одного владельца, используя только предикат owns.

6. АРИФМЕТИКА В Turbo Prolog

Турбо-Пролог располагает двумя числовыми типами доменов: целыми и действительными числами. Четыре основные арифметические операции — это сложение, вычитание, умножение и деление, а также целочисленное деление div нахождение остатка целочисленного деления mod для целых чисел.

Стандартными математическими функциями являются следующие предикаты:

sin, cos, tan, round, trunc, abs.

/* Программа 3.3 ”Числа”. Назначение:  */

/* демонстрация  реализации арифметики. */

predicates

 

   add(integer,integer)

   substruct(integer,integer)

   multiply(integer,integer)

   divide(integer,integer)

   fadd(real,real)

   fsubstruct(real,real)

   fmultiply(real,real)

   fdivide(real,real)

 

goal

   write("        Results"), nl, nl,

   add(44,23),

   substruct(44,23),

   multiply(44,23),

   divide(44,23),

   fadd(12.65,7.3),

   fsubstruct(12.65,7.3),

   fmultiply(12.65,7.3),

   fdivide(12.65,7.3), nl,

   write("           All done, bye!").

 

clauses

   add(X,Y):-

      Z = X + Y, write("Sum = ",Z), nl.

  

   substruct(X,Y):

      Z = X — Y, write("Diff = ",Z), nl.

 

   multiply(X,Y):-

      Z = X * Y, write("Pro = ",Z), nl.

 

   divide(X,Y):-

      Z = X / Y, write("Quo = ",Z), nl.

 

   fadd(P,Q):-

      R = P + Q, write("Fsum = ",R), nl.

 

   fsubstruct(P,Q):-

      R = P — Q, write("Fdiff = ",R), nl.

 

   fmultiply(P,Q):-

      R = P * Q, write("Fpro = ",R), nl.

 

   fdivide(P,Q):-

      R = P / Q, write("Fquo = ",R), nl.

/*            Конец программы             */

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

ГЛАВА 4. ПРЕДИКАТ ОТСЕЧЕНИЯ (!). ПРОГРАММИРОВАНИЕ АЛЬТЕРНАТИВ. ПРАВИЛА ПОВТОРА

1. ПОВТОРЕНИЯ И ВОЗВРАТЫ

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

Итеративное правило имеет следующий вид:

iterative_rule :- % правило повторения

 <предикаты и правила>,

 fail. % неудача

Встроенный предикат fail(неудача) вызывает возврат, поэтому <предикаты и правила> выполняются до тех пор, пока не будут перебраны все способы их повторного согласования.

Рассмотрим задачу о генерации платежной ведомости почасовых выплат кафедры ВТиПМ (пример 4.1).

Пример 4.1.

Предикат базы данных имеет вид:

/* преподаватель(имя, кафедра, почасовая_оплата, часы) */

prep(name, faculty, pay, hours)

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

culc_sum(Pay, Hours, Sum_pay):-

 Sum_pay=Pay*Hours.

Задача правила report (выдать отчет о выплатах) заключается в формировании отчета. Оно вызывает правило culc_sum для вычисления выплат, затем предикат write для печати информации о преподавателе, затем fail инициирует возврат к следующему утверждению prep.

/*Программа 4.1 «Платежная ведомость». Назначение:*/

/*демонстрация  метода возврата после неудачи   */

domains

 

  name, faculty = symbol

  pay, hours, sum_pay = real

 

predicates     

 

  prep(name, faculty, pay, hours)

  report

  culc_sum(pay, hours, sum_pay)

 

goal

  write("Отчет  о выплатах "),

  nl, report.

 

clauses

 

prep("Иванов ", "ОМД",3.50,40.00).

prep("Петров ", "ВТиПМ",4.50,36.00).

prep("Сидоров ", "ВТиПМ",5.00,40.00).

prep("Данилов ", "ПКиСУ",4.50,25.50).

 

report :-

   prep(N, ”ВТиПМ”, P,H),

   culc_sum(P,H,S),

   write(N,," $", S),nl,

   fail.

              

culc_sum(P,H,S):-

   S = P * H.

/*           Конец программы              */

Упражнение 4.1.

Для программы 4.1 напишите правило генерации списка всех преподавателей, у которых почасовая оплата 5 долларов.

2. ОТСЕЧЕНИЕ (!)

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

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

Поэтому необходимо уметь его ограничить или исключить вовсе.

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

Более точно, отсечение имеет два побочных (т.е. проявляемых при возврате) эффекта:

1. БЛОКИРУЕТ  ВОЗВРАТ К ПРЕДШЕСТВУЮЩИМ ЕМУ  ПОДЦЕЛЯМ В ДАННОМ УТВЕРЖДЕНИИ.

правило1:-

 согласована подцель1, передоказать

 согласована подцель2, нельзя

 !,

согласована подцель3, попытка передоказать

отказ подцель4.

2. ЗАПРЕЩАЕТ  ИСПОЛЬЗОВАНИЕ ВСЕХ УТВЕРЖДЕНИЙ  ДАННОЙ ПРОЦЕДУРЫ, КОТОРЫЕ В БАЗЕ  ДАННЫХ НАХОДЯТСЯ ПОСЛЕ ДАННОГО.

 правило1:- передоказать

согласована подцель1, нельзя

 !,

отказ подцель2.

 

 правило1:- передоказать

 <.......>.

 правило1:- нельзя

 < .......>.

Действие отсечения превращает процедуру, способную генерировать альтернативные варианты означивания переменных цели (такая процедура называется НЕДЕТЕРМИНИРОВАННОЙ), в процедуру, порождающую лишь один ответ (ДЕТЕРМИНИРОВАННУЮ).

3. ПРОГРАММИРОВАНИЕ АЛЬТЕРНАТИВ

Рассмотрим кусочно-гладкую функцию (пример 4.2).

Пример 4.2.

f(x)=0, если x<3.

f(x)=1, если 3<=x<=5.

f(x)=0, если x<5.

Функция определяется тремя взаимоисключающими правилами.

Воспользуемся декларативным принципом Пролога —

КАЖДОЙ АЛЬТЕРНАТИВЕ — СВОЕ УТВЕРЖДЕНИЕ:

f(X,0):- X<3.

f(X,1):- X>=3, X<=5.

f(X,2):- X>5.

При запросе

goal

   f(1,Y), Y>2.

первое правило даст отказ, затем будут проверены второе и третье, затем система ответит «нет».

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

f(X,0):- X<3,!.

f(X,1):- X<=5,!.

f(X,2):- X>5.

Если сейчас мы ПОМЕНЯЕМ МЕСТАМИ УТВЕРЖДЕНИЯ, ТО МОЖЕТ ИЗМЕНИТЬСЯ ТОЛЬКО ЭФФЕКТИВНОСТЬ ПРОГРАММЫ, НО НЕ ЕЕ ПРАВИЛЬНОСТЬ.

Отсечения, которые меняют процедурное поведение программы, но не ее декларативный смысл, называются ЗЕЛЕНЫМИ.

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

f(X,0):- X<3,!.

f(X,1):- X<=5,!.

f(X,2).

Теперь ПРИ ПЕРЕСТАНОВКЕ УТВЕРЖДЕНИЙ ПРОГРАММА БУДЕТ ДАВАТЬ НЕВЕРНЫЕ РЕЗУЛЬТАТЫ.

Отсечения, которые меняют декларативный смысл программы, называются КРАСНЫМИ.

Далеко не всегда возникает необходимость в использовании «красных» отсечений. Запрограммируем функцию, выбирающую максимум из двух чисел (пример 4.3)

Пример 4.3.

max(real,real,real).

max(X,Y,Y):-

   Y>=X,!.    % «зеленое отсечение»

max(X,Y,X):-

   Y<X.

Перепишем ее с использованием «красного» отсечения:

max(X,Y,Y):-

   Y>=X,!.    % ”красное отсечение”

max(X,Y,X).

При запросах типа max(3,7,M) процедура будет вести себя правильно, но на запрос max(3,7,3) (максимум из 3 и 7 равен 3 ?) система ответит «да»...

Исправим процедуру:

max(X,Y,M):-

   Y>=X,!,M=Y. 

max(X,Y,X):-

   Y<X.

Но лучшим решением все же был первый вариант с использованием «зеленого» отсечения.

Рассмотрим «геометрический» пример на использование альтернатив (пример 4.4)

Пример 4.4.

На плоскости задан круг радиуса R, вписанный в квадрат с центром в начале координат. Сколько точек, брошенных на плоскость, попадут:

— вне квадрата;

— внутрь круга;

— вне круга, но внутри квадрата.

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

/* Программа 4.2 «Точка». Назначение:     */

/* демонстрация  использования отрицания   */

/* при  программировании альтернатив.      */

predicates

 

   show_point  % показать точку

   %вычисление места точки

   pos_point(real,real,real)

   out_sqr(real,real,real) % вне квадрата 

   in_circ(real,real,real) % внутри круга

 

goal

   show_point.

 

clauses

 

   show_point:-                  

      write(" R? "), readreal(R),

      write(" X? "), readreal(X),

      write(" Y? "), readreal(Y),

      pos_point(X,Y,R).

 

   pos_point(X,Y,R):-

      out_sqr(X,Y,R),

      write(" вне квадрата"), nl.          

   pos_point(X,Y,R):-

      in_circ(X,Y,R),

      write("внутри круга"), nl.

   pos_point(X,Y,R):-

      not(out_sqr(X,Y,R)),

      not(in_circ(X,Y,R)),

      write("вне круга,внутри квадрата"),nl.

 

   out_sqr(X,Y,R):-        % точка вне квадрата

      abs(X)>R;

      abs(Y)>R.

              

   in_circ(X,Y,R):-        % точка  внутри круга

               X*X+Y*Y<R*R.            

/*        Конец программы                   */

Упражнение 4.2.

Модифицировать программу 4.2, использовав отсечение ! вместо отрицания not при программировании альтернатив.

Теперь будем запрашивать точки в цикле.

Испробуем наш испытанный метод — возврат после неудачи:

show_point:-                  

   write(" R? "), readreal(R),

   write(" X? "), readreal(X),

   write(" Y? "), readreal(Y),

   pos_point(X,Y,R),

   fail.

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

4. ПРАВИЛО ПОВТОРА

Попытаемся заставить правило show_point читать ряд значений координат точки. Организуем бесконечный цикл с именем repeat:

repeat.                 

repeat :- repeat.

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

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

Вставим его в правило show_point:

show_point:-

   repeat,

   readreal(X),readreal(Y),

   <.....................>,

   fail.

Чтобы превратить этот бесконечный цикл в цикл с постусловием, поступим так:

show_point:-

   repeat,

   <................>,

   < условие выхода >,

   !.

Если < условие выхода > дает отказ, то происходит возврат к repeat; если же условие выхода успешно согласовывается, то отсечение не дает осуществить возврат к repeat, цель show_point дает отказ, и запросы прекращаются.

/* Программа 4.3 «Точки». Назначение:         */

/* демонстрации  использования правила повтора */

predicates

 

   show_point

   repeat

   pos_point(real,real,real)

   out_sqr(real,real,real)

   in_circ(real,real,real)

 

goal

   show_point.

 

clauses

 

   show_point:-        

      write(" R? "), readreal(R), 

      repeat,

      write(" X? "),readreal(X),

      write(" Y? "),readreal(Y),

      pos_point(X,Y,R), % условие выхода

      !.

           

   repeat.              % бесконечный цикл