Generating generic functions

Abstract

We present an approach to the generation of generic functions from user-provided specifications. The specifications consist of the type of a generic function, examples of instances that it should “match” when specialized, and properties that the generic function should satisfy. We use the type-based function generator Djinn to generate terms for specializations of the generic function types on the type indices of generic functions. Then we use QuickCheck to prune the generated terms by testing against properties, and by testing specialized candidate functions against the provided examples. Using this approach we have been able to generate generic equality, map, and zip functions, for example. Categories and Subject Descriptors D.1.m [Programming Techniques]: Generic Programming; I.2.2 [Artificial Intelligence]: Automatic Programming General Terms Design, Experimentation