Modelling Scoped Instances With Constraint Handling Rules

Modelling Scoped Instances with Constraint Handling Rules

based on the master thesis by Gerrit van den Geest.

• Atze Dijkstra, Gerrit van den Geest, Bastiaan Heeren, S. Doaitse Swierstra, 2007
• Rejected by ICFP 2007
• Abstract: Haskell's class system provides a programmer with a mechanism to implicitly pass parameters to a function. A class predicate over some type variable in the type signature of a function induces the obligation for the caller to implicitly pass an appropriate instance of the class to the function. The class system is programmed by providing class instances for concrete types, thus providing, for each class, a unique mapping from types to instances. This mapping is used whenever an instance for a class predicate over some type is required. Choosing which instance to pass is solely based on the instantiated type of the class predicate.
  Although this mechanism has proved to be powerful enough for modelling overloading and a plethora of other programming language concepts, it is still limited in the sense that multiple instances for a type cannot exist at the same time. Usually one can program around this limitation by introducing dummy types, which act as a key to map to additional instances; but this indirect way of allowing extra instances clutters a program and still is bound to the finite number of types statically available in a program. The latter restriction makes it impossible to dynamically construct instances, which, for example, depend on runtime values.
  In this paper we lift these restrictions by means of local instances. Local instances allow us to shadow existing instances by new ones and to construct instances inside functions, using function arguments. We provide a translation of class and instance definitions to Constraint Handling Rules, making explicit the notion of ``scope of an instance'' and its role in context reduction for instances. We deal with the ambiguity of choosing between instances by using a framework for heuristically choosing between otherwise overlapping instances.

-- AtzeDijkstra - 21 Sep 2007