Modeling and implementation of Common LISP functional language compiler

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.

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. Felleisen M., Findler R.B., Flatt M., Krishnamurthi S., Barzilay E., McCarthy J., Tobin-Hochstadt S. The Racket Manifesto (PDF). Proceedings of the First Summit on Advances in Programming Languages: 2015. 113–128.

3. Abelson H., Sussman D. Structure and interpretation of computer programs. KDU; 2022. 608 p. (In Russ.)

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. 3rd ed. Shriram Krishnamurthi, 2022. 376 p.

6. Ershov A. P., Pokrovsky S. B. Evolution of programming languages. Problemy informatiki = Problems of informatics. 2017; (2): 70-79. (In Russ.). EDN ZOLFPJ.

7. Dushkin R.V. Functional programming in Haskell. Moscow: DMK Press; 2016. 608 p. (In Russ.)

8. Romanov S. S. Key concepts and features of object-oriented programming. Tavricheskii nauchnyi obozrevatel' = Tavricheskiy scientific observer. 2016; (12-2): 141-146. (In Russ.). EDN YFXCCN.

9. Gontsova A. V. Experience in Developing a Translator from RISC-V Assembly Language to Machine Code. In: Obrabotka informatsii i matematicheskoe modelirovanie : materialy Vserossiiskoi nauchno-tekhnicheskoi konferentsii = Information Processing and Mathematical Modeling. Proceedings of the All-Russian Scientific and Technical Conference. 2024. Novosibirsk: Siberian State University of Telecommunications and Informatics; 2024. P. 85–88. (In Russ.). DOI 10.55648/OIMM-2024-1-85. EDN DUZEDV.

10. Narkevich A. S. The structure of the bytecode of the Java virtual machine. In: Informatsionnye tekhnologii: materialy 85-i nauchno-tekhnicheskoi konferentsii professorsko-prepodavatel'skogo sostava, nauchnykh sotrudnikov i aspirantov (s mezhdunarodnym uchastiem) = Information technologies. Materials of the 85th scientific and technical conference of faculty, researchers and graduate students (with international participation. Minsk: Belarusian State Technological University; 2021. P. 80-82. (In Russ.). EDN VLEPYZ.

11. Alfred V. Aho, Monica S. Lam, Ravi Sethi, Jeffrey. Compilers:Principles, Technologies and Tools. 2nd ed. Moscow: Dialectics-Williams; 2020. 1184 p. (In Russ.)

12. Namakonov E. S., A. V. Podkopaev Compilation of the OCaml memory model to Power. Trudy Instituta sistemnogo programmirovaniya RAN = Proceedings of the Institute for System Programming of the Russian Academy of Sciences. 2019; 31(5): 63-78. (In Russ.) DOI 10.15514/ISPRAS-2019-31(5)-4. EDN GPHUIK.

13. Jeremy Sick. Compilation Basics: An Incremental Approach. St.Peterburg: Peter; 2024. 256 p. (In Russ.)

14. Alfred V. Aho, Monica S. Lam, Ravi Sethi, Jeffrey D. Ullman. Networks. Compilers: principles, technologies and tools. Moscow: Dialectics-Williams; 2018. 1184 p. (In Russ.)

15. Seibel Peter. Practical use of Common Lisp. Moscow: DMK Press; 2017. 488 p. (In Russ.)

16. Paul Graham. ANSI Common LISP. Moscow: Symvol-Plus; 2020. 448 p. (In Russ.)

17. Chaplygin A.A. Modeling of a functional programming language interpreter with metaprogramming capabilities. Izvestiya Yugo-Zapadnogo gosudarstvennogo universiteta. Seriya: Upravlenie, vychislitel'naya tekhnika, informatika. Meditsinskoe priborostroenie = Proceedings of the Southwest State University. Series: Control, Computing Engineering, Information Science. Medical Instruments Engineering. 2024;14(2):181-193. (In Russ.). https://doi.org/10.21869/2223-1536-2024-14-2-181-193

18. Vladimirov K. I. Optimizing compilers. Structure and algorithms. Moscow: AST; 2024. 272 p. (In Russ.)

19. Lopez Bruno Cardos, Auler Rafael. LLVM: An Infrastructure for Compiler Development. Moscow: DMK Press; 2015. 342 p. (In Russ.)