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

Специализация - это оптимизация программ на основе использования наперёд заданной информации о значении части переменных. Методы специализации программ развиваются с 1970-х годов (смешанные вычисления, частичные вычисления, суперкомпиляция). Однако удивительно, что после трёх десятилетий разработанные специализаторы до сих пор не достигли того уровня, когда они станут пригодны для широкого практического применения. Возникает вопрос: в чём же причина? Наша гипотеза состоит в том, что задача специализации требуют гораздо большего участия человека в управлении процессом специализации, анализе результатов, проведении компьютерных экспериментов, чем в случае обычной оптимизации программы в компиляторах. Требуется погружение специализаторов в привычные для программистов интегрированные среды разработки, включая создание соответствующих диалоговых средств. В данной статье описываются результаты разработки и реализации методов интерактивной специализации на основе частичных вычислений для подмножества языка Java. Реализация выполнена в рамках популярной среды разработки (IDE) Eclipse. Разрабатываются сценарии человеко-машинного диалога с подсистемой специализации, интерактивные средства для составления задания на специализацию и управление процессом специализации. Приводится пример успешного применения разработанного специализатора. Остаточная программа работает в несколько раз быстрее чем исходная.

анализ программ, преобразование программ, интерактивная специализация программ, частичные вычисления, объектно-ориентированный язык, среда разработки программ

1. Jones N.D., Sestoft P. and Søndergaard H. An experiment in partial evaluation: the generation of a compiler generator. Rewriting Techniques and Applications, Lecture Notes in Computer Science, J.-P. Jouannaud, (Ed.), vol. 202. Springer-Verlag, 1985, pp. 124-140

2. Jones N.D., Gomard C.K., and Sestoft P. Partial Evaluation and Automatic Program Generation. Prentice-Hall, 1993. Доступно по ссылке: http://www.itu.dk/~sestoft/pebook/pebook.html, дата обращения: 20.06.2018

3. Futamura Y. Partial evaluation of computation process - an approach to a compiler-compiler. Systems, Computers, Controls, vol. 2, no. 5, 1971, pp. 45-50

4. Futamura Y. Partial evaluation of computation process - an approach to a compiler-compiler. Higher-Order and Symbolic Computation, vol. 12, no. 4, Dec 1999, pp. 381-391. Updated and revised version of [3]. Доступно по ссылке: http://doi.org/10.1023/A:1010095604496, дата обращения: 20.06.2018

5. Futamura Y. EL1 Partial Evaluator (Progress Report). Center for Research in Computing Technology, Harvard University, Tech. Rep., 1973. Доступно по ссылке: http://fi.ftmr.info/PE-Museum/EL1.PDF, дата обращения: 20.06.2018

6. Turchin V.F. The concept of a supercompiler. ACM Transactions on Programming Languages and Systems, vol. 8, no. 3, 1986, pp. 292-325

7. Turchin V.F. Supercompilation: techniques and results. Perspectives of System Informatics, Second International Andrei Ershov Memorial Conference, Akademgorodok, Novosibirsk, Russia, June 25-28, 1996. Proceedings, Lecture Notes in Computer Science, D. Bjørner, M. Broy, and I.V. Pottosin, (Eds.), vol. 1181. Springer, 1996, pp. 227-248

8. Eclipse Foundation. Eclipse Integrated Development Environment (IDE). Доступно по ссылке: https://www.eclipse.org, дата обращения: 20.06.2018

9. Eclipse Foundation. Eclipse Java development tools (JDT). Доступно по ссылке: https://www.eclipse.org/jdt, дата обращения: 20.06.2018

10. Klimov Yu.A. An approach to polyvariant binding time analysis for a stack-based language. First International Workshop on Metacomputation in Russia, Proceedings. Pereslavl-Zalessky, Russia, July 2-5, 2008. Pereslavl-Zalessky: Ailamazyan University of Pereslavl, 2008, pp. 78-84. Доступно по ссылке: http://meta2008.pereslavl.ru/accepted-papers/paper-info-6.html, дата обращения: 20.06.2018

11. Климов Ю.А. Особенности применения метода частичных вычислений к специализации программ на объектно-ориентированных языках. Препринты ИПМ им. М.В. Келдыша, № 12, 2008. Доступно по ссылке: http://library.keldysh.ru/preprint.asp?id=2008-12, дата обращения: 20.06.2018

12. Климов Ю.А. Возможности специализатора CILPE и примеры его применения к программам на объектно-ориентированных языках. Препринты ИПМ им. М.В. Келдыша, № 30, 2008. Доступно по ссылке: http://library.keldysh.ru/preprint.asp?id=2008-30, дата обращения: 20.06.2018

13. Климов Ю.А. SOOL: объектно-ориентированный стековый язык для формального описания и реализации методов специализации программ. Препринты ИПМ им. М.В. Келдыша, № 44, 2008. Доступно по ссылке: http://library.keldysh.ru/preprint.asp?id=2008-44, дата обращения: 20.06.2018

14. Климов Ю.А. Специализатор CILPE: анализ времен связывания. Препринты ИПМ им. М.В. Келдыша, № 7, 2009. Доступно по ссылке: http://library.keldysh.ru/preprint.asp?id=2009-07, дата обращения: 20.06.2018

15. Климов Ю.А. Специализатор CILPE: генерация остаточной программы. Препринты ИПМ им. М.В. Келдыша, № 8, 2009. Доступно по ссылке: http://library.keldysh.ru/preprint.asp?id=2009-08, дата обращения: 20.06.2018

16. Климов Ю.А. Специализатор CILPE: доказательство корректности. Препринты ИПМ им. М.В. Келдыша, № 33, 2009. Доступно по ссылке: http://library.keldysh.ru/preprint.asp?id=2009-33, дата обращения: 20.06.2018

17. Климов Ю.А. Специализация программ на объектно-ориентированных языках методом частичных вычислений. Дис. к.ф.-м.н., Институт прикладной математики им. М.В. Келдыша РАН, Москва, Россия, ноябрь 2009, 183 стр. Доступно по ссылке: http://pat.keldysh.ru/~yura/publications/2009.10-Klimov-Disser-Specializacia_programm_na_ob'ektno-orientirovannyx_yazykah.pdf, дата обращения: 20.06.2018

18. Климов Ю.А. Специализатор CILPE: частичные вычисления для объектно-ориентированных языков. Программные системы теория и приложения, № 3(3), 2010, стр. 13-36 Доступно по ссылке: http://psta.psiras.ru/read/psta2010_3_13-36.pdf, дата обращения: 20.06.2018

19. Bulyonkov M.A. and Kochetov D.V. Practical aspects of specialization of Algol-like programs. Dagstuhl Seminar on Partial Evaluation, Lecture Notes in Computer Science, O. Danvy, R. Gluck, and P. Thiemann, (Eds.), vol. 1110. Springer, 1996, pp. 17-32

20. Ershov A.P. and Itkin V.E. Correctness of mixed computation in Algol-like programs. MFCS, Lecture Notes in Computer Science, J. Gruska, (Ed.), vol. 53. Springer, 1977, pp. 59-77

21. Andersen L.O. Program analysis and specialization for the C programming language. Ph.D. dissertation, DIKU, University of Copenhagen, May 1994, (DIKU report 94/19)

22. Andersen L.O. Binding-time analysis and the taming of C pointers. Proceedings of the 1993 ACM SIGPLAN symposium on Partial Evaluation and Semantics-Based Program Manipulation (PEPM '93). ACM, 1993, pp. 47-58. Доступно по ссылке: http://dx.doi.org/10.1145/154630.154636, дата обращения: 20.06.2018

23. Consel C., Lawall J.L., and Meur A.-F.L. A tour of Tempo: a program specializer for the C language. Sci. Comput. Program., vol. 52, no. 1-3, 2004, pp. 341-370

24. Meur A.L., Lawall J.L. and Consel C. Towards bridging the gap between programming languages and partial evaluation. Proceedings of the 2002 ACM SIGPLAN Workshop on Partial Evaluation and Semantics-Based Program Manipulation (PEPM ’02), Portland, Oregon, USA, January 14-15, 2002, P. Thiemann, (Ed.). ACM, 2002, pp. 9-18. Доступно по ссылке: http://doi.acm.org/10.1145/503032.503033, дата обращения: 20.06.2018

25. Schultz U.P., Lawall J.L. and Consel C. Automatic program specialization for Java. ACM Trans. Program. Lang. Syst., vol. 25, no. 4, 2003, pp. 452-499

26. Muller G., Moura B., Bellard F. and Consel C. Harissa: A flexible and efficient Java environment mixing bytecode and compiled code. Proceedings of the Third USENIX Conference on Object-Oriented Technologies (COOTS), June 16-20, 1997, Portland, Oregon, USA, S. Vinoski, (Ed.). USENIX, 1997, pp. 1-20. Доступно по ссылке: http://www.usenix.org/publications/library/proceedings/coots97/muller.html, дата обращения: 20.06.2018

27. Shali A. and Cook W.R. Hybrid partial evaluation. SIGPLAN Not., vol. 46, no. 10, Oct. 2011, pp. 375-390. Доступно по ссылке: http://doi.acm.org/10.1145/2076021.2048098, дата обращения: 20.06.2018

28. Ji R. and Bubel R. PE-KeY: A partial evaluator for Java programs. Proceedings of the 9th International Conference on Integrated Formal Methods, IFM’12. Berlin, Heidelberg: Springer-Verlag, 2012, pp. 283- 295. Доступно по ссылке: http://dx.doi.org/10.1007/978-3-642-30729-4_20, дата обращения: 20.06.2018

29. Ahrendt W., Beckert B., Bubel R., Hahnle R., Schmitt P.H. and Ulbrich M., (Eds.). Deductive Software Verification - The KeY Book - From Theory to Practice. Lecture Notes in Computer Science. Springer, 2016, vol. 10001. Доступно по ссылке: https://doi.org/10.1007/978-3-319-49812-6, дата обращения: 20.06.2018

30. Würthinger T., Wimmer C., Wöß A., Stadler L., Duboscq G., Humer C., Richards G., Simon D., and 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, Onward! 2013. New York, NY, USA: ACM, 2013, pp. 187-204. Доступно по ссылке: http://doi.acm.org/10.1145/2509578.2509581, дата обращения: 20.06.2018

31. Würthinger T., Wimmer C., Humer C., Wöß A., Stadler L., Seaton C., Duboscq G., Simon D., and Grimmer M. Practical partial evaluation for high-performance dynamic language runtimes. SIGPLAN Not., vol. 52, no. 6, Jun. 2017, pp. 662-676. Доступно по ссылке: http://doi.acm.org/10.1145/3140587.3062381, дата обращения: 20.06.2018