ТП.Отчет программиста

Отчёт SWI-Prolog программистов

Программисты: Минюров Евгений, Шарипов Денис.

1. Постановка задач

Задача: написать два серверных модуля: модуль для работы сервера и модуль решателя для игры «Восемь».

1.1 Функции модуля для работы сервера

1. Запуск сервера;

2. обмен сообщениями между сервером и клиентом;

3. остановка работы сервера.

1.2 Функции модуля решателя

1. Получение сообщения от клиента;

2. обработка полученного сообщения;

3. построение графа поиска решения игры;

4. передача сообщения клиенту.

2. Выполнение

2.1 Подготовительная часть

Для знакомства с сервером SWI-Prolog были разработаны следующие учебные программы:

• повторяющиеся вычисления;

• обмен сообщения с сервером SWI-Prolog;

• синхронные и асинхронные AJAX-запросы.

Исходный код этих программ приведён в Приложении (ссылка на приложение; смотри конец отчёта).

Написанные программы помогли получить общее представление о клиент-серверных технологиях конкретно в SWI-Prolog. Кроме того, с их помощью на начальных этапах осуществлялось предварительное тестирование программы на предмет работоспособности.

2.2 Основная часть

Все заданные функции спроектированных модулей были успешно реализованы. В процессе работы возникли небольшие трудности, поэтому совместно стал работать менеджер проекта Вахитов Антон.

Исходный код приведён в Приложении (ссылка на приложение).

Приложение №1. Учебные программы

1. Повторяющиеся вычисления

1.1 Операторы fail и repeat

run:-

repeat,nl,

write('Вводите слова, я буду повторять их'), nl,

write('Если хотите остановить меня, введите stop.'), nl,

read(X), check(X),

nl,write('Ok, bye!').

check(stop).

check(X):-

X \= 'stop', nl,write(X),

fail.

?- run.

1.2 Рекурсивный вызов функции

list1([student('Ivanov','Otlichnik'),

student('Petrov','Horoshist'),

student('Ivanov','Troechik') ]).

run:- list1(Ls),

show_list(Ls),

nl,write('OK, bye').

show_list([]).

show_list([H|Ts]):-

process1(H),

show_list(Ts).

process1(student(Name,Mark)):-

nl,

write(Name),write(' - '),write(Mark).

?- run.

2. Обмен сообщения с сервером SWI-Prolog

2.1 Отображение текста

:- use_module(library(http/thread_httpd)).

:- use_module(library(http/http_dispatch)).

:- http_handler(root(hello_world), say_hi, []).

server(Port) :-

http_server(http_dispatch, [port(Port)]).

say_hi(_Request) :-

format('Content-type: text/plain~n~n'),

format('Hello World!~n').

2.2 Обмен html-сообщениями

:- use_module(library(http/thread_httpd)).

:- use_module(library(http/http_dispatch)).

:- use_module(library(http/http_error)).

:- use_module(library(http/html_write)).

:- http_handler('/', say_hi, []).

server(Port) :-

http_server(http_dispatch, [port(Port)]).

say_hi(_Request):-

reply_html_page([title('Buttons'),h1('Это обмен сообщениями')],

[form('name="ButtonsPlace"',''),

script('type="text/javascript"', 'function Add()

{var element=document.createElement("input");

element.setAttribute("type", "radio"); element.setAttribute("name", "feed");

document.ButtonsPlace.appendChild(element);

var label=document.createTextNode("Line");

document.ButtonsPlace.appendChild(label);

var br = document.createElement("br");

document.ButtonsPlace.appendChild(br);}'),

button('onclick="Add()"','Make')

]).

3. Синхронные и асинхронные AJAX-запросы

3.1 Синхронный AJAX-запрос

:- use_module(library(http/thread_httpd)).

:- use_module(library(http/http_dispatch)).

:- use_module(library(http/http_error)).

:- use_module(library(http/html_write)).

:- http_handler('/', say_hi, []).

server(Port) :-

http_server(http_dispatch, [port(Port)]).

say_hi(_Request):-

reply_html_page([title('Buttons'),h1('Это обмен сообщениями')],

[form('name="ButtonsPlace"',''),

script('type="text/javascript"', 'function Http()

{ var xmlhttp = new XMLHttpRequest(); xmlhttp.open("Get","/",false);

xmlhttp.send(); alert(xmlhttp.status); alert(xmlhttp.responseText); }'),

button('name=ad onclick="Http()"','Make')]).

3.2 Асинхронный AJAX-запрос

:- use_module(library(http/thread_httpd)).

:- use_module(library(http/http_dispatch)).

:- use_module(library(http/http_error)).

:- use_module(library(http/html_write)).

:- http_handler('/', say_hi, []).

server(Port) :-

http_server(http_dispatch, [port(Port)]).

say_hi(_Request):-

reply_html_page([title('Buttons'),h1('Это обмен сообщениями')],

[form('name="ButtonsPlace"',''),

script('type="text/javascript"', 'function Http()

{ var xmlhttp = new XMLHttpRequest(); xmlhttp.open("Get","/",true);

xmlhttp.send(); alert(xmlhttp.status); alert(xmlhttp.responseText); }'),

button('name=ad onclick="Http()"','Make')]).

Приложение №2

1. Модуль решателя задач

:- module(p8,[g/1]).

:-use_module(srv8).

/***************************************************************************

пролог-программа эвристического поиска: головоломка "Игра в восемь"

***************************************************************************/

:- dynamic dN/1, dmax_f/1.

/*

goal(StState) :-

start, % запускаем сервер

g(StState). % решаем задачу

*/

g(StartState):-

retractall(dN(_)),

retractall(dmax_f(_)),

assert(dN(0)),

assert(dmax_f(100)),

%startState(StartState), % статический тест

evrpoisk(StartState,Reshenie),

%delete(Reshenie,StartState,Reshenie1),%только при запуске кнопкой

reverse(Reshenie,Reshenie2), %reverse(Reshenie1,Reshenie2),

pokazresh2(Reshenie2).

evrpoisk(Start,Reshs):-

dmax_f(Fmax),

rasshirit([],lis(Start,0/0),Fmax,_,yes,Reshs).

rasshirit(Ps,lis(B,_),_,_,yes,[B|Ps]):-

addN,

dmax_f(Fmax), checkM(B,Fmax).

rasshirit(Ps,lis(B,F/G),Predel,Der1,IsResh,Reshs):-

F =< Predel,

( bagof(B1/C, arc2(B,B1,C,Ps), Preemniks),!,

preemspis(G,Preemniks,DDs),

opt_f(DDs,F1),

rasshirit(Ps,der(B,F1/G,DDs),Predel,Der1,IsResh,Reshs);

IsResh=nikogda %нет преемников - тупик

).

rasshirit(Ps,der(B,F/G,[D|DDs]),Predel,Der1,IsResh,Reshs):-

F =< Predel,

opt_f(DDs,OF),

minn(Predel,OF,Predel1),

rasshirit([B|Ps],D,Predel1,D1,IsResh1,Reshs),

prodoljit(Ps,der(B,F/G,[D1|DDs]),Predel,Der1,IsResh1,IsResh,Reshs).

rasshirit(_,der(_,_,[]),_,_,nikogda,_):- !. %тупиковое дерево - нет решений

rasshirit(_,Der,Predel,Der,no,_):- f(Der,F), F > Predel. %рост остановлен

arc2(B,B1,C,Ps):- arc(B,B1,C), not(member(B1,Ps)). %антицикл

prodoljit(_,_,_,_,yes,yes,_). %Reshs

prodoljit(Ps,der(B,_/G,[D1|DDs]),Predel,Der1,IsResh1,IsResh,Reshs):-

( IsResh1=no,

vstav(D1,DDs,HDDs);

IsResh1=nikogda,

HDDs = DDs

),

opt_f(HDDs,F),

rasshirit(Ps,der(B,F/G,HDDs),Predel,Der1,IsResh,Reshs).

preemspis(_,[],[]).

preemspis(G0,[B/C|BBs],DDs):-

G is G0 + C,

h(B,H),

F is G + H,

preemspis(G0,BBs,DD1s),

vstav(lis(B,F/G),DD1s,DDs).

%вставка дерева D в список деревьев DDs

%с сохранением упорядоченности по f-оценкам:

vstav(D,DDs,[D|DDs]):-

f(D,F),

opt_f(DDs,F1),

F =< F1, !.

vstav(D,[D1|DDs],[D1|DD1s]):-

vstav(D,DDs,DD1s).

%получение f-оценки:

f(lis(_,F/_),F). %f-оценка листа

f(der(_,F/_,_),F). %f-оценка дерева

opt_f([D|_],F):- f(D,F). %наилучшая f-оценка для списка деревьев

opt_f([],Fmax):- dmax_f(Fmax). %плохая f-оценка: нет деревьев

minn(X,Y,X):- X =< Y, !.

minn(_,Y,Y).

%--------- отображение решающего пути через интерфейс к C++ -----------

pokazresh2([]).

pokazresh2([H|Ts]):-

process1(H),

pokazresh2(Ts).

process1(Ls):-

convert1(Ls,L1s), %конвертируем список операторов X/Y в список строк

concat_atom(L1s,',',AL),

sendToC(AL,Answer),

check(Answer).

convert1([],[]).

convert1([H1|T1s],[H2|T2s]):-

H1 = X/Y, %здесь символ "/" явл-ся ОПЕРАТОРОМ: надо превратить в строку

atom_concat(X, '/', X1),

atom_concat(X1, Y, XY),

XY = H2,

convert1(T1s,T2s).

check(1).

check(0). %потом сделать: check(0):- halt.

addN:- %RTTI + страховочный порог

dN(N),

integer(N),

N < 20000, %N < 28000,% предел ~30тыс. узлов

N1 is N+1,

retract(dN(_)),

assert(dN(N1)),!.

addN:-

%nl,write('Задача НЕ решена: размер графа больше 20000 узлов'),

%nl,write('Вот начало решения:'),

retract(dmax_f(_)), assert(dmax_f(1)),!.

checkM(_,Fmax):- Fmax =< 1, !.

checkM(B,_):- goalFin(B).

%====== динамически заданный эвристический граф для задачи "Игра в 8" ======

% задача решается методом разделения на подзадачи: стратегия "Разделяй и Властвуй"

arc([Pusto|Ls],[Fishka|L1s],1):- %стоимости всех дуг равны 1

perest(Pusto,Fishka,Ls,L1s). %переставив Pusto и Fishka, получаем L1s

perest(P,F,[F|Ls],[P|Ls]):- rasst(P,F,1).

perest(P,F,[F1|Ls],[F1|L1s]):- perest(P,F,Ls,L1s).

rasst(X/Y,X1/Y1,R):- %"расстояние" между клетками

rasst1(X,X1,Rx),

rasst1(Y,Y1,Ry),

R is Rx + Ry.

rasst1(A,B,R):-

R is A - B, R >= 0, !;

R is B - A.

%эвристическая оценка h равна сумме расстояний фишек от их "целевых" клеток

%плюс "степень упорядоченности", умноженная на 3:

h([_|Ls],H):- %h([Pusto|Ls],H) /*Singleton variables*/

goalFin([_|GLs]), %goal1([Pusto1|GLs]) /*Singleton variables*/

sumrasst(Ls,GLs,R),

uporyad(Ls,Up),

%H is R + 3*Up.

%H is R + 2*Up. %путь короче, но ищет дольше

H is R + Up. %путь еще короче, но ищет еще дольше

sumrasst([],[],0). %т.е. число фишек не на своем месте

sumrasst([F|Ls],[F1|L1s],R):-

rasst(F,F1,R1),

sumrasst(Ls,L1s,R2),

R is R1 + R2.

uporyad([First|Ls],U):-

upor2([First|Ls],First,U).

upor2([F1,F2|Ls],_,U):-

ochki2(F1,F2,U1),

upor2([F2|Ls],_,U2),

U is U1 + U2.

upor2([Last],_,U):- ochki2(Last,_,U).

ochki2(2/2,_,1):- !. %фишка в центре - 1 очко

ochki2(1/3,2/3,0):- !. %правильная последовательность - 0 очков

ochki2(2/3,3/3,0):- !.

ochki2(3/3,3/2,0):- !.

ochki2(3/2,3/1,0):- !.

ochki2(3/1,2/1,0):- !.

ochki2(2/1,1/1,0):- !.

ochki2(1/1,1/2,0):- !.

ochki2(1/2,1/3,0):- !.

ochki2(_,_,2):- !. %неправильная последовательность - 2 очка

goalFin([2/2,1/3,2/3,3/3,3/2,3/1,2/1,1/1,1/2]). %финишная ситуация

sendToC(AL,Answer):- nl,web_write(AL), Answer=1.

startState([3/2,1/2,1/3,3/3,2/2,3/1,2/1,1/1,2/3]). % статика, L=6ходов

%===========================================================================

%?- start(p8:g([3/2,1/2,1/3,3/3,2/2,3/1,2/1,1/1,2/3])).

%?- start, g([3/2,1/2,1/3,3/3,2/2,3/1,2/1,1/1,2/3]).

%?- goal([3/2,1/2,1/3,3/3,2/2,3/1,2/1,1/1,2/3]).

2. Модуль сервера

:- module(srv8,

[

start/0, %start/1,

s/0, %stop/0,

web_write/1,

debug_print/2

]).

:-use_module(library(http/thread_httpd)).

:-use_module(library(http/http_dispatch)).

:-use_module(library(http/http_json)).

:-use_module(library(http/http_files)).

:-use_module(p8).

% загружаем конфигурацию

%:-dynamic solver/1. % только при start/1

:-dynamic web_log/1.

debug_print(Format, Args) :-

format(user, Format, Args).

web_g(Request) :-

purgateAllSrv,

wstat(Request).

wstat([_,_,_,_,_,_,_,search([X1])|_]):-

term_to_atom(X1,A),

atom_to_chars(A,Str),

wstat3(Str,Str2),

parse(Str2,[],X3),

% del(X3,X4),

wstat2(X3).

del([_|Hs],Hs).

parse([],X3,X3).

parse([X,Z,Y,_|Hs],X3,X4):-

% S=[X,Z,Y],

% name(At,S),

atom_codes(X2,[X]),

atom_codes(Y2,[Y]),

conver(X2,I1),

conver(Y2,I2),

append(X3,[I1/I2],L3),

parse(Hs,L3,X4).

conver('1',1).

conver('2',2).

conver('3',3).

wstat3([_H1,_H2,_H3,_H4,_H5|X1],X1).

wstat2(X4):-

debug_print('запрос: ~p ~n',[X4]),

g(X4),

findall(X, web_log(X), Xs),

reply_json(Xs).

web_clear(_Request) :-

debug_print('очищаем историю сообщений Msg ~n', []),

retractall(web_log(_)),

format('Content-Type: text/plain~n~n', []).

start_web(Port) :-

http_handler('/', http_reply_from_files('www', []), [prefix]),

http_handler('/proba', web_g, []),

http_handler('/clear', web_clear, []),

http_server(http_dispatch, [port(Port)]).

start :-

purgateAllSrv,

start_web(8080).

purgateAllSrv :-

retractall(web_log(_)).

%retractall(solver(_)).

web_write(Msg) :-

format(atom(A), '~p', [Msg]), % in=Msg, out=A

assert(web_log(A)).

web_format(Format, Args) :- format(atom(Msg), Format, Args), web_write(Msg).

s :-

web_clear(_Request),

%thread_httpd:http_stop_server(8080,[]),

http_stop_server(8080,[]),

halt,!.

?- start.