20 ms·
Hey, C Is a Functional Language Too
- cschramm 14y agoNo it's not. What makes a language functional is its ability to eliminate tail recursion.
- charliesome 14y agoGCC can eliminate tail recursion, so does that make C functional? I don't think the author is seriously of the belief that C is a functional language. This is just a fun little example of writing C in a functional style.
- Jach 14y agoGCC can even eliminate non-tail recursion, such as with this piece of black magic: int factorial(int x) { if (x > 1) return x * factorial(x-1); else return 1; } will be optimized by GCC to int factorial(int x) { int result = 1; while (x > 1) result *= x--; return result; } (http://ridiculousfish.com/blog/posts/will-it-optimize.html http://ridiculousfish.com/blog/posts/will-it-optimize.html)
- dbaupp 14y agoThat's not a very good definition. It means that GHC-flavoured Haskell isn't functional: http://www.haskell.org/haskellwiki/Tail_recursion http://www.haskell.org/haskellwiki/Tail_recursion
- batterseapower 14y agoI think you might have misinterpreted the contents of that page. As someone who has worked on GHC, I can assure you that it does perform tail call optimisation.
- dbaupp 14y agoI believe I have. Thank you for correcting me.
- eru 14y agoThat's a very weird definition. Eliminating tail calls is fun, and useful. But not all that essential in, say, a lazy language. Having first-class function values in the first place strikes me as way more important. Purity helps, too.
- Evbn 14y agoHow do you write a function to sum a list of a billion elements in Haskell? What would happen without tail call elimination?
- eru 14y agoWith foldl', of course. If you don't have tail recursion elimination, foldl' would have to be provided as a built-in. Summing up numbers is inherently strict, so you'd want tail call elimination for that. But functional mainstains, like say, map or filter are usually not implemented with tail recursion in Haskell, because that would be too strict and would break on infinite lists.
- jfb 14y agoTail-call elimination is a feature of the language environment, not of the language itself.
- Turing_Machine 14y agoNot necessarily. The Scheme spec requires tail-call elimination, and I think the same may be true of some other functional-ish languages.
- Nursie 14y agoThis seems like a lot of work just to avoid using the heap...
- cmsd2 14y agoFrom that it looks like the caller always has to allocate the right amount of space on the stack to hold the result. What if the result size is known only by the callee? Denying yourself the use of the heap is also going to make closures rather difficult. You can use this style to pass back a function pointer, but the caller would also need to allocate space for the callee's captured variables. Ick.
- jrajav 14y agoThis is essentially the technique used to implement the meat of Chicken Scheme, too. [1][2][3] It's a pretty neat idea, but not a new one. 1: http://en.wikipedia.org/wiki/Chicken_Scheme http://en.wikipedia.org/wiki/Chicken_Scheme 2: http://wiki.call-cc.org/chicken-compilation-process http://wiki.call-cc.org/chicken-compilation-process 3: The homepage is called www.call-cc.org :P
- ginko 14y agoI would say the aspect that defines a functional programming language is the support of higher order functions. I.e. functions that can take functions as arguments and more importantly can return functions as return value.
- zokier 14y agoDoesn't function pointers enable passing functions around in C?
- ginko 14y agoYes, but you can't combine function pointers to create and return new functions.
- flatline 14y agoSure you can - just not anonymously. Kind of like how you can have "higher order functions" and "closures" in Java with anonymous classes - roughly equivalent, but awkward and not quite what the language was designed for. C is probably better in this regard than Java, but the lack of managed memory is a major drawback.
- JoeAltmaier 14y agoRight. SO you can program 'functionally' in those languages, but they are not 'functional programming languages' because they don't support it natively.
- sixbrx 14y ago"just not anonymously" Just not depending on anything in the environment either except globals, which is a huge limitation. So writing a function inc by = \x -> x + by becomes unnecessarily difficult for example.
- aaronblohowiak 14y ago
- chrisdew 14y agoThis is the same as the design of Chicken Scheme's implementation (on top of C). http://en.wikipedia.org/wiki/Chicken_(Scheme_implementation)#Design http://en.wikipedia.org/wiki/Chicken_(Scheme_implementation)...
- szany 14y agoIn fact it's purely functional! http://conal.net/blog/posts/the-c-language-is-purely-functional http://conal.net/blog/posts/the-c-language-is-purely-functio...
- xyzzy123 14y agoIt would be hilarious to provide this as an answer in a job interview to "how do you reverse a linked list?"
- agumonkey 14y agoIt looks like someone trying to prove Greenspun right.
- fab13n 14y ago...and pigs can fly, if you throw them fast enough. This is just an encoding of a Turing-complete language into another, I don't see what's been demonstrated here.
- fauigerzigerk 14y agoI'm not sure this is even Turing complete considering the limitation he mentions: >The main limitation is that you need to know the size of the return value.
- jvranish 14y agoIt's still Turing complete (though that's not saying much really). You can always grow the stack more :P
- fauigerzigerk 14y agoI don't think that solves the problem. Whatever fixed stack size you choose, you still cannot write a program that determines the size of the lists at runtime. A Turing complete system would have to be able to do that. The only way I see is to allocate (almost) the entire machine memory to the stack, create one giant array in that chunk of memory and then put all lists in that single array. That's tantamount to reimplementing malloc on the stack.
- charliesome 14y agoAny physical machine cannot be Turing complete because it has a finite amount of RAM.
- fauigerzigerk 14y agoSure, but we're talking about whether or not this particular style of C can be Turing complete and I'm not sure it is, even on a machine with an infinite amout of RAM.
- michaelfeathers 14y agoI think that this is an interesting area. We can support just about any style in an existing programming language, but there are often rough edges. This reminds me of how I used to mimic OO in C years ago. At a certain point you realize that you have to forgo certain things to help the person coming after you avoid making mistake -- often they do not see the ramifications of your conventions. I see this in Ruby right now when I write in a functional style. The code is often terse yet easy to read, but the lack of lazy evaluation makes it far more memory consumptive than code written in a straightforward procedural style. If you know you are making the tradeoff, it is fine. For many people, it is too subtle.
- georgeg 14y ago... and why is it not obvious? just curious..
- slig 14y agoQuick question: why does he do this? int main(int argc, char * argv[]) { (void)argc; (void)argv; I've programmed C while in school, but I don't remember ever seeing this and I'm not sure how to google it.
- walrus 14y agoIt stops the compiler from complaining about unused variables: http://stackoverflow.com/questions/8052091/void-cast-of-argc-and-argv http://stackoverflow.com/questions/8052091/void-cast-of-argc...
- tmhedberg 14y agoWhy would you do this instead of declaring it as `int main(void)`?
- jvranish 14y agoI use clang with a -Wall and -Wextra, which will complain about all sorts of stuff I generally want to know about, including unused variables (I think gcc does the same?). For the rare cases where I actually want to leave a variable unused I do the above to make the warning go away.
- deleted 14y ago[deleted]
- flyinglizard 14y agoAt some point the stack is going to grow which will cause allocation at the OS level. And if we're discussing small embedded systems with fixed stacks, this code is entirely unsafe (non deterministic stack usage may cause stack overruns). In embedded systems (non-MMU ones) you generally want to avoid repeated dynamic runtime allocation to prevent memory fragmentation. It's a cute example, but I can't see any scenario where its better or safer than heap use.
- jvanenk 14y ago> It's a cute example, but I can't see any scenario where its better or safer than heap use. The author does explicitly point this out: "While I find this style strangely addictive, I don’t think I would advocate its general use."
- ibotty 14y agomoney quote (at the end of the article): "So my title is misleading. I don’t think C is a functional language. But it’s an awful lot of fun (and sometimes very useful) to use C’s functional subset."
- utopkara 14y agoDitto on the addictiveness of continuation-passing style. However, don't try it when coding with peers who are not used to it; you can be burnt at the stake. Because, even though it makes the code easier to read, to the untrained eye it is just cryptic.
- Evbn 14y agoOn another satirical but deeply intellectually serious note: http://conal.net/blog/posts/the-c-language-is-purely-functional http://conal.net/blog/posts/the-c-language-is-purely-functio... By Conal Elliot.
- jmilloy 14y agoI disagree completely that this is a 'functional subset' of C. I also don't know a lot about this stuff, so tear me up. A functional language isn't just one that doesn't use malloc/only uses the stack. It must actually not have state, and instead evaluate a single function down to the result. Here, after calling make_lists, the input and the result still both exist as state variables (immutable, yes, but that's not enough)! At the same time, I haven't looked at code for a lisp interpreter, but I feel safe assuming that it allocates some memory somewhere. Functional programming doesn't have anything to do with the underlying implementation. The trick here, if any, is that the "underlying implementation" and the code are in the same language/program.
- mellery451 14y agoit might have also been worthwhile to mention that the stack array declaration: int32_t result[my_array_size]; relies on C99 support, which is not necessarily ubiquitous (especially in embedded device work). At the very least, many compilers make you explicitly enable C99 support.
- vu3rdd 14y agoIn my opinion, the meat of functional programming languages is that they are expression oriented. C clearly is not an expression oriented language.