Can functional programming be liberated from the von Neumann paradigm? (2010)


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?

In my recent post, Why program with continuous time?, I had suggested that the abstraction of continuous time is useful even if “in the end all streams are discrete”.
I advised designing APIs based on the principle that “programming is more about the middle than the end, i.e., more about composition than about output.”
As an example, I pointed out that we don’t represent numbers as strings even if “in the end”, numbers are output as strings, suggesting that the key reason to choose an abstraction other than strings is composability (here, arithmetic). The post gives a few other examples of this principle of designing an API for composition, not for input or output.

Roly Perera noted that

… you never really need to reach “the end”. (It really is all about composition.)

To extend an example in the previous post, after numbers, then strings, and then pixels, are phosphors the end?
(Sorry for the obsolete technology.)
After phosphors come photons.
After photons comes retina & optic nerve.
Then cognitive processing (and emotional and who-knows-what-else).
Then, via motor control, to mouse, keyboard, joystick etc.
Then machine operating system, and software again.
Round & round.
More importantly, our interactions with other wetware organisms and with our planet and cosmos, and so on.

Roly added:

What looks like imperative output can be just what you observe at the boundary between two subsystems.

Which is exactly how I look at imperative input/output.

Representation shifts often happen at programming interfaces.
Major interfaces in a whole system sometimes require a major representation shift, namely marshalling to and unmarshalling from serialized, memory-external representations.
For instance, conversion from strings to numbers on input to a computer or brain and conversion of numbers to strings on the way out.
Or replace strings with other rendered representations.
Another example: conversion from continuous time & space to discrete time & space (“sampling”) on input to a digital machine, and conversion from discrete time & space to continuous time & space (“reconstruction”) on the way from digital machine (computer, CD/DVD player) to a brain.

This perspective is what’s behind my confidence that we will someday really learn to look at whole systems in a consistently functional/denotational style (simple & precise semantics).
The imperative interfaces in today OSs and data-bases are troubling at first, and indeed I often hear people (even on #haskell) using these examples as demonstration that the imperative programming model is inescapable.
These examples don’t trouble me, however, because I see that we’ve already dealt with others of their kind.
Underneath the implementation of our current functional abstractions (numbers, strings, trees, functions, etc), there are imperative mechanisms, such as memory allocation & deallocation, stack frame modification, and thunk overwriting (to implement laziness).
Every one of these mechanisms can be used as evidence against the functional paradigm by someone who hasn’t yet realized how the mechanism can be shifted out of the role of a programming model notion and into the role of implementation of a programming model notion.
The new notion is more composable by virtue of being semantically simpler and mathematically more well-behaved.

Stack and register munging and jump/GOTO are implementations of the semantically simpler notion of function application.
(I mean “function” in the sense of math and of pure functional programming.) Moreover, stack & register munging is the input/output (IO) part of the implementation of function application.
Information goes out of one context and into another.
My vision of “solving the I/O problem” for functional programming is nothing like Haskell’s semantically imperative (non-)solution (caled “IO” in Haskell), but rather to continue shifting semantically imperative mechanisms out of the programming model and into the implementation of (semantically simple) function application.

How do we get from here (still stuck in the quagmire of imperative programming models) to there (simple semantics and consistently excellent composability)?
First, stop rehearsing the thinking that keeps us stuck.
When we keep telling ourselves and each other that imperative notions are inevitable, accompanying such statements with hand-waving arguments, we are weaving self-fulfilling prophecies.
A person convinced of (and perhaps ego-invested in) the nonexistence of new possibilities is a person actively resisting their opportunity to discover possibilities — too stuck in the obvious to discover new truths.

The significant problems of our time cannot be solved by the same level of thinking that created them. – Albert Einstein

They are ill discoverers that think there is no land, when they can see nothing but sea. – Francis Bacon

Hand-waving is an important factor in staying stuck in impossibility thinking, since rigorous argument uncovers unconscious limiting assumptions.
I’m just as happy if you are working on showing impossibility as discovering the possible, as long as you are rigorous and get rigorous peer review.
Otherwise, we all fall into the trap of self-deceit:

Nothing is easier than self-deceit. For what each man wishes, that he also believes to be true. – Demosthenes

If you wish to see the truth, then hold no opinion for or against – Osho (Rajneesh Chandra Mohan Jain)

The discovery of this reality is hindered rather than helped by belief, whether one believes in God or believes in atheism. We must make here a clear distinction between belief and faith, because, in general practice, belief has come to mean a state of mind which is almost the opposite of faith. Belief, as I use the word here, is the insistence that the truth is what one would “lief” or wish it to be. The believer will open his mind to the truth on the condition that it fits in with his preconceived ideas and wishes. Faith, on the other hand, is an unreserved opening of the mind to the truth, whatever it may turn out to be. Faith has no preconceptions; it is a plunge into the unknown. Belief clings, but faith lets go. In this sense of the word, faith is the essential virtue of science, and likewise of any religion that is not self-deception. – Alan Watts

In summary, I’m suggesting we take a fresh look at I/O and functional programming.
Instead of putting I/O into the functional programming model (as in continuation- and stream-based I/O), or adopting a hybrid functional/imperative model (as in monadic I/O), let’s explore how to move I/O entirely out of our programming model into the implementation of a denotationally simple model for whole systems.

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…

Read More

This site uses Akismet to reduce spam. Learn how your comment data is processed.