All programming languages and all programming styles can be similarly dismissed as encoding one Turing-complete form into another. Why pay attention to any of them?
This article is clearly someone having fun with their language. It isn't a serious claim about C being functional, something which the author states explicitly if you read to the end.
Re:Hey, C Is a Functional Language Too
by andrewcooke on Friday November 02, 2012 @11:35AM
(#4733100)
http://news.ycombinator.com/item?id=4693920
"everything is turing complete" is a perfect example of the kind of middle-brow dismissal i understood pg to be talking about.
Re:Hey, C Is a Functional Language Too
by fauigerzigerk on Friday November 02, 2012 @08:44AM
(#4732333)
I'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.
It's still Turing complete (though that's not saying much really). You can always grow the stack more :P
Re:Hey, C Is a Functional Language Too
by fauigerzigerk on Friday November 02, 2012 @09:28AM
(#4732499)
I 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.
Re:Hey, C Is a Functional Language Too
by charliesome on Friday November 02, 2012 @10:08AM
(#4732651)
Any physical machine cannot be Turing complete because it has a finite amount of RAM.
Re:Hey, C Is a Functional Language Too
by fauigerzigerk on Friday November 02, 2012 @10:18AM
(#4732681)
Sure, 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.
A machine with an infinite amount of RAM can have an infinite stack size.
Re:Hey, C Is a Functional Language Too
by fauigerzigerk on Friday November 02, 2012 @10:35AM
(#4732767)
C arrays that live on the stack have to be created with a constant size (at least before C99). It's a limitation of the language regardless of any machine or stack size.
If we're going to grant that a machine can have infinite ram, surely we can grant that a spec of C can have infinite stack allocated arrays... :)
That's already been granted in this argument. The question now is, given an infinite stack, is this programming style Turing-complete?
Address space is not limited by RAM. The only concern is fixed vs expandable width address.
That is a purely theoretical concern, not a practical blocker against any program anyone would ever run.
Re:Hey, C Is a Functional Language Too
by fauigerzigerk on Friday November 02, 2012 @10:59AM
(#4732923)
A program that determines the number of items it needs to store in a list only at runtime doesn't seem that theoretical to me.
This is just an encoding of a Turing-complete language into another, I don't see what's been demonstrated here.