Hey, C Is a Functional Language Too • Hacker News Board

Re: Hey, C Is a Functional Language Too

#41

Post by fauigerzigerk » Fri, Nov 02, 2012, 1:28 PM UTC

jvranish wrote: post #33

fauigerzigerk wrote: post #29

Earlier quoted context omitted.

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

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

#42

Post by [deleted] » Fri, Nov 02, 2012, 1:57 PM UTC

slig wrote: post #28

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

[deleted]

Re: Hey, C Is a Functional Language Too

#43

Post by charliesome » Fri, Nov 02, 2012, 2:08 PM UTC

fauigerzigerk wrote: post #41

jvranish wrote: post #33

Earlier quoted context omitted.

It's still Turing complete (though that's not saying much really). You can always grow the stack more :P

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 reimp…

Any physical machine cannot be Turing complete because it has a finite amount of RAM.

Re: Hey, C Is a Functional Language Too

#44

Post by charliesome » Fri, Nov 02, 2012, 2:09 PM UTC

jvranish wrote: post #37

jrajav wrote: post #18

Earlier quoted context omitted.

Yes, but functions aren't truly first-class values; you cannot create new ones on-the-fly (proprietary extensions notwithstanding).

Actually, if you look closely you'll notice that not other language lets you do this either (except through an 'eval' or similar). What I think you actually mean is that this still doesn't let you use closures. But in fact it does! :D You'll have to do a lot of void * casting to make it work though.

C does not provide closures. You can pass around a struct with a function pointer and a data or state pointer though. That will let you achieve the same thing, but it won't be as pretty.

Re: Hey, C Is a Functional Language Too

#45

Post by utopkara » Fri, Nov 02, 2012, 2:17 PM UTC

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.

Re: Hey, C Is a Functional Language Too

#46

Post by fauigerzigerk » Fri, Nov 02, 2012, 2:18 PM UTC

charliesome wrote: post #43

fauigerzigerk wrote: post #41

Earlier quoted context omitted.

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 reimp…

Any physical machine cannot be Turing complete because it has a finite amount of RAM.

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.

Re: Hey, C Is a Functional Language Too

#47

Post by spacemanaki » Fri, Nov 02, 2012, 2:20 PM UTC

ginko wrote: post #10

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.

As jeremyjh already pointed out, this results in a pretty weak definition. You end up with JavaScript, Ruby, Python, and Objective-C all being lumped as "functional languages", and if you squint a little bit, you can put Java in there too (anonymous inner classes). I think C, C++ and C# could be as well, but I don't know them well enough.

So I don't think it's very productive to use a definition like this, but not because I want to be divisive, or "move the goal posts" or because I'm trying to be elitist here. It's because when a colleague asks you "what's functional programming?" I think it's much more helpful to describe the kind of programming that is encouraged in Haskell and Clojure than to just say, "well it's just map, filter, and fold in JavaScript".

Re: Hey, C Is a Functional Language Too

#48

Post by flatline » Fri, Nov 02, 2012, 2:28 PM UTC

ginko wrote: post #16

zokier wrote: post #11

Earlier quoted context omitted.

Doesn't function pointers enable passing functions around in C?

Yes, but you can't combine function pointers to create and return new functions.

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

Re: Hey, C Is a Functional Language Too

#49

Post by JoeAltmaier » Fri, Nov 02, 2012, 2:31 PM UTC

flatline wrote: post #48

ginko wrote: post #16

Earlier quoted context omitted.

Yes, but you can't combine function pointers to create and return new functions.

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

Right. SO you can program 'functionally' in those languages, but they are not 'functional programming languages' because they don't support it natively.

Re: Hey, C Is a Functional Language Too

#50

Post by _ea1k » Fri, Nov 02, 2012, 2:31 PM UTC

fauigerzigerk wrote: post #46

charliesome wrote: post #43

Earlier quoted context omitted.

Any physical machine cannot be Turing complete because it has a finite amount of RAM.

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.