title: What data structures and algorithms are not implementable in C?
body: <p>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 (<a href="http://www.ioccc.org/2001/herrmann1.hint" rel="nofollow noreferrer">ioccc.org Immanuel Herrmann</a>).  I've also seen some intriguing C algorithms that mimic the concurrency model of Erlang, but don't recall the source.</p>
  
  <p>What inspired this question was the StackOverflow post (<a href="https://stackoverflow.com/questions/500607/what-are-the-lesser-known-but-useful-data-structures">Lesser Known Useful Data Structures</a>) and the Patrick Dussud interview on channel9 (<a href="http://channel9.msdn.com/Shows/Going+Deep/Patrick-Dussud-Garbage-Collection-Past-Present-and-Future" rel="nofollow noreferrer">Garbage Collection - Past, Present and Future</a>) - explaining how they wrote the the first CLR garbage collector (written in Lisp targeting the JVM, compiled from Lisp to C++ for the CLR).</p>
  
  <p>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. </p>