Self-Assembly: Lightweight Language Extension and Datatype Generic Programming, All-in-One!

In this paper we show a general mechanism, called self-assembly, for lightweight language extensions (LLEs). LLEs allow users to define generic operations or properties that operate over a large class of types. With LLEs it is possible, for example, for users to define their own Java-style automatic serialization mechanism; or implement simple forms of custom pluggable type system extensions like an immutability checker. However unlike language built-in mechanisms (such as Java serialization), LLEs are user-definable, multi-purpose (they can be used to define various forms of generic functionality), and highly customizable and extensible. The key idea, inspired by existing datatype-generic programming approaches, is to provide programmers with a generic mechanism for providing automatic implementations of type classes. We implemented our technique as a library, \sselfassembly, for Scala, and evaluated its practicality by migrating a full-featured industrial-strength serialization framework, Scala/Pickling, keeping the same published performance numbers while reducing the code size for type class instance generation by 56%.