В данной статье я собираюсь рассказать о приложении (написанное мной) для Андроида, интерпретирующее Пролог программы написанные синтаксисом разработанным в 70-е года (тоесть в первоначальном своём виде: факты и правила, операторы и вопросы; о нём вы можете почитать в книге “Иван Братко, Программирование на языке Пролог для искусственного интеллекта”, ссылка находится в конце статьи). Называется оно Prolog Classic (ссылка для скачивания находится в конце статьи).
Данное приложение написано на Java n-ide для Андроид (написанное mr Duy, за что ему особая благодарность, так как у меня нет компьютера, только смартфон; это приложение вы найдёте в Google play).
1. Особенности языка Пролог
Итак, Пролог — язык логического программирования, основанный на языке предикатов математической логики дизъюнктов Хорна, представляющей собой подмножество логики предикатов первого порядка.
Язык сосредоточен вокруг небольшого набора основных механизмов, включая сопоставление с образцом, древовидного представления структур данных и автоматического перебора с возвратами. Хорошо подходит для решения задач, где рассматриваются объекты (в частности структурированные объекты) и отношения между ними. Пролог, благодаря своим особенностям, используется в области искусственного интеллекта, компьютерной лингвистики и нечислового программирования в целом. В некоторых случаях реализация символьных вычислений на других стандартных языках вызывает необходимость создавать большое количество кода, сложного в понимании, в то время как реализация тех же алгоритмов на языке Пролог даёт простую программу, легко помещающуюся на одной странице.
Prolog является декларативным языком программирования: логика программы выражается в терминах отношений, представленных в виде фактов и правил. Для того чтобы инициировать вычисления, выполняется специальный запрос к базе знаний, на которые система логического программирования генерирует ответы «истина» и «ложь». Для обобщённых запросов с переменными в качестве аргументов созданная система Пролог выводит конкретные данные в подтверждение истинности обобщённых сведений и правил вывода.
Задача пролог-программы заключается в том, чтобы доказать, является ли заданное целевое утверждение следствием из имеющихся фактов и правил.
В данной реализации Пролога написанной для Андроид, представлены почти все возможности изначального Пролога описанного в книге Братко [1]: безтиповое программирование; программное определение новых операторов; возможность задания нескольких вопросов в одной программе; извлечение знаний (фактов, правил, вопросов, операторов) из файлов; программная запись новых структур (фактов, правил, вопросов, операторов) в базу знаний, а также удаление из неё.
Подробнее о Прологе вы можете прочитать, также, в статье-учебнике [2] .
Рассмотрим несколько программ-примеров.
1.1. Работа соператорами
:- op( 1, xfx, родитель).
игорь родитель марии.
анна родитель марии.
?- Кто родитель марии.
В консоли мы получим такой ответ:
Кто = игорь
Если мы поставим точку с запятой, то Пролог выдаст нам другой ответ:
Кто = игорь;
Кто = анна
И снова поставив точку с запятой мы узнаем, что больше родителей марии нет:
Кто = игорь;
Кто = анна;
no.
Теперь, усложним задачу. Добавим ещё два оператора и по-новому зададим факты:
:- op( 1, fx, отец).
:- op( 1, fx, мать).
:- op( 2, xfx, родитель).
отец игорь родитель марии.
мать анна родитель марии.
отец вася родитель ирины.
мать ольга родитель ирины.
Задав вопрос:
?- Кто родитель марии.
мы теперь получим следующие два ответа, использовав точку с запятой:
Кто = отец игорь;
Кто = мать анна
Поставив точку мы завершим программу.
Теперь зададим такой вопрос, чтобы узнать, кто отец кого:
?- отец Кто родитель Кого.
и получим ответы (использовав точку с запятой):
Кто = игорь, Кого = марии;
Кто = вася, Кого = ирины.
Как видите объявление операторов в программе, помогает общаться с компьютером на языке приближённом к естественному языку.
1.2. Безтиповое программирование
К примеру, напишем программу, которая вставляет заданный символ в конец списка из других символов:
add(X,[],[X]).
add(X,[Y|L1],[Y|L2]):- add(X,L1,L2).
?- add(z,[a,b,c,d,e,f],L).
Результатом будет:
L = [a,b,c,d,e,f,z].
Видно, что этот предикат состоит из двух частей - факта и правила. При выполнении программы вызов этого предиката приводит к перебору правил в порядке сверху-вниз, каждый раз переданный список аргументов предиката сопоставляется с аргументами факта или правила. Если сопоставление невозможно — то выполняется переход к следующему факту или правилу. Так, первый факт описывает следующее «если список, переданный во втором аргументе пуст, то есть сопоставляется с [] — то список третьего аргумента должен состоять из одного элемента X - [X]». Если список непустой -то управление получит правило, которое:
- отделяет от исходного списка один элемент, получая список остальных элементов L1. Конструкция [Y|L1];
- инициирует рекурсивную обработку L1;
- получив результат рекурсивного вызова в переменной L2, дописывает к нему в начало элемент Y. Конструкция [Y|L2].
Механизм выбора правил отдаленно напоминает полиморфизм функций в языках типа С++, но является более гибким, так как выбор происходит во время выполнения программы, а не при компиляции.
Как видите это очень просто, в Прологе, и весьма компактно (программа занимает 3 строчки).
Теперь усложним задачу, добавим в список среди символов цифры и зададим программе, чтобы она каждую цифру умножала на 2, а каждый символ ‘a’ удваивала, таким образом получив строку из двух символов - ‘aa’:
listFoo([],[]).
listFoo([N|L1],[N2|L2]):-
numeral(N), N2 = N*2,
listFoo(L1,L2).
listFoo([a|L1],[aa|L2]):-
listFoo(L1,L2).
listFoo([C|L1],[C|L2]):-
listFoo(L1,L2).
?- listFoo([1,a,b,c,3,str,ok(m)],L).
Теперь заданный список состоит из чисел, символов и строк. Трансформируя его заданным нами предикатом listFoo мы получим:
L = [2,aa,b,c,6,str,ok(m)].
Заметьте, в этой программе используется встроенный предикат numeral (N), который бывает истинным, если его аргумент является числом. Так же предикат равенства имеет две функции: если одну или две стороны можно вычислить, а потом унифицировать, то мы получим вычисления, в противном случае, Пролог попытается просто унифицировать левую и правую часть равенства. Здесь мы применяем его для вычислений (В книге Братко не так, там для вычислений используется специальный оператор is. Однако я когда-то, в другой советской книжке читал, непомню автора и названия, там равенство применялось так же как у меня).
Вот мы с вами написали программу работающую со списком, у которого елементы списка могут быть произвольного типа, а точнее никакого типа нет - есть только термы (некая древовидная структура имеющая функтор и аргументы (или ноль аргументов)). Да и сам список нигде не обьявляется, ни типы аргументов нашего предиката listFoo. В строго типизированных языках типа С++ не так просто в один контейнер поместить и числа и строки, и символы одновременно, и там в функиях нужно объявлять типы входных и выходных переменных.
1.3. Задание нескольких вопросов в программе
Напишем такую программу:
мужчина(олег).
мужчина(димитрий).
женщина(алла).
женщина(маша).
?- write(мужчины:), nl,
мужчина (М);
write(женщины), nl,
женщина (Ж).
Здесь, в вопросе, мы использовали точку с запятой. Она соответствует логическому ИЛИ. Это значит, что то что до точки с запятой является одним вопросом, после неё другим. Посмотрим как это работает.
Запустив программу мы увидим:
мужчины:
М = олег
Перебирая другие ответы мы получим:
мужчины:
М = олег;
М = димитрий;
женщины:
Ж = алла;
Ж = маша;
no.
Таким образом, с помощью многих вопросов мы можем получить от компьютера исчерпывающую информацию.
Далее привожу таблицу встроенных предикатов моего приложения. Тех предикатов, которых нет в Братко я выделил жирным шрифтом цветом:
! - Отсечение.
atom(A) - Является истинным, если терм А является атомом.
functor_chars(T,CL) - Является истинным, если CL - список символов из которых состоит функтор терма Т.
retractA(T) - Является истинным, если в базе знаний существет такой факт или правило Т, кторое предикат и удаляет. Поиск ведётся с начала базы знаний.
retractZ(T) - Является истинным, если в базе знаний существет такой факт или правило Т, кторое предикат и удаляет. Поиск ведётся с конца базы знаний.
assertA(T) - Всегда является истинным и добавляет Т как факт или правило в начало базы знаний.
assertZ(T) - Всегда является истинным и добавляет Т как факт или правило в конец базы знаний.
read(T) - Читает терм с текущего потока ввода (консоль или файл) и является истинным, если прочитанный терм равен терму Т.
write(T) - Всегда является истинным и выводит терм Т в текущий потока вывода (консоль или файл).
nl - Всегда является истинным и выводит поток вывода (консоль или файл) на новую строку.
tab(N) - Является истинным, если N является положительным целочисленным числом и выводит в поток вывода (консоль или файл) количество пробелов указанных числом N.
numeral(T) - Всегда является истинным, если терм Т является числом.
T1 <= T2 - Является истинным, если число Т1 меньше или равно Т2.
T1 < T2 - Является истинным, если число Т1 меньше Т2.
T1 >= T2 - Является истинным, если число Т1 больше или равно Т2.
T1 > T2 - Является истинным, если число Т1 больше Т2.
T1 = T2 - Является истинным: 1) Если одну или две стороны можно вычислить, а потом унифицировать; 2) В противном случае, если можно просто унифицировать левую и правую часть равенства.
var(V) - Является истинным, если V является свободной переменной.
see(Dir) - Является истинным, если Dir это атом в котором указан путь и имя существующего файла. Предикат устанавливает данный файл как поток ввода. Если Dir равен user потоком ввода будет консоль, при этом открытые файлы не закрываются.
seen - Является истинным, если текущий поток ввода является файлом, который и закрывает.
time(N) - Является истинным, если N равно прошедшему времени в миллисекундах начиная от 00:00 01.01.1970 года (этот предикат полезен для генерации случайных чисел).
not(P) - Логическое отрицание. Истиннен, если предикат P является ложным в любом случае.
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], в котором для человека, который не одну программу написал на Прологе, многие места в программе будут легко понятны, да и программа маленькая.
Приложение Prolog Classic находится на форуме 4pda в теме Prolog Classic [5].
Моя почта: elevferii_pechori@mail.ru.
Составлять статью помогал Владимир Васильев rrrfer@mail.ru.
Список литературы
1. Братко И. Программирование на языке Пролог для искусственного интеллекта.- М., 1990.
2. Введение в логическое программирование (Prolog). URL: Введение в логическое программирование (Prolog) — Блог программиста
3. Принципы построения программ на Prolog. URL: Принципы построения программ на Prolog — Блог программиста
4. Программный код игры в «крестики и нолики» с искусственным интеллектом. URL: https://4pda.to/forum/index.php?showtopic=1021403&view=findpost&p=105946577
5. Prolog Classic | Эмуляция Пролог программ с выводом в консоль. URL: Prolog Classic - 4PDA
