-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathc_project(5s).txt
345 lines (279 loc) · 17.3 KB
/
c_project(5s).txt
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
Титул
ОГЛАВЛЕНИЕ
Список сокращения и условных обозначений 3
Введение 4
1 Среды выполнения языка prolog 5
2 Swi-prolog в деталях 7
3 Начало работы в SWI-Prolog 8
3.1 Командная строка 8
3.2 Синтаксис SWI-Prolog 8
4 Решение задач в среде SWI-Prolog 10
4.1 Алгоритмы сортировки 10
4.2 Теорема о четырех цветах 10
4.3 Задача о Ханойской башне 12
4.4 Простая экспертная система 13
4.5 Web приложение в SWI-Prolog 16
4.5.1 Реализация простого web api 18
4.5.2 Simple Web 18
5 Тестирование 22
Заключение 23
Список использованных источников и литературы 24
Приложение 25
СПИСОК СОКРАЩЕНИЯ И УСЛОВНЫХ ОБОЗНАЧЕНИЙ
AI – искусственный интеллект.
ISO – International Organization for Standardization.
BSD License – семейство лицензий бесплатного программного обеспечения.
GUI - graphical user interface.
SGML - Standard Generalized Markup Language.
RDF - Resource Description Framework.
RDFS - Resource Description Framework Schema.
IDE - integrated development environment.
SWI - Sociaal-Wetenschappelijke Informatica.
HTTP - Hypertext Transfer Protocol.
REST - Representational State Transfer.
HTML - HyperText Markup Language.
SVM - Support Vector Machine.
GOFAI - Good Old Fashioned Artificial Intelligence.
ВВЕДЕНИЕ
Целью курсового проекта является рассмотрение возможностей среды «SWI - prolog» для решения «интеллектуальных» задач на языке prolog. Несмотря на то, что язык prolog уже достаточно старый и не является фаворитов в изучении искусственного интеллекта, он до сих пор входит в списки языков, рекомендуемых к изучению AI и парадигмы логического программирования. Сама «open source» платформа «SWI - prolog» является одной из основных сред разработки на prolog. В ходе проекта будут рассмотрены следующие вопросы:
1. В чем различие между платформами?
2. Какие возможности предоставляет платформа «SWI - prolog»?
3. Подходит ли платформа для реализации различный алгоритмов и экспертных систем?
4. Подходит ли для реализации web сервисов и есть ли сторонние библиотеки?
5. Возможно ли тестировать код в SWI-Prolog?
Фрагменты кода, указанные в проекте доступны в репозитории на GitHub:
1 СРЕДЫ ВЫПОЛНЕНИЯ ЯЗЫКА PROLOG
Из-за того язык prolog изначально был плохо стандартизирован (это не точно) начали появляться различные его имплементации с радикально разным синтаксисом и разной семантикой вместе с сообществами разработчиков, работающих с определенной имплементацией. Текущий стандарт ISO состоит из двух частей, одна из которых как раз и нацелена на стандартизацию различных имплементаций языка, однако, несмотря на это большинство имплементации не следуют этому стандарту, что приводит к проблемам с совместимостью.
На данный момент существует два основных диалекта языка prolog:
1. ISO Prolog;
2. Edinburgh Prolog;
Таблица 1.
Список основных имплементаций:
НаименованиеОСЛицензияУправление системойИнтерфейс ССинтаксисBPrologUnix, Windows, Mac OS XFree for non-commercial uses++ISO-Prolog, plus event-handling, CLP(FD), and tablingCiaoUnix, Windows, Mac OS XGPL, LGPL++ISO-Prolog, plus extensionsDOS-PROLOGMS-DOSShareware+-Edinburgh PrologECLiPSeLinux, Windows, Solaris, macOSMPL++Extended Prolog, Multi-dialect, including ISOGNU PrologUnix, Windows, Mac OS XGPL, LGPL++ISO-PrologJekejeke PrologJVM, AndroidDistribution Evaluation+-ISO-Prolog, Java APIНаименованиеОСЛицензияУправление системойИнтерфейс ССинтаксисJIPrologJVM, AndroidShareware/Commercial and AGPL++(java)ISO-PrologJLogJVMGPL--ISO-PrologJScriptLogWeb BrowserGPL--ISO-PrologjTrologJVMLGPL--ISO-PrologLPA-PROLOGWindowsCommercial++Edinburgh Prolog with extensionsOpen PrologMac OSFreeware--SWI-PrologUnix, Linux, Windows, macOSBSD License++ISO-Prolog, Edinburgh PrologVisual PrologWindowsFreeware, Commercial++XSB PrologLinux, Windows, Solaris, macOSLGPL++ISO-Prolog, tabled WFSYAP-PrologLinux, Windows, Solaris, Mac OS X, HP-UXGPL or Artistic (user choice)++Edinburgh, ISO-Prolog, Quintus and SICStus Prolog compatible
Существует еще много других менее популярный имплементаций.
2 SWI-PROLOG В ДЕТАЛЯХ
SWI-Prolog – реализация языка prolog. Надежные многопоточные, расширенные типы данных, неограниченная арифметика и представление текста в Юникоде позволяет представлять документы в форматах XML, JSON, RDF. Низкоуровневый интерфейс с языком С служит основой для высокоуровневой интеграции в такие языки, как С++, Java, Python. Имеет большое количество функций, библиотек, включая тестирование, GUI, web server, SGML, RDF, RDFS, IDE, debugger.
SWI-Prolog «комплектуется» расширяемым web сервером (HTTP), позволяющий писать REST сервисы и клиентские приложения, основанные на HTML, CSS, JS.
SWI-Prolog предоставляет «add-on distribution» и механизм установки расширений, названный «packs». Pack используется для обмена кодом среди сообщества.
SWI-Prolog находится в разработке с 1987 года. Главный автор Jan Wielemaker. Название SWI-Prolog – это аббревиатура для Sociaal-Wetenschappelijke Informatica.
Далее в проекте будет использованная версия SWI-Prolog 7.7.23.
3 НАЧАЛО РАБОТЫ В SWI-PROLOG
В данном проекте не будут затронуты такие темы, как установка и настройка. Подробнее об это смотрите в официальной документации.
3.1 Командная строка
По уполчанию SWI-Prolog устанавливается, как «swipl». Аргументы командной строки SWI-Prolog и внутренних утилит задокументированы в стандартной Unix man форме. Для запуска программы нужно ввести следующие команду:
$ swipl
Welcome to SWI-Prolog ...
...
После начала работы обычно загружается файл используя предикат «consult/1», который может быть сокращен до имени файла в квадратных скобках.
?- [likes].
true.
В качестве альтернативы исходный файл может задан, как аргумент командной строки.
$ swipl likes.pl
Welcome to SWI-Prolog ...
...
Для остановки программы есть два пути:
1. Ввод стандартного символа остановки файла (обычно «Control-D»);
2. Выполнить предикат «halt.».
3.2 Синтаксис SWI-Prolog
Синтаксис SWI-Prolog близок к стандарту ISO-Prolog, который базируется на Edinburgh Prolog. Формальное описание дано в стандарте ISO.
SWI-Prolog позволяет использовать вложенные «/* ... */» комментарии. ISO стандарт принимает подобный синтаксис.
4 РЕШЕНИЕ ЗАДАЧ В СРЕДЕ SWI-PROLOG
4.1 Алгоритмы сортировки
В стандарте ISO есть предикаты «sort/2» и «keysort/2», которые являются наиболее важными предикатами для сортировки в prolog. Поведение этих предикатов описано в спецификации.
Иногда возникает потребность в написании собственных алгоритмов сортировки.
Рисунок 1. «Пузырьковая сортировка»
Рисунок 2. «Быстрая сортировка»
4.2 Теорема о четырех цветах
Теорема о четырех цветах (также известная, как «Guthrie’s problem») одна из классический задач, которая оставалась нерешенной на протяжении приблизительно ста двадцати четырех лет и считалась очень сложной проблемой до тех пор, пока Кеннет Аппель и Вольфганг Хакен не предложили решение. Теорема утверждает, что, как бы не была разделена плоскость, достаточно всего четыре цвета, чтобы ни одна область не имела соседа с точно таким же цветом.
Для начала определим границы каждой области, как факт в нашей базе знаний. Предикат «neighbours» определяет список соседей области. В качестве областей будут взяты страны Евросоюза.
Рисунок 3. «Определение соседей»
Далее необходимо указать точку входа в программу. В ней использует предикат «setof», чтобы создать список, где каждый элемент в форме «Страна/Х». Затем вызывается предикат «colours», который привяжет каждый Х в списке к подходящему цвету.
Рисунок 4. «Точка входа»
Предикат «colours» выбирает значение для переменной «Colour» из списка кандидатов, затем проверяет есть ли совпадение у соседей.
Рисунок 5. «Предикат «colours»»
Предикат «neighbour» определяет являются ли данные ему страны соседями.
Рисунок 6. «Предикат «neighbour»»
Предикат «member» является стандартной функцией, определяющей, является ли первый аргумент частью второго, как элемент списка.
Рисунок 7. «Предикат «member»»
Теперь при выполнении предиката «colour_countries» будет выведет список список, состоящий из элементов типа «страна/цвет».
Рисунок 8. «Результат выполнения предиката «colour_countries»»
4.3 Задача о Ханойской башне
Задача о Ханойской башне была изобретена Эдуардом Лукасом в 1893 году. Он также придумал романтическую историю об этой башне.
Рисунок 9. «Задача о Ханойской башне»
Предикат «move» принимает 5 аргументов, где N – количество дисков, Х – стартовый столб, Y – вспомогательный столб, Z – конечный столб и P это список передвижений n – го диска из X к Z.
После выполнения данного предиката «move(3, X, Y, Z, P).» будет получен следующий результат «P = [[X, Z], [X, Y], [Z, Y], [X, Z], [Y, X], [Y, Z], [X, Z]] .».
4.4 Простая экспертная система
Когда-то давно, до SVM и нейронных сетей, AI был полностью основан на «правилах». Сегодня, при доминировании, так называемых «curve-fitting» AI, эта технология известна, как GOFAI, или «Good Old Fashioned Artificial Intelligence». Далее будет рассмотрен простой пример.
Современные подходы к созданию AI превосходят GOFAI в точности. Они проще в разработке, но есть недостатки: им нужно очень много данных. В чем же плюс GOFAI? Когда вы играете в «Go» или ищите котов на фотографии, нет разницы, как компьютер пришел к решению. Но, когда речь заходит о системах безопасности или диагностики возникнет необходимость в понимании, почему было принято определенное решение. С GOFAI есть возможность видеть, что компьютер выучил и на основании этого делать корректировки.
Ниже представлена база знаний о фруктах и их характеристиках.
Рисунок 10. «Данные для экспертной системы»
В этой системе «эксперту» нужно спросить пользователя о фрукте, чтобы он мог его идентифицировать. Есть два типа значений, «boolean», что может быть «да», и набор значений, что может быть, например, цвет. «Boolean» значения нужны для однозначных вопросов, тогда как наборы значений нужны для меню.
Рисунок 11. «Предикаты, отвечающие за вопросы пользователю»
Теперь нужно определить предикаты «ask/2» и «menuask/3». Также нужно оповестить «Prolog», что предикат «known/3» является динамическим. Во-первых, нужно проверить, есть ли факт в «known/3», если нет, то проверяем схожесть атрибутов и значений и, наконец, если совпадений нет, то спрашиваем.
Рисунок 12. «Основная часть экспертной системы»
Чтобы сделать жизнь пользователя легче можно добавить стартовый предикат.
Рисунок 13. «Стартовый предикат»
Теперь, при вызове предиката «go», экспертная система будет работать. Ниже представлен пример работы.
Рисунок 14. «Пример работы экспертной системы»
4.5 Web приложение в SWI-Prolog
SWI-Prolog предоставляет возможности для созданий веб приложений. Далее будут рассмотрены несколько простых примеров.
Рисунок 15. «Простой сервер»
Предикат «server» создает простой HTTP сервер. Предикат «http_handler» обрабатывает запрос «/hello_world» и передает его в предикат «say_hi», который добавляет HTTP заголовок «Content-type: text/plain» и отправляет текст «Hello World!» как ответ.
Чтобы отправлять не простой текст, а «html» нужно добавить HTTP заголовок «Content-type: text/html»
Рисунок 16. «Сервер, отдающий HTML»
Теперь при обращении на «http://localhost:3000/hello_world» будет получен следующий результат:
Рисунок 17. «Результат запроса на сервер»
В дополнение к основному переводу терминов Prolog в HTML, библиотека «library(http/html_write)» позволяет писать «правила». На рисунке ниже будет представлена страница, показывающая список доступных Prolog модулей, но вместо того, чтобы заполнять большие объемы данных вручную, будет использована «\» конструкций, что и есть «правило».
Рисунок 18. «Использование конструкции «\»»
HTML «правила» позволяют создавать страницы динамически, но SWI-Prolog также предоставляет модули для извлечения параметров из запроса, создания запроса к другим обработчика динамически. Также существует возможность вставлять JS на страницу динамически, используя библиотеку «http/js_write». Для обработки JSON существует библиотека «json_read» и «json_write». Существует и более современный способ «читать» json. Это новые предикаты json_read_dict/2 , json_read_dict/3 , json_write_dict/2 , json_write_dict/3.
4.5.1 Реализация простого web api
В данном примере будет реализован простой API сервис по складыванию двух чисел. Сервер будет ждать JSON запроса в форме «{"a": 3, "b": 4}» и отвечать в «{"answer": 7}».
Рисунок 19. "WEB API"
4.5.2 Simple Web
Простой фреймворк построенный поверх существующих в SWI-Prolog пакетов и библиотек и заметно упрощающий разработку web приложений. Фреймворк требует «умной» системы папок для статических файлов и подразумевает использование пакета «simple-template».
Простой пример:
Рисунок 20. "simple web hello world"
Более сложный пример с применение шаблонов:
Рисунок 21. "Основной файл приложения"
На рисунке 14 происходит инициализация сервера и обработка запросов.
Рисунок 22. "Шаблон"
На рисунке 15 изображен html шаблон, приминающий некоторые данные.
После исполнения команды «swipl app.pl» будет запущен сервер на порту 5000. При обращении к «http://localhost:5000/» будет получен следующий результат:
Рисунок 23. "hello swi prolog"
При обращении к «http://localhost:5000/api» будет получен следующий результат:
Рисунок 24. "hello api"
При обращении к «http://localhost:5000/test» будет получен следующий результат:
Рисунок 25. "test menu"
5 ТЕСТИРОВАНИЕ
Автоматическое тестирование программного обеспечения, вероятно, является наиболее важной мерой обеспечения качества. Тесты могут проверить работоспособность системы, хотя многие разработчики пренебрегают ими.
Тесты пишутся на prolog и заключаются в директивы «begin_tests/1» и «end_tests/1». Они могут быть встроены в исходный модуль или в отдельный файл. Код внутри теста является обычный prolog кодом. Точки входа определяются правилами «test(Name)» или «test(Name, Options)».
Простой пример:
Рисунок 26. "simple test"
Пролог — это интерактивная среда. Там, где пользователи неинтерактивных систем склонны писать тесты в виде кода, разработчики Prolog стремятся выполнять запросы в интерактивном режиме во время разработки. Такой тип тестирование обычно быстрее, но недостатком является то, что тесты теряются в конце сеанса.
Автогенерируемые тесты экспериментально поддерживаются в библиотеке «test_wizard».
Во время тестирования очень важно знать, какие части программы покрыты тестами. Экспериментальный анализ предоставляет библиотека «test_cover».
Одна из причин внедрения тестирования — это обеспечение портативности между имплементациями. К сожалению, создание портативного набора тестов подразумевает плохую интеграцию в среду разработки.
ЗАКЛЮЧЕНИЕ
В данной курсовой работе были рассмотрены возможности решения разного рода интеллектуальных задач в среде SWI-Prolog.
В первой главе был проведен анализ существующих решений по реализации языка prolog.
Во второй главе представлена краткая информация о SWI-Prolog. На основании информации первой и второй главы, можно сделать вывод, что SWI-Prolog является универсальным решением, подходящим под большинство задач.
Далее, в третьей главе, следует список из реализаций различных задач в среде SWI-Prolog, от простых алгоритмов сортировки, до написания web сервера с помощью сторонних библиотек. SWI-Prolog имеет множество встроенных или внешних api для решения подобного рода задач.
Также была рассмотрена возможность модульного тестирования. SWI-Prolog позволяет проводить тестирование с помощью различных подходов в том числе с помощь специальных утилит.
Таким образом, все поставленные задачи были решены.
СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ И ЛИТЕРАТУРЫ
1. Prolog [Электронный ресурс], - https://en.wikipedia.org/wiki/Prolog (дата обращения 27.11.2018)
2. Comparison of Prolog implementations [Электронный ресурс], - https://en.wikipedia.org/wiki/Comparison_of_Prolog_implementations (дата обращения 27.11.2018)
3. SWI-Prolog implementation [Электронный ресурс], - https://en.wikipedia.org/wiki/SWI-Prolog (дата обращения 03.12.2018)
4. SWI-Prolog [Электронный ресурс], - http://www.swi-prolog.org/ (дата обращения 03.12.2018)
5. Introduction to logic programming with prolog [Электронный ресурс], - https://www.matchilling.com/introduction-to-logic-programming-with-prolog/ (дата обращения 05.12.2018)
6. The tower of Hanoi [Электронный ресурс], - https://proofwiki.org/wiki/Tower_of_Hanoi#Historical_Note (дата обращения 06.12.2018)
7. The tower of Hanoi puzzle [Электронный ресурс], - https://www.cpp.edu/~jrfisher/www/prolog_tutorial/2_3.html (дата обращения 06.12.2018)
8. GOFAI: A Simple Prolog Expert [Электронный ресурс], - http://www.paulbrownmagic.com/blog/simple_prolog_expert (дата обращения 08.12.2018)
9. Prolog Web Applications [Электронный ресурс], - https://www.metalevel.at/prolog/web (дата обращения 23.12.2018)
ПРИЛОЖЕНИЕ
2