Should data structures be integrated into the language (as in Python) or be provided in the standard library (as in Java)?

Question

In Python, and most likely many other programming languages, common data structures can be found as an integrated part of the core language with their own dedicated syntax. If we put LISP's integrated list syntax aside, I can't think of any other languages that I know which provides some kind of data structure above the array as an integrated part of their syntax, though all of them (but C, I guess) seem to provide them in the standard library.

From a language design perspective, what are your opinions on having a specific syntax for data structures in the core language? Is it a good idea, and does the purpose of the language (etc.) change how good this could be of a choice?

Edit: I'm sorry for (apparently) causing some confusion about which data structures I mean. I talk about the basic and commonly used ones, but still not the most basic ones. This excludes trees (too complex, uncommon), stacks (too seldom used), arrays (too simple) but includes e.g. sets, lists and hashmaps.

Answer 1

It depends what the language is for.

Some examples (somewhat stolen from other answers):

• Perl has special syntax for hashtables, arrays, strings. Perl is often used for scripting, these are useful for scripting.
• Matlab has special syntax for lists, matrices, structures. Matlab is for doing matrix and vectorial mathematics for engineering.
• Java/.NET support string and arrays. These are general purpose languages where arrays and strings are often used (less and less with use of new collection classes)
• C/C++ support arrays. These are languages that do not hide hardware from you. Strings are partially supported (no concatenation, use strcpy, etc.)

I think it depends what the purpose/spirit/audience of your language is; how abstract and how far away from hardware you want it to be. Generally the languages that support lists as primitives allow you to create infinitely long lists. While low level such as C/C++ would never have these, because that is not the goal, the spirit of those languages.

To me, garbage collection follows the same logic: does the audience of your language care about knowing exactly when and if memory is being allocated or freed? If yes, malloc/free; if no, then garbage collection.

Answer 2

Perl has hashmaps and PL/SQL supports records, and I have very foggy memories of matlab having syntax to support vectors and matrices of all different dimensions (though I could be wrong about this one and it could be argues that these are data types not data structures)... I would say that having some native support for very common structures is nice to have. Usually it seems that arrays and hashmaps/associative arrays are the most common natively supported structures, and they are probably the most commonly used as well.

Don't forget that if you add native syntax support for other structures such as binary-trees, those structures also have be implemented by the language's supporting tools (compiler/runtime/etc). How many strucutres do you want to build support for?

You'll have to invent new notation for the less commonly natively supported structures... Keep It Simple!.

Answer 3

My favourite example here is Lua. Lua has only one built-in data type, the "table", but its flexibility and speed mean you actually use them in place of regular arrays, linked lists, queues, maps and they're even the basis for Lua's object-oriented features (i.e. classes).

Lua is such an amazingly simple language, but the flexibility of the table data structure makes it quite powerful as well.

Answer 4

You don't have to have dedicated syntax for every high-level data type. For example, it's tolerable to have set([1, 2, 3]) (as Python 2.x did) instead of {1, 2, 3}.

The important thing is to have some convenient way to construct a high-level data structure. What you want to avoid is code like:

s = set()
s.add(1)
s.add(2)
s.add(3)

which annoys me greatly when I use std::vector, std::set, and std::map in C++. Thankfully, the new standard will have std::initializer_list.

Answer 5

In my opinion, it's an amazingly simple addition which can come handy surprisingly often, at least if done with caution - i.e. at most for tuples, lists, maps and sets as those have well-recognized literals.

• It's cheap to add to a language. It doesn't cost you much of that precious complexity budget:
  • the grammar is basically someBracket {expr ','} someBracket or someBracket {expr ':' expr ','} someBracket, with some dead simple extras if you want things like optional trailing commas. The float literals can easily be longer in the grammar.
  • In many languages, none of the popular literals clash with existing syntax (an exception I can think of is a language with brace-like blocks as expressions, a comma operator and no semicolon, as in {1, 2})
  • The semantics can be defined in less than five sentences, the informal version being "Instantiate a new $collection, then call .add/.append/.setItem once per given expressions with that (those) expression(s) as arguments".
• Due to the previous third point, it's also very easy to implement.
• It comes in incredibly handy when you need one, and doesn't (need to) impact the syntax of other elements, i.e. you don't "pay" for it when you don't use it.

Answer 6

Clojure is a lisp but supports

Lists: (x1 x2)
Vectors: [x1 x2]
Maps: {k1 v1 k2 v2}
Sets: #{x1 x2}

Answer 7

The more data structures you have in the language itself the more difficult the language would be to learn. It might be a personal preference but I tend to prefer a simpler language and then any extras can be supplied by libraries.

Languages designed for specific fields can sometimes benefit from having certain data structures built-in to the language such as Matlab. But too many can overwhelm you.

Answer 8

For a language to be really useful, it has to do a certain degree of tasks out of the box. Because practical day to day programming requires tools that solve their problems at some generic level. Minimalism looks compact and cool but when you want to start using to solve big but repeated problems, you need a level of abstraction on top of which you can build upon.

So I think programming languages should ship support for most commonly used data structures in the syntax for the tasks the language is designed for.

Answer 9

In general I find convenient to have literals for lists, sets and so on. But it sometimes bugs me that I do not know anything about the actual implementation of - say - the Python list or the Javascript array. The only thing I can be sure of is that they expose a given interface.

I take as a benchmark of a language expressiveness how well it can write its own data structures as libraries, and how convenient is to use them.

For instance, Scala provides various collections with different implementation and performance guarantees. All of them are implemented in Scala itself, and the syntax to use them is only slightly more complex than if they were builtin and had runtime support.

The only basic structure that really needs support from the runtime itself, at least in a managed language, is the array: if you do not manage the memory, you will have a hard time getting a bunch of adjacent bytes. Every other structure can be built out of arrays and pointers (or references).

Answer 10

APL (and related modern variants, A+, J and K) have scalar, vector and matrix as first-class data structures.

Yes, they can be deprecated as mere variants on array. But they're also free from complex declarations and don't come from a separate library, they feel like complex data structures that are a first-class part of the language.

Answer 11

From a language design perspective, what are your opinions on having a specific syntax for data structures in the core language? Is it a good idea, and does the purpose of the language (etc.) change how good this could be of a choice?

List and map literals and a convenient closure syntax are essential features of high-level languages.

The difference between this Java code:

Thing t = new Thing();
t.setFoo(3);
t.setBar(6.3);
t.setBaz(true);

and this Groovy code:

t = new Thing(foo: 3, bar: 6.3, baz: true)

is enormous. It's the difference between a 40,000 line program and a 10,000 line program. Syntax matters.

Answer 12

Sure it depends on the application of the programming language, but for higher level languages it should be as convenient as possible to work with any common data structure. Have a look at the list of abstract data types in Wikipedia for examples. I found the following basic principles most common (but I'd like to hear other opinions too):

• ordered sequences (1-dimensional): array, queue, stack, lists...
• ordered multi-dimensional structures: table, vector, matrice..
• maps: hashmap, dictionary, set, multimap... (1-dimensional)
• multi-dimensional maps: functions, maps of maps...
• graph types: trees, directed graphs...

You can emulate any structure with any other structure - it only depends on how easy and clear the programming language allows it. For instance:

• queue and stack are easy to emulate with arrays or lists, of the latter provide operations like push, pop, shift etc.
• ordered sequences can be emulated with maps that have numeric keys
• sets can be emulated by maps that map values to a boolean
• most graph types can be emulated by nesting sequences or maps
• functions can be used to emulate maps if you can easily modify their definition

Most languages provide at least one type for ordered sequences, one for 1-dimensional maps, and one for multi-dimensional maps, limited to functions. Personally, I often miss sets and ordered multi-dimensional structures in languages like Perl, PHP, JavaScript, Lua... because emulating them is not convenient enough.

Answer 13

I think it is a bad idea to have too many privileged data types that get special syntax. This complicates the language syntax needlessly, making code harder to read, making it harder for beginners to learn and making it harder to develop tools for the language.

It's OK to make an exception for a small number of very common data structure types. I'd probably allow at a maximum:

• Fixed-length arrays
• Sets
• Hashmaps
• Sequences / lists
• Records / structs / classes

Anything more sophisticated than that should probably be left to libraries to handle, using the language's normal syntax for custom data types.

In particular, things like Red/Black trees, Priority Queues etc. have quite a lot of possible implementation options, so it isn't wise to bake a particular implementation into the core language. It's better to let people choose the most appropriate implementation for their situation. Examples of implementation choices that I might not want a language designer to restrict my choice on:

• Mutable or immutable?
• Allows nulls or not?
• Synchronised or not?
• Backed by persistent storage or not?

Answer 14

I believe that with most modern programming languages, having data structures defined in core or "standard library" (like asked in the question) makes little difference. What is instead very different is having them in core/standard vs separated packages.

The advantages of having good, efficient implementations in core/standard means that then all packages can reuse (and eventually extend) them for their task (like in Julia), otherwise each package will need to implement its own "version" (like numpy, tensorflow,.. in Python or the tidyverse ecosystem for R).