Finding Resource Bounds in the Presence of Explicit Deallocation

  • Hoang Truong
  • Marc Bezem
Conference paper
Part of the Lecture Notes in Computer Science book series (LNCS, volume 3722)


A software program requesting a resource that is not available usually raises an out-of-resource exception. Component software is software that has been assembled from standardized, reusable components which, in turn, may also composed from other components. Due to the independent development and reuse of components, component software has a high risk of causing out-of-resource exceptions. We present a small component language and develop a type system which can statically prevent this type of errors .

This work continues our previous works [3,18] by including explicit deallocation. We prove that the type system is sound with respect to safe deallocation and that sharp resource bounds can be computed statically.


Type System Component Software Local Store Operational Semantic Parallel Composition 
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.


Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.


  1. 1.
    Barendregt, H.: Lambda Calculi with Types. In: Abramsky, Gabbay, Maibaum (eds.) Handbook of Logic in Computer Science, vol. II. Oxford University Press, Oxford (1992)Google Scholar
  2. 2.
    Bezem, M., Truong, H.: A Type System for the Safe Instantiation of Components. Electronic Notes in Theoretical Computer Science 97 (July 2004)Google Scholar
  3. 3.
    Bezem, M., Truong, H.: Counting Instances of Software Components. In: Proceedings of LRPP 2004 (July 2004)Google Scholar
  4. 4.
    Cardelli, L.: Type systems. In: Tucker, A.B. (ed.) The Computer Science and Engineering Handbook, ch. 103, pp. 2208–2236. CRC Press, Boca Raton (1997)Google Scholar
  5. 5.
    Crary, K., Walker, D., Morrisett, G.: Typed Memory Management in a Calculus of Capabilities. In: Twenty-Sixth ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, San Antonio, TX, USA, January 1999, pp. 262–275 (1999)Google Scholar
  6. 6.
    Crary, K., Weirich, S.: Resource Bound Certification. In: The Twenty-Seventh ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, Boston, MA, USA, January 2000, pp. 184–198 (2000)Google Scholar
  7. 7.
    Dushnik, B., Miller, E.W.: Partially Ordered Sets. American Journal of Mathematics 63 (1941)Google Scholar
  8. 8.
    Englander, R.: Developing Java Beans, 1st edn. (June 1997) ISBN 1-56592-289-1Google Scholar
  9. 9.
    Gamma, E., Helm, R., Johnson, R., Vlissides, J.: Design Patterns - Elements of Reusable Object-Oriented Software. Addison-Wesley, Reading (1994) ISBN 0201633612Google Scholar
  10. 10.
    Meijer, E., Szyperski, C.: Overcoming Independent Extensibility Challenges. Communications of the ACM 45(10), 41–44 (2002)CrossRefGoogle Scholar
  11. 11.
    Pierce, B.: Types and Programming Languages. MIT Press, Cambridge (2002) ISBN 0-262-16209-1Google Scholar
  12. 12.
    Pierce, B.: Advanced Topics in Types and Programming Languages. MIT Press, Cambridge (2005) ISBN 0-262-16228-8zbMATHGoogle Scholar
  13. 13.
    Seco, J.C.: Adding Type Safety to Component Programming. In: Proc. of the PhD Student’s Workshop in FMOODS 2002, University of Twente, the Netherlands (March 2002)Google Scholar
  14. 14.
    Smith, F., Walker, D., Morrisett, G.: Alias Types. In: European Symposium on Programming, Berlin, Germany (March 2000)Google Scholar
  15. 15.
    Szyperski, C.: Component Software: Beyond Object-Oriented Programming, 2nd edn. Addison-Wesley, Reading (2002) ISBN 0201745720Google Scholar
  16. 16.
    Terese: Term Rewriting Systems. Cambridge Tracts in Theoretical Computer Science, vol. 55. Cambridge University Press, Cambridge (2003)Google Scholar
  17. 17.
    Thai, T., Lam, H.: .NET Framework Essentials, 3rd edn. (August 2003) ISBN 0-596-00302-1Google Scholar
  18. 18.
    Truong, H.: Guaranteeing Resource Bounds for Component Software. In: Steffen, M., Zavattaro, G. (eds.) FMOODS 2005. LNCS, vol. 3535, pp. 179–194. Springer, Heidelberg (2005)CrossRefGoogle Scholar
  19. 19.
    Wadler, P.: Linear types can change the world! In: Broy, M., Jones, C. (eds.) Programming Concepts and Methods, Sea of Galilee, Israel, April 1990. North Holland, Amsterdam (1990) IFIP TC 2 Working ConferenceGoogle Scholar
  20. 20.
    Wright, A.K., Felleisen, M.: A Syntactic Approach to Type Soundness. Information and Computation 115(1), 38–94 (1994)zbMATHCrossRefMathSciNetGoogle Scholar
  21. 21.
    Zenger, M.: Type-Safe Prototype-Based Component Evolution. In: Magnusson, B. (ed.) ECOOP 2002. LNCS, vol. 2374, p. 470. Springer, Heidelberg (2002)CrossRefGoogle Scholar

Copyright information

© Springer-Verlag Berlin Heidelberg 2005

Authors and Affiliations

  • Hoang Truong
    • 1
  • Marc Bezem
    • 1
  1. 1.Department of InformaticsUniversity of BergenBergenNorway

Personalised recommendations