This 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

2: http://wiki.call-cc.org/chicken-compilation-process

3: The homepage is called www.call-cc.org :P

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

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

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

This is the same as the design of Chicken Scheme's implementation (on top of C).

http://en.wikipedia.org/wiki/Chicken_(Scheme_implementation)...

In fact it's purely functional!

http://conal.net/blog/posts/the-c-language-is-purely-functio...

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

This seems like a lot of work just to avoid using the heap...

It would be hilarious to provide this as an answer in a job interview to "how do you reverse a linked list?"

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

Quick question: why does he do this?

    int main(int argc, char * argv[]) {
      (void)argc;
      (void)argv;

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

It looks like someone trying to prove Greenspun right.

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

money 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."

In my opinion, the meat of functional programming languages is that they are expression oriented. C clearly is not an expression oriented language.

it might have also been worthwhile to mention that the stack array declaration:

   int32_t result[my_array_size];

... and why is it not obvious? just curious..

On another satirical but deeply intellectually serious note:

http://conal.net/blog/posts/the-c-language-is-purely-functio...

By Conal Elliot.

No it's not. What makes a language functional is its ability to eliminate tail recursion.