11. Maps and strings

What this is for

You print a map for a log line. The test asserts on the output. It passes on your machine, passes in review, and fails in CI — not always, just often enough that somebody adds a retry.

The cause is that in most languages iteration order is whatever the hash function did. Go randomises it deliberately, so nobody can depend on it. Rust randomises its hash seed per process, so the order differs between runs. Both of those are admissions: hash order leaked into programs and then broke them, and the only fix left was to make the leak loud.

Burxt takes the other end. Iteration order is insertion order. Not unspecified, not arbitrary, not do not rely on it — defined.

That is not taste. The thesis of this language is that the same inputs produce the same bytes — it is what the byte-identical self-hosting fixpoint exists to prove — and a container whose iteration order depends on a hash function’s internals is a determinism hazard sitting in the middle of it. Printing a map, serialising one, or hashing a structure containing one would all become run-dependent, and none of those should be.

Think of a cloakroom

You hand over a coat and get a numbered ticket. Later you hand back the ticket and get the coat.

And the coats hang on the rail in the order they arrived. Not in an order the cloakroom attendant finds convenient, and certainly not in a different order each evening — because when you walk past the rail looking for yours, an order you can predict is the entire point.

A step closer

The rail is two arrays rather than buckets of lists.

entries holds the coats in arrival order, and that is what iteration walks. slots is the ticket table — open addressed, linear probing, holding an index into entries plus one, so that a zero can mean empty without a sentinel constant. A removed entry keeps its place as a tombstone so everything after it holds its position, and count() answers the ones that are still coats.

That shape is right here for a reason particular to Burxt: there is no per-entry allocation at all. Every allocation lands in a region, and a region is a bump pointer — so a container that allocated once per insertion would make the region grow for no reason.

In code

Using one

use "lib/map.bx";

let mutable counts: Map<String, Int> = map_new();
let added: Int = counts.set("apples", 3);
let again: Int = counts.set("pears", 7);

print(counts.count());              // 2
print(counts.get("apples", 0));     // 3
print(counts.get("plums", 0));      // 0 — the fallback
print(counts.has("pears"));         // true

let keys: [String] = counts.keys();     // in the order they went in
for k in keys {
    print(k);
}

let removed: Bool = counts.remove("apples");   // true; false if it was not there
print(removed);

lib/map.bx is a library file, like lib/option.bx and lib/result.bx. Ordinary Burxt written with the generics, and the only compiler support it needs is one builtin, hash. If a map had needed a keyword, those generics would not be real.

Reading: get or find

Two ways, and the difference is whether a default is the right answer.

use "lib/map.bx";

let mutable counts: Map<String, Int> = map_new();
let added: Int = counts.set("pears", 7);

print(counts.get("plums", 0));          // the value, or the fallback you gave

match counts.find("pears") {            // the value, or None
    None => { print("no pears"); }
    Some(n) => { print(n); }
}

get is for when a default is genuinely right — a missing count is zero. find answers an Option<V>, the one type that cannot be read without saying what happens when there is nothing there.

find could not be written until v0.0.118, and the reason shows how these pieces lean on each other: a variant payload had to be a scalar, so Option<Point> was refused, so an Option<V> return would have restricted map values to scalars. get with a fallback was the honest answer while that was true. When the payload rule lifted, find was three lines.

Keys are Equatable

Int, Bool, String, Decimal — exactly the types == works on, which is the bound the generics page already describes. A key needs equality and a hash, and the set of types that have equality is the set that can have one. So there is no Hashable bound: it would name the same four types twice.

use "lib/map.bx";

let mutable by_number: Map<Int, String> = map_new();
let one: Int = by_number.set(1, "one");
print(by_number.get(1, "?"));           // one

A class as a key is refused. It would need structural hashing, which needs a per-type walk, which needs either a derive mechanism or an interface with a method — both larger than this container. For a compound key, build a String from the parts.

Values have no such restriction:

use "lib/map.bx";

class Point { x: Int, y: Int }

let mutable places: Map<String, Point> = map_new();
let put: Int = places.set("origin", Point { x: 1, y: 2 });
let here: Point = places.get("origin", Point { x: 0, y: 0 });
print(here.y);

Everything is a method except map_new

function map_new<K: Equatable, V>() -> Map<K, V>                     // an empty map
function (mutable self: Map<K, V>) set(key: K, value: V) -> Int       // 1 if new, 0 if it replaced
function (self: Map<K, V>) get(key: K, fallback: V) -> V
function (self: Map<K, V>) find(key: K) -> Option<V>
function (self: Map<K, V>) has(key: K) -> Bool
function (mutable self: Map<K, V>) remove(key: K) -> Bool
function (self: Map<K, V>) count() -> Int
function (self: Map<K, V>) keys() -> [K]

Methods rather than free functions, and that was forced rather than chosen: Burxt has no writable parameters, so a container that changes has to change through mutable self. The API is better for it — counts.set("k", 1) reads better than map_set(counts, "k", 1) — which is the usual way a real constraint turns out to have been pointing at the nicer design all along.

set answers 1 when the key is new and 0 when it replaced a value, so counting distinct keys needs no second lookup.

Strings

A String is bytes. Not a rope, not a UTF-16 array, not an object with a hidden encoding field.

print(len("hello"));                 // 5 — bytes, not characters
print(byte_at("hello", 0));          // 104
print(substring("hello", 1, 3));     // ell — a start and a LENGTH
print("total: " + to_string(3));     // joining builds a new String

Interpolation is a join written differently — "total: {amount}" — and + on two Strings builds a new one, which means it allocates, which means Memory applies.

lib/string.bx is where the rest lives, and it is ordinary Burxt too:

Those last two are a pair on purpose. string_to_int used to be the only one and it answered 0 for garbage — which is the silent-wrong-answer shape this whole language is against, and it took a real bug to notice. Now the fallback is either named by the caller or handed back as an Option.

One honest gap: there is no case conversion yet. The split separator was a single byte until v0.0.189 — so ", " and "\r\n" could not be split on at all — and it is a String now.

Why it is built this way

Because a hash order that leaks into a program is a bug you find later. Go randomises map iteration deliberately and Rust randomises its hash seed per process, and both are admissions that programs came to depend on an order nobody promised. A language whose whole argument is that a wrong answer must not be plausible cannot ship a container whose output order changes between runs.

Because it needs no keyword. Map<K, V> is one file of ordinary Burxt, and the only compiler support it asks for is hash(x). If a map had needed a keyword, the generics were not real.

The shape, and why it is that shape

There is no per-entry allocation: a map is the two arrays in the diagram and nothing else. That matters more here than in most languages, because every allocation lands in a region and a region is a bump pointer — a container that allocated once per insertion would make the region grow for nothing.

Growing the table re-places the cards and drops the tombstones. It never reorders the pegs.

What it costs

A tombstone stays. Removing an entry keeps its place so everything after it holds its insertion position. count() answers the live entries; the storage does not shrink until the region goes.

Keys are Equatable — Int, Bool, String, Decimal. Not a class of yours, because == does not work on one.

A String is bytes. len counts bytes and byte_at reads one, so anything beyond ASCII is a byte-by-byte question you have to answer yourself. There is no .chars() yet.

What is deliberately absent

No unwrap. Same reason as lib/option.bx: it is a decision disguised as a convenience.

No map, filter or each. They need a function as a value, and a closure needs an owner for its captured state — a memory question, not a syntax one. Iterate keys() with a for loop, which cannot capture anything by accident.

No HashDoS protection. hash is deterministic and unseeded, because a seeded hash cannot iterate in a defined order, and that is the whole point of the container. A caller feeding attacker-chosen keys can force collisions and turn O(1) into O(n). If you need that guarded the answer will be a second constructor — map_seeded(seed) — so the program that needs it says it needs it, rather than every program paying for it. A security property should be visible in the code that has it.

When you reach for it

for iterates a named array, so bind keys() first: a method call in the for header would be recomputed on every pass, and the compiler refuses it rather than doing that quietly.

Examples

Insertion order, including an overwrite. apple is set twice and keeps its original place:

use "lib/map.bx";

let mutable counts: Map<String, Int> = map_new();
let a: Int = counts.set("pear", 2);
let b: Int = counts.set("apple", 5);
let c: Int = counts.set("fig", 1);
let d: Int = counts.set("apple", 6);

print(counts.count());
let names: [String] = counts.keys();
for key in names {
    print(key + " " + to_string(counts.get(key, 0)));
}

3
pear 2
apple 6
fig 1

Three live entries, not four. apple holds its second position with its new value — which is the behaviour you would have assumed, and the one most languages do not give you.

And the refusal that keeps a loop honest, if you skip the binding:

use "lib/map.bx";

let mutable counts: Map<String, Int> = map_new();
let a: Int = counts.set("pear", 2);
for key in counts.keys() {
    print(key);
}

error: `for` iterates a named array, and this is a method call: its result would be recomputed on every pass. Bind it first — `let items = ...;` — and iterate that.
 --> counts.bx:5:26
  |
5 | for key in counts.keys() {
  |                          ^

Next

Tools and agents — burxt mcp-schema, which derives an agent’s tool schema from the preconditions so the two cannot drift, and burxt review, which answers what a change did to what a program promises.

Or the reference for every keyword, builtin, command and standard-library function — generated by reading the compiler, with a search box.

The design record carries the reasoning behind every refusal above: spec/1.0/M11-MAPS.md.