Чаплыгин Александр Александрович - кандидат технических наук, доцент, доцент кафедры программной инженерии.
ул. 50 лет Октября, д. 94, Курск 305040
Aleksandr А. Chaplygin - Cand. of Sci. (Engineering), Associate Professor, Associate Professor of the Software Engineering Department, Southwest State University.
50 Let Oktyabrya str. 94, Kursk 305040
Цель исследований заключается в создании модели компилятора функционального языка Common Lisp, реализации этой модели и тестировании модели компилятора с помощью целевой виртуальной машины, чтобы увеличить скорость выполнения программ.
Методы. С помощью денотационной семантики была построена формальная модель компилятора функционального языка Common Lisp. Компиляция происходит в несколько этапов. На первом этапе исходный язык преобразуется в промежуточный lambda-язык, в котором все макросы раскрываются, встроенные формы преобразуются в аналогичные выражения, а имена переменных заменяются на локальные, глобальные и глубокие ссылки. На втором этапе выражение на промежуточном языке преобразуется из древовидной структуры в линейный список из примитивных инструкций целевой виртуальной машины.
Результаты. Полученные в результате компиляции примитивные инструкции кодируются с помощью специального ассемблера в числовой код для выполнения на целевой виртуальной машине. Также в результате компиляции получаются список констант и размер памяти необходимый для работы скомпилированной программы. Целевая виртуальная машина состоит из отделов памяти для кодированной программы, констант, глобальных переменных, стека, списка кадров активации, регистров (аккумулятор, указатель стека, указатель команд, текущий кадр активации). Кадры активации представляют собой объекты-массивы, которые хранят указатель на предыдущий кадр, номер уровня глубины вызовов и локальные аргументы. Сборка мусора происходит с помощью метода пометки и очистки.
Заключение. В результате работы была построена и реализована модель компилятора функционального языка Common Lisp. По сравнению с интерпретатором скорость работы программы возросла в среднем в 20 раз. Дальнейшее увеличение скорости можно достичь с помощью различных оптимизаций компилятора на разных стадиях. Из простых оптимизаций можно отметить: оптимизацию арифметических выражений, устранение лишних команд, упрощение выражений.
Purpose of research is to create a compiler model for the functional language Common Lisp, implement this model, and test the compiler model using a target virtual machine to increase the execution speed of programs.
Methods. A formal compiler model of the functional language Common Lisp was built using denotational semantics. Compilation takes place in several stages. At the first stage, the source language is transformed into an intermediate lambda language in which all macros are expanded, embedded forms are transformed into similar expressions, and variable names are replaced with local, global, and deep references. At the second stage, the expression in the intermediate language is transformed from a tree structure into a linear list of primitive instructions of the target virtual machine.
Results. The resulting primitive instructions are encoded using a special assembler into numeric code for execution on the target virtual machine. The compilation also results in a list of constants and the amount of memory required for the compiled program to run. The target virtual machine consists of memory sections for the encoded program, constants, global variables, stack, list of activation frames, registers (accumulator, stack pointer, instruction pointer, current activation frame). Activation frames are array objects that store a pointer to the previous frame, the call depth level number, and local arguments. Garbage collection takes place using the tagging and cleaning method.
Conclusion. As a result, a Common Lisp functional language compiler model was built and implemented. Compared to the interpreter, the speed of the program has increased by an average of 20 times. Further speed increases can be achieved by using various compiler optimizations at different stages. Of the simple optimizations, it can be noted: optimization of arithmetic expressions, elimination of unnecessary commands, simplification of expressions.
The authors declare that there are no conflicts of interest present.