So You Want To Analyze Scheme Programs With Datalog?
Static analysis approximates the results of a program by examining only its syntax. For example, control-flow analysis (CFA) determines which syntactic lambdas (for functional languages) or (for object-oriented) methods may be invoked at each call site within a program. Rich theoretical results exist studying control flow analysis for Scheme-like languages, but implementations are often complex and specialized. By contrast, object-oriented languages (Java in particular) enjoy high-precision control-flow analyses that scale to thousands (or more) of lines of code. State-of-the-art implementations (such as DOOP on Soufflé) structure the analysis using Horn-SAT (Datalog) to enable compilation of the analysis to efficient implementations such as high-performance relational algebra kernels. In this paper, we present an implementation of control-flow analysis for a significant subset of Scheme (including set!, call/cc, and primitive operations) using the Soufflé Datalog engine. We present an evaluation on a worst-case term demonstrating the polynomial complexity of our m-CFA and remark upon scalability results using Soufflé.
Sat 28 AugDisplayed time zone: Seoul change
01:30 - 03:00 | |||
01:30 30mFull-paper | Scheduling Musical Events in Max/MSP with Scheme For Max Scheme Iain Duncan University of Victoria Pre-print | ||
02:00 30mFull-paper | So You Want To Analyze Scheme Programs With Datalog? Scheme Davis Silverman Syracuse University, USA, Yihao Sun Syracuse University, Kristopher Micinski Syracuse University, Thomas Gilray University of Alabama at Birmingham Pre-print | ||
02:30 30mFull-paper | Prototypes: Object-Orientation, Functionally Scheme François-René Rideau Mutual Knowledge Systems, Inc., Alex Knauth Mutual Knowledge Systems, Inc., Nada Amin Harvard University Pre-print |