Paper notes: Out of the Tar Pit, Moseley and Marks 2006

This 2006 paper by Moseley and Marks was recommended by Rich Hickey, among others; I first saw it recommended on StackOverflow.com.

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

  1. Complexity is the main source of problems in software: it must be avoided whenever possible; when unavoidable, it must be separated/divided.
    Essential LogicSeparate
    Essential ComplexityStateSeparate
    Accidental Useful ComplexityState/ControlSeparate
    Accidental Useless ComplexityState/ControlAVOID
    • 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".
  2. A system can be separated into three main parts, supported by language(s) and infrastructure:
    1. Essential Logic: i.e. behavior. In FRP, functional and relational basis
    2. Essential State: in FRP, relational basis
    3. Accidental State and Control: - e.g. optimizations, derived data one uses for performance and convenience
  3. Aim for simplicity: With old and new systems, avoid state, avoid explicit control where possible, and get rid of code generally.
  4. Their recommended approach is functional relational programming:
    • State in the ideal world:
      Data EssentialityData TypeData MutabilityClassification
      EssentialInput-Essential State
      EssentialDerivedImmutableAccidental State
      EssentialDerivedMutableAccidental State
      AccidentalDerived-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:
          1. 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.
          2. 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.
blog comments powered by Disqus