Sun Sep 13 10:22:16 CEST 2009

Control-Flow Analysis of Higher-Order Languages (Shivers)

Based on the techniques of CPS and non-standard abstract semantic
interpretation (NSAS).

The basic problem is described as an interdependency of two analysis
phases: flow analysis needs a control flow graph, but because code can
be bound to variables, the construction of the control flow graph
needs flow analysis.

In CPS Scheme, the problem is reduced to determining which call sites
call which lambdas.  This is because all control transfers are
represented by procedure calls.  This problem is represented as the
search for a function L(c) which maps a call site c to a minimal set
of lambda expressions that are possibly called at c.

NSAS is described as a technique to construct a computable analysis
for a certain property X.

    - Start with a denotational semantics S

    - Construct a _non-standard_ semantics S_X derived from S, that
      precisely expresses X.

    - Construct an _abstract_ version of S_X that trades accuracy for
      compile-time computability.

Note that this is one of (the main?) practical reasons why
denotational semantics are important.

The denotational semantics for CPS Scheme is presented as an
``interpreter written in a functional language''.

[1] http://www.ccs.neu.edu/home/shivers/citations.html#diss