Does Chapel have dynamic data structures?

Question

Chapel appears to be focused on n-dimensional arrays and tuples of fixed size. At first sight, there appear to be no dynamic data structures.

One particular issue is that you appear to have to pre-declare the size of associative arrays. Maps and dictionaries in other languages are not restricted in this way.

Does Chapel have a more dynamic map/dictionary type and I just missed it?

Answer 1

First, the answer to your question is yes. The built-in equivalent to a map/dictionary is an associative array in Chapel. See associative arrays primer.

For example, let's declare a dictionary from famous people's names to their birth year.

First, create a domain (ie index set) that will contain the names:

var setOfNames : domain(string); // a domain (set) whose indices are strings

A type declaration of domain(t), where t is some type, creates an associative domain.

Then, create an array over that domain storing an integer age. That in effect creates a map from string -> int.

var nameToBirthYear : [setOfNames] int;

To add somebody to the set, we need to first add them to the domain, and then set their birth year in the array.

setOfNames.add("Thomas Jefferson");
nameToBirthYear["Thomas Jefferson"] = 1743;

setOfNames.add("Alan Turing");
nameToBirthYear["Alan Turing"] = 1912;

Chapel is designed to support multiple arrays over the same domain. So if we wanted to separately also know the place of birth, we could create a separate array to track that.

var nameToBirthPlace : [setOfNames] string;

nameToBirthPlace["Thomas Jefferson"] = "the Colony of Virginia";
nameToBirthPlace["Alan Turing"] = "London, England";

Now, what if we want to add a new famous person?

setOfNames.add("Ada Lovelace");
// note now that both nameToBirthYear and nameToBirthPlace now have
// a value for the key "Ada Lovelace". That new element starts out with
// the default value - so it's 0 and the empty string in this case.
nameToBirthYear["Ada Lovelace"] = 1815;
nameToBirthPlace["Ada Lovelace"] = "London, England";

As a demonstration, we'll loop over the index set and print out the related array elements. (Note that this loop would make more sense with zippered iteration, but I'm trying to keep this example focused on associative arrays and domains).

for name in setOfNames {
  var birthYear = nameToBirthYear[name];
  var birthPlace = nameToBirthPlace[name];
  writeln(name, " started out in ", birthPlace, " in the year ", birthYear);
}

Note that these associative arrays and domains are currently implemented with hashtables. It's possible to create a custom associative array implementation or to create a custom (non-array) data structure for a red-black tree or whatever is needed.

In the future, it might one day be possible to add a key,value pair directly to an associative array (without explicitly mentioning the array's domain). 1-D arrays support such a feature when the domain is not shared by other arrays - see array vector operations primer ).