Nothing Special   »   [go: up one dir, main page]

Skip to main content

Constructing Call Graphs of Scala Programs

  • Conference paper
ECOOP 2014 – Object-Oriented Programming (ECOOP 2014)

Part of the book series: Lecture Notes in Computer Science ((LNPSE,volume 8586))

Included in the following conference series:

Abstract

As Scala gains popularity, there is growing interest in programming tools for it. Such tools often require call graphs. However, call graph construction algorithms in the literature do not handle Scala features, such as traits and abstract type members. Applying existing call graph construction algorithms to the JVM bytecodes generated by the Scala compiler produces very imprecise results due to type information being lost during compilation. We adapt existing call graph construction algorithms, Name-Based Resolution (RA) and Rapid Type Analysis (RTA), for Scala, and present a formalization based on Featherweight Scala. We evaluate our algorithms on a collection of Scala programs. Our results show that careful handling of complex Scala constructs greatly helps precision and that our most precise analysis generates call graphs with 1.1-3.7 times fewer nodes and 1.5-18.7 times fewer edges than a bytecode-based RTA analysis.

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

Access this chapter

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 39.99
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 54.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Agesen, O.: Constraint-based Type Inference and Parametric Polymorphism. In: LeCharlier, B. (ed.) SAS 1994. LNCS, vol. 864, pp. 78–100. Springer, Heidelberg (1994)

    Chapter  Google Scholar 

  2. Ali, K., Lhoták, O.: Application-only Call Graph Construction. In: Noble, J. (ed.) ECOOP 2012. LNCS, vol. 7313, pp. 688–712. Springer, Heidelberg (2012)

    Chapter  Google Scholar 

  3. Ali, K., Lhoták, O.: averroes: Whole-program analysis without the whole program. In: Castagna, G. (ed.) ECOOP 2013. LNCS, vol. 7920, pp. 378–400. Springer, Heidelberg (2013)

    Chapter  Google Scholar 

  4. Ali, K., Rapoport, M., Lhoták, O., Dolby, J., Tip, F.: Constructing call graphs of Scala programs. Tech. Rep. CS-2014-09, U. of Waterloo (2014)

    Google Scholar 

  5. Bacon, D.F.: Fast and Effective Optimization of Statically Typed Object-Oriented Languages. PhD thesis, University of California, Berkeley (1997)

    Google Scholar 

  6. Bacon, D.F., Sweeney, P.F.: Fast static analysis of C++ virtual function calls. In: OOPSLA, pp. 324–341 (1996)

    Google Scholar 

  7. Bravenboer, M., Smaragdakis, Y.: Strictly Declarative Specification of Sophisticated Points-to Analyses. In: OOPSLA, pp. 243–262 (2009)

    Google Scholar 

  8. Cremet, V., Garillot, F., Lenglet, S., Odersky, M.: A core calculus for Scala type checking. In: Královič, R., Urzyczyn, P. (eds.) MFCS 2006. LNCS, vol. 4162, pp. 1–23. Springer, Heidelberg (2006)

    Chapter  Google Scholar 

  9. Dean, J., Grove, D., Chambers, C.: Optimization of object-oriented programs using static class hierarchy analysis. In: Olthoff, W. (ed.) ECOOP 1995. LNCS, vol. 952, pp. 77–101. Springer, Heidelberg (1995)

    Google Scholar 

  10. DeFouw, G., Grove, D., Chambers, C.: Fast Interprocedural Class Analysis. In: POPL, pp. 222–236 (1998)

    Google Scholar 

  11. Grove, D., Chambers, C.: A framework for call graph construction algorithms. ACM Trans. Program. Lang. Syst. 23(6), 685–746 (2001)

    Article  Google Scholar 

  12. Heintze, N.: Set-Based Analysis of ML Programs. In: LISP and Functional Programming, pp. 306–317 (1994)

    Google Scholar 

  13. Heintze, N., Tardieu, O.: Ultra-fast Aliasing Analysis using CLA: A Million Lines of C Code in a Second. In: PLDI, pp. 254–263 (2001)

    Google Scholar 

  14. Henglein, F.: Dynamic Typing. In: Krieg-Brückner, B. (ed.) ESOP 1992. LNCS, vol. 582, pp. 233–253. Springer, Heidelberg (1992)

    Chapter  Google Scholar 

  15. IBM. T.J. Watson Libraries for Analysis WALA (April 2013), http://wala.sourceforge.net/

  16. Kneuss, E., Suter, P., Kuncak, V.: Phantm: PHP analyzer for type mismatch. In: SIGSOFT FSE, pp. 373–374 (2010)

    Google Scholar 

  17. Lhoták, O., Hendren, L.: Scaling Java Points-to Analysis Using SPARK. In: Hedin, G. (ed.) CC 2003. LNCS, vol. 2622, pp. 153–169. Springer, Heidelberg (2003)

    Chapter  Google Scholar 

  18. Lhoták, O., Hendren, L.: Context-Sensitive Points-to Analysis: Is It Worth It? In: Mycroft, A., Zeller, A. (eds.) CC 2006. LNCS, vol. 3923, pp. 47–64. Springer, Heidelberg (2006)

    Chapter  Google Scholar 

  19. Odersky, M.: The Scala Language Specification version 2.9. Tech. rep., EPFL, DRAFT (May 2011)

    Google Scholar 

  20. Odersky, M., Spoon, L., Venners, B.: Programming in Scala, 2nd edn. Artima Press (2012)

    Google Scholar 

  21. Ryder, B.: Constructing the call graph of a program. IEEE Transactions on Software Engineering 5(3), 216–226 (1979)

    Article  MATH  MathSciNet  Google Scholar 

  22. Sallenave, O., Ducourneau, R.: Lightweight generics in embedded systems through static analysis. In: LCTES, pp. 11–20 (2012)

    Google Scholar 

  23. Sewe, A., Mezini, M., Sarimbekov, A., Binder, W.: Da capo con scala: design and analysis of a Scala benchmark suite for the Java virtual machine. In: OOPSLA, pp. 657–676 (2011)

    Google Scholar 

  24. Shivers, O.: Control-Flow Analysis of Higher-Order Languages. PhD thesis, CMU (May 1991)

    Google Scholar 

  25. Sridharan, M., Dolby, J., Chandra, S., Schäfer, M., Tip, F.: Correlation Tracking for Points-To Analysis of JavaScript. In: Noble, J. (ed.) ECOOP 2012. LNCS, vol. 7313, pp. 435–458. Springer, Heidelberg (2012)

    Chapter  Google Scholar 

  26. Srivastava, A.: Unreachable procedures in object oriented programming. ACM Letters on Programming Languages and Systems 1(4), 355–364 (1992)

    Article  Google Scholar 

  27. Tip, F., Palsberg, J.: OOPSLA, pp. 281–293 (2000)

    Google Scholar 

  28. Tip, F., Sweeney, P.F., Laffra, C., Eisma, A., Streeter, D.: Practical extraction techniques for Java. ACM Trans. Program. Lang. Syst. 24(6), 625–666 (2002)

    Article  Google Scholar 

  29. Vallée-Rai, R., Gagnon, E.M., Hendren, L., Lam, P., Pominville, P., Sundaresan, V.: Optimizing Java Bytecode Using the Soot Framework: Is It Feasible? In: Watt, D.A. (ed.) CC 2000. LNCS, vol. 1781, pp. 18–34. Springer, Heidelberg (2000)

    Chapter  Google Scholar 

Download references

Author information

Authors and Affiliations

Authors

Editor information

Editors and Affiliations

1 Electronic Supplementary Material

Rights and permissions

Reprints and permissions

Copyright information

© 2014 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Ali, K., Rapoport, M., Lhoták, O., Dolby, J., Tip, F. (2014). Constructing Call Graphs of Scala Programs. In: Jones, R. (eds) ECOOP 2014 – Object-Oriented Programming. ECOOP 2014. Lecture Notes in Computer Science, vol 8586. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-662-44202-9_3

Download citation

  • DOI: https://doi.org/10.1007/978-3-662-44202-9_3

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-662-44201-2

  • Online ISBN: 978-3-662-44202-9

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics