Colibri: The Fully Declarative And Turing-Complete Language Lurking Inside Swift’s Type System

In this article I want to show you Colibri, a language using type declarations for modelling logic, behavior and relationships. It is found within Swift’s type system. Colibri follows Language Oriented Programming — each module (be it a model type, use case or feature) defines it own set of instructions that can be used to interact with it. These instructions are defined in one or more Domain Specific Languages (DSL). It is fully declarative.

Declarative programming is a style of programming that expresses the logic of computation without describing its control flow. It allows you to focus on the ‘what’ of a program, rather than the ‘how’. Declarative programs can be constructed in a fraction of the time, using much less code than a traditional computer program. Declarative methods for programming and data modelling can help avoid making the mistakes that have lead to failing software projects for several decades. — Declarative Amsterdam

Let’s start with a simple example, a math engine that adds, subtracts, multiplies, and divides in a serial fashion.
In Colibri this might looks as follows:

• The struct MathEngine has a nested enum Operations which has four cases: to add a double, to subtract a double, to multiply with a double and to divide by a double.

struct MathEngine {
    enum Operation {
        case add(Double)
        case subtract(Double)
        case multiply(with:Double)
        case divide(by: Double)
    }
    // ...
}

• It also has a nested enum called Command with one case to register a listener callback function.

struct MathEngine {
    //...
    enum Command {
        case register(listener: (MathEngine) -> ())
    }
    //...
}

• The current value and any listener are kept in member properties.

struct MathEngine {
    //...
    let value: Double
    let listeners: [(Self) -> ()]
    
    init(value: Double) {
        self.init(value, [])
    }
    
    private init(_ value: Double,_ listeners: [(Self) -> Void]) {
        self.value = value
        self.listeners = listeners
        listeners.forEach{ $0(self) }
    }
    //...
}

• The alter method receives one or several Operation values and pattern matches them to simple codes implementing the wanted behaviour. It returns a new instance of MathEngine with the newly calculated value.
  In the first case it adds the given amount, in the second it multiplies the value with it. The third case implements subtracting by adding the negative amount recursively, and the fourth case implements division by multiplying with the reciprocal amount recursively.

struct MathEngine {
    //...
    func alter(_ operation: Operation) -> MathEngine {
        switch operation {
        case .add(let a)            : MathEngine(value + a, listeners)
        case .multiply(with: let a) : MathEngine(value * a, listeners)
        case .subtract(let a)       : alter(.add(-a))
        case .divide(by: let a)     : alter(.multiply(with: 1.0/a))
        }
    }
    // ...
}

• The last piece of our MathEngine is the settings method that takes a Command and decodes it via pattern matching. The only command our engine knows right now is the .register(listener:...) command. It returns a new MathEngine with the new callback added to the listeners array.

struct MathEngine {
    //...
    func settings(_ c:Command) -> Self {
        switch c {
        case let .register(listener:l): Self(value, listeners + [l])
        }
    }
}

This is the complete MathEngine data structure uninterrupted:

struct MathEngine {
    enum Operation {
        case add(Double)
        case subtract(Double)
        case multiply(with:Double)
        case divide(by: Double)
    }
    enum Command {
        case register(listener: (MathEngine) -> ())
    }

    let value: Double
    let listeners: [(Self) -> ()]

    init(value: Double) {
        self.init(value, [])
    }
    private init(_ value: Double,_ listeners: [(Self) -> Void]) {
        self.value = value
        self.listeners = listeners
        listeners.forEach{ $0(self) }
    }

    func alter(_ o:[Operation])  -> Self { o.reduce(self) { $0.alter($1) } }
    func alter(_ o:Operation...) -> Self { alter(o) }
    func alter(_ operation: Operation) -> MathEngine {
        switch operation {
        case .add(let a)            : MathEngine(value + a, listeners)
        case .multiply(with: let a) : MathEngine(value * a, listeners)
        case .subtract(let a)       : alter(.add(-a))
        case .divide(by: let a)     : alter(.multiply(with: 1.0/a))
        }
    }
    func settings(_ c:Command) -> Self {
        switch c {
        case let .register(listener:l): Self(value, listeners + [l])
        }
    }
}

Now let’s have a look how to use this data structure.

First we define a callback method that prints our MathEngine's value:

func print(_ m: MathEngine) {
    print(m.value)
}

We create a MathEngine x that has an initial value of 100. We register our print callback function as a listener and than add 50, multiply with 2, divide by 3, and subtract 50.

let x = MathEngine(value: 100)
    .settings(.register(listener: print))
    .alter(.add(50))
    .alter(.multiply(with: 2))
    .alter(.divide(by: 3))
    .alter(.subtract(50))

This will be printed to the console:

100.0
150.0
300.0
100.0
50.0

Since alter is overloaded to also work with lists of Operations, we might do the following:

let y = MathEngine(value: 1000)
    .settings(.register(listener: print))
    .alter(
        .add(500),
        .subtract(250),
        .multiply(with: 2),
        .divide(by: 0.25)
    )

For our second example let’s create a bank account.
It has

• an id
• a list of transactions, which either can be withdrawal or deposit
• a lineOfCredit to which we can borrow
• a list of eventListeners who will be informed for any deposit and withdrawal attempt
• a computed property totalAmount which will be the sum of any deposit and withdrawal

In alter first a check will be performed to ensure a withdrawal transaction won't result into a totalAmount below the credit line. All listeners will be informed via an event .withdrawal(of: a, from:self, .failed) or .withdrawal(of: a, from:self, .succeeded). A deposit transaction will always succeed.
If the transaction passes the test it will be added to the list of transactions and a new Account will be returned

Finally the account has an admin method that can be used to set the line of credit and to register new event listeners.

struct Account {
    enum Transaction {
        case withdrawal(amount: UInt)
        case deposit(amount: UInt)
    }
    enum Operation {
        case make(transaction:Transaction)
    }
    enum Event {
        enum Response {
            case failed
            case succeeded
        }
        case withdrawal(of:UInt,from:Account, Response)
        case deposit   (of:UInt, on:Account, Response)
    }
    enum Admin {
        case lineOfCredit(UInt)
        case register(eventListener:(Event) -> ())
    }

    let id: String
    let transactions: [Transaction]
    let lineOfCredit: UInt
    let eventListener:[(Event) -> ()]
    var totalAmount: Int {
        transactions.reduce(0) {
            switch $1 {
            case let .withdrawal(a): return $0 - Int(a)
            case let .deposit   (a): return $0 + Int(a)
            }
        }
    }

    init(id:String) {
        self.init(id ,[], 0, [])
    }

    private init(_ id:String, _ transactions: [Transaction], _ loc:UInt, _ l:[(Event) -> ()]) {
        self.id = id
        self.transactions = transactions
        self.lineOfCredit = loc
        self.eventListener = l
    }

    func alter (_ c: Operation...) -> Self { c.reduce(self) { $0.alter($1) } }
    private func alter(_ c:Operation) -> Self {
        func isWithdrawalPossible(_ amount: UInt) -> Bool { (totalAmount + Int(lineOfCredit) - Int(amount) >= 0) }
        switch c {
        case let .make(transaction: .withdrawal(amount: a)):
            switch isWithdrawalPossible(a) {
            case false: eventListener.forEach{ $0(.withdrawal(of: a, from:self, .failed)) }; return self
            case true : eventListener.forEach{ $0(.withdrawal(of: a, from:self, .succeeded)) }
            }
        case let .make(transaction: .deposit(amount: a)): eventListener.forEach{ $0(.deposit(of: a, on: self, .succeeded)) }
        }
        switch c {
        case let .make(transaction: t): return Self(id, transactions + [t], lineOfCredit, eventListener)
        }
    }

    func admin(_ a:Admin...) -> Self { a.reduce(self) { $0.admin($1) }  }
    private func admin(_ a:Admin) -> Self {
        switch a {
        case let .lineOfCredit(l)           : Self(id, transactions, l           , eventListener      )
        case let .register(eventListener: l): Self(id, transactions, lineOfCredit, eventListener + [l])
        }
    }
}

Now let’s use Account.
First we define a print function that takes an Account.Event

func print(_ e:Account.Event) {
    switch e {
    case let .withdrawal(of:a, from:acc, .succeeded): print("withdrawal of \(a) from \(acc.id) succeeded")
    case let .withdrawal(of:a, from:acc, .failed)   : print("withdrawal of \(a) from \(acc.id) failed")
    case let .deposit   (of:a,   on:acc, .succeeded): print("deposit of \(a) on \(acc.id) succeeded")
    case let .deposit   (of:a,   on:acc, .failed)   : assert(false, "deposit should never fail")
    }
}

We create an Account, register print on it, and perform several transactions.

var x = Account(id: "100101")
x = x.admin(.register(eventListener: print))
x = x.admin(.lineOfCredit(200))
x = x.alter(.make(transaction: .deposit(amount: 1000)))
x = x.alter(.make(transaction: .withdrawal(amount: 500)))
x = x.alter(.make(transaction: .withdrawal(amount: 600)))
x = x.alter(.make(transaction: .withdrawal(amount: 200)))
print("total on \(x.id): \(x.totalAmount)")

It will output

deposit of 1000 on 100101 succeeded
withdrawal of 500 from 100101 succeeded
withdrawal of 600 from 100101 succeeded
withdrawal of 200 from 100101 failed
total on 100101: -100

As alter and admin are overloaded to also accept lists of values, we can do:

let y = Account(id: "223344")
    .admin(
        .register(eventListener: print),
        .lineOfCredit(300)
    )
    .alter(
        .make(transaction: .deposit(amount: 1000)),
        .make(transaction: .withdrawal(amount: 500)),
        .make(transaction: .withdrawal(amount: 400)),
        .make(transaction: .withdrawal(amount: 400)),
        .make(transaction: .withdrawal(amount: 1))
    )
print("total on \(y.id): \(y.totalAmount)")

The next example is a TodoItem data type.
It has an id, a title, a state (unfinished, inProgress, finished), a dueDate, a location (unknown, an address or a coordinate with latitude and longitude), and a list of collaborators.
It Change DSL encodes six instructions:

• .setting(.title(to: <new string>))
• .setting(.state(to: <new state>))
• .setting(.dueDate(to: <new date>))
• .setting(.location(to: <new location>))
• .adding(.collaborator(<new collaborator>))
• .removing(.collaborator(<existing collaborator>))

In alter we pair each of this instruction with the minimal code needed to implement the behaviour

struct TodoItem {
    enum Change {
        case setting(Setting); enum Setting {
            case title   (to: String)
            case state   (to: State)
            case dueDate (to: DueDate)
            case location(to: Location)
        }
        case adding(Adding); enum Adding   {
            case collaborator(Collaborator)
        }
        case removing(Removing); enum Removing {
            case collaborator(Collaborator)
        }
    }

    let id           : UUID
    let title        : String
    let state        : State
    let dueDate      : DueDate
    let location     : Location
    let collaborators: [Collaborator]

    init(title: String) {
        self.init(UUID(), title, .unfinished, .none, .unknown, [])
    }
    private init(_ i:UUID, _ t: String, _ s:State, _ d:DueDate, _ l:Location, _ c:[Collaborator]) {
        id            = i
        title         = t
        state         = s
        dueDate       = d
        location      = l
        collaborators = c
    }
  
    func alter(by c:[Change])  -> Self { c.reduce(self) { $0.alter(by:$1) } }
    func alter(by c:Change...) -> Self { alter(by: c) }
    private func alter(by c: Change) -> Self {
        switch c {
        case let .setting(.title(to: t))    : Self(id, t    , state, dueDate, location, collaborators                      )
        case let .setting(.state(to: s))    : Self(id, title, s    , dueDate, location, collaborators                      )
        case let .setting(.dueDate(to: d))  : Self(id, title, state, d      , location, collaborators                      )
        case let .setting(.location(to: l)) : Self(id, title, state, dueDate, l       , collaborators                      )
        case let .adding  (.collaborator(c)): Self(id, title, state, dueDate, location, collaborators + [c]                )
        case let .removing(.collaborator(c)): Self(id, title, state, dueDate, location, collaborators.filter{$0.id != c.id})
        }
    }
}   

extension TodoItem {
    enum State {
        case unfinished
        case inProgress
        case finished
    }
}

extension TodoItem {
    enum DueDate {
        case none
        case date(Date)
    }
}

enum Location {
    case unknown
    case coordinate(Coordinate)
    case address(Address)
}

struct Address {
    let street : String
    let city   : String
    let country: String
    let zipCode: String
}

struct Coordinate {
    let latitude : Double
    let longitude: Double
}

struct Collaborator {
    enum Change {
        case name(to:String)
    }
    let id  : UUID
    let name: String

    init(name: String) {
        self.init(UUID(), name)
    }
    private init (_ i: UUID, _ n: String) {
        id   = i
        name = n
    }

    func alter(_ c:Change) -> Self {
        switch c {
        case let .name(to:n): Self(id, n)
        }
    }
}

Using this it might look like:

let cal = Calendar.current
let tomorrowNoon = cal.date(byAdding: .hour, value: 12, to: cal.date(byAdding: .day, value: 1, to: cal.startOfDay(for: .now))!)!

let alice = Collaborator(name: "Alice")
let bob = Collaborator(name: "Bob")

let berlin = Location.coordinate(Coordinate(latitude: 52.520008, longitude: 13.404954))
let beerShop = Location.address(Address(street: "Kreuzbergstrasse 78", city: "Berlin", country: "Germany", zipCode: "10965"))

var buyBeer = TodoItem(title: "Buy beer")
buyBeer =
    buyBeer
        .alter(by: .setting(.title(to: "Buy beer — ASAP!")))
        .alter(by: .setting(.state(to: .inProgress)))
        .alter(by: .setting(.dueDate(to: .date(tomorrowNoon))))
        .alter(by: .setting(.location(to: beerShop)))
        .alter(by: .adding(.collaborator(alice)))

let buyChips = TodoItem(title: "Buy chips")
    .alter(by:
            .setting(.state(to: .inProgress)),
            .setting(.dueDate(to: .date(tomorrowNoon))),
            .adding (.collaborator(alice)),
            .adding (.collaborator(bob)),
            .setting(.location(to: berlin))
    )

The following example is an implementation of Conway’s Game of Life. This has significance as it proves the Turing completeness of Colibri.

Gosper’s glider gun

struct Life:Codable {
    enum Change {
        case process
        case pause, unpause
        case set (_Set); enum _Set {
            case cells([Cell])
        }
    }
    let paused             : Bool
    let step               : Int
    let size               : Int
    let stateForCoordiantes: [Life.Cell.Coordinate : Life.Cell.State] init(coordinates: [Cell.Coordinate]) {
        self.init(cells:coordinates.map { Cell(coordinate:$0) })
    }
    init(cells: [Cell]) {
        self.init(0,cells,false, 0)
    }
    func alter(_ cs: [Change] ) -> Self { cs.reduce(self) { $0.alter($1) } }
    func alter(_ cs: Change...) -> Self { cs.reduce(self) { $0.alter($1) } }
    func alter(_ c : Change   ) -> Self {
        if paused && !unpausing(c) { return self }
        switch c {
                                            //     |step|,|<----------------------- cells --------------------->|,paused,|<------- size -------->|
        case let .set(.cells(cells)): return .init(step+1,cells                                                  ,paused,stateForCoordiantes.count)
        case .pause                 : return .init(step+1,stateForCoordiantes.map{ Cell(coordinate:$0,state:$1) },  true,stateForCoordiantes.count)
        case .unpause               : return .init(step+1,stateForCoordiantes.map{ Cell(coordinate:$0,state:$1) }, false,stateForCoordiantes.count)
        case .process               : return alter(.set(.cells(applyRules())))
        }
    }
}

extension Life {
    struct Cell: Hashable, Equatable, Codable {
        init(coordinate: Coordinate, state:State = .alive) {
            self.coordinate = coordinate
            self.state = state
        }
        struct Coordinate: Equatable, Codable {
            let x, y: Int
        }
        enum State: Hashable, Codable {
            case alive, dead
        }
        let coordinate: Coordinate
        let state     : State
    }
}

private extension Life {
    init(_ step: Int,_ cells: [Cell] = [],_ paused:Bool,_ size:Int) {
        self.step                = step
        self.paused              = paused
        self.stateForCoordiantes = cells.reduce([:]) { var a = $0; a[$1.coordinate] = $1.state; return a }
        self.size                = size
    }
    func applyRules() -> [Life.Cell] {
        Array(Set(self.stateForCoordiantes.map { k,v in Cell(coordinate: k, state: v)}.flatMap { neighbors(for:$0) }))
            .compactMap {
                let neigbours = aliveNeighbors(for: $0)
                let isAlive:Bool
                switch (neigbours.count, $0.state) {
                case (0...1, .alive): isAlive = false
                case (2...3, .alive): isAlive = true
                case (4...8, _     ): isAlive = false
                case (3,      .dead): isAlive = true
                case (_,      _    ): isAlive = false
                }
                return isAlive ? .init(coordinate: .init(x: $0.coordinate.x, y: $0.coordinate.y), state:.alive) : nil
            }
    }
    func neighbors(for cell: Life.Cell) -> [Life.Cell] {
        aliveNeighbors(for: cell) + deadNeighbors(for: cell)
    }
    func aliveNeighbors(for cell: Life.Cell) -> [Life.Cell] {
        allNeigbourCoordinates(cell).map {
            Cell(coordinate: $0, state: stateForCoordiantes[$0] ?? .dead)
        }.filter { $0.state == .alive }
    }
    func allNeigbourCoordinates(_ cell: Life.Cell) -> [Life.Cell.Coordinate] {
        [
            .init(x:cell.coordinate.x-1, y:cell.coordinate.y-1),
            .init(x:cell.coordinate.x-1, y:cell.coordinate.y  ),
            .init(x:cell.coordinate.x-1, y:cell.coordinate.y+1),
            .init(x:cell.coordinate.x  , y:cell.coordinate.y-1),
            .init(x:cell.coordinate.x  , y:cell.coordinate.y+1),
            .init(x:cell.coordinate.x+1, y:cell.coordinate.y-1),
            .init(x:cell.coordinate.x+1, y:cell.coordinate.y  ),
            .init(x:cell.coordinate.x+1, y:cell.coordinate.y+1),
        ]
    }
    func deadNeighbors(for cell: Life.Cell) -> [Life.Cell] {
        Set(allNeigbourCoordinates(cell))
            .subtracting(aliveNeighbors(for:cell).map{ $0.coordinate })
            .map { Cell(coordinate:$0,state:.dead) }
    }
}
private func unpausing(_ c:Life.Change) -> Bool {
    switch c {
    case .unpause: return true
    default      : return false
    }
}
extension Life.Cell.Coordinate: Hashable {
    func hash(into hasher: inout Hasher) {
        hasher.combine(x)
        hasher.combine(y)
    }
}

You will find the project including a macOS UI on GitLab.

This example is Snake, which the older among us will most likely know from old Nokia phones.

Snake in action

struct Snake {
    enum Change {
        case move(Move); enum Move {
            case forward
            case right
            case left
        }
        case grow
    }
    enum Facing {
        case north
        case east
        case south
        case west
    }

    let head  : Coordinate
    let tail  : [Coordinate]
    let facing: Facing
    var body  : [Coordinate] { [head] + tail }

    init(head:Coordinate) {
        self.init(head, [], .north)
    }
    func alter(_ c:Change) -> Self {
        switch c {
        case let .move(d): move(d)
        case     .grow   : grow()
        }
    }
}

private extension Snake {
    init(_ h:Coordinate,_ t:[Coordinate],_ f:Facing) { head = h; tail = t; facing = f }
    func move(_ move:Change.Move) -> Self {
        var newTail: [Coordinate] { Array(body.prefix(tail.count)) }
        switch (facing, move) { //         |<-------------- head -------------->|  tail  |facing|
        case (.north,.forward): return Self(Coordinate(x:head.x    ,y:head.y - 1),newTail,.north)
        case (.east ,.forward): return Self(Coordinate(x:head.x + 1,y:head.y    ),newTail,.east )
        case (.south,.forward): return Self(Coordinate(x:head.x    ,y:head.y + 1),newTail,.south)
        case (.west ,.forward): return Self(Coordinate(x:head.x - 1,y:head.y    ),newTail,.west )
        case (.north,   .left): return Self(Coordinate(x:head.x - 1,y:head.y    ),newTail,.west )
        case (.east ,   .left): return Self(Coordinate(x:head.x    ,y:head.y - 1),newTail,.north)
        case (.south,   .left): return Self(Coordinate(x:head.x + 1,y:head.y    ),newTail,.east )
        case (.west ,   .left): return Self(Coordinate(x:head.x    ,y:head.y + 1),newTail,.south)
        case (.north,  .right): return Self(Coordinate(x:head.x + 1,y:head.y    ),newTail,.east )
        case (.east ,  .right): return Self(Coordinate(x:head.x    ,y:head.y + 1),newTail,.south)
        case (.south,  .right): return Self(Coordinate(x:head.x - 1,y:head.y    ),newTail,.west )
        case (.west ,  .right): return Self(Coordinate(x:head.x    ,y:head.y - 1),newTail,.north)
        }
    }
    func grow() -> Self {
        //  |head|<----------------- tail ----------------->|facing|
        Self(head,!tail.isEmpty ? tail+[tail.last!] : [head],facing)
    }
}

Snake's Change DSL encodes the instructions

• .move(.forward)
• .move(.right)
• .move(.left)
• .grow

In the move method all combinations of a direction instruction and the currently facing compass direction are mapped to new Snake instances with new head, new tail and the new compass direction.

grow method grows the snake by adding the last tail element.

You will find the code on GitLab.

So far we have seen rather simple DSLs, but there might be more complex ones. In my article Diplomacy in Declarative Swift I show how we can model instructions that follow English sentences quite closely:
.move(.army(of:.germany, from:bulgaria, to:constantinople))
Even non-coders can instantly understand, what is going on. And believe me: I tested this. I asked strangers in places like cafés if they could tell me, what is going on. Interestingly non-coders were faster answering it successfully, as programmers often first dove into discussions if this possibly was functioning code at all.

I have limited this article to examples concerning model types, but it is also possible to create whole architectures with Colibri. I have written several articles about it, with the most complete one being A New Coding Paradigm: Declarative Domain Programming. It contains an architecture inspired by Robert C. Martin’s Clean Architecture. It also shows how BDD and TDD can easily be handled.