Tuesday, May 19, 2015 - 12:00pm to 1:00pm
Location:Traffic 21 Classroom 6501 Gates & Hillman Centers
Speaker:NICOLAS FELTMAN, Ph.D. Student http://www.cs.cmu.edu/~nfeltman/
Staged programming languages assign a stage to each expression and evaluate each expression in its assigned stage. While staged programming has been studied extensively in the areas of partial evaluation and meta programming, in this talk we present an algorithm for statically splitting programs written in a two-stage typed lambda calculus (with a circle modality denoting computation in a later stage) into multi-pass programs that are structured as two dependent, unstaged programs and are evaluated using two distinct execution passes. While splitting has been studied in the past under the names "pass separation" and "data specialization", such techniques were either manual or applicable only to simple programs that lack important features such as recursion and first-class functions. Since this work builds on a lambda calculus, our splitting algorithm enables the programmer to write staged programs by using powerful programming abstractions in a composable and modular fashion. Our splitting transformation maps such programs into multi-pass programs that can run significantly more efficiently by assigning frequent computations to earlier passes so that they can be reused (cheaply) later. Our experiments based on a prototype implementation show that our splitting algorithm is able to perform highly non-trivial algorithmic transformations, sometimes automatically improving efficiency asymptotically by nearly a linear factor. Since the splitting transformation takes place at compile time, these benefits are achieved without significant run-time penalty. Presented in Partial Fulfillment of the CSD Speaking Skills Requirement.