Abstract: Despite significant progress in programming technology, large-scale software development remains expensive and error prone. We identify four problems with object-oriented programming that contribute to this situation: implementation bias, feature combinatorics, representation assembly, and representation selection. The first two problems complicate software decomposition, where implementation bias is a single component's overdependence on non-essential implementation details, and feature combinatorics is the library design challenge of implementing a compact set of non-redundant building blocks spanning a feature space. The last two problems afflict software recomposition, where representation assembly refers to the safe integration of components, and representation selection to a client's choice of an optimal implementation of some interface. Current mechanisms of decomposition and recomposition such as aggregation, inheritance, and aspect-orientation do not address all of these problems. These mechanisms are known to be fragile under evolution, require global reasoning that violates component encapsulation, and trade decomposability for safety and reusability for performance. We trace the source of these problems to a lack of interface abstraction at instantiation sites (including new object instantiations as well as implementation inheritance dependencies), together with the lack of locally-encapsulated constraints on reuse. To solve these problems we first extend the object-oriented paradigm to a new model called interface-oriented programming (IOP), which we then implement in a language called PJ. In PJ, the implementation-biased partial class increments of OOP are generalized and replaced with the particle construct, an unbiased partial class construct where all inheritance dependencies, variable types, and dynamic instantiation expressions are declared using interfaces. A particle may also specify encapsulated recomposition constraints in terms of interfaces. We then present representation inference , a new form of composition that automatically infers alternative integrated sequences of particles that completely implement interfaces while also respecting each particle's local constraints. The final element of our design is a language-integrated, pervasive factory mechanism that dynamically selects interface representations from the inferred alternatives using the context of each instantiation site, enabling context-sensitive representation choices without sacrificing reusability. We demonstrate via examples implemented in PJ how our solution addresses each problem.