There's a quotation by Ralph William Gosper, Jr that says:
A data structure is just a stupid programming language.
What did he mean by this? Alas, all I can find in Google about it is relentless copy/pastes of the quotation itself, without any context.
Well, it seems like the heart of the statement is:
A data structure is just a ... programming language
Which is quite true if you think about it. After all, compilers rely on this transitivity all the time; they take a programming language, convert it into a data structure, do some transformations on that data, and then turn the result into another programming language.
In fact, if you wanted to you could even make something crazy like a C data structure, that lets you write C code by calling its various methods - for instance (in kinda C#, because that's what I'm using right now):
var C = new HorribleCObject();
C.Function<int>("main", typeof(char[][]), typeof(int))
.Variable("i", typeof(int), 0)
.While("i", Func(i) => i < 10))
.Call("printf", "%d", "i")
.PostIncrement("i")
.EndWhile();
.Return(0)
.EndFunction();
Now, as to the full quote: why would something like that be stupid compared to (say) writing in C itself? It should be pretty obvious that this is verbose and not nearly as legible as its equivalent in C (and, in practice, might not support the full scope of what C can do - typedefs would be tricky); hence, this data structure is just a "stupid" programming language, embedded in a "real" programming language. That same logic can be generalized to any data structure you can think of; linked lists are just a "stupid" version of Lisp, and hash maps are just a "stupid" version of some theoretical Hash Programming Language (Hasp?).
The thing is, though, that we don't always want to write Hasp in order to interact with our hash maps. It's the problem all domain specific languages have - on the one hand, a well-implemented DSL is powerful enough to express everything the underlying model can do; on the other hand, you have to implement the DSL in the first place, and then other people have to learn it. That takes time and effort that they probably don't want to spend; after all, I just want to put things in my hash map and then check other things are in there, I don't want to learn all the intricacies of Hash Oriented Programming.
So, pretty much without thinking about it, we take these theoretical highly specific and very smart programming languages and distill them down to the few, stupid operations embodied in a data structure. A linked list has one small collection of simple methods; a hash map has some others. We ignore the other, more powerful operations you could potentially perform over the data structure (most LinkedList implementations don't have a .Map or .ForEach function, for instance, and I can't even imagine what you would do in Hasp), in favor of implementing them explicitly in the parent programming language - which is what most programmers are going to be familiar with.
Data structures are, essentially, a stupid extension of their parent language into the problem space that they conceptually represent. A sufficiently smart extension would require a new, specific programming language, and most people aren't going to want to learn that.
A data structure is a REPRESENTATION of a programming language. But not a particularly "sharp" one.
This can be seen from a "node diagram" like the one in the wiki article below:
http://en.wikipedia.org/wiki/Root_node#Terminology
Nevertheless, a data structure is INCOMPLETE as a programming language, because it lacks syntax and complete thoughts that would be intelligible to a programmer. A data structure's "language" might be compared to a child who said something like, "Me, cold. Get coat."
The "language" is fractured, but can be understood. The child is saying that "s/he is cold, and would like more clothes as covering." The child's utterance is a "stupid" version of the English language, and likewise data structure in relation to a programming language.
I believe that what Bill Gosper intended is that all data structures are just programming constructs with limited applicability. This is also related to the idea that "Language design is library design and library design is language design" [1].
One way of thinking about the issue is to consider data structures merely on an algorithmic basis. Forget about storage requirements or type annotations for the moment because these are simply ancillary.
For example, you could codify an associative array (called a map in some languages) in two ways: Either by using some kind of index stored in memory or by using a simple case expression.
In Haskell you could codify an associative array as a data structure...
let assocArray = [("a", 1),("b", 2),("c", 3)]
let key = "b"
lookup key assocArray
...or by using a case expression...
let key = "b"
case key of
"a" -> 1
"b" -> 2
"c" -> 3
...or even more directly...
let key = "b"
if key == "a"
then 1
else if key == "b"
then 2
else if key == "c"
then 3
else undefined
It is easy to see to that this kind of mirroring between data structures and code is possible by looking at the lambda calculus. Any value can be represented by a function in the lambda calculus and the calculus itself is universal (turing complete).
[1] The quote is thanks to Bjarne Stroustrup.
Consider Javascript, where all data is code. Consider LISP, where all data is code and all code is data.
In the beginning, end, and everywhere in between, data is just bits. That we attempt to ontologize bits with text and symbols to make them easily human-readable and human-transformable is a layer of abstraction that requires a) You learn the definition language and b) you learn the leakiness of the abstraction.
For example, in C#, learning the difference between a struct and class requires you learn the difference in equality comparison between value-types and reference-types. Every data ontology requires its own set of rules you must learn and adhere to. And, like any language, it allows you to quickly get to the general idea, but the closer you want to approach the actual truth of the matter, the more you should just look at the binary yourself.
Finally, when one considers a B-tree or similar data structure, navigating the structure of the tree and performing other kinds of operations on it requires a specialized kind of syntax that's not necessarily transferable across trees, structures, or languages.
