Is Haskell a purely functional language?
There is a lot of confusion about the meaning of “functional” and “declarative” as descriptions of programming languages and paradigms. For instance, Haskell is sometimes advertised as a “purely functional programming language” and other times as “the world’s finest imperative programming language”. I added some playful confusion (and clarity, I hope) with my post The C language is purely functional.
I still regularly hear people ask and disagree about whether Haskell’s monadic I/O is “functional”. I would say yes in one (technical) sense of “functional”. But not the same sense in which we say “functional programming has simple, precise semantics” or “functional programming has good compositional properties” or “functional programming is good for reasoning about”. Monadic I/O is a clever trick for encapsulating sequential, imperative computation, so that it can “do no evil” to the part that really does have precise semantics and good compositional properties.
It’s because of this confusion that I’ve started using the more specific term “denotational programming” in my blog subtitle and elsewhere, as an alternative to what I used to call “functional programming”. While there are other notions of “functional”, applicable even to monadic IO, I think “denotational” captures the fundamental and far-reaching benefits that we called “good for reasoning about” and “powerfully compositional”.
When I bash monadic I/O, my real complaint isn’t with the technical invention–which I like. Rather, I’m cranky about confusion and misleading communication, and about distraction from what we originally meant by “functional programming”–from what I call “denotational programming”.
I don’t mind that we haven’t yet been liberated from the von Neumann model. As long as remember we haven’t.
As long as we keep on searching.
Andrea Vezzosi:
Do you have the reasons why IO doesn’t meet those criteria written up somewhere? Currently we’ve this nice model of pure computations that we can see it’s easily composable, but it doesn’t capture a good deal of what we can do with computers, and then we’ve this hard to work with IO which can describe the rest. Now, one could think that the complexity of IO stems from what it describes, which would mean there’s no room for researching a nicer model. It’d be nice to see an analysis of IO that shows how the complexity arises from how it is formulated rather than what it describes.
Though even what we want to describe is ambiguous, do we want to describe interaction with the current OSes? or some other nicer model? In the latter case, can that model be implemented over current OSes, and will we be able to interoperate with programs written imperatively, or do we need our own separate world?
Though it seems that if we could answer these questions we’d have concluded the research. I guess i’m asking for a more precise formulation of what you’re aiming for.
my apologies if these are recurring questions too
5 January 2010, 5:27 pmS.J.:
Aren’t all programming languages denotational and it’s only the degree or expressiveness that differentiates one from the other? Isn’t functional programming a specialized subset of denotational semantics?
8 January 2010, 11:07 amconal:
See Backus’s Turing Award lecture, Can Programming Be Liberated from the von Neumann Style? A functional style and its algebra of programs.
I get the clearest understanding by considering the influence of denotational models on reasoning. My experience seems to show that when a data type (or a language) has a simple denotational model, that type is correspondingly easy to reason about, and when the denotational model rings true (compellingly captures the essence of what the type represents), then the programming interface will be correspondingly satisfying to work with.
Now consider the denotational model of Haskell
IO. Well, you’ll have difficulty doing so, since we don’t have a denotational model. Consider instead what such a model would be. Remember thatIOhas thousands of primitives (mostly generated by the foreign-function interface) and nondeterministic concurrency.I’ve noticed that some folks want programming models to serve the machine, by capturing what the machine can do. I’m more interested in machines as lenses for ideas, i.e., the role of the machine for me is to display ideas for me to observe. I want to express those ideas in a precise & simple way, thus the appeal of denotational design.
No problem. I’m getting a sense of what questions to include in a FAQ. Thanks.
8 January 2010, 1:03 pmconal:
When I talk about “denotational programming”, I mean an approach to programming, not a language property. So I’m having trouble relating to the question. In denotational programming, all types & operations have precise meanings, given in the style of denotational semantics.
8 January 2010, 1:14 pmS.J.:
My comment’s about using a broader term at the expense of losing specificity implied by functional programming. Surely denotational encompasses functional, but covers many other aspects as well. Perhaps that’s your intent.
8 January 2010, 9:06 pmdaryoush:
I am not sure I understand what this means:
“functional programming has simple, precise semantics” or “functional programming has good compositional properties” or “functional programming is good for reasoning about”.
What would Haskell’s monadic I/O look like if you had what you are thinking about functional? Can you give a few example of what you can’t defined precisely, what kind of compositional properties are missing, and/or an example of monadic IO program that you can’t reason about.
Thanks,
Daryoush
11 January 2010, 5:25 pmMagnus:
Nobody’s mentioned it, but isn’t this what Landin called “denotative”?
BTW, his paper on the next 700 programming languages reads in many ways like a description of Haskell
12 January 2010, 8:18 amconal:
To the Haskell programmer, it wouldn’t look like anything at all. In other words, the imperative computation would be hidden away in implementations of denotationally defined abstractions. Just as is the case now with imperative computations that implement function call and laziness (stack munging and thunk overwriting).
The early part of Backus’s “liberated” paper discusses these issues with imperative programming. Haskell IO programming is a way to generate imperative computations. Those computations involve system calls, side-effected variables, and loops, just as in Fortran. And they can contain semantically nondeterministic concurrency. Very difficult to reason about precisely.
12 January 2010, 11:25 amconal:
Oh — I’d forgotten about Landin’s use of “denotative”. Thanks for the reminder.
From section 8 of The Next 700 Programming Languages:
Then in section 9:
I think Landin does indeed mean what I mean. I’m uncertain, as his conditions (b) & (c) say that subexpressions “denote something”, but he doesn’t say that the something must be explicitly defined. One could say that Haskell IO expressions “denote something” but we don’t quite know what, but then how could we test the claim for validity? What I mean by “denotational programming” requires well-defined, precise and tractable denotations. Those denotations then serve as the basis for implementation correctness, documentation, and formal reasoning.
If I knew that Landin did indeed mean having a precise & tractable denotation, I’d happily adopt his “denotative” in place of my “denotational”. Hm.
12 January 2010, 11:52 amConal:
Though I doubt that
20 March 2010, 3:28 pmIOdoes denote anything, given the requirement of compositionality of semantics. Consider thatIOincludes exception-handling, which is sensitive to order-of-evaluation of pure (non-IO) expressions. Exception-handling thus extracts more meaning than exists out of pure sub-expressions, breaking compositionality.Vinod:
I think it is unfortunate that functional programming means what it means today
When I was a physics graduate student I always thought that functional programming meant programming with functions though I never took the meaning of the word “function” as in mathematics but as in Fortran 
I suppose the correct phrase should be “side effect free functional programming”
Oh well…
31 March 2010, 8:18 pmManuel Chakravarty:
Vinod, some of it call it “purely functional programming”.
Conal, nice observation about Landin. I have to say “denotative” is an appealing term.
31 July 2011, 4:23 pmAndy Melnikov:
IO also includes concurrency, which is even more troublesome.
18 November 2011, 2:50 amWhy are getArgs and getProgName IO actions? - Tech Forum Network:
[…] Don Stewart’s as the most simple and concise, but Conal’s (with its associated blog post) is definitely worth a […]
7 June 2013, 6:56 am