AI на минималках 2: Генератор стихов на Prolog

в 19:40, , рубрики: AI, algorithms, Prolog, Алгоритмы, искусственный интеллект, Программирование

AI на минималках 2: Генератор стихов на Prolog

Мемная картинка

На картинке — четверостишье, сгенерированное моей программой.

Оказывается "стихи" писать легко, нужно только знать несколько необходимых ингредиентов: размер, ритм, рифма. "Стихи" в кавычках, потому что в настоящем стихосложении, как и в любом другом искусстве, незыблемых законов нет. Однако в классике очень много правил, при соблюдении которых получается писать неплохие стихи, даже если вы никогда раньше этого не делали. Причём эти правила довольно просто программируются: "в строке должно быть равно N слогов", "нечётные строки должны рифмоваться", "ударные и безударные слоги в строке должны идти в определённом порядке" и т.д. Перечислив все правила, я свёл задачу генерации стихов к простому комбинаторному поиску. Язык Prolog как раз и предназначен для таких задач — описании правил и генерации объектов, выполняющих эти правила.

Кто хочет научится писать стихи и познакомиться с Prolog, прошу под кат.

Как научиться писать стихи за 10 минут

Проще всего учиться на примерах великих поэтов. Возьмём классическое стихотворение Тютчева с расставленными ударениями:

Люблю грозу в начале мая, 9
Когда весенний, первый гром, 8
Как бы резвяся и играя, 9
Грохочет в небе голубом. 8

Гремят раскаты молодые, 9
Вот дождик брызнул, пыль летит, 8
Повисли перлы дождевые, 9
И солнце нити золотит. 8

С горы бежит поток проворный, 9
В лесу не молкнет птичий гам, 8
И гам лесной, и шум нагорный — 9
Всё вторит весело громам. 8

Ты скажешь: ветреная Геба, 9
Кормя Зевесова орла, 8
Громокипящий кубок с неба, 9
Смеясь, на землю пролила 8

Сразу видно, что стих состоит из нескольких четверостиший, в каждом из которых рифмуются строки одинаковой четности. Заметим, что ударные и безударные слоги чередуются в определённом порядке: _'_'_'_'_ (нижнее подчёркивание означает безударный, а кавычка — ударный слог). Такой ритмический рисунок называется размером стиха. Размер состоит из стоп, в каждой стопе ровно один ударный слог. У Тютчева размер двухсложный, с первым безударным, вторым ударным слогом. Такой размер называется ямбом. Есть и другие размеры, например хорей с ударением на первом слоге. Повторение одного размера в четверостишье задаёт стиху ритм, без которого даже с рифмой четверостишье будет звучать как проза.

Системы рифмовки тоже могут быть разные. У Тютчева рифмовка перекрёстная, ещё бывают кольцевая (рифмуются первая с последней и вторая с третьей строки) и смежная (первая со второй, третья с четвёртой).

Рифмовать слова тоже можно по-разному. Различают мужские и женские рифмы. В мужской ударение падает на последний слог, в женской на предпоследний. Есть ещё дактилическая рифма, где ударение падает на второй с конца слог, но к таким словам довольно сложно подобрать пару:

Дело было вечером,
Делать было нечего.

Получается примерно следующий алгоритм написания стихов:

  1. Выберите о чём будет стих. Часто через стихи поэты передают чувства.
  2. Напишите первый черновой вариант, пока без рифмы и ритма.
  3. Подгоните каждую строчку под определённый размер. Важно соблюдать ритмический рисунок.
  4. Зарифмуйте строчки по определённой системе.
  5. Отшлифуйте получившийся текст.
  6. Стих готов!

С практикой вам станет проще рифмовать слова и соблюдать ритм:

Шёл поэт по улице, 7
Кутался в пальто. 5
Всё пройдёт, забудется, 7
Время — решето. 5

Обратите внимание, ритмический рисунок совпадает у рифмующихся строчек. У второй и четвёртой хорей получается как бы "рваным", но ритм от этого не страдает.

Введение в Prolog

Теперь сформулируем правила, которым должны удовлетворять четыре строки в четверостишье:

  1. Строчки грамматически корректны, т.е. не нарушают правила русского языка.
  2. Строки рифмуются по определённой системе, возьмём перекрёстную.
  3. У рифмующихся строк совпадает ритмический рисунок.

Мы специально не стали брать "осмысленность" стиха, т.к. это требование в стихосложении довольно субъективное, его сложно объяснить машине, да и вообще, в любой грамматически верной строке можно найти смысл (глокая куздра глокочет бокра и кудрячет бокрёнка).

Получается настоящая комбинаторная задача: в пространстве всех возможных строк найти четыре, выполняющие данные правила. Остаётся только как-то их запрограммировать. В принципе, для этого подходит любой императивный язык, но Prolog подходит лучше всего, т.к. создавался специально для таких задач.

Prolog это логический язык программирования. Он очень сильно отличается от императивных языков тем, что все конструкции — декларативные, т.е. программы на Prolog описывают что надо сделать, а не как это сделать. Этим он похож на функциональные языки типа LISP. Prolog моделирует логику предикатов первого порядка.

Prolog можно рассматривать как некую СУБД или экспертную систему, в которой есть знания, и из этих знаний можно делать логические выводы с помощью правил. Знания выражают в виде фактов (предикатов) о внешнем мире. Например, вот так можно записать факт того, что Сократ смертен:

человек(сократ).
смертен(Х) :- человек(Х).

Слова в Prolog бывают либо атомами (сократ), либо предикатами (человек), либо переменными (Х). Атомы это некоторые объекты, предикаты это свойства объектов или отношения между ними. Переменные должны начинаться с заглавной буквы, атомы и предикаты с прописной. Предложения должны оканчиваться точкой. В Prolog нет ограничений на латиницу, поэтому слова можно писать и на русском. Первая строчка выражает факт того, что Сократ — человек. Вторая моделирует условие "каждый человек смертен". Части импликации разделяются знаком :- и меняются местами.

Теперь если открыть любой интерпретатор Prolog (на маке есть SWI-Prolog), то появится консоль со знаком ?-. Это экспертный режим, где можно задавать вопросы СУБД и получать ответы. Сохранив скрипт в файле socrates.pl и загрузив его командой [socrates]., мы сможем спросить является ли Сократ
смертным:

?- смертен(сократ).
true.

Система логически вывела нам факт смертности Сократа. Но это ещё далеко не всё, попробуйте вместо Сократа подставить переменную:

?- смертен(Неизвестно).
Неизвестно = сократ.

Prolog сам подобрал единственно возможное значение переменной "Неизвестно". Пролог следует т.н. гипотезе закрытого мира (closed-world assumption) — всё, чего нет в базе считается неверным:

?- смертен(аристотель).
false.

Хотя Аристотель был таким же человеком, но в нашей программе это не отражено, поэтому Prolog выводит false.

"Хорошо, и как же на этом программировать?" — спросите вы. Здесь Пролог очень схож с функциональными языками, где программы определяются рекурсивно. Рассмотрим как вычислить последовательность Фибоначчи. Определим отношение fib(n, f_n), означающее что $n$-ное число Фибоначчи равно $f_n$:

fib(0, 1).
fib(1, 1).
fib(N, F) :- N #> 1,
             M #= N - 1,
             K #= M - 1,
             F #= G + P,
             fib(M, G),
             fib(K, P).

Первые две строки задают известный факт, что первый и второй элемент последовательности равны 1. Затем идёт рекурсивное определение, которое можно прочесть так: "Отношение между двумя числами fib(N, F) верно только в том случае, когда N больше единицы, M равно N - 1, K равно M - 1, а F равно сумме G и P, которые находятся в отношениях fib(M, G) и fib(K, P)". Запятые тут означают логическое "И". Операторы сравнения #> и #= нестандартны для Пролога, они находятся в библиотеке CLPFD, идущей вместе с дистрибутивом SWI-Prolog. Эта библиотека "чинит" недостатки стандартных числовых отношений вроде =, > и т.д. Чтобы использовать библиотеку, нужно сразу после старта REPL консоли набрать ?- use_module(library(clpfd)).

Теперь откроем swipl, загрузим скрипт и введём ?- fib(10, X). Пролог выведет X = 89. То есть он подобрал первое значение переменной X, которое удовлетворяет этому отношению. Если нажать клавишу ';', то выйдет false, так Пролог говорит, что других значений X он найти не может. Теперь классный момент: введём ?- fib(X, 13). Пролог выдаст X = 6. То есть так можно вычислять еще и обратную функцию. Мы получили две программы по цене одной!

Ещё интересно как работают списки в Prolog. У списка есть голова (первый элемент) и хвост (остальные). Синтаксис такой: Список = [Голова | Хвост]. Например, если Список = [1, 2, 3, 4], то Голова = 1, а Хвост = [2, 3, 4]. Это разделение очень полезно при рекурсивном определении отношений. Вот так можно закодить отношение freq(E, L, F) которое выполняется когда элемент E входит в список L ровно F раз:

freq(_, [], 0).
freq(Element, [Head|Tail], F) :- Head #= Element,
                     F #= P + 1,
                     freq(Element, Tail, P),
                     !.
freq(Element, [Head|Tail], F) :- Head #= Element,
                     freq(Element, Tail, F),
                     !.

Сначала как обычно выполняется базовый случай: в пустом списке частота любого элемента равна нулю. Роль "любого элемента" здесь играет переменная "_". В Прологе так обозначаются "свободные" переменные, встречающиеся только один раз. Затем рассматривается два случая — когда голова списка равна подсчитываемому элементу и когда нет. В первом случае инкрементируется счётчик вхождений элемента в массив. Затем Пролог продолжает рекурсивно пробовать удовлетворять freq. Если запросить ?- freq([1, 2, 2, 3], 2, X), то интерпретатор построит примерно такую цепочку равенств для нахождения правильного значения Х:

X #= X1, Tail = [2, 2, 3]
X1 #= X2 + 1, Tail = [2, 3]
X3 #= X4 + 1, Tail = [3]
X5 #= X6, Tail = []
Последний вызов: freq(_, [], 0), X6 #= 0.

Развёртывая равенства получим X #= 2.

Восклицательный знак здесь играет важную роль. Это т.н. "cut operator", который обрезает дерево поиска интерпретатору. Он говорит "если интерпретатор дошел до меня, то не нужно пробовать удовлетворить другой вариант freq". Из-за этого у Х будет только одно возможное значение.

Комбинаторный поиск в Prolog

Prolog идеально подходит для комбинаторного перебора. Нужно только закодировать правила, которым подчиняются перебираемые объекты, и запустить интерпретатор. Рассмотрим классическую задачу генерации всех магических квадратов 3 на 3. Магическим называется квадрат, в котором все числа положительны и различны, а суммы в каждом столбце, строке и диагонали совпадают. Пример:

A|B|C   2|7|6
-|-|-   -|-|-
D|E|F = 9|5|1
-|-|-   -|-|-
G|H|I   4|3|8

Каким правилам подчиняются числа в квадрате?

  1. В квадрате 3х3 ровно 9 чисел.
  2. Каждое число целое и строго положительное.
  3. Все числа различны.
  4. Есть 7 равенств, выполняющие условие "магичности" квадрата.

С помощью библиотеки CLPFD можно очень легко закодировать эти правила в Прологе:

magic([A, B, C, D, E, F, G, H, I]) :- Vars = [A, B, C, D, E, F, G, H, I],
                                    Vars ins 1..100,
                                    all_different(Vars),
                                    A + D + G #= B + E + H,
                                    B + E + H #= C + F + I,
                                    C + F + I #= A + B + C,
                                    A + B + C #= D + E + F,
                                    D + E + F #= G + H + I,
                                    G + H + I #= A + E + I,
                                    A + E + I #= C + E + G,
                                    label(Vars).

Отношение magic определяет 9 различных переменных из интервала [1, 100] с семью равенств. Функция label позволяет назначить конкретные значения этим переменным. Если запустить ?- magic(S). то интерпретатор Пролога будет последовательно выводить все возможные магические квадраты 3х3.

Вернёмся к нашей оригинальной задаче: генерации стихотворений. Стихотворение состоит из четверостиший. Четверостишие определяется следующими правилами:

  1. Строчки грамматически корректны, т.е. не нарушают правила русского языка.
  2. Строки рифмуются по определённой системе, возьмём перекрёстную.
  3. У рифмующихся строк совпадает ритмический рисунок.

Всё, что нужно сделать — это корректно закодировать это правила на Прологе. Самое сложное здесь это первое правило. Грамматическая корректность это довольно непростое требование, грамматика русского языка очень богата, у нас есть спряжения, морфология, и проч. Поэтому я решил взять конкретные шаблоны, которые наверняка будут грамматически корректны. Все слова в настоящем времени и мужского рода:

Нечётные строчки: Прил Сущ Нар Глаг
Пример: Жёлтый жираф тихо спит, Маленький заяц быстро бежит
Чётные строчки: Нар Глаг Сущ
Пример: Громко поёт соловей, Быстро играет музыкант

Нужно только добавить достаточно слов каждой части речи, чтобы стихи получались богатыми.

Как это кодировать? Очень просто — вначале составляется словарь наподобие такого:

наречие(ушло, 1).
наречие(хило, 1).
наречие(хорошо, 3).
прилагательное(кроткий, 1).
прилагательное(дохлый, 1).
прилагательное(фирменный, 1).
глагол(ценит, 1).
глагол(читает, 2).
глагол(касается, 2).
существительное(бык, 1).
существительное(слон, 1).
существительное(укротитель, 3).

Второй аргумент указывает на порядковый номер ударного слога. В слове "кроткий", ударение падает на первый слог, а в слове "укротитель" на третий. Эта информация пригодится когда мы будет строить ритмический рисунок строчки.

Затем определяется предикат предложение:

предложение([А, Б, В, Г]) :- прилагательное(А, _),
                           существительное(Б, _),
                           наречие(В, _),
                           глагол(Г, _).

И похожий предикат для чётных строчек. Тогда Пролог будет генерировать корректные предложения запросом ?- предложение(П).

Теперь ко второму правилу рифмовки. Как определить что два слова рифмуются? Рифмуются слова, у которых ударение падает на тот же слог и у которых окончания похожи (зрелый — спелый, бедный — каретный, новый — здоровый). Есть такое понятие — парные буквы, наверняка вы ещё их в школе проходили. Вот несколько таких пар:

(а, я).
(б, п).
(в, ф).
(и, ы).
(с, ц).

Назовём все такие пары омофонными. Окончания рифмующихся слов могут отличаться, но только если разные буквы будут принадлежать одной паре. Например, пара "бедный — каретный", окончания "едный — етный" отличаются, но пара (д, т) — омофонная, поэтому рифма не нарушается. То есть, рифму можно описать следующим правилом:

  • Окончания рифмующихся слов отличаются не более чем на омофонные пары. Под окончанием здесь понимается часть слова начиная с ударного слога и до конца. Окончания у рифмующихся слов равны по длине.

Чтобы закодировать такое правило надо сначала определить все омофонные пары:

омофон_пара(а, я).
омофон_пара(б, п).
омофон_пара(в, ф).
омофон_пара(г, к).
омофон_пара(д, т).
омофон_пара(ж, ш).
омофон_пара(з, с).
омофон_пара(ч, щ).
омофон_пара(и, ы).
омофон_пара(е, э).
омофон_пара(у, ю).
омофон_пара(я, а).
омофон_пара(п, б).
омофон_пара(ф, в).
омофон_пара(к, г).
омофон_пара(т, д).
омофон_пара(ш, ж).
омофон_пара(с, з).
омофон_пара(щ, ч).
омофон_пара(ы, и).
омофон_пара(э, е).
омофон_пара(ю, у).
омофон_пара(н, м).
омофон_пара(м, н).
омофон_пара(ц, с).
омофон_пара(с, ц).

Затем определить предикат "похожие_по_звучанию(Слово1, Слово2)", который выполняется когда слова 1 и 2 отличаются не более чем на омофонные пары:

похожие_по_звучанию([], []).
похожие_по_звучанию([Б1|К1], [Б2|К2]) :- Б1 = Б2, похожие_по_звучанию(К1, К2).
похожие_по_звучанию([Б1|К1], [Б2|К2]) :- омофон_пара(Б1, Б2), похожие_по_звучанию(К1, К2).

Здесь слово разбивается на список своих букв и рассматриваются два случая: когда буквы равны и когда они принадлежат одной омофонной паре.

Зная всё это, написать предикат "рифмуется(Слово1, Слово2)" не составляет труда:

рифмуется(С1, С2) :- ударение(С1, У1),
                     ударение(С2, У2),
                     индекс_гласной(С1, У1, И1),
                     индекс_гласной(С2, У2, И2),
                     atom_chars(С1, Буквы1),
                     atom_chars(С2, Буквы2),
                     length(Буквы1, Д1),
                     length(Буквы2, Д2),
                     Д1 - И1 #= Д2 - И2, % ударение на тот же слог
                     slice(Буквы1, И1, Д1, Окончание1),
                     slice(Буквы2, И2, Д2, Окончание2),
                     похожие_по_звучанию(Окончание1, Окончание2),
                     С1 = С2.

Предикат atom_chars позволяет разбить слово на составляющие его буквы, а slice вычленяет ударное окончание из обеих слов. Обратите внимание на последнее требование: C1 = C2, оно нужно чтобы одно и то же слово не генерировалось при запросе ?- рифмуется(Слово1, Слово2).

Остаётся последнее правило: совпадение ритмического рисунка у строчек. Давайте договоримся, что ритмический рисунок строки будем записывать с помощью букв "б" и "у", где "б" означает безударный слог, а "у" ударный. Сам такой рисунок будем называть "шаблоном".

Например, у строки "Люблю грозу в начале мая" шаблон будет "бубубубуб", т.е. чистый ямб. Хорей будет выглядеть наоборот "убубубуб".

По каждой строчке в стихе можно строить такие шаблоны. Совпадением ритмического рисунка будет совпадение шаблонов. Как строить такие шаблоны? Нужно каждое слово в строке разбить на слоги, ударный слог записать как "у", остальные как "б" и повторить для всех слов.

Я не буду здесь приводить полный код этой процедуры, при желании вы можете ознакомиться с кодом всего проекта в открытом репозитории

Приведу только конечный вид предиката "стих", по которому можно генерировать четверостишия:

стих([П1, Щ1, Н1, Г1], [Н2, Г2, Щ2], [П3, Щ3, Н3, Г3], [Н4, Г4, Щ4], Р1, Р2, Р3, Р4) :-
    прилагательное(П1, _),
    существительное(Щ1, _),
    наречие(Н1, _),
    глагол(Г1, _),
    ритм_предложения([П1, Щ1, Н1, Г1], Р1),
    наречие(Н2, _),
    Н1 = Н2,
    глагол(Г2, _),
    Г1 = Г2,
    существительное(Щ2, _),
    Щ1 = Щ2,
    ритм_предложения([Н2, Г2, Щ2], Р2),
    прилагательное(П3, _),
    П1 = П3,
    существительное(Щ3, _),
    Щ1 = Щ3,
    Щ2 = Щ3,
    наречие(Н3, _),
    Н2 = Н3,
    Н1 = Н3,
    глагол(Г3, _),
    Г2 = Г3,
    Г1 = Г3,
    ритм_предложения([П3, Щ3, Н3, Г3], Р3),
    рифмуется(Г1, Г3),
    наречие(Н4, _),
    Н1 = Н4,
    Н3 = Н4,
    Н2 = Н4,
    глагол(Г4, _),
    Г1 = Г4,
    Г3 = Г4,
    Г2 = Г4,
    существительное(Щ4, _),
    Щ1 = Щ4,
    Щ3 = Щ4,
    Щ2 = Щ4,
    ритм_предложения([Н4, Г4, Щ4], Р4),
    рифмуется(Щ2, Щ4).

классика(Стих) :- стих(А, Б, В, Г, хорей, рваный_хорей, хорей, рваный_хорей), Стих = [А, Б, В, Г].

Здесь включены все три правила стихосложения (грамматическая корректность, рифма, ритм) и ещё добавлены условия на различность X = Y чтобы слова не повторялись.

Наконец, можно проверить как это всё работает если набрать ?- классика(Стих).

Что дальше?

Понятно, что всё описанное это только proof of concept, можно и дальше развивать эту тему. Например, добавить ещё слов в словарь, расширить грамматику, чтобы она включала разные времена и роды слов. Можно также определить новые шаблоны стихотворений, отличных от классики, да и вообще поле для экспериментов тут очень богатое.

Надеюсь вам понравилась статья и вы узнали что-то новое. Ссылка на репозиторий проекта: prolog-poetry. Там же есть полная инструкция по запуску.

Автор: Евгений Грязнов

Источник


* - обязательные к заполнению поля


https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js