Higher-Order Redundancy Elimination

Functional programs often define functions by pattern matching where patterns may inadvertedly overlap through successive function calls. This leads to hidden inefficiencies since the recursively called function possibly repeats redundant tests while trying to match the pattern. An analysis which is based on conservative symbolic execution (similar to higher order constant propagation) is proposed for a strict higher-order language to drive an arity raiser which generates specialized versions for functions with partially known arguments. To ensure termination only the definitely consumed part of the partially known arguments is considered. 1 Introduction Pattern matching is ubiquitous in modern functional programming languages like ML or Haskell. It is a convenient tool to build readable programs that process algebraic datatypes. However, pattern matching is a high-level concept that the compiler must transform into sequences of test operations. Patterns must be unnested to yield flat..