Модель и реализация компилятора функционального языка Common LISP

Цель исследований заключается в создании модели компилятора функционального языка Common Lisp, реализации этой модели и тестировании модели компилятора с помощью целевой виртуальной машины, чтобы увеличить скорость выполнения программ.

Методы. С помощью денотационной семантики была построена формальная модель компилятора функционального языка Common Lisp. Компиляция происходит в несколько этапов. На первом этапе исходный язык преобразуется в промежуточный lambda-язык, в котором все макросы раскрываются, встроенные формы преобразуются в аналогичные выражения, а имена переменных заменяются на локальные, глобальные и глубокие ссылки. На втором этапе выражение на промежуточном языке преобразуется из древовидной структуры в линейный список из примитивных инструкций целевой виртуальной машины.

Результаты. Полученные в результате компиляции примитивные инструкции кодируются с помощью специального ассемблера в числовой код для выполнения на целевой виртуальной машине. Также в результате компиляции получаются список констант и размер памяти необходимый для работы скомпилированной программы. Целевая виртуальная машина состоит из отделов памяти для кодированной программы, констант, глобальных переменных, стека, списка кадров активации, регистров (аккумулятор, указатель стека, указатель команд, текущий кадр активации). Кадры активации представляют собой объекты-массивы, которые хранят указатель на предыдущий кадр, номер уровня глубины вызовов и локальные аргументы. Сборка мусора происходит с помощью метода пометки и очистки.

Заключение. В результате работы была построена и реализована модель компилятора функционального языка Common Lisp. По сравнению с интерпретатором скорость работы программы возросла в среднем в 20 раз. Дальнейшее увеличение скорости можно достичь с помощью различных оптимизаций компилятора на разных стадиях. Из простых оптимизаций можно отметить: оптимизацию арифметических выражений, устранение лишних команд, упрощение выражений.

1. Sperber Michael, Dybvig R. Kent, Flatt Matthew, Van Straaten Anton; et al. (August 2007). Revised6 Report on the Algorithmic Language Scheme (R6RS). Scheme Steering Committee. Retrieved 2011-09-13.

2. The Racket Manifesto (PDF) / M. Felleisen, R.B. Findler, M. Flatt, S. Krishnamurthi, E. Barzilay, J. McCarthy, S. Tobin-Hochstadt // Proceedings of the First Summit on Advances in Programming Languages; 2015. P. 113–128.

3. Абельсон Х., Сассман Д. Структура и интерпретация компьютерных программ, КДУ, 2022. 608 с.

4. Hart Tim, Levin Mike. AI Memo 39-The new compiler (PDF). Archived from the original (PDF) on 2020-12-13. Retrieved 2019-03-18.

5. Krishnamurthi Shriram. Programming Languages: Application and Interpretation. 3-thd edition. - Shriram Krishnamurthi, 2022. 376 p.

6. Ершов А. П., Покровский С. Б. Эволюция языков программирования // Проблемы информатики. 2017. № 2(35). С. 70-79. EDN ZOLFPJ.

7. Душкин Р. В. Функциональное программирование на языке Haskell. М.: ДМК Пресс, 2016. 608 с.

8. Романов С. С. Ключевые понятия и особенности объектно-ориентированного программирования // Таврический научный обозреватель. 2016. № 12-2(17). С. 141-146. EDN YFXCCN.

9. Гонцова А. В. Опыт разработки транслятора с языка Ассемблер RISC-V в машинный код // Обработка информации и математическое моделирование: материалы Всероссийской научно-технической конференции, Новосибирск, 24–25 апреля 2024 года. Новосибирск: Сибирский государственный университет телекоммуникаций и информатики, 2024. С. 85-88. DOI 10.55648/OIMM-2024-1-85. EDN DUZEDV.

10. Наркевич А. С. Структура байт-кода виртуальной машины Java // Информационные технологии: материалы 85-й научно-технической конференции профессорско-преподавательского состава, научных сотрудников и аспирантов (с международным участием), Минск, 01–13 февраля 2021 года. Минск: Белорусский государственный технологический университет, 2021. С. 80-82. EDN VLEPYZ.

11. Альфред В. Ахо, Моника С. Лам, Рави Сети, Джеффри. Компиляторы: принципы, технологии и инструментарий. 2-е изд. М.: Диалектика-Вильямс, 2020. 1184 c.

12. Намаконов Е. С., Подкопаев А. В. Компиляция модели памяти OCaml в Power // Труды Института системного программирования РАН. 2019. Т. 31, № 5. С. 63-78. DOI 10.15514/ISPRAS-2019-31(5)-4. EDN GPHUIK.

13. Джереми Сик. Основы компиляции: инкрементный подход. СПб.: Питер, 2024. 256 с.

14. Компиляторы: принципы, технологии и инструментарий / Ахо Альфред В., Лам Миника С., Сети Рави, Ульман Джеффри Д. М.: Диалектика-Вильямс, 2018. 1184 с.

15. Сайбель Питер. Практическое использование Common Lisp. М.: ДМК Пресс, 2017. - 488 с.

16. Грэй Пол. ANSI Common LISP. М.: Символ-Плюс, 2020. 448 с.

17. Чаплыгин А.А. Моделирование интерпретатора функционального языка программирования с возможностями метапрограммирования // Известия Юго-Западного государственного университета. Серия: Управление, вычислительная техника, информатика. Медицинское приборостроение. 2024. Т. 14, № 2. С. 181-193. https://doi.org/10.21869/2223-1536-2024-14-2-181-193

18. Владимиров К. И. Оптимизирующие компиляторы. Структура и алгоритмы. М.: АСТ, 2024. 272с.

19. Лопес Бруно Кардос, Аулер Рафаэль. LLVM: инфраструктура для разработки компиляторов. М.: ДМК Пресс, 2015. 342 с.