[Colloq] PhD Thesis Defense-Dimitris Vardoulakis, Monday, June 4th at 2:30pm

[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: 166 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