Программирование на языке Prolog

 

Пример 8

 

Программе, описанной в  Примере 7, задается вопрос:

dog(X).

В качестве ответа будет  получен результат:

 

X =jek

X= rex

X= holly

 

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

Конъюнктивный вопрос – это конъюнкция целей, поставленная в виде вопроса. Подцели отделяются друг от друга запятой.

 

Пример 9

 

dog(jek),dog(rex),dog(X).

 

Простой вопрос является частным  случаем конъюнктивных вопросов с единственной целью. В простейшем конъюнктивном вопросе все подцели  простые. 

Правило  - это утверждение вида A¬B₁, B₂,…,B_n, где n³0. A называется заголовком правила, а B₁, B₂,…,B_n  - телом правила. Как A, так и B_i должны быть целями. Правило состоит из одной головной цели и одной или более хвостовых целей, которые истинны при некоторых условиях.

Правило обычно имеет несколько  хвостовых целей в форме конъюнкции целей. Конъюнкцию можно рассматривать  как логическую функцию И. Таким образом, правило согласовано, если согласованы все его хвостовые цели.

 

Пример10

 

dog(X) :- parent(X,Y),dog(Y).     // X является собакой, если у него есть родитель Y и Y - собака        

homo(Х) :-men(Х).                      // X – человек, если X – мужчина

 

Разница между правилами  и фактами чисто семантическая. Хотя, для правил мы используем синтаксис операторов (более подробное рассмотрение операторного и процедурного синтаксисов выходит за рамки курса), нет никакого синтаксического различия между правилом и фактом.

Так, правило:

 

dog(X) :- parent(X,Y),dog(Y).     может быть задано как

:- dog(X)’,’ parent(X,Y)’,’dog(Y).

Запись верна, поскольку :- является оператором “при условии, что”, а ',' - это оператор конъюнкции. Однако удобнее записывать это как:

 

dog(X) :- parent(X,Y),dog(Y).

 

и читать следующим образом: “ Х - собака при условии, что родителем  Х является Y и Y - собака”.

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

 

Пример 11

 

Родственное отношение «внук» можно описать так:

 

vnuk(X,Y):-fath(Y,Z),fath(Z,X). // X- внук Y, если Y – отец Z и Z – отец X

vnuk(X,Y):-moth(Y,Z),fath(Z,X). //X- внук Y, если Y –мать Z и Z – отец X

vnuk(X,Y):-fath(Y,Z),moth(Z,X). //X- внук Y, если Y –отец Z и Z – мать X

vnuk(X,Y):-moth(Y,Z),moth(Z,X). //X- внук Y, если  –мать Z и Z –мать X

 

Однако, то же самое отношение  можно записать компактнее, определив  «промежуточное» отношение parent (родитель):

 

parent(X,Y):- fath(X,Y). //X – родительY, если X – отец Y

parent(X,Y):-moth(X,Y). //X – родительY, если X – мать Y

Тогда родственное отношение  «внук» можно определить так:

  vnuk(X,Y):- parent(Y,Z), parent(Z,X).         

 

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

Простой абстрактный  интерпретатор.

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

Абстрактный интерпретатор выполняет вычисления с ответами «да/нет». Он получает программу P и основной вопрос Q и дает ответ да, если Q выводимо из P, и ответ нет, в противном случае. Кроме того, если цель не выводима, интерпретатор может вообще не завершить работу. В этом случае не выдается никакого ответа. Работу интерпретатора схематично можно описать следующим образом:

 

Вход:                           Основной вопрос Q и программа P

Результат:                   да, если найден вывод Q из программы P,

                                    нет – в противном случае

Алгоритм:                  Положить резольвенту равной Q.

Пока резольвента A1,A2,…,An не пуста –

начало цикла

Выбрать цель Ai, 1 £ i  £  n, и такой основной пример

предложения  A¬B1,B2,…,Bk, где k³0 в Р, что A=Ai

(если такого предложения  нет - выйти из цикла);

положить резольвенту  равной

A1,…,Ai-1, B1,…,Bk ,Ai+1,…,An

конец цикла

если резольвента пуста, то результат – да, иначе результат  – нет.  

 

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

Рассмотрим протокол поиска ответа на примере.

 

Пример 12

 

Программа, определяющая родственное  отношение «сын»:

 

fath(abram,isak).

fath(aran,lot).

men(abram).

men(lot).

men(isak).

sun(X,Y):-fath(Y,X),men(X).

Вопрос: sun(lot, aran)                                

Протокол интерпретатора:

Вход: sun(lot, aran) и программа

Резольвента не пуста

 Выбор: sun(lot, aran) (единственный выбор)

 Выбор: sun(lot, aran):- fath(aran,lot), men(lot).      Новая резольвента: fath(aran,lot), men(lot).

Резольвента не пуста.

    Выбор: fath(aran,lot)                                // первая подцель в новой резольвенте

   Выбор: fath(aran,lot).                               //из двух фактов fath(abram,isak), fath(aran,lot) подходит последний

Резольвента не пуста.

Выбор: men(lot)                                       // вторая подцель в новой резольвенте

Выбор: men(lot).                                     //из трех фактов men(abram), men(isak),men(lot)  подходит последний

Новая резольвента пуста.

Результат: да

3 Ход работы

3.1Построение треугольника Паскаля

 

Пример  выполнения:

 

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

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

 

 

Ход выполнения:

 

Был создан проект под названием  «ТреугольникПаскаля» (рисунок 3), состоящий из основного окна Task Window и трех диалоговых окон: AboutDialog, Help, MyDialog. В окне MyDialog  пользователь будет вводить требуемый уровень треугольника и нажимать на кнопку OK для отображения соответствующего треугольника на экран. Для создания диалоговых окон необходимо нажать на кнопку Dialog в окне проекта, создать нужное диалоговое окно и разместить нужные элементы управления на нем (пример окна MyDialog на рисунок 4.

Двойным щелчком мыши на кнопке OK открывается окно атрибутов  данной кнопки (рисунок 5), в котором можно установить соответствующие атрибуты, включая и идентификатор данного элемента (в нашем случае idc_ok). Именно для данного идентификатора будет прописан основной код программы. Идентификатор для поля ввода текста зададим idc_mydialog_1. Для перехода к написанию кода для данного объекта в окне проекта (рисунок 6) необходимо нажать кнопку Dialog, выбрать нужное диалоговое окно и нажать на кнопку CodeExpert в результе чего будет открыто окно Dialog and Window Expert (рисунок 7). Для перехода к написанию кода элемента управления необходимо в секции Dialog or Window Selection выбрать соответствующее окно (в нашем случае выбрано диалоговое окно MyDialog). В секции Place Source Code in… выбрать модуль проекта (в нашем случае выбран проект ТреугольникПаскаля.pro). В списке типа событий Event Type выбрать нужный тип (в нашем случае выбран Control – элементы управления), в списке Event or Item (событие или элемент) выбрать нужную позицию (в нашем случае выбран идентификатор кнопки OK – idc_ok). После указанных действий необходимо нажать на кнопку Edit Clause – редактировать правила (рисунок 7). Если правила для события или элемента еще не существовали, то кнопка Edit Clause первоначально называется Add Clause – добавить правила.

 

Рисунок 3 - Окно проекта

 

Рисунок 4 - Окно MyDialog

 

Рисунок 5 - Атрибуты кнопки Ок

 

 

Рисунок. 7 - Dialog and Window Expert

 

 

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

 

Рисунок 8 - Редактор кода

 

domains

r=real    % задаем r типа real (действительные числа)

s=string   % задаем s типа string (строки)

predicates

nondeterm calculate1(r,r) 

nondeterm calculate2(r,r,r,r,r,r,r,r)

nondeterm proverka (s)

% определяем предикаты calculate1, calculate2, proverka. Ключевое слово nondeterm означает, что данные предикаты недетерминированные, т.е. для каждого из объявленных предикатов существует более одной альтернативы. Предикат calculate1(номер уровня введенный пользователем, номер уровня в «данный момент») отвечает за проверку достижимости требуемого уровня. Предикат calculate2(номер уровня введенный пользователем, номер уровня в данный момент, искомый элемент данного уровня, …вспомогательные переменные).

 

Clauses

% обработка нажатия кнопки  Ok

dlg_mydialog_eh(_Win,e_Control(idc_ok,_CtrlType,_CtrlWin,_CtlInfo),0):-!,

EDIT_WIN=win_GetCtlHandle(_WIN,idc_mydialog_1), P=win_GetText(EDIT_WIN), proverka(P),!.

proverka (P):- str_real(P,P1),!,nl, write ("Треуголик Паскаля с уровнем равным ",P),calculate1(P1,1),!.

proverka(P):- dlg_MessageBox("Ошибка","Вы должны ввести ЧИСЛО большее 0 ",2,0,0,0).

calculate1(X,N):- X<=0,nl,write ("Ошибка!!!Введите положительное целое число, большее 0").

calculate1(X,N):- N<=X,nl,calculate2(X,N,1,0,1,N,1,0),!.

calculate2(X,N,X1,Y1,Z1,T1,F1,F3):- X1>0, write (X1," "), Y2=Y1+1,Z2=Z1*Y2,

T2=T1-F3,F2=F1*T2,X2=F2/Z2,F4=F3+1, !,calculate2(X,N,X2,Y2,Z2,T1,F2,F4).

calculate2(X,N,X1,_,_,_,_,_):- N1=N+1,calculate1(X,N1).

 

Работу программы можно  описать следующим образом: в  переменную Edit_WIN передаем управление компонентом mydialog_1 (поле ввода требуемого уровня), который имеет идентификатор idc_mydialog_1. В P мы записываем значение, введенное пользователем, используя встроенный предикат win_GetText. Далее вызываем предикат proverka, предназначенный для проверки корректности введенного пользователем значения. Для этого используется встроенный предикат str_real, который переводит переменные типа string в переменные типа real. В случае успеха в переменную P1 записывается значение пользователя, но уже в числовом виде и происходит вызов предиката calculate1, который совместно c предикатом calculate2 отвечают за нахождение элементов треугольника. В случае неудачи выдается соответствующее сообщение, извещающее пользователя о необходимости ввода только чисел. При вызове предиката calculate1 переменная X содержит значение введенного пользователем уровня, а переменная N содержит номер уровня на текущий момент поиска решения. При успешной проверке X<=N (то есть требуемый уровень еще не достигнут) происходит вызов предиката calculate2. Предисат calculate2 рекурсивно вычисляет элементы очередного уровня треугольника Паскаля. По окончании вычислений всех элементов очередного уровня вторая альтернатива предиката calculate2 вызывает предикат calculate1 с увеличенным на единицу значением уровня треугольника. Программа завершает свою работу по мере достижения требуемого уровня.

Основной код программы  прописан, но он сработает только после  нажатия на кнопку OK диалогового окна MyDialog, которое пользователю еще необходимо вызвать. В нашем проекте вызов диалогового окна будет производиться нажатием одного из пунктов меню. Для этого необходимо в окне проекта (рисунок 3) нажать на кнопку Menu, двойным щелчком открыть окно меню, в котором создать дополнительный пункт (рисунок 9.) при помощи кнопки New (в нашем проекте был создан пункт меню Paskal) и установить соответствующие атрибуты пункта меню, включая его идентификатор (в нашем случае id_paskal).

 

Рисунок 9 - Окно редактирования меню проекта

 

Для перехода к редактору  кода данного пункта меню необходимо проделать операции аналогичные  действиям описанным для перехода к коду кнопки OK, но при этомнеобходимо выбрать окно Task Window, выбрать в списке Event Type позицию Menu, в списке Event or Item выбрать идентификатор нужного пункта меню (в нашем проекте это id_paskal, рисунок 10) и нажать соответствующую кнопку для перехода к редактору кода.

 

Рисунок 10 - Dialog and Window Expert

В редакторе кода необходимо прописать вызов диалогового  окна MyDialog:

 

task_win_eh(_Win,e_Menu(id_paskal,_ShiftCtlAlt),0):-!,

dlg_mydialog_Create(_Win),!.

 

Для запуска проекта необходимо нажать на клавиатуре кнопку F9 либо соответствующие кнопки в меню или на панели инструментов.

При запуске программы, пользователь вызывает окно MyDialog нажатием кнопки Paskal меню. В появившемся окне пользователь вводит требуемый уровень и нажимает на кнопку OK. В окне Messages выводится результат выполнения программы (рисунок 11).

 

Рисунок 11 - Результат работы Prolog-программы

 

Вывод:

 

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

 

 

3.2 Работа со списками

 

Задание: Объединить два списка, найти максимальный элемент и удалить его.

 

Ход выполнения:

 

В среде Visual Prolog 5.2 создан соответствующий  проект.

 

Логика программы:

 

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