-
Notifications
You must be signed in to change notification settings - Fork 107
TM015 String Dictionaries
Pyret string dictionaries come in two “brands”: immutable and mutable. To use them in a Pyret environment (file or repl),
import string-dict as SD
In the following, for convenience, we often abbreviate dictionary as dict, immutable string dictionary as SD (or ISD, if we want to emphasize its immutablity); and mutable string dictionary as MSD. The primary string-dict datatype is the immutable, and immutability is implied if no qualifier is used.
To create an empty ISD, do
isd1 = SD.make-string-dict()
To create an ISD with some initialized contents, do
isd2 = [SD.string-dict: "a", 15, "b", 10]
This creates an ISD that maps "a" to 15 and "b" to 10.
The strings "a" and "b" are the keys of the string dict. Their
corresponding values are 15 and 10. These latter can be any
Pyret values. Keys must be Pyret strings.
The corresponding constructions for MSDs are:
msd1 = SD.make-mutable-string-dict() msd2 = [SD.mutable-string-dict: "a", 15, "b", 10]
|
Note
|
Implementation: A string dict is implemented with an “underlying” JavaScript object. At the initialization stage, the underlying object is either empty (if an empty string dict was created) or a simple hash that maps the initial keys to their initialized values. This holds for ISDs and MSDs. The underlying object representation starts to differ for the two brands as more keys are added to the string dict. |
|
Note
|
Nomenclature: ISDs and MSDs have matching methods for accessing and
querying them, but with slightly different signatures befitting
their different goals. To emphasize this, the MSD method names
have a -now suffix.
|
A string dict’s get-value method takes a key as argument and returns
its value if found.
If the dict does not map the key to a value, an error is raised.
In addition, there is a get method that returns an option: The
option contains the key’s value, if found, or an empty option, if
the there is no value.
isd1 = [SD.string-dict: "a", 15]
isd1.get-value("a") => 15
isd1.get-value("b") =e=> Key b not found
isd1.get("a").or-else(42) => 15
isd1.get("b").or-else(42) => 42
msd1 = [SD.mutable-string-dict: "a", 15]
msd1.get-value-now("a") => 15
msd1.get-value-now("b") =e=> Key b not found
msd1.get-now("a").or-else(42) => 15
msd1.get-now("b").or-else(42) => 42
|
Note
|
Implementation: See the note for set below.
|
An ISD’s set method returns a new ISD that
differs from the original ISD only in that it maps the key to the
new value.
isd1 = [SD.string-dict: "a", 15]
isd1.get-value("a") => 15
isd1.get-value("b") =e=> Key b not found
isd2 = isd1.set("a", 20)
isd3 = isd2.set("b", 25)
isd3.get-value("a") => 20
isd3.get-value("b") => 25
isd2.get-value("a") => 20
isd2.get-value("b") =e=> Key b not found
isd1.get-value("a") => 15
isd1.get-value("b") =e=> Key b not found
An MSD’s set-now takes a key and a new value, and maps the
key in the dict to the new value. If the key was already mapped,
the old mapping is replaced. Otherwise, a new mapping is created.
msd2.set-now() returns mothing. It is performed purely for
its side effect.
msd1 = [SD.mutable-string-dict: "a", 15]
msd1.get-value-now("a") => 15
msd1.get-value-now("b") =e=> Key b not found
msd1.set-now("a", 20)
msd1.set-now("b", 25)
msd1.get-value-now("a") => 20
msd1.get-value-now("b") => 25
|
Note
|
Implementation: An MSD’s underlying object simply
updates itself on a set-now to include the new mapping of the key,
by either modifying an existing mapping, or adding a new one.
|
An
ISD cannot afford to do this, as the original ISD must be
preserved. To this end, an ISD set uses a new underlying object
that inherits from the original underlying object. The new
key mapping is added to this new object.
This requires that the ISD and MSD get[-value] be implemented
differently.
An MSD’s get[-value]-now can retrieve the
key value from the underlying object’s own properties. An ISD’s
get[-value], on the other hand, may have to search the prototype chain
of the underlying object in order to arrive at the key’s mapping.
As an optimization to reduce the access time for subsequent
get[-value]`s, an ISD’s `get[-value], once it finds its key in the prototype
chain, adds the mapping directly to the underlying object.
|
Note
|
Time complexity:
For MSDs, set-now and get[-value]-now directly translate to
object access on a flat yet dynamic JavaScript object. The
complexity of the Pyret set-now and get[-value]-now therefore mirrors JavaScript’s
own access complexity. Dynamically growable objects may not give
O(1) access in general, but an [implementation note
from the Google V8
team](https://developers.google.com/v8/design#prop_access)
suggests otherwise.
|
A string dict’s has-key method returns a boolean indicating if
the argument key is present or not in the dict.
isd1 = [SD.string-dict: "a", 15]
isd2.has-key("a") => true
isd2.has-key("z") => false
msd1 = [SD.mutable-string-dict: "a", 15]
msd2.has-key-now("a") => true
msd2.has-key-now("z") => false
|
Note
|
Implementation: For an ISD, has-key will do the same
optimization as get[-value]: If the key is in the prototype chain, it
is promoted to the underlying object.
|
A string dict’s keys method returns the set of all the keys defined in the
dict:
isd1 = [SD.string-dict: "a", 15, "b", 10]
isd1.keys() => [tree-set: "a", "b"]
msd1 = [SD.mutable-string-dict: "a", 15, "b", 10]
msd1.keys-now() => [tree-set: "a", "b"]
An ISD’s remove method returns a new ISD without the argument
key.
isd1 = [SD.string-dict: "a", 15, "b", 10]
isd2 = isd1.remove("a")
isd2.get-value("a") =e=> Key a not found
isd1.get-value("a") => 15
An MSD’s remove-now method deletes the argument key from the
MSD. It returns nothing, i.e., it is performed purely for its
side effect.
msd1 = [SD.mutable-string-dict: "a", 15, "b", 10]
msd1.remove-now("a")
msd1.get-value-now("a") =e=> Key a not found
|
Note
|
Implementation: An MSD’s remove simply deletes the
key from the underlying object. An ISD can’t afford to do this,
so it creates a new mapping for the key that maps it to
undefined.
|
A string dict’s count method returns the number of defined keys
in it.
isd1 = [SD.string-dict: "a", 15, "b", 10, "c", 5]
isd1.count() => 3
msd1 = [SD.mutable-string-dict: "a", 15, "b", 10]
msd1.count-now() => 2
An ISD’s unfreeze method returns a new MSD that has the same
keys and values as the ISD.
isd1 = [SD.string-dict: "a", 15, "b", 10, "c", 5]
msd1 = isd1.freeze()
msd1.get-value-now("c") => 5
msd1.count() => 3
Another possible name for this method: defrost.
An MSD’s seal method returns a sealed version of the MSD. A
sealed MSD allows access (get-now, get-value-now) but not modification
(set-now, remove-now).
msd1 = [SD.mutable-string-dict: "a", 15, "b", 10] msd2 = msd1.seal()
msd2.get-value-now("a") => 15
msd2.set-now("a", 24) =e=> Cannot modify sealed string dict
However, a sealed string dict can see modifications performed on the unsealed version.
msd1.set-now("a", 24)
msd2.get-value-now("a") => 24
An MSD’s freeze method returns a new ISD that has the same
keys and values as the MSD.
msd1 = [SD.mutable-string-dict: "a", 15, "b", 10]
isd1 = msd1.freeze()
isd1.get-value("a") => 15
isd1.count() => 2
Two ISDs are “equal” iff they have the same keys bound to the same values. Similarly for two MSDs. An ISD is not equal to an MSD even if the two have the same key/values.
isd1 = [SD.string-dict: "a", 15, "b", 10]
isd2 = [SD.string-dict: "a", 15]
isd3 = isd2.set("b", 10)
isd1 == isd2 => false isd1 == isd3 => true
msd1 = [SD.mutable-string-dict: "a", 15, "b", 10]
msd2 = [SD.mutable-string-dict: "a", 15]
msd3 = [SD.mutable-string-dict: "a", 15]
msd2.set("b", 10)
msd1 == msd2 => true msd1 == msd3 => false