This 2006 paper by Moseley and Marks was recommended by Rich Hickey, among others; I first saw it recommended on StackOverflow.com.
- PDF: Out of the Tar Pit
- Summary: Proposes the Functional Relational Programming (FRP) approach to address out-of-control complexity in software.
You can witness many of the ideas below actually implemented (at least partly) in the Clojure language and some of its libraries.
The Four Main Points
- Complexity is the main source of problems in software: it must be
avoided whenever possible; when unavoidable, it must be
Complexity Type Recommendation Essential Logic Separate Essential Complexity State Separate Accidental Useful Complexity State/Control Separate Accidental Useless Complexity State/Control AVOID
- Look for: essential vs. accidental complexity
- State (esp. hidden state) is the main source of complexity,
e.g. frequent "solution" to re-install, restart, reboot - they're
all about getting to a known working state!
- Testing is made much harder by state. With functional paradigm, it's far easier.
- Control: imperative programming causes accidental control-complexity.
- Code volume: the less code, the better.
- Other causes: complexity breeds complexity; simplicity is hard; and too-powerful programming languages corrupt.
- Their critique of OOP, functional, and logic programming is
excellent - clearly outlines problems in each:
- OOP: "Conventional imperative and object-oriented programs suffer greatly from both state-derived and control-derived complexity."
- Functional: avoiding state/side-effects => referential
transparency. But that advantage can be lost if one has to
pass around huge parameter-set.
- Monads are one solution to enable state, but "can very easily be abused to create a stateful, side-effecting sub-language".
- A system can be separated into three main parts, supported by
language(s) and infrastructure:
- Essential Logic: i.e. behavior. In FRP, functional and relational basis
- Essential State: in FRP, relational basis
- Accidental State and Control: - e.g. optimizations, derived data one uses for performance and convenience
- Aim for simplicity: With old and new systems, avoid state, avoid explicit control where possible, and get rid of code generally.
- Their recommended approach is functional relational programming:
- State in the ideal world:
Data Essentiality Data Type Data Mutability Classification Essential Input - Essential State Essential Derived Immutable Accidental State Essential Derived Mutable Accidental State Accidental Derived - Accidental State
- Accidental state can always be (re)derived, should be excluded
from ideal world.
- Most systems have large amounts of accidental state.
- Control in the ideal world: generally, should be completely omitted from the ideal world. Requirements should not be concerned with execution.
- Formal specification languages
- Functional, Logic programming enables executable specifications.
- Two main camps:
- Property-based, focus on what is required and not how it's to be achieved. Includes algebraic approaches, e.g. Larch, OBJ. The authors favor this approach.
- Model-based/State-based: build a (stateful) model of the system, specify how it behaves. e.g. Z, VDM. Usually specifies how a stateful, imperative language solution must behave.
- Required Accidental Complexity, 7.2.3:
- For performance/efficiency (most commonly needed)
- For ease of expression
- Use DSLs to separate, restrict power of languages to make them easier to reason about.
- The Relational Model
- Four parts: structure, manipulation (specifies derived data), integrity, data independence (logical data separate from its physical representation)
- NOT the same as SQL.
- Accidental state can always be (re)derived, should be excluded from ideal world.
- State in the ideal world: