[Haskell-cafe] Graph theory analysis of Haskell code

[Tim Chevalier]

On 12/5/07, Ivan Miljenovic <ivan.miljenovic at gmail.com> wrote:
> How I envisage it happening is that a parser would be used to find all
> "functions" in the given code, treat these as nodes in the graph and
> then use directed edges to indicate which functions call other
> functions.

aka a "call graph". This is called "control flow analysis" and the
classic paper on it is Olin Shivers' dissertation, "Control Flow
Analysis of Higher Order Languages"
(http://repository.readscheme.org/ftp/papers/shivers-diss.ps.gz ).

> This resultant graph can then be analysed in various ways
> suitable to the context (e.g. find that a library module can be split
> into two since there are two completely separate trees present in the
> graph that don't interact at all, or if a function is only ever called
> by one other function then it can be subsumed into it).
>

One example of an analysis like this is done by GHC's inliner. See the
paper "Secrets of the Glasgow Haskell Compiler Inliner" by Peyton
Jones and Marlow
(http://research.microsoft.com/~simonpj/Papers/inlining/).


> So, here is the question I ask of all of you: is this feasible?  Do
> you know if anything like this has ever been attempted before?  I know
> there are some other usages of graph theory related to source code
> (e.g. McCabes complexity metric [1]), but I couldn't seem to find
> anything related to what I'm proposing.  I intend to code this up in
> Haskell (possibly using FGL: I know of it, but haven't really looked
> at it) and use Haskell as my primary target for analysis, so in a
> sense the resultant graph could be seen as a Haskell equivalent to
> UML.
>

This is very well-trodden ground, but if you familiarize yourself with
the literature on the subject, then who knows, you may discover
something new. And you can take pleasure in knowing that you've
already independently conceived of an idea that lots of smart people
have seen fit to put a lot of time into :-)

Cheers,
Tim

-- 
Tim Chevalier * catamorphism.org * Often in error, never in doubt
"It's true I don't want to join the Army or turn lathes in precision
parts factories, I'm nearsighted and psychopathic anyway.  America I'm
putting my queer shoulder to the wheel."  -- Allen Ginsberg