There and Back Again

• Autorzy: Danvy O. , Goldberg M.
• Języki publikacji: EN

Abstrakty

EN

We present a programming pattern where a recursive function defined over a data structure traverses another data structure at return time. The idea is that the recursive calls get us `there' by traversing the first data structure and the returns get us `back again' while traversing the second data structure. We name this programming pattern of traversing a data structure at call time and another data structure at return time "There And Back Again" (TABA). The TABA pattern directly applies to computing symbolic convolutions and to multiplying polynomials. It also blends well with other programming patterns such as dynamic programming and traversing a list at double speed. We illustrate TABA and dynamic programming with Catalan numbers. We illustrate TABA and traversing a list at double speed with palindromes and we obtain a novel solution to this traditional exercise. Finally, through a variety of tree traversals, we show how to apply TABA to other data structures than lists. A TABA-based function written in direct style makes full use of an ALGOL-like control stack and needs no heap allocation. Conversely, in a TABA-based function written in continuation-passing style and recursively defined over a data structure (traversed at call time), the continuation acts as an iterator over a second data structure (traversed at return time). In general, the TABA pattern saves one from accumulating intermediate data structures at call time.

Słowa kluczowe

EN

recursive programming; continuations; defunctionalization; There And Back Again; TABA

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2005
• Tom: Vol. 66, nr 4
• Strony: 397--413
• Opis fizyczny: Bibliogr. 20 poz.

Twórcy

autor

Danvy O.

• BRICS, Department of Computer Science, University of Aarhus IT-parken, Aabogade 34, DK-8200 Aarhus N, Denmark

autor

Goldberg M.

• Department of Computer Science, Ben Gurion University Be’er Sheva 84105, Israel

Bibliografia

• [1] Śrī Bhāratī Kŗşna Tīrthajī Mahārāja, J. S.: Vedic Mathematics, Motilal Banarsidass Publishers Private Limited, 1992.
• [2] Biernacka, M., Biernacki, D., Danvy, O.: An Operational Foundation for Delimited Continuations in the CPS Hierarchy, Technical Report BRICS RS-04-29, DAIMI, Department of Computer Science, University of Aarhus, Aarhus, Denmark, December 2004, A preliminary version was presented at the the Fourth ACM SIGPLAN Workshop on Continuations (CW 2004).
• [3] Bird, R. S.: Using circular programs to eliminate multiple traversals of data, Acta Informatica, 21, 1984, 239–250.
• [4] Burge,W. H.: Recursive Programming Techniques, Addison-Wesley, 1975.
• [5] Danvy, O.: On listing list prefixes, LISP Pointers, 2(3-4), January 1989, 42–46.
• [6] Danvy, O., Filinski, A.: Representing Control, A Study of the CPS Transformation, Mathematical Structures in Computer Science, 2(4), 1992, 361–391.
• [7] Danvy, O., Lawall, J. L.: Back to Direct Style II: First-Class Continuations, Proceedings of the 1992 ACM Conference on Lisp and Functional Programming (W. Clinger, Ed.), LISP Pointers, Vol. V, No. 1, ACM Press, San Francisco, California, June 1992.
• [8] Danvy, O., Nielsen, L. R.: Defunctionalization at Work, Proceedings of the Third International ACM SIGPLAN Conference on Principles and Practice of Declarative Programming (PPDP’01) (H. Søndergaard, Ed.), ACM Press, Firenze, Italy, September 2001, Extended version available as the technical report BRICS RS-01-23.
• [9] Gill, A. J., Launchbury, J., Jones, S. L. P.: A Short Cut to Deforestation, Proceedings of the Sixth ACM Conference on Functional Programming and Computer Architecture (Arvind, Ed.), ACMPress, Copenhagen, Denmark, June 1993.
• [10] Graham, R. L., Knuth, D. E., Patashnik, O.: Concrete Mathematics, Addison-Wesley, 1989.
• [11] Mogensen, T. A.: Glossary for Partial Evaluation and Related Topics, Higher-Order and Symbolic Computation, 13(4), 2000, 355–368.
• [12] Pettorossi, A.: Program Development Using Lambda Abstraction, Foundations of Software Technology and Theoretical Computer Science, Seventh Conference (K. V. Nori, Ed.), number 287 in Lecture Notes in Computer Science, Springer-Verlag, Pune, India, December 1987.
• [13] Pettorossi, A., Proietti, M.: Importing and Exporting Information in Program Development, Partial Evaluation and Mixed Computation (D. Bjørner, A. P. Ershov, N. D. Jones, Eds.), North-Holland, 1988.
• [14] Pettorossi, A., Proietti,M.: A Comparative Revisitation of some ProgramTransformationTechniques, Partial Evaluation (O. Danvy, R. Gl¨uck, P. Thiemann, Eds.), number 1110 in Lecture Notes in Computer Science, Springer-Verlag, Dagstuhl, Germany, February 1996.
• [15] Reynolds, J. C.: Definitional Interpreters for Higher-Order Programming Languages, Higher-Order and Symbolic Computation, 11(4), 1998, 363–397, Reprinted from the proceedings of the 25th ACM National Conference (1972), with a foreword.
• [16] Steele Jr., G. L.: Common Lisp: The Language, Digital Press, 1984.
• [17] Tofte, M., Birkedal, L., Elsman, M., Hallenberg, N.: A Retrospective on Region-Based Memory Management, Higher-Order and Symbolic Computation, 17(3), 2004, 245–265.
• [18] Wadler, P.: Deforestation: Transforming programs to eliminate trees, Theoretical Computer Science, 73(2), 1989, 231–248.
• [19] Wand, M.: Continuation-Based Program Transformation Strategies, Journal of the ACM, 27(1), January 1980, 164–180.
• [20] Xi, H., Pfenning, F.: Dependent Types in Practical Programming, Proceedings of the Twenty-Sixth Annual ACM Symposium on Principles of Programming Languages (A. Aiken, Ed.), ACMPress, San Antonio, Texas, January 1999.