A Method for Automatic Program Inversion Based on LR(0) Parsing

• Autorzy: Glück R. , Kawabe M.
• Języki publikacji: EN

Abstrakty

EN

We describe a method for automatic program inversion of first-order functional programs based on methods of LR(0) parsing. We formalize the transformation and illustrate it with several example programs. We approach one of the main problems of automatic program inversion-the elimination of nondeterminism-by viewing an inverse program as a context-free grammar. We apply LR-based parsing methods to turn a nondeterministic program into a deterministic program. This improves the efficiency of the inverse programs and greatly expands the application range of our earlier method for program inversion.

Słowa kluczowe

EN

program inversion; program transformation; LR parsing; functional programming

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2005
• Tom: Vol. 66, nr 4
• Strony: 367--395
• Opis fizyczny: Bibliogr. 29 poz., wykr.

Twórcy

autor

Glück R.

• DIKU, Dept. of Computer Science University of Copenhagen, DK-2100 Copenhagen, Denmark

autor

Kawabe M.

• Graduate School of Science and Engineering Waseda University Tokyo, 169-8555, Japan

Bibliografia

• [1] Abramov, S. M., Glück, R.: Principles of inverse computation and the universal resolving algorithm, The Essence of Computation: Complexity, Analysis, Transformation (T. Æ. Mogensen, D. Schmidt, I. H. Sudborough, Eds.), LNCS 2566, Springer-Verlag, 2002.
• [2] Abramov, S. M., Glück, R.: The universal resolving algorithm and its correctness: inverse computation in a functional language, Science of Computer Programming, 43(2-3), 2002, 193–229.
• [3] Aho, A. V., Johnson, S. C.: LR parsing, Computing Surveys, 6(2), 1974, 99–124.
• [4] Aho, A. V., Sethi, R., Ullman, J. D.: Compilers: Principles, Techniques and Tools, Addison-Wesley, 1986.
• [5] Bird, R., de Moor, O.: Algebra of Programming, Prentice Hall International Series in Computer Science, Prentice Hall, London, New York, Toronto, 1997.
• [6] Darlington, J.: An experimental program transformation and synthesis system, Artificial Intelligence, 16(1), 1981, 1–46.
• [7] Dijkstra, E. W.: Program inversion, Program Construction: International Summer School (F. L. Bauer, M. Broy, Eds.), LNCS 69, Springer-Verlag, 1978.
• [8] Eppstein, D.: A heuristic approach to program inversion, Int. Joint Conference on Artificial Intelligence (IJCAI-85),Morgan Kaufmann, Inc., 1985.
• [9] Floyd, R. W.: Nondeterministic algorithms, Journal of the ACM, 14(4), 1967, 636–644.
• [10] Glück, R., Kawabe, M.: A program inverter for a functional language with equality and constructors, Programming Languages and Systems. Proceedings (A. Ohori, Ed.), LNCS 2895, Springer-Verlag, 2003.
• [11] Glück, R., Kawabe, M.: Derivation of deterministic inverse programs based on LR parsing, Functional and Logic Programming. Proceedings (Y. Kameyama, P. J. Stuckey, Eds.), LNCS 2998, Springer-Verlag, 2004.
• [12] Glück, R., Kawabe, M.: Revisiting an automatic program inverter for Lisp, SIGPLAN Notices, 2005, To appear.
• [13] Glück, R., Kawada, Y., Hashimoto, T.: Transforming interpreters into inverse interpreters by partial evaluation, Proceedings of the ACM SIGPLAN Workshop on Partial Evaluation and Semantics-Based Program Manipulation, ACM Press, 2003.
• [14] Glück, R., Leuschel, M.: Abstraction-based partial deduction for solving inverse problems: a transformational approach to software verification, Perspectives of System Informatics. Proceedings (D. Bjørner, M. Broy, A. V. Zamulin, Eds.), LNCS 1755, Springer-Verlag, 2000.
• [15] Glück, R., Turchin, V. F.: Application of metasystem transition to function inversion and transformation, Proceedings of the Int. Symposium on Symbolic and Algebraic Computation (ISSAC’90), ACM Press, 1990.
• [16] Gries, D.: The Science of Programming, Chapter 21: Inverting Programs, Texts and Monographs in Computer Science, Springer-Verlag, 1981, 265–274.
• [17] Kawabe, M., Glück, R.: The program inverter LRinv and its structure, Practical Aspects of Declarative Languages. Proceedings (H. Manuel, D. Cabeza, Eds.), LNCS 3350, Springer-Verlag, 2005.
• [18] Khoshnevisan, H., Sephton, K. M.: InvX: an automatic function inverter, Rewriting Techniques and Applications. Proceedings (N. Dershowitz, Ed.), LNCS 355, Springer-Verlag, 1989.
• [19] Knuth, D. E.: On the translation of languages from left to right, Information and Control, 8(6), 1965, 607–639.
• [20] Korf, R. E.: Inversion of applicative programs, Int. Joint Conference on Artificial Intelligence (IJCAI-81), William Kaufmann, Inc., 1981.
• [21] McCarthy, J.: The inversion of functions defined by Turing machines, in: Automata Studies (C. E. Shannon, J. McCarthy, Eds.), Princeton University Press, 1956, 177–181.
• [22] Mu, S.-C., Bird, R.: Inverting functions as folds, Mathematics of Program Construction. Proceedings (E. A. Boiten, B. M¨oller, Eds.), LNCS 2386, Springer-Verlag, 2002.
• [23] Mu, S.-C., Bird, R.: Rebuilding a tree from its traversals: a case study of program inversion, Programming Languages and Systems. Proceedings (A. Ohori, Ed.), LNCS 2895, Springer-Verlag, 2003.
• [24] Nemytykh, A. P., Pinchuk, V. A.: Program transformation with metasystem transitions: experiments with a supercompiler, Perspectives of System Informatics. Proceedings (D. Bjørner, M. Broy, I. V. Pottosin, Eds.), LNCS 1181, Springer-Verlag, 1996.
• [25] Pettorossi, A., Proietti, M., Renault, S.: Reducing nondeterminism while specializing logic programs, Proceedings of the Twenty Fourth ACM Symposium on Principles of Programming Languages, ACM Press, 1997.
• [26] Romanenko, A. Y.: Inversion and metacomputation, Proceedings of the ACM Symposium on Partial Evaluation and Semantics-Based Program Manipulation, ACM Press, 1991.
• [27] Rosenblueth, D. A., Peralta, J. C.: SLR inference: an inference system for fixed-mode logic programs based on SLR parsing, Journal of Logic Programming, 34(3), 1998, 227–259.
• [28] Sippu, S., Soisalon-Soininen, E.: Parsing Theory II: LR(k) and LL(k) Parsing, vol. 20 of EATCS Monographs in Theoretical Computer Science, Springer-Verlag, Berlin, Heidelberg, New York, 1990.
• [29] Turchin, V. F.: Program transformation with metasystem transitions, Journal of Functional Programming, 3(3), 1993, 283–313.