Control-flow Analysis of Functional Programs

Jan Midtgaard, ACM Computing Surveys, 2012, forthcoming

Abstract

We present a survey of control-flow analysis of functional programs, which has been the subject of extensive investigation throughout the past 30 years. Analyses of the control flow of functional programs have been formulated in multiple settings and have led to many different approximations, starting with the seminal works of Jones, Shivers, and Sestoft. In this paper, we survey control-flow analysis of functional programs by structuring the multitude of formulations and approximations and comparing them.

Revision history

This CFA survey started out as a chapter of my thesis. Since then it has undergone several revisions:

The first revision is available as BRICS technical report RS-07-18.
The second revision didn't make it. ;-)
The third revision was accepted to ACM CSur.

Here's the latest version as pdf, © ACM, 2010. This is the author's version of the work. It is posted here by permission of ACM for your personal use. Not for redistribution.

Survey material

Here's a BibTeX entry for the survey itself:

@Article{Midtgaard:CSur12,
  author = 	 "Jan Midtgaard",
  title = 	 "Control-flow analysis of functional programs",
  year = 	 2012,
  journal =      "{ACM} Computing Surveys",
  note =         "Forthcoming",
}

Here's the BibTeX file containing the references from the survey.

I keep scanned electronic copies of some of the more rare papers cited above. Send me an email if you are missing a specific paper.

Post-survey material

Since the completion of the survey the following CFA papers have been published:

Abstracting Abstract Machines
David Van Horn and Matthew Might, The 15th ACM SIGPLAN International Conference on Functional Programming (ICFP'10), DOI link
Polyvariant flow analysis with higher-ranked polymorphic types and higher-order effect operators
Stefan Holdermans and Jurriaan Hage, The 15th ACM SIGPLAN International Conference on Functional Programming (ICFP'10), DOI link
Abstract Interpreters for Free
Matthew Might, Static Analysis, 17th International Symposium (SAS 2010), DOI link
Pushdown Control-Flow Analysis of Higher-Order Programs
Christopher Earl, Matthew Might, and David Van Horn, The 2010 Workshop on Scheme and Functional Programming (SFP 2010)
EigenCFA: Accelerating flow analysis with GPUs
Tarun Prabhu, Shreyas Ramalingam, Matthew Might, and Mary Hall, The 38th Annual ACM Symposium on the Principles of Programming Languages. (POPL'11), DOI link
Flow-Sensitive Sub-Zero Control-Flow Analysis in Linear-Log Time
Michael D. Adams, Andrew W. Keep, Jan Midtgaard, Matthew Might, Arun Chauhan, and R. Kent Dybvig, The 26th ACM SIGPLAN Conference on Object-Oriented Programming, Systems, Languages, and Applications (OOPSLA 2011), DOI link
Ordering Multiple Continuations on the Stack
Dimitrios Vardoulakis and Olin Shivers, The 2011 ACM SIGPLAN Workshop on Partial Evaluation and Program Manipulation (PEPM 2011), DOI link
Pushdown Flow Analysis of First-Class Control
Dimitrios Vardoulakis and Olin Shivers, The 16th ACM SIGPLAN International Conference on Functional Programming (ICFP 2011), DOI link
...

Send me an email if you are aware of other CFA papers.