Поэтический дискурс с привкусом реверс-инжиниринга

в 22:00, , рубрики: python, лингвистические технологии, Программирование, реверс-инжиниринг

«Старик Ассемблер нас заметил,
И в гроб сходя, благословил»

image

Однажды я решил написать программу, сочиняющую стихи. Алгоритм придумался быстро – в конце сочиняемых строф ставить рифмующиеся слова, а остальную часть строфы заполнять словами с учетом рифмы, ритма, и вероятности их нахождения рядом с другими словами, взятыми из готовых связных текстов. Эдакие марковские цепи с прикрученными к ним рифмами.

Перед тем, как реализовывать алгоритм, я решил посмотреть, что уже создано другими. Первым в Яндекс-поиске нашелся (кто бы сомневался!) Яндекс.Автопопоэт, использующий обученные на стихах классиков нейронные сети. Вторым пунктом шла программа «Помощник поэта», при ближайшем рассмотрении оказавшаяся обычным словарем рифм. А вот на третьем месте был сайт известного писателя и матерого фидошника Lleo aka Леонида Каганова.

Почему он там оказался? Потому, что в бытность студентом Горного института, Lleo написал сочиняющую стихи программу в качестве дипломной работы. Не знаю, насколько поэтичной была защита такого диплома, но программа, по-видимому, работала неплохо – на сайте автора были выложены написанные ею стихи. Там же нашлась и сама программа, работала она под MS-DOS и 32-битным расширителем DOS/4GW. Были выложены также и исходники этой версии. Из пояснительной записки к диплому я узнал, что была также версия под OS/2, видимо, даже с графическим интерфейсом, но ее исходников не нашлось. Зато MS-DOS-версию можно было запустить под DOSBox и увидеть ее в действии: она действительно выдавала рифмованные и довольно связные стихи, хотя и не очень осмысленные. Для 1996 года, когда Lleo написал эту программу, такой уровень автогенерированных стихов был очень крут. На мой взгляд, они даже не сильно хуже стихов Яндекс.Автопопоэта. А может быть Lleo и стал известным писателем с помощью доработанной версии своей программы?! (Скандалы, интриги, расследования! Шучу, конечно, но кто знает…).

Я стал изучать как работает эта программа. Для сочинения стихов ей было нужно 2 файла – база слов и разметка рифм и размера сочиняемых виршей. Исходники были на Ассемблере, около 3500 строк исходников под TASM. Автор программы написал по этому поводу: «я остановил свой выбор для решения большинства задач именно на Ассемблере. Именно на нем я выполнял все учебные работы, позволяющие выбирать язык программирования. Главным образом потому, что мне писать и отлаживать программу на этом языке быстрее и проще — он позволяет более гибко взаимодействовать с машиной». И тут я полностью согласен – Ассемблер очень гибок, и не навязывает какую-либо парадигму программирования. Хотя конечно же, быстрее писать программы на современных языках, собирая их из готовых библиотек-кубиков. В исходниках имелись все характерные приметы Ассемблерных программ того времени – короткие не всегда вразумительные, понятные только автору названия переменных и функций; фиксированные размеры используемых массивов с комментарием «наверное хватит»; куча глобальных переменных, и местами остроумные авторские комментарии и сообщения об ошибках, вроде «Творческий кризис!!!» в тот момент, когда у программы кончаются слова для подбора рифм. Вот в таком духе:

@@punkt13:
    ;call io
    ;db 13,10,'{{F_LEVEL}}=',0
    ;movzx eax,[F_LEVEL]
    ;call pr_dec

    cmp [nomer_LEVEL],0 ;13) Если слово не оконечное ■ к 16
    jne @@punkt16

    ;call io
    ;db 13,10,'ОШИБКА ПОИСКА РИФМЫ',0
    ;call key

    cmp [F_LEVEL],0 ;13.0) если ■сфера поиска■ = вся база
    jne @@punkt14
    cmp [FREE_RHYME],0  ;13.1) Если и рифма была свободная, то
    je @@error_twor     ;■ТВОРЧЕСКИЙ КРИЗИС■, конец
    stc
    ret ;вернуться с неудачей

@@punkt14:
    cmp [F_LEVEL],1 ;14) ;Если ■сфера поиска■ = ■заданная тематика■, то
    je @@565656
    ;call io
    ;db 13,10,'поиск шел в АССОЦИАЦИЯХ, теперь будет в теме',0

Тут-то все и началось – увлекшись изучением исходников, я забыл о том, что изначально собирался реализовать алгоритм с нуля, а, вспомнив собственные ассемблерные программы, решил портировать алгоритм Lleo на современный язык программирования. Тем более, что этот алгоритм сильно походил на тот, что я задумывал. В качестве языка для портирования я выбрал Python – на нем очень удобно работать с текстом.

Разбор программы начался с того, что я прошелся по коду и убрал весь закомментированный код, его там было много. Оставил только закомментированный отладочный вывод – он помогал понять что происходит в данном месте программы. Далее я удалил все сугубо служебные вызовы, наподобие получения ключей командной строки и файлового ввода-вывода. Теперь, когда остался только код, касающийся алгоритма, я стал в нем разбираться и портировать на Python. У тех функций, назначение которых было ясно, я сразу заменил названия на понятные или, переписав на Python, удалил ассемблерный код. Остальные — стал построчно переводить на Python. Построчно, конечно, сильно сказано — в программе широко использовались глобальные переменные состояния, и, чтобы такого не было в Python-коде, во многих местах алгоритм приходилось полностью переписывать, без оглядки на строки оригинальной программы. На этом этапе код выглядел таким образом — еще не Python, но уже не Ассемблер:

randomValue = init random(777)

if curMode=='C':            
    print'НАПИСАНИЕ СТИХОТВОРЕНИЯ',13,10,' база: ',0
    BASEname    
    NAME_SHABLON    
    call loadBASE   
    call CREATE
else if curMode=='U':           
    print'ПРОДОЛЖИТЬ РАССТАНОВКУ УДАРЕНИЙ',13,10,' база: ',0        
    call loadBASE       
    call stat       
    call setUdarenie_N
    call saveBASE
    #        call automat - автом расст удар
    #   jmp @@udara1        
    return        

К сожалению, сразу я не догадался заглянуть в текст пояснительной записки к диплому, будучи уверенным, что там написана стандартная лабуда про экономическое обоснование. Из-за этого, собственно алгоритм стихов и формат базы данных слов, я буквально реверс-инжинирил – по вразумительности названий переменных и функций, исходники программы не очень далеко ушли от листинга дизассемблера. Хотя в целом, алгоритм стихов и формат словесной базы описаны в дипломной записке. Каюсь и посыпаю голову пеплом. Хорошо, что их разбор заняло не больше пары-тройки вечеров. Кроме того, в документации оказались далеко не все детали формата и алгоритма, так что позже реверс-инжиниринг продолжился. Для работы с бинарными данными, в Python нашлась очень удобная функция unpack. И, немного повозившись с порядком байт данных в данных (естественно тут он little endian, так как программа написана под Intel-процессор), я смог загрузить словесную базу. Формат файла с ритмом стиха был текстовым, и очень простым, код его загрузки разбирать не понадобилось.

Теперь следовало разобраться в собственно алгоритме написания стихов. Как уже я писал выше, в целом, он был описан в пояснительной записке, но некоторых деталей там не было. Например, то, что шаблон стиха задан в обратном порядке – от конца строфы, к началу. Так же, как и то, что латинская буква ‘p’ везде заменяется на русскую 'р' – наследие FIDO, где с русской «р» был глюк, и ее везде заменяли на латинскую, так что в скачанных из FIDO русскоязычных текстах «р» везде была латинской, и ее следовало преобразовать обратно в русскую. Ну и другие подобные мелочи. В целом же, алгоритм был похож на описанные в начале статьи марковские цепи с рифмами, но выделялся тем, что использовал стек для сохранения состояния во время написания строфы, с возможностью отката состояний в том случае, если алгоритм зайдет в тупик, не найдя слова с нужным ударением и количеством слогов. В коде была также видна попытка сделать сочинение стихов на заданную тему, для чего выбиралось начальное слово этой темы, и дальше поиск шел по связанным с ним словам. Но похоже, эта фича так и не заработала, и в функции make_RND_FIELD_TEMA остался только 1 захардкоденный индекс слова, с которого программа начинает подбор слов.

В процессе разбора программы встречались забавные моменты.
Например, в начале программы шел такой фрагмент:

jmp @@skip      ; Это...
db  'WATCOM' ; И это нужно для того, чтобы работало под DOS4GW
@@skip:

Дело в том, что 32-битный расширитель DOS/4GW был написан для программ, скомпилированных коммерческими компиляторами от Watcom, и сам являлся коммерческим продуктом. И то, что программа скомпилирована именно компилятором от Watcom, определялось по строке "Watcom" в начале кода программы. Если этой строки не было, то DOS/4GW работать отказывался. Справедливости ради, замечу, что продвинутые люди в то время пользовались расширителем PMODE/W by Tran, где такой ерунды нет, который заметно меньше по размеру, бесплатен, и умеет приписываться к программе, в то время, как DOS/4GW обычно лежит в виде отдельного исполняемого файла.

Был еще такой кусок кода:

proc bswap_eax ;я же не виноват, блин, что у 386 процессора нет bswap!
mov [bswap_mes],eax ;приходится извращаться...

Действительно, команды bswap на 80386 процессоре не было, она появилась, начиная с 80486 и оказалась очень удобна, например для конвертирования порядка байт little endian -> big endian. Так что народ писал такие вот функции и комментарии.

Еще один курьез приключился когда я тестировал алгоритм написания стиха. Для теста я задал такой конец строфы, чтобы в рифму однозначно подставилось слово "занято", которое я точно видел в файле БД слов. Однако эта рифма почему-то не находилась. Оказалось, что в БД записано слово "занят", а "о" в конце — это часть служебных данных — указатель на ассоциированное с ним слово. То, что это была буква «о» — просто случайное совпадение.

Когда написание стихов заработало, я быстренько запилил написание прозы – обычные марковские цепи, и захотелось бОльшего – чтобы моя программа умела сама генерировать из текста словесную базу, а не только пользоваться готовой от оригинальной программы. Генерации базы оказалась посвящена чуть ли не бОльшая часть программы, и по продуманности алгоритма работы, эта часть впечатлила меня сильнее, чем та, что сочиняет стихи. Фактически, она делает всю подготовительную работу для сочинения стихов: умеет из вводимого текста парсить слова, разбивать их на слоги, и даже автоматически расставлять ударения на основе ранее набранной статистики ручной расстановки ударений по слогам. Хотя, ударения ставятся далеко не всегда корректно. И, насколько мне известно, в русском языке нет какого-либо устойчивого правила расстановки ударений. База ударений хранилась в отдельном файле $$$$SLOG.BSY, формата которого в дипломной записке описано не было. Тут снова пришлось немного реверс-инжинирить.

Когда генерация базы данных слов заработала, уже можно было начать экспериментировать с различными текстами. В результате экспериментов, выяснилось, что взятый из программы алгоритм разбиения слов на слоги не всегда работает корректно, и я переписал его с нуля. Это позволило также доработать алгоритм получения рифмующегося окончания – теперь он работает именно со слогами и ударениями, а не просто идет до нужной по порядку гласной, полагаясь на этот признак для поиска нужного слога.

После этого, весь функционал я запаковал в объекты, разложил по модулям, и быстренько запилил использующий эти модули скрипт на Python, работающий из командной строки, запускающийся с теми же ключами, и умеющий все то же, что и оригинальная программа. А еще он умеет загружать базы от оригинальной программы, хотя сохраняет их уже в своем формате – сериализацией данных через Python pickle. Хотя алгоритм оригинальной программы изрядно перелопачен, во многих местах я оставил оригинальные комментарии – читать их интересно, и они хранят дух той эпохи. Кроме того, будучи запущенной с ключом –oldschool, скрипт выводит в консоль help оригинальной программы, где есть куча приветов разным человекам и пароходам.

Вот пример сочиняемых стихов:

***
 мАркеров И смОтрит нА
 конурУ И именА
 втОрник Я сначАла Ехал
 консультАция должнА

 пАмять хИтрость И даЕт
 вскАкиваю И поЕт
 нАдо А потОм Я вЫшел
 головОй И продаЕт

***
 какИми словАми сейчАс нЕ смущАет
 вокрУг стУк однАжды агА иногдА
 листОчков врАг нОмер одИн предлагАет
 прогрАмма нЕ пЕрвый трамвАй шЕл кудА

 покАзывает чтО нибУдь сО словАми
 егО зА компьЮтер забЫла включИть
 старАясь нЕ врЕмя семЕстра А сАми
 потОм Я самА проезднОй нЕ учИть

В результате, мы имеем программу, сочиняющую графоманские стихи, с помощью которой довольно интересно экспериментировать с различными текстами.

Что еще к ней можно доделать хорошего:

  • при генерации базы слов составлять словарь рифм – это позволит ускорить подбор слов
  • научить программу использовать словари ударений из Интернета, что позволит более корректно автоматически расставлять ударения (но все равно не всегда правильно – в русском языке есть слова с одинаковым написанием, но разным ударением)
  • научить программу сочинять на тех иностранных языках, где написание однозначно определяет звучание слова. С английским это будет проблематично – там, как говорится, «Пишем Ливерпуль читаем Манчестер», а вот с французским – вполне реально. Вдобавок, там проще расставлять ударения – они (почти) всегда падают на конец слова.

Вот собственно, все, о чем я хотел рассказать в этой статье.
Плоды своих трудов я выложил на Github.

Всем спасибо за внимание!

Автор: sunman

Источник

Поделиться

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