dict

Key/Value Dictionaries — machines/dict.shoddy

Summary

dict gives you a dictionary: a bag of values, each one filed under a key you choose, so you can put a value in under some name and fetch it straight back later by that same name. Look up "ADA" and get 96; look up "LIN" and get 78. A key can be anything Shoddy can compare with = — a number, a string, a boolean, even a whole record. Each key holds one value at a time, so putting a new value under a key that's already there quietly replaces the old one. Underneath, a dictionary is just an ordinary list of key/value pairs, which makes it plain, honest, and easy to reason about. Everything is pure: DictPut and DictDel don't change the dictionary you hand them. They hand you back a new one with the change made, and the old one carries on unbothered.

A Brief History of Dictionaries

The idea of filing a value under a key is older than computers — it's what a real dictionary does (look up a word, read its meaning), what an address book does, what the index at the back of a book does. Computing borrowed the word early and never gave it back. Different languages call the same idea different things: a map, a hash, an associative array, a dictionary. They all mean the same promise: hand me a key, I'll hand you the value that goes with it.

The way this machine does it is the oldest way there is. In the LISP world of the late 1950s and 1960s, before anyone had fancy machinery for the job, people kept key/value data in an association list — literally a list of little pairs, each pair holding a key and its value. To find a key you walked the list from the front, comparing as you went, and stopped at the first pair whose key matched. That's it. No hashing, no trees, no cleverness. It was easy to build, easy to understand, and — for the short lists LISP programs usually kept — perfectly quick. The association list has never really died; it's still exactly the right tool when you only have a handful of things to file away, and it's what you're looking at here.

Later, as programs grew and dictionaries got big, cleverer machinery arrived. The hash table scatters keys into numbered buckets, so a lookup jumps almost straight to the answer instead of walking the whole list. Various balanced trees keep keys in sorted order. Those are what most languages hand you today when you ask for a dictionary. This machine doesn't bother with any of that — and that's a deliberate choice. A list of pairs is honest about what it is: slow in the way a stack of paper is slow, fine at the sizes it's meant for, and simple enough that you can read the whole implementation in one sitting. Shoddy by name. If a program ever genuinely needs dictionaries with thousands of entries, a hashed version could slot in behind these very same words, and nothing that calls them would need to change a line.

Why It's Useful

All the time, a program needs to remember "the thing that goes with this other thing." The price for each product code. The score for each player. How many times each word appeared. A setting for each option name. You could keep two lists side by side — one of names, one of values — and promise yourself you'll always keep them lined up, but that's a promise you'll break by Tuesday. A dictionary keeps the pairing for you: one place, one lookup, no bookkeeping. Reach for dict whenever you're tempted to say "for each X, remember its Y" — a lookup table, a tally, a little pile of named settings. It fetches Y back when you name X, without you hunting through a list yourself. It's built for the small stuff: a few dozen or a few hundred entries, held in memory while your program runs. (If you need to remember things between runs and look them up on disk by key, that's what isam is for.)

User's Guide

A dictionary starts as an empty list, { }. You add to it with DictPut, which takes the dictionary, a key, and a value, and hands you back a new dictionary with that pairing added. Because everything is pure, the usual shape is to keep the newest dictionary in a variable and feed it into the next call — the same way you'd build up any immutable value in Shoddy.

Include "dict.shoddy"

Def Main()
    Let d = DictPut(DictPut({ }, "ADA", 96), "LIN", 78)

    Print(DictGet(d, "ADA"))              ' 96
    Print(DictHas(d, "GRACE"))            ' False
    Print(DictGetOr(d, "GRACE", 0))       ' 0   (no such key, so the default)

    Let d2 = DictPut(d, "ADA", 100)       ' same key again: replaces 96
    Print(DictGet(d2, "ADA"))             ' 100

    Let d3 = DictDel(d2, "LIN")           ' remove LIN
    Each(DictKeys(d3), Fn(k) => Print(k)) ' ADA

A few things worth remembering:

One value per key. Putting a value under a key that's already in the dictionary replaces what was there — a dictionary never holds two values under the same key. If you want the old one, hold onto the old dictionary; DictPut left it untouched.
Looking up a missing key stops your program. DictGet raises an error if the key isn't there. If a key might be missing, check first with DictHas, or use DictGetOr, which hands back a default of your choosing instead of stopping.
Deleting a key that isn't there is harmless. DictDel simply gives you back a dictionary without that key — whether or not it was ever in there — so you never have to check before removing.
Keys can be more than strings. Because keys are compared with plain =, you can file values under numbers, booleans, or records just as happily as under strings. Whatever you can compare, you can use as a key.
Keep it small. Every lookup walks the list from the front, so a dictionary of ten thousand entries will be slow. That's by design — see below. For a few hundred entries you'll never notice.

Under the Hood

You don't need any of this to use the machine — it's here for the curious.

A dictionary is nothing more than a List Of Pair, built on the Pair type from seq: each pair holds a key in its Fst and the matching value in its Snd. The empty dictionary is the empty list { }, and there is no wrapper type, no hidden state, no index — what you see is the whole thing. That plainness is the point.

Every operation is built from ordinary seq words over that list. DictHas is Any with a test that checks each pair's Fst against your key. DictGet walks the list by hand, comparing the front pair's key and recursing into the rest until it either matches or runs off the end (at which point it raises DICTGET: KEY NOT FOUND). DictDel is Filter keeping every pair whose key isn't yours, and DictPut is delightfully lazy: it deletes the key first, then prepends a fresh pair to the front. That is how "put" manages to replace rather than duplicate, and why the newest value ends up at the head of the list. DictKeys and DictVals are just Map(d, Fst) and Map(d, Snd).

What it costs. Because a lookup walks the list front to back, comparing keys one at a time until it finds a match, the work grows in step with the number of entries: this is a linear scan. Ten entries, up to ten comparisons; a thousand entries, up to a thousand. Every one of the words here — DictHas, DictGet, DictDel, even DictPut (which deletes before it prepends) — pays that same cost. A hash table would turn most of those into a single jump regardless of size; a sorted tree would turn them into a handful of comparisons. A list of pairs turns them into "read the whole thing." That is slower, and it is on purpose. At the sizes this machine is meant for, the simplicity is worth more than the speed, and if it ever isn't, a faster engine can hide behind the same words without a single caller noticing. Shoddy by name.

Word Reference

Every word, over the Pair type from seq

Building and changing

Word	Description
DictPut(d, k, v)	Files value `v` under key `k`, handing you back a new dictionary. If `k` was already in `d`, its old value is replaced — a key never holds two values. The dictionary you passed in is left unchanged.
DictDel(d, k)	Hands you back a new dictionary with key `k` removed. Harmless if `k` wasn't there to begin with — you get back a dictionary without it either way. The original is unchanged.

Looking things up

Word	Description
DictHas(d, k)	True or False: is there a value filed under key `k`? Good to check before a lookup that might miss.
DictGet(d, k)	Gives you the value filed under key `k`. Stops the program with an error (`DICTGET: KEY NOT FOUND`) if that key isn't there.
DictGetOr(d, k, dflt)	Same as `DictGet`, but hands back `dflt` instead of an error when the key is missing.

Reading it all out

Word	Description
DictKeys(d)	Every key in the dictionary, as a list.
DictVals(d)	Every value in the dictionary, as a list, lined up with the keys `DictKeys` gives you.

Who Uses It

	User	How
	csv	A row zipped with its header IS an association list, which is exactly what `CsvPairs` hands back.
	html	`DictHas` and `DictGet` read an element's attribute list.
	https	HTTP headers are an association list too, so `HttpHeader` is `DictGetOr` with the name lowercased first.
	json	A JSON object's members are an association list, so `JGet` and `JPut` are `DictGet` and `DictPut` wearing a hat.
	reckoner	The registers are an association list, exactly as dict already shapes one.
	tally	A spec file is a dictionary: `SpecGet` and `SpecGetOr` are `DictGet` and `DictGetOr` with the key folded to upper case.
	xml	An element's attributes are an association list too, so `XAttr` and `XPutAttr` are the same two words in another hat.

The Machines It Uses

	Machine	Why
	seq	`Any` answers the has-key question over the pair list.