Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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.

share|improve this question
1  
Are we excluding the object and the hashmap? –  Orbling Apr 4 '11 at 20:21
3  
@Anto: Well many languages have hashmaps in the form of associative arrays, Perl, PHP, JS (technically an object here), etc. –  Orbling Apr 4 '11 at 20:27
1  
Perhaps you could be more specific about which data structures you're thinking of, aside from arrays, lists, hashmaps/associative arrays? –  FrustratedWithFormsDesigner Apr 4 '11 at 20:53
1  
Include hashmaps, lists and anything more advanced as the "complex data structures" and throw out arrays as too simple. –  Anto Apr 4 '11 at 20:56
1  
I think a more sensible title would be something like: "What data structures should be included in the language, and what in the library?" A meaningful answer depends heavily on the language though: the more cleanly the library is integrated into the language, the more reasonable it is to move structures into the library. –  Jerry Coffin Apr 4 '11 at 22:16

13 Answers 13

up vote 9 down vote accepted

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.

share|improve this answer
4  
This is a bad place to use the term "C/C++", because the presence of high-level template types in C++ is a major difference between the two languages. –  dan04 Apr 5 '11 at 13:26
    
Garbage collection can be done in a deterministic fashion, you just need linear types (or their poor man's replacement: RAII). –  Eduardo León Apr 16 '13 at 23:52
    
@EduardoLeón, although you can call garbage collection at a deterministic point, I do not think how long it will run for is deterministic (for the same reason that malloc and new are non-deterministic in C/C++). –  earlNameless Apr 22 '13 at 14:38
    
@earlNameless: It is deterministic relative to the resource's usage: linear types (or uniqueness types, which are similar) make it a type error (and, thus, compilation error) to not free resources (modulo the possibility, not captured by the type system, of any abnormal program termination), or to use them after they have been disposed. –  Eduardo León Apr 22 '13 at 17:21

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!.

share|improve this answer
    
There's no need to invent a literal syntax for e.g. trees - they're rarer, they aren't even in the stdlib of many languages! By the same argument, one could oppose the inclusion of operators because "you'd have to invent new notation for the less commonly used operations". –  delnan Apr 4 '11 at 20:35
    
@delnan: The way I understood it was from the perspective of designing a new language and wondering whether or not data structures besides arrays should be natively supported by (possibly) new syntax, or if they should be supported by including a library. –  FrustratedWithFormsDesigner Apr 4 '11 at 20:40
    
Well, the first sentence explicitly talks about "common data structures", so I assume OP is not insane enough to try add special syntax for every obscure data structure ever invented. –  delnan Apr 4 '11 at 20:42
    
@delnan: ...and then the OP goes on to exclude LISP lists and arrays (in general) "...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" ...so I thought they were pondering data structures more exotic than arrays/lists... –  FrustratedWithFormsDesigner Apr 4 '11 at 20:44
    
Yes (I interpreted "above the arrays" as "other common data structures"), but nothing in the question hints at "let's make literals for every single data structure we have". It's fine to state that this should be limited to what's reasonable, but I don't think we can say "bad idea" just because of this assumption. –  delnan Apr 4 '11 at 20:53

My favourite example here is Lua. Lua has only one built-in data type, the "table", but it's 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.

share|improve this answer
1  
JavaScript objects are really the same way--Arrays are just really objects with numerical properties and a length, for example. –  Tikhon Jelvis Apr 5 '11 at 4:33
    
Lua tables are different to JavaScript Objects: In JavaScript {} is not [], in Lua you have {} for both. Lua tables better compare to lists in Lisp. –  Jakob Apr 6 '11 at 19:48
    
I guess in JavaScript, "everything is an object" - including arrays - but not everything is an array. In Lua, everything is a table. –  Dean Harding Apr 6 '11 at 20:13

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.

share|improve this answer

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.
share|improve this answer

Clojure is a lisp but supports

Lists: (x1 x2)
Vectors: [x1 x2]
Maps: {k1 v1 k2 v2}
Sets: #{x1 x2}
share|improve this answer

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.

share|improve this answer

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.

share|improve this answer

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.

share|improve this answer
    
APL also has nested arrays, and arrays do not have to have homogeneous data type, which all makes for very powerful data structures. –  RFlack May 24 at 5:41

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.

share|improve this answer
    
In C# one can do: var t = new Thing(foo: 3, bar: 6.3, baz: true); - only 4 more characters. –  Job Apr 6 '11 at 20:59
    
it's actually the same number; the Groovy code should read 'def t = ...' –  kevin cline Apr 7 '11 at 6:01

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?
share|improve this answer

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).

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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