Constructing call graphs of Scala programs

Karim Ali; Marianna Rapoport; Ondřej Lhoták; Julian Dolby; Frank Tip

doi:10.1007/978-3-662-44202-9_3

Constructing call graphs of Scala programs

Karim Ali, Marianna Rapoport, Ondřej Lhoták, Julian Dolby, Frank Tip

Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

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.

Original language	English (US)
Title of host publication	ECOOP 2014 - Object-Oriented Programming
Subtitle of host publication	28th European Conference, Proceedings
Publisher	Springer Verlag
Pages	54-79
Number of pages	26
ISBN (Print)	9783662442012
DOIs	https://doi.org/10.1007/978-3-662-44202-9_3
State	Published - 2014
Event	28th European Conference on Object-Oriented Programming, ECOOP 2014 - Uppsala, Sweden Duration: Jul 28 2014 → Aug 1 2014

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	8586 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	28th European Conference on Object-Oriented Programming, ECOOP 2014
Country/Territory	Sweden
City	Uppsala
Period	7/28/14 → 8/1/14

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/978-3-662-44202-9_3

Cite this

Ali, K., Rapoport, M., Lhoták, O., Dolby, J., & Tip, F. (2014). Constructing call graphs of Scala programs. In ECOOP 2014 - Object-Oriented Programming: 28th European Conference, Proceedings (pp. 54-79). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 8586 LNCS). Springer Verlag. https://doi.org/10.1007/978-3-662-44202-9_3

Constructing call graphs of Scala programs. / Ali, Karim; Rapoport, Marianna; Lhoták, Ondřej et al.
ECOOP 2014 - Object-Oriented Programming: 28th European Conference, Proceedings. Springer Verlag, 2014. p. 54-79 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 8586 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Ali, K, Rapoport, M, Lhoták, O, Dolby, J & Tip, F 2014, Constructing call graphs of Scala programs. in ECOOP 2014 - Object-Oriented Programming: 28th European Conference, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 8586 LNCS, Springer Verlag, pp. 54-79, 28th European Conference on Object-Oriented Programming, ECOOP 2014, Uppsala, Sweden, 7/28/14. https://doi.org/10.1007/978-3-662-44202-9_3

Ali K, Rapoport M, Lhoták O, Dolby J, Tip F. Constructing call graphs of Scala programs. In ECOOP 2014 - Object-Oriented Programming: 28th European Conference, Proceedings. Springer Verlag. 2014. p. 54-79. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-662-44202-9_3

@inproceedings{a7d8e278902f47dda93fec7e379e66ca,

title = "Constructing call graphs of Scala programs",

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.",

author = "Karim Ali and Marianna Rapoport and Ond{\v r}ej Lhot{\'a}k and Julian Dolby and Frank Tip",

year = "2014",

doi = "10.1007/978-3-662-44202-9_3",

language = "English (US)",

isbn = "9783662442012",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "54--79",

booktitle = "ECOOP 2014 - Object-Oriented Programming",

note = "28th European Conference on Object-Oriented Programming, ECOOP 2014 ; Conference date: 28-07-2014 Through 01-08-2014",

}

TY - GEN

T1 - Constructing call graphs of Scala programs

AU - Ali, Karim

AU - Rapoport, Marianna

AU - Lhoták, Ondřej

AU - Dolby, Julian

AU - Tip, Frank

PY - 2014

Y1 - 2014

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=84905397852&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84905397852&partnerID=8YFLogxK

U2 - 10.1007/978-3-662-44202-9_3

DO - 10.1007/978-3-662-44202-9_3

M3 - Conference contribution

AN - SCOPUS:84905397852

SN - 9783662442012

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 54

EP - 79

BT - ECOOP 2014 - Object-Oriented Programming

PB - Springer Verlag

T2 - 28th European Conference on Object-Oriented Programming, ECOOP 2014

Y2 - 28 July 2014 through 1 August 2014

ER -

Constructing call graphs of Scala programs

Abstract

Publication series

Conference

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this