Can functional programming be liberated from the von Neumann paradigm?

This post describes an idea I’ve had in mind for years and have chatted about with friends but haven’t written down before.

Functional programmers used to worry about how to solve “the I/O problem”. Functional programming (FP) eschews any notion of side-effect or order of execution, and instead has an order-independent notion of evaluation. In contrast, input & output (I/O) seems to be an inherently effectful, ordered notion.

For a long time, I’ve been dissatisfied with the current Haskell solution to “the I/O problem”. Of course it’s very clever and effective. With “monadic IO” we can program both functionally and imperatively, and the imperative semantics doesn’t compromise the functional semantics.

I look at monadic IO not as any solution to functional I/O, but rather as a (clever) way not to bring I/O into the functional world. There’s a ton of confusion buzzing around monadic IO, so let me try to restate more carefully: “monadic IO” is a way to generate imperative computations (not just I/O) without having to say anything at all about the semantic content of those computations. Rather than retooling our mental habits completely away from the imperative model of computation, monadic IO is a way to hang onto these old mental habits, and use them in a hybrid functional/imperative programming style, in which the imperative doesn’t contaminate the functional, semantically.

John Backus offered us a gift and a blessing in his 1977 Turing Award lecture, Can Programming Be Liberated from the von Neumann Style? A functional style and its algebra of programs. He told us how the sequential/imperative model enslaves us in weak thoughts, inhibiting manageable scaling (sections 1 through 5.1). In the abstract, Backus says

Conventional programming languages are growing ever more enormous, but not stronger. Inherent defects at the most basic level cause them to be both fat and weak: their primitive word-at-a-time style of programming inherited from their common ancestor–the von Neumann computer, their close coupling of semantics to state transitions, their division of programming into a world of expressions and a world of statements, their inability to effectively use powerful combining forms for building new programs from existing ones, and their lack of useful mathematical properties for reasoning about programs.

As well, Backus showed one way to throw off the shackles of this mental and expressive slavery — how to liberate our notions of programming by leaving the von Newmann mental model behind.

Haskell is often described as a “purely functional programming language”, and in a technical sense it is. (In good company, too; see The C language is purely functional.) However, as commonly practiced, imperative computation still plays a significant role in most Haskell programs. Although monadic IO is wily enough to keep a good chunk of purity in our model, Haskell programmers still use the imperative model as well and therefore have to cope with the same fundamental difficulties that Backus told us about. In a sense, we’re essentially still programming in Fortran, with its mixture of statements and expressions (or, semantically, of commands and values). Don’t get me wrong; Haskell is a much better Fortran than the original. (If you have an urge to inform me how monadic IO works, re-read what I’m really saying. Honestly, I know.)

(Sadly, the very definition of “program” in Haskell requires that there be a main of type IO ()! Haskell programs thus cannot be purely functional (except technically), and so cannot be composed except very weakly, as Backus describes. For an alternative model, see Tangible Functional Programming: a modern marriage of usability and composability.)

In a sense, I see us as in a worse position than before. Since the adoption of monadic IO, it’s been less immediately apparent that we’re still enslaved, so there’s been much less activity in searching for the promised land that the prophet JB foretold. Our current home is not painful enough to goad us onward, as were continuation-based I/O and stream-based I/O. (See A History of Haskell, section 7.1.) Nor does it fully liberate us.

Since I/O is an intrisically sequential, effectful notion, and we need some way of doing input & output, perhaps the best we can do is what we’ve done with monadic I/O: support both imperative and functional programming and proctect the functional from the imperative.

Or can we do better?

Continue reading ‘Can functional programming be liberated from the von Neumann paradigm?’ »