The C language is purely functional (2009) | Hacker News Reader

The C language is purely functional (2009)

conal.net

78 pointsdbaupp19 comments

For some context, conal did the pioneering work on "classic" Functional Reactive Programming with Hudak, before the Haskell language had moved to monadic IO.

Originally, IO in Haskell was done based on streams as in Miranda from which it was inspired. A program is then a transformation on a stream of operating system events into a stream of operating system commands, both represented as data. That's pretty cool, because it makes it easy to write your program and then mock the operating system rather than actually touching the real world. The closest we have to this now is the "interact" function, which allows you to model your IO as a transformation of a stdin stream to a stdout stream.

Conal isn't much convinced that monadic IO was the best solution to the IO problem. The idea that monadic IO is a "pure" or "denotational" way to interact with the real world is arguably pretty weak, and that's the point of conal's post here: if you take the idea to its logical conclusion, we might end up just concluding that cpp is pure and denotational.

Instead, conal has worked on FRP approaches to interacting with the real world which are pure and have a very denotational feel to them: you're just writing down functions from time and a time-stamped stream of events. I still hold out enormous hope for this approach, but I'm not placing any bets on it.

I knew there was a 'pre-monad IO period', but I never knew exactly what that was. I've been interested in FRP for a while, but never drew the connections. Thanks for this comment!

Link to Google Cache for those who can't read the article:

http://webcache.googleusercontent.com/search?q=cache:J5AGFg1...

This is an extreme exaggeration, but it illustrates the point that a C programmer writes some source code that produces effects only at runtime and the compiler may be thought of as a pure function (though, with a bit of external state, but that is manageable in Haskell too).

The point is, it is the runtime system that produces the side effects, just as Haskell RTS does; the only difference is that Haskell annotates effects with its type system.

On the other hand, it completely blurs the line between "pure code" and "effectful code". Though the definition of "pure code" is rather tricky (we used to it in the Haskell meaning, with memory management completely abstracted away and explicit signatures of side-effect presence), but what's the point of a term that applies to all source code in existence?

> the only difference is that Haskell annotates effects with its type system.

I kind of disagree. Haskell doesn't only annotate effects with its type system. Haskell goes much further than that. It encourages an explicit and clear split between purely-function code and side effects.

But what do I know? Despite reading about it a lot, I've never written any Haskell ;)

Haskell does [partial?] type erasure, so RTS often knows nothing about types, it can't distinguish a pure function from any other one. The type consistence and runtime correctness is assured by the typechecker at compile time.

Total type erasure, at least ignoring `Typeable`.

> “C programmers” really program not in C, but in the purely functional language cpp (the “C Preprocessor”).

Well ...

The C Preprocessor might be functional in the same sense as the lambda calculus but that's about it.

And actually it isn't really: it needs to be supplied "evaluations" to work. Evaluation is naturally recursive but cpp only performs one pass, so you need to explicitly request more evaluations (or "scans").

See here: http://pfultz2.com/blog/2012/05/10/turing/ and here: http://theorangeduck.com/page/c-preprocessor-turing-complete

Not being Turing Complete makes it less than the lambda calculus, which is still consistent with "purely functional". Purely functional is about expressive power you can't have, not power you can. So take the lambda calculus and restrict it, it remains purely functional.

Yeah right, but that makes a bar stool into a purely functional language as well; so the point is kinda pedantic.

Not being able to recurse makes the language awful to use for almost everything excepted simple substitution, which is effectively what it is used for.

The C preprocessor, combined with the EVALn macros, is Turing-Complete-up-to-N-iterations, so not quite a bar stool.

Isn't it possible to learn functional programming in C ?

I often read people saying learning a functional language taught them good programming practices that they could apply to other language, so I conclude that functional programming is only made mandatory and very encouraged in functional language, but it doesn't mean it's not possible to use functional programming to a language like C.

I guess one way to learn functional programming simply would be to write as many pure functions as possible, and go from there. No need to learn a functional programming language. Honestly, haskell melt my brain several times and I did not see the point of learning it.

Functional programming generally involves a lot of dynamic memory allocations (which are usually optimized in some way). Without some form of assisted memory management, this quickly becomes excruciating. C also lacks function closures, so important abstractions like function composition, partial application and higher order functions. It also lacks type parameterization and polymorphism.

Not everyone will consider all of these to be fundamental to functional programming, but I'm certain most people would require at least one. C simply doesn't provide powerful enough mechanisms for abstraction to enable any interesting parts of functional programming.

C++, Rust, D and Nim all do, however. If one ever felt the need to use them in a functional matter it would be possible, albeit unpleasant.

Additional reading: https://news.ycombinator.com/item?id=8609775

>Functional programming generally involves a lot of dynamic memory allocations (which are usually optimized in some way)

It's symptomatic of many functional languages, but it's not a prerequisite.

> . C also lacks function closures, so important abstractions like function composition, partial application and higher order functions.

That, on the other hand, is a core feature of functional languages (what does it mean to have functions as first class citizens if one cannot manipulate them in an algebraic way?). I actually think it's the only needed feature to qualify.

> It also lacks type parameterization and polymorphism.

These are strongly typed languages features, I wouldn't define a functional language by it (I don't think it's necessary), although it appears in many of them.

If I get the point of the article, the author would argue that cpp provides some form of closure (you can code a macro that generates a function that behaves somewhat like a closure if you want...)

I feel primitive. Separating runtime from dev time is as advanced as the steam engine.

Too bad that the pure cpp code can't issue C actions which depend on results of previously issued actions. You can't implement cat in cpp+C, while you can in haskell.

> You can't implement cat in cpp+C

Yes you can.

I think that you missed the point of the article.

Just write a cpp macro that outputs a cat implementation in C.

Reply on news.ycombinator.com