A graph-based higher-order intermediate representation
Authors:
- 1 February 2015
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 202-212
Abstract
Many modern programming languages support both imperative and functional idioms. However, state-of-the-art imperative intermediate representations (IRs) cannot natively represent crucial functional concepts (like higher-order functions). On the other hand, functional IRs employ an explicit scope nesting, which is cumbersome to maintain across certain transformations. In this paper we present Thorin: a higher-order, functional IR based on continuation-passing style that abandons explicit scope nesting in favor of a dependency graph. This makes Thorin an attractive IR for both imperative as well as functional languages. Furthermore, we present a novel program transformation to eliminate the overhead caused by higher-order functions. The main component of this transformation is lambda mangling: an important transformation primitive in Thorin. We demonstrate that lambda mangling subsumes many classic program transformations like tail-recursion elimination, loop unrolling or (partial) inlining. In our experiments we show that higher-order programs translated with Thorin are consistently as fast as C programs.Keywords
This publication has 14 references indexed in Scilit:
- Code Refinement of Stencil CodesParallel Processing Letters, 2014
- Control-flow analysis of functional programsACM Computing Surveys, 2012
- Compiling with continuations, continued2007
- Secrets of the Glasgow Haskell Compiler inlinerJournal of Functional Programming, 2002
- SSA is functional programmingACM SIGPLAN Notices, 1998
- Sparse functional stores for imperative programs1995
- A correspondence between continuation passing style and static single assignment formACM SIGPLAN Notices, 1995
- The essence of compiling with continuations1993
- Efficiently computing static single assignment form and the control dependence graphACM Transactions on Programming Languages and Systems, 1991
- Lambda lifting: Transforming programs to recursive equations1985