A common task in programming is to arrange for data to be passed from the point where it first becomes available to the places where it is needed, which may be much further down the call hierarchy. One approach is to store the data in a global variable. Another alternative is to add extra parameters at each level to thread it from the point of supply to the point of use. Neither of these is particularly attractive: The former is inflexible, while the latter requires modification of the program text, adding auxiliary parameters to each function definition and call.
This paper explores the design space for a third alternative, using types to direct the introduction and use of implicit parameters and so carry data from supply to use. This gives the flexibility of parameterization without the burden of adding parameters by hand. The most general point in the design space uses relations on types to support sophisticated forms of overloading, and includes several known systems as special cases, including Haskell type classes and a recent proposal for dynamic scoping in statically-typed languages. Our work provides new insights about the relationships between these systems, as well as some new ideas that are useful in their own right. A particular novelty of this paper is in the application of ideas from the theory of relational databases to the design of type systems.