Генетическое программирование для тестирования компилятора: опыт аспиранта ML-лаборатории ИТМО
Виктор Петухов, студент второго курса аспирантуры Университета ИТМО и техлид в одной из команд проекта Kotlin в JetBrains (занимается компилятором Kotlin), решил совместить работу с детальным изучением профессиональной проблематики в научном формате и присоединился к лаборатории машинного обучения ИТМО. Рассказываем, что из этого получилось.
Фотография Marc Reichelt / Unsplash.com
История вопроса
Языки программирования — фундамент огромного спектра продуктов, сервисов и критически значимой инфраструктуры. В своей научной статье по этой теме Виктор подчеркивает, что ошибки в коде компиляторов действительно могут привести к существенным последствиям. Однако количество всевозможных тестовых сценариев для них обычно крайне велико, поэтому составлять их приходится с привлечением интеллекта — человеческого или «искусственного», чтобы должным образом исследовать наиболее подверженные ошибкам части компилятора.
Но автоматическое составление таких тестов обладает ограничениями. Как правило, мы тяготеем к генерированию семантически корректных фрагментов кода, минуя парсер (самую простую часть компилятора) и пробираясь к самым сложными частям: подсистеме вывода типов, механизму разрешения вызовов и прочим. Если использовать для этого формальную модель, такую как грамматику, доля получаемых семантически корректных фрагментов кода будет слишком мала.
С помощью методов машинного обучения можно улучшить ситуацию — добиться большого количества генерируемых семантически корректных примеров, а также попытаться решить интересные второстепенные задачи. Такие как направленную генерацию кода — например, на оптимизацию величины времени работы компилятора или потребляемой им памяти при компиляции. Так можно протестировать производительность компилятора.
Задача попутной оптимизации характеристики производительности при генерации кода является не простым дополнением к произвольной генерации. На данный момент над этой проблемой работает не так много специалистов, поэтому Виктор увидел здесь возможность для развития профессиональных и научных компетенций — решил предложить такой способ генерации исходного кода на Kotlin, чтобы «либо время компиляции, либо потребляемая память были максимальными».
Как это работает
Использование генетического программирования для тестирования производительности компилятора подразумевает, что с каждой новой генерацией кода осуществляется оптимизация некоторого целевого параметра — например, использованной памяти.
Генератор кода, в свою очередь, также должен обеспечивать как можно большую долю семантически корректных фрагментов. Для этого Виктор — вместе с коллегами — разработал генератор с оператором скрещивания, который учитывает типы доступных переменных.
Пример скрещивания фрагментов исходного кода с учетом типов
На скриншоте продемонстрирована возможная подстановка одного фрагмента кода вместо другого (скрещивание двух файлов с исходных кодом). Здесь видно, что такая подстановка будет совместима по типам, в соответствии с реализованным оператором скрещивания. В месте, куда подставляется фрагмент кода, присутствуют все требуемые типы или их подтипы, присутствующие внутри подставляемого фрагмента.
В ходе эксперимента были обнаружены некоторые проблемы в производительности компилятора Kotlin — например, экспоненциальный рост времени анализа лямбд в правой части оператора »+=» по мере увеличения глубины вложенности этих лямбд. Команда компилятора уже занимается этой проблемой. На скриншоте далее — показываем, как изменяется время компиляции приведенного фрагмента кода, если добавлять вложенные лямбды.
Пример точечной проблемы, которую удалось обнаружить
Что дальше
Сейчас проектом занимаются пять человек. Это — коллективный труд исследователей Университета ИТМО и представителей JetBrains. Коллеги убеждены в целесообразности продолжения исследования и совершенствования предложенного Виктором подхода.
«Мы хотели бы реализовать и оператор мутации, чтобы избавиться от предвзятости относительно начального набора данных и генерировать принципиально новые конструкции языка. Помимо генетического программирования мы планируем применить здесь и генеративные модели, а затем провести сравнение результатов и подумать о разработке методологии тестирования производительности компиляторов»
— Виктор Петухов, аспирант второго года обучения, программист — на факультете ИТ и программирования, программист в JetBrains и в команде компилятора Kotlin.
Дополнительное чтение в нашем блоге на Хабре:
