E.O. Deryugina − Ph.D. (Eng.), Associate Professor, 

«Information Systems and Networks» Department, Kaluga Branch of Bauman MSTU

E-mail: syvorova_eo@mail.ru

N.A. Borsuk − Ph.D. (Eng.), Associate Professor, 

«Information Systems and Networks» Department, Kaluga Branch of Bauman MSTU

E-mail: borsuk.65@yandex.ru

A.V. Kuzminsky − Graduate Student, 

«Information Systems and Networks» Department, Kaluga Branch of Bauman MSTU

E-mail: alexqzminsky@gmail.com

stract

Computational trees are considered one of the intermediate forms of representation of program code during the procedure of translating it into executable form. The computational tree is derived from the abstract syntax tree and has a more formalized structure, which, on the one hand, saves memory of the machine on which code transformations are performed, and on the other hand, allows you to enter additional information about its elements (for example, node and data typing). As a rule, interpreters do not stop the translation at this stage, but translate the calculation tree into the «linear» format of lower-level commands.this, although it reduces the final memory consumption even more and allows you to implement a virtual bus in the «switch» mode for fast processing of commands, in itself requires both time and intermediate memory expenditures-this is a particularly time-consuming task when implementing functional programming languages.

It is assumed that saving the form of the calculation tree as the final format for representing the program code for its execution by the interpreter will allow saving time for its further processing, without significantly increasing memory consumption.

Reduction of a computational tree (in the terminology of lambda calculus, which is a mathematical apparatus for such transformations, called a redex) is the process of convolution by sequentially traversing it to some finite form. A redex is considered calculated if all its elements are defined by the language rules as constructors.

The classic «switch» that underlies the interpreter's virtual machine − its executing core-is not intended for reducing computational trees. Strictly speaking, such interpreters perform only partial reduction by collapsing the subtrees that define constant expressions. In order to make the computational tree the final format for representing program code, the «switch» should be replaced with a fullfledged «reducer», equipped, in addition to the main mechanism for traversing and collapsing trees, with additional algorithms and data structures, such as a cache for storing the results of performing functions to prevent repeated calculations, a garbage collector module − and its corresponding memory model, etc.

Replacing a virtual machine of the «switching» type with a reducer as part of an interpreter in order to perform calculations based on computational trees-in other words, their construction from an intermediate to a final form of program representation − finds practical application, and also opens a wide field for further research in this area.

1. Mak R. Writing Compilers and Interpreters: A Software Engineering Approach. New Delhi: Wiley India. 2009.
2. Muchnick S.S. Advanced compiler design and implementation. San Francisco, Calif.: Morgan Kaufmann Publishers. 2017.
3. Fild A., Kharrison P. Funktsional′noe programmirovanie. Per. s angl. M.: Mir. 1993. 637 s. (in Russian).
4. Akho A.V., Lam M.S., Seti R., Ul′man D.D. Kompilyatory: printsipy, tekhnologii i instrumentarii. Izd. 2-е. Per. s angl. M.: Izdatel′skii dom «Vil′yams». 2018. 1184 s. (in Russian).
5. Pratt T. Yazyki programmirovaniya: razrabotka i realizatsiya. Per. s angl. M.: Mir. 2009. 327 s. (in Russian).
6. Khanter R. Proektirovanie i konstruirovanie kompilatorov. Per. s angl. M.: Finansy i statistika. 2014. 232 s. (in Russian).
7. Khanter R. Osnovnye kontseptsii kompilyatorov. Per. s angl. M.: Izdatel′skii dom «Vil′yams». 2002. 256 s. (in Russian).
8. Cooper K.D., Torczon L. Engineering a Compiler, Second Edition. San Francisco, Calif.: Morgan Kaufmann Publishers. 2012.
9. Maksimov A.V. Optimal′noe proektirovanie assemblernykh program matematicheskikh algoritmov: teoriya, inzhenernye metody. SPb: Izdatel′stvo «Lan′». 2016. 192 s. (in Russian).
10. Deryugina E.O., Borsuk N.A., Kozeeva O.O. Sravnitel′nyi analiz yazykov programmirovaniya Python и PHP. Vestnik obrazovatel′nogo konsortsiuma «Srednerusskii universitet». Informatsionnye tekhnologii. 2017. № 1(9). S. 36−38 (in Russian).
11. Deryugina E.O., Kuz′minskii A.V. Integrirovanie s dobavleniem v С++ − pochemu eto plokho i kak reshaet dannyyu problem. Sb. materialov Mezhdunar. nauchno-praktich. konf. «Razvitie nauki i obrazovaniya v sovremennom mire». V 6-ti chastyakh. ООО «ARKonsalt». 2015. S. 159−160 (in Russian).