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.

14 Comments

  1. 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 :)

  2. S.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?

  3. conal:

    Do you have the reasons why IO doesn’t meet those criteria written up somewhere?

    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 that IO has thousands of primitives (mostly generated by the foreign-function interface) and nondeterministic concurrency.

    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 …

    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.

    my apologies if these are recurring questions too :)

    No problem. I’m getting a sense of what questions to include in a FAQ. Thanks.

  4. conal:

    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?

    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.

  5. S.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.

  6. daryoush:

    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

  7. Magnus:

    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 :-)

  8. conal:

    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?

    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).

    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.

    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.

  9. conal:

    Nobody’s mentioned it, but isn’t this what Landin called “denotative”?

    Oh — I’d forgotten about Landin’s use of “denotative”. Thanks for the reminder.

    From section 8 of The Next 700 Programming Languages:

    The commonplace expressions of arithmetic and algebra have a certain simplicity that most communications to computers lack. In particular, (a) each expression has a nesting subexpression structure, (b) each subexpression denotes something (usually a number, truth value or numerical function), (c) the thing an expression denotes, i.e., its “value”, depends only on the values of its subexpressions, not on other properties of them.

    It is these properties, and crucially (c), that explains why such expressions are easier to construct and understand. Thus it is (c) that lies behind the evolutionary trend towards “bigger righthand sides” in place of strings of small, explicitly sequenced assignments and jumps. When faced with a new notation that borrows the functional appearance of everyday algebra, it is (c) that gives us a test for whether the notation is genuinely functional or merely masquerading.

    Then in section 9:

    An important distinction is the one between indicating what behavior, step-by-step, you want the machine to perform, and merely indicating what outcome you want. Put that way, the distinction will not stand up to close investigation. I suggest that the conditions (a-c) in Section 8 are a necessary part of “merely indicating what outcome you want.” The word “denotative” seems more appropriate than nonprocedural, declarative or functional. The antithesis of denotative is “imperative.” Effectively “denotative” means “can be mapped into ISWIM without using jumping or assignment,” given appropriate primitives.

    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.

  10. Conal:

    One could say that Haskell IO expressions “denote something” but we don’t quite know what ….

    Though I doubt that IO does denote anything, given the requirement of compositionality of semantics. Consider that IO includes 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.

  11. 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… :)

  12. Manuel Chakravarty:

    Vinod, some of it call it “purely functional programming”.

    Conal, nice observation about Landin. I have to say “denotative” is an appealing term.

  13. Andy Melnikov:

    Consider that IO includes exception-handling

    IO also includes concurrency, which is even more troublesome.

  14. Why 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 […]

Leave a comment