8

This may sound naive, but are there any data structures / algorithms that cannot be constructed in C, given enough code? I understand the argument of being Turing complete. I also know it's beneficial to have an elegant solution and that time complexity is important (i.e. more expressive or succinct when implemented in Ruby / Java / C# / Haskell / Lisp). All the languages I've researched or used all seem to have been created or subsequently refactored into C based compilers, interpreters, and/or virtual machines. Are some complex data structures only implementable with an interpreter and/or virtual machine? If that virtual machine or interpreter is C based, isn't that just another data structure abstraction of the underlying C code? i.e. C has a simple type system but serves as the foundation for a dynamic type system. I was surprised to learn metaprogramming seems possible in C using the preprocessor (ioccc.org Immanuel Herrmann). I've also seen some intriguing C algorithms that mimic the concurrency model of Erlang, but don't recall the source.

What inspired this question was the StackOverflow post (Lesser Known Useful Data Structures) and the Patrick Dussud interview on channel9 (Garbage Collection - Past, Present and Future) - explaining how they wrote the the first CLR garbage collector (written in Lisp targeting the JVM, compiled from Lisp to C++ for the CLR).

So, at the end of the day, after I finish punching my cards, I'm wondering if this question is probably more about C programming language design than convenience of programming and time complexity. For example, I could implement a highly complex algorithm in Prolog that is very elegant and quite difficult to understand expressed any other way, but I'm still limited by the assembly instructions and the computer architecture (on/off) at the other end of the stick, so I'd be here all night.

Community
  • 1
  • 1
Stix
  • 159
  • 9
  • I think you mean "elegant" not "eloquent". :) – ooga Jan 28 '14 at 03:25
  • There's probably nothing that can't be done in C, but there are lots of cases where vanilla C is a poor choice either because it's too primitive and expensive to code in, or because it's too dangerous and error-prone. – Hot Licks Jan 28 '14 at 03:26
  • @ooga - It's a voice synthesis app. – Hot Licks Jan 28 '14 at 03:28
  • You say that you understand what "Turing Complete" means and then you ask whether there is an algorithm that cannot be implemented in C. I am therefore not convinced that you actually understand what "Turing Complete" means. I can't make heads or tails of this question; what are you actually asking? – Eric Lippert Jan 28 '14 at 03:44
  • @EricLippert - I understand what it generally means. I'm confused by the limitations of a Turing machine (for example http://en.wikipedia.org/wiki/Turing_machine seems to imply they do not model computational complexity or concurrency very well). Technically, the Church-Turing thesis is a conjecture/hypothesis (albeit a proven axiom when characterizing effectively-computable functions http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.146.5402). I understand your point, just wondering how far up in abstraction I can go before C is not an option (vanilla nor as an intermediate target)? – Stix Jan 28 '14 at 14:44
  • @HotLicks - Not a voice app, very complex graph theory and physics. – Stix Jan 28 '14 at 14:49
  • 1
    Basically, if you can't do it in C (and the problem is not due to the need for assembly-level access to the machine) then you can't do it in any other language. – Hot Licks Jan 28 '14 at 16:13

3 Answers3

15

Shor's algorithm for factorizing integers in O((log n)^3) polynomial time cannot be implemented in C, because the computers that it can run on do not yet officially exist. Maybe someday there will be a quantum circuit complete version of C and I'll have to revise my answer.

Joking aside, I don't think anybody can give you a satisfying answer to this. I will try to cover some aspects:

  • Vanilla, standard C might not be able to make use of the whole feature set of your processor. For example, you are not able to use the TSX feature of recent Intel processors explicitly. You can of course resort to OS primitives, inline assembly, language extensions or third-party libraries to circumvent that.
  • C by itself is not very good at parallel/asynchronous/concurrent/distributed programming. Some examples of languages that probably make a lot of tasks infinitely easier in this area are Haskell (maybe Data Parallel Haskell soon?), Erlang, etc. that provide very fast and lightweight threads/processes and async I/O. Working with green threads and heavily asynchronous I/O in C is probably less pleasant, although I'm sure it can be done.
  • In the end, on the user level side of things, of course you can emulate every Turing complete language with any other, as you pointed out so correctly.
Dan D.
  • 73,243
  • 15
  • 104
  • 123
Niklas B.
  • 92,950
  • 18
  • 194
  • 224
  • Also you can include assembly into C, which means anything an interpreter does, you can too. But i guess that would not be considered 'vanilla' – da_steve101 Jan 28 '14 at 03:51
  • @Niklas B. - That's a very interesting algorithm. I guess everything ultimately is a result of hardware architecture. I add processors and use openCL, I've got good parallelism, but as pointed out above that's not vanilla. – Stix Jan 28 '14 at 05:00
  • @Stix: I becomes even more interesting when someone executes it and reads all your private RSA-encrypted mails :) – Niklas B. Jan 28 '14 at 05:37
5

Any Turing-complete machine or language can implement any other Turing-complete language, which means it can implement any program in any other Turing-complete language by interpretation if no other way. So the question you're asking is ill-formed; the issue is not whether tasks can be accomplished but how hard you have to work to accomplish them.

C in particular functions almost as a "high-level assembler language", since it will let you get away with many things that more recent languages won't, and thus may allow solutions that would be harder to implement in a more strongly-checked language.

That doesn't mean C is the best language for all those purposes. It forces you to pay much more attention to detail in many areas ranging from memory management to bounds checking to object-orientation (you CAN write OO code in C, but you have to implement it from the ground up). You have to explicitly load and invoke libraries for things that may be built into other languages. C datatypes can be incredibly convoluted (though typedefs and macros can hide much of that complexity). And so on.

The best tool for any given task is the one that (a) you are, or can become, comfortable with; (b) that's a good fit for the task at hand, and (c) that you have available.

keshlam
  • 7,931
  • 2
  • 19
  • 33
1

Take a look at Turing completeness: Turing Completeness

Basically, any language which is Turing complete can execute all Turing-computable functions. C is a Turing complete language, so in theory you can implement any known solvable algorithm in C (albeit it may be terribly inefficient).

George
  • 416
  • 3
  • 11