В данной статье я собираюсь рассказать о приложении (написанное мной) для Андроида, интерпретирующее Пролог программы написанные синтаксисом разработанным в 70-е года (тоесть в первоначальном своём виде: факты и правила, операторы и вопросы; о нём вы можете почитать в книге “Иван Братко, Программирование на языке Пролог для искусственного интеллекта”, ссылка находится в конце статьи). Называется оно Prolog Classic (ссылка для скачивания находится в конце статьи).
В настоящий момент, начиная с версии 4.0, помимо атомарных тером: атом, переменная и число, появились ещё 2: изображение и аудиозапись (читай ниже). Ещё есть возможность паралельного программирования (читай ниже).
Данное приложение написано на Java n-ide для Андроид.
1. Особенности языка PrologClassic
Итак, Пролог — язык логического программирования, основанный на языке предикатов математической логики дизъюнктов Хорна, представляющей собой подмножество логики предикатов первого порядка.
Язык сосредоточен вокруг небольшого набора основных механизмов, включая сопоставление с образцом, древовидного представления структур данных и автоматического перебора с возвратами. Хорошо подходит для решения задач, где рассматриваются объекты (в частности структурированные объекты) и отношения между ними. Пролог, благодаря своим особенностям, используется в области искусственного интеллекта, компьютерной лингвистики и нечислового программирования в целом. В некоторых случаях реализация символьных вычислений на других стандартных языках вызывает необходимость создавать большое количество кода, сложного в понимании, в то время как реализация тех же алгоритмов на языке Пролог даёт простую программу, легко помещающуюся на одной странице.
Prolog является декларативным языком программирования: логика программы выражается в терминах отношений, представленных в виде фактов и правил. Для того чтобы инициировать вычисления, выполняется специальный запрос к базе знаний, на которые система логического программирования генерирует ответы «истина» и «ложь». Для обобщённых запросов с переменными в качестве аргументов созданная система Пролог выводит конкретные данные в подтверждение истинности обобщённых сведений и правил вывода.
Задача пролог-программы заключается в том, чтобы доказать, является ли заданное целевое утверждение следствием из имеющихся фактов и правил.
В данной реализации Пролога написанной для Андроид, представлены почти все возможности изначального Пролога описанного в книге Братко [1]: безтиповое программирование; программное определение новых операторов; возможность задания нескольких вопросов в одной программе; извлечение знаний (фактов, правил, вопросов, операторов) из файлов; программная запись новых структур (фактов, правил, вопросов, операторов) в базу знаний, а также удаление из неё.
Подробнее о Прологе вы можете прочитать, также, в статье-учебнике [2] .
1.1. Задание нескольких вопросов в программе
Напишем такую программу:
мужчина(олег).
мужчина(димитрий).
женщина(алла).
женщина(маша).
?- write(мужчины:), nl,
мужчина (М);
write(женщины), nl,
женщина (Ж).
Здесь, в вопросе, мы использовали точку с запятой. Она соответствует логическому ИЛИ. Это значит, что то что до точки с запятой является одним вопросом, после неё другим. Посмотрим как это работает.
Запустив программу мы увидим:
мужчины:
М = олег
Перебирая другие ответы мы получим:
мужчины:
М = олег;
М = димитрий;
женщины:
Ж = алла;
Ж = маша;
no.
Таким образом, с помощью многих вопросов мы можем получить от компьютера исчерпывающую информацию.
1.2. Параллельное программирование:
1.2.а. Паралельные правила
В реализации данного пролога существует предикат ‘::-’, который является тем же правилом, но с той разницей, что его предикаты в теле правила выполняются параллельно. Для удобства, назовём его правилом П.
Например:
ПравилоП(X)::- предикат1(X), предикат2(X), предикат3(X).
Здесь, все три предиката будут выполняться одновременно. Что касается переменных, если, к примеру, они есть в голове правила и далее, используются, скажем, во всех предикатах, то на момент запуска предикатов, будут использоваться переменные из заголовка тела, в каждом предикате, такими какими являются в голове правила (включая свободные переменные). И что важно, конкретизация переменных, из головы правила, в одном предикате, не повлияет на те же переменные из другого предиката (считайте их разными копиями). Но, после удачного выполнения эти копии между собой унифицируются. И только после этого, такое правило может быть удачным (декларативно - «истинным»).
В таком правиле тоже есть механизм возврата с поиском новых решений. С декларативной стороны он выдаст, при необходимости, все возможные решения для каждого предиката, и нам не важно как он их будет искать. Но с технической стороны, это будет происходить следующим образом. Скажем, такое правило, после первого запуска, выдаст первые решения для своих предикатов. Если нужно искать следующий результат, для правила, то сначала делается откат последнего предиката (крайний справа или снизу). Если последний предикат всё равно будет ложным, тогда откатывается предпоследний предикат и т.д. Похоже на обычное правило, не так ли? Но дальше вы узнаете, что есть и разница. Если, скажем, при выполнении правила ПравилоП(Х) (см. выше), после первого решения для правила, неудачным стал предикат предикат2(X), тогда он отправляется в конец списка (после последнего удачного предиката):
ПравилоП(X)::- предикат1(X), предикат3(X), предикат2(X).
И если после этого, неудачными будут предикаты: предикат1(X), предикат2(X), тогда, теперь первый предикат отправится перед предикатом предикат2(X) (то-есть, после последнего удачного предиката):
ПравилоП(X)::- предикат3(X), предикат1(X), предикат2(X).
А если бы, с самого начала после первого удачного решения, неудачными стали бы оба предиката предикат1(X), предикат2(X), тогда они бы оба отправились в конец списка (после последнего удачного предиката предикат3(X)):
ПравилоП(X)::- предикат3(X), предикат1(X), предикат2(X).
Как видите, порядок отправляющихся одновременно предикатов сохраняется: слева на право.
Все эти перемещения и порядок нужны для того, чтобы получить ВСЕ решения, как если бы они выполнялись последовательно.
1.2.б. Параллельные вопросы
Поговорим ещё об одном виде параллельного программирования - это параллельные вопросы (операторы: ‘!-’ и ‘?-’).
Параллельные вопросы бывают двух видов:
- У первых предикаты выполняются точно также - последовательно, - как и у главного вопроса, за исключением, что эти параллельные вопросы выполняются одновременно с главным и параллельными вопросами.
Например:
cons(вопрос2) ?- предикат1, предикат2.
Левая часть предиката должна обязательно состоять из функтора cons и одного атомарного аргумента, который не может быть переменной (идентификатор вопроса).
- У вторых предикаты выполняются параллельно, как в правилах П, ну и конечно, сами вопросы выполняются одновременно с главным и параллельными вопросами.
Например:
par(вопрос2) ?- предикат1, предикат2.
Левая часть предиката должна обязательно состоять из функтора par и одного атомарного аргумента, который не может быть переменной (идентификатор вопроса).
Теперь, поговорим немножко о том что будет, если нехватит ОЗУ при выполнении параллельных правил П.
Допустим, у вас, выполняется параллельное правило правП1 с предикатами: предикат1, предикат2. Итак, предикат1 и предикат2 выполняются параллельно. Что же будет, если во время их выполнения не хватит оперативной памяти? А будет то, что в какой-то момент, один предикат будет выполняться дальше, а другой будет ждать, пока не выполнится первый. А если быть точнее, пока не освободится достаточно памяти. А поскольку надо, чтобы не просто выполнился один из предикатов, а после выполнения одного снова освободилась память, - я советую делать следующее. Допустим, вам известно, что с правиломП может такое случиться. Тогда, с каждым его предикатом (предикат1, предикат2 и т.д.) нужно сделать следующую трансформацию:
предикат1_(M,X):- предикат1(X), assertA (p(M,X)), false; retractA (p(M,X)).
Мы создали новый предикат предикат1_(M,X), в котором при удачном выполнении предиката предикат1(X), сохраняется результат его выполнения в факт p(M,X), где М - это уникальный идентификатор предиката (чтобы не путался факт одного предиката с фактом другого). Таким образом, после выполнения предиката предикат1(X), весь стэк освобождается до момента его выполнения, что позволяет дальше выполняться другим параллельным предикатам.
2. Встроенные предикаты
!/0 - Отсечение.
atom/1 - Является истинным, если аргумент является атомом.
chars/2 - Является истинным, если 1-ый аргумент - список символов из которых состоит функтор терма 2-ого аргумента.
retractA/1 - Является истинным, если в базе знаний существет такой факт или правило (аргумент), которое есть предикат, и удаляет его. Поиск ведётся с начала базы знаний.
retractZ/1 - Является истинным, если в базе знаний существет такой факт или правило (аргумент), которое есть предикат, и удаляет его. Поиск ведётся с конца базы знаний.
assertA/1 - Всегда является истинным и добавляет аргумент как факт или правило в начало базы знаний.
assertZ/1 - Всегда является истинным и добавляет аргумент как факт или правило в конец базы знаний.
read/1 - Читает терм с текущего потока ввода (консоль или файл) и является истинным, если прочитанный терм равен терму аргумента.
write/1 - Всегда является истинным и выводит терм аргумента в текущий потока вывода (консоль или файл).
nl/0 - Всегда является истинным и выводит поток вывода (консоль или файл) на новую строку.
tab/1 - Является истинным, если аргумент - это число, и выводит в поток вывода (консоль или файл) некоторое количество пробелов указанных в аргументе.
numeral/1 - Всегда является истинным, если терм аргумента является числом.
<=/2 - Является истинным, если число 1-го аргумента меньше или равно числу 2-го аргумента.
</2 - Является истинным, если число 1-го аргумента меньше числу 2-го аргумента.
>=/2 - Является истинным, если число 1-го аргумента больше или равно числу 2-го аргумента.
>/2 - Является истинным, если число 1-го аргумента больше числа 2-го аргумента.
=/2 - Является истинным: 1) Если одну или две стороны можно вычислить, а потом унифицировать; 2) В противном случае, если можно просто унифицировать левую и правую часть равенства. Изображения звукозаписи и сравниваются по-байтово.
var/1 - Является истинным, если аргумент является свободной переменной.
see/1 - Является истинным, если аргумент это атом в котором указан путь и имя существующего файла. Предикат устанавливает данный файл как поток ввода. Если аргумент равен user потоком ввода будет консоль, при этом открытые файлы не закрываются.
seen/0 - Является истинным, если текущий поток ввода является файлом, который и закрывает.
time/1 - Является истинным, если аргумент равен прошедшему времени в миллисекундах начиная от 00:00 01.01.1970 года (этот предикат полезен для генерации случайных чисел).
not/1 - Логическое отрицание. Истиннен, если предикат аргумента является ложным в любом случае.
2. Использование интерпретатора Пролог на Android
Поскольку приложение является интерпретатором — оно не создаёт apk файл. С другой стороны это может быть даже удобно, так как пользователь всегда может что-то изменить в программе по своему усмотрению, или просто посмотреть как написана программа и из текста понять её работу целиком или каких-то частей.
Итак, поговорим о том как работать в данном приложении, разберём по шагам:
- Запускаем приложение. Сразу после запуска появится окно для ввода текста программы;
- Для открытия записанной программы ипользуем кнопку Open, для сохранения — Save, для очистки окна — New. Программы нужно сохранять только с расширением *.txt, иначе не сможете их открыть;
- После написания программы запускаем его кнопкой Run, после чего появится консольное окно, в котором будет отображаться результат исполнения программы («yes.», «no.» или значения переменных в вопросе). Когда результатом будут значения переменных, можно либо завершить программу точкой, либо вводом точки с запятой получить значения переменных следующего результата программы. Если в программе допущена синтаксическая ошибка (обычно это нехватка запятой или точки), то при запуске программы на экран выведится соответствующее предупреждение;
- Приложение позволяет не только статически указывать предикаты в программе (факты, правила, вопросы), но и динамически записывать читая их из файла или консоли;
- Что касается отладки программ: специального отладчика в программе нет, но я в таком случая всегда пользуюсь предикатом write/1 для вывода на экран любой информации вовремя исполнения программы.
Данное приложение может работать только с консолью, такова была моя задумка. Я искал такое приложение, для написания программ с искуственным интеллектом, под Андроид и в Google play и в поисковике, но нигде не найдя пришлось написать самому.
3. Особенности реализации и работы интерпретатора
Теперь я вам немного расскажу о важных моментах реализации моего приложения на java языке:
3.1. Использование и реализация стэка
Стэк в моём приложении Prolog Classic нужен не только для хранения значений переменных в предикатах, но и для хранения точек отката. Получается у нас двухмерная матрица.
В длину, скажем, это глубина выполнения предикатов с переменными; в ширину — сохранение точек отката. То есть, перед унификацией каждого нового предиката, копируется одномерный стэк с переменными и в этом новом одномерном стэке, являющейся точкой отката, при унификации, или добавляются новые переменные из текущего предиката, или происходит конкретизация каких-либо переменных в текущем одномерном стэке. А если после конкретизации что-то пойдёт не так, то предыдущий стэк даст нам возможность снова скопировать предыдущия значения переменных.
3.2. Механизм работы интерпретатора
Ядром интерпретатора это выполнение предикатов при помощи вложенной рекурсии. Тоесть, берётся первый предикат тела вопроса, унифицируется с подходящим фактом или правилом, и дальше, главная функция интерпретатора вызывает саму себя, но с новыми параметрами. Если данный предикат — правило, тогда выполняется первый предикат тела данного правила, если факт — тогда следующий предикат вопроса. И далее всё по аналогии.
Программа выполняется в отдельном потоке. Это нужно для того, чтобы видеть исполнение программы в реальном времени (например, в каком-нибудь цикле постоянно что-то выводится на экран и этот цикл продолжается долго).
3.3. Преобразование предложений программы в прологовские структуры
Для работы программы, интерпретатор должен первоначально преобразовать приложения текста в структуры (факты, правила, вопросы). Для этого используется операторная нотация [1].
Рассмотрим, к примеру, следующий вопрос в программе:
?- мужчина.
‘?-’ здесь является префиксным оператором, тоесть он должен стоять в предложении перед своим аргументом. Это предложение равносильно предложению записанному так:
?-(мужчина).
Рассмотрим другой пример:
?- вася слесарь.
‘?-’ является префиксным оператором — это мы уже знаем. А слово ‘слесарь’ постфиксным оператором, если конечно мы не забыли определить его перед использованием (предложение определения оператора в программе должно стоять до его использования!). Постфиксный оператор как и префексный имеет всего один аргумент. Предложение выше равносильно следующему предложению:
?-(слесарь(вася)). % Если приоритет оператора '?-' выше чем у 'слесарь'
или
слесарь(?-(вася)). % Если приоритет оператора 'слесарь' выше чем у '?-'
Существуют ещё инфиксные операторы, которые должны стоять в середине предложения — между своими двумя аргументами.
Распознаются операторы в предложении следующим образом. Берётся оператор с наивысшим приоритетом и ищется в предложении (если это префиксный оператор, то первое слово в предложении должно равняться этому предикату, если это постфиксный — последнее слово должно совпадать с оператором, если инфиксный — тогда в предложении, слева направо, ищется слово совпадающее с оператором). Если оператор не найден — берётся оператор у которого приоритет пониже и т.д.
Скобки среди операторов мы используем для того, когда хотим, чтобы оператор более высокого приоритета был аргументом оператора более низкого приоритета, например:
X = 5*(2+1)
Здесь оператор ‘*’ имеет более низкий приоритет, чем ‘+’, но скобки всё меняют. Теперь оператор ‘+’ благодаря скобкам имеет приоритет 0.
Заметим, что обычный терм — это, по сути, тоже оператор с нулевым приоритетом, где функтор это имя оператора, а в скобках — это древовидная структора из операторов ‘,’. Однако при обработке интерпретатором текста программы, после вторичной обработки такой структуры из запятых, они становятся аргументами заданного функтора и запятые исчезают. Тоже самое касается правил, где правая часть оператора ‘:-’ исчезает становясь телом правила.
Заключение
В конце, хочется сказать, что данное приложение работая интерпретатором и в консоли предназначено скорее для написания научно-исследовательских работ у которых код программы всегда открыт и имеется возможность улучшить или изменить программу. Пролог — это язык логического программирования, но содержит и свойства процедурного исполнения программ (бывает, важен порядок выполнения предикатов; отсечение [3]), что очень похоже на то как думает наш мозг. Поэтому он очень хорошо подходит для написания программ с искусственным интеллектом. В качестве примера, можете посмотреть программный код игры «крестики и нолики» [4], в котором для человека, который не одну программу написал на Прологе, многие места в программе будут легко понятны, да и программа маленькая.
Моя почта: elevferii_pechori@mail.ru.
Составлять статью помогал Владимир Васильев rrrfer@mail.ru.
Список литературы
1. Братко И. Программирование на языке Пролог для искусственного интеллекта.- М., 1990.
2. Введение в логическое программирование (Prolog). URL:
https://pro-prof.com/archives/2362
3. Принципы построения программ на Prolog. URL:
https://pro-prof.com/forums/topic/semantics-prolog
4. Программный код игры в «крестики и нолики» с искусственным интеллектом. URL: https://disk.yandex.ru/d/5ED-43Uveub1ew
5. Prolog Classic | Интерпретатор Пролог программ с выводом в консоль. NashStore: https://store.nashstore.ru/store/651cf1c60a39b23f221fc121
или Яндекс Диск:
https://disk.yandex.ru/d/5ED-43Uveub1ew
6. Исходный код интерпретатора Prolog-программ на Android (PrologClassic). URL:
https://disk.yandex.ru/d/AVxfoYbg07ZcnA%5Bprolog%5D
