Constraints to Stop Higher-Order Deforestation

Abstract

Wadler's deforestation algorithm removes intermediate data structures from functional programs. To be appropriate for inclusion in a compiler, deforestation must terminate on all programs. Several techniques exist to ensure termination of deforestation on all first-order programs, but a technique for higher-order programs was only recently introduced by Hamilton and later Marlow. We present a new technique for ensuring termination of deforestation on all higher-order programs that allows useful transformation steps prohibited in Hamilton's and Marlow's techniques. The technique uses a constraint-based higher-order control-flow analysis. 1 Introduction Lazy, higher-order, functional programming languages lend themselves to a certain style of programming which uses intermediate data structures [28]. However, this style also leads to inefficient programs. Example 1 Consider the following program. letrec a = x; y: case x of [] ! y (h : t) ! h : a t y in u; v; w: a (a u v) w The mai...