For example, why doesn't JavaScript provide a BST as a native data structure you could use?

var bst = new BST();

Alternative question: what are the costs and benefits to including such structures in a language? I don't see what the costs are, other than the time it takes to implement. Would having an additional data structure slow other things down?

Basically, I'm asking this from the perspective of someone who is familiar with the basics of data structures and is a JavaScript developer, but knows very little about compilers and language design. The way I see it, by adding an additional data structure, it's there if you want it, but won't hurt those who don't want to use it. But I'm sure that there are important things I'm not considering, and what I'm really asking is "what are they"?

  • 1
    The answers to such question often boil down to "you would have to ask the original designer or the standards body." We can do no more than guess at the reasons for inclusion or not. – user40980 Nov 15 '15 at 18:19
  • 2
    Why the creators of X did not include feature Y is usually not answerable. It's probably going to be some mix of "no one wanted a Y" or "it goes against the goals/purpose of the language" or "there were more important things to do", and obviously it's going to be different for every language that doesn't have Y. In the case of Javascript not having BSTs, it doesn't have many data structures period, probably because the standard space and time trade-offs between those data structures are all moot when you're working in a dynamically-typed scripting language. – Ixrec Nov 15 '15 at 18:21
  • I've noticed a trend where afaik, none of the higher level languages I've come across implement data structures like BST, so I figured that there was a generally applicable reason. – Adam Zerner Nov 15 '15 at 18:21
  • Regarding the assertion that adding a feature to a language has no costs other than implementation, you might find these posts interesting: blogs.msdn.com/b/ericlippert/archive/2003/10/28/… blogs.msdn.com/b/ericgu/archive/2004/01/12/57985.aspx – Ixrec Nov 15 '15 at 18:25
  • JavaScript has a famously minimal "standard library", and for a long time wasn't really used for nontrivial algorithmic stuff. Therefore it's not a very instructive example. Java for examples has various trees in its standard library. C++ has std::map and std::set. – user7043 Nov 15 '15 at 18:28

When you are designing a programming language, you generally want the core of the language to be as simple as possible but as general as possible and as expressive as possible, while still fulfilling its core design objectives. When you add a feature to a language, you have to consider how it fits with the overall design and philosophy of the language. Anything that doesn't meet that esthetic belongs in an external library, not in the language.

The purpose of binary trees is to provide a fast way to lookup something given a key. Because Javascript has lists with key/value pairs as one of its core features, there is a potential use for binary trees in the the language itself. But the designer of Javascript didn't choose a binary tree as his backing store; he picked a hash table. So the binary tree is left with no potential use case in the language itself.

If you're going to add binary trees to a language, why not also add b-trees? Red-black trees? Skip lists? Why a binary tree specifically? Each of these data structures does essentially the same thing, but with different performance characteristics. Having such data structures in a library allows the programmer to choose what he needs from the library without adding dead weight to the language.

For all of these reasons, binary trees are a better fit in an external library rather than the programming language, in most cases.

  • Why is it that you want to keep it as simple as possible? Does adding an additional data structure have any costs other than "it's another thing for newcomers to learn"? – Adam Zerner Nov 15 '15 at 19:43
  • 1
    No. Newcomers still need to learn the libraries so that they don't reinvent the wheel. It's a matter of cognitive load. Generally speaking, the simpler the language is, consistent with what language designers call expressiveness, the more productive you're going to be in the language. The very best languages allow you to keep the entire language in your head while you program. You can't do that with external libraries. Your language will always need a looping mechanism; it won't always need a binary tree. (not even very often, in fact). – Robert Harvey Nov 15 '15 at 19:46
  • Gotcha, thanks! That answers my question. I see the thinking, but I'm not sure if I agree with the logic. This is tangential to the actual question, but I'd love to hear your thoughts - if the downside to adding data structures is the time it takes to learn and the cognitive load on developers to think about how they want to structure their code, then why not just "make it optional". Ie. have the standard guides and tutorials revolve around the lightweight version, but have a heavyweight version available for those who are experienced enough to handle it? – Adam Zerner Nov 15 '15 at 19:51
  • 1
    One of the things that distinguishes library features from language features is that language features are bound to the syntax of the language. Any language worth its salt already allows you to write a binary tree without any special help from the language syntax. That's why the binary tree belongs in a library. – Robert Harvey Nov 15 '15 at 19:56
  • 2
    As far as I know, the nature of "you don't pay for what you don't use" is unique to the C++ language specifically; it is a core part of its design. There are lots of additional costs to adding a feature to a language, as Eric Lippert illustrates. All of those costs are avoided if you just write an external library., – Robert Harvey Nov 15 '15 at 19:59

Not the answer you're looking for? Browse other questions tagged or ask your own question.