[Colloq] REMINDER: PhD Thesis Defense-Dimitris Vardoulakis, Today at 2:30pm in 366 WVH

[kirsten at ccs.neu.edu]

The College of Computer and Information Science presents: 

Thesis Defense by: 
Dimitris Vardoulakis 

Date: Monday, June 4th, 2012 
Time: 2:30pm 
Where: 366 WVH 

Thesis Title: CFA2: Pushdown Flow Analysis for Higher-Order Languages 

Abstract: 

Most higher-order flow analyses approximate programs as graphs. Each node in such a graph represents a program point plus some information about the environment and the calling context. The analysis considers every path in the graph to be a possible execution of the program. 
Therefore, executions are strings in a regular language. 

This abstraction is sufficient for languages like Fortran, where most control flow happens with conditionals and loops. But in a higher-order language, the dominant control-flow mechanism is function call and return. The execution traces that properly match calls with returns are strings in a context-free language. Approximating this control flow with a regular language permits spurious paths where a function is called from one program point and returns to a different one. Call/return mismatch degrades precision and may also slow down the analysis. 

We present flow analyses that provide unbounded call/return matching in a general setting: our analyses apply to typed and untyped languages, with first-class functions, side effects, tail calls and first-class control. This is made possible by several individual techniques. We generalize the concept of summaries to powerful control constructs, like tail calls and continuations. We propose a syntactic classification of variable references that allows precise lookups for local references and falls back to a conservative approximation for references captured in closures. We show that the use of big-step semantics in a flow analysis can minimize memory consumption and make the analysis faster. We present experimental results from two implementations for Scheme and JavaScript which show that our analyses work well in practice. 

Thesis Committee: 

Olin Shivers (Advisor) 
Matthias Felleisen 
Mitchell Wand 
Alex Aiken (External member, Stanford University) 


Kirsten Anderson
Northeastern University
College of Computer & Information Science
202 West Village H
360 Huntington Ave
Boston, MA 02115
(617) 373-8685
(617) 373-5121