Three Threads

March 4, 2014

Three threads have been twisting in my mind lately.

I finally read Moseley’s and Marks’s “Out of the Tar Pit” this week. It’s been on my reading list for months (years?), but I’ve been so absorbed in learning, and doing, Cocoa programming for Mac and iOS that I’ve neglected broader topics. Moseley and Marks take on the perennial issue of complexity in software systems. Specifically, they tackle the complexity of understanding, developing, and maintaining software systems as opposed to computational complexity. While they spread the blame for complexity around, mutable state takes the bulk of their scorn. I have some issues with their proposed solution—functional relational programming—in that they discount the complexity of building user interfaces for rich productivity apps like we craft at Omni. That said, I share their concern about mutable state.

Also sitting in my stack of reading material is Okasaki’s Purely Functional Data Structures. The book is a readable survey of techniques for building data structures for functional languages. Most other data structure texts, while claiming to be language agnostic, assume that you’re working in an imperative programming language. Okasaki presents a variety of data structures suitable for (and efficient in) purely functional languages. The book’s examples are in Standard ML with an appendix giving versions in Haskell.

The third thread is the intersection of object-oriented programming and functional programming. William Cook’s OOPSLA 2009 paper, “On Understanding Data Abstraction, Revisited”, reminded me that there’s no reason for the traditional coupling of object-oriented programming languages and mutable state. We can encapsulate data and operations in objects while maintaining a purely functional style. In some sense this is just a higher-order form of functional programming. Instead of passing a single function as a first class value, we pass an object which is a set of functions. As Cook writes:

“Object interfaces are essentially higher-order types, in the same sense that passing functions as values is higher-order. Any time an object is passed as a value, or returned as a value, the object-oriented program is passing functions as values and returning functions as values. The fact that the functions are collected into records and called methods is irrelevant. As a result, the typical object-oriented program makes far more use of higher-order values than many functional programs.”

After discussing the causes of complexity and our current approaches to (attempting to) tame it, they advocate for functional reactive programming, first proposed by Elliott and Hudak, as the way out.

Three threads: mutable state as the source of complexity, functional data structures, and objects as higher order functional values. A sensible way to tie these threads together might be to dive into functional reactive programming. ReactiveCocoa is the likely entry point from here. At some point I’ll likely do that, but I have a much more ill-conceived project in mind now.

I’m going to work through Purely Functional Data Structures, implementing all the data structures and exercises in a functional subset of Objective-C. I’ll write about the results here as I go. I’m interested in discovering what patterns emerge along the way. I hope that somewhere down the line is a development style that fuses functional models and object-oriented views, with functional reactive programming to tie them together. This might prove to be a terrible idea, but I’m looking forward to learning whether that’s true.