Modern object-oriented languages like Java and Scala include collections classes/interfaces that provide the basis for many data structures. Collection frameworks typically support structures like sets, maps/dictionaries, sequences/lists inspired by set theory as well as more specialized forms of these such as queues, stacks, arrays, and sorted sets and maps targetted to common computing tasks. Different flavors of each collection type may be provided to support concurrent access, parallelization, or functional-style programming (immutable structures) vs imperative-style programming (mutable structures).
Slang provides a minimalistic collection framework with the following design goals:
- constain the capabilities of collections so as to enable the type of memory management needed when compiling for embedded systems (e.g., no garbage collection - static allocation of all data, or limited forms of garbage collection),
- control of aliasing/sharing and use of structural equality instead of reference equality to facilitate verification, and
- approximate alignment with Scala collections (easy to move back and forth between Slang collections and their Scala counterparts). Note that although Slang and Scala collections have some similarities, Slang uses a different type system and different syntax for many collection methods/operations.
The Slang collection framework together with Slang’s
datatype variants of class structures provide the basis for almost
all data structures used in a Slang program.
The Slang collection framework includes both mutable and immutable variants of the following:
- Sequences - ordered, indexable, lists of elements
- Sets - unordered sets of elements
- Maps - associations between “keys” and elements, enabling the “look up” of an element by its key.
ToDo, From John, To Robby: Add quick summary giving the main idea / restriction rules on how mutable and immutable are combined or combinations are disallowed. Details of the rules would be given later.
ToDo, From John, To Robby: Add quick summary of the copy on demand concept associated with collections. More details and diagrams will be given later.
Note: Though Slang supports sets and maps, the sequences types are the “workhorses” in the current version of Slang. The interfaces and expression forms for sequences are more thoroughly developed.