iBet uBet web content aggregator. Adding the entire web to your favor.
iBet uBet web content aggregator. Adding the entire web to your favor.



Link to original content: https://unpaywall.org/10.1007/BFB0053377
Near optimal hierarchical encoding of types | SpringerLink
Skip to main content
Springer Nature Link
Log in

Near optimal hierarchical encoding of types

  • Conference paper
  • First Online:
ECOOP'97 — Object-Oriented Programming (ECOOP 1997)

Part of the book series: Lecture Notes in Computer Science ((LNCS,volume 1241))

Included in the following conference series:

Abstract

A type inclusion test is a procedure to decide whether two types are related by a given subtyping relationship. An efficient implementation of the type inclusion test plays an important role in the performance of object oriented programming languages with multiple subtyping like C++, Eiffel or Java. There are well-known methods for performing fast constant time type inclusion tests that use a hierarchical bit vector encoding of the partial ordered set representing the type hierarchy. The number of instructions required by the type inclusion test is proportional to the length of those bit vectors. We present a new algorithm based on graph coloring which computes a near optimal hierarchical encoding of type hierarchies. The new algorithm improves significantly on previous results — it is faster, simpler and generates smaller bit vectors.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

References

  1. Hassan At-Kaci, Robert Boyer, Patrick Lincoln, and Roger Nasr. Efficient implementation of lattice operations. ACM Transactions on Programming Languages and Systems, 11(1):115–146, 1989.

    Article  Google Scholar 

  2. Preston Briggs, Keith Cooper, Ken Kennedy, and Linda Torczon. Coloring heuristics for register allocation. In ACM Conference on Programming Language Design and Implementation, pages 275–284, Portland, June 1993. ACM.

    Google Scholar 

  3. Yves Caseau. Efficient handling of multiple inheritance hierarchies. In Conference on Object Oriented Programming Systems, Languages & Applications, pages 271–287, Washington, October 1993. ACM.

    Google Scholar 

  4. Norman H. Cohen. Type-extension type tests can be performed in constant time. ACM Transactions on Programming Languages and Systems, 13(4):626–629, 1991.

    Article  Google Scholar 

  5. Peter Dencker, Karl Dürre, and Johannes Heuft. Optimization of parser tables for portable compilers. ACM Transactions on Programming Languages and Systems, 6(6):546–572, 1984.

    Article  Google Scholar 

  6. J. A. Ellis and P. M. Lepolesa. A Las Vegas graph coloring algorithm. The Computer Journal, 32(5):474–476, 1989.

    Article  MathSciNet  Google Scholar 

  7. Charles Fleurent and Jacques A. Ferland. Genetic and hybrid algorithms for graph coloring. Annals of Operations Research, page to appear, 1995.

    Google Scholar 

  8. James Gosling, Frank Yellin, and The Java Team. The Java Application Programming Interface. Addison-Weley, 1996.

    Google Scholar 

  9. Michel Habib and Lhouari Nourine. Bit-vector encoding for partially ordered sets. In ORDAL'94, LNCS 831, pages 1–12. Springer, 1994.

    Google Scholar 

  10. Michel Habib and Lhouari Nourine. Tree structure for distributive lattices and its applications. Theoretical Computer Science, 165:391–405, 1996.

    Article  MathSciNet  Google Scholar 

  11. David W. Matula and Leland L. Beck. Smallest-last ordering and clustering and graph coloring algorithms. Journal of the ACM, 30(3):417–427, July 1983.

    Article  MathSciNet  Google Scholar 

  12. David W. Matula, George Marble, and Joel D. Isaacson. Graph coloring algorithms. In R. C. Read, editor, Graph Theory and Computing, pages 109–122. Academic Press, 1972.

    Google Scholar 

  13. Niklaus Wirth. Type extensions. ACM Transactions on Programming Languages and Systems, 10(2):204–214, 1988.

    Article  MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Institut für Computersprachen, Technische Universität Wien, Argentinierstraße 8, A-1040, Wien, Austria

    Andreas Krall

  2. Object Systems Group, Centre Universitaire d'Informatique, Université de Genève, 24 rue Général-Dufour, CH-1211, Geneva, Switzerland

    Jan Vitek

  3. Department of Computer Science, University of Victoria, P.O. Box 3055, V8W 3P6, Victoria, BC, Canada

    R. Nigel Horspool

Authors
  1. Andreas Krall
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Jan Vitek
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. R. Nigel Horspool
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Mehmet Akşit Satoshi Matsuoka

Rights and permissions

Reprints and permissions

Copyright information

© 1997 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Krall, A., Vitek, J., Horspool, R.N. (1997). Near optimal hierarchical encoding of types. In: Akşit, M., Matsuoka, S. (eds) ECOOP'97 — Object-Oriented Programming. ECOOP 1997. Lecture Notes in Computer Science, vol 1241. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0053377

Download citation

  • DOI: https://doi.org/10.1007/BFb0053377

  • Published:

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-63089-0

  • Online ISBN: 978-3-540-69127-3

  • eBook Packages: Springer Book Archive

Publish with us

Policies and ethics

Search

Navigation