5 Hashtables and Sets

5.1. Hashtables

The rewriting paradigm of Stratego is functional in nature, which is somewhat contradictory to the imperative nature of hashtables. Normally, this doesn’t present any practical problems, but remember that changes to hashtables “stick”, i.e. they are changed by side-effect.

The Stratego hashtable API is pretty straightforward. Hashtables are created by new-hastable and destroyed by hashtable-destroy.

stratego> import lib
stratego> new-hashtable => h
Hashtable(136604296)

The result Hashtable(136604296) here is a handle to the actual hashtable. Consider it a pointer, if you will. The content of the hashtable must be retrieved with the hashtable-* strategies, which we introduce here. The strategy hashtable-copy can be used to copy a hashtable.

Adding a key with value to the table is done with hashtable-put(|k,v), where k is the key, v is the value. Retrieving the value again can be done by hashtable-get(|k).

stratego> <hashtable-put(|"one", 1)> h
Hashtable(136604296)
stratego> <hashtable-get(|"one")
1

The contents of the hashtable can be inspected with hashtable-values and hashtable-keys.

Nesting is also supported by the Stratego hashtables. Using hashtable-push(|k,v), a new “layer” can be added to an existing key (or an initial layer can be added to a non-existing key). Removing a layer for a key can be done with hashtable-pop(|k).

stratego> <hashtable-push("one",2)> h
Hashtable(136604296)
stratego> <hashtable-get("one")> h
[2,1]
stratego> <hashtable-pop(|"one")> h
Hashtable(136604296)
stratego> <hashtable-get(|"one")> h
[1]
stratego> <hashtable-remove(|"one")> h
Hashtable(136604296)
stratego> <hashtable-values> h
[]

5.2. Indexed Sets

The library provides a rather feature complete implementation of indexed sets, based on hashtables. A lightweight implementation of sets, based on lists, is explained in the chapter on lists.

Similar to hashtables, indexed sets are created with the new-iset strategy, copied with iset-copy and destroyed with iset-destroy.

stratego> new-iset => i
IndexedSet(136662256)

The resulting term, IndexedSet(136662256), is a handle to the actual indexed set, which can only be manipulated through the iset-* strategies.

Adding a single element to a set is done with iset-add(|e), whereas an entire list can be added with the iset-addlist(|es). Its elements can be returned as a list using iset-elements.

stratego> <iset-addlist(|[1,2,3,4,4])> i
IndexedSet(136662256)
stratego> iset-elements
[1,2,3,4]

Notice that the result is indeed a set: every value is only represented once.

Using iset-get-index(|e), the index of a given element e can be found. Similarly, iset-get-elem(|i) is used to get the value for a particular index.

stratego> <iset-get-index(|3)> i
2
stratego> <iset-get-elem(|3)> i
4

Note that the indexes start at 0.

The set intersection between two sets can be computed with the iset-isect(|set2) strategy. The strategy iset-union(|set2) calculates the union of two sets, whereas iset-subset(|set2) checks if one set is a subset of another. Equality between two sets is checked by iset-eq(|set2). These strategies are all used in a similar way:

stratego> <iset-eq(|set2)> set1

A single element can be removed from the set with iset-remove(|e). iset-clear will remove all elements in a set, thus emptying it.