On the way to Strange Loop this year, John Van Enk and I were trying to find a way to write some C code that avoided dynamic (malloc) allocation. We discovered a technique that allows you to forgo the use of malloc in many common cases. It also enables very pure functional C code.
You doubt? I shall demonstrate! I will show how you can write a linked list reversal function in C using:
Linked lists, with no malloc!
And this isn’t just a trick that only works in this special case, it is quite generally applicable.
The trick is to allocate values on the stack and then pass pointers to them to the next “continuation” to build up your results. This lets you get away with a functional style in C without the need to call malloc and free (malloc and free pretty much ruin everything).
As long as your intermediate values don’t get so big that you blow the stack, you should be good. The main limitation is that you need to know the size of the return value.
Would this ever actually be useful?
While I find this style strangely addictive, I don’t think I would advocate its general use. However it has a few interesting advantages that might be handy in certain situations:
Fixed Memory Bounds – Since everything is allocated on the stack. If we can prove that our functions terminate (say we show that a function is structurally recursive ). We get a proof of finite memory use with it!
Better Function Composition – I was kinda surprised by this, but I guess I shouldn’t have been. The code is a bit more ugly, but it’s definitely easier to build large things up using smaller reusable pieces.
No Malloc – Almost non-existent allocation overhead.
So what does “functional language” mean, then?
Almost every language has a functional subset. And it seems pretty silly to call a language “functional” just because it has a functional subset.
I think it would be much more meaningful if we described a language as “functional” only if it encourages a functional style. A functional style is a style that emphasizes“values” over states or “places”, expressions over statements, recursion over mutation.
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.
I write software for embedded systems. Most of that ends up being C, but I make heavy use of Python and Ruby for automating system tests. I'm also a big fan of Haskell, and get excited about tools, techniques and practices, that make it easier to write correct software.