Исследование эффективности специализации интерпретаторов на объектно-ориентированном языке Java методами частичных вычислений с BT-объектами

Исследование эффективности специализации интерпретаторов на объектно-ориентированном языке Java методами частичных вычислений с BT-объектами

Автор: Адамович Игорь Алексеевич, Климов Юрий Андреевич

Журнал: Программные системы: теория и приложения @programmnye-sistemy

Рубрика: Программное и аппаратное обеспечение распределенных и суперкомпьютерных систем

Статья в выпуске: 4 (55) т.13, 2022 года.

Бесплатный доступ

Барьеры на пути специализации реальных программ, написанных в объектно-ориентированной парадигме, часто могут быть преодолены при помощи современных методов метавычислений. Один из барьеров - необходимость разрешения полиморфизма на этапе анализа программы, до ее исполнения. Эта проблема успешно решается для ряда случаев в специализаторе JaSpe, что показано в данной статье. Работа посвящена компиляции программ с использованием метода специализации, без использования компилятора. Мы применили специализатор JaSpe, основанный на методе частичных вычислений, к двум интерпретаторам языка арифметических выражений, написанным на Java. Интерпретаторы были реализованы методом рекурсивного спуска и с использованием шаблона «посетитель». В результате успешной специализации данных интерпретаторов по программе вычисления квадратного корня на языке арифметических выражений были получены скомпилированные версии программы на языке Java. При этом скорость полученных версий программы по сравнению с исходной увеличилась в 12-22 раза.

Еще

Интерпретаторы, компиляторы, частичные вычисления, специализация, метавычисления

Короткий адрес: https://sciup.org/143179414

IDR: 143179414   |   DOI: 10.25209/2079-3316-2022-13-4-111-137

Список литературы Исследование эффективности специализации интерпретаторов на объектно-ориентированном языке Java методами частичных вычислений с BT-объектами

  • Jones N. D., Gomard C. K., Sestoft P. Partial Evaluation and Automatic Program Generation, Prentice-Hall International Series in Computer Science, 1st ed..– Prentice-Hall.– 1993.– ISBN 978-0130202499%.– 415 pp. hUtRtpLs://www.itu.dk/people/sestoft/pebook/jonesgomardsestoft-a4.pdf
  • Marlet R. Program Specialization.– Wiley–ISTE.– 2012.– ISBN 9781848213999.– 544 pp. https://doi.org/10.1002/9781118576984
  • Turchin V. F. The concept of a supercompiler // ACM Transactions on Programming Languages and Systems.– 1986.– Vol. 8.– No. 3.– pp. 292–325. https://doi.org/10.1145/5956.5957
  • Turchin V. F. Supercompilation: Techniques and results // Perspectives of System Informatics, Second International Andrei Ershov Memorial Conference (Akademgorodok, Novosibirsk, Russia, June 25–28, 1996), Lecture Notes in Computer Science.– vol. 1181, eds. Bjørner D., Broy M., Pottosin I. V., Berlin–Heidelberg: Springer.– ISBN 978-3-540-49637-3.– pp. 227–248. https://doi.org/10.1007/3-540-62064-8_20
  • Климов Анд. В. Введение в метавычисления и суперкомпиляцию // Будущее прикладной математики: Лекции для молодых исследователей. От идей к технологиям, М.: КомКнига.– 2008.– ISBN 978-5-484-01028-8.– с. 343–368. hUtRtpLs://pat.keldysh.ru/~anklimov/papers/2008-Klimov–Introduction_to_Supercompilation.pdf
  • Romanenko S. A. Arity raiser and its use in program specialization // Proceedings of the 3rd European Symposium on Programming, Lecture Notes in Computer Science.– vol. 482, Berlin–Heidelberg: Springer.– 1990.– ISBN 978-3-540-47045-8.– pp. 341–360. https://doi.org/10.1007/3-540-52592-0_73
  • Futamura Y. Partial evaluation of computation process — an approach to a compiler-compiler // Higher-Order and Symbolic Computation.– 1999.– Vol. 12.– No. 4.– pp. 381–391. https://doi.org/10.1023/A:1010095604496
  • Futamura Y. EL1 Partial Evaluator, Progress Report.– Cambridge, Massachusetts, USA: Center for Research in Computing Technology, Harvard University.– 1973.– 12 pp. hUtRtpLs://fi.ftmr.info/PE-Museum/EL1.PDF
  • Турчин И.Ф. и др. Базисный РЕФАЛ и его реализация на вычисли-тельных машинах, Фонд алгоритмов и программ для ЭВМ (в отрасли «Строительство»).– Т. 40.– М.: ЦНИПИАСС.– 1977.– 263 с. hUtRtpLs://pat.keldysh.ru/~roman/doc/1977___Bazisnyj_Refal_i_ego_realizaciya_na_vychislitel’nyx_mashinax__CNIPIASS.pdf
  • Адамович И. А., Климов Анд. В. Интерактивный специализатор подмножества языка Java, основанный на методе частичных вычислений // Труды Института системного программирования РАН.– 2018.– Т. 30.– №4.– с. 29–44 (In English). https://doi.org/10.15514/ISPRAS-2018-30(4)-2
  • Адамович И. А., Климов Ю.А. Специализатор JaSpe: алгоритм внутри-процедурного анализа времени связывания программ на подмножестве языка Java // Программные системы: теория и приложения.– 2020.– Т. 11.– №1(44).– с. 3–29. UhtRtpL://psta.psiras.ru/rehatdt/ppss:/ta/2d0o2i.0o_rg1/_130-.2592.p0d9f/2079-3316-2020-11-1-3-29
  • Адамович И. А. Специализатор JaSpe: BT-объекты и межпроцедурный аспект алгоритма анализа времен связывания // Программные системы: теория и приложения.– 2021.– Т. 12.–№4(51).– с. 3–33. hUtRtpL://psta.psiras.ru/rheattdp/sp:/st/ad2o0i2.o1r_g/41_03.2-3522.0p9d/f2079-3316-2021-12-4-3-32
  • Eclipse integrated develoment environment (IDE).– Eclipse Foundation. UhtRtpLs://www.eclipse.org
  • Nadeem A. Human-centered approach to static-analysis-driven developer tools // Communications of the ACM.– 2022.– Vol. 65.– No. 3.– pp. 38–45. https://doi.org/10.1145/3486597
  • Tiganov D., Do L. N.Q., Ali K. Designing UIs for static-analysis tools // Communications of the ACM.– 2022.– Vol. 65.– No. 2.– pp. 52–58. https://doi.org/10.1145/3486600
  • Климов Ю.А. Возможности специализатора CILPE и примеры его применения к программам на объектно-ориентированных языках // Препринты ИПМ им. М. В. Келдыша.– 2008.– 030.– 28 с. hUtRtpL://library.keldysh.ru/preprint.asp?id=2008-30
  • Климов Ю.А. Специализатор CILPE: частичные вычисления для объектно-ориентированных языков // Программные системы: теория и приложения.– 2010.– Т. 1.– №3(3).– с. 13–36. hUtRtpL://psta.psiras.ru/read/psta2010_3_13-36.pdf
  • Morris F. L. The next 700 formal language descriptions // LISP and Symbolic Computation.– November 1993.– Vol. 6.– No. 3–4.– pp. 249–257. https://doi.org/10.1007/BF01019460
  • Jones N. D., Sestoft P., Søndergaard H. Mix: A self-applicable partial evaluator for experiments in compiler generation // LISP and Symbolic Computation.– Febrary 1989.– Vol. 2.– No. 9.– pp. 9–50. https://doi.org/10.1007/BF01806312
  • Романенко С. А. Генератор компиляторов, порожденный самоприменением специализатора, может иметь ясную и естественную структуру // Препринты ИПМ им. М. В. Келдыша.– 1987.– 026.– 39 с. hUtRtpLs://keldysh.ru/papers/1987/prep1987_26.pdf
  • Romanenko S. A. Compiler generator produced by a self-applicable specializer can have a surprisingly natural and understandable structure // Partial Evaluation and Mixed Computation, North–Holland: Elsevier Sxience Publishers B.V..– 1988.– с. 445–463. hUtRtpLs://pat.keldysh.ru/~roman/doc/1988-Romanenko–A_Compiler_Generator_Produced_by_a_Self-Applicable_Specializer.pdf
  • Consel С., Danvy O. Static and dynamic semantics processing // Proceedings of the 18th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (January 21–23, 1991, Orlando, Florida, USA), New York: ACM.– 1991.– ISBN 978-0-89791-419-2.– pp. 14–24. https://doi.org/10.1145/99583.99588
  • Consel C., Khoo S. C. Semantics-directed generation of a prolog compile // Science of Computer Programming.– 1993.– Vol. 21.– No. 3.– pp. 263–291. https://doi.org/10.1016/0167-6423(93)90011-D
  • W¨urthinger T., Wimmer C., W¨oß A., Stadler L., Duboscq G., Humer C., Richards G., Simon D., Wolczko M. One VM to rule them all // Proceedings of the 2013 ACM International Symposium on New Ideas, New Paradigms, and Reflections on Programming & Software (October29–31, 2013, Indianapolis, Indiana, USA), New York: ACM.– 2013.– ISBN 978-1-4503-2472-4.– с. 187–204. https://doi.org/10.1145/2509578.2509581
  • W¨urthinger T., Wimmer C., Humer C., W¨oß A., Stadler L., Seaton C., Duboscq G., Simon D., Grimmer M. Practical partial evaluation for high-performance dynamic language runtimes // ACM SIGPLAN Notices.– June 2017.– Т. 52.– №6.– с. 662–676. https://doi.org/10.1145/3140587.3062381
  • Latifi F., Leopoldseder D., Wimmer C., M¨ossenb¨ck H. CompGen: generation of fast JIT compilers in a multi-language VM // Proceedings of the 17th ACM SIGPLAN International Symposium on Dynamic Languages, DLS 2021 (19 October 2021, Chicago, IL, USA).– 2021.– ISBN 978-1-4503-9105-4.– с. 35–47. https://doi.org/10.1145/3486602.3486930
  • Bezanson J., Edelman A., Karpinski S., Shah V. B. Julia: A Fresh Approach toNumerical Computing // SIAM Review.– 2017.– Т. 59.– №1.– с. 65–98. https://doi.org/10.1137/141000671
  • Weisstein E. W. Newton’s Iteration.– MathWorld— A Wolfram Web Resource. UhtRtpLs://mathworld.wolfram.com/NewtonsIteration.html
  • Бахвалов Н. С., Кобельков Г. М., Жидков Н. П. Численные методы.– М.: Лаборатория знаний.– 2020.– ISBN 978-5-00101-836-0.– 636 с.
  • Aho A. V., Lam M. S., Sethi R., Ullman J. D. Compilers: Principles, Techniques, and Tools, 2nd ed..– AddisonWesley.– 2006.– ISBN 978-0321486813.– 1040 с.
  • Gamma E., Helm R., Johnson R., Vlissides J. Design Patterns: Elements of Reusable Object-Oriented Software, 1st ed..– Addison Wesley.– 1994.– ISBN 978-0201633610.– 331 с.
  • Java Microbenchmark Harness.– Oracle Corporation. hUtRtpLs://github.com/openjdk/jmh
Еще
Статья научная
QR-код для установки приложения SciUp Наведите камеру и скачайте бесплатное приложение SciUp