What data structures and algorithms are not implementable in C? [closed]

Question

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.

Answer 1

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.

Answer 2

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.