[Pl-seminar] PL seminar schedule (NOTE: nonstandard day/time)

[Aaron Turon]

NEU Programming Languages Seminar presents

Norman Ramsey
Tufts University

Thursday, May 6, 2010

1:15pm - 3:00pm
Room 366 WVH (http://www.ccs.neu.edu/home/wand/directions.html)

                       Beautiful Optimization
                  Norman Ramsey, Tufts University
         (joint work with João Dias and Simon Peyton Jones)

If you pick up a compiler textbook and turn to the section on code
improvement (optimization), you'll find a rat's nest of analysis and
transformations, painstakingly specified with lots of imperative
operations on sets, and seemingly unrelated to each other or anything
else.  But if you dig deeper, you may discover that many of the
analyses are simple applications of program logic, and most of the
transformations can be composed from simpler transformations:
substitution of equals for equals, removal of redundant assignments,
and insertion(!) of redundant assignments.  As part of work on the
back end of the Glasgow Haskell Compiler, I've been trying to solve
two problems:

 - Find new ways of thinking about old optimizations, so that
   ugly algorithms can be recast as beautiful reasoning.

 - Find ways of implementing analysis and optimization that reflect
   how we'd like to think about them, so that our beautiful reasoning
   can be reflected in beautiful code.

I'm exploring these problems as my colleagues and I build a Haskell
library called 'Hoopl', which is only now becoming mature enough to
address interesting problems.  I therefore plan a very informal talk:

 - Some reminders about program logic and dataflow analysis,
   emphasizing their relationship

 - How Hoopl helps you implement an optimization based on dataflow
   analysis

 - Some example dataflow 'passes', which may combine analysis and
   optimization

 - Perhaps some irresponsible speculation about elimination of
   induction variables and reduction in operator strength

I will also mention an open problem: what should we do, as
semanticists, about the problem that dataflow analysis seems more
powerful than Hoare logic?