language: en

Type-driven Defunctionalization

Jeffrey M. Bell & Fran~coise Bellegarde & James Hook
Pacific Software Research Center Oregon Graduate Institute of Science & Technology
PO Box 91000 Portland, Oregon 97291-1000 USA
fbell,bellegar,hookg@cse.ogi.edu

Abstract In 1972, Reynolds outlined a general method for eliminating functional arguments known as defunctionalization. The idea underlying defunctionalization is encoding functional values as first-order data, and then to realized the applications of the encoded function via an apply function. Although this process is simple enough, problems arise when defunctionalization is used in a polymorphic language. In such a language, a functional argument of a higher-order function can take different type instances in different applications. As a consequence, its associated apply function can be untypable in the soucre language. In the paper we present a defunctionalization transformation which preserves typa-bility. Moreover, the transformation imposes no restriction on functional arguments of recursive functions, and it handles functions as results as well as functions encapsulated in constructors or tuples. The key to this success is the use of type information in the defunctionalization transformation. Run-time characteristics are preserved by defunction-alization; hence, there is no performance improvement coming from the transformation itself. However closures need not be implemented to compile the transformed program. Since the defunctionalization is driven by type information, it can also easily perform a specialization of higher-order functions with respect to the values of their functional arguments, hence gaining a real run-time improvement of the transformed program.

1 Introduction