The C language is purely functional

There has been a scurry of reaction on twitter and reddit to Robert Fischer’s post saying that Scala is Not a Functional Programming Language. James Iry responded by saying that analogous reasoning leads to the conclusion that Erlang is Not Functional

My first inclination was to suggest that Haskell, as commonly practiced (with monadic IO), is not a functional language either. Instead, I’m going to explain how it is that the C language is purely functional.

The story of C

First, let me make that claim more precise. What I really mean is that almost everyone who “writes C programs” is really programming in a purely functional language. Modulo some minor historical accidents.

“C programmers” really program not in C, but in the purely functional language cpp (the “C Preprocessor”). As with any purely functional language, cpp consists only of (nestable) expressions, not statements. Now here’s the clever part: when evaluated (not executed), a cpp expression yields a (pure) value of type C, which is an ADT (abstract data type) that represents imperative programs. That value of type C is then executed (not evaluated) by the cpp language’s RTS (run-time system). As a clever optimization, cpp’s RTS actually includes a code generator, considerably improving performance over more naïve implementations of the C abstract data type.

(So now you can see that, “C programmer” is almost always a misnomer when applied to a person. Instead people are cpp programmers, and cpp programs are the real C programmers (producers of C). I don’t think I can buck this misnomer, so I’ll stay with the herd and use “C programming” to mean cpp programming.)

In this way, the geniuses Brian Kernighan and Dennis Ritchie applied monads (from category theory) to programming language design considerably before the work of Moggi and Wadler. (Even earlier examples of this idea can be found, so I’m taking liberty with history, choosing to give K&R credit for the sake of this post.)

Now along the way, some mistakes were made that tarnished the theoretical beauty of cpp+C:

  • Although cpp is in spirit purely functional, pragmatists insisted on the unnecessary and theoretically awkward construct #undef, which allows a single name to be re-defined.

  • Scoping rules are not as clean as, say, the lambda calculus or Scheme, (But hey — even John McCarthy got scoping wrong.)

  • The C ADT is implemented simply as String (or char *, for you type theorists, using a notation from Kleene), and the representation is exposed rather than hidden, so that cpp programs operate directly on strings. The wisdom of data abstraction caught on later.

Fortunately for purists, the relatively obscure programming language Haskell restored the original untarnished beauty of K&R’s vision by fixing these defects. The type system was modernized, scoping rules improved, and the C type (renamed to “IO“, to avoid expensive legal battles) made abstract.

(Admittedly, Haskell also had some shameful pre-teen influences from hooligans like Church, Curry, Landin, and Milner, before it settled into its true cpp+C nature, under the guiding influence of Wadler (under the influence of Moggi).)

What about Haskell?

Which leads to the question: is Haskell+IO a purely functional programming language?

Sure it is, even as much as its predecessor C (more precisely, cpp+C).

Some who ought to know better would claim that Haskell+IO is only technically pure. (See claims and follow-up discussion, in response to a remark from James Iry.)

I must then respond that, in that case, even C programming is only technically pure.

Which is absurd.

43 Comments

  1. Liyang HU:

    I like your reasoning, and would like to subscribe to your newsletter.

    Thank you, this post made me smile. /Liyang

  2. Christoph:

    There are C statements, that are not expressions. E.g. you can not write (pseudonotation)

    a = if b expr1 else expr2

    (ok, there is ?:)

    or

    a = do {…} while(expr);

    The same for while(){} and blocks {}.

  3. Jesse Rusak:

    Brilliant. This is exactly what I wanted to point out, but written with hilarious side effects.

  4. loupgaroublond:

    I’ve left a response on my blog, comparing Makefiles to functional languages as well. http://loupgaroublond.blogspot.com/2009/05/what-are-functional-languages.html

  5. james iry:

    Oddly enough, even though you are going for absurdity, what you say here leads to practical results. For instance what you are describing here is a transformation from one language to another. That transformation is a pure function. And indeed, it turns out that functional programming is very good for writing such transformers. We frequently call them compilers.

    I hear what you are saying, Conal. I even agreed with it in the comments. The semantics of the IO DSL are not pure. Fine, agreed 100%. But in Haskell ‘print “hello”‘ does not print, it returns a what a more imperative programmer might call a “callback” that will print if pushed out the door to be called. Haskell newbies who don’t understand that can be surprised by that behavior if they take the IO DSL too literally, and experienced Haskell programmers can use that fact to their advantage.

    I don’t see anything wrong with explaining all the above to Haskell newbies. Why can’t we explain IO at two levels of abstraction? One level is the level of the Haskell language and the other is the level of the IO DSL?

  6. Jonathan Allen:

    Well done. I was looking for something that demonstrated how crazy that whole evaluation/execution thing was.

  7. j willson:

    i dont understand

  8. Matt M:

    I think “purely functional” is best used as a modifier for a semantics. Haskell is frequently interpreted under a purely functional semantics in which programs represent either primitive values or functions on those values (or types or type classes, etc – I’m not going to bother trying to make this precise). While there is an equivalent purely functional semantics for C (heap passing style for example), people generally don’t consider that interpretation.

  9. conal:

    There are C statements, that are not expressions. E.g. you can not write (pseudonotation) […]

    Hi Cristoph,

    Please try on this rewrite:

    There are cpp expressions that evaluate to C “statements”, that are not C “expressions.”

    Do you see the difference?

    The C monad does indeed consist of values that could be called “statements”, if that monad were taken to be a programming language rather than a data type. While I’m sympathetic with using the term “statement” in this way, I’ve also seen rampant confusion when people confuse these two “language” layers in Haskell (where the C monad is cleaned up a little and called “IO“).

    A lot of C programmers have this confusion, because they learned an imperative programming language (e.g., Fortran or Pascal) before they were exposed to the purely functional language cpp+C, or because they were taught cpp+C by someone who’d previously used an imperative language (or who was taught by …). Another source of confusion has been the sloppy practice of abbreviating “cpp+C” as “C”. In writing “The C Programming Language”, perhaps Kernighan and Ritchie never anticipated that anyone would contemplate actually programming in the C monad directly, and so didn’t think confusion would result from the Zen practice (popularized by monks at Bell Labs) of shortening names to as few characters as possible. My personal theory, borne of deep respect, is that they knew full well what confusion would result and chose to allow (even encourage) it. When a C practitioner suddenly groks the purely functional monadic essence of their tool, the force of shock is so great that it may catapult him/her into enlightenment.

    When C programmers don’t reach enlightenment before picking up Haskell, they are likely to carry the same confusion into Haskell programming, e.g., missing the distinction between evaluation and execution.

    Worse yet, they might not realize that Haskell is a much more powerful purely functional language than their previous one (cpp), and so think that one cannot write useful, purely functional programs without the help of an imperative crutch like IO or C.

  10. sclv:

    I’d agree that there’s a “functional” subset of c by this description, and the point on imperative code being imperative code is well taken. But there’s also a nonfunctional c — i.e. (sideeffectingfunc() / sideffectingfunctwo(()). There’s no simple way to separate the potentially purely function subset of c from the whole thing, while the IO monad at least lets us describe Haskell without IO. Although Haskell without IO can be written in an imperative style too, if one uses a state monad for teletype and storage… So maybe what we should be saying is that being functional isn’t a property of a language, but a way of being in a language, and a language is functional to the extent that it helps programmers be functional.

  11. conal:

    James: I like your explanation very much. It makes a distinction that is very important in theory and practice. As much as people program insist on using IO (and therefore surrender semantic clarity and tractability), I’d also like them to understand both the functional perspective (evaluation of expressions) and the imperative perspective (execution of commands, i.e., values of type IO).

    So your distinction helps one skillfully carry imperative thinking into Haskell. That’s the whole purpose of the IO monad, which packages up imperative programming, retaining its basic semantic flaws. John Backus described those flaws in his Turing Award paper Can Programming Be Liberated from the von Neumann Style? A functional style and its algebra of programs.

    My personal preference is to join Backus in leaving imperative thinking behind, which is why I work on semantically precise & tractable alternatives to IO.

  12. Yaakov M. Nemoy: What are functional languages? | Techie News:

    […] Conal Elliott wrote on his blog that C is really a pure functional language called cpp that can be reduced to a monadic construct […]

  13. conal:

    From the #haskell IRC:

    <Saizan> conal: the monad analogy doesn't quite hold, since CPP macros can't create
             new C values at runtime

    Thanks for catching my sloppiness. An analogy holds, but I didn’t state it accurately.

    Haskell+IO has a monadic structure where cpp+C has a more elegant and general basis, namely the monoid. In other words, the C monoid was succeeded by the IO monad. Although monad is less simple/elegant than monoid, it gives a very powerful advantage, as Saizan pointed out.

  14. conal:

    Haskell is frequently interpreted under a purely functional semantics […]. While there is an equivalent purely functional semantics for C (heap passing style for example), people generally don’t consider that interpretation.

    Hi Matt,

    I think you’re comparing the semantics of the (imperative) C monoid with the (functional) Haskell language. I suggest instead relating the functional cpp language to the functional Haskell language, and relating the imperative C monoid to the imperative IO monad.

    As James Iry pointed out for Haskell, the C type has both a functional semantics as well (very different heap passing etc), namely as as strings, using string concatenation.

  15. conal:

    Well done. I was looking for something that demonstrated how crazy that whole evaluation/execution thing was.

    “And those who were seen dancing were thought to be insane by those who could not hear the music.” – Friedrich Wilhelm Nietzsche

  16. conal:

    sclv wrote:

    I’d agree that there’s a “functional” subset of c by this description, […]

    I’d rather you didn’t “agree” with me, since that’s not at all what I was trying to convey. Rather, the C monoid has imperative semantics, and its functional host language cpp has purely functional semantics (except some goofs like #undef).

    There’s no simple way to separate the potentially purely function subset of c from the whole thing, while the IO monad at least lets us describe Haskell without IO.

    Again, we’re talking on different levels. I’d say that there a very simple and bombproof way to separate pure from imperative in cpp+C: cpp is entirely pure, while C is not. Exactly the same situation holds for Haskell+IO: Haskell is entirely pure, while IO is not.

  17. Matt M:

    Hi Conal,

    I more or less ignored the C preprocessor, as I see it as a non-sequitur. You can describe the semantics of the preprocessor in simple functional terms, but as soon as you move to describe the semantics of C proper, you either have to introduce some heap-passing denotation or (much more commonly) give an imperative operational semantics. The situation with Haskell is not analogous, because even if you stop cold before assigning any operational meaning to values in the IO monad, you’ve still described a huge and interesting subset of Haskell. In fact (which is a point I was trying to make with my last post), it’s common to think of things this way, with values in the IO monad denoting mere instructions for some abstract machine with no further meaning. I would say such a semantics is purely functional and is fairly described as “Haskell.”

  18. conal:

    Hi Matt,

    I don’t think we’re disagreeing about much more than what to discuss. Since the discussion is taking place on this blog post thread, I’ll (mostly) stick to the topic of the post.

    I more or less ignored the C preprocessor, as I see it as a non-sequitur.

    Perhaps only if you miss the point of the post, or want it to be something other than what it is.

    You can describe the semantics of the preprocessor in simple functional terms, but as soon as you move to describe the semantics of C proper, you either have to introduce some heap-passing denotation or (much more commonly) give an imperative operational semantics.

    The same is true of Haskell: describing the semantics of IO requires very different machinery from its semantically simpler functional host (generator) language.

    The situation with Haskell is not analogous, because even if you stop cold before assigning any operational meaning to values in the IO monad, you’ve still described a huge and interesting subset of Haskell.

    The difference I see here is that Haskell is much richer, more well structured, and more powerful than cpp. So much so that one can do lots of cool stuff without bringing in the imperative crutch (IO) at all. In contrast, cpp is so weak a (functional) programming language that most of the real work is relegated to the supporting imperative monoid (i.e., C). So I’d say the situation is analogous. I also think the differences are hugely important, as I believe you do.

    Sadly–and here is the real intent behind my post–many Haskell programmers believe that IO is necessary to do “real programming”, and they use Haskell as if it were C (relegating lots of work to IO). In other words, monadic IO has proved to be such a comfortable “solution” to I/O in a functional language, that very few folks are still searching for a genuinely (not merely technically) functional solution. Before monadic IO, there was a lot of vibrant and imaginative work on functional I/O. It hadn’t arrived yet, but was still in touch with the Spirit of functional programming. With the invention and acceptance of monadic imperative programming, it’s like the Haskell community wandered into an opium den and are still lying there in a fog.

    Okay, I may be exaggerating a bit. Some are in rehab, and some “didn’t inhale”.

    By relating Haskell+IO to cpp+C, I’m not trying to lower the former or elevate the latter. Instead, I’m trying to waken functional programmers out of the opium fog and remind them how fun and creative genuinely functional programming can be.

  19. Matt M:

    Hi Conal,

    I think we’re converging.

    I more or less ignored the C preprocessor, as I see it as a non-sequitur.

    Perhaps only if you miss the point of the post, or want it to be something other than what it is.

    Well, I think I got the point of the post, and I still see it as non-sequitur. What if I run the C compiler with the preprocessor disabled? Is it still a pure functional language? I guess you could argue it is, with an empty set of denoted functions and a program denoting a single string literal. Since such a trivial “identity map” semantics is as much a purely functional language as the C preprocessor (and only slightly more trivially so), I see the preprocessor as non-sequitur.

    IMO the target of your objections should be semantic complexity, not impurity. It is possible to translate a C program (that doesn’t do IO) into a Haskell program in heap passing style (wrapped up in a monad or not) such that it is pure, but every bit as complex as the original. It seems best to me to let “purely functional” refer to languages where the objects of discourse are immutable values, and let how to best structure state and side-effects be a separate debate.

  20. Cale:

    Though I haven’t read either of the two articles this post is based on, I sort of have the feeling that the analogy is somewhat disingenuous. While the things you are saying are to some extent true, they are exactly the sort of thing likely to be misinterpreted by those who don’t already know the sense in which they are true.

    It’s possible that your goal is to be satirical though, and if that’s the case, then great. :)

    I’m sure that you also realise the sense in which the separation of concerns between CPP and C is very different from the separation of concerns between the pure fragment of Haskell and IO.

    Most people do not write the computational part of their program in CPP and do only input and output in C. They more or less can’t, because there’s no (convenient) way for the resulting C program to form new CPP computations and evaluate them to determine how it should proceed, and even if they could, they generally would not because CPP is too inexpressive.

    Moreover, the algebraic properties which IO actions already satisfy are actually quite strong. When we have a term like x >>= f, its imperative semantics can be constructed from the semantics of x and f in a uniform way. It’s true that the things we can say about it are not as strong as would be ideal, sure, but it’s in a completely different realm from what one can say about concatenation of strings which represent parts of C programs. Sure, strings under concatenation form a monoid, but it’s a monoid which reflects essentially none of its structure into the semantics of the resulting programs. In fact, even syntactic correctness is not guaranteed by CPP, whereas if a Haskell expression for an IO term can be evaluated, it is at least type correct and can also be executed (even if it doesn’t end up doing what you wanted it to do).

    The real point though, is that the evaluation of Haskell expressions, something which is entirely pure, can be used to do most of the computational legwork. Hence, even if the execution of the IO fragment of the program is perhaps still harder to check than we might like, it’s much smaller and simpler than it would otherwise be, the better part of it having been shifted into a language which is actually purely functional.

    The extent to which this is the case is something which can probably only be properly conveyed by reading and writing Haskell programs, so in the company of non-Haskell-programmers, it’s perhaps easy to be misunderstood. Especially so if you start explaining it by relation to CPP and C.

    I understand and sympathise with your concern (to some extent) that I/O should satisfy stronger algebraic laws and be easier to reason about. However, I’m not sure it’s worth misrepresenting the progress that’s already been made.

  21. conal:

    Cale wrote:

    Though I haven’t read either of the two articles this post is based on, I sort of have the feeling that the analogy is somewhat disingenuous. While the things you are saying are to some extent true, they are exactly the sort of thing likely to be misinterpreted by those who don’t already know the sense in which they are true.

    Somewhat disingenuous”? You’re too generous!

    I see what you mean about my post misleading some folks. There’s already a lot of confusion, and I’ve added some.

    It’s possible that your goal is to be satirical though, and if that’s the case, then great. :)

    Indeed satire is my goal, as a poke at the popular description of Haskell as a “purely functional programming language”, even when common practice often relies crucially on imperative semantics (IO).

    My worry is that as much as we believe we’re programming functionally, we won’t be trying to figure out how to program functionally. That’s what I meant in a comment above about the opium den.

    I’m sure that you also realise the sense in which the separation of concerns between CPP and C is very different from the separation of concerns between the pure fragment of Haskell and IO.

    Most people do not write the computational part of their program in CPP and do only input and output in C. They more or less can’t, because there’s no (convenient) way for the resulting C program to form new CPP computations and evaluate them to determine how it should proceed, and even if they could, they generally would not because CPP is too inexpressive.

    Moreover, the algebraic properties which IO actions already satisfy are actually quite strong. When we have a term like x >>= f, its imperative semantics can be constructed from the semantics of x and f in a uniform way. It’s true that the things we can say about it are not as strong as would be ideal, sure, but it’s in a completely different realm from what one can say about concatenation of strings which represent parts of C programs. Sure, strings under concatenation form a monoid, but it’s a monoid which reflects essentially none of its structure into the semantics of the resulting programs. In fact, even syntactic correctness is not guaranteed by CPP, whereas if a Haskell expression for an IO term can be evaluated, it is at least type correct and can also be executed (even if it doesn’t end up doing what you wanted it to do).

    The real point though, is that the evaluation of Haskell expressions, something which is entirely pure, can be used to do most of the computational legwork. Hence, even if the execution of the IO fragment of the program is perhaps still harder to check than we might like, it’s much smaller and simpler than it would otherwise be, the better part of it having been shifted into a language which is actually purely functional.

    I agree on almost all points. I had not gone into how it is that Haskell is a better C (or as Simon PJ said, “the world’s finest imperative programming language”). Thanks for doing so.

    My “almost” qualifier refers to this bit:

    the algebraic properties which IO actions already satisfy are actually quite strong.

    Which algebraic properties do you mean? The monadic laws? They always strike me as very weak.

    And this bit:

    When we have a term like x >>= f, its imperative semantics can be constructed from the semantics of x and f in a uniform way.

    Would you elaborate on what “uniform way” you have in mind? I don’t know of a way to give nontrivial semantics to (>>=) that isn’t type-specific (in this case, IO-specific).

    The extent to which this is the case is something which can probably only be properly conveyed by reading and writing Haskell programs, so in the company of non-Haskell-programmers, it’s perhaps easy to be misunderstood. Especially so if you start explaining it by relation to CPP and C.

    Thanks for saying so. Caveat lector!

    I understand and sympathise with your concern (to some extent) that I/O should satisfy stronger algebraic laws and be easier to reason about. However, I’m not sure it’s worth misrepresenting the progress that’s already been made.

    Thanks. I do indeed bad-mouth Haskell IO, because I want people to re-imagine life without it, as we used to do. I want us to get back to simple functional semantics and not be satisfied with merely functional packaging around imperative semantics. And in my zeal I sometimes contribute more chaos. Hopefully people who read my post will read your balancing comments as well.

  22. conal:

    Well, I think I got the point of the post, and I still see it as non-sequitur.

    Ouch! Hey, Matt — words hurt. How about saying that my post is “differently-sequitured”? ;)

    After all, there are many perspectives to sample. I’m aware than I’m offering an unusual one. If I were rehashing one of the already-popular perspectives, I wouldn’t have taken the time to write a post.

    What if I run the C compiler with the preprocessor disabled? […]

    Yet again, you’re departing from the context of my post, which is “cpp+C”. I don’t see your remarks as invalid; just off the topic of this post, and perhaps another venue would happily offer them more space for discussion.

    IMO the target of your objections should be semantic complexity, not impurity.

    Semantic complexity is exactly the heart of my objections. I’ve raised that issue in a variety of ways, trying to reach various ears.

    Watch the “should”s, would you? I’m getting the impression that you believe there’s one right way about things like what to talk about and how. Just an FYI on the impression.

    It is possible to translate a C program (that doesn’t do IO) into a Haskell program in heap passing style (wrapped up in a monad or not) such that it is pure, but every bit as complex as the original.

    I agree. Sounds like a good topic for a (different) blog post. Go for it!

    It seems best to me to let “purely functional” refer to languages where the objects of discourse are immutable values, and let how to best structure state and side-effects be a separate debate.

    “Best”. Sigh. I hope people will explore a variety of ways to discuss these issues, including the one you suggested.

  23. Cale:

    When I was speaking of the semantics of >>= I had intended it to be IO-specific. I don’t think it’s possible to give a particularly meaningful semantics to all monads at once.

    The details of how the semantics of x >>= f depends on that of x and f will depend on the precise imperative semantics you choose, but more or less consists of the fact that

    • if the execution of x results in changing the environment from S to S’ with some effects E resulting in v
    • and the execution of f v results in changing the environment from S’ to S” with some effects E’ resulting in w
    • then the execution of x >>= f results in changing the environment from S to S” with effects being the sequential composition of E and E’ resulting in w.

    This is somewhat trivial, perhaps, but it’s more than string concatenation of random fragments of C programs gives you.

    There really are algebraic laws satisfied by IO programs other than the monad laws. One can write down laws regarding exceptions, regarding how terminal I/O works, the ways in which concurrent programs are nondeterministic (the STM paper gives a semantics for STM transactions and their interleaving in IO), and various other things.

    For a perhaps overly simplistic example, we have that:

    putStr x >> putStr y = putStr (x ++ y)

    and this in turn could be proved from the definition of putStr and (++) and properties about how putChar works and the semantic rule for (>>) (which is similar to/derivable from the one I gave for >>= above).

    Another simple one is that effectively:

    forkIO x >> forkIO y = forkIO y >> forkIO x

    because of the necessary nondeterminism of the semantics of concurrent programs.

    The more laws that our programs satisfy, and the simpler those laws are, the easier it is to comprehend the meaning of our programs, to transform them, and to ensure that they’re what we intended.

    It is indeed hard to construct a complete model in which algebraic properties that IO programs have can completely characterise their behaviour. Nonetheless, they still satisfy some algebraic properties, and can be reasoned about to some extent.

  24. conal:

    There is quite a bit of discussion of this post on reddit as well.

  25. Matt M:

    Hi Conal,

    I’m not going to respond to your reprimands other than to say I’ve followed and respect your work and apologize if my comments have come off as too abrasive.

    Ouch! Hey, Matt — words hurt. How about saying that my post is “differently-sequitured”?

    Note the context: I didn’t say your post was non-sequitur, only that the “C preprocessor is a functional language” part of the argument was. And then I gave a supporting argument of this fact: you can replace the C preprocessor with the identity map (considered a “language”) and the rest of your argument still goes through.

    RE: the target of your objections should be semantic complexity, not impurity.

    My objection here is purely definitional: I don’t think calling Haskell + IO “impure” fits with what I consider “purely functional” to mean. You jump from considering a single value in IO as an imperative program (which is fair, if slightly dubious considering it’s not text but a potentially infinite function chain) to calling Haskell + IO imperative. I don’t agree with that jump, but think the substance of your argument is right on.

  26. Ryan Ingram:

    The C ADT is implemented simply as String (or char *, for you type theorists, using a notation from Kleene )

    This is an amazing bit of wordplay. I love the misuse of “char *”

  27. conal:

    Thanks, Matt. As for “non-sequitur”, “should”, and “best”: particular hot buttons of mine. Hence my reaction. Some explanation at Fostering creativity by relinquishing the obvious.

    Thanks for the encouraging comments. Regards, – Conal

  28. conal:

    Thanks, Ryan!

    The (imagined) C/Kleene connection had never occurred to me until a moment before I typed those words. Now that it has, I can’t help but wonder.

  29. sclv:

    Ah, I didn’t quite understand your description of cpp before… I had imagined it as something closer to, e.g. Lennart’s cmonad in haskell, rather than getting the point about monoids. Now it becomes clear. Nonetheless, I think the point about how easy it is to write imperative Haskell with no IO is also worth considering.

  30. Isaac Dupree:

    Haskell can be distinguished by how many of its modules/libraries/files are “completely useless”, incapable of doing any IO whatsoever when you look at all the types of the functions they export! In cpp+C, perhaps only the Boost Preprocessor Library deserves this honor. (In the more usual analogy where C is the language, there are some fairly-“useless” C libraries: you can tell once you look at their full implementations: but they’re not as common, nor as often revered, as the multitudes of do-nothing libraries in Haskell are! :-)

  31. Eyal Lotem:

    Interesting perspective!

    I think people like to celebrate Haskell’s power in the pure side of things, and its ability to combine imperative programs in powerful ways, and like to call it “pure functionality” when it is in fact something else.

    I totally sympathize with the excitement about Haskell’s ability to redefine the semantics of return and (>>=) and thus change/enhance the semantics of the language a program is written in (and not at the syntactic level, as Lisp does, but the semantic level, which I see as far more powerful. AFAIK you cannot implement continuations as a lisp macro).

    This ability allows defining things like continuations, exceptions, global environments, etc to be added to the language as libraries, and can be mixed and matched into existing code without breaking it (Assuming it uses the proper abstractions).

    Instead of calling this “purely functional”, we should figure out a name that conveys the true meaning:

    A) Powerful (turing-complete), expressive (Haskell’s niceness as a language) and interlaced (IO actions are allowed to depend on the purely functional side’s results, and vice versa) handling of IO actions as first-class values

    B) Ability to enhance the language: defining new loops, continuations, and stuff other languages are made of, are just libraries in Haskell.

  32. Cale:

    Eyal Lotem: For what it’s worth, I’m pretty sure you could implement continuations in lisp in a way roughly equivalent to the way we do it in Haskell, by defining the appropriate return, bind, and callCC. They’re just ordinary functions. You could also implement a macro for do-notation. However, doing it in such a way that the benefit of recognising it as a monad becomes apparent without making the notation completely inconvenient to use is a bigger trick. The benefit of recognising it as a monad in Haskell comes from the fact that all the functions which are polymorphic and work in all monads come for free as a result. Lisp doesn’t have the equivalent of typeclasses — it’s usually not even statically typechecked — so the kind of polymorphism needed is a bit cumbersome to express. (You need to do something like passing implementations of return and bind around as parameters. It’s possible that macros could alleviate some of that pain.)

  33. The Real Adam – Shippin’ ain’t easy:

    […] because you can: living frugally, JavaScript pixel art and hand-built microprocessors. Also, C as a functional language is nicer to think about than I’d first thought. If you ever get bored, check out the C output […]

  34. Helltime for June 1 « I Built His Cage:

    […] Conal Elliott hilariously writes how C is a purely-functional language. Definitely worth the read. When you come back here, remember that, just like in Smalltalk […]

  35. C is functional, Erlang and Scala are not? « fnpl:

    […] that can be browsed beginning at Conal Elliott’s brilliant and hilarious post explaining how The C language is purely functional. (You can follow the links to other parts of the discussion after you stop […]

  36. Conal Elliott » Blog Archive » Can functional programming be liberated from the von Neumann paradigm?:

    […] 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 (IO) still plays a significant role in […]

  37. Conal Elliott » Blog Archive » 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. […]

  38. Raoul Duke:

    Conal, where would I read up more on how we’d get rid of the imperative stuff entirely, and go with purely functional, and still have terminal interaction? I’m not yet sure what to use for a google search to find out :-) Thank you.

  39. Norman Ramsey:

    As Simon PJ said in an invited talk in 2003, Haskell is the world’s finest imperative language…

  40. “The C language is purely functional” « Nicholas Wilson:

    […] with an interest in computing theory, functional linguistics, or computational logic needs to read this. Perhaps it was famous and I had not found it before, but it is […]

  41. Conal Elliott » Blog Archive » Circuits as a bicartesian closed category:

    […] programming languages. In functional languages (or even semi-functional ones like Fortran, ML, and Haskell+IO), we answer the connectivity/composition questions by nesting function applications. Overall inputs […]

  42. David Peklak:

    So is Java is purely functional language that yields a pure value of type “Java byte-code”?

  43. conal:

    Perhaps from an implementator’s perspective, in contrast with Haskell+IO and CPP+C, where the programming model itself is a functional language evaluating to an imperative computation.

Leave a comment