Efficient Interpretation by Transforming Data Types and Patterns to Functions

Abstract: This paper describes an efficient interpreter for lazy functional languages like Haskell and Clean. The interpreter is based on the elimination of algebraic data types and pattern-based function definitions by mapping them to functions using a new efficient variant of the Church encoding. The transformation is simple and yields concise code. We illustrate the concepts by showing how to map Haskell and Clean programs to the intermediate language SAPL (Simple Application Programming Language) consisting of pure functions only. An interpreter is described for SAPL, based on straightforward graph reduction techniques. This interpreter can be kept small and elegant because function application is the only operation in SAPL. The application of a few easy to realize optimisations turns this interpreter into an efficient one. The resulting performance turns out to be competitive in a comparison with other interpreters like Hugs, Helium, GHCi and Amanda for a large number of benchmarks. 1.