Hi,
I'm a C# developer and I don't have enough information about functional languages,
My question that is there any algorithm needs functional language exclusively to be implemented?
Regards.
views:
139answers:
3
+3
A:
No, however a functional language may lead to a more elegant implementation for an algorithm that can exploit the features of such a language. For example, one that requires large recursive depth.
Justin Ethier
2010-10-16 18:10:20
A:
As I understand it, such algorithm would have to be translated into a set of machine commands executed on some micro-processor (whether you use compiled or interpreted language). And none of the current processors are 'functional'.
In fact, this leads to even broader assertion: any 'functional algorithm' can be implemented in C or assembler :)
Nikita Rybak
2010-10-16 18:13:12
That functional language is translated into imperative instruction set does not matter. A Turing Complete language can simulate any other Turing Complete language. Any algorithm that can be run under a Turing Complete language, can be run on any other Turing Complete language. This guarantees that all "functional algorithm" can be run in "imperative machine", and all "imperative algorithm" can be run in "functional machine".
Lie Ryan
2010-10-16 19:32:44
Therefore, the assertion is even broader: "Any algorithm that can be executed in one Turing Complete language, can be implemented in any other Turing Complete language"
Lie Ryan
2010-10-16 19:35:16
@Lie I know that there's a lot of theory around Turing Machine and 'proof' can be extended however far you want (even into the fields of nuclear physics, probability theory or economics). But it doesn't make 'homemade' argument less valid. In fact, I wanted to keep it on 'handcrafted' level.
Nikita Rybak
2010-10-16 19:42:29
@Nikita Rybak: Your argument is perfectly valid, it is true that, because all current functional language is implemented on an imperative instruction set (e.g. x86), therefore all currently known functional algorithms can be implemented imperatively. I'm just showing that, the vice versa will be true as well, that all imperative algorithm can be translated into functional algorithm.
Lie Ryan
2010-10-16 19:55:32
+6
A:
As long as a language is Turing complete, any algorithm can be implemented in it (by definition of "algorithm"). But as others have said, functional languages can do certain things more elegantly. (Just take a look at Haskell. What a lovely language.) I'd also argue that there is a class of problems that OOP languages do better. (In my opinion, GUIs, although some may disagree.)
Gregory Higley
2010-10-16 18:16:27
Thanks, Pavel. I'd thought of saying "any computable algorithm" after I'd written it, but didn't bother changing it.
Gregory Higley
2010-10-16 21:19:58