An Interactive Specializer Based on Partial Evaluation for a Java Subset

Specialization is a program optimization approach that implies the use of a priori information about values of some variables. Specialization methods are being developed since 1970s (mixed computations, partial evaluation, supercompilation). However, it is surprising, that even after three decades, these promising methods have not been put into the wide programming practice. One may wonder: What is the reason? Our hypothesis is that the task of specialization requires much greater human involvement into the specialization process, the analysis of its results and conducting computer experiments than in the case of common program optimization in compilers. Hence, specializers should be embedded into integrated development environments (IDE) familiar to programmers and appropriate interactive tools should be developed. In this paper we provide a work-in-progress report on results of development of an interactive specializer based on partial evaluation for a subset of the Java programming language. The specializer has been implemented within the popular Eclipse IDE. Scenarios of the human-machine dialogue with the specializer and interactive tools to compose the specialization task and to control the process of specialization are under development. An example of application of the current version of the specializer is shown. The residual program runs several times faster than the source one.

program analysis, program transformation, interactive program specialization, partial evaluation, object-oriented language, integrated development environment

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, 415 p. Available at: http://www.itu.dk/~sestoft/pebook/pebook.html, accessed 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]. Available at: http://doi.org/10.1023/A:1010095604496, accessed 20.06.2018

5. Futamura Y. EL1 Partial Evaluator (Progress Report). Center for Research in Computing Technology, Harvard University, Tech. Rep., 1973. Available at: http://fi.ftmr.info/PE-Museum/EL1.PDF, accessed 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). Available at: https://www.eclipse.org, accessed 20.06.2018

9. Eclipse Foundation. Eclipse Java development tools (JDT). Available at: https://www.eclipse.org/jdt, accessed 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. Available at: http://meta2008.pereslavl.ru/accepted-papers/paper-info-6.html, accessed 20.06.2018

11. Klimov Yu.A. [Program specialization for object-oriented languages by partial evaluation: approaches and problems]. Preprinty` IPM im. M.V. Keldy`sha [Keldysh Institute Preprints], no. 12, 2008 (in Russian). Available at: http://library.keldysh.ru/preprint.asp?id=2008-12, accessed 20.06.2018

12. Klimov Yu.A. [Specializer CILPE: examples of object-oriented program specialization]. Preprinty` IPM im. M.V. Keldy`sha [Keldysh Institute Preprints], no. 30, 2008 (in Russian). Available at: http://library.keldysh.ru/preprint.asp?id=2008-30, accessed 20.06.2018

13. Klimov Yu.A. [SOOL: an object-oriented stacked-based language for specification and implementation of program specialization techniques]. Preprinty` IPM im. M.V. Keldy`sha [Keldysh Institute Preprints], no. 44, 2008 (in Russian). Available at: http://library.keldysh.ru/preprint.asp?id=2008-44, accessed 20.06.2018

14. Klimov Yu.A. [Specializer CILPE: binding time analysis]. Preprinty` IPM im. M.V. Keldy`sha [Keldysh Institute Preprints], no. 7, 2009 (in Russian). Available at: http://library.keldysh.ru/preprint.asp?id=2009-07, accessed 20.06.2018

15. Klimov Yu.A. [Specializer CILPE: residual program generation]. Preprinty` IPM im. M.V. Keldy`sha [Keldysh Institute Preprints], no. 8, 2009 (in Russian). Available at: http://library.keldysh.ru/preprint.asp?id=2009-08, accessed 20.06.2018

16. Klimov Yu.A. [Specializer CILPE: correctness proof]. Preprinty` IPM im. M.V. Keldy`sha [Keldysh Institute Preprints], no. 33, 2009, (in Russian). Available at: http://library.keldysh.ru/preprint.asp?id=2009-33, accssed 20.06.2018

17. Klimov Yu.A. [Specialization of programs in object-oriented languages by partial evaluation]. Ph.D. dissertation, Keldysh Institute of Applied Mathematics of RAS, Moscow, Russia, Nov 2009, 183 p. (in Russian). Available at: http://pat.keldysh.ru/~yura/publications/2009.10-Klimov-Disser-Specializacia_programm_na_ob'ektno-orientirovannyx_yazykah.pdf, accessed 20.06.2018

18. Klimov Yu.A. [Specializer CILPE: Partial evaluation for object-oriented languages]. Programmny`e sistemy`: teoriia i prilozheniia [Program Systems: Theory and Applications], no. 3(3), pp. 13–36, 2010 (in Russian). Available at: http://psta.psiras.ru/read/psta2010_3_13-36.pdf, accessed 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. Available at: http://dx.doi.org/10.1145/154630.154636, accessed: 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. Available at: http://doi.acm.org/10.1145/503032.503033, accessed 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. Available at:

27. http://www.usenix.org/publications/library/proceedings/coots97/muller.html, accessed 20.06.2018.

28. Shali A. and Cook W.R. Hybrid partial evaluation. SIGPLAN Not., vol. 46, no. 10, Oct. 2011, pp. 375–390. Available at: http://doi.acm.org/10.1145/2076021.2048098, accessed 20.06.2018.

29. 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. Available at: http://dx.doi.org/10.1007/978-3-642-30729-4_20, accessed 20.06.2018

30. 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. Available at: https://doi.org/10.1007/978-3-319-49812-6, accessed 20.06.2018

31. 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. Available at: http://doi.acm.org/10.1145/2509578.2509581, accessed 20.06.2018

32. 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. Available at: http://doi.acm.org/10.1145/3140587.3062381, accessed 20.06.2018.