Out Of The Tar Pit

2006 - Ben Mosely & Peter Marks pdf


  1. What is meant by complexity.
  2. Why complexity is a problem.
  3. Causes of complexity.
  4. In relation to common programming paradigms.
  5. Proposal for an optimum solution.

What is complexity?

...the type of complexity we are discussing in this paper is that which makes large systems hard to understand.

Why is complexity important?

The primary status of complexity as the major cause of [the problems of software development] comes simply from the fact that being able to understand a system is a prerequisite for avoiding all of them

Approaches to understanding.

  1. Testing
  2. Informal Reasoning

Causes of complexity.

A look at the common causes of complexity that not inherent to the problem domain.


The stored information, at a point in time, to which the program has access.

  • Each bit of state doubles the total number of states
  • Otherwise pure functions that call stateful functions are stateful.
  • Results potentially affected by everything that has gone before.*

This is why rebooting works!


Specification of the order in which program statements are executed.

  • Over specification, how as opposed to what.
  • We must understand which orderings are actually important.
  • Concurrency, another level of complexity.


  • Often caused by State and Control
  • Linear or non-linear relationship to complexity?


  • Complexity breeds complexity
  • Simplicty is hard
  • Power corrupts

Managing complexity.

How the problems of complexity are tackled in common programming paradigms.

Object Orientation.

  • Traditionally encourage state, though encapsulated.
  • Typically imperative, explicit flow of control.
  • Identity vs Value.

Not suitable for controlling complexity.

Functional Programming.

  • Discourage mutable state, simpler concurrency.
  • More declarative, use of functions over collections i.e map / reduce etc.
  • Not immune from state-like, approaches.
  • Less modularity than OOP.

Improvement over OOP, especially with regard to state.

Logic Programming.

  • Even more declarative style than FP.
  • Actual implmentations (i.e. Prolog) often include state and flow of control issues, i.e. non-termination.

The Relational Model

... an elegant approach to structuring data, a means for manipulating such data, and a mechanism for maintaining integrity and consistency of state
  • Query languages typically minimal state, minimal flow control.
  • Doesn't have to be SQL (which does have some problems).
  • "Lower powered" Prolog variants, like Datalog, have potential.*

Functional Relational Programming.

A proposed optimum approach for minimising complexity, making use of functional / logical paradigms along with Codd's relational model.

Ideal scenario.

The system is restricted to the following three elements.

  1. Essential state, captured in a relational model.
  2. Essential logic, captured in relational model or in pure functions.
  3. Accidental state and control.

Accidental state and control.

  • Required for performance / scalability etc.
  • Seperated from essentials.
  • System should run in absence of this component.
  • Declarative performance hints.

Questions / Discussion

  • Emphasis on relational model, are devs comfortable?
  • How do micro-service architectures compare to this approach?
  • Anyone up for a compsci UG in Manchester?

Slides at http://www.ryanwgough.com

@ryanwgough on Twitter