| Преподаватель | Дата | Оценка |
|---|---|---|
| Сошников Д.В. | ||
| Левинская М.А. |
Комментарии проверяющих (обратите внимание, что более подробные комментарии возможны непосредственно в репозитории по тексту программы)
В результате выполнения курсового проекта я получила следующие навыки и знания:
- Углубила свои познания в теоретической части логического программирования. После написания эссе мне стала понятна природа типов в логических языках, и почему создатели языков делали выбор в пользу типизации или ее отсутсвия. Теперь, если передо мной встанет задача, для решения которой лучше всего подойдет логическая парадигма, я точно сделаю адекватный выбор инструмента с учетом использования типов. Возможно, мне когда-нибудь придется участвовать в разработке логического языка, вот тогда-то я применю свои познания и приму грамотное архитектурное решение.
- Научилась обрабатывать данные в формате GEDCOM. Если в будущем мне понадобится обрабатывать генеалогические деревья, то мне не придется разбираться со структурой их хранения.
- Написала парсер, обрабатывающий текстовые данные. Пришлось вспомнить регулярные выражения. Задачи обработки текста встречаются в любом приложении хоть как-то связанном с текстовыми данными, поэтому это, несомненно, универсальный и полезный навык.
- Закрепила навыки, полученные в 3 лабораторной работе, связанные с поиском в пространстве состояний. В КП это было необходимо для построения цепочки родства.
- Закрепила навыки, полученные в 4 лабораторной работе, связанные в грамматическим разбором предложения.
- Создать родословное дерево своего рода на несколько поколений (3-4) назад в стандартном формате GEDCOM с использованием сервиса MyHeritage.com
- Преобразовать файл в формате GEDCOM в набор утверждений на языке Prolog, используя следующее представление: с использованием предиката
child(ребенок, родитель),male(человек),female(человек) - Реализовать предикат проверки/поиска троюродного брата или сестры
- Реализовать программу на языке Prolog, которая позволит определять степень родства двух произвольных индивидуумов в дереве
- [На оценки хорошо и отлично] Реализовать естественно-языковый интерфейс к системе, позволяющий задавать вопросы относительно степеней родства, и получать осмысленные ответы.
Я зарегестрировалась на сервисе MyHeritage.com, создала свое родословное дерево, в нем оказалось 63 человека. Потом я экспортировала дерево из этого сервиса в формате GEDCOM.
В условиях ограниченного времени мне показалось нецелесообразным изучать новые для себя технологии и языки (хотя в условиях более мягких дедлайнов по остальным курсам, я бы все-таки сделала это). Поэтому выбор доступного мне инструмента для парсинга был невелик -- С++, Python и Prolog. Основная проблема заключалась в поиске определенных данных и аккумулирования их в соответствующих структурах с последующей записью в выходной файл. Это легче всего сделать на скриптовом языке, поэтому я выбрала Python. К тому же, я уже использовала его для парсинга в других лабораторных работах, где передо мной стояла задача парсинга веб-страниц. Это все-таки немного отличается от парсинга GEDCOM файла.
Программа работает до невозможного просто. Построчно проходя по файлу, мы находим id человека, его имя и фамилию и добавляем эту информацию в словарь, находим пол человека и добавляем его в соответсвующий список male или female, находим информацию о семье (муже и жене), если у них есть дети, то печатаем предикаты child в выходной файл. После прохождения всего файла, печатаем предикаты female и male из списков female и male. В программе используется модуль re, который дает возможность использовать, в данном случае, простые регэкспы.
UPD: парсер был переписан. Была предпринята попытка использовать функциональный стиль на Питоне. Старую версию парсера можно найти в ветке master. В новом парсере я использую лямбда-выражение, функции высших порядков (map, filter) и итератор. Логика осталась такой же, как и в предыдущей версии, но изменилась структура программы. В отдельные функции вынесены поиск id, имя и фамилии и пола. Для составления предикатов child при проходе по файлу используется итератор. Все также используются регулярные выражения.
Согласно варианту мне нужно реализовать предикат поиска троюродных братьев и сестер (triple). Для его реализации я написала еще два предиката -- double (поиск двоюродных братьев и сестер) и sibling (поиск братьев и сестер).
Предикат sibling проверяет, есть ли общие родители у двух человек и имеет проверку, не один и тот же ли это человек.
sibling(Person, Sibling):-
child(Person, P),
child(Sibling, P),
Person \= Sibling.Предикат double проверяет двоюродное родство. Двоюродное родство означает, что родители двух человек являются братьями или сестрами друг друга. Поэтому проверяем родство между всеми родителями данных людей.
double(Person, BroOrSis):-
child(Person, P1),
child(BroOrSis, P2),
sibling(P1, P2),
Person \= BroOrSis.Предикат triple проверяет троюродное родство, принцип его работы такой же, как и у предиката double, только теперь проверяем родителей на двоюродное родство.
triple(Person, BroOrSis):-
child(Person, P1),
child(BroOrSis, P2),
double(P1, P2),
Person \= BroOrSis.Результат работы:
?- triple('Anastasia Dovzhenko',X).
X = 'Ivan Gavrov'
X = 'Alexey Gavrov'
X = 'Vladimir Meshcheryakov'
X = 'Ksenia Meshcheryakova'
X = 'Ksenia Makhnina'
X = 'Pasha Makhnin'
X = 'Ekaterina Parechina'
X = 'Svetlana Parechina'
X = 'Valeria Snetkova'
X = 'Maria Sultanova'
X = 'Daria Sultanova'
false.
?- triple('Nadezhda Libgot',X).
false.Используем поиск в ширину для того, чтобы найти кратчайшее отношение родства. Реализуем предикаты check_link, для определения прямых отношений между двумя людьми. Прямые -- то есть люди связаны на прямую, а не через какого-то человека. В итоге есть проверка отношений муж, жена, брат, сестра, отец, мать, сын, дочь, ребенок, родитель. Я не использовала правила для получения дальнего родства, чтобы при поиске цепочек связи между людьми, она не "перескакивала" через родственников, которые связаны на прямую. Далее находится цепочка родственников, по которой и связаны эти люди, затем эту цепочку переводим в цепочку родства и получается ответ.
Результат работы
?- relative('Anatoly Dovzhenko','Kirill Libgot',X).
X = [father, husband, daughter].
(т.е. Anatoly Dovzhenko является отцом мужа дочери Kirill Libgot)
?- relative('Julia Dovzhenko','Anastasia Dovzhenko',X).
X = [wife, brother, father].
(т.е. Julia Dovzhenko является женой брата отца Anastasia Dovzhenko)
?- relative_thread('Lev Libgot','Maria Nosova',X).
X = ['Lev Libgot','Kirill Libgot','Nadezhda Libgot','Maria Nosova']
?- relative_thread('Ksenia Meshcheryakova','Ekaterina Nosova',X).
X = ['Ksenia Meshcheryakova','Lyubov Meshcheryakova','Gennady Nosov','Nikolay Nosov','Ekaterina Nosova']
?- check_link(sister, 'Maria Sultanova', X).
X = 'Daria Sultanova'.Обрабатываем запросы, выполненые на естественном языке и на основе запроса проверяем истинность высказывания или находим родственников. Запоминается последнее имя, на которое производился запрос, с помощью предиката nb_getval. Сначала проверяем корректность построения вопроса. Затем, в зависимости от постановки вопроса, ищем ответ. При анализе предложения также проверяем корректность построения и разбираем его по частям, оборачивая части вопроса в соответсвущие структуры.
Приведу пример одного из правил для предиката ask_question, все остальные построены аналогичным образом. Это правило находит ответ на вопрос, сколько определенных родственников имеет какой-то человек. Сначала мы проверяем корректность входных данных с помощью предикатов question_word, quantity, purals, help_word, male, female, have_has, question_mark. Также запоминаем, относительно имени какого человека задается вопрос, с помощью встроенного предиката nb_setval. Это потребуется в дальнейшем для обработки запросов с местоимениями. Приводим множественное число к единственному в предикате pural. ask_relative ищет всех запрашиваемых родственников заданного человека, а setof создает список из найденных уникальных имен. Далее получаем длину этого списка и печатаем результат в нужном порядке.
ask_question(List):-
List = [A,B,C,D,E,F,H],
question_word(A),
quantity(B),
purals(C),
help_word(D),
(male(E);female(E)),
nb_setval(lastName,E),
have_has(F),
question_mark(H),
pural(C1,C),
setof(X,ask_relative(X,E,C1),T),
length(T,Res),!,
write(E),
write(" have "),
((Res =:= 1,write(Res),write(" "),write( C1));(\+(Res =:= 1),write(Res),write(" "),write( C))),!.Результат работы
?- ask_question([how,many,brothers,does,'Nadezhda Libgot',have,?]).
Nadezhda Libgot have 2 brothers
true.
?- ask_question([how,many,sisters,does,'Kirill Libgot',have,?]).
Kirill Libgot have 1 sister
true.
?- ask_question([how,many,brothers,does,he,have,?]).
Kirill Libgot have 2 brothers
true.
?- ask_question([who,is,'Nadezhda Dovzhenko',"'s",son,?]).
Alexander Dovzhenko is Nadezhda Dovzhenko's son
true
Igor Dovzhenko is Nadezhda Dovzhenko's son
true.
?- ask_question([who,is,her,son,?]).
Alexander Dovzhenko is Nadezhda Dovzhenko's son
true
Igor Dovzhenko is Nadezhda Dovzhenko's son
true.
?- ask_question([is,'Tatiana Gavrova','Victor Gavrov',"'s",wife,?]).
true.
?- ask_question([is,'Natalia Makhnina',his,daughter,?]).
true.
?- analysis([who,is,'Igor Dovzhenko',"'s",brother,?],X).
X = sentence(question_type(questionWord(who), auxiliaryVerb(is)), names(person('Igor Dovzhenko', "'s")), relationship_(brother), questionMark(?)) .
?- analysis([how,many,sons,does,'Julia Dovzhenko',have,?],X).
X = sentence(question_type(questionWord(how), much_many(many)), relationship_(sons), helpWord(does), names(person('Julia Dovzhenko')), haveHas(have), questionMark(?)) .
?- analysis([is,'Maria Nosova','Tikhon Nosov',"'s",wife,?],X).
X = sentence(question_type(auxiliaryVerb(is)), names(person('Maria Nosova'), relative_('Tikhon Nosov', "'s")), relationship_(wife), questionMark(?)) .Полученные навыки и знания я описала в начале этой работы, поэтому здесь хотелось бы сказать о плюсах и минусах моей работы и о курсе в целом.
Как уже было замечено в 3 лабораторной работе, поиск в ширину, который я использую для построения цепочки родства, имеет экспоненциальную сложность по памяти, поэтому если цепочка будет слишком длинной, то произойдет переполнение стека, и мы не получим никакого результата. Не считая этого, мой определитель родства работает корректно и может построить цепочку для любых двух людей из дерева. Также мы можем проследить, через каких именно родственников идет эта связь. Мне кажется, что можно было бы визуализировать родословное дерево, например, с помощью библиотек d3.js ли cytoscape.js. Сделать небольшое веб-приложение. Когда мы просто пишем какие-то запросы на определение цепочки родства, не всегда понятно, правилен ли результат. А с помощью визуализации все было бы наглядно. Разбор предложений было реализовывать гораздо проще, чем если бы я это делала с помощью императивного языка. Вообще было несложно работать с генеалогическим деревом, потому что это самый распространенный пример задачи, когда речь идет о логических языках программирования. Такие примеры есть на первых страницах любого учебника по изучению логических языков программирования, и несколько раз упоминались в наших лекциях.
Отдельно хочется отметить написание реферата. Было достаточно сложно найти релевантные источники по моей теме. Типизация в логических языках как ни что другое связано с их математической составляющей. Мне не хватало знаний в теории формальных логик. На самом деле я рада, что мне досталась именно такая тема, написание реферата помогло мне лучше понять природу логического программирования и разобраться с типизацией в целом.
Данная работа показывает реальную задачу, при решении которой лучше всего использовать логический язык программирования. Это, несомненно, полезный опыт, нежели если бы мы реализовывали какие-то абстрактные предикаты, не имеющие никакого практического применения. Этот курсовой проект был мне очень интересен, я получила большое удовольствие от работы над ним. Данный курс дался мне нелегко, так как тяжело было перестроиться на новую парадигму программирования, но впечатления, которые он оставил и опыт, подарили мне желание изучать все больше концептуально разных технологий, языков и идей.