Reusability and modularity in consumer, producer, and transformation operations

Abstract

Since 1954 when the first high-level programming language Fortran was invented, the past decades have witnessed several significant revolutions of modularization in programming areas: structured programming, modules and encapsulation, abstract objects and datatypes, inheritance, and many other paradigms of type systems and recursion patterns. The essence of modularization is that, by separating the functionality of a program into a network of independent or loosely dependent components, each component is easier to be reused and maintained without affecting others. And the ultimate goal of modularization, is to enhance the efficiency/productivity of programmers and reduce the cost of software development and maintenance, and meanwhile ensure (type) safety and execution performance as much as possible. Newly proposed modularization techniques in existing languages, can in turn promote the development of new language features and even new language paradigms.

In recent few years, researchers have put great effort on resolving the Expression Problem (coined by Philip Wadler) in different languages. The requirements for modularization are well described in the Expression Problem, especially it highlights two dimensions of extensibility at the same time: on data variants and operations. Unfortunately, although existing approaches satisfy this primary requirement, the term "operation" is not well identified; more specifically, most existing approaches focus on the modularity of consumer operations that consume data structures and collect information, but not producer operations that build data structures. Additionally, it is difficult to balance modularity with other attributes, including type-safety, conciseness, expressiveness, and efficiency.

This dissertation investigates modularization techniques for consumers and producers with simple, type-safe and reusable patterns, without breaking the modularity of data variants. Specifically, three research problems are studied in this dissertation: boilerplate traversals, type-safe modular parsing and modular unfolds. As a result, this dissertation proposes: Shy, a Java library that captures generic traversal patterns and automatically generates boilerplate traversal code with extensibility; a type-safe pattern for writing modular parsers in object-oriented programming; and SCCL, a specialized coalgebra combinator library for modularizing producers by modularizing categorical f-coalgebras in Haskell. Consequently, there is a significant reduction in client code due to modularity and reusability, evidenced by a number of case studies and applications.