Pieces of a Word
The sealed language package
This volume puts a machine that reads and writes English beside The World. Nothing in the valley is allowed to move while that happens: the ground rules, the animals, the genome, the creature network and the package that writes the world down all have to end this volume with the bytes they started with.
The new package is internal/lang, every piece of language machinery
in this volume lives there, and the five simulation packages plus the store are sealed
against it by a test that walks their import lines. The last volume made the same
kind of seal around SQL because a tick that waits on a socket has no budget. This volume
needs the rule at the slower end: a tick is a hundred milliseconds, while a sentence can
take seconds to come back.
Start with the ground, which has no creatures in it at all. A thousand valley-years of terrarium with an empty creature phase hooked into every one of its three million six hundred thousand ticks, folded down to two digests: one for the ground and everything standing on it at the end, one for a census taken every midsummer of all thousand years.
$ go run ./cmd/books -mode keep -years 1000
books: seed 5, 1000 years, an empty roster hooked into every tick
world df1c117e69bdf157 the terrarium's own, unmoved
census 75c77a67f6f430bb the terrarium's own, unmoved
Those two digests are the oldest figures in this book. They cover seed flight, germination, plant death, moisture, nutrient and where a founding generation lands, and the census half means a valley that arrived at the right ending by a different road would fail. Three and a half minutes of arithmetic for two digests is a fair price for a claim nobody has to take on trust.
Then the animals. Nineteen creatures founded on the herd stream, each stamped out of an identity genome, each handed a brain of its own, and two years of valley with nothing registered into the breeding seam. The right-hand column of that block is not somebody copying the left-hand one: those figures are constants inside the bench, and the word at the end of each line is a comparison the program made.
$ go run ./cmd/stamp -mode herd
stamp: 12x8 valley, tick 901, year 1 summer, 12 plants standing at 1517.5 grams
19 creatures founded on stream 12, each stamped from an identity
genome and given a brain of its own off stream 14
beast.Roster.Born is nil: nothing has registered a breeding pass into it
this run before the genome holds
creatures founded 19 19 yes
creatures struck off 17 17 yes
still walking after 6750 ticks 2 2 yes
first death tick 1044 on 9,5 tick 1044 on 9,5 yes
last death tick 3400 on 11,5 tick 3400 on 11,5 yes
grams in 46567.944597 46567.944597 yes
grams out 46567.944597 46567.944597 yes
the two ledgers differ by -1.455e-11, which is the last bits of the adding
Seventeen animals starve, and they starve on the ticks they have always starved on: the first on tick 1044 over cell 9,5 and the last on tick 3400 over 11,5. The grams close in and out at 46567.944597, which is the same number the ledger has closed on since the chapter that first weighed a valley.
The third is neither the ground nor a valley. Sixty-four genomes drawn off their own stream, four trials apiece, scored on grams eaten, every scorecard folded into one digest. A scorecard carries one column per thing a creature could choose to do, so it is the run that would catch a table that quietly grew a column.
$ go run ./cmd/score -mode spread | tail -18
the best of them 179.4530
the genome a quarter of the way down 40.0000
the middle one 4.8405
three quarters of the way down 0.0000
the worst of them 0.0000
the average 24.5807
genomes that ate anything at all 38
genomes that scored nothing whatever 26
grams the generation ate between them 1573.1642
grams of fodder it was offered 120320.0000
the share of the larder it found 1.31%
trials that ended in a store at nothing 129
creature-ticks over the ring of water 1885
creature-ticks past the last cell 0
digest of the scored generation e3cd4c94f2fa1612
Best still 179.4530, middle still 4.8405, average still 24.5807, twenty-six of the
sixty-four still scoring nothing whatever, and the generation still folding to
e3cd4c94f2fa1612. Three runs, three unrelated parts of the world, and not a
figure out of place on any of them.
Those three were not picked for being cheap. They were picked because they have no package in common past the module boundary: the first runs the terrarium with the creature phase emptied out, the second runs creatures over a valley with the breeding seam disconnected, and the third runs a scoring harness that is neither. A change that moved one of them and left the other two alone would be a change to one subsystem, and a change that moved all three would be a change to the arithmetic underneath all of them. Between them they leave very little room for a volume to have touched something quietly.
Now the rule that keeps them that way. The last volume's version of this test reads the
import lines of five packages and fails if any of them names the store. This one reads six
and fails if any of them names internal/lang, and the sixth is the store
itself, sealed against language on purpose: a vector arriving at a
database is a list of floats and a count of them, and the thing writing it down has no
need to know what produced it.
// internal/lang/rule_test.go
var sealed = []string{"sim", "terra", "beast", "gene", "mind", "store"}
func TestNoSealedPackageImportsLang(t *testing.T) {
const forbidden = "theworld/internal/lang"
fset := token.NewFileSet()
checked := 0
for _, pkg := range sealed {
dir := filepath.Join("..", pkg)
ents, err := os.ReadDir(dir)
if err != nil {
t.Fatalf("reading %s: %v", dir, err)
}
for _, e := range ents {
if e.IsDir() || !strings.HasSuffix(e.Name(), ".go") {
continue
}
path := filepath.Join(dir, e.Name())
f, err := parser.ParseFile(fset, path, nil, parser.ImportsOnly)
if err != nil {
t.Fatalf("parsing %s: %v", path, err)
}
checked++
for _, imp := range f.Imports {
p, err := strconv.Unquote(imp.Path.Value)
if err != nil {
t.Fatalf("%s: unreadable import %s", path, imp.Path.Value)
}
if p == forbidden {
t.Errorf("%s imports %s: a tick that can ask a model a question has no budget", path, forbidden)
}
}
}
}
if checked < 80 {
t.Fatalf("only %d files read across %v: the walk found less than the tree holds", checked, sealed)
}
t.Logf("%d files read across %d sealed packages, and not one of them names it", checked, len(sealed))
}$ go test ./internal/lang/ -run 'NoSealedPackageImportsLang' -v
=== RUN TestNoSealedPackageImportsLang
rule_test.go:65: 96 files read across 6 sealed packages, and not one of them names it
--- PASS: TestNoSealedPackageImportsLang (0.00s)
PASS
ok theworld/internal/lang 0.004s
The floor of eighty files is the part people leave out. A walk that finds nothing passes cheerfully, and a test that passes cheerfully after somebody moves a directory is worse than no test at all, because it is now evidence. Ninety-six files today, and the number only goes up.
With that settled, here is what the rest of the page is for. Nothing that reads text reads letters, and nothing that reads text reads words either. What a reader of language is handed is a list of integers, and there is a table that turns one into the other. A token is a run of bytes the table has a number for. That sentence is the whole subject of this chapter, and by the end of it you will have built the table, used it in both directions, and measured one sentence in the unit it defines.
The chronicle text corpus
A table like that has to be counted off some text, and there is a choice about which text. The usual answer is a scrape of everything: encyclopedias, forums, code, the lot. This world has something better to hand, and it is the only place in this volume where the subject of the book and the subject of the volume are the same object. Since the chapter that gave it a founding document, The World has been keeping a chronicle. Eleven rows written on the tick it was named, and one row a year for as long as it runs, each of them a finished English sentence with the world's own names already in it.
Two registers live in that file and they need telling apart before anything counts them. The eleven founding rows are an operator writing prose: full sentences, first person, a few hundred words of somebody deciding what things are going to be called. The eighty yearly rows are annalistic, which is the register a chronicle has always wanted: what year it is, what the count was, what changed since the last one. One of those is English and the other is a form with numbers in it, and a table counted off both learns both. Where that shows up is at the far end of the table, and it is visible enough that it is one of the runs below.
The chronicle lives in a database, and this chapter has no business starting one. So it is dumped: an eighty-year run of the valley, every line it wrote,
one JSON object a line, committed under exemplars/ and embedded the way the
founding document is embedded. The mode that cut it is in this page's bench and needs
no database either, because a chronicle row is a tick, a kind and a sentence, and the
sentence is assembled out of the founding document exactly the way the daemon assembles
it. What a database adds is the entry number, which is a counter, and durability, which a
fixture does not want.
// exemplars/exemplars.go
//go:embed chronicle.jsonl
var Files embed.FS
// Line is one row of the chronicle as the dump carries it: the number
// the database gave it, the tick it belongs to, what sort of entry it
// is, and what it says.
type Line struct {
Entry int64 `json:"entry"`
Tick int `json:"tick"`
Kind string `json:"kind"`
Text string `json:"text"`
}$ go run ./cmd/pieces -mode annals
pieces: 80 years of one valley, and every line it writes down kept
founded at tick 0: The World, on ground it calls The Hollow, 29 hobbs standing
11 lines of the founding document, every one of them tick 0
year tick walking born gone chronicle
10 35550 191 1013 851 21
20 71550 236 1643 1436 31
30 107550 238 1731 1522 41
40 143550 235 1773 1567 51
50 179550 237 1843 1635 61
60 215550 236 1902 1695 71
70 251550 237 1931 1723 81
80 287550 238 1965 1756 91
the chronicle it wrote
rows 91
of those, the founding document 11
and the yearly count 80
the text column, one entry a line 7123 bytes
written to chronicle-81.jsonl
bytes 11693
sha256 90cdf0222d1d64e2
against the copy this build carries
exemplars/chronicle.jsonl 90cdf0222d1d64e2
and the run just made 90cdf0222d1d64e2
the same bytes
287550 ticks in 2m17.118s, 2097 ticks a second (measured here; yours will differ)
The last three lines are the reason the mode is in the bench at all. A committed file is a thing a reader has to believe; a committed file that a run reproduces to the byte is a thing a reader can check, and checking it costs one comparison of two digests. The duration and the rate on the closing line belong to an eight-core Ryzen 7 3700X and will be different on your machine. Everything above them is arithmetic and comes out the same anywhere.
Read that file back and one decision has to be made before any counting starts: which of the four columns is language. The entry number is something Postgres handed out. The tick is a number this world counts in. The kind is a label a program chose. None of those three is anybody's writing, and a table counted off them would spend its first dozen merges learning to spell integers. The corpus is the text column and nothing else, one entry a line.
// exemplars/exemplars.go
// Corpus is the text column of a chronicle and nothing else: one
// entry a line, every line ended.
func Corpus(lines []Line) []byte {
var b bytes.Buffer
for _, l := range lines {
b.WriteString(l.Text)
b.WriteByte('\n')
}
return b.Bytes()
}$ go run ./cmd/pieces -mode corpus
pieces: the history this world kept, read as a corpus
the file this build carries
exemplars/chronicle.jsonl 11693 bytes
sha256 90cdf0222d1d64e2
rows 91
genesis 11
count 80
the text column, one entry a line, and nothing else
bytes 7123
sha256 9adbf2236921cdc7
characters 7123
words, counted on whitespace 1400
distinct byte values in it 53
byte values a table starts with 256
the first rows and the last, cut to fit
entry tick kind text
1 0 genesis This is The World. I built it and I run it, and on the ...
2 0 genesis The land is The Hollow. It is one valley with stone rou...
3 0 genesis The animals are hobbs. One of them is a hobb. They eat,...
4 0 genesis Asteria keeps it. She is not down in the valley and she...
5 0 genesis People gather at Firstlight. Nobody is there and nothin...
6 0 genesis The way in is The Commons. Anybody who comes here comes...
... ... ... ...
86 269550 count year 75: 238 hobbs standing in The Hollow, 1962 born an...
87 273150 count year 76: 237 hobbs standing in The Hollow, 1962 born an...
88 276750 count year 77: 237 hobbs standing in The Hollow, 1962 born an...
89 280350 count year 78: 238 hobbs standing in The Hollow, 1963 born an...
90 283950 count year 79: 238 hobbs standing in The Hollow, 1963 born an...
91 287550 count year 80: 238 hobbs standing in The Hollow, 1965 born an...
91 entries and not one of them is a word list: this is what the world said
Seven thousand one hundred and twenty-three bytes. That is a small corpus by any standard, and it is the right size for this chapter for a reason that is not about convenience: a table counted off it is small enough that you can print a readable slice of the whole thing and argue with individual rows. Two other numbers on that block matter later. Characters equals bytes exactly, 7,123 both, because every byte this world has ever written down is a plain ASCII one. And fifty-three distinct byte values occur in seven thousand bytes, out of the 256 a byte can hold, which is the first hint that counting bytes one at a time wastes almost all of the room available.
The merge table
Here is the whole algorithm in four sentences. Start with every byte value as a token of its own, so there are 256 tokens before anything has been learned and no input can ever arrive that the table has no number for. Count how often each adjacent pair of tokens occurs across the corpus. Take the commonest pair, give it a number nothing else has, and replace every occurrence of it with that number. Do the whole thing again on the result, as many times as you want tokens.
Do one by hand before running any of it, on eleven bytes taken out of the corpus:
standing in. Eleven bytes make ten adjacent pairs, and here they are, in
order: st, ta, an, nd, di,
in, ng, g , i,
in. Nine of the ten occur once. One of them, in, occurs twice,
at bytes six and seven and again at bytes ten and eleven.
So the commonest pair is in, and merging it means minting one number that
nothing else uses and putting it wherever those two bytes sat side by side. The eleven
tokens become nine: s, t, a, n,
d, the new one, g, a space, and the new one again. Two tokens
saved, one row added to a table. Count the pairs of that nine-token list and the process
starts over, with the new number now eligible to be half of the next pair, which is how a
token that stands for four bytes gets built out of a token that stands for two.
Every property this chapter needs is already visible in that eleven-byte example. The
table grows by exactly one row a merge. The text shrinks by exactly the number of times
the merged pair occurred. And the order matters, because merging in first
destroys the pair di as a thing that could ever be merged in this text, while
creating a pair that did not exist before.
The counting is the part to run first, because it is the part people assume is complicated. It is one pass and a map.
// internal/lang/token.go
// Break is the one byte a merge never touches.
//
// Pairs are counted inside an entry and never across the end of one,
// because two chronicle entries are two things that happened and
// nothing joins them. The consequence is worth being clear about: no
// merge can contain this byte, so an encoder can run straight down a
// whole file and the boundaries look after themselves.
const Break = '\n'
// commonest is the pair to merge next, and how often it occurs.
func commonest(lines [][]int) (Pair, int) {
tally := map[Pair]int{}
for _, line := range lines {
for i := 0; i+1 < len(line); i++ {
tally[Pair{line[i], line[i+1]}]++
}
}
var best Pair
most := 0
for p, n := range tally {
switch {
case n > most:
best, most = p, n
case n == most && (p.A < best.A || (p.A == best.A && p.B < best.B)):
best = p
}
}
return best, most
}$ go run ./cmd/pieces -mode pairs
pieces: every adjacent pair of bytes in the corpus, counted once
bytes of corpus 7123
adjacent pairs, entries apart 6941
distinct pairs among them 412
the 12 commonest, which is the order the merges will come in
rank a b pair count
1 110 100 "nd" 192
2 97 110 "an" 190
3 105 110 "in" 188
4 110 32 "n " 181
5 101 32 "e " 161
6 32 49 " 1" 160
7 104 101 "he" 135
8 32 97 " a" 130
9 115 32 "s " 130
10 32 105 " i" 129
11 100 32 "d " 119
12 110 103 "ng" 97
the commonest pair is 192 of 6941, one in 36.2
Two details in that block decide reproducibility. The first is the tie-break, and the fact that there has to be one. Ranks eight and nine are both 130, and a Go map hands its keys back in a different order every run, so a program that took whichever it saw first would train a different table on Tuesday than it trained on Monday. The rule here is the cheapest one available: lowest first half, then lowest second half. Which rule it is barely matters. That it is a rule at all is what makes a token count a number two machines can compare.
The second is that the counting is done inside an entry and never across the end of one. Two chronicle rows are two things that happened years apart, and a pair straddling them is an accident of how the file was written down. Refusing to count those has a consequence that pays for itself: no merge can ever contain a line ending, so an encoder handed a whole file never has to know where the lines are.
Merging is the same loop with a substitution on the end of it. Every merge mints exactly one new number, which is why the table's rows are in a fixed order and why that order is the table: the first row is applied first when anything is encoded, and a table whose rows were shuffled would encode the same sentence into different integers.
// internal/lang/token.go
func Train(corpus []byte, want int) *Table {
lines := split(corpus)
var merges []Pair
for len(merges) < want {
p, n := commonest(lines)
if n < 2 {
break
}
id := Bytes + len(merges)
for i := range lines {
lines[i] = apply(lines[i], p, id)
}
merges = append(merges, p)
}
t, err := New(merges)
if err != nil {
// Unreachable: every merge above is made of ids that exist.
panic(err)
}
return t
}
// apply replaces every occurrence of one pair with one id, left to
// right and without overlapping: in three of the same byte running
// together, the first two merge and the third is left where it is.
func apply(ids []int, p Pair, id int) []int {
out := ids[:0:0]
for i := 0; i < len(ids); {
if i+1 < len(ids) && ids[i] == p.A && ids[i+1] == p.B {
out = append(out, id)
i += 2
continue
}
out = append(out, ids[i])
i++
}
return out
}The stopping condition is the only judgement in there. A pair that occurs once is a pair whose merge costs a row in the table to save a single token, so the loop stops when the commonest pair left is down to one. On this corpus that happens at 354 merges, and this chapter keeps 256 of them, which puts the vocabulary at 512: the byte alphabet, doubled.
$ go run ./cmd/pieces -mode merges
pieces: 256 merges counted off 7123 bytes of chronicle
byte values, there from the start 256
merges asked for 256
merges learned 256
vocabulary 512
the first 12, in the order they were learned
token a b stands for
256 110 100 "nd"
257 105 110 "in"
258 97 256 "and"
259 101 32 "e "
260 32 49 " 1"
261 115 32 "s "
262 104 259 "he "
263 257 103 "ing"
264 32 258 " and"
265 263 32 "ing "
266 111 110 "on"
267 32 98 " b"
and the last 12
token a b stands for
500 57 356 "9 hobbs standing in The Hollow, 16"
501 57 371 "9: 235 hobbs standing in The Hollow, 18"
502 58 32 ": "
503 65 439 "Any"
504 73 32 "I "
505 79 110 "On"
506 84 104 "Th"
507 87 353 "Way"
508 97 117 "au"
509 97 276 "ast"
510 97 305 "at "
511 98 111 "bo"
the longest token in the table
token 458
bytes it stands for 39
which are ": 238 hobbs standing in The Hollow, 196"
written to merges-81.txt
bytes 5892
sha256 ed2bfde380f9fa11
read back, vocabulary 512
the same table, and the same corpus in the same tokens
Read the top twelve and the bottom twelve as two different things, because they are.
The top twelve are English. nd, in, and,
e , ing: those are the pieces any English corpus would
hand over first, and a table counted off a library would learn most of them in the same
order. Token 260 is the odd one, 1, a space followed by a digit, and
it is there because eighty of these ninety-one entries are a sentence with four numbers
in it.
The bottom twelve are this world and nowhere else. Token 500 stands for thirty-four bytes of one particular sentence about a valley; token 501 for thirty-eight bytes of the same sentence with different numbers in it. The longest row in the table is thirty-nine bytes long. Those are not words and they are not phrases anybody chose; they are the most repeated runs of bytes in a history that says almost the same thing eighty times, and the counting found them without being told what a sentence is.
The tail of the table also shows the tie-break doing its job in public. From token 502 onwards the first column climbs steadily, 58, 65, 73, 79, 84, 87, then three at 97 and one at 98: every one of those pairs occurs exactly twice, so the counts no longer separate them and the ordering is entirely the rule. When a table's rows stop being interesting, that is what it looks like from the outside.
The table has to survive being written down, because a table that only exists inside the process that counted it is not a table anybody can price a prompt against. It goes out as text: one merge a line, four tab-separated columns, and a header naming the corpus it was counted from.
$ head -8 merges-81.txt
# a merge table for The World, one merge a line
# corpus 7123 bytes, sha256 9adbf2236921cdc7
# merges 256, vocabulary 512
256 110 100 "nd"
257 105 110 "in"
258 97 256 "and"
259 101 32 "e "
260 32 49 " 1"
The fourth column can be worked out from the first three, so it carries no information at all, and the loader treats it accordingly: it reads the column and checks it against what the first three make, and takes nothing from it. A file you can open and read is a file whose first merge you can argue with, and checking the readable column means it cannot quietly drift away from the one that matters. The digest in the header is there because a merge table and the text it was counted from are one object in two files: encoding a corpus with a table trained on a different one is not an error anything can catch; it costs more tokens than the matching table, for ever.
// internal/lang/table.go
want := Bytes + len(merges)
if got[0] != want {
return nil, fmt.Errorf("lang: line %d of the table mints token %d where token %d comes next", n, got[0], want)
}
merges = append(merges, Pair{got[1], got[2]})
t, err := New(merges)
if err != nil {
return nil, fmt.Errorf("lang: line %d of the table: %w", n, err)
}
shown, err := strconv.Unquote(f[3])
if err != nil {
return nil, fmt.Errorf("lang: line %d of the table: column 4 is not a quoted string: %q", n, f[3])
}
if real := string(t.piece[want]); shown != real {
return nil, fmt.Errorf("lang: line %d of the table says token %d is %q and its two halves make %q",
n, want, shown, real)
}Three refusals, and each of them is a state a hand-edited file can be in. A row out of order mints the wrong number and everything after it is off by one. A half that has not been minted yet is a table that cannot be built, and it is the check that stops a decoder recursing for ever on a cycle somebody typed in by accident. And a fourth column that disagrees with the first three is a file whose readable part was edited and whose real part was not, which is the exact failure a readable format invites.
The byte round trip
Encoding is the training loop with the counting taken out. Every byte becomes its own token, then every merge is applied in the order it was learned, and the result is the same list of numbers the training arrived at. That is not a coincidence to be grateful for, it is the reason encoding is one function and not a second implementation of a first: a test in this package encodes the whole corpus and checks the count against the count training finished on.
// internal/lang/token.go
func (t *Table) Encode(b []byte) []int {
ids := make([]int, len(b))
for i, c := range b {
ids[i] = int(c)
}
for i, p := range t.merges {
ids = apply(ids, p, Bytes+i)
}
return ids
}
func (t *Table) Decode(ids []int) ([]byte, error) {
out := make([]byte, 0, len(ids)*2)
for i, id := range ids {
p, err := t.Piece(id)
if err != nil {
return nil, fmt.Errorf("lang: token %d of %d: %w", i+1, len(ids), err)
}
out = append(out, p...)
}
return out, nil
}
// Piece is the bytes one token stands for.
func (t *Table) Piece(id int) ([]byte, error) {
if id < 0 || id >= len(t.piece) {
return nil, fmt.Errorf("lang: no token %d in a table of %d", id, len(t.piece))
}
return t.piece[id], nil
}
Piece is a bounds check and a slice index, and the bounds check is what
stops this being a panic waiting to happen. An id is an integer that arrived from
somewhere: out of a file, off a wire, out of somebody else's tokenizer. A table asked
for token 700 when it holds 512 has been handed a number from a different vocabulary,
and saying so is the difference between an error a caller can report and a crash halfway
through a decode.
Encode makes one pass over the text for every merge in the table, so
encoding a sentence with this table walks it 256 times. That is the wrong algorithm for
a vocabulary of a hundred thousand and it is the right one here, where the table is 256
rows and the text is a sentence: the whole corpus, all 7,123 bytes of it, goes through
in a few milliseconds. The thing to notice is not the speed but that the loop is
literally the training loop with commonest deleted, so there is no second
definition of what a token is anywhere in this package.
$ go run ./cmd/pieces -mode encode
pieces: one chronicle entry, encoded by a table of 512
entry 51 of the chronicle
year 40: 235 hobbs standing in The Hollow, 1773 born and 1567 gone
bytes 66
tokens 7
every token of it, in order
n token bytes stands for
1 331 6 "year 4"
2 48 1 "0"
3 383 38 ": 235 hobbs standing in The Hollow, 17"
4 55 1 "7"
5 51 1 "3"
6 311 12 " born and 15"
7 493 7 "67 gone"
decoded again
year 40: 235 hobbs standing in The Hollow, 1773 born and 1567 gone
the bytes it started as true
Sixty-six bytes and thirteen words go in, and seven numbers come out. Look at where the boundaries fall, because they fall nowhere a person would put them. Token 3 begins with a colon and ends in the middle of the number 1773. Tokens 4 and 5 are the two digits that particular year happened to need. Token 6 carries the phrase between two of the numbers and the first two digits of the second one. Not one of those seven tokens is a word, and no rule about words was involved in producing them: the counting found the runs that repeat, and in a history that writes the same sentence eighty times with different numbers in it, the runs that repeat are the sentence with holes where the numbers go.
Now the law, which everything above is in service of. Encode then decode returns the input bytes exactly, for every input, including inputs that are not text. It holds for free given a byte alphabet, and the reason to state it out loud is that the obvious variation breaks it.
$ go run ./cmd/pieces -mode round
pieces: encode, decode, compare, over an alphabet of bytes
vocabulary 512
alphabet bytes
input bytes tokens back same
the whole corpus 7123 1419 7123 true
the first entry alone 323 136 323 true
a sentence the corpus does not hold 88 46 88 true
nothing at all 0 0 0 true
a pasted line with a dash in it 44 22 44 true
the same line cut to 26 bytes 26 12 26 true
4096 seeded random bytes 4096 4093 4096 true
7 of 7 inputs came back as the bytes they went in as
The last row is the one that says the law is a law. Four thousand and ninety-six bytes drawn off a seeded generator are not text in any language, and the table encodes them into 4,093 tokens and gets all 4,096 bytes back. It saves three tokens out of four thousand, which is what a table trained on one small history is worth on noise, and it loses nothing, which is what a byte alphabet buys.
The reasonable alternative is to say that the alphabet is characters. A byte is a storage detail; text is made of characters; work in characters and the whole thing is tidier. In Go that is one conversion, right at the top of the encoder, before anything else has happened:
// the one line that makes a rune tokenizer a rune tokenizer:
// decide that the input is characters before deciding anything
// else about it.
in = []byte(string([]rune(string(c.in))))Run the same seven inputs through it. Five of them come back unharmed, which is the trouble with this mistake: it works on everything you are likely to try first.
$ go run ./cmd/pieces -mode round -runes
pieces: encode, decode, compare, over an alphabet of runes
vocabulary 512
alphabet runes
input bytes tokens back same
the whole corpus 7123 1419 7123 true
the first entry alone 323 136 323 true
a sentence the corpus does not hold 88 46 88 true
nothing at all 0 0 0 true
a pasted line with a dash in it 44 22 44 true
the same line cut to 26 bytes 26 16 30 false
4096 seeded random bytes 4096 7663 7666 false
5 of 7 inputs came back as the bytes they went in as
the first one that did not
in 26 bytes 61636b20e280
out 30 bytes efbfbdefbfbd
first byte that differs 24
Start at the symptom. Twenty-six bytes went in and thirty came out, and the first byte
that differs is byte 24. The input is an ordinary line somebody pasted out of an editor
that turned two hyphens into a dash, and a dash of that kind is three bytes in UTF-8:
e2 80 94. Cutting the line at twenty-six bytes, which is the sort of thing
a preview column does without asking, leaves two of those three behind. So the last two
bytes of the input are e2 80, which is the beginning of a character and not
a character.
Now work back. []rune(string(b)) has to hand back something for those two
bytes, and what Go hands back is the replacement character, once for each byte it could
not make sense of. That is ef bf bd each time, six bytes where there were
two, which is the thirty. The conversion has not failed and has not returned an error;
it has quietly substituted, which is what it is documented to do and is exactly wrong
here. Nothing downstream can tell. The decoder gets valid tokens, produces valid text,
and the text is not what arrived.
The bottom row is the same cause with the volume turned up. Random bytes are almost never valid UTF-8, so nearly every one of them becomes a replacement character, and 4,096 bytes come back as 7,666. The byte tokenizer got that case exactly right without anybody thinking about it, because it never asked what a byte meant.
One limit of the byte alphabet needs to stay explicit: nothing stops a token boundary falling inside a character. The three bytes of that dash go through as three separate tokens, because this corpus has never held one, and a table counted off a corpus that had would happily merge two of the three and leave the third on its own. It does not matter. Decoding concatenates the pieces and the character reassembles itself, and that is the whole difference between the two designs: one of them can cut a character in half and put it back together, the other cannot represent one it did not expect.
$ go test ./exemplars/ ./internal/lang/ -run 'TheDumpIsOneRowALine|TheCorpusIsTheTextColumnAndNothingElse|AHalfWrittenDumpIsAnErrorAndNotAShortHistory|EncodeThenDecodeIsTheInput|EncodingTheCorpusLandsOnTheTrainedCount|NoMergeCrossesTheEndOfAnEntry|TheSameCorpusTrainsTheSameTable|AMergeTableSurvivesBeingWrittenDown|ATokenFromAnotherVocabularyIsAnError' -v
=== RUN TestTheDumpIsOneRowALine
exemplars_test.go:29: 91 rows, entry 1 to entry 91, no gaps
--- PASS: TestTheDumpIsOneRowALine (0.00s)
=== RUN TestTheCorpusIsTheTextColumnAndNothingElse
--- PASS: TestTheCorpusIsTheTextColumnAndNothingElse (0.00s)
=== RUN TestAHalfWrittenDumpIsAnErrorAndNotAShortHistory
--- PASS: TestAHalfWrittenDumpIsAnErrorAndNotAShortHistory (0.00s)
PASS
ok theworld/exemplars 0.003s
=== RUN TestEncodeThenDecodeIsTheInput
--- PASS: TestEncodeThenDecodeIsTheInput (0.00s)
=== RUN TestEncodingTheCorpusLandsOnTheTrainedCount
--- PASS: TestEncodingTheCorpusLandsOnTheTrainedCount (0.00s)
=== RUN TestNoMergeCrossesTheEndOfAnEntry
--- PASS: TestNoMergeCrossesTheEndOfAnEntry (0.00s)
=== RUN TestTheSameCorpusTrainsTheSameTable
--- PASS: TestTheSameCorpusTrainsTheSameTable (0.00s)
=== RUN TestAMergeTableSurvivesBeingWrittenDown
--- PASS: TestAMergeTableSurvivesBeingWrittenDown (0.00s)
=== RUN TestATokenFromAnotherVocabularyIsAnError
--- PASS: TestATokenFromAnotherVocabularyIsAnError (0.00s)
PASS
ok theworld/internal/lang 0.008s
Nine tests and every one of them is a sentence from this page made checkable. The round trip over eight inputs including 512 seeded random bytes. Encoding landing on the count training finished with. No merge containing a line ending. The same corpus training the same table twice. The file format surviving a round trip and refusing three kinds of edited file. A token from another vocabulary coming back as an error. And, in the fixture package, that the committed chronicle parses to the last line, is numbered from one without a gap, and that a half-written dump is refused rather than read as a short history.
Pricing one sentence
Tokens are the unit this volume prices in, so the unit has to be settled before anything is quoted in it. The count is the number of entries the encoder emits, whitespace and punctuation included. It is never a word count and it is never a character count, and the way to make that a measurement instead of a claim is to print all three for one sentence.
The sentence is one of this world's own, out of the founding note about where whatever stops moving ends up.
Start with the table rather than the sentence, because two of its numbers are fixed by arithmetic and nothing else. A table that has learned m merges holds V = 256 + m tokens: the 256 byte values it began with, plus one new number a merge. With 256 merges that is 512, and the choice of 256 was made off the curve further down this page rather than off any property of language. The other fixed number is the floor. However many merges you learn, a text of b bytes can never encode to fewer than one token, and it can never encode to more than b, because every byte is already a token before any merge is applied. Every count in this volume sits between those two.
Take the sentence Bodies, husks, whatever falls: it ends in one place and the ground takes it back. Count it three ways by hand first.
Characters: every letter, every space, the two commas, the colon and the full stop. Eighty-one of them, and because every byte in this corpus is plain ASCII, eighty-one bytes as well. Words, if a word is a run of non-space characters: fifteen, counting falls: as one and back. as one. Tokens: whatever the table says, and the table has no opinion about spaces or full stops, so the answer cannot be guessed from either of the other two.
The ratios are what the rest of the volume actually uses. Write c for characters, w for words and t for tokens. Then c/t is how many characters one token is worth on this text, and t/w is how many tokens a word costs. Neither is a constant. Both are properties of the table and the text together, which is the single most useful thing to know about them: a figure measured on one text with one table is not a figure about another.
$ go run ./cmd/pieces -mode price
pieces: one sentence, priced three ways
the sentence, and where the chronicle keeps it
Bodies, husks, whatever falls: it ends in one place and the ground takes it back.
inside entry 10
characters 81
words, counted on whitespace 15
tokens, by a table of 512 41
characters a token 1.98
tokens a word 2.73
and the same three over the whole corpus
characters 7123
words 1400
tokens 1419
characters a token 5.02
Eighty-one characters, fifteen words, forty-one tokens. The three numbers are not close to each other and no ratio between two of them survives being carried to the third. And the same table on the same corpus is getting 5.02 characters a token overall, two and a half times better than the 1.98 it manages on this sentence, which needs an explanation rather than a shrug.
The explanation is that eighty of the ninety-one entries are one sentence written eighty times with different numbers in it, and the merges went where the repetition was. That sentence encodes to seven tokens for sixty-six bytes. The founding note is prose that occurs once, so it gets the ordinary English merges and nothing else, and it costs 2.73 tokens a word. A reader who took the corpus-wide 5.02 and priced their own writing with it would be out by a factor of two and a half in the direction that costs money.
The trade behind the vocabulary size is the other half of the same picture, and the curve does something people do not expect.
$ go run ./cmd/pieces -mode grow
pieces: what each merge buys, over 7123 bytes of chronicle
asked learned vocabulary tokens bytes/token saved
0 0 256 7123 1.00
1 1 257 6931 1.03 192
2 2 258 6743 1.06 188
4 4 260 6400 1.11 343
8 8 264 5901 1.21 499
16 16 272 5171 1.38 730
32 32 288 3836 1.86 1335
64 64 320 2292 3.11 1544
128 128 384 1783 3.99 509
256 256 512 1419 5.02 364
512 354 610 1223 5.82 196
asking for more than 354 gets 354: no pair is left that occurs twice
the table this chapter keeps
merges 256
vocabulary 512
tokens for the whole chronicle 1419
The saved column has to be read against the step it covers, because the rows are not evenly spaced. The very first merge takes 192 tokens off the corpus on its own. Merges 33 to 64, thirty-two of them, take 1,544 between them, about 48 apiece. Merges 65 to 128 take 509, under 8 apiece. The 128 after those take 364, under 3 apiece. Every one of them costs the same thing: one row in a table that has to be carried, shipped and held in memory beside everything else, and every one buys less than the one before it. That is the whole of what choosing a vocabulary size is, and there is no correct answer to it, only a curve and a budget.
Which leaves the design most people would have reached for first: split on spaces and call each word a token. It is one line of Go, so the page runs it instead of dismissing it.
$ go run ./cmd/pieces -mode price -split | tail -23
the same sentence, by a tokenizer that splits on whitespace
vocabulary, off this corpus 431
tokens for the sentence 15
words it has no id for 0
and the entry it would write next year, which is not in the corpus
year 81: 240 hobbs standing in The Hollow, 1970 born and 1760 gone
already in the chronicle false
tokens, by the merge table 11
tokens, by the word list 10
words it has no id for at all 3
"81:"
"1970"
"1760"
and the whole corpus, taken apart into words and put back
words the list knows 431
bytes in 7123
bytes out 7122
entry boundaries in 91
entry boundaries out 0
the bytes it started as false
On the sentence it was built from, the word list wins: fifteen tokens against forty-one,
and a vocabulary of 431 against 512. Then the valley finishes another year and writes the
entry it writes every year, and three of its words have no number at all. Not a rare
number, not an unusual number: 81:, 1970, 1760. The
merge table encodes the same sentence in eleven tokens without being consulted about it,
because a number it has never seen is still a run of bytes and every byte has an id.
The last block is the quieter failure and the worse one. Take the whole corpus apart into words and put it back together and you get 7,122 bytes where there were 7,123, which looks like nothing at all until you read the line under it. Ninety-one entry boundaries went in and none came out. The eighty years of history have become one line, and the byte count barely moved because a line ending and a space are both one byte. A tokenizer that loses the difference between two entries and a space in the middle of one has not lost a byte; it has lost the structure, and it did it without changing a number anybody was watching.
Why token counts name a table
The mechanism generalises past this chapter and past this world. Any system that charges for text charges for it in units of some table, and the table is not a natural fact about language. It was counted off a corpus somebody chose, at a size somebody picked off a curve like the one above, with a tie-break somebody had to write down. Three tables counted off three corpora will give three different answers for the same sentence, and all three will be right.
That is why the count is defined here as the number of entries the encoder emits and not as anything more intuitive. It is the only definition that can be checked: hand a table and a string to two programs and they agree to the integer, whereas words depends on what you think a word is and characters depends on whether you are counting characters or bytes. A figure quoted in that unit names the table it was measured with, for the same reason a weight names its scale.
The three properties that make the table usable, stated once so nothing later has to argue them again. It is total: the byte alphabet means no input can arrive that has no representation, which is what the round trip over random bytes demonstrates and what the character alphabet gives away. It is lossless: decode of encode is the input, proved on the corpus, on text the corpus does not hold, on a cut character and on noise. And it is deterministic: the same corpus and the same merge count produce the same table, on any machine, in any order the map felt like today, because the tie-break is a rule and not an accident.
One thing this chapter did not do, said plainly because the word gets used loosely. Nothing here was trained in the sense that word usually carries. There is no gradient in this package, no backward pass, no loss and no learning rate. Counting how often two bytes sit next to each other is counting, and calling it training would put this page on the wrong side of a distinction the rest of the volume depends on.
What the chapter leaves standing is small and deliberately dull: a package with a
tokenizer in it, a fixture with a history in it, a digest tying the two together, and a
file format that can be written out and read back with three ways to be refused. Anything
that wants tokens asks Train for a table over the committed corpus and gets
the same 512 entries every time, on any machine, or reads one back off disk with
ReadTable and gets a table that encodes identically. Nothing in the valley
knows any of it exists, which is the seal at the top of this page doing exactly the job it
was put there for.
- Why the alphabet is the 256 byte values and not the characters of any encoding, and what specifically goes wrong at byte 24 of a line cut in the middle of a dash.
- What the tie-break in
commonestis for, and why ranks eight and nine of the pair count both reading 130 is the reason it exists. - Why counting stops at the end of a chronicle entry, and what that buys an encoder handed a whole file.
- Why the fourth column of
merges-81.txtis checked on load rather than read, given that it carries no information. - Why one sentence of this corpus costs 41 tokens at 1.98 characters a token while the corpus as a whole runs at 5.02, and which of those two numbers you would use to price text of your own.
- What the word list has no number for the moment the valley finishes its eighty-first year, and why the merge table does.
Exercise 1 — find the point of no return. The merge table stops at 354 because no pair is left occurring twice. Find the merge count at which the table stops learning English and starts learning this valley's boilerplate, and say how you decided.
Run the listing at a few sizes and read the tail of each one:
go run ./cmd/pieces -mode merges -merges 32 -top 6
go run ./cmd/pieces -mode merges -merges 48 -top 6
go run ./cmd/pieces -mode merges -merges 64 -top 6
The longest-token line the mode prints at the end is the quickest instrument. At
32 merges the longest row in the table stands for seven bytes and is a fragment any
English text would produce. By 48 it stands for thirty-two, and what it stands for
has standing in in the middle of it. So the turn happens between those
two, and by 256 the longest row is thirty-nine bytes of one particular sentence.
The honest answer to "where" is a range and not a number. A second way to ask the
same question is -mode grow and its saved column: the merges that buy
the most are the ones learning English, and the fall-off starts as the table begins
spending rows on the sentence this valley writes every year.
Exercise 2 — price your own writing. Encode a paragraph you wrote yourself with this table and work out its characters a token. Explain the number you get before you look at anything else.
The bench takes the sentence on a flag, so no code is needed:
go run ./cmd/pieces -mode price -line "whatever you want to price, in quotes"Expect something near the 1.98 the founding note gets and nowhere near 5.02, and expect it to fall further the less your text looks like this valley. The line saying which entry holds the sentence will report that no entry does, which is the honest answer and not an error. The general lesson is the one the volume needs: a characters-a-token figure is a property of a table and a text together, so the corpus-wide number is the least useful of the two for pricing anything that is not the corpus.
Exercise 3 — break the table on purpose. Write a merge table
by hand that makes ReadTable refuse, once for each of the three things it
refuses, and check that the error names the line.
Write the table out first so you have a real one to damage:
go run ./cmd/pieces -mode merges -merges 8 -table hand-81.txt
cat hand-81.txt
Three edits, one at a time. Swap two rows: the reader stops at the first of them and
says it mints a token where a different one comes next. Change the second column of
the first merge to 9999: the reader says a token can only be made of
tokens that already exist, because 9,999 has not been minted at line one and never
will be. And change only the quoted fourth column of any row: the reader says what
the row claims and what its two halves actually make, and refuses. That third one is
the whole reason the column is checked. Its information content is zero, so nothing
would be lost by trusting it, and trusting it is how a readable file ends up
disagreeing with itself. A test in the package asserts all three, pinned:
go test ./internal/lang/ -run TestAMergeTableSurvivesBeingWrittenDown.