The standard library, part 4: a dictionary
A list finds a value by its position. A dict finds a value by its key: a name, or a number that is not a position. This page adds the type, and follows it through every stage of the compiler, because a new type touches all of them.
cargo run -- run examples/faults.zeno
23: over temperature (x4)
17: over voltage (x2)
40: fan stalled (x1)
99: a code nobody wrote down (x1)
most often: over temperature
true false
the fan stalled 1 time
left out 1 reading with an unknown code
[23: 4, 17: 2, 40: 1]
["mode": "manual", "unit": "celsius", "limit": "85"]
["mode", "unit", "limit"]
["manual", "celsius", "85"]
3
examples/faults.zeno counts the fault
codes a device has sent and looks up what each one means. The
decisions are 6.29 to 6.40 in decisions.md.
A dict first held only numbers, bools and text. It now holds anything a list can, and a loop can be given the key and the value together. That is the second half of this page, Any value, and a loop with two names, with decisions 10.11 to 10.14.
What a dict does
let ages = ["Ada": 36, "Alan": 41] # written out
let seen: dict[int, int] = [:] # empty: the type says what it will hold
| Written | Gives |
|---|---|
ages["Ada"] |
the value under that key. A key that is not there is a KeyError |
ages["Grace"] = 45 |
stores: adds the key, or replaces its value |
"Ada" in ages, "Bob" not in ages |
bool: is there such a key? |
len(ages) |
how many keys |
for name in ages { } |
each key, in the order they were put in |
for name, age in ages { } |
each key and what is under it |
ages.get("Bob") |
the value, or none |
ages.get("Bob", 0) |
the value, or the second argument |
ages.pop("Alan") |
takes the key out and gives its value |
ages.keys(), ages.values() |
a new list of each |
ages.clear() |
empties it |
a == b |
true when the same keys have the same values, in any order |
print(ages) |
["Ada": 36, "Alan": 41], as it is written |
A key is a str or an int. A value is anything a list can hold,
except none. All the keys of one dict are one type and so are all
the values, so dict[str, int] says everything about what is inside.
Three ways to ask for a key
print(ages["Ada"]) # I know it is there. If not: KeyError
let age = ages.get("Bob") # it may not be: int or none
if "Bob" in ages { ... } # is it?
Zeno does not answer none or 0 for a key that was never stored
when you wrote ages["Bob"]. A misspelt key would then be a wrong
total at the end of the program instead of an error at the line with
the spelling mistake (6.34).
One bracket for both
Braces in Zeno are always a block of code, and square brackets always hold values. So a dict is written in square brackets, and what makes it a dict is the colon:
[1, 2, 3] # a list
["a": 1, "b": 2] # a dict
[] # the empty list
[:] # the empty dict
How it is built
A new type goes through every stage. Here they are in order, with the place in the source where each one does its part.
The parser: which one is it?
list in src/parser.rs is called when the parser meets [. It reads
one expression and looks at what follows:
[ ] an empty list
[ : ] an empty dict
[ expr , or ] a list
[ expr : a dict: read the value, then more `key: value`
One token decides, and the parser never has to go back. The tree gets
a new node, ExprKind::Dict, which holds the pairs. A list item in the
middle of a dict, or the other way round, gets a message that says how
an entry is written:
error: every entry of a dict is written `key: value`, and this one has no `:`
The checker: what does it hold?
Ty::Dict(key, value) in src/checker.rs is the type. dict_written
works out the type of a dict that is written out: it looks at each
pair, refuses a key that is not text or an int, and refuses a pair that
does not match the ones before it.
error: the values of a dict are all of one type. This one is float, and the
ones before it are int
It also refuses the same key written twice, which in any other language quietly keeps the second:
error: this key is written twice in the dict. A dict has each key once, so
the second would replace the first. Take one of them out
Everything else is a few lines each, next to what a list does there:
ages["Ada"] checks the key against the key type and gives the value
type; a loop variable gets the key type; get with one argument gives
V or none, which the rest of the checker already knows must be tested
before it is used.
zeno run and the VM: a Vec and a HashMap
Dict in src/value.rs:
pub struct Dict {
entries: Vec<(Value, Value)>, // in the order the keys were put in
places: HashMap<Key, usize>, // where each key is in `entries`
}
The Vec gives the order, and the HashMap finds a key without
looking at all of them. Key is a small enum with two cases, Int
and Str, because a Zeno Value in general cannot be hashed (a float
has no sensible hash) and a key never needs to be.
The VM has one new instruction. zeno bytecode shows it:
0000 1 Const 0 ; "Ada"
0001 | Const 1 ; 36
0002 | Const 2 ; "Alan"
0003 | Const 3 ; 41
0004 | Dict 2
Dict 2 takes two pairs off the stack and leaves one dict. Reading and
storing use GetIndex and SetIndex, which lists already had: the
work is in ops::item and ops::set_item, which now look at what kind
of value they were handed.
The C runtime: a hash table
A compiled program cannot lean on Rust's HashMap, so src/runtime.c
has its own, under the heading "Dicts". It is about 300 lines, half
of them comments.
typedef struct {
zeno_list *keys;
zeno_list *values;
int64_t *index; /* position + 1 of a key in `keys`, or 0 for an empty place */
int64_t room; /* how many places `index` has: 0, or a power of two */
char key_kind;
char value_kind;
} zeno_dict;
The keys are in one list and the values in another, side by side.
values->items[i] belongs to keys->items[i]. Those two lists are the
order, and they are ordinary lists, so keys(), values() and the
for loop are code that was already there.
The index is what makes finding fast:
keys "Ada" "Alan" "Grace"
values 36 41 45
index [0, 3, 0, 0, 1, 0, 2, 0]
To find "Alan":
- Work out a number from the key, its hash. For text this is FNV-1a: start with a fixed number, and for each byte, XOR it in and multiply by a prime. Two different texts almost never give the same number.
- Keep the low bits of the hash. With 8 places that is a number from 0 to 7: the place to start at.
- Look at that place in the index. 0 means empty: the key is not in the dict. Otherwise it is a position (plus one). Is the key at that position the one we want? If so, found. If not, two keys landed on the same place: step to the next place and look again.
The index always has at least twice as many places as there are keys.
When a store would make it more than half full, zeno_dict_index
makes one twice the size and puts every key in again. That is why step
3 ends quickly: half the places are empty, so a run of full ones is
short.
pop takes the key and the value out of the two lists, which moves
everything after them down by one. Every position in the index after
that point is now wrong, so the index is written again from the list.
That is the price of keeping the order (6.33).
The two letters, key_kind and value_kind, say what the dict holds:
's' text, 'i' int, 'f' float, 'b' bool. With them the runtime
can compare two keys, show a dict and compare two dicts without help
from the compiler.
The C backend
let ages = ["Ada": 36, "Alan": 41] and three lines that use it
become:
z_ages = zeno_dict_of('s', 'i', 2, (zeno_slot){.s = "Ada"}, (zeno_slot){.i = 36},
(zeno_slot){.s = "Alan"}, (zeno_slot){.i = 41});
zeno_dict_set(z_ages, (zeno_slot){.s = "Grace"}, (zeno_slot){.i = t1});
... zeno_dict_at(z_ages, (zeno_slot){.s = "Ada"}, 3, 7).i ...
... (zeno_dict_find(z_ages, (zeno_slot){.s = "Bob"}) >= 0) ...
A zeno_slot is the 64-bit box that an item of a list already
travels in. The 3, 7 is the line and column, for the KeyError.
A loop over a dict is a loop over a list of its keys, made for the loop:
zeno_list *t2 = zeno_dict_keys(z_ages);
for (int64_t t3 = 0; t3 < t2->len; t3++) {
const char *z_name = t2->items[t3].s;
...
}
zeno_list_drop(t2);
So the body can add keys and take them out, and the loop still walks
the keys it began with. The work is in open_list_loop in
src/emit_c.rs: a dict is turned into its list of keys, and the code
for a list takes over.
The LLVM backend
The same calls, written as IR. let ages = ["Ada": 36] and
print(ages["Ada"]):
%t1 = call ptr @zeno_dict_new(i32 115, i32 105) ; 's' and 'i'
%t2 = ptrtoint ptr @.str.1 to i64 ; "Ada" as a slot
call void @zeno_dict_set(ptr %t1, i64 %t2, i64 36)
store ptr %t1, ptr @z_ages
%t3 = load ptr, ptr @z_ages
%t4 = ptrtoint ptr @.str.1 to i64
%t5 = call i64 @zeno_dict_at(ptr %t3, i64 %t4, i32 2, i32 7)
115 and 105 are the letters s and i as numbers. One thing differs
from the C backend: get(key) on a dict of ints. The answer is an
int or none, which travels as a pair, a flag and a number. In C the
runtime gives back that pair as a struct. In IR the backend asks the
runtime where the key is (zeno_dict_find, which answers -1 for
"nowhere"), asks for the value there, and builds the pair itself with
insertvalue. It is the same trick find on a list uses.
With no collector
zeno build --no-collector has no collector to tidy up, so every
value has one owner that frees it (docs/one-owner.md). A dict follows
the rules a list follows. The checker needed a line in each place
where it says "a list has one owner": a dict has one too.
function tally(words: list[str]) -> dict[str, int] {
let seen: dict[str, int] = [:]
for word in words {
seen[word] = seen.get(word, 0) + 1
}
return seen # gives the dict to the caller
}
let counts = tally(["a", "b", "a"]) # `counts` is its owner now
print(counts)
# end of the block: the dict is freed
When the owner's block ends, the compiled program calls
zeno_dict_drop, which frees the two lists, the index and the dict.
Text needs one more thing. With no collector, whatever keeps text has
a copy of its own (docs/text.md). So a dict has its own copy of every
key and every value that is text, and zeno_dict_drop frees those as
well. Storing under a key the dict already has does not copy the key a
second time, and frees the old value.
zeno build --no-collector --memory examples/faults.zeno shows that
it adds up:
memory: 32 blocks made (1088 bytes), at most 784 bytes in use at once, no collector, 0 blocks left at the end
pool: 1104 bytes taken, in a pool of 32768
text: at most 148 bytes in use at once, in a room of 1024
In a firmware build
A key that is not there stops the program, as a bad index does:
let ages = ["Ada": 36]
print(ages["Bob"])
error: uncaught KeyError: this dict has no key "Bob"
--> ages.zeno:2:7
It cannot be caught there, and a try around it is refused when the
program is built, with a message that says so. A program that must not
stop asks first, with in or get.
Any value, and a loop with two names
cargo run -- run examples/channels.zeno
["voltage": [12.0, 13.0, 11.0], "current": [1.5, 3.5], "temperature": [40.0, 44.0], "humidity": [55.0]]
voltage: mean 12.0 over 3
current: mean 2.5 over 2
temperature: mean 42.0 over 2
humidity: mean 55.0 over 1
["low": 11.0, "high": 13.0] 3.5
voltage: reading 1 is 13.0, outside 11.5 to 12.5
voltage: reading 2 is 11.0, outside 11.5 to 12.5
current: reading 1 is 3.5, outside 0.0 to 3.0
humidity: nobody said what this may read
3 readings out of range
true Limit(low=11.5, high=13.5)
dropped [55.0] and kept ["voltage", "current", "temperature"]
examples/channels.zeno keeps the
readings of each channel in a list under the channel's name, and what
each channel may read as an object under the same name.
What can be under a key
let readings: dict[str, list[float]] = [:] # lists
let limits = ["voltage": Limit(11.5, 12.5)] # objects
let shapes: dict[str, Shape] = ["round": Circle(1.0)] # an interface
let ranges: dict[str, dict[str, float]] = [:] # dicts
let waits = ["blink": 500 ms] # quantities
let steps: dict[str, function(int) -> int] = [:] # functions
What is under a key is the thing itself, and not a copy:
readings["voltage"].append(12.0) # adds to the list in the dict
limits["voltage"].high = 13.5 # changes the object in the dict
One thing cannot be a value, and that is none (10.11). get gives
none for a key that is not there, and in a dict[str, int or none]
that answer would mean two things. The checker says so, and says what
to do: leave the key out.
A loop with two names
for channel, values in readings { # a dict: the key, and what is under it
for at, value in values { # a list: the position, and what is there
...
}
}
The rule is the same for both, and for text and a range as well: the
second name is what is at the first (10.12). In a dict, values is
readings[channel]. In a list, value is values[at]. Over
range(5, 8) the first name counts the trips from 0 and the second is
the number.
The pairs are as they were when the loop began, so the body may store into the dict and take keys out.
The parser and the tree
for_loop in src/parser.rs reads a name, and then a comma and a
second name if there is one. The node StmtKind::For has a new part,
second, which is None for the loop that was there before. Two
names that are the same, or three names, get a message that says what
two names are for.
The checker
pair_types in src/checker.rs answers what the two names are: the
key type and the value type for a dict, and int and the item type
for everything else. The rest is the loop that was there.
For the values, no_such_value is the one place that says what a dict
cannot hold. It is asked where a dict[...] type is written and where
a dict is written out.
A dict that is written out can be told what its values are by the
place it goes, as a list is (10.13). That is how
["round": Circle(1.0), "square": Square(2.0)] is a
dict[str, Shape] when it goes into one, and how a 200 becomes a
u8. expecting leaves a note for dict_written, which checks each
value against it.
In a generic, dict[K, V] is laid over the dict that is given, and
says what K and V are. Three functions learned about Ty::Dict
for that: mentions, bind and filled.
zeno run and the VM
ops::pairs in src/ops.rs gives the pairs of anything that can be
looped over: the entries of a dict, or each item with its position.
zeno run walks that list and sets two variables each trip.
The VM has three new instructions. zeno bytecode on
for name, age in ages { print(name, age) }:
0003 2 GetLocal 0 ; ages
0004 | ForStartPairs
0005 | Const 2 ; 0
0006 | ForNextPair 15
0007 | ForSecond 1
0008 3 Const 3 ; <function print>
0009 | GetLocal 4 ; name
0010 | GetLocal 5 ; age
0011 | Call 2
0012 | Pop 1
0013 2 Pop 2
0014 | Jump 6
0015 | Pop 3
ForStartPairs takes the dict off the stack and leaves two lists, the
values and the keys. With the position that makes three things under
the loop's variables. ForNextPair pushes the next key (or the
position, for a list) and moves the position on, or jumps to 15 when
there are no more. ForSecond pushes the value that goes with it.
The two values it pushes are the two variables, name and age.
The C backend
zeno_dict *t1 = z_ages;
zeno_list *t2 = zeno_dict_keys(t1);
zeno_list *t3 = zeno_dict_values(t1);
zeno_list *t4 = t2;
for (int64_t t5 = 0; t5 < t4->len; t5++) {
const char *z_name = t4->items[t5].s;
int64_t z_age = t3->items[t5].i;
...
}
zeno_list_drop(t4);
zeno_list_drop(t3);
A list of the values beside the list of the keys, and one position for both. Over a list there is nothing to make: the first name is the position the loop already had.
for (int64_t t7 = 0; t7 < t6->len; t7++) {
int64_t z_n = t6->items[t7].i;
int64_t z_at = t7;
A value that is a list or an object is a pointer in the dict's list of
values, with the kind letter 'p':
z_lists = zeno_dict_of('s', 'p', 1, (zeno_slot){.s = "a"}, (zeno_slot){.p = zeno_list_of(...)});
The runtime knows how to show and compare an int or a piece of text from its kind letter. It cannot know that for a pointer, so the compiler writes a function for each such type, as it already did for a list of them, and hands it over:
zeno_dict_str_with(z_lists, zeno_item_repr_list_float)
zeno_dict_eq_with(z_lists, z_lists, zeno_item_eq_list_float)
zeno_dict_str and zeno_dict_eq are those two with no function,
which means "go by the letter". The LLVM backend calls the same two
and builds the same loop, in open_loop in src/emit_llvm.rs.
With no collector
The loop with two names works there: the value is looked at, and the
two lists the loop made are freed when it ends, also when a break
or a return leaves it early.
Values that are lists or objects do not (10.14, a limit of version 0.1):
error: with no collector a value of a dict is an int, a float, a bool or
a str for now, and this is list[float]. Keep those in a list, and the
position of each in the dict
A dict of lists would own its lists, and every way into the dict would need a rule about who owns what comes out. Those rules exist for a list of owned items, and the decision lists what they would be for a dict. No program for a board has needed them yet.
What a dict cannot do yet
- A value cannot be
noneorT or none. Leave the key out (10.11). - With no collector a value is an int, a float, a bool, text, a sized number or a quantity (10.14).
- A key cannot be an enum case.
Things to try
-
Run
examples/faults.zeno. Then add a code toarrivedthat is already there, and one that is new. Where in the output does each show up, and why there? -
Write
let d = ["a": 1, "a": 2]and read the message. Then store the two one after the other, withd["a"] = 1andd["a"] = 2. Why is one refused and the other not (6.36)? -
Change
meanings[worst]in the example tomeanings[99]and run it. Then build it with--firmwareand run that. Now wrap the line intry/except KeyErrorand build both ways again. -
Write a function that takes a sentence and gives back a
dict[str, int]of how often each word is in it. Usesplit(). Print the word that comes most often. -
In a loop over a dict, add a new key on every trip. Does the loop ever end? Find the line in
open_list_loop(src/emit_c.rs) that makes it so, and the one insrc/ops.rs(items) that does the same forzeno run. -
Run
zeno bytecodeon a program withd["k"] = d.get("k", 0) + 1. Which instruction stores? Find where the VM runs it and follow it intoops::set_item. -
In
src/runtime.c, makezeno_dict_hashreturn 0 for every key. Runcargo test dict. Do the tests still pass? What has changed for a dict with ten thousand keys? Put it back. -
Build a program that fills a dict with 1000 int keys using
--no-collector --memory. How many bytes are in use at most? The index doubles each time it fills: which sizes did it go through? Then raiseZENO_POOL(docs/pool.md) and try 10000. -
poprewrites the whole index. Think of a way to take a key out without moving the ones after it (a "tombstone": a mark that says "something was here"). What would a loop andprintthen have to skip, and what wouldlencount? -
Run
examples/channels.zeno. Then changefor at, value in valuestofor value, at in valuesand read what the checker says aboutlimit.holds(value). Why does the order of the two names matter, and what is the one rule that says which is which (10.12)? -
Write
let d: dict[str, int or none] = [:]and read the message. Then write a program that needs "this key has no value yet" and do it the way the message says. What doesgetgive for such a key? -
Give
Limita second class beside it,Band, and an interfaceCheckwithholdsthat both are. Makelimitsadict[str, Check]with one of each. What doeslimitshave to say on itsletline, and why can adict[str, Limit]that is made already not be passed where adict[str, Check]is wanted (10.13)? -
Run
zeno bytecodeon a loop with two names over a list, and compare it with the one over a dict above. Which instructions are the same? FindForNextPairinsrc/vm.rsand see what it pushes for each. -
Build
examples/channels.zenowith--no-collectorand read the two messages. Then change the program so that it builds: keep the lists in alist[list[float]]and the position of each in adict[str, int]. Which of the two programs is easier to get wrong, and where? -
Add a method
has(key)that means the same askey in d. Followgetthroughbuiltins.rs,checker.rs,emit_c.rsandemit_llvm.rs. Then take it out again: why is one way to ask better than two?
This page is docs/dict.md in the language repository.