Jan Midtgaard’s excellent survey on CFA has been accepted by ACM Computing Surveys and is now “forthcoming”. It’s been a valuable resource to me and others; I recommend it to anyone interested in the literature on CFA.
http://www.brics.dk/~jmi/Midtgaard%3aCSur10.html
Control-flow Analysis of Functional Programs
Jan Midtgaard, ACM Computing Surveys, 2010, forthcoming
Abstract
We present a survey of control-flow [...]
Joachim Breitner has recently formalized Shivers’ kCFA algorithm and proof of correctness in Isabelle:
http://afp.sourceforge.net/entries/Shivers-CFA.shtml
A Haskell prototype of the Isabelle formalization is also available on Hackage in the ’shivers-cfg’ package:
http://hackage.haskell.org/package/shivers-cfg
Tell the Doctor about it.
Doctor JS is a genius. He’ll analyze your JavaScript code, complete with: polymorphism, prototypes, exceptions, and callbacks.
DoctorJS is a static analysis tool developed by my PRL lab neighbor, Dimitris Vardoulakis. It’s an implementation of Vardoulakis and Olin Shivers‘ CFA2—a context-free approach to control flow analysis.
Brendan Eich, CTO of [...]
We’ve been working on two techniques for systematically deriving abstract interpretations approximating canonical machines for higher-order languages. The first allocates continuations in a bounded store to achieve a finite state-space. We demonstrate the generality of this approach by transforming classical abstract machines into abstract interpreters.
Abstracting Abstract Machines.
David Van Horn and Matthew Might.
The 15th ACM SIGPLAN [...]
A new preprint by Matthew Might, Yannis Smaragdakis, and David Van Horn.
Preprint
Slides from NEPLS
Implementation
Abstract:
Low-level program analysis is a fundamental problem, taking the shape of “flow analysis” in functional languages and “points-to” analysis in imperative and object-oriented (OO) languages. Despite the similarities, the vocabulary and results in the two communities remain largely distinct, with limited [...]
The Higher-Order Flow Analysis Forum has just been set up:
The HOFA forum is an email forum for the discussion and dissemination of research results in the area of higher-order flow analysis, broadly construed, within computer science and related disciplines. Flow analysis and related static analyses are a fundamental tool for program verification, bug detection, compiler [...]
The Complexity of Flow Analysis in Higher-Order Languages: Abstract, Dissertation, Slides.
PhD Thesis Defense
Computer Science Department
Brandeis University
Date: Wednesday, July 22, 2009
Time: 2-4pm
Place: Volen 101
The Complexity of Flow Analysis in Higher-Order Languages
David Van Horn
Abstract:
This dissertation proves lower bounds on the inherent difficulty of deciding flow analysis problems in higher-order programming languages. We give exact characterizations of the computational complexity of 0CFA, the kCFA hierarchy, and related analyses. [...]
Subcubic Control Flow Analysis Algorithms, Jan Midtgaard and David Van Horn.
We give the first direct subcubic algorithm for performing control flow analysis of higher-order functional programs. Despite the long held belief that inclusion-based flow analysis could not surpass the “cubic bottleneck, ” we apply known set compression techniques to obtain an algorithm that runs in [...]