Логическое программирование для начинающих. Prolog
0. Предисловие
Эта работа является моим рефератом по курсу «Логическое программирование», которое я изучал в МАИ. Тема реферата: «Как научить младшую сестру/брата логическому программированию».
Также хотелось бы добавить, что в этой работе нет объяснения того, как установить язык программирования Prolog, запускать программы и т.д. Информацию об этом можно взять из другой статьи (см. 1 статью в списке литературы).
1. Введение
Мне попалась очень хорошая тема. Всем известно, что человек поистине разбирается в какой-то теме, если он может объяснить ее ничего не знающему в этой области человеку. Например, младшему брату. Поэтому изложение материала не должно быть сложным, обязательно должны быть примеры, подкрепляющие сказанное. Но прежде чем начать рассказывать о логическом программировании, нужно рассказать о самом программировании. Приступим.
2. Что такое программирование?
Объяснить это не так уж и сложно. Программирование — процесс написание программ, программа же является некоторой инструкцией компьютеру от человека, следуя которым, компьютер сделает то, что человек от него хочет. Людей, пишущих код (программу), называют программистами. Общение с компьютером происходит не на простом языке. Машина его просто не понимает. Специально для программирования были созданы языки, понятные компьютеру. Такие языки получили название — языки программирования. Когда стало понятно, что такое программирование, можно приступить к логическому программированию.
3. Что такое логическое программирование?
Логическое программирование — парадигма (модель) программирования основанная на логике: компьютеру даются факты и правила, на основе которых он автоматически доказывает или опровергает теоремы. Одним из самых популярных языков логического программирования является Prolog. Именно на его примере я буду объяснять эту парадигму программирования. Начнем.
4. Основы Prolog
В Prolog есть предикаты — логические формулы принимающие аргументы (один или несколько). Например: study(somebody, something) принимает в себя следующие аргументы: данные человека (имя и т.д.) на место somebody и то, что он изучает (например, математику, английский) на место something. Пусть верны следующие утверждения:
Саша изучает испанский язык
Даша играет в CS: GO
Тимур старше Имеди
Исмаилу 19 лет
Разберем данные утверждения. Они состоят из объектов: Саша, Даша, Тимур, Имеди, Исмаил, испанский язык, CS: GO, 19 лет. Объект может быть чем угодно. Также существуют связи между объектами, выражаемые глаголами: изучать (Сашу с испанским связывает то, что она его изучает), играть, видеть, бежать и т.д. Связь также можно выразить с помощью прилагательных: старше, умнее, быстрее и т.д.
Напишем простейшую программу на Прологе, чтобы показать возможности этого языка:
study(imedy, deutsch).При ее запуске можно задать некоторые вопросы:
Пусть мы хотим узнать «Имеди изучает немецкий?» На Прологе этот вопрос выглядит так:
?- study(imedy, deutsch).
true.Как же программа узнала что Имеди изучает немецкий? Все просто: программа проверила, есть ли в ее базе знаний сведения об этом. Мы ранее занесли данные об изучении немецкого (во время написания программы). Так как в базе есть сведения об этом, то ответ на наш вопрос — да (правда).
Давайте спросим то, о чем программе не знает, например, «изучает ли Имеди математику?»:
?- study(imedy, math).
false.Вышла ошибка. Это значит, что у программы нет данных об этом событии, ответ на вопрос — нет. Хватит с простыми программами, давайте усложним задачу:
% Ниже правила
speciality(X,tech_translator) :- studied_languages(X),studied_technical(X).
speciality(X,programmer) :- studied(X,mathematics),studied(X,compscience).
speciality(X,lit_translator) :- studied_languages(X),studied(X,literature).
studied_technical(X) :- studied(X,mathematics).
studied_technical(X) :- studied(X,compscience).
studied_languages(X) :- studied(X,english).
studied_languages(X) :- studied(X,german).
% Ниже факты
studied(petya,mathematics).
studied(vasya,german).
studied(petya,compscience).
studied(vasya,literature).
studied(petya,english).Есть 2 человека: Петя и Вася, каждый из них изучал какие-то предметы (математику compscience, иностранные языки и т.д.). Такие данные называются фактами. Выше них в программе написаны правила, которые помогают программе определить профессию людей на основании заданных фактов. Чтобы задать правило, нужно заменить точку ».» (как было в фактах) на знак »:-» и написать условие, когда правило будет истинным. Разберу первое правило для примера:
speciality(X,tech_translator) :-studied_languages(X),ыеstudied_technicaical(X). — означает, что, чтобы у Х — какого-то человека (в этой программе на это место ставятся Петя, Вася) — была специальность технического переводчика, необходимо, чтобы он изучил языки и (знак запятой в правиле) техничексие науки. Только при таком условии у человека будет специальность технического переводчика. Можно заметить, что в программе изучение языков, технических наук заданы тоже как правила.
studied_technical(X) :- studied(X,mathematics).
studied_technical(X) :- studied(X,compscience).Это означает, что изучение технических наук значит изучение математики или compscience. Эти две строчки можно заменить на одну с помощью занка или (точка с запятой):
studied_technical(X) :- studied(X,mathematics); studied(X,compscience).
Изучение же языков предполагает изучение английского или (опять же 2 строчки можно заменить на одну) немецкого.
Давайте уже запустим нашу программу и, задав вопросы, узнаем специальности каждого человека.
Важно: даже в вопросе можно не указывать имена людей, названия профессий. В таком случае можно задать переменные (Х, Y, Res и т.п.) в соответсвие которым программа сама поставит людей, специальности.
?- speciality(petya, X).
X = tech_translator ;
X = tech_translator ;
X = programmer ;
false.Я задал вопрос, какая специальность у Пети. Компьютер на основе фактов (изучение Петей немецкого, английского, математики и compscience) вывел следующие профессии: программист, технический переводчик (не является ошибкой, что вывелось 2 раза, т.к. Петя изучал и немецкий, и английский. Компьютер двумя разными путями пришел к этому ответу). «false» означает, что больше профессий у Пети нет. И это верно: Петя не изучал литературу, поэтому не может быть литературным переводчиком. Чтобы узнать все возможные решения, можно задать следующий вопрос:
?- speciality(X, Y).
X = petya,
Y = tech_translator ;
X = petya,
Y = tech_translator ;
X = petya,
Y = programmer ;
X = vasya,
Y = lit_translator.Важно ометить, что происходит перебор не только профессий, но и людей. Думаю, что работа программы уже должна быть понятной. Перейдем к следующему важному разделу в Прологе.
5. Списки в Prolog
Списки являются важной структурой в Prolog. «Списки позволяют хранить произвольное количество данных. Связный список — структура данных, состоящая из узлов. Узел содержит данные и ссылку (указатель, связку) на один или два соседних узла. Списки языка Prolog являются односвязными, т.е. каждый узел содержит лишь одну ссылку» (см. первый материал из списка литературы). «При работе с односвязными списками выделяется первый узел (называемый головой списка), остальные узлы (составляющие хвост списка) можно получить передвигаясь по указателям вплоть до последнего узла» (см. четвертый материал из списка литературы). Хвост списка тоже является списком, поэтому он обрабатывается так же.
Объявление списков происходит через запятую: []- пустой, [x], [x, y], [12, 13, word]. Унификация списков: [] — пустой список, [Head|Tail] — это список, в котором выделяюттcя первый элемент (голова) и остальная часть — хвост. Чтобы отделить голову списка от ее хвоста, используется знак »|».
Можно унифицировать такой список [X1, X2|Tail]. Тогда каждый раз первые два элемента списка будут составлять голову, а остальная часть списка будет в Tail (если отсечь голову, то первые два элемента бывшего хвоста станут головой нового списка).
Так как списки хранят данные, которые мы должны использовать для решения некоторых задач, то необходимо научиться обрабатывать списки. Обработка списков происходит с помощью предикатов. Приведем примеры:
Реализация предиката нахождения длины списка:
mylength([], 0) .
mylength([_|T], N) :- mylength(T, N1), N is N1 + 1.
?- mylength([1,2,3],N).
N = 3.
?- mylength([1, 2, 3], N).
N = 3.
?- mylength([1, 2, 3, X], N).
N = 4.
?- mylength([1, 2, 3, X, ABC], N).
N = 5.
?- mylength([], N).
N = 0.
?- mylength([L], N).
N = 1.Объяснение: длина пустого списка равняется нулю. Если список непустой, то берется хвост списка, а к итоговому результату прибавляется единица. Это рекурсивно продолжается до тех пор, пока получившийся список не будет пустым. Выводится итоговый результат, являющийся длиной изначального списка.
Знак »_» означает, что на этом месте находится один любой элемент списка.
Перечисление элементов списка по одному:
element([H|T], Element) :- Element = H; element(T, Element).
?- element([1,2,3,4], Elem).
Elem = 1 ;
Elem = 2 ;
Elem = 3 ;
Elem = 4 ;
false.Объяснение: element([H|T], Element) истенно, если Element равен H или если предикат element (T, Element) истинный. Когда список закончится, эта рекурсия прекратится. Таким образом, предикат будет истинным, если Element будет равен каждому элементу списка [H|T]. Пролог найдет все решения (все элементы списка) и перечислит их.
Перечисление элементов списка с пропуском нечетных по порядку:
element([_, X2|Tail], Element) :- Element = X2; element(Tail, Element).
?- element([1,2,3,4], Elem).
Elem = 2 ;
Elem = 4 ;
false.
?- element([1,x,3,y,4,z], Elem).
Elem = x ;
Elem = y ;
Elem = z ;
false.Реализация предиката, проверяющего принадлежность элемента списку:
mymember(H, [H|]).
mymember(H, [|T]) :- mymember(H, T).
?- mymember(1, [1,2,3]).
true ;
false.
?- mymember(10, [1,2,3]).
false.Чтобы после нахождения элемента, программа завершалась, можно записать предикат следующим образом:
mymember(H, [H|]):-!.
mymember(H, [|T]) :- mymember(H, T).
?- mymember(1, [1,2,3]).
true.Объяснение: если элемент находится в голове списка, то проверка завершена (утверждение истинно), иначе рекурсивно идет проверка хвоста списка.
Реализация предиката объединения списков:
myappend([], X, X).
myappend([A|X], Y, [A|Z]) :- myappend(X,Y,Z).
?- myappend([1,2], [2,3,x,y,z,W,E], X).
X = [1, 2, 2, 3, x, y, z, W, E].
?- myappend([1,2], X, [1,2,3,4,5,0]).
X = [3, 4, 5, 0].Объяснение: объединение пустого списка с непустым равняется непустому (он не меняется).Это как в математике: 0 + 2 = 2. Если первый список — непустой, то у него отсекается голова, она становится головой итогового списка, а полученный после отсечения хвост опять проверяется на пустоту: если пустой, то к нему добавляется второй список, иначе процесс отчесений головы (уже у бывшего хвоста первого списка) продолжается до получения пустого списка. К нему добавляется второй. Рекурсивно объединяются списки. Это тяжело объяснить, но если расписать на бумаге, то все станет понятным.
С помощью этого предиката можно найти недостающий список при конкатенации (объединении), если известны один из списков и итоговый список. Также можно найти последний элемент списка. Пусть это будет заданием обучающемуся.
Давайте реализуем последний предикат — удаление элемента:
myremove(X,[X|T],T):-!.
myremove(X,[Y|T],[Y|T1]):-myremove(X,T,T1).
?- myremove(x, [x,y,4,1,2], R).
R = [y, 4, 1, 2].
?- myremove(1, [2,3,4,1,2],R).
R = [2, 3, 4, 2].Объяснение: если нужный элемент находится в голове списка, то она просто отсекается, хвост — получившийся список. Иначе рекурсивно проходим по списку, и когда нужный элемент будет в голове, то произойдет его удаление.
По спискам можно еще о чем-то написать, но я думаю, что смог на каком-то уровне объяснить эту важную структуру.
6. Вывод
В заключение хотелось бы сказать, что я рассказал лишь малую часть о Прологе. Дальше я бы советовал начать усердно решать логические задачи, самому создавать предикаты обработки списков, научиться обрабатывать естественный язык. Но используя мою работу, человек сможет познакомиться с Прологом, напишет свою первую программу на этом замечательном языке, научится решать какие-то легкие логические задачи. Я старался максимально подробно все расписывать, чтобы у обучающегося вне зависимости от возраста не осталось непонятых моментов.
Список литературы:
Логическое программирование на Prolog для чайников
Материалы видеолекций по Логическому программированию
Видеоматериал Prolog 7. Обработка списков
Списки в Prolog
