Typeless Typeclasses: Implementing Monads and Monad Transformers in Lisp
Please login to view abstract download link
Typeclasses are an abstraction that facilitates parametric overloading, also known as bounded polymorphism, in programming languages and theorem provers. In practical terms, typeclasses can be used to write highly abstract algorithms and perform automated reasoning. They have seen great success in such academic and industrial programming systems as Isabelle, Coq, Haskell and Lean [1]. As the name suggests, typeclasses are usually implemented in typed contexts, where the type system can guide instance resolution and enforce invariants. Since the widespread success of typeclasses stems from these affordances, one would expect giving them up to be widely regarded as a bad move. However, we demonstrate that it is not quite so, and that it may even provide some benefits, by implementing typeclasses in a modern dialect of Lisp --- the language of choice for exploring the possibilities of artificial intelligence on automated computing machines. We propose a way to implement typeclasses using just lists, symbols, procedures and SRFI-39 parameters, in addition to a few optional SRFI-93 macros for convenience. Our implementation is first-class and supports many features seen in other similar systems, including inheritance, constraints, minimal complete definitions, laws and proof erasure. As a result, our implementation is small, easy to understand, and allows expressing less conventional ideas like higher-order instances and deferred instance resolution. In order to test the viability of our approach, we implement the algebraic hierarchy from equivalence relations to groups to rings and the categorical hierarchy from functors to monads to monad transformers in two flavors. This covers the corresponding classes and some of their best-known instances [2]. While we can confidently say that typeclasses are indeed usable without a type system, we are still unsure whether it is actually a good idea to do so. Our implementation is still in prototype stage, and our experiences of its usability are biased by prior knowledge. Some essential classes and instances are missing from our test suite, our conformance checker is incomplete, and our macros are not as hygienic as they ought to be [3]. We want to improve our implementation and try to incorporate it into a teaching context before we draw any conclusions.