Incremental algorithms for dispatching in dynamically typed languages. (English) Zbl 1321.68177
Proceedings of the 30th ACM SIGPLAN-SIGACT symposium on principles of programming languages, POPL ’03, New Orleans, LA, USA, January 15–17, 2003. New York, NY: Association for Computing Machinery (ACM) (ISBN 1-58113-628-5). 126-138 (2003).
MSC:
| 68N19 | Other programming paradigms (object-oriented, sequential, concurrent, automatic, etc.) |
| 68N15 | Theory of programming languages |
References:
| [1] | K. Arnold and J. Gosling. The Java Programming Language. The Java Series. Addison-Wesley, Reading, Massachusetts, 1996. · Zbl 0876.68015 |
| [2] | P. Deutsch and A. Schiffman. Efficient implementation of the Smalltalk-80 system. In 11th Symposium on Principles of Programming Languages, POPL’84, pages 297-302, Salt Lake City, Utah, Jan. 1984. ACM SIGPLAN — SIGACT, ACM Press. 10.1145/800017.800542 |
| [3] | M. Dietzfelbinger, A. R. Karlin, K. Mehlhorn, F. Meyer auf der Heide, H. Rohnert, and R. E. Tarjan. Dynamic perfect hashing: Upper and lower bounds. SIAM J. Comput., 23(4):738-761, Aug. 1994. 10.1137/S0097539791194094 · Zbl 0820.68038 |
| [4] | R. Dixon, T. McKee, M. Vaughan, and P. Schweizer. A fast method dispatcher for compiled languages with multiple inheritance. In Proceedings of the 4th Annual Conference on Object-Oriented Programming Systems, Languages, and Applications, pages 211-214, New Orleans, Louisiana, Oct. 1-6 1989. OOPSLA’89, ACM SIGPLAN Notices 24(10) Oct. 1989. 10.1145/74877.74900 |
| [5] | K. Driesen. Selector table indexing & sparse arrays. In Proceedings of the 8th Annual Conference on Object-Oriented Programming Systems, Languages, and Applications, pages 259-270, Washington, DC, USA, Sept. 26 - Oct. 1 1993. OOPSLA’93, ACM SIGPLAN Notices 28(10) Oct. 1993. 10.1145/165854.165902 |
| [6] | K. Driesen and U. Hölzle. Minimizing row displacement dispatch tables. In Proceedings of the 10th Annual Conference on Object-Oriented Programming Systems, Languages, and Applications, pages 141-155, Austin, Texas, USA, Oct. 15-19 1995. OOPSLA’95, ACM SIGPLAN Notices 30(10) Oct. 1995. 10.1145/217838.217851 |
| [7] | P. Ferragina and S. Muthukrishnan. Efficient dynamic method-lookup for object oriented languages. In J. Díaz and M. Serna, editors, Algorithms-ESA ’96, Fourth Annual European Symposium, volume 1136 of Lecture Notes in Computer Science, pages 107-120, Barcelona, Spain, 25-27 Sept. 1996. Springer. · Zbl 1379.68105 |
| [8] | M. L. Fredman, J. Komlós, and E. Szemerédi. Storing a sparse table with O(1) worst case access time. J. ACM, 31(3):538-544, July 1984. 10.1145/828.1884 · Zbl 0629.68068 |
| [9] | J. Y. Gil and P. Sweeney. Space- and time-efficient memory layout for multiple inheritance. In Proceedings of the 14th Annual Conference on Object-Oriented Programming Systems, Languages, and Applications, pages 256-275, Denver, Colorado, Nov.1-5 1999. OOPSLA’99, ACM SIGPLAN Notices 34(10) Nov. 1999. 10.1145/320384.320408 |
| [10] | U. Hölzle, C. Chambers, and D. Ungar. Optimizing dynamically-typed object-oriented languages with polymorphic inline caches. In Proceedings of the 5th European Conference on Object-Oriented Programming, number 512 in Lecture Notes in Computer Science, Geneva, Switzerland, July 15-19 1991. ECOOP’91, Springer Verlag. |
| [11] | S. Muthukrishnan and M. Müller. Time and space efficient method-lookup for object-oriented programs. In Proceedings of the Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, pages 42-51, New York/Philadelphia, Jan. 28-30 1996. ACM/SIAM. · Zbl 0847.68016 |
| [12] | A. Royer. Optimizing Method Search with Lookup Caches and Incremental Coloring. In Proceedings of the 7th Annual Conference on Object-Oriented Programming Systems, Languages, and Applications, pages 110-126, Vancouver, British Columbia, Canada, Oct.18-22 1992. OOPSLA’92, ACM SIGPLAN Notices 27(10) Oct. 1992. 10.1145/141936.141947 |
| [13] | D. Sleator and R. Tarjan. Self-adjusting binary search trees. J. ACM, 32(3):652-686, July 1985. 10.1145/3828.3835 · Zbl 0631.68060 |
| [14] | B. Stroustrup. The Design and Evolution of C++. Addison-Wesley, Reading, Massachusetts, Mar. 1994. |
| [15] | J. Vitek and R. N. Horspool. Taming message passing: Efficient method lookup for dynamically typed object-oriented languages. In Proceedings of the 8th European Conference on Object-Oriented Programming, number 821 in Lecture Notes in Computer Science, Bologna, Italy, July 4-8 1994. ECOOP’94, Springer Verlag. |
| [16] | J. Vitek and R. N. Horspool. Compact dispatch tables for dynamically typed object oriented languages. In T. Gyimothy, editor, Compiler Construction, 6th International Conference, volume 1060 of Lecture Notes in Computer Science, pages 309-325, Linköping, Sweden, 24-26 Apr. 1996. Springer. |
| [17] | O. Zendra, C. Colnet, and S. Collin. Efficient dynamic dispatch without virtual function tables: The SmallEiffel compiler. In Proceedings of the 12th Annual Conference on Object-Oriented Programming Systems, Languages, and Applications, pages 125-141, Atlanta, Georgia, Oct. 5-9 1997. OOPSLA’97, ACM SIGPLAN Notices 32(10) Oct. 1997. 10.1145/263698.263728 |
| [18] | Y. Zibin and J. Y. Gil. Fast algorithm for creating space efficient dispatching tables with application to multi-dispatching. In Proceedings of the 17th Annual Conference on Object-Oriented Programming Systems, Languages, and Applications, pages 142-160, Seattle, Washington, Nov. 4-8 2002. OOPSLA’02, ACM SIGPLAN Notices 37(10) Nov. 2002. 10.1145/582419.582434 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
