# Getting started Kest is a statically typed language for the gameplay half of a game: rules, AI, quests and simulation. A program is compiled to bytecode and run by a small machine that an engine embeds through one C header. The same `kest` command line runs programs on their own, which is how this page uses it. ## Getting the command line **From a release.** Each release on the [releases page](https://github.com/Rawframe-Project/kest/releases) carries an archive for Linux on x86-64 and arm64, macOS on arm64 and Windows on x86-64, with every file's checksum in `SHA256SUMS` and a build provenance attestation (`gh attestation verify -R Rawframe-Project/kest`). Unpack it anywhere and put its `bin` directory on the path. The Windows archive needs Windows 10 version 1903 or later. The archive holds the command line, the header, the static library, the standard library and the VS Code extension; nothing else needs to be installed. **In the browser.** The [playground](https://rawframe-project.github.io/kest/) runs the command line built as WebAssembly inside the page. **From source.** Kest is C11 with no dependency beyond the C library; it builds with CMake 3.25 or newer. On Linux and macOS, with Ninja: ```sh git clone https://github.com/Rawframe-Project/kest.git cd kest cmake --preset dev cmake --build --preset dev out/dev/kest run examples/math.kest ``` On Windows, with Visual Studio, use the `windows-msvc` preset; the command line is then `out\windows-msvc\kest.exe`. It needs Windows 10 version 1903 or later: its manifest sets the process's code page to UTF-8, so a path with any character in it works, and an older Windows ignores the manifest and reads a path in the system's code page. Everything a build makes is under `out/`, next to a link to the standard library, so the command line there finds it. To install into a prefix, with the standard library where the command line looks for it: ```sh cmake -S . -B out/install -DCMAKE_INSTALL_PREFIX=/usr/local -DKEST_CHECKED=OFF cmake --build out/install sudo cmake --install out/install ``` `out/install/install_manifest.txt` lists every file the install put there. ## A first program A file with a `main` is a program. `main` takes nothing and gives an `i32`, which becomes the exit status, or gives nothing, which exits with 0. ```kest import std.io fn main() -> i32 { io.print("hello from kest") return 0 } ``` ```text hello from kest ``` `kest run hello.kest` compiles and runs it. Printing is not built into the language: `std.io` declares it as a door the host provides, and the command line is a host that provides it. [Embedding Kest](embedding.md) explains doors. The commands used every day: | Command | What it does | | --- | --- | | `kest run file.kest` | compiles the program and runs `main` | | `kest check file.kest` | reports everything wrong with the program at once, without running it | | `kest fmt -w file.kest` | rewrites the file in the one layout the language has | | `kest test` | runs the project's tests | | `kest doc file.kest` | prints what a module declares, with the comment above each declaration | Every command takes `--json` and then reports in JSON for tools. [The command line](command-line.md) lists every command and option. ## A project A single file needs nothing around it. A directory becomes a project when it has a `kest.project` file, and `kest new` makes one: ```sh kest new demo cd demo kest run kest test ``` That gives a manifest, a program in `src/main.kest` and a test in `tests/adding.kest`. Inside a project, `kest check`, `kest build` and `kest run` work on the entry the manifest names when no file is given, and `kest test` runs every `.kest` file directly under the tests directory. `kest.project` is lines of `name value`, and `#` starts a comment: | Line | Meaning | | --- | --- | | `project demo` | the project's name | | `entry src/main.kest` | the program `check`, `build` and `run` use when no file is named | | `source src` | a directory the project's modules live under; one line per directory | | `tests tests` | the directory `kest test` runs | | `kest 0.0.1` | the version the project was written against | | `profile kest-det 4` | the deterministic profile it is written under, see [Determinism](determinism.md) | | `edition 2026` | the edition of the language it is written in, see [Versions and editions](editions.md) | An unknown name in the manifest is an error rather than a line that is skipped: every command run in the project refuses it with `K0709`, and `kest doctor` says what it read. **Modules and sources.** A module's name is where its file is: `module game.npc` lives in `game/npc.kest` under one of the `source` directories. Inside a project the `source` lines are the whole list of places an import is looked for, in the order they are written. A dependency is another `source` line pointing at wherever its code was put; there is no package registry and nothing is downloaded. A module found under two sources is an error, because the import line cannot say which one it means. **Tests.** A test is a program that checks itself and answers with which check failed, so 0 is a pass: ```kest module adding fn add3(a: i32) -> i32 { return a + 3 } fn main() -> i32 { if add3(1) != 4 { return 1 } if add3(-3) != 0 { return 2 } return 0 } ``` `kest test adding.kest` runs it and reports it passed. A project whose manifest names a tests directory with no tests in it fails `kest test`, so a run of nothing is never reported as a pass. ## When something is off `kest doctor` prints the version, where the command line looks for the standard library and whether it found it, and what the project in the current directory says about itself. The standard library is found at `$KEST_LIB` if that is set, then in `lib/` beside the command line (a source tree), then in `../lib/kest/` beside it (an install or an unpacked archive), and last where the build was told it would be installed. The first one that exists is used. ## Where to go next - [Coming from Lua or Rust](coming-from-lua-or-rust.md) lists what is different here, from the mistakes newcomers make. - [Language basics](language-basics.md), [Data](data.md), [Text](text.md) and [Functions](functions.md) cover the language. - [Promises](promises.md) covers what the compiler proves about a function. - [Embedding Kest](embedding.md) covers running Kest inside an engine. # Language basics How a Kest file is laid out, its names, numbers, operators and control flow. [Data](data.md) covers structs, arrays, stores, enums and optionals; [Text](text.md) covers strings; [Functions](functions.md) covers generics, function values and blocks. ## Contents - [Files and modules](#files-and-modules) - [Lines, blocks and comments](#lines-blocks-and-comments) - [Names, `let` and `const`](#names-let-and-const) - [Numbers and conversions](#numbers-and-conversions) - [Operators](#operators) - [Control flow](#control-flow) - [`defer`](#defer) - [When a program faults](#when-a-program-faults) - [Keywords](#keywords) ## Files and modules A file that starts with `module` is a module, and its name is its path: `module game.map` is `game/map.kest`, relative to the root the first file was found in or to a project's `source` directories. A file with no `module` line is a program to run and cannot be imported. What another module declares is always written through the last part of its name, including after `import`: `map.Tile`, `map.load(...)`. There is no `use`, no bare import and no wildcard, so every name says where it came from. ```kest module shop import std.io import std.math fn main() -> i32 { io.print("{math.max(2, 7)}") return 0 } ``` ```text 7 ``` A module may write its own declarations without a prefix. Two modules may end in the same word (`render.math` and `physics.math` can both be in one program), but one file may not import both, since `math.` would then mean either; the error points at both import lines. `std` is reserved for the standard library. Two files may import each other. Each file is read once, however many files import it. ## Lines, blocks and comments A newline ends a statement; there are no semicolons. A statement continues onto the next line while a bracket is open or when the line ends in a binary operator. One exception: a line may end after `>` only where a type ends (`ref`), so a comparison has to stay on one line. Blocks are braces, always, even around one statement. Conditions take no parentheses: `if x < 3 { }`, never `if (x < 3) { }`. Comments are `//` to the end of the line, and there is no other kind. Names are UTF-8, so `let hız = 5` is a valid line. The layout is the formatter's: four spaces a level, one space around a binary operator, and a list that does not fit in 80 columns goes one item to a line. `kest fmt -w` writes it and `kest fmt --check` names the files that are not in it. A file that does not parse is never rewritten. ## Names, `let` and `const` `let` names a value. Its type comes from the value and may be written. A `let` always has a value: `let a: i32` on its own is an error, so no name is ever read before it holds something. `const` names a value worked out while compiling, and always writes its type, because it can be read from other files. ```kest module totals import std.io const SLOTS: i32 = 4 * 8 const STEP: f32 = 1.0 / 60.0 fn main() -> i32 { let count = 3 let speed: f32 = 2.5 count += SLOTS io.print("{count} {speed * STEP * 60.0}") return 0 } ``` ```text 35 2.5 ``` A constant may be arithmetic on numbers and other constants, a conversion, a struct or enum value built from those, a fixed run such as `[1.0, 0.5, 0.25]`, `len` of a fixed run and `hash` of a value. It may not call a function, choose between values with `if` or `match`, or fill a hole in a string; those happen while running. A constant can count a fixed run: `[i32; SLOTS]`, or `[Npc; npc.PARTY]` from another module. Inside a body, a `let` or a parameter may reuse the name of something the file declares. From there on the name means the local, and the file's own is written with its module in front. Two locals may not share a name. ## Numbers and conversions | Type | What | | --- | --- | | `i8` `i16` `i32` `i64` | signed whole numbers | | `u8` `u16` `u32` `u64` | unsigned whole numbers | | `f32` `f64` | IEEE 754 floats | | `bool` | `true` or `false` | A whole-number literal is an `i32` unless the place it goes wants another width, and a literal with a point is an `f32` unless an `f64` is wanted. A literal that does not fit where it is written is an error: `let x: u8 = 300`. Nothing converts on its own. Naming a type converts: `f32(n)`, `i32(x)`, `u8(300)`. The rules are the same while compiling and while running: - Whole numbers wrap at their width, in both directions. Narrowing keeps the low bits, so `u8(300)` is 44. - A float converted to a whole number truncates toward zero and stops at the ends of the range; a float that is not a number converts to 0. - `/` truncates toward zero, and `%` takes the sign of the left side, for floats too: `-7.5 % 2.0` is `-1.5`. - Dividing a whole number by zero stops the program. Dividing a float by zero gives an infinity, or `nan` for `0.0 / 0.0`, as IEEE 754 says. - The smallest number of a width divided by -1 is itself, and its remainder is 0. - A shift count at or past the width shifts everything out: `1 << 64` on an `i64` is 0 and `-8 >> 64` is -1. A negative count is an error. ```kest module widths import std.io fn main() -> i32 { let n = 7 let half = f32(n) / 2.0 let small = u8(300) let wide: i64 = 5000000000 let cut = i32(-2.9) io.print("{half} {small} {wide} {cut} {-7 % 3}") return 0 } ``` ```text 3.5 44 5000000000 -2 -1 ``` `bits(x)` is a float's bits as a `u32` or `u64`, and `float(b)` turns them back; neither rounds. `f32` and `f64` are separate types and an `f32` operation rounds to `f32` at every step. ## Operators Tightest first: ``` ~ - ! on one value * / % + - << >> & ^ | < <= > >= == != && || ``` The bitwise operators bind tighter than comparisons, so `state & MOVING == MOVING` means what it looks like. `&`, `|`, `^` and `~` work on whole numbers and on [sets of flags](data.md#flags); `bool` has `&&`, `||` and `!`. `>>` brings in the sign on a signed type and zeros on an unsigned one. Assignment is `=`, `+=`, `-=`, `*=` and `/=`, and nothing else: there is no `++`, no `%=` and no ternary operator. There is no `+` on text; text is joined with holes, see [Text](text.md). A statement that only computes a value is an error, which catches `a == b` written where `a = b` was meant. A call may be a statement on its own, and its answer may be ignored. ## Control flow ```kest module control import std.io fn main() -> i32 { let hp = 3 let said = if hp > 0 -> "alive" else -> "down" let total = 0 for i in 0..5 { if i == 2 { continue } if i == 4 { break } total += i } let left = 10 while left > 7 { left -= 1 } for at, x in [5, 6] { total += at * x } io.print("{said} {total} {left}") return 0 } ``` ```text alive 10 7 ``` - **`if`** gives a value when its arms are written with `->`, and then it needs an `else`. All arms of one `if` are either values or blocks. `else` may start the next line in an `if` that gives a value. - **`for`** walks a range `a..b` (up to but not including `b`), an array, a fixed run, text (a `u8` at a time), a store (a reference at a time) and a set of flags. `for i, x in xs` also gives the position. A range is worked out once, and an array walk takes its length once, so pushing inside the body does not lengthen the walk; removing inside it is an error when the walk reaches past the end. - **`while`**, **`while let`**, **`break`** and **`continue`** work as expected; `break` and `continue` belong to the loop they are written in. - **`match`** chooses between the cases of an enum, see [Data](data.md#enums-and-match). A function that gives something back has to end in something that gives it: a `return`, an `if` or `match` whose every arm does, or a `while true` that nothing breaks out of. A `for` and a `while let` do not count, since they may run no times. `main` takes nothing and gives `i32` or nothing; one file may declare only one `main`. An exit status holds 0 to 255, and a `main` that answers anything else is an error rather than a number cut to fit. ## `defer` `defer f(x)` runs the call when the enclosing block ends, however it ends: at the closing brace, through `return`, `break` or `continue`. Several run in reverse order. A block on its own is a statement, which gives a name a shorter life and makes a `defer` run sooner. ```kest module closing import std.io fn close(what: text) { io.print("closed {what}") } fn main() -> i32 { { defer close("the first") defer close("the second") io.print("inside") } io.print("after") return 0 } ``` ```text inside closed the second closed the first after ``` A `defer` takes a call and nothing else, and the call sees the names as they are when the block ends, not when the `defer` was written. What a deferred call does counts against the function's [promises](promises.md). ## When a program faults A program that divides a whole number by zero, reads past the end of an array or runs out of its budget stops there with an error naming the line and the calls that led to it. That is a fault, not an exception: nothing catches it, and no `defer` runs. The host is told the call failed, and the program's state is whatever the fault left; nothing is rolled back. [Embedding Kest](embedding.md#when-a-call-fails) covers what a host does about it. For an expected failure, a function answers with a value instead. [Data](data.md#saying-that-something-failed) lists the three shapes. ## Keywords ``` break const continue defer else enum extern false fn for if import in let match module none return struct true while ``` `flags`, `scratch`, `own`, `compares`, `orders`, `resumes`, `wait` and `block` mean something only where they stand (a declaration, a block, a field, a type parameter, a signature) and are ordinary names everywhere else. `type` is not reserved. # Data Structs, fixed runs, arrays, stores and references, enums, sets of flags, optionals and vectors: what each is, what it costs, and what copies. ## Contents - [Values and handles](#values-and-handles) - [Structs](#structs) - [Fixed runs](#fixed-runs) - [Arrays](#arrays) - [Stores and references](#stores-and-references) - [Enums and `match`](#enums-and-match) - [Flags](#flags) - [Optionals](#optionals) - [Saying that something failed](#saying-that-something-failed) - [Vectors](#vectors) - [What compares, hashes and prints](#what-compares-hashes-and-prints) - [Containers and the heap](#containers-and-the-heap) ## Values and handles Every type is one of two kinds, and the difference decides what a function can change: - **Values**: numbers, `bool`, text, structs, fixed runs `[T; N]`, vectors, enums, flags and optionals. Handing one to a function or to a `let` copies it. - **Handles**: arrays `[T]`, stores `store` and function values. Handing one over hands over the same thing, so writing through any name for it is seen through every other. A struct holding an array holds the handle, not a copy of the elements. ```kest module walk import std.io struct Body { x: f32 speed: f32 } fn moved(b: Body, dt: f32) -> Body { let after = b after.x += b.speed * dt return after } fn main() -> i32 { let b = Body(0.0, 2.0) b = moved(b, 0.5) let xs = [1, 2, 3] let ys = xs ys[0] = 9 io.print("{b.x} {xs[0]}") return 0 } ``` ```text 1.0 9 ``` The mistake this makes easiest: writing a field of a struct parameter writes the function's own copy, which the caller never sees. The compiler warns (`K0346`) when a function writes a field of a parameter and does not give that type back. The fix is to answer with the changed value and let the caller store it, as `moved` does. ## Structs A struct is built by calling it with its fields in the order they are declared. There are no struct literals with names and no named arguments. ```kest module npcs import std.io struct Npc { name: text health: i32 } fn main() -> i32 { let ann = Npc("ann", 10) let hurt = ann hurt.health -= 3 io.print("{ann.health} {hurt.health} {hurt}") return 0 } ``` ```text 10 7 Npc("ann", 7) ``` A struct is laid out like the C struct of the same fields, so a host can lend an array of them and the program works on the host's memory in place. **Fields only one module may name.** A field written `own` can only be named inside the module that declared the struct: read, written or given when the struct is built. A struct whose every field is `own` can only be built by its own module, which is how an opaque type is written. `std.table` keeps its arrays this way so nothing outside can move a key without its value. ```kest module ledger struct Ledger { own entries: [i32] } fn empty() -> Ledger { let fresh: [i32] = array() return Ledger(fresh) } fn record(l: Ledger, amount: i32) { push(l.entries, amount) } ``` `own` is a word only in front of a field name, so a field may still be called `own`. ## Fixed runs `[T; N]` is `N` values of `T` laid out in place, and it is a value: copying it copies every element. `N` is a number or a constant. An index written as a number is checked while compiling; one worked out while running is checked while running. `len` of a fixed run is the number in its type. ```kest module quads const CORNERS: i32 = 4 struct Quad { xs: [f32; CORNERS] tag: i32 } fn width(q: Quad) -> f32 { return q.xs[1] - q.xs[0] } ``` ## Arrays An array is a growable handle. `array()` is an empty one, typed by where it goes; `array(n, v)` is `n` copies of `v`; `[1, 2, 3]` is a literal. `push` adds to the end, `pop` takes the last off as an optional, `remove(xs, i)` takes out the one at `i` and shifts the rest down, and `clear` empties it while keeping its room. ```kest module counts import std.io fn main() -> i32 { let xs: [i32] = array() push(xs, 3) push(xs, 4) push(xs, 5) let last = pop(xs) let first = remove(xs, 0) xs[0] += 10 io.print("{len(xs)} {last} {first} {xs[0]}") return 0 } ``` ```text 1 5 3 14 ``` An element of an array is a place: `xs[i].health -= 1` writes the element where it is. Reading past the end stops the program. `room(xs, n)` makes room for `n` elements without changing the length, and `fit(xs, v)` is `push` that never grows: it answers `false` when there is no room. Those two are how a function that promises not to allocate fills a buffer, see [Promises](promises.md). A `[u8]` holds bytes. `push(bytes, "some text")` appends a whole piece of text, and `text(bytes)` turns bytes back into text, refusing bytes that are not UTF-8. ## Stores and references A `store` owns values and hands out a `ref` for each one added. A reference can go stale, because something else may remove what it named, so reading through one with `get` answers an optional. `set` writes a value back, `remove` takes it out, and a `for` over a store walks a reference at a time. ```kest module world import std.io struct Npc { hp: i32 } fn main() -> i32 { let npcs: store = store() let a = add(npcs, Npc(10)) let b = add(npcs, Npc(20)) remove(npcs, a) if let one = get(npcs, b) { let hurt = one hurt.hp -= 5 set(npcs, b, hurt) } let alive = 0 for r in npcs { if let one = get(npcs, r) { alive += one.hp } } io.print("{len(npcs)} {get(npcs, a) == none} {alive}") return 0 } ``` ```text 1 true 15 ``` **Stale stays stale.** A reference is a place and a stamp, and every place a process hands out gets a stamp it never hands out again. A reference to something removed reads `none` even after its place is reused, and a reference from another store reads `none` in this one. Writing or removing through a stale reference does nothing and answers that it did nothing. Removing during a walk of the store is safe; the walk does not go back. Adding during a walk lands wherever the store puts it, which the walk may or may not reach, so gather what to add and add it afterwards. Two references compare equal when they are the same handout, and a reference hashes, so `table.Table, V>` hangs data off an entity without changing the entity. A reference has no text and means nothing in another machine: a saved world stores the program's own identifiers, not references. An element of a store is not a place: read it with `get`, change the copy, write it back with `set`. Reading a whole element, changing several fields and writing it back is faster than resolving the element once per field. Nothing counts references and nothing is told about a removal, so two values may name each other through references without either keeping the other alive. ## Enums and `match` An enum is one of several cases, and a case may carry values, written by position. ```kest module door import std.io enum Door { Shut Locked(i32) Open(f32) } fn describe(d: Door) -> text { return match d { Shut -> "shut" Locked(key) -> "locked with {key}" Open(width) -> "open {width} wide" } } fn main() -> i32 { io.print(describe(Door.Locked(7))) match Door.Open(1.5) { Open(width) { io.print("{width}") } else { io.print("not open") } } return 0 } ``` ```text locked with 7 1.5 ``` - `match` chooses between the cases of an enum and nothing else. Numbers and text are chosen between with `if`. - Every case is answered, or `else` answers the rest. A `match` that misses a case is an error that names each missing case. - An arm is `Case -> value` or `Case { ... }`, and all arms of one `match` are the same kind. A `match` whose arms give values is itself a value. - `match a, b { ... }` answers two enums at once, an arm per combination, with `else` in a position for any case there. Arms are tried in order, and an arm nothing can reach is an error. An enum is laid out as a C tagged union: a four-byte tag, then the payload at its own alignment. A case added in the middle renumbers the cases after it, which a host or a saved file reading tags sees; see [Host memory](host-memory.md#saving-and-reloading). ## Flags `flags` declares a set of named bits over an unsigned width. Which bit a name is depends on where it was written, so there are no powers of two to get wrong. ```kest module states import std.io flags State: u8 { Moving Airborne Hurt } fn main() -> i32 { let state = State.Moving | State.Hurt if state & State.Hurt != State() { io.print("hurt") } let count = 0 for flag in state { count += 1 } io.print("{count} {u8(state)} {state}") return 0 } ``` ```text hurt 2 5 State.Moving | State.Hurt ``` `&`, `|`, `^` and `~` combine two of one set, and `~` flips only the bits the set has names for; `==` and `!=` compare. `State()` is the empty set, `u8(state)` gives the bits and `State(bits)` takes them back, keeping the bits that have names and dropping any other, as `u8(300)` keeps the bits a `u8` holds. A set is not a number, so arithmetic on one is an error, and a ninth flag on a `u8` is an error rather than a silent change of layout. `match` does not apply to a set. ## Optionals `T?` holds a `T` or `none`. A value standing where an optional is wanted becomes one; that is the only conversion the language makes on its own. `if let` and `while let` take the value out under a name, and `== none` and `!= none` ask without taking it out. There is no operator that takes the value out without asking. ```kest module maybe import std.io fn find(xs: [i32], wanted: i32) -> i32? { for i in 0..len(xs) { if xs[i] == wanted { return i } } return none } fn main() -> i32 { let xs = [4, 8, 15] if let at = find(xs, 8) { io.print("at {at}") } if find(xs, 16) == none { io.print("not there") } return 0 } ``` ```text at 1 not there ``` `if let` and `while let` bind a name and nothing else: there are no patterns. An optional of an optional is two questions that stay apart, and a value becomes an optional only once, so `1` does not fit where an `i32??` is wanted. ## Saying that something failed There are no exceptions and no built-in result type. A function that can fail picks one of three shapes, by what the caller can do about it: - **`T?`** when there is nothing to say beyond "there is none": `get`, `find`, `os.read`, `text.number`. - **`bool`** when the caller only needs to know whether it worked: `fit`, `table.fit`. - **An enum** when the caller handles different reasons differently. An enum may take types, `enum Answer { Held(T) Trouble(text) }`, and `match` makes the caller answer every case. None of them stops the program. A fault is reserved for what the machine cannot make sense of. ## Vectors `vec2`, `vec3` and `vec4` are two to four `f32`s named `x`, `y`, `z` and `w`. They are the only types with operators the language did not already have: `+`, `-`, `*` and `/` between two vectors of one width a component at a time, `*` and `/` between a vector and an `f32` on either side, unary `-`, `==`, `!=` and the four assignment forms. ```kest module falling import std.io struct Body { at: vec3 speed: vec3 } fn fall(b: Body, dt: f32) -> Body no.alloc no.host deterministic { let down = vec3(0.0, -9.81, 0.0) return Body(b.at + b.speed * dt, b.speed + down * dt) } fn main() -> i32 { let b = fall(Body(vec3(0.0, 10.0, 0.0), vec3(1.0, 0.0, 0.0)), 0.5) io.print("{b.at.x} {b.speed.y}") return 0 } ``` ```text 0.5 -4.905 ``` Each component is the single `f32` operation it would be written out as, so vectors give the same bits everywhere. A vector is laid out as a C struct of its floats; `vec3` is twelve bytes aligned to four. A struct the program declares never gets operators. `std.vec` builds `dot`, `length`, `distance`, `direction`, `lerp`, `cross` and `perpendicular` on top. ## What compares, hashes and prints A value laid out flat compares with `==` when everything in it compares: numbers, `bool`, text, flags, vectors, a struct whose fields compare, a fixed run of something that compares, and an enum whose cases carry only things that compare. Arrays, stores and function values never compare, nor does anything holding one, because equal contents and the same handle are different questions. A reference compares as an identity. `hash(x)` gives a `u64` for exactly the values that compare. It is the same number on every machine and in every version: FNV-1a over the bytes for text, and fixed arithmetic for everything else. So a struct can be a table key, and two structs with the same fields are one key. A float that is not a number is not equal to itself, so a table refuses it as a key. Nothing is salted; a program taking keys from someone it does not trust hashes them with something of its own first. A hole in a string writes any value that compares, the way a program would write it: `Npc("ann", 7)`, `[1, 2, 3]`, `Door.Locked(7)`, `State.Moving | State.Hurt`, or `none`. A whole-number float keeps its point (`3.0`), the shortest spelling that reads back as the same number is used, and the three values without a spelling print as `inf`, `-inf` and `nan`. Arrays, stores, references and function values have no text. ## Containers and the heap Arrays, stores and text live on the program's heap. What putting one more entity into each costs a frame, when nothing said how many were coming, is roughly one piece of text (16 bytes), one array element (about 50 bytes), one table pair (about 75) or one store element (about 115), because each grows by doubling. Told how many are coming, with `array(n, v)`, `store(n)`, `room` or `table.refill`, the frame pays nothing: the room is made once, before the frame. A store or array whose elements are removed and added again forever reuses its room and does not grow. Memory nothing can reach is given back by the collector; [Host memory](host-memory.md#the-collector) says when. # Text `text` is UTF-8 bytes and a length. This page covers writing strings, building text, walking it cheaply, and where Unicode stops being the language's business. ## Contents - [Strings and holes](#strings-and-holes) - [Escapes and bytes](#escapes-and-bytes) - [Text is its bytes](#text-is-its-bytes) - [Finding and cutting](#finding-and-cutting) - [Building text](#building-text) - [`std.text`](#stdtext) - [Characters](#characters) - [What a host decides](#what-a-host-decides) ## Strings and holes A string may hold code in braces, a hole, and the hole's value is written into the text. There is no `+` on text: text is joined with holes. ```kest module greet import std.io fn main() -> i32 { let name = "ann" let apples = 3 io.print("{name} has {apples} apples, {apples * 2} by tomorrow") io.print("a hole holds code, so {len("quotes")} need no escape") return 0 } ``` ```text ann has 3 apples, 6 by tomorrow a hole holds code, so 6 need no escape ``` A hole may hold any value that compares, written the way a program writes it; see [Data](data.md#what-compares-hashes-and-prints). A string with a hole is built while running, on the heap, so a function that promises `no.alloc` may hold a plain string but not fill a hole. A hole holds one value and nothing after it, so there is no width or format to write there (`"{n:4}"` is an error); an empty hole `{}` is an error, and so is a comment inside a hole. ## Escapes and bytes The escapes are `\n`, `\t`, `\r`, `\\`, `\"`, `\{`, `\}`, `\0` and `\u{...}`. `\u{...}` is a character by its number, one to six hex digits up to `U+10FFFF`, written as its UTF-8 bytes; surrogates are refused. A file may not hold a carriage return inside a string, or an invisible character such as a zero-width joiner or a direction mark, written as itself: those are written with `\r` or `\u{...}` so a reader can see them. `'a'` is one byte, of type `u8`. It is not a character: `'ı'` is two bytes and is an error. `\0` is an ordinary character inside text: text carries its length, so a zero byte in the middle is counted like any other. ## Text is its bytes `len(t)` counts bytes, `t[i]` is a byte, and `for b in t` walks the bytes. Text compares with `==` and `<` by its bytes, which is a total order, and `t != ""` asks whether anything is left. There is no character type: `"hız"` is four bytes. All of these are cheap because the length is part of the value: `len` is a read, not a walk. ## Finding and cutting The builtins for searching and cutting: | Call | What it gives | Heap | | --- | --- | --- | | `find(t, needle)` | where `needle` first is, as `i32?` | none | | `find(t, needle, from)` | the same, starting at `from`, as a place in all of `t` | none | | `matches(t, at, needle)` | whether `needle` is exactly at `at` | none | | `rest(t, at)` | the text from `at` to the end | none | | `slice(t, from, count)` | `count` bytes from `from` | none | A cut is a place inside the text it was cut from and a length, so none of these copies anything. Starting past the end is an error rather than a read past it; starting exactly at the end finds nothing or gives empty text. A position below zero written as a number is refused while compiling. The cheap way to walk text is forwards, keeping what is left: ```kest module fields import std.io fn count(line: text, separator: text) -> i32 no.alloc { let seen = 0 let tail = line while tail != "" { seen += 1 if let at = find(tail, separator) { tail = rest(tail, at + len(separator)) } else { tail = "" } } return seen } fn main() -> i32 { io.print("{count("ann,bo,cy", ",")}") return 0 } ``` ```text 3 ``` ## Building text Text built a piece at a time is built as bytes. `push(out, piece)` appends a whole piece of text to a `[u8]`, and `text(out)` makes one piece of text at the end, refusing bytes that are not UTF-8. Gathering bytes copies each piece once; joining with a hole in a loop copies everything gathered so far every time round. ```kest module building import std.io fn listed(names: [text]) -> text { let out: [u8] = array() for at, name in names { if at > 0 { push(out, ", ") } push(out, name) } return text(out) } fn main() -> i32 { io.print(listed(["ann", "bo", "cy"])) return 0 } ``` ```text ann, bo, cy ``` `fit(out, piece)` appends without growing and is all or nothing: it answers `false` and leaves `out` as it was when the piece does not fit. With a buffer made once with room, `text.fitting` and `text.fittingNumber` build a line in a function that promises `no.alloc`. A `[u8]` with any bytes in it is fine; only `text(...)` cares about UTF-8. ## `std.text` What a program does with text beyond the builtins is `std.text`, written in Kest: - reading: `number` and `real` give `T?` and refuse anything that is not exactly a number of that type, including one too large for it; there are no exponents in what they read except the spellings a hole writes; - writing: `fixed(value, places)` writes a float with that many places; `left` and `right` pad to a column width in bytes; - testing: `contains`, `starts`, `ends`; - cutting and joining: `trim`, `split`, `join`, `repeat`; - ASCII case: `upper`, `lower`; - characters: see below. ```kest module words import std.io import std.text fn main() -> i32 { let line = " ann,bo,cy " let names = text.split(text.trim(line), ",") io.print("{len(names)} {names[1]} {text.join(names, " and ")}") if let n = text.number("42") { io.print("{n + 1} {text.upper("hi")} {text.contains(line, "bo")}") } io.print("{text.fixed(2.0 / 3.0, 2)} [{text.right("7", 3)}]") return 0 } ``` ```text 3 bo ann and bo and cy 43 HI true 0.67 [ 7] ``` `kest doc lib/std/text.kest` lists every function with its comment. ## Characters A character here means what UTF-8 says. `text.chars(t)` counts characters, `text.charWidth(t)` is the byte width of the character at the front of `t`, `text.charBytes(b)` is the width a leading byte announces (0 for a continuation byte), `text.charBack(t, at)` is where the character before `at` starts, and `text.charAt(t, i)` and `text.charsOf(t)` give characters as text of their own. Bytes that are not valid UTF-8 count as one character each, so a count never stops early. There is no `for` over characters. The cheap walk keeps what is left and steps by width, which reads the text once and allocates nothing: ```kest module characters import std.io import std.text fn characters(line: text) -> i32 no.alloc { let count = 0 let tail = line while tail != "" { tail = rest(tail, text.charWidth(tail)) count += 1 } return count } fn main() -> i32 { if let second = text.charAt("hız", 1) { io.print("{characters("hız")} {len("hız")} {second}") } return 0 } ``` ```text 3 4 ı ``` `charAt` counts from the start each time it is asked, so a loop over `charAt` reads the text once per character; `charsOf` walks once. ## What a host decides The language owns UTF-8 and nothing above it: that source and incoming bytes are valid, counting and stepping over characters, comparing and searching by bytes (correct for UTF-8), and ASCII case. A host owns everything that depends on a human language or a Unicode version: normalization (`é` and `e` plus an accent are different text here), collation, locale-aware case (the capital of `i` in Turkish), grapheme clusters, display width, bidirectional text and shaping. A program that needs those asks a host door for them; `examples/locale.kest` shows the line. # Functions Overloading, calling a function on a value, generics, function values, blocks, bodies that wait between frames, and walking a struct's fields. ## Contents - [Declaring a function](#declaring-a-function) - [One name, several functions](#one-name-several-functions) - [`x.f(a)`](#xfa) - [Generics](#generics) - [Function values](#function-values) - [Blocks](#blocks) - [A body that waits](#a-body-that-waits) - [Walking a struct's fields](#walking-a-structs-fields) ## Declaring a function ```kest module heal struct Npc { name: text health: i32 } fn healed(n: Npc, by: i32) -> Npc no.alloc { let after = n after.health += by return after } fn shout(n: Npc) { } ``` A function that gives nothing has no `->`; there is no `void` to write. Parameters and the result are always typed, and bodies infer the rest. [Promises](promises.md) such as `no.alloc` go after the result. Parameters are values (a struct parameter is a copy) and handles (an array parameter is the caller's array); see [Data](data.md#values-and-handles). ## One name, several functions Two functions may share a name when they take different things. The call decides by what is passed, and since nothing converts on its own exactly one matches or none does. A literal fits any width of its family, and when that leaves more than one a whole number prefers `i32` and a float prefers `f32`, the same rule that types a bare `let`. ```kest module sizes import std.io fn describe(n: i32) -> text { return "a number" } fn describe(t: text) -> text { return "text of {len(t)} bytes" } fn main() -> i32 { io.print("{describe(3)}, {describe("abc")}") return 0 } ``` ```text a number, text of 3 bytes ``` When nothing matches, the error lists every function of the name with what it takes, nearest first. `main` may not be overloaded. A file may add its own `len`, `get`, `set`, `find`, `add` or `remove`; the builtin still answers for the types the file's own does not take. ## `x.f(a)` `x.f(a)` is another way of writing `f(x, a)`, so a chain reads left to right. The function is looked for among the file's own, then in the module that declared the value's type (`std.text` for text, `std.vec` for vectors), then among the builtins, and is taken when its first parameter can be `x`. There are no methods beyond that: nothing is declared inside a type. ```kest module pots import std.io struct Pot { level: i32 } fn fill(p: Pot, by: i32) -> Pot { return Pot(p.level + by) } fn main() -> i32 { let full = Pot(1).fill(2).fill(3) let xs = [4, 5] io.print("{full.level} {xs.len()}") return 0 } ``` ```text 6 2 ``` A field that holds a function is called as that field. The module a type came from has to be imported for its functions to be found. ## Generics A function may take types as well as values, and a copy is compiled for each set of types it is called with. The types come from what is passed and where the answer goes; they are never written at the call. A type parameter may be asked for exactly two things: `compares` (`==` and `!=`, and therefore `hash`) and `orders` (`<`, `<=`, `>`, `>=`). Nothing else, so arithmetic or a field on a type parameter is an error. The body is checked once, against what the declaration asks for, and a call with a type that lacks it is refused at the call. ```kest module largest import std.io fn largest(xs: [T], start: T) -> T no.alloc { let best = start for x in xs { if x > best { best = x } } return best } struct Pair { first: A second: B } fn main() -> i32 { let p = Pair(1, "a") io.print("{largest([3, 9, 4], 0)} {largest(["b", "c"], "a")} {p.second}") return 0 } ``` ```text 9 c a ``` Structs and enums take types the same way: `Pair(1, "a")` is a `Pair`. A shape is written with its types wherever a type goes (`Pair`), and `Pair` on its own is not a type. Writing types at a call, as in `store()`, is an error that says to write `store()` and put the type on the binding. A struct has `==` from its fields but no order, because a struct with three fields has at least three orders. What sorts is told the order with a function value; see `sort.by` in [The standard library](standard-library.md). Nothing is boxed: a copy over `[vec2]` knows a `vec2` is two `f32`s. The cost is one compiled body per set of types. ## Function values A function's name is a value of its function type, and the promises are part of the type: `fn(i32) -> i32 no.alloc`. A value that promises more may go where one that promises less is wanted, never the other way. ```kest module apply import std.io fn twice(n: i32) -> i32 no.alloc { return n * 2 } fn apply(f: fn(i32) -> i32 no.alloc, n: i32) -> i32 no.alloc { return f(n) } fn main() -> i32 { let rules: [fn(i32) -> i32 no.alloc] = array() push(rules, twice) io.print("{apply(twice, 5)} {rules[0](4)}") return 0 } ``` ```text 10 8 ``` **There are no closures.** A function value names a function, and what a closure would have captured is passed beside it: a predicate that needs a threshold takes the threshold as a parameter. To run something later, store a struct holding the function and its data. A generic function is called, not handed around, and two function values do not compare. `let f = twice` binds the name to that one function, and assigning another to it is an error. To hold any function of a shape, write the shape on the `let`. ## Blocks A block is a body written where a function is called and handed to a parameter of type `block(T) -> R` (or `block(T)` for one that gives nothing). `|x| value` gives a value, and `|x| { ... }` does something and gives nothing. A block reads and writes the names where it is written. ```kest module counting import std.io fn countWhere(xs: [T], keep: block(T) -> bool) -> i32 { let n = 0 for x in xs { if keep(x) { n += 1 } } return n } fn each(xs: [T], body: block(T)) { for x in xs { body(x) } } fn main() -> i32 { let floor = 3 let total = 0 let xs = [3, 9, 4] let over = xs.countWhere(|x| x > floor) xs.each(|x| { total += x }) io.print("{over} {total}") return 0 } ``` ```text 2 16 ``` A block is not a closure: the function that takes it is compiled into each place it is called, so nothing is captured and nothing goes on the heap, and a `no.alloc` function may use one. A block may only be handed to a parameter and called or handed on; it cannot be stored, returned or given to a host. `return` inside a block is an error, and `break` only leaves a loop inside the block. ## A body that waits Work a game does over many frames (walk a route, then work, then rest) is a sequence with a pause at the end of each frame. A function can be written that way: it names a field it resumes from, and `wait` ends the call. ```kest module patrol import std.io enum GuardAt { Start Walking Looking Done } struct Guard { post: i32 posts: i32 looks: i32 at: GuardAt } fn watch(g: Guard) -> Guard resumes g.at { while g.post < g.posts { g.post += 1 wait Walking g.looks = 2 while g.looks > 0 { g.looks -= 1 wait Looking } } g.at = GuardAt.Done return g } fn main() -> i32 { let g = Guard(0, 2, 0, GuardAt.Start) while g.at != GuardAt.Done { g = watch(g) io.print("{g.at} at post {g.post}") } return 0 } ``` ```text GuardAt.Walking at post 1 GuardAt.Looking at post 1 GuardAt.Looking at post 1 GuardAt.Walking at post 2 GuardAt.Looking at post 2 GuardAt.Looking at post 2 GuardAt.Done at post 2 ``` `resumes g.at` names a parameter the function takes and gives back, and a field of it whose type is an enum the program declares. `wait Walking` sets that field to `Walking`, gives the parameter back and ends the call; the next call carries on after that `wait`. A case no `wait` names starts the body from the top. Only the parameter is kept between calls, which is what makes the state plain data that saves, loads, compares and survives a reload like any struct. So no `let`, `for`, `if let` or `match` name may be in reach of a `wait`; whatever the body needs afterwards goes in a field. A `wait` cannot be inside a `for`, a body that waits has no `defer` and no open `scratch` block at a `wait`, each `wait` names a case that carries nothing, no case is waited at twice, and a block handed to another function cannot wait. `examples/chores.kest` is a longer example. ## Walking a struct's fields `for name, value in fields(x)` is written out while compiling, once per field of the struct `x`, in declaration order. `name` is the field's name as text and `value` is the field itself with its own type; writing `value` writes that field of `x`. Each copy is checked on its own, so a call inside picks the overload for that field's type. `for value in fields(x)` leaves out the names. ```kest module inspect import std.io struct Where { x: f32 y: f32 } struct Npc { name: text hunger: i32 at: Where } fn main() -> i32 { let n = Npc("ann", 3, Where(1.5, 2.0)) for name, value in fields(n) { io.print("{name}: {value}") } for part in fields(n.at) { part = part * 2.0 } io.print("{n.at}") return 0 } ``` ```text name: ann hunger: 3 at: Where(1.5, 2.0) Where(3.0, 4.0) ``` It exists for two jobs, a save and load written once for every shape and what an inspector shows, and nothing more: nothing is kept at run time and no code writes code. `x` has to be a local or a field of one. `examples/records.kest` writes a struct to bytes with one overloaded `put` per field type and reads it back. # Promises A function may promise three things about itself after its result: `no.alloc`, `no.host` and `deterministic`. The compiler proves each one over every body the function reaches, or refuses the program at the line that breaks it. ## Contents - [The three promises](#the-three-promises) - [What reaches the heap](#what-reaches-the-heap) - [How a refusal reads](#how-a-refusal-reads) - [Promises through function values](#promises-through-function-values) - [Promises on host doors](#promises-on-host-doors) - [Filling a buffer without allocating](#filling-a-buffer-without-allocating) - [`scratch` blocks](#scratch-blocks) - [What the compiler proved anyway](#what-the-compiler-proved-anyway) ## The three promises | Promise | Means | What it is for | | --- | --- | --- | | `no.alloc` | the body takes nothing from the program's heap | a frame step that must not pay for allocation or be interrupted by the collector | | `no.host` | the body calls nothing the host provides | a function that is pure computation, safe to call while the host holds its own locks | | `deterministic` | the body answers the same bits on every machine that keeps the [simulation profile](determinism.md) | lockstep networking, replays, rollback | ```kest module step fn cooled(left: [i32]) no.alloc no.host deterministic { for i in 0..len(left) { if left[i] > 0 { left[i] -= 1 } } } ``` The promises are written in any order, each once. They are proved where they are written: a helper called from a promising function is judged by its body, transitively, and does not have to repeat the promise. A host can ask whether a function made each promise before calling it (`kest_entry_promises`). `no.host` and `deterministic` differ: a door the host declares `deterministic`, such as `Math.sqrt`, may be called from a `deterministic` body but never from a `no.host` one. ## What reaches the heap - an array literal, `array()`, `store()`, and `text(bytes)`; - a string with a hole in it; - `push`, `add` and `room`, which may grow what they are given; - a lend handed back from a host, whose header is on the heap; - a call to a host door that does not declare `no.alloc`. Everything else does not: `fit`, `pop`, `remove`, `clear`, `get`, `set`, `find`, `matches`, `rest`, `slice`, `len`, `hash`, structs, optionals, fixed runs built in place, and calls to functions whose bodies do not allocate. A `defer`red call counts like any other call. `no.alloc` is about the program's heap only: what the compiler, a diagnostic or a host's own C code allocates is outside it. ## How a refusal reads A refusal names the line that breaks the promise and then every call between it and the promise: ``` error[K0401]: this allocates, and `chain.stepFrame` promises `no.alloc` --> chain.kest:5:17 | 5 | let trail = [n, n, n] | ^^^^^^^^^ a run that can grow is one on the heap --> chain.kest:17:4 | 17 | fn stepFrame(n: i32) -> i32 no.alloc { | ^^^^^^^^^ `chain.stepFrame` promises it here --> chain.kest:18:12 | 18 | return second(n) | ^^^^^^^^^ which calls `chain.second` ``` The promise is proved twice: once over the source, which is where the path above comes from, and again over the instructions the compiler emitted. If the two ever disagree the second calls it a fault in the compiler. A misspelt promise such as `no.allocate` is an error that lists the three. ## Promises through function values A promise is part of a function type, so a call through a function value is judged by the type. A type that promises nothing is not a body that allocates; it is one nothing is known about, and calling it from a promising function is `K0402`, with the fix of writing the promise into the type: `fn(i32) -> i32 no.alloc`. Only a function that keeps the promise fits that type. A host that writes a function index into a frame is checked by the machine at the call (`K0623`). ## Promises on host doors An `extern` declares its own promises, because its body is C the compiler cannot read: `extern fn Clock.now() -> u64 no.alloc`. The machine checks the part it can see: after a call to a door that promised `no.alloc`, the program's heap must be where it was, or the call fails with `K0631`. What the host's C code does with its own memory is the host's business. ## Filling a buffer without allocating `push` may grow, so a `no.alloc` body cannot call it. `fit` is `push` that never grows: it writes where there is room and answers `false` where there is not. Room is made before the frame with `array(n, v)` followed by `clear`, or with `room(xs, n)`; `clear` keeps the room. ```kest module gather import std.io fn gather(into: [i32], many: i32) -> i32 no.alloc { clear(into) let put = 0 for i in 0..many { if fit(into, i) { put += 1 } } return put } fn main() -> i32 { let buffer: [i32] = array() room(buffer, 4) io.print("{gather(buffer, 6)} {len(buffer)}") return 0 } ``` ```text 4 4 ``` `array()` makes an array with no room, and the compiler warns (`K0347`) when a body fills one with `fit` without giving it room first. `table.fit` and `table.refill` do the same for a table, and `text.fitting` for bytes of text. ## `scratch` blocks A `scratch { }` block marks the heap when it is entered and puts it back when it is left, so a block that builds text to print costs the same every time round a loop. ```kest module frames import std.io struct Npc { name: text hp: i32 } fn tick(world: [Npc]) -> i32 no.alloc { let alive = 0 for i in 0..len(world) { if world[i].hp > 0 { world[i].hp -= 1 alive += 1 } } return alive } fn main() -> i32 { let world = [Npc("ann", 2), Npc("bo", 0)] for round in 0..3 { scratch { let line = "round {round}: {tick(world)} alive" io.print(line) } } return 0 } ``` ```text round 0: 1 alive round 1: 1 alive round 2: 0 alive ``` What is made inside may not outlive the block, and the compiler proves it: giving it back from the function, storing it in a name declared outside, or putting it into an array or store from outside is an error (`K0507`). Growing anything older than the block is also an error, so inside a block a call that is handed something older can only be made if it promises `no.alloc`. Copying out is fine: a number is a number afterwards, and `text.fitting(out, piece)` copies bytes into a buffer from outside. A host may be handed what the block made, so `io.print` works inside one, but a host that keeps it past the call keeps a pointer into memory that is about to be reused. Every way out of a block puts the heap back, including a fault or a budget running out. Blocks nest up to eight deep in one body. ## What the compiler proved anyway The proof runs whether or not a function promises anything. `kest check --cost` prints, for each function, whether it reaches the heap, whether it reaches the host, whether anything in it is outside the deterministic profile, and which promises it could make. `kest check --json` carries the same facts under `proved`. # Determinism A replay, a rollback or a lockstep game between two machines needs the same program to compute the same world everywhere. Kest writes that promise down as a versioned profile, `kest-det 4`, and a function promises to keep it with `deterministic`. ## Three questions - **Does the same source mean the same thing?** Yes. Every rule below is the language's, not the C compiler's. - **Does the same program on one machine do the same thing twice?** Yes. Nothing reads a clock, an address or the environment unless the program asks a host door, and nothing about a run is seeded from outside. - **Is a run bitwise identical on two platforms?** Yes, for everything in the profile, including `sin`, `cos`, `pow` and `atan2`. CI runs every example on Linux x86-64, Linux arm64, macOS arm64 and Windows x86-64 and fails if any of them prints a different byte. ## The profile **What a target must be.** Two's complement integers of 8, 16, 32 and 64 bits; IEEE 754 binary32 and binary64 in the default rounding mode (round to nearest, ties to even); 8-bit bytes. A host that changes the rounding mode, or turns on flush-to-zero, has left the profile. **Where state comes from.** Every allocation starts as zeros, and no value a program can read comes from an address, a clock or the order files were read in. A reference is the one value that holds something from outside the program (which handout of the process it was), and a program cannot read that: a reference has no text and no number, and it hashes by its place. **Whole numbers.** Every width wraps at its own end. Narrowing keeps the low bits; widening a signed number carries its sign. Division truncates toward zero and the remainder takes the left side's sign. Division by zero is a fault, never a value. **Sets of flags.** A set holds the bits it has names for and no others. `~` flips those bits, and a set made from a number, `State(bits)`, keeps those of its bits and drops the rest, so a set always writes itself as the set it equals. **Floats.** `f32` arithmetic rounds to `f32` at every step, and a multiply followed by an add is always two roundings: nothing is ever fused into one. Subnormals behave as IEEE 754 says. The two zeros compare equal and hash alike. Every value that is not a number has one set of bits (`0x7FC00000` for `f32`, `0x7FF8000000000000` for `f64`) as far as `bits` and `hash` can see, because processors disagree about the sign of `inf - inf`. **Floats to whole numbers.** Truncate toward zero, stop at the ends of the width, and give 0 for a value that is not a number, the same while compiling and while running. **Mathematics.** `sin`, `cos`, `pow` and `atan2` in `std.math` are written in Kest out of additions, multiplications and divisions (fdlibm's algorithms, in `std.fdlibm`), so they are the same steps on every machine. They are within an ulp of the C library's for ordinary arguments. `sqrt`, `floor` and `ceil` are host doors that IEEE 754 requires to be exact, and `std.math` declares them `deterministic`. **Order.** An array walks by index, a store by place, text by byte, a range from first to last, and a table in the order its puts and removes left, which the same operations always reproduce. **Hashing and randomness.** `hash` is FNV-1a from a fixed start for text and fixed arithmetic for everything else, with nothing taken from the run. `std.random` is a source the program holds and seeds; the same seed gives the same numbers everywhere, and none of its functions call the host. **What is outside.** Clocks, files, the program's arguments and every host door not declared `deterministic`. ## Promising it ```kest module lockstep struct Unit { x: f32 vx: f32 } fn step(u: Unit, dt: f32) -> Unit no.alloc deterministic { return Unit(u.x + u.vx * dt, u.vx * 0.98) } ``` The compiler refuses a `deterministic` function that can reach anything outside the profile, with the path to the call that does. A host asks with `kest_entry_promises(..., KEST_PROMISE_DETERMINISTIC)` before installing a step it means to replay, and writes `kest_profile()` down beside a replay or a save, because a run under another profile is a different run. ## What a host owes The three doors `std.math` declares `deterministic` are promises the host keeps: `Math.sqrt` must be correctly rounded, and `Math.floor` and `Math.ceil` exact, including for negatives and for values that are already whole. A host that binds a fast approximate square root has left the profile. `examples/determinism.kest` folds every rule above, including those doors, into one number and prints each part, so a platform that disagrees says where. The release engine (`kest build --release`) keeps the profile too, as long as the C compiler does not contract floating point on its own: GCC and MSVC respect what the generated file asks for, and clang told `-ffp-contract=fast` does not. See [Release builds](release-builds.md). # The standard library Every module is Kest source under `lib/std`, compiled with the program each time, so there is no library version to mismatch. `kest doc lib/std/.kest` prints every declaration of a module with its comment, and the reference on the documentation site is generated the same way. Each function is called through its module (`text.trim(line)`) or on a value (`line.trim()`, see [Functions](functions.md#xfa)). Importing a module compiles all of it and asks the host for every door it declares, whichever functions the program calls. An import nothing writes through is a warning (`K0511`). ## Modules | Module | What it holds | | --- | --- | | `std.io` | `print` (text and a line end) and `write` (text alone), through the host door `Io.write` | | `std.math` | `min`, `max`, `abs`, `clamp`, `sign`, `lerp`, `isNumber`, `sqrt`, `floor`, `ceil`, `round`, `sin`, `cos`, `tan`, `asin`, `acos`, `atan`, `atan2`, `pow` | | `std.vec` | `dot`, `length`, `lengthSquared`, `distance`, `distanceSquared`, `direction`, `lerp`, `perpendicular`, `cross` for `vec2`, `vec3` and `vec4` | | `std.text` | reading and writing numbers, searching, trimming, splitting, joining, case, characters; see [Text](text.md#stdtext) | | `std.table` | `Table`, a hash table: `empty`, `set`, `get`, `orElse`, `has`, `remove`, `count`, `keyAt`, `valueAt`, `keysOf`, `fit`, `refill`, `compact` | | `std.sort` | `by`, `byWith`, `ascending`, `descending` | | `std.random` | `Source`, a seeded generator: `from`, `next`, `number`, `below`, `between`, `fraction`, `chance`, `one`, `shuffle` | | `std.hash` | `start` and `join`, to fold several hashes into one | | `std.bytes` | numbers, truths and text written into and read out of `[u8]`, for saves and records | | `std.os` | `read`, `write` and `exists` for files, `argCount`, `arg` and `args`, `now` and `millisBetween`, all through host doors | | `std.fdlibm` | the algorithms `std.math` computes sines, cosines, arctangents and powers with | Most functions promise `no.alloc no.host deterministic` where they can; `kest check lib/std/.kest` prints each signature with its promises. ## Notes by module **`std.math`.** Every function comes in both widths a program works in (`f32` and `f64`, `i32` and `i64`). `asin` and `acos` answer `none` outside -1 to 1. `sqrt` of a negative and `0.0 / 0.0` give `nan`, and a value too large to hold gives an infinity; `math.isNumber(x)` is the test for a value a program can go on with, since `nan` is not equal to itself. `abs` of the smallest `i32` is itself, because negating it wraps. `sqrt`, `floor` and `ceil` are host doors; the rest is Kest, which is what makes them [deterministic](determinism.md). **`std.vec`.** `length`, `distance` and `direction` scale by the largest component before squaring, so they work for any vector whose answer fits an `f32`. `lengthSquared`, `distanceSquared` and `dot` are plain arithmetic and overflow where the squares do; they are for comparing. `direction` answers `none` for a zero vector. **`std.table`.** Keys are anything that compares, structs included. `get` answers `V?`; `orElse(t, k, fallback)` is the lookup with a fallback. Pairs are walked by place, `keyAt(t, at)` and `valueAt(t, at)` for `at` below `count(t)`, without copying. `set` may grow, so a `no.alloc` frame uses `fit`, which writes only where the key already is, after `refill` made room before the frame. A table keeps the room it has held; `t = table.compact(t)` gives it back. A key that is not equal to itself (a `nan`, or a struct holding one) is not stored. ```kest module stock import std.io import std.sort import std.table struct Item { name: text price: i32 } fn cheaper(a: Item, b: Item) -> bool no.alloc no.host { return a.price < b.price } fn main() -> i32 { let counts: table.Table = table.empty() counts.set("apple", 3) counts.set("apple", counts.orElse("apple", 0) + 2) let items = [Item("rope", 5), Item("lamp", 2), Item("map", 9)] sort.by(items, cheaper) let prices = [4, 1, 3] sort.by(prices, sort.descending) io.print("{counts.orElse("apple", 0)} {counts.has("plum")} {items[0].name} {prices[0]}") return 0 } ``` ```text 5 false lamp 4 ``` **`std.sort`.** Sorts in place, allocating nothing, by a function that promises `no.alloc no.host`. `ascending` and `descending` are the usual orders for anything that `orders`; `byWith(xs, context, before)` passes something to the order. A struct has no order of its own, so a sort of structs is always told one. **`std.random`.** A `Source` is a value the program carries: `source = random.next(source)` before each number. Nothing is global and nothing asks the host, so one seed gives one run on every machine. `shuffle` rearranges an array in place and answers the source it left off at; `one` picks an element or answers `none` for an empty array. ```kest module dice import std.io import std.random fn main() -> i32 { let source = random.from(42) let total = 0 for i in 0..3 { source = random.next(source) total += random.below(source, 6) + 1 } io.print("{total}") return 0 } ``` **`std.hash`.** `hash(x)` covers a whole value. To hash some fields of a struct, fold them: `hash.join(hash.join(hash.start, hash(item.id)), hash(item.price))`. Folding with `std.hash` makes two programs that fold the same fields agree. **`std.bytes`.** Writes numbers low byte first at their own width, floats as their bits, and text with its length, so what is written reads back as exactly itself. A `Reader` reads in order; reading past the end answers zero and marks the reader `short`, so a load reads everything and checks once at the end. **`std.os`.** Every function is a door the host binds, so a program that imports it runs only under a host that provides files, arguments and a clock; the command line does, and passes the words after `--` as the arguments. `read` answers `none` for a file that is missing, and empty text for an empty file; a zero byte in a file is read like any other, since text carries its length. A file the heap has no room to hold as text is not `none`: the command line refuses the call with `K0662`, as a host does when a door cannot do what it was asked. So is a file, or a standard input read with `Io.read`, of more than 2,147,483,647 bytes, the most a door of the command line or of the host `emit --c` writes reads into one piece of text. `now` is microseconds from an unspecified start; the command line uses a monotonic clock where the platform has one. # Embedding Kest A host is any C or C++ program that runs Kest: an engine, a tool, a server. It includes `include/kest.h`, links `libkest.a` (which needs only the C library and `-lm`), compiles a program, binds the doors the program asks for, starts a machine and calls into it. This page covers that path; [Host memory](host-memory.md) covers text, lending memory, keeping values between frames and reloading, and [Running untrusted code](untrusted-code.md) covers mods and player scripts. The API reference, generated from the header, is on the documentation site. ## Contents - [The shape of a host](#the-shape-of-a-host) - [Doors: what a program asks the host for](#doors-what-a-program-asks-the-host-for) - [Calling in: frames](#calling-in-frames) - [Sizing a machine](#sizing-a-machine) - [When a call fails](#when-a-call-fails) - [Budgets, cancelling and threads](#budgets-cancelling-and-threads) - [Versions](#versions) - [The example hosts](#the-example-hosts) ## The shape of a host The program: ```kest module rules extern fn Host.write(value: text) no.alloc fn damage(hp: i32, hit: i32, armour: i32) -> i32 no.alloc deterministic { let taken = hit - armour if taken < 1 { return hp - 1 } return hp - taken } fn announce() { Host.write("the rules are loaded\n") } ``` The host: ```c #include #include "kest.h" // The door the program declares as `extern fn Host.write(value: text)`. static void write_it(KestValue *frame, KestRuntime *runtime, void *context) { (void)runtime; (void)context; uint32_t length = 0; const char *bytes = kest_text_bytes(&frame[0], &length); fwrite(bytes, 1, length, stdout); } int main(void) { KestBuild *build = kest_build("rules.kest", NULL, stderr, KEST_FORM_TEXT, 0); if (build == NULL) { return 1; } KestHost *host = kest_host_new(); if (host == NULL || !kest_host_bind(host, "Host.write", write_it, NULL)) { kest_host_free(host); kest_build_free(build); return 1; } KestLimits limits = {0, 0, 1024 * 1024, 0}; KestRuntime *vm = kest_start(build, host, &limits); if (vm == NULL) { kest_build_report(build, stderr, KEST_FORM_TEXT); kest_host_free(host); kest_build_free(build); return 1; } kest_call(vm, kest_entry(vm, "announce"), NULL, 0); int32_t damage = kest_entry(vm, "damage"); KestValue frame[3] = {{.integer = 80}, {.integer = 25}, {.integer = 5}}; if (kest_call(vm, damage, frame, 3)) { printf("hp left: %lld\n", (long long)frame[0].integer); } else { kest_report(vm, stderr, KEST_FORM_TEXT); } kest_runtime_free(vm); kest_host_free(host); kest_build_free(build); return 0; } ``` ```sh cc -std=c11 -Iinclude host.c out/dev/libkest.a -lm -o host && ./host ``` The objects, and what must outlive what: | Object | Made by | Freed by | Notes | | --- | --- | --- | --- | | `KestBuild` | `kest_build`, `kest_build_within`, `kest_build_from` | `kest_build_free` | the compiled program; read-only once built, and it outlives every machine started from it (`kest_build_free` refuses while machines stand on it) | | `KestHost` | `kest_host_new` | `kest_host_free` | a list of bound doors; a machine copies it at start, so it may be freed once every machine using it has started | | `KestRuntime` | `kest_start`, `kest_start_untrusted` | `kest_runtime_free` | a machine: its own stack, heap and report; one build may start many | `kest_build` takes the path, the standard library directory (`NULL` for the usual search), where to write what stopped the build, the form to write it in, and a ceiling on the bytes compiling may take (0 for none). `kest_build_from` compiles files held in memory, which is how a release binary carries its program. Compiling a large program takes tens of milliseconds and starting a machine from a build takes well under one, so a host that wants many machines compiles once. The library opens a file with the C library's `fopen`, which on Windows reads a path in the process's code page. A host there that hands it paths in UTF-8, as `kest.exe` does, sets that code page to UTF-8 with an application manifest (`activeCodePage`, Windows 10 version 1903 and later; `cmake/kest.manifest` is the command line's) and calls `setlocale(LC_CTYPE, ".UTF8")`. The character type is all a path needs. A host may set any locale. The library reads and writes a number with `.` before its fraction whatever the locale says, so a program means and prints the same under `de_DE` as under `C`. ## Doors: what a program asks the host for A program reaches the outside only through `extern` functions, and a host provides each by name. The part before the dot is a capability: `Host.write` is under `Host`, `Clock.now` under `Clock`. Denying a capability is not binding it. A program that declares a door the host did not bind is refused at `kest_start`, by name, before anything runs. A host that did not write the program reads what it asks for before deciding: `kest_build_extern(build, i)` walks every door the program can call (from 0 until it answers `NULL`), `kest_build_capability(build, i)` walks the capabilities, and `kest_extern_takes`, `kest_extern_layout` and `kest_extern_gives` say what crosses at each door. A door is bound once; binding a name again is refused. A door nothing in the program calls is not on the list, and the compiler warns about it (`K0506`). A bound function receives the frame: its arguments laid out in slots, which it overwrites with its answer. A door that cannot do what it was asked calls `kest_native_failed(runtime, why)` and returns; the call in the program then fails with the host's words (`K0662`) and whatever the door wrote is not read. `std.io`, `std.math` and `std.os` declare doors too. A program that imports `std.math` asks for `Math.sqrt`, `Math.floor` and `Math.ceil`, whichever functions it calls, because the host may call any function of the program. ## Calling in: frames `kest_entry(vm, name)` finds a function once; it answers -1 for a name the program does not define, and is refused (with the copies named in the report) for a name that is several functions. Calls then go by the number. A number belongs to the build it came from, so after a reload a host asks again. `kest_call(vm, entry, frame, slots)` puts the arguments in the frame and writes the answer over them. A frame is `KestValue` slots, and a value takes one slot per scalar: - whole numbers and `bool` go through `.integer` (a `bool` is 0 or 1); - `f32` and `f64` go through `.real` (an `f32` in a slot is a double); - text is two slots, the bytes and the length; a host reads it with `kest_text_bytes` and hands it in with `kest_text`, which copies the host's bytes onto the machine's heap; - a struct is its fields in order, a `vec3` is three slots, and an enum is its tag followed by its widest case's slots. The frame has to be as wide as the larger of what goes in and what comes out; `kest_frame_slots` says how wide. `kest_frame_takes` and `kest_frame_at` say where each argument starts, `kest_frame_layout` and `kest_frame_gives` describe each argument and the answer piece by piece, and `kest_slot_of` says which member of `KestValue` a piece goes through. `kest_frame_fills` and `kest_frame_reads` let a host state what it is about to write or read, and the machine checks that against the program before the call. A host that only has words (a console, a config file) hands them over with `kest_takes_text` and reads the answer back with `kest_gave_text`. The machine checks what crosses where it can: a handle or text that did not come from this machine, a handle that is not exactly what `kest_call` or `kest_borrow` gave (an address moved from one, or a piece of text), text whose length slot runs past the end of the text it is in, a tag that is no case of the enum, or a frame too narrow are refused before the call runs. `kest_gave_text` asks the same of the text in the frame it writes out, which the host may have written over since the call (`K0632`). What it cannot check is a bound function that reads more slots than its declaration says. Calling by name costs a search; calling by number costs about the same as a call inside the program. A host that has many things to process hands a batch in one call (a lent array, see [Host memory](host-memory.md#lending-memory)) rather than calling once per item. ## Sizing a machine `KestLimits` is four numbers: stack slots, call depth, heap bytes and fuel. Zero for the first two means what the program needs, which the machine works out; zero heap means no ceiling; zero fuel means no budget. `kest_needs(build, &limits, &why)` answers the stack and depth the whole program needs; `kest_needs_of` answers for one function and what it reaches; `kest_needs_from` answers where the machine stands when the program calls into the host, which a host that calls back in from inside a door adds to what that callee needs. A program that can call itself, or calls through a function value, has no least: `why` says which, and the host gives a number of frames, which `kest_bound` and `kest_bound_of` turn into slots. `kest emit` prints the same numbers beside each function. A machine that runs out says what it needed. The heap is the ceiling a host watching a frame budget sets. Crossing it fails at the line that asked, with how much the program had, how much it asked for and what was growing (`K0617`); the machine itself running out of memory is a different code (`K0605`). `kest_heap_used`, `kest_heap_taken` and `kest_heap_most` read the heap. ## When a call fails `kest_call` answers `false` when the program faulted (a division by zero, an index past the end, a ceiling crossed, a door that failed, a budget spent), and `kest_report(vm, out, form)` writes what happened: the code, the line and the calls that led there. `kest_build_report` is the same for the build, including warnings a successful build had and why a start was refused. Every diagnostic has the same shape at compile time and at run time, in text or JSON. A fault is not a rollback. The program's state is whatever the fault left: a body that wrote half the world before faulting leaves half the world written. The machine is not spoiled, and the next call runs on that state. A host holding a world through a failure picks one of three answers on purpose: throw the machine away and start again, restore a save taken before the call, or carry on knowing what it carries on with. No `defer` runs during a fault, so state the host paired through two doors (open, close) may be left open, and the host closes it when a call answers `false`. A machine keeps the last sixteen diagnostics nobody has read (`KEST_MOST_UNREAD`) and counts the rest. A host that writes the report into a file of its own, such as one `tmpfile` reused for the life of the host, reads it back without touching a terminal. ## Budgets, cancelling and threads `KestLimits.fuel` (or `kest_fuel_set`) is a budget of steps, where a step is a backward jump or a call, plus a unit for every 64 bytes or elements an instruction such as a text join or an array copy touches. It is a count, so two machines given the same budget stop at the same place. A machine that runs out fails with `K0659`; it is not broken, and a host that gives it more with `kest_fuel_set` can call it again. `kest_fuel_left` reads what is left, and `kest_fuel_spend` lets a door charge the program for work it did in C. The cost of checking the budget is too small to measure. `kest_cancel(vm)` asks a running machine to stop. It is a single store, safe from a signal handler or another thread, and the machine stops at its next step with `K0660`. A build may be shared by any number of threads. A machine belongs to one thread while it runs: two machines of one build run on two threads at once without seeing each other, but two threads calling into one machine is undefined, and nothing locks. Start machines from any thread, but handle a failed `kest_start` on one thread at a time, since a failed start writes the build's report. A breakpoint written by the debugger is written into the build, so debug a build no other machine is running. ## Versions `kest_version()` is the version string `kest --version` prints. `KEST_ABI_VERSION` is the shape of the header; a host compares it with `kest_abi_version()` before calling anything else and stops if they differ, because a header and a library from two versions disagree about memory in ways C cannot see. `kest_profile()` names the deterministic profile. `kest_checked()` says whether the library was built with its own checks and sanitizers, which catch host mistakes a release build cannot. See [Versions and editions](editions.md). ## The example hosts - `examples/least.c` is the smallest real host: it compiles, binds by name against a table of what it provides, checks each door's layout, sizes the machine from the program and calls. It is meant to be read top to bottom. - `examples/engine.c` is shaped like a game: it builds a program, asks it for a world, keeps that world between frames, lends its own memory a frame at a time, spends a budget, saves the world and reloads the program under it. `make engine && ./examples/engine`. - `examples/embed.c` calls every door of the API, including the mistakes a host can make and what each is told. It is the place to look when a door does not behave as this page says. - `examples/tetris/` and `examples/colony/` are games drawn with raylib; see [Examples](examples.md). # Host memory What a host may hold of the program's memory, how it lends the program its own, how a world lives across frames, and how a running game reloads its rules. Read [Embedding Kest](embedding.md) first. ## Contents - [The rule underneath](#the-rule-underneath) - [Text](#text) - [Lending memory](#lending-memory) - [Keeping values between calls](#keeping-values-between-calls) - [Giving memory back](#giving-memory-back) - [The collector](#the-collector) - [Saving and reloading](#saving-and-reloading) - [What the machine cannot check](#what-the-machine-cannot-check) ## The rule underneath A machine's heap belongs to the machine. Text, arrays and stores the program makes live there, and a host holds them as handles in `KestValue` slots. A handle is a pointer and carries no stamp, so the machine cannot tell a handle that is still good from one into memory it has since reused. Most of this page is the consequences of that one fact. A reference into a store is the exception: it is a place and a stamp, so a stale one is always caught. The build that checks itself (`kest-debug` in every build, or a library built with the sanitizers) is told where every host block begins and ends, and catches several host mistakes that a release library cannot see. A host is worth running against it once. ## Text `kest_text(runtime, bytes, length, &frame[i])` copies the host's bytes onto the machine's heap and writes the two slots a piece of text takes. The copy is the point: the program may keep text as long as it likes, which no host can promise for its own buffer. Bytes that are not UTF-8 are refused (`K0611`); a zero byte is a character like any other and is copied with the rest, because text carries its length. A length past 2,147,483,647 bytes, the most `len` counts, is refused before a byte is read (`K0630`). Handing the machine a pointer of the host's own as text is refused at the call, because it did not come from this machine. So is a length in the second slot that runs past the end of the text the address is in, or is below nought; a length shorter than the text is a piece of it. `kest_text_bytes(&slot, &length)` reads text back. It is not a C string: text cut from the middle of other text is a place inside it and has no terminating zero, and text may hold a zero byte anywhere, so a copy that stops at the first zero stops short. A host passes the bytes and the length on together. Where only a C string will do, such as a path or a name, it refuses text holding a zero before copying it and ending the copy with one, as the command line does for a file's name. ## Lending memory A host can lend the program an array of its own memory instead of copying it in: ```c KestValue events = kest_borrow(runtime, event_array, count, "Event", sizeof(Event)); ``` The program sees an ordinary `[Event]` and reads and writes the host's bytes in place. The element type is named, and the machine checks the size against its own layout of that type and the alignment of the address; a mismatch is refused with the program's layout printed at the declaration (`K0610`). `kest_build_layout(build, "Event", &layout)` gives the size, alignment and each piece's offset, kind and field name before lending, so a host can compare with `offsetof` once. What the program cannot do with a lent array: - grow or shrink it: `push`, `pop`, `remove` and `clear` are refused, because the length and the block are the host's; - keep it past `kest_lend_ends(runtime, lent)`, after which a read is refused (`K0637`); - lend a type holding text, an array, a store, a reference or a function value (`K0647`), because those would be pointers the machine did not put there. A lend costs a small header on the heap whatever its size. Headers of ended lends are reused, so a host that lends and ends a batch every frame pays for its widest frame once. `text(raw)` of a lent `[u8]` is the one place a lend copies: the text is the program's, the bytes stay the host's. A host whose data is a byte buffer at an arbitrary address (a packet) cannot lend it as a wider type, because the address may not be aligned for it. It either copies the batch into an array of the type, which its compiler aligns, or lends the bytes as `[u8]` and lets the program read numbers out of them with explicit byte order. A store cannot be lent: it is a slot map, not a run of elements. A host that wants one asks the program to make it. ## Keeping values between calls The collector finds what is live by walking the machine's own slots. It cannot read the host's variables, so a handle a host keeps in its own memory across a call that allocates may be collected under it. There are two ways to be right: - **Hand it back in.** A handle passed in the frame of every call is in the walk. `examples/engine.c` passes its world into each call. - **Say so.** `kest_keeps(runtime, value)` keeps it alive until `kest_lets_go(runtime, value)` or a heap reset. It is not a count: keeping one value twice keeps it once. `kest_still_holds(runtime, value)` answers whether the machine still has the memory a value is in, and `kest_kept_where` says where it lives: `KEST_KEPT_HEAP` (gone at a reset), `KEST_KEPT_PROGRAM` (text the source wrote, which lasts as long as the build), `KEST_KEPT_LENT` (a lend's header in front of the host's block) or `KEST_KEPT_NOWHERE`. A host asks before keeping a value, not after. A host must never keep a pointer into what a handle holds: an array that grows moves its elements, and only the handle knows where they went. `kest_held_new` and the `kest_held_*` functions do all of this for the common case of one world kept across frames: `kest_held_begin` calls a function and keeps what it gives back as the world, and `kest_held_call` calls with the world in front of the other arguments. `kest_held_run(held, "ground.tiles", &count, &stride)` reads a run inside the world where it lies, so drawing a map copies nothing. ## Giving memory back **`kest_heap_reset`** throws the whole heap away between calls. Every handle the host holds is then dead, until the machine makes something new in the same place, at which point the old handle reads the new data. That is safe only for a host that keeps nothing across the reset. **`kest_scratch_mark` and `kest_scratch_rewind`** do the same for part of the heap: a host marks before calling a query that makes text or arrays, copies out what it wants (a number, or text with `kest_gave_text` into its own buffer), and rewinds. Anything the program made after the mark is gone, including anything a step pushed into the world, so a mark goes around a query, never around a step that keeps something. Eight marks may be open at once, and a rewind to an outer mark closes the inner ones. ```c uint32_t mark = kest_scratch_mark(runtime); kest_call(runtime, query, frame, room); kest_gave_text(runtime, query, frame, mine, sizeof(mine)); kest_scratch_rewind(runtime, mark); ``` Inside the program, a `scratch { }` block does the same with a proof that nothing escapes; see [Promises](promises.md#scratch-blocks). Both resets and marks are refused while the program is running (from inside a door) and while anything is lent. ## The collector The heap is a non-moving mark and sweep collector. Nothing moves, because slots carry no type tags: a walk treats every eight bytes as a possible address. A number that happens to look like an address keeps that memory alive, which costs memory and never correctness. It walks on its own when the program has been handed as much as it was holding at the last walk (with a floor of 256 KB). `kest_collect_after` changes the multiplier, and `kest_collect` walks now, which a host with a frame budget calls between frames to move the pause there. A function that promises `no.alloc` is never interrupted by a walk, because a walk happens inside an allocation. A pause is linear in what is still reachable, about 0.7 ms per megabyte on a desktop machine, so a world of about 20 MB reachable fits a walk in a 60 fps frame. There is no incremental collector; slots without tags cannot support the write barrier one needs. `kest_collected` reports each pause as it finishes, `kest_telemetry` fills counters for the heap's work, and `kest_clock` gives the machine the host's clock to time its pauses with. ## Saving and reloading A reload replaces the rules of a running game without losing its world. The protocol is two functions the program declares: `save`, which takes the world and answers bytes, and `restore`, which takes the bytes and answers a world. `kest_held_reload(held, path, said, room)` builds the new program, asks the running machine to `save`, asks a machine of the new build to `restore`, checks that every door the host has called still exists and takes what it took, and only then replaces the running machine. If any step fails, the running machine is exactly where it was, and `said` says which step stopped it. `kest_held_changed` answers whether any file the program was built from has changed. ```kest module keeper import std.bytes struct World { day: i32 gold: i32 } fn begin() -> World { return World(0, 10) } fn step(w: World) -> World { return World(w.day + 1, w.gold + 2) } fn save(w: World) -> [u8] no.host deterministic { let out: [u8] = array() bytes.putI32(out, w.day) bytes.putI32(out, w.gold) return out } fn restore(saved: [u8]) -> World no.host deterministic { let r = bytes.reader(saved) return World(bytes.readI32(r), bytes.readI32(r)) } ``` A host saving a world by its own means compares layouts: every layout has a mark (`kest_layout_mark`) folded from its size, alignment and every piece's offset, kind and name, and for an enum or a set of flags which cases or bits it has in what order. The same mark means the same shape; a different one means a field moved, changed width or was renamed, or a case or flag was added in the middle, which renumbers the ones after it. A reference is not an identity across machines, so a saved world stores the program's own identifiers and remaps them on the way back in. `kest_build_code_mark` changes when what the machine will run changes and not for a comment; `kest_build_mark` changes when any byte of any file read changes. A host caching builds asks the first; a host watching files asks the second, or `kest_held_changed`. ## What the machine cannot check Everything else a host can get wrong is refused where it is done. These are the few that are not, because a pointer carries no stamp: - A handle to a lend that has ended names whatever is lent next. - A value kept across `kest_heap_reset` reads whatever the machine puts there next. - A block lent must outlive the lend, and a lend may not claim more elements than the block holds. The checking build catches both; a release build does not. - The `context` pointer given to `kest_host_bind` must outlive every machine started with that host. - A bound function must read the slots its declaration says and no more; `kest_extern_takes` and `kest_extern_layout` are how a host checks before binding. - A machine may be sized smaller than the program needs, deliberately, to keep a program out of the rest of a frame; the machine cannot tell that from a mistake, and refuses at the line that runs out. # Running untrusted code A host that runs code it did not write (a mod, a player's script, a level from the internet) starts the machine differently and gives it ceilings. This page says what Kest promises such a host, how far each promise is kept, and what is the host's to get right. ## Starting a machine for it ```c KestHost *host = kest_host_new(); kest_host_bind(host, "Game.spawn", spawn, world); kest_host_open(host, "Game.spawn"); KestLimits limits = {0, 0, 4 * 1024 * 1024, 1000000}; KestRuntime *vm = kest_start_untrusted(build, host, &limits); ``` `kest_start_untrusted` differs from `kest_start` in three ways: - **Only opened doors.** The program may ask only for doors the host bound and then opened with `kest_host_open`. A door bound for the host's own tools is not handed to every mod; a program asking for one is refused by name (`K0663`). - **Ceilings are required.** `limits` must give a fuel budget and a heap ceiling. Zero for either is refused (`K0664`, `K0665`) rather than read as "no ceiling", because a host that forgot is exactly the host this is for. - **Only the verified machine runs.** The machine runs only bytecode the verifier proved, never a body compiled to C by the release engine, even if the host linked one in. Compile untrusted source with ceilings too: `kest_build_within(path, library, errors, form, room, work)` bounds the bytes compiling may take and the work it may do, counted in units that are the same on every machine (`K0658`, `K0666`). Without a work ceiling, a crafted file can make compiling take time that grows faster than the file. ## The threat model The attacker writes Kest source and nothing else: never bytecode (Kest has no bytecode format) and never the host. The source is compiled and run on someone else's machine by a host that started it with `kest_start_untrusted`. For that source, Kest is to promise: 1. **No memory error.** No source makes the compiler, the machine or the standard library read or write memory it does not own. 2. **Nothing but what was given.** A program reaches only the doors the host bound and opened. 3. **Everything bounded, by counts.** Running time, the heap, call depth and the compiler's own work are bounded by numbers the host sets, and reaching one is a refusal that says which, at the same place on every machine. 4. **Nothing of the process in a value.** No address, and nothing else about the process, can be read out of a value the program holds. 5. **Only the machine runs it.** Untrusted code never runs as C compiled by the release engine. Outside the model: timing side channels; bugs in the host's own doors; a door the host opened being used for what it does. ## Where each promise stands | Promise | How it is kept | | --- | --- | | No memory error | Every chunk of bytecode is verified before it runs: every slot, constant, function, door and layout an instruction names exists; every jump lands on an instruction; the operand stack has one depth on every path and never under- or overflows; every slot is read only as what it holds on every path; memory from a `scratch` block never outlives it; and the two slots of a piece of text belong to one piece. The one read the verifier cannot place, a walk's byte of text, is checked in every build. The compiler, machine and verifier are fuzzed under the sanitizers, including with bytecode no compiler wrote. | | Nothing but what was given | Every door is one the host bound; an untrusted machine takes only opened ones. A door handed a handle checks that this machine made it, text handed to a door is one verified piece, and a door's answer is refused if the program could not have made it. | | Everything bounded | Fuel, heap, compile memory (`--room`), compile work (`--work`) and every count a program can have (nesting, names, loops; see [Diagnostics](diagnostics.md#limits)) are bounded. An untrusted machine without fuel and heap ceilings does not start. | | Nothing of the process | A reference hashes by its place, not its address, and has no text or number. An audit of every value a door or instruction hands back is still to be done. | | Only the machine | An untrusted machine never enters a release-compiled body. | The verified machine costs nothing extra over a trusted one running the same program; the ceilings cost a few percent. What untrusted code gives up is the release engine, which runs the same workloads 1.4 to 10 times faster. ## What the host owns **Its doors.** What a door does with the values it is handed is the host's to get right, and it is where most real bugs will be. `kest hostile file.kest [seed]` writes the file back with a function after it for every call of every door it declares, with the values a hostile program could pass: numbers at the ends of every width, floats that are not numbers, empty text and very long text, text with a zero in it, every case of every enum, and sets of flags from the empty one to every flag the set names. The host builds that file, binds its doors as usual, calls `hostile0`, `hostile1` and so on (`hostile` answers how many there are), and runs under its own sanitizers. Each call must answer, or be refused by the door in words with `kest_native_failed`. The engine in this tree is held to it; the first run found two of its doors turning an infinite float into a number. **A second wall.** For a host that wants a fault in the machine kept out of its own memory regardless, the library builds as WebAssembly (`kest.wasm`, with `-DKEST_WASM=ON`) and runs inside a WebAssembly runtime. Every example answers the same there, at three to four times the cost of the native machine. ## Reporting a vulnerability Report it privately through [GitHub's private vulnerability reporting](https://github.com/Rawframe-Project/kest/security/advisories/new), not in a public issue. A useful report has the Kest source that shows it, what `kest --version` says, and the platform. The organization's [security policy](https://github.com/Rawframe-Project/.github/blob/main/SECURITY.md) says what happens next. # Release builds Kest has two engines for one language. The bytecode machine compiles a program in milliseconds and reloads it while a game runs. The release engine writes the same program as C for the C compiler a game ships with, which runs it several times faster. A program answers the same on both; CI runs every example both ways and compares. ## A single binary ```sh kest build --release game.kest ./game ``` `kest build --release` writes the program as C, compiles it with the compiler `CC` names (or `cc`, and `cl` on Windows) against the library and `kest.h` found beside the command line, and writes one binary named after the program without `.kest` (with `.exe` on Windows). The library is `libkest.a`, or `kest.lib` for the Windows command line, which MSVC builds. A compiler named `cl` or `clang-cl` is handed MSVC's flags, and any other `cc`'s; on Windows, run it where `cl` is on the path, such as a Developer Command Prompt, and the object `cl` writes beside the C is taken away with it. That name is letters, digits, `.`, `_` and `-`, not starting with `-`, which every shell, `cmd.exe` and file system read the same; a program named otherwise is refused (`K0663`) rather than made into a binary that cannot be moved or run everywhere. The compiler is started directly with its arguments, with no shell between, so a path with a space or a quote in it needs nothing done to it. On Windows a `CC` that names a `.bat` or `.cmd` file is the exception: Windows runs it through `cmd.exe`, which reads `%`, `^` and `&` itself. Such a wrapper still works, and what kest hands it is only the install's paths and the checked release name. `CC` is split into words at spaces and tabs: the first is the compiler and the rest are flags it is given first, as in `CC="gcc -m32"`, and a run in double quotes stays one word, as in `CC='"C:/Program Files/LLVM/bin/clang"'`. The binary carries every file the program was read from, its modules, the standard library's and the project manifest, and builds from those in memory, so it runs where there is no source and no library. Every word after the binary's name on its command line belongs to the program. A release that cannot be made says why (`K0663`). The binary carries readable source. A game that must not ship readable Kest packs the binary the way it packs its other content; there is no bytecode format to ship instead, by design (see [Versions and editions](editions.md#what-is-not-promised)). ## Inside an engine An engine with its own `main` and its own doors uses the C directly: ```sh kest emit --c rules.kest > rules.c cc -O2 -Iinclude -DKEST_NO_MAIN -c rules.c -o rules.o ``` `rules.c` is one translation unit. With `-DKEST_NO_MAIN` it exports one function, `bool kest_natives_here(KestRuntime *runtime)`, which binds every compiled body to a machine the engine started. The engine builds the same program from source as usual (`kest_build`, `kest_start`), calls `kest_natives_here` on the machine, and from then on calls into compiled bodies through the same `kest_call` and the same frames. A compiled body that calls a door goes through the host's binding as the machine would. A body the C backend cannot write is named in the file with the reason and stays with the machine, called from the compiled bodies through a door of its own; one such body costs that body and nothing above it. Over the examples and the standard library every body is written. The one thing it does not write today is a constant run of numbers containing an infinity. `examples/colony` does this: `--native 1` binds its rules as C, and without it the machine runs them from source, which is what a reload needs. The engine can switch between them at a reload. ## Keeping the two engines alike **Floating point.** The machine rounds a multiply and an add separately. The generated file asks the C compiler to do the same (no floating-point contraction), which GCC and MSVC respect. A compiler that fuses them anyway answers different bits from `deterministic` code; clang told `-ffp-contract=fast` ignores what the file asks for, so do not build release Kest with that flag. **Promises.** The release engine keeps `no.alloc` and `no.host`. It spends no fuel budget, but it does hear `kest_cancel` at the back of every `while`, so a runaway loop in a release still stops when asked. **Untrusted code.** A release is for code its author trusts: nothing proves the C a host compiler made the way the verifier proves bytecode. A machine started with `kest_start_untrusted` never enters a compiled body, even one the host linked in. See [Running untrusted code](untrusted-code.md). # The command line `kest` is the compiler, the runner and every tool, and it is a host like any other: it provides the doors `std.io` and `std.os` declare. `kest help` prints the same list as this page. ## Contents - [Commands that read a program](#commands-that-read-a-program) - [Commands that read a file](#commands-that-read-a-file) - [Projects and tools](#projects-and-tools) - [Options](#options) - [Output, JSON and exit status](#output-json-and-exit-status) - [Editors](#editors) - [The debugger](#the-debugger) ## Commands that read a program These read the files named and everything they import. The first file settles where imports resolve from. | Command | What it does | | --- | --- | | `check ...` | resolves everything and reports every error and warning at once. Prints what the first file declares, and one line per imported module. `--cost` adds what the compiler proved about each function | | `run ...` | compiles and runs `main`; the exit status is what `main` answered | | `call [argument]...` | calls one function and prints what it gives. Arguments are read as literals (`min 3 7` is the `i32` one, `min 3.5 7.5` the `f32` one); a name with a dot is a function of an imported module, written as `check` prints it | | `tick [n]` | calls `onEvents(events: [i32])` once with `n` events and `onEvent(event: i32)` `n` times, whichever the file defines, and reports the crossings and what the heap did. `4,5,6` instead of a count lends those events. `--reset` throws the heap away between events | | `emit ...` | prints the bytecode, with what each function needs to be called; `--c` prints the program as C instead | | `profile ` | runs the program and reports, in counts, the steps of the budget, the calls of each function, the crossings into the host and the heap. There are no durations: a clock is the host's | | `debug ` | runs the program with breakpoints, see [below](#the-debugger) | | `hostile [seed]` | writes the file back with calls to every door it declares, with hostile arguments, for a host to run; see [Running untrusted code](untrusted-code.md#what-the-host-owns) | ``` $ kest call examples/math.kest factorial 5 120 $ kest profile examples/math.kest 42 step(s), 15 call(s), 2 crossing(s) into the host, 48 byte(s) of heap and 48 at most examples.math.factorial#i32 4 call(s) examples.math.gcd#i32,i32 6 call(s) ``` ## Commands that read a file These read each file on its own and follow no imports, since what a file is does not depend on what it imports. One file that cannot be read does not stop the rest. | Command | What it does | | --- | --- | | `fmt ...` | prints the file in the one form. `-w` rewrites each file and names the ones it changed; `--check` names the files `-w` would rewrite and exits non-zero. A file that does not parse is reported and never rewritten, and neither is one whose formatted text does not hold every word and comment the file holds, in order; the editor's formatting through `kest lsp` is held to the same. A rewrite goes through a file beside the target and a rename, so an interrupted run leaves the original | | `parse ...` | prints the syntax tree | | `lex ...` | prints the tokens, whatever else is wrong with the file | | `doc ` | prints what the module declares, each declaration as written with the comment above it, as Markdown. A comment directly above a declaration is about it; comments before the first declaration are about the file | ## Projects and tools | Command | What it does | | --- | --- | | `new ` | makes a directory with a manifest, a program and a test. The name is the manifest's `project` line, so a name that is not UTF-8, has a control character in it (a line break among them) or has a directory longer than 255 bytes is refused with `K0667` before anything is made | | `build [file]` | compiles and says nothing when it compiles. Without a file, the project's entry. `--release` makes a binary, see [Release builds](release-builds.md) | | `test [file]...` | runs each program and reports which answered 0; without files, the project's tests | | `doctor [dir]` | prints the version, where the standard library is looked for and whether it was found, and what the project says about itself | | `lsp` | the language server, see [Editors](#editors) | | `dap` | the debugger for an editor, over the Debug Adapter Protocol | ## Options | Option | Meaning | | --- | --- | | `--json` | everything the command says, as JSON | | `--room ` | the most memory the whole command may ask for, compiling and the heap the program runs on together: bytes, or a number with `K`, `M` or `G`. Compiling past it is `K0658`; the program past it is `K0617` | | `--work ` | the most work compiling may do, counted the same on every machine (a word read, a piece of the tree, an instruction laid down or proved). Past it is `K0666` | | `--fuel ` | the most steps `run`, `tick` and `call` may take; past it is `K0659` | | `--` | everything after it is the program's own; `std.os.args` hands it over | | `--version` | prints the version, ABI, JSON schema, profile and edition | Without `--room`, `--work` or `--fuel` there is no ceiling. ## Output, JSON and exit status What is wrong goes to standard error and what a program or command answers goes to standard output, so `kest check x.kest > declared` keeps the answer and shows the mistakes. A command that worked writes nothing to standard error except warnings. With `--json`, the object goes to standard output and what the program itself printed goes to standard error; with `call`, the value goes to standard output alone, so `$(kest call ...)` is the value. Every JSON object starts with `schema`, the version of the JSON's shape (4 today), and has `diagnostics` and `errors`. Each diagnostic has `severity`, `code`, `file`, `line`, `column`, `offset`, `length`, `message`, and where they apply `notes`, `suggestion` and `leftOut`. `check --json` adds every type with its layout, every function with its parameters, result, promises, what was proved about it and a `signature` hash that changes only when a caller would see a change, and every constant. `emit --json` adds the instructions, the layouts with their marks, the doors the program asks for, and what each function needs to be called. `doc --json` adds the module, what the file says about itself and every declaration. `hostile --json` adds `seed`, `calls`, `unmakeable` (the doors taking what a program cannot make) and the file it writes as `text`. `debug` is a conversation with a person and refuses `--json`; `dap` is the debugger an editor drives, and `lsp` and `dap` speak their own protocols. Every command that compiles a program (`check`, `emit`, `build`, `run`, `call`, `tick`, `profile`, `lex` and `parse`) reports `cost`, the bytes reading and compiling took, and `work`, the units of work. The exit status is 1 when anything was refused, and otherwise what `main` returned (0 to 255). A warning is not a refusal. ## Editors `kest lsp` answers an editor over the Language Server Protocol on standard input and output. It is the same build as `kest check`, so what the editor shows and what the command line says cannot differ. It provides diagnostics, hover, go to definition, references, document and workspace symbols, rename, completion and formatting. A rename of a name a file declares at its top level edits every file of the project that names it, the declaring one included, in one edit across them; it is refused with a message, rather than done in part, for a name declared in the standard library or outside the project's directory, for one named by a file outside it, in a file in no project (which a `kest.project` beside it mends), in a project that does not build, and when there was no room to find every place the name is written. A link to a directory is not part of the project, and inside and outside are decided where a path really leads. A reference list is refused the same way when there was no room to keep every place. A rename or a reference list may be asked from where a name is declared as well as from where it is used, and a reference list asked with `includeDeclaration` has the declaration in it. It reads unsaved buffers, every open one, and a file importing an edited buffer is checked against what is on screen. What is wrong with no file in particular, such as a `kest.project` that cannot be read, is shown at the start of the open file, and so is a build that ran out of memory (`K0639`), as the command line says it. A module the open file reaches that does not build is shown, with its first mistake, on the line that imports it, or on the import it is reached through; that module's own file is sent what is wrong with it, and is sent an empty list once a build reads it clean again, unless it is open, when its own build says what its list holds. Files are named to the editor from the root, the standard library's included when `KEST_LIB` or the path `kest` was started by is relative. Every request is answered: one it ran out of memory answering gets error `-32603` saying so, and a message it cannot read gets an error with no id (`-32700` when it is not JSON). The VS Code extension is in `editors/vscode` and ships in the release archive. Its one setting, `kest.path`, is the `kest` command to run. It starts `kest lsp`, highlights Kest, and has a *Kest: debug this file* command that starts `kest dap`. ## The debugger ``` $ kest debug game.kest > break 42 breakpoint at game.kest:42:9 in game.step > run stopped at game.kest:42:9 in game.step > where -> game.kest:42:9 in game.step game.kest:88:12 in game.main > locals world slot 0 12 > next stopped at game.kest:43:5 in game.step > continue ``` `break ` sets a breakpoint in the named file and `break other.kest:12` in another; `step` stops at the next instruction anywhere, `next` steps over calls, `where` lists the frames innermost first, and `locals` shows each slot under the name the body gave it (`not written yet` for one the body has not reached). A breakpoint is written into the bytecode and taken out again when hit, so a machine nobody is debugging pays nothing. A breakpoint inside a call a host makes back into the program from a door cannot stop there (`K0708`), because the host's C frame is gone by the time anyone could resume. `kest dap` is the same debugger driven by an editor: breakpoints in the gutter, the call stack, a frame's variables, continue, step over, step into and step out. The program's output goes to the editor's debug console. It cannot pause a running program. A message it cannot read is said in the debug console, and every request it reads is answered. # Diagnostics The compiler reports every error it can find in one pass, not the first. Each has a stable code, the place, the reason, and what to write instead where that is known. Failures while running have the same shape, so nothing that reads diagnostics needs to know which kind it has. ## Reading one ``` error[K0201]: expected end of line, found `{` --> typo.kest:16:15 | 16 | let p = P { x: 1, y: 2 } | ^ a struct is built by position, in the order its fields are declared: `P(...)` ``` A diagnostic about more than one place shows each: a broken promise shows the line that breaks it, the promise, and every call in between; a failure while running shows the calls that led to it, outermost last. A diagnostic shows at most eight places and says how many it left out. A warning starts with `warning` and does not stop the build. ## Codes A code's meaning does not change between versions; its words may be improved. The first two digits say where it comes from: | Codes | From | | --- | --- | | `K01xx` | reading the characters of a file: an unterminated string, a byte that begins no character, an escape that is not one | | `K02xx` | the shape of the program: a missing bracket, a statement that cannot start there | | `K03xx` | types and bodies: an unknown name, a type mismatch, a missing case, an argument count | | `K04xx` | promises: `no.alloc`, `no.host` and `deterministic` | | `K05xx` | what cannot be compiled: a limit reached, a constant that cannot be worked out, an unused declaration | | `K06xx` | running: division by zero, an index past the end, a ceiling, a budget, a failed door, a host mistake caught at the boundary | | `K07xx` | files and modules: an import that is not found, a module in the wrong place, a file that cannot be read | ## The mistakes newcomers make These are what people and models new to Kest write most often, and what the compiler says. | Written | Said | Instead | | --- | --- | --- | | `max(1, 2)` without importing | `K0306` unknown name `max` | `import std.math` and write `math.max(1, 2)` | | `P { x: 1, y: 2 }` or `P(x: 1)` | `K0201` a struct is built by position | `P(1, 2)` | | `io.print(count)` | `K0310` `value` expects `text`, found `i32` | `io.print("{count}")` | | `"{f(\"x\")}"` | `K0102` a hole holds code, so a string inside one needs no escape | `"{f("x")}"` | | `"{n:4}"` | `K0201` expected the end of the hole, found `:` | `"{text.right("{n}", 4)}"` with `import std.text` | | `fn hurt(n: Npc) { n.hp -= 1 }` | warning `K0346`: the parameter is a value, so the write is discarded | `fn hurt(n: Npc) -> Npc` and give the changed one back | | `store()` | `K0211` the type is not given where it is called | `let nodes: store = store()` | | `if (x < 3) { }` | `K0213` a condition is written without brackets round the whole of it | `if x < 3 { }` | | `match` over a number or text | `match` chooses between the cases of an enum | `if` | Three mistakes the compiler cannot refuse: a field of a parameter written and not given back (it warns), `remove(xs, i)` inside `for i in 0..len(xs)`, which reads past the end once something is removed (walk a store instead, or gather what to remove and remove it after), and treating a struct as shared when it is a copy. ## Warnings worth reading | Code | Says | Why it is there | | --- | --- | --- | | `K0346` | a write to a parameter's field is discarded | the most common bug for someone coming from a language where objects are references | | `K0347` | an array has no room, so every `fit` into it writes nothing | `array()` makes no room; give it some with `room` or `array(n, v)` | | `K0506` | nothing calls an `extern`, so no host is asked for it | a host author reading the file would bind it for nothing | | `K0508`, `K0509` | nothing reads a constant, nothing names a type | dead declarations | | `K0511` | nothing writes through an import | an import is read and compiled whether used or not | | `K0512` | nothing reads a local | a value worked out for nobody, or an `if let` whose name could be `!= none` | These are said about the file that was named, not the library it imports. ## JSON `--json` emits the same set, notes and suggestions included, for tools and for models repairing their own output: ```json { "schema": 4, "diagnostics": [ { "severity": "error", "code": "K0309", "file": "bad.kest", "line": 8, "column": 12, "offset": 109, "length": 7, "message": "`doc.hurt` takes 2 arguments, found 1", "notes": [ {"file": "bad.kest", "line": 3, "column": 19, "message": "this one was not written"} ] } ], "errors": 1 } ``` A diagnostic about a whole file has `file` and no line; one about the whole program has neither. `suggestion` is the line shown under the caret, and `leftOut` counts the places that did not fit. `schema` changes when a field changes meaning or goes away, not when one is added; see [Versions and editions](editions.md). ## Limits A few numbers are limits because an instruction holds them in two bytes or a frame counts them in one. Each is a diagnostic with the number in it (`K0502` for how many, `K0503` for how far, `K0630` for more than `len` can count), never a wrap or a silent cut: | At most | What | | --- | --- | | 256 | names in a function, counting its parameters | | 16 | loops one inside another | | 128 | expressions one inside another | | 32 | `break`s in one loop, and 32 `continue`s | | 32 | `defer`s in a function | | 65535 | bytes of code a jump reaches, or a loop reaches back | | 8 | `scratch { }` blocks one inside another in one body | | 64 | `scratch { }` blocks one machine holds open at once | | 8 | things one `match` chooses between at once | | 256 | combinations one `match` answers before it needs an `else` | | 65535 | elements in a `[T; N]`, and at least one | | 65535 | bytes, and slots, in one value: a struct, an enum, a `[T; N]`, or an optional, which is what it holds and one byte more (`K0327`) | | 65535 | slots a function's names hold at once, and slots of values it works on at once, such as two values of 32768 slots side by side in an array being made | | 65536 | constant values in one function, counting every element of a table it reads where it is written | | 65536 | doors a program asks the host for | | 2147483647 | elements in an array or a store, and bytes in text | | 16777215 | places in one store | | 1099511627775 | places a process hands out, counting the ones reused | All but the last three are found while compiling. The rest are met while running. # Versions and editions `kest --version` prints five numbers, and each moves for a different reason: ``` kest 0.0.1, abi 4, json 4, profile kest-det 4, edition 2026 ``` | Number | What it versions | Read by | | --- | --- | --- | | `kest 0.0.1` | the release, by Semantic Versioning | people | | `abi 4` | the shape of the C API in `include/kest.h` (`KEST_ABI_VERSION`, `kest_abi_version()`) | hosts | | `json 4` | the shape of the JSON every command writes under `--json` (`schema` in each object, `KEST_JSON_SCHEMA`); `lsp` and `dap` speak their own protocols instead | tools | | `profile kest-det 4` | what `deterministic` promises (`kest_profile()`), see [Determinism](determinism.md) | hosts keeping replays and saves | | `edition 2026` | the language a program is read in (`KEST_EDITION`) | programs | ## What a program is promised **A program is read in the edition it names.** A project names its edition with an `edition` line in `kest.project`, and a project that names none is read in `2026`, the first. A change that would stop a program compiling, or make it mean something else, is only made in a new edition, and a later compiler reads a program in the edition it names the way it was read before. **A warning comes first.** Anything a new edition refuses is warned about in the edition before it, with its own code and what to write instead. A name that was retired says what replaced it: `vec.add` is refused with `a + b` beside it. **Every edition gets what cannot break a program:** syntax where no program could have written anything before, library functions beside the existing ones, and new warnings. Two kinds of fix apply to every edition because no program has a right to the old behaviour: a behaviour that contradicted the documentation, and a hole in what [Running untrusted code](untrusted-code.md) promises. Both are named as what they are in the changelog. **Diagnostic codes are stable.** `K0342` keeps meaning what it means; the words under it may be improved. ## What hosts and tools are promised Before 1.0.0, nothing a host or a tool reads is frozen. The C API, the JSON and the shape of the standard library may change between any two releases, and each change says in the changelog what a host or tool has to do about it. The numbers still tell a host which shape it has: - A host compares `KEST_ABI_VERSION` with `kest_abi_version()` before calling anything and stops when they differ. The ABI number goes up whenever anything a host can see changes: a function's arguments or answer, a struct's fields or their order, an enum's cases or their numbers, or what any of them mean. It does not go up for something added at the end, which an older host never sees. - A tool reads `schema` first. It goes up when a field changes meaning, is removed, or is added to a list that was said to be complete, and not when a field is added beside the others. - A host keeping a replay or a save writes the profile down beside it. Its number goes up only when what a program can observe about arithmetic changes. From 1.0 on, these become the promises: the ABI frozen for all of 1.x except additions at the end, schema 4 objects readable by schema 4 tools for all of 1.x, and a program that checks under one 1.x checking under every later one. ## What is not promised **The bytecode is not a format.** It is internal, unversioned and not stable between any two builds of the compiler, even of the same commit on two machines. Nothing reads it back; a program ships as its source beside the machine, or as a [release binary](release-builds.md) that carries its source. Compiling is fast enough (a hundred thousand lines in about two hundred milliseconds) that a cache would buy nothing worth a format. **A reference is not an identity outside its machine.** A saved world stores the program's own identifiers. ## How the language changes A change to syntax, to what a program means, to the shape of the standard library, to a door of the C API, to a name in the JSON or to the deterministic profile starts as a GitHub issue labeled `feature` whose body carries the design: what changes, why, what it breaks and for whom, what else was considered, and which edition it lands in. The reasoning of a change that is made ends up in the documentation of the part it governs. # Coming from Lua or Rust What is different in Kest, ordered by how often it trips people up. Each point links to the page with the whole story. **A name keeps its module.** After `import std.math`, `max` is written `math.max`. There is no `use`, no bare import, and no global `print`: printing is `io.print` from `std.io`, and it takes text. See [Language basics](language-basics.md#files-and-modules). **A struct is built by position.** `Point(3, 4)`, in the order the fields are declared. There are no struct literals with names and no named arguments. See [Data](data.md#structs). **A struct is a value, an array is a handle.** Handing a struct to a function hands over a copy, so writing its fields changes nothing for the caller; give the changed struct back. Arrays, stores and tables are handles and are shared. This is the mistake Lua programmers make most. See [Data](data.md#values-and-handles). ```kest module bodies import std.io struct Body { x: f32 speed: f32 } fn moved(b: Body, dt: f32) -> Body { let after = b after.x += b.speed * dt return after } fn main() -> i32 { let b = Body(0.0, 2.0) b = moved(b, 0.5) io.print("{b.x}") return 0 } ``` ```text 1.0 ``` **Arrays count from zero**, and reading past the end stops the program instead of answering `nil`. **Numbers are sized and never convert on their own.** A whole number is `i32` and a float is `f32` unless written otherwise, and `f32(n)` converts. Whole numbers wrap at their width; a float converted to a whole number truncates and saturates. See [Language basics](language-basics.md#numbers-and-conversions). **There is no `nil`.** A value that may be missing is `T?`, opened with `if let`, and asked about with `== none`. See [Data](data.md#optionals). **`match` is for enum cases only.** Numbers and text are chosen between with `if`. An `if` gives a value with `->` arms: `let s = if hp > 0 -> "alive" else -> "down"`. There is no ternary. See [Data](data.md#enums-and-match). **Text is bytes and is joined with holes.** `"{name} has {n}"`, never `+` or `..`. `len` counts bytes, and characters are what `std.text` says UTF-8 means. See [Text](text.md). **No closures.** A function value names a function, and what a closure would capture is passed as an argument. For a body written at the call site, use a [block](functions.md#blocks): `xs.countWhere(|x| x > floor)` reads `floor` where it is written. **No exceptions, no `Result`, no `?` operator.** A function that can fail answers `T?`, `bool` or an enum of its own. See [Data](data.md#saying-that-something-failed). **No lifetimes, no borrow checker, no `unsafe`.** Memory is collected. Entities that point at each other live in a `store` and hold `ref`s, which go stale safely when what they named is removed. See [Data](data.md#stores-and-references). **Generics ask for two things only.** A type parameter may require `compares` or `orders`, and nothing else; there are no traits, no operator overloading and no methods declared inside types. `x.f(a)` calls `f(x, a)`. See [Functions](functions.md). **The compiler proves performance promises.** `no.alloc`, `no.host` and `deterministic` on a function are checked over everything it calls. A frame step is usually all three. See [Promises](promises.md). **The program can only do what the host lets it.** There is no file, clock or network access except through doors the host binds; the command line binds files, arguments and a clock through `std.os`. See [Embedding Kest](embedding.md#doors-what-a-program-asks-the-host-for). **One layout.** `kest fmt -w` writes it; there are no style options. Braces always, no semicolons, no parentheses around conditions, `//` comments only. # Examples Every program under `examples/` checks its own answers and exits with which check failed, so `kest run examples/.kest` answering 0 means it works. CI runs every one of them on every platform, under both engines, and compares what they print. ## Two games **The colony** (`examples/colony/`) is a colony simulation whose rules are Kest and whose window is a raylib host in C. Colonists get hungry and tired, find jobs by a breadth-first search, chop trees, haul wood to a stockpile, sow and reap fields and build walls. The player marks work with the mouse. It shows a world kept across frames by the `kest_held_*` doors, the host reading the map where it lies with `kest_held_run`, saving through `std.bytes`, reloading the rules under a running world, and the same rules run by the machine or compiled to C (`--native 1`). ```sh git clone --depth 1 --branch 5.5 https://github.com/raysan5/raylib.git ../raylib make -C ../raylib/src PLATFORM=PLATFORM_DESKTOP cmake --preset dev -DKEST_RAYLIB=$PWD/../raylib/src cmake --build --preset dev --target colony out/dev/examples/colony/colony out/dev/examples/colony/colony --size 512x384 --people 512 --native 1 ``` Run it from the root of the tree. Keys: `1` chop, `2` build a wall, `3` sow a field, `0` cancel; drag with the left button to mark, move with `WASD` or the arrows, zoom with the wheel. `--frames n` runs that many frames with no player and prints what a frame cost; `--shot file.png` saves the last one. `kest run examples/colony/game/trial.kest` plays five simulated minutes with no window and checks the result. **Tetris** (`examples/tetris/`) is a Tetris clone written for LÖVE in Lua, brought over: the rules are `examples/tetromino.kest`, and `examples/tetris/game.kest` adapts them to an engine that keeps the game between frames and draws through two doors. `cmake --build --preset dev --target tetris` with `KEST_RAYLIB` set the same way, then `out/dev/examples/tetris/host`. `kest run examples/tetromino.kest` plays a whole game with a player written in Kest that drops every piece where it lands lowest. ## Hosts - `examples/least.c` with `least.kest`: the smallest host, to read top to bottom. - `examples/engine.c` with `engine.kest`: a game-shaped host that keeps a world, lends memory, spends a budget and reloads. - `examples/embed.c` with `embed.kest`: every door of the C API, including the mistakes a host can make. Every build makes them, in `out//examples`. ## Programs by topic | Topic | Examples | | --- | --- | | first programs | `math`, `world`, `player`, `tree`, `state` | | frames over arrays of structs | `ants`, `physics`, `frame`, `rows`, `inline` | | stores and references | `quests`, `registry`, `holding`, `lookup`, `settlement` | | enums, flags, optionals | `state`, `flags`, `tree`, `lookup` | | text | `words`, `pieces`, `parse`, `scan`, `lines`, `locale` | | numbers and determinism | `numbers`, `determinism`, `vectors`, `chance`, `ordering` | | functions | `shapes`, `boxes`, `methods`, `blocks`, `carried`, `chores`, `records` | | memory | `grow`, `queue`, `churn`, `borrow` | | saving and reloading | `saving`, `records`, `held` | | the host boundary | `host`, `events`, `embed`, `engine`, `least`, `twins` | | modules and projects | `game` with `game/npc.kest`, and `slice/`, a whole project with tests | `examples/slice/` is a small colony written as a project (`kest.project`, modules under `src`, a test under `tests`), with rules, a save format and a word list at once. # Standard library reference Every module of `lib/std`, as `kest doc` prints it: each declaration as it is written, with the comment above it. ## `std.bytes` Numbers, truths and text written into a run of bytes and read back out of one, which is what a save, a reload and a record on disk are made of. Every number is written low byte first at its own width, a float as its bits, so what is read back is what was written and the same bytes on every machine. Text is the number of bytes it is, as a `u32`, and then the bytes. Writing is adding to the end of a run of bytes, so a save is a run of these. ### `putU8` ```kest fn putU8(out: [u8], value: u8) no.host deterministic ``` ### `putBool` ```kest fn putBool(out: [u8], value: bool) no.host deterministic ``` ### `putU32` ```kest fn putU32(out: [u8], value: u32) no.host deterministic ``` Written out a byte at a time rather than in a loop of four: the loop was most of what writing one cost. ### `putI32` ```kest fn putI32(out: [u8], value: i32) no.host deterministic ``` ### `putU64` ```kest fn putU64(out: [u8], value: u64) no.host deterministic ``` ### `putI64` ```kest fn putI64(out: [u8], value: i64) no.host deterministic ``` ### `putF32` ```kest fn putF32(out: [u8], value: f32) no.host deterministic ``` ### `putF64` ```kest fn putF64(out: [u8], value: f64) no.host deterministic ``` ### `putText` ```kest fn putText(out: [u8], value: text) no.host deterministic ``` ### `putBytes` ```kest fn putBytes(out: [u8], values: [u8]) no.host deterministic ``` ### `putI32s` ```kest fn putI32s(out: [u8], values: [i32]) no.host deterministic ``` ### `putF32s` ```kest fn putF32s(out: [u8], values: [f32]) no.host deterministic ``` ### `Reader` ```kest struct Reader { bytes: [u8] state: [i32] } ``` Reading goes along a run of bytes from the start. Two handles, held in step: the bytes, and where the reading has got to with whether it ever ran short. A read past the end answers nought and marks the reader short, so a restore reads everything and then asks once whether what it read was all there. ### `reader` ```kest fn reader(bytes: [u8]) -> Reader no.host deterministic ``` ### `short` ```kest fn short(r: Reader) -> bool no.alloc no.host deterministic ``` Whether a read has run past the end. ### `left` ```kest fn left(r: Reader) -> i32 no.alloc no.host deterministic ``` How many bytes there are still to read. ### `take` ```kest fn take(r: Reader, many: i32) -> i32 no.alloc no.host deterministic ``` Where the next `many` bytes start, or minus one when there are not that many left, which marks the reader short and reads nothing. ### `word` ```kest fn word(from: [u8], at: i32) -> u32 no.alloc no.host deterministic ``` The four bytes at `at`, low first, as one number. ### `readU8` ```kest fn readU8(r: Reader) -> u8 no.alloc no.host deterministic ``` ### `readBool` ```kest fn readBool(r: Reader) -> bool no.alloc no.host deterministic ``` ### `readU32` ```kest fn readU32(r: Reader) -> u32 no.alloc no.host deterministic ``` ### `readI32` ```kest fn readI32(r: Reader) -> i32 no.alloc no.host deterministic ``` ### `readU64` ```kest fn readU64(r: Reader) -> u64 no.alloc no.host deterministic ``` ### `readI64` ```kest fn readI64(r: Reader) -> i64 no.alloc no.host deterministic ``` ### `readF32` ```kest fn readF32(r: Reader) -> f32 no.alloc no.host deterministic ``` ### `readF64` ```kest fn readF64(r: Reader) -> f64 no.alloc no.host deterministic ``` ### `readBytes` ```kest fn readBytes(r: Reader) -> [u8] no.host deterministic ``` ### `readI32s` ```kest fn readI32s(r: Reader) -> [i32] no.host deterministic ``` ### `readF32s` ```kest fn readF32s(r: Reader) -> [f32] no.host deterministic ``` ### `readText` ```kest fn readText(r: Reader) -> text no.host deterministic ``` Text as it was written. Bytes that are not there are read as the empty text and mark the reader short; bytes that are there and are not UTF-8 are refused where they are made into text, the way any bytes are. ## `std.fdlibm` The sine, the cosine, where two numbers point and one number to the power of another, in `f64`, which `std.math` hands its own on to in both widths. They are written in Kest rather than declared, so that they are in the deterministic profile: every step of each is an addition, a multiplication or a division, which IEEE-754 rounds the same way on every machine, and the two engines keep each one a step of its own. Declared, they were the platform's libm, which is not required to round them correctly, and two platforms could differ in the last bit and then diverge. They are fdlibm's algorithms, as musl and FreeBSD carry them, and every constant is written as the bits of the one in those sources: a reduction by quarter turns in three rounds, and a polynomial on the quarter turn. Against glibc's they are within an ulp. Past two to the twentieth quarter turns, about 1.6 million, the reduction musl hands to a longer algorithm is this one still, so a sine or a cosine that far out is the same on every machine and further from the true one than an ulp. Copyright (C) 1993, 2004 by Sun Microsystems, Inc. All rights reserved. Developed at SunPro, a Sun Microsystems, Inc. business. Permission to use, copy, modify, and distribute this software is freely granted, provided that this notice is preserved. ### `highWord` ```kest fn highWord(value: f64) -> i32 no.alloc no.host deterministic ``` How fdlibm reads a double: its high thirty-two bits with their sign, which is where the exponent and the top of the fraction are, and its low ones. ### `lowWord` ```kest fn lowWord(value: f64) -> u32 no.alloc no.host deterministic ``` ### `lowCleared` ```kest fn lowCleared(value: f64) -> f64 no.alloc no.host deterministic ``` The same double with its low thirty-two bits nought, which is how fdlibm cuts a number into a head it can multiply exactly and a tail. ### `withHighWord` ```kest fn withHighWord(value: f64, word: i32) -> f64 no.alloc no.host deterministic ``` ### `negated` ```kest fn negated(value: f64) -> f64 no.alloc no.host deterministic ``` The other sign, nought included: `0.0 - value` is nought with no sign when `value` is nought, and this is nought with one. ### `magnitude` ```kest fn magnitude(value: f64) -> f64 no.alloc no.host deterministic ``` The same number without its sign, nought included. ### `S1` ```kest const S1: f64 = float(u64(0xBFC5555555555549)) ``` ### `S2` ```kest const S2: f64 = float(u64(0x3F8111111110F8A6)) ``` ### `S3` ```kest const S3: f64 = float(u64(0xBF2A01A019C161D5)) ``` ### `S4` ```kest const S4: f64 = float(u64(0x3EC71DE357B1FE7D)) ``` ### `S5` ```kest const S5: f64 = float(u64(0xBE5AE5E68A2B9CEB)) ``` ### `S6` ```kest const S6: f64 = float(u64(0x3DE5D93A5ACFD57C)) ``` ### `C1` ```kest const C1: f64 = float(u64(0x3FA555555555554C)) ``` ### `C2` ```kest const C2: f64 = float(u64(0xBF56C16C16C15177)) ``` ### `C3` ```kest const C3: f64 = float(u64(0x3EFA01A019CB1590)) ``` ### `C4` ```kest const C4: f64 = float(u64(0xBE927E4F809C52AD)) ``` ### `C5` ```kest const C5: f64 = float(u64(0x3E21EE9EBDB4B1C4)) ``` ### `C6` ```kest const C6: f64 = float(u64(0xBDA8FAE9BE8838D4)) ``` ### `TO_INT` ```kest const TO_INT: f64 = float(u64(0x4338000000000000)) ``` ### `INV_PIO2` ```kest const INV_PIO2: f64 = float(u64(0x3FE45F306DC9C883)) ``` ### `PIO2_1` ```kest const PIO2_1: f64 = float(u64(0x3FF921FB54400000)) ``` ### `PIO2_2` ```kest const PIO2_2: f64 = float(u64(0x3DD0B4611A600000)) ``` ### `PIO2_2T` ```kest const PIO2_2T: f64 = float(u64(0x3BA3198A2E037073)) ``` ### `PIO2_3` ```kest const PIO2_3: f64 = float(u64(0x3BA3198A2E000000)) ``` ### `PIO2_3T` ```kest const PIO2_3T: f64 = float(u64(0x397B839A252049C1)) ``` ### `sinKernel` ```kest fn sinKernel(x: f64, y: f64, withTail: bool) -> f64 no.alloc no.host deterministic ``` ### `cosKernel` ```kest fn cosKernel(x: f64, y: f64) -> f64 no.alloc no.host deterministic ``` ### `Reduced` ```kest struct Reduced { head: f64 tail: f64 quarter: i32 } ``` What a number is past the nearest multiple of a quarter turn, as a head and a tail, and which of the four quarters that multiple is. ### `reduced` ```kest fn reduced(x: f64) -> Reduced no.alloc no.host deterministic ``` ### `sin` ```kest fn sin(value: f64) -> f64 no.alloc no.host deterministic ``` ### `cos` ```kest fn cos(value: f64) -> f64 no.alloc no.host deterministic ``` ### `AT0` ```kest const AT0: f64 = float(u64(0x3FD555555555550D)) ``` ### `AT1` ```kest const AT1: f64 = float(u64(0xBFC999999998EBC4)) ``` ### `AT2` ```kest const AT2: f64 = float(u64(0x3FC24924920083FF)) ``` ### `AT3` ```kest const AT3: f64 = float(u64(0xBFBC71C6FE231671)) ``` ### `AT4` ```kest const AT4: f64 = float(u64(0x3FB745CDC54C206E)) ``` ### `AT5` ```kest const AT5: f64 = float(u64(0xBFB3B0F2AF749A6D)) ``` ### `AT6` ```kest const AT6: f64 = float(u64(0x3FB10D66A0D03D51)) ``` ### `AT7` ```kest const AT7: f64 = float(u64(0xBFADDE2D52DEFD9A)) ``` ### `AT8` ```kest const AT8: f64 = float(u64(0x3FA97B4B24760DEB)) ``` ### `AT9` ```kest const AT9: f64 = float(u64(0xBFA2B4442C6A6C2F)) ``` ### `AT10` ```kest const AT10: f64 = float(u64(0x3F90AD3AE322DA11)) ``` ### `ATAN_HI0` ```kest const ATAN_HI0: f64 = float(u64(0x3FDDAC670561BB4F)) ``` ### `ATAN_HI1` ```kest const ATAN_HI1: f64 = float(u64(0x3FE921FB54442D18)) ``` ### `ATAN_HI2` ```kest const ATAN_HI2: f64 = float(u64(0x3FEF730BD281F69B)) ``` ### `ATAN_HI3` ```kest const ATAN_HI3: f64 = float(u64(0x3FF921FB54442D18)) ``` ### `ATAN_LO0` ```kest const ATAN_LO0: f64 = float(u64(0x3C7A2B7F222F65E2)) ``` ### `ATAN_LO1` ```kest const ATAN_LO1: f64 = float(u64(0x3C81A62633145C07)) ``` ### `ATAN_LO2` ```kest const ATAN_LO2: f64 = float(u64(0x3C7007887AF0CBBD)) ``` ### `ATAN_LO3` ```kest const ATAN_LO3: f64 = float(u64(0x3C91A62633145C07)) ``` ### `atan` ```kest fn atan(value: f64) -> f64 no.alloc no.host deterministic ``` ### `PI` ```kest const PI: f64 = float(u64(0x400921FB54442D18)) ``` ### `PI_LO` ```kest const PI_LO: f64 = float(u64(0x3CA1A62633145C07)) ``` ### `atan2` ```kest fn atan2(y: f64, x: f64) -> f64 no.alloc no.host deterministic ``` Where two numbers point, in radians from the positive `x` axis and between -pi and pi. A program turning towards something has a difference and wants an angle, and working that out from `sin` and `cos` is working backwards. ### `DP_H1` ```kest const DP_H1: f64 = float(u64(0x3FE2B80340000000)) ``` ### `DP_L1` ```kest const DP_L1: f64 = float(u64(0x3E4CFDEB43CFD006)) ``` ### `TWO53` ```kest const TWO53: f64 = float(u64(0x4340000000000000)) ``` ### `HUGE` ```kest const HUGE: f64 = float(u64(0x7E37E43C8800759C)) ``` ### `TINY` ```kest const TINY: f64 = float(u64(0x01A56E1FC2F8F359)) ``` ### `L1` ```kest const L1: f64 = float(u64(0x3FE3333333333303)) ``` ### `L2` ```kest const L2: f64 = float(u64(0x3FDB6DB6DB6FABFF)) ``` ### `L3` ```kest const L3: f64 = float(u64(0x3FD55555518F264D)) ``` ### `L4` ```kest const L4: f64 = float(u64(0x3FD17460A91D4101)) ``` ### `L5` ```kest const L5: f64 = float(u64(0x3FCD864A93C9DB65)) ``` ### `L6` ```kest const L6: f64 = float(u64(0x3FCA7E284A454EEF)) ``` ### `P1` ```kest const P1: f64 = float(u64(0x3FC555555555553E)) ``` ### `P2` ```kest const P2: f64 = float(u64(0xBF66C16C16BEBD93)) ``` ### `P3` ```kest const P3: f64 = float(u64(0x3F11566AAF25DE2C)) ``` ### `P4` ```kest const P4: f64 = float(u64(0xBEBBBD41C5D26BF1)) ``` ### `P5` ```kest const P5: f64 = float(u64(0x3E66376972BEA4D0)) ``` ### `LG2` ```kest const LG2: f64 = float(u64(0x3FE62E42FEFA39EF)) ``` ### `LG2_H` ```kest const LG2_H: f64 = float(u64(0x3FE62E4300000000)) ``` ### `LG2_L` ```kest const LG2_L: f64 = float(u64(0xBE205C610CA86C39)) ``` ### `OVT` ```kest const OVT: f64 = float(u64(0x3C971547652B82FE)) ``` ### `CP` ```kest const CP: f64 = float(u64(0x3FEEC709DC3A03FD)) ``` ### `CP_H` ```kest const CP_H: f64 = float(u64(0x3FEEC709E0000000)) ``` ### `CP_L` ```kest const CP_L: f64 = float(u64(0xBE3E2FE0145B01F5)) ``` ### `IVLN2` ```kest const IVLN2: f64 = float(u64(0x3FF71547652B82FE)) ``` ### `IVLN2_H` ```kest const IVLN2_H: f64 = float(u64(0x3FF7154760000000)) ``` ### `IVLN2_L` ```kest const IVLN2_L: f64 = float(u64(0x3E54AE0BF85DDF44)) ``` ### `THIRD` ```kest const THIRD: f64 = float(u64(0x3FD5555555555555)) ``` ### `pow` ```kest fn pow(x: f64, y: f64) -> f64 no.alloc no.host deterministic ``` ## `std.hash` `hash(x)` answers for one value. A program that wants one for several -- the two fields it means out of a struct, a run of them, a name and a number -- folds them together, and what it folds them with used to be whatever the reference suggested. Two programs folding the same fields differently are two answers to what reads like one question, so the fold is written once, here, and it is the fold this compiler uses for a program made of several files: FNV-1a over the eight bytes of each number. ### `start` ```kest const start: u64 = 14695981039346656037 ``` Where a fold begins. Folding into nought would make a run of noughts fold to nought and every value that starts with one look alike. ### `join` ```kest fn join(mark: u64, one: u64) -> u64 no.alloc no.host deterministic ``` One number folded into what is there so far. Low byte first, which is the order the compiler folds a file's mark in and the order another machine has to agree with. ## `std.io` Saying something is the host's to do, not the language's. A command line writes to its output; an engine writes to its console; neither is something this language should have decided for them. ### `Io.write` ```kest extern fn Io.write(value: text) no.alloc ``` Handing a piece of text over is not making one, so this promises nothing is allocated and a frame that has promised the same may write. What holds the host to it is the machine: a bound function that takes from the heap under this promise is refused where it was called. ### `write` ```kest fn write(value: text) no.alloc ``` ### `print` ```kest fn print(value: text) no.alloc ``` ## `std.math` Two functions may share a name when they take different things, so there is one `min` rather than a `minInt` and a `minFloat`. Which is meant is settled by what is passed, and nothing converts on its own, so `min(1, 2.0)` is not a question with a quiet answer. What cannot be written in Kest is declared instead. A host that a program using this module runs against has to provide these, and a program that never reaches one never asks for it. All three are exact on every machine: IEEE-754 rounds a square root correctly, and a floor and a ceiling round nothing. ### `Math.sqrt` ```kest extern fn Math.sqrt(value: f64) -> f64 no.alloc deterministic ``` ### `Math.floor` ```kest extern fn Math.floor(value: f64) -> f64 no.alloc deterministic ``` ### `Math.ceil` ```kest extern fn Math.ceil(value: f64) -> f64 no.alloc deterministic ``` ### `min` ```kest fn min(a: i32, b: i32) -> i32 no.alloc no.host deterministic ``` ### `min` ```kest fn min(a: i64, b: i64) -> i64 no.alloc no.host deterministic ``` ### `min` ```kest fn min(a: f32, b: f32) -> f32 no.alloc no.host deterministic ``` ### `min` ```kest fn min(a: f64, b: f64) -> f64 no.alloc no.host deterministic ``` ### `max` ```kest fn max(a: i32, b: i32) -> i32 no.alloc no.host deterministic ``` ### `max` ```kest fn max(a: i64, b: i64) -> i64 no.alloc no.host deterministic ``` ### `max` ```kest fn max(a: f32, b: f32) -> f32 no.alloc no.host deterministic ``` ### `max` ```kest fn max(a: f64, b: f64) -> f64 no.alloc no.host deterministic ``` ### `abs` ```kest fn abs(value: i32) -> i32 no.alloc no.host deterministic ``` The smallest `i32` is one further out than the largest, so its distance from nought is not an `i32` and `abs` of it is itself: negating it wraps, which is what arithmetic does at the end of a width. Nothing here refuses it, because a value that wraps is what its type says happens; a program that cannot have that answer holds the value away from the edge before asking. ### `abs` ```kest fn abs(value: i64) -> i64 no.alloc no.host deterministic ``` ### `abs` ```kest fn abs(value: f32) -> f32 no.alloc no.host deterministic ``` ### `abs` ```kest fn abs(value: f64) -> f64 no.alloc no.host deterministic ``` ### `clamp` ```kest fn clamp(value: i32, low: i32, high: i32) -> i32 no.alloc no.host deterministic ``` ### `clamp` ```kest fn clamp(value: i64, low: i64, high: i64) -> i64 no.alloc no.host deterministic ``` ### `clamp` ```kest fn clamp(value: f32, low: f32, high: f32) -> f32 no.alloc no.host deterministic ``` ### `clamp` ```kest fn clamp(value: f64, low: f64, high: f64) -> f64 no.alloc no.host deterministic ``` ### `isNumber` ```kest fn isNumber(value: f64) -> bool no.alloc no.host deterministic ``` Whether this is a number to go on with. A float has two answers that are not one: infinity, which is what a number too big to hold comes back as, and the value that is not a number, which is what a question with no answer comes back as -- `sqrt` of a negative is that, and so is nought divided by nought. Both come out of arithmetic without a word said, and neither can be found by comparing, because the one that is not a number is not equal to itself and infinity is equal to itself. Every number less itself is nought and neither of those is, which is the whole question and needs no constant. This language has no exponent in a literal, so the largest `f32` cannot be written down and a check against it could not be written here at all. ### `isNumber` ```kest fn isNumber(value: f32) -> bool no.alloc no.host deterministic ``` ### `sqrt` ```kest fn sqrt(value: f64) -> f64 no.alloc deterministic ``` A `f32` goes through the `f64` one and comes back, because a frame works in `f32` and widening one by hand at every call is the module not doing its half. Widening is exact and narrowing rounds, so there is one rounding here and one in the host. What that comes to depends on the function. `sqrt` is rounded exactly by every machine that has one, and `f64` carries more than twice the digits of `f32`, so the answer rounded twice is the answer rounded once: the nearest `f32` to the true one. `floor` and `ceil` are exact and `round` is built out of `floor`. `sin`, `cos` and `pow` are not promised to be rounded exactly by anybody, so what comes back is the nearest `f32` to the host's own answer, which is within a hair of the true one and is the same hair a program would get by asking in `f64` itself. ### `sqrt` ```kest fn sqrt(value: f32) -> f32 no.alloc deterministic ``` ### `floor` ```kest fn floor(value: f64) -> f64 no.alloc deterministic ``` ### `floor` ```kest fn floor(value: f32) -> f32 no.alloc deterministic ``` ### `ceil` ```kest fn ceil(value: f64) -> f64 no.alloc deterministic ``` ### `ceil` ```kest fn ceil(value: f32) -> f32 no.alloc deterministic ``` ### `sin` ```kest fn sin(value: f64) -> f64 no.alloc no.host deterministic ``` The sine, the cosine, where two numbers point and one number to the power of another are `std.fdlibm`'s, written in Kest and inside the deterministic profile, in both widths here. ### `cos` ```kest fn cos(value: f64) -> f64 no.alloc no.host deterministic ``` ### `pow` ```kest fn pow(base: f64, exponent: f64) -> f64 no.alloc no.host deterministic ``` ### `atan2` ```kest fn atan2(y: f64, x: f64) -> f64 no.alloc no.host deterministic ``` Where two numbers point, in radians from the positive `x` axis and between -pi and pi. A program turning towards something has a difference and wants an angle, and working that out from `sin` and `cos` is working backwards. ### `atan` ```kest fn atan(value: f64) -> f64 no.alloc no.host deterministic ``` The angle whose tangent is `value`, between -pi/2 and pi/2. ### `atan` ```kest fn atan(value: f32) -> f32 no.alloc no.host deterministic ``` ### `sin` ```kest fn sin(value: f32) -> f32 no.alloc no.host deterministic ``` ### `cos` ```kest fn cos(value: f32) -> f32 no.alloc no.host deterministic ``` ### `pow` ```kest fn pow(base: f32, exponent: f32) -> f32 no.alloc no.host deterministic ``` ### `atan2` ```kest fn atan2(y: f32, x: f32) -> f32 no.alloc no.host deterministic ``` ### `tan` ```kest fn tan(value: f64) -> f64 no.alloc no.host deterministic ``` A tangent is a sine over a cosine. ### `tan` ```kest fn tan(value: f32) -> f32 no.alloc no.host deterministic ``` ### `asin` ```kest fn asin(value: f64) -> f64? no.alloc deterministic ``` Nothing outside -1 to 1 has an angle, and asking for one is a question with no answer rather than a number to make up. ### `acos` ```kest fn acos(value: f64) -> f64? no.alloc deterministic ``` ### `asin` ```kest fn asin(value: f32) -> f32? no.alloc deterministic ``` And in the width a frame works in, widened and asked of the same `atan2`. What is outside -1 to 1 in one width is outside it in the other. ### `acos` ```kest fn acos(value: f32) -> f32? no.alloc deterministic ``` ### `round` ```kest fn round(value: f64) -> f64 no.alloc deterministic ``` The nearest whole number, with a half going up: `round(2.5)` is 3 and `round(-2.5)` is -2, which is what `floor(value + 0.5)` says and what a program that wanted anything else would write for itself. Written here rather than declared. Every `extern` in this module is a function every host of every program that imports it has to provide, so one more is a thing every host has to be changed for; what can be built out of what is already declared is built. ### `round` ```kest fn round(value: f32) -> f32 no.alloc deterministic ``` ### `sign` ```kest fn sign(value: i32) -> i32 no.alloc no.host deterministic ``` Written here rather than declared, because they are what the host already gives with an operator in front. ### `sign` ```kest fn sign(value: i64) -> i32 no.alloc no.host deterministic ``` A sign is one of three answers whatever width it was asked about, so this gives back the width those three fit in rather than the one it was handed. There is no `sign` for a float. Two of the values a float has are not on one side of nought or the other: what is not a number is on neither, and this shape would call it nought, which is the answer for a number that is exactly nought and is a made-up one here. A program that wants it asks `isNumber` first and then compares, which is the two questions it is really asking. ### `lerp` ```kest fn lerp(from: f32, to: f32, amount: f32) -> f32 no.alloc no.host deterministic ``` ### `lerp` ```kest fn lerp(from: f64, to: f64, amount: f64) -> f64 no.alloc no.host deterministic ``` ## `std.os` What only a host can do. Everything in here is a door the host binds, which is the whole of this language's answer to the question of who may touch a file, a clock or the words a program was started with: nobody, unless a host says so. There is no global filesystem and no ambient clock, and there is not going to be one. That is not caution, it is the same rule the rest of the language is built on. A program that promises `no.host` cannot reach any of this, the compiler proves it, and what that promise then means is exactly what a reader wants it to mean: this runs the same on every machine and touches nothing outside itself. A program that wants a file says so in its type. A host that binds none of these runs programs that do not use them and refuses the ones that do, before they run, by name. That is the capability model: the list of what a host provides is the list of what a program may do. `kest` binds all of them. Another host binds what it wants to allow. ### `Host.fileRead` ```kest extern fn Host.fileRead(path: text) -> text? ``` Reading a whole file. Nothing rather than empty text when it cannot be read, because a file that is not there and a file with nothing in it are different answers and a program that cannot tell them apart will one day have to. ### `Host.fileWrite` ```kest extern fn Host.fileWrite(path: text, bytes: text) -> bool ``` Writing one, answering whether it arrived. The bytes are text, which is what this language has: a file of anything else is a lend, and that is the host's own door rather than this one. ### `Host.fileExists` ```kest extern fn Host.fileExists(path: text) -> bool ``` And whether it is there at all, which is a question a program asks before it does something rather than after it has failed. ### `Host.argCount` ```kest extern fn Host.argCount() -> i32 no.alloc ``` How many words the program was started with, and which. The name the program was invoked by is not one of them: what a program wants is what it was asked to do, and a host that is not a command line has no such name to give. ### `Host.arg` ```kest extern fn Host.arg(at: i32) -> text? ``` ### `Host.clock` ```kest extern fn Host.clock() -> i64 no.alloc ``` A clock that measures elapsed time and only goes forwards, in microseconds, from somewhere nobody promises anything about. It is for measuring how long something took and for nothing else: two runs do not start it at the same place, and what it says is not a date. What a host binds to it is the host's. `kest` binds the platform's monotonic clock where there is one, and says so: on a platform with none it falls back to a wall clock, which can go backwards. It is not determinism and a body that promises `no.host` cannot read it. ### `read` ```kest fn read(path: text) -> text? ``` ### `write` ```kest fn write(path: text, bytes: text) -> bool ``` ### `exists` ```kest fn exists(path: text) -> bool ``` ### `argCount` ```kest fn argCount() -> i32 no.alloc ``` ### `arg` ```kest fn arg(at: i32) -> text? ``` ### `args` ```kest fn args() -> [text] ``` All of them in one array, for a program that wants to walk them rather than count them. It allocates, which is why it is not the only way to ask. ### `now` ```kest fn now() -> i64 no.alloc ``` Microseconds since the clock's own start. `now() - before` is the only thing to do with two of these. ### `millisBetween` ```kest fn millisBetween(before: i64, after: i64) -> i64 no.alloc no.host deterministic ``` And what that is in milliseconds, because a frame budget is written in them and dividing by a thousand in three places is three places to get it wrong. ## `std.random` Numbers that look random, out of a state a program holds. Nothing here is global and nothing asks the host: a simulation that wants to run twice and see the same thing has to be able to say where its numbers came from, and a generator hidden behind a name nobody passes cannot say that. The state is a value like any other, so a source is carried the way a count is: `source = random.next(source)`, and what comes back is both the next state and the next number. That is one thing to hold rather than two, and it is why `next` gives a `Source` and not a number. This is xorshift64, which is small, fast and good enough to place things with. It is not for anything that has to be unguessable. ### `Source` ```kest struct Source { state: u64 } ``` ### `from` ```kest fn from(seed: u64) -> Source no.alloc no.host deterministic ``` A source that starts where it is told. Nought is not a state this can leave, so it is turned into one that it can. ### `next` ```kest fn next(s: Source) -> Source no.alloc no.host deterministic ``` ### `number` ```kest fn number(s: Source) -> u64 no.alloc no.host deterministic ``` What it is on, as a whole number. Every bit of it is worth as much as any other, which is what lets the ones below take a part of it. ### `below` ```kest fn below(s: Source, count: i32) -> i32 no.alloc no.host deterministic ``` Below `count`, and nought when `count` is not above nought, because there is no number below one of those to give. This is a remainder, so a count that does not divide the whole range leaves the first few numbers very slightly likelier than the rest -- by about `count` in eighteen billion billion, which is not a difference anything counting them will see. Throwing away the numbers that cause it is the other way, and it makes this a loop that might go round again, which is worse in a language where a frame has a budget. ### `between` ```kest fn between(s: Source, from: i32, to: i32) -> i32 no.alloc no.host deterministic ``` Between two numbers, the first included and the second not, which is how a count is written everywhere else in this language. ### `fraction` ```kest fn fraction(s: Source) -> f32 no.alloc no.host deterministic ``` Between nought and one, as a fraction. The top bits are used because they are the ones a shift leaves alone. ### `chance` ```kest fn chance(s: Source, hundredths: i32) -> bool no.alloc no.host deterministic ``` True about that many times in a hundred. ### `one` ```kest fn one(s: Source, xs: [T]) -> T? no.alloc no.host deterministic ``` One of them, and nothing when there are none. The source is used as it stands, so a caller that wants a different one asks for the next source first, the same as everything else here. ### `shuffle` ```kest fn shuffle(s: Source, xs: [T]) -> Source no.alloc no.host deterministic ``` Every arrangement as likely as any other, in place and allocating nothing. The source that comes back is where the next call starts, because this used as many numbers as the array is long. ## `std.sort` Sorting needs to be told what comes first, and being told is a function value: `fn(T, T) -> bool no.alloc no.host`. The promise is part of the type, so a sort that promises both can call one and the compiler can still prove it . Both, because a sort that promises what it will not do has to be handed something that promises the same: what it is told to compare with is the one body it cannot read. One body, one copy per type it is called with. Gapped insertion -- Shell's, with Knuth's `3h+1` gaps -- which is in place, allocates nothing, recurses nowhere, and costs the same on any two runs of the same length and shape. Plain insertion is faster on a run that is already nearly in order and is quadratic on one that is not: sorting four thousand numbers out of order cost two hundred and sixty million instructions, which is most of a second, and costs a million now. ### `by` ```kest fn by(items: [T], before: fn(T, T) -> bool no.alloc no.host) no.alloc no.host ``` `sort.by(items, sort.ascending)`: what it is sorted by is the second thing, which is what the name says. It was `sort.sort`, because a module and its one function had a name between them, and a call read as a stammer. ### `byWith` ```kest fn byWith(items: [T], with: C, before: fn(T, T, C) -> bool no.alloc no.host) no.alloc no.host ``` And the same sort told something beside what it compares: `byWith(npcs, player, nearer)` where `nearer` reads the player's position out of what it was handed. This language has no closures and does not want any, so what a predicate would have captured is written beside it, where a reader sees it and where the promise can still be proved. Without this, sorting by a distance from a point meant building an array of pairs and sorting that, which is an allocation and a copy for what is the commonest sort a simulation does. The same walk as `by` with one more thing passed through it, written out rather than shared. `by(items, before)` could have been `byWith(items, before, callIt)` over a two-line adapter, and that is what a language with closures would do -- it costs 15 % of every `sort.by` in every program, measured, because every comparison goes through a call whose body is not known. Fourteen lines written twice is the cheaper of the two. ### `ascending` ```kest fn ascending(a: T, b: T) -> bool no.alloc no.host deterministic ``` The usual order for anything that has one. A copy per type it is asked for, checked as that type -- so `sort.by(words, sort.ascending)` works for text and for every number, and a shape with no order of its own is refused in the copy that was asked for rather than by a rule written here. ### `descending` ```kest fn descending(a: T, b: T) -> bool no.alloc no.host deterministic ``` ## `std.table` A hash table, written in Kest on a generic struct and generic functions . `hash` is the one thing the language provides, and it applies exactly where `==` does, so a copy over a key that does not compare is refused where it is made. Open addressing, linear probing. The keys and the values sit next to each other in two arrays and `slots` says where each one is: nought for empty, -1 for a key that was taken out, and otherwise one more than the position. Probing forward means a lookup reads memory in order, which is what a frame budget wants and what a chain of pointers is not. A struct is a value, so a table handed to a function is a copy of the four handles rather than of what they hold. Everything that changes is therefore behind one of them: `slots` is emptied and refilled rather than replaced, and how many pairs there are is `len(keys)` rather than a number beside it. A field written here would be written on the copy. All four are written `own`, so the handles are this module's and nothing outside can be handed one. That is what makes the invariants above hold against a program rather than merely against a careful one. The pairs are walked over `keys` and `values`, which are packed and in step: `values[i]` is what `keys[i]` is set to, and there are `count(t)` of both. The order is the order they went in, except where something was taken out and the last pair moved into the hole -- so it is an order, and not one to rely on. A table is not made smaller when things are taken out of it. Nothing here frees anything: making the slots smaller would make a new array and leave the old one where it is, so shrinking costs memory rather than giving it back. What a table has held, it keeps room for until the heap is thrown away. ### `EMPTY` ```kest const EMPTY: i32 = 0 ``` ### `TAKEN` ```kest const TAKEN: i32 = -1 ``` ### `Table` ```kest struct Table { own keys: [K] own values: [V] own slots: [i32] // How many of the slots are marks. It is an array of one rather than a // number, for the same reason everything else here is behind a handle: a // number written in a function would be written on that function's copy. own marks: [i32] } ``` What it holds, held in step: the pair at a place is `keys[i]` beside `values[i]`, and `slots` says where a key's place is. Every one of them is this module's own, because a handle handed out is a handle written through and two lines of ordinary Kest used to be enough to leave the four of them disagreeing -- `pop(t.keys)` never wrote a field, it read one and changed what it named. What reaches them from outside is what is declared below. ### `empty` ```kest fn empty() -> Table no.host deterministic ``` What a table starts as. `table.empty()` rather than `table.table()`, which is the same stammer `sort.sort` was. ### `count` ```kest fn count(t: Table) -> i32 no.alloc no.host deterministic ``` ### `keysOf` ```kest fn keysOf(t: Table) -> [K] no.host deterministic ``` The keys, copied, for a program that wants them in an order of its own. The pair at a place is `keys[i]` and `values[i]`, and a sort that moves one and not the other leaves a table that answers about a key with another key's value -- measured, and once no refusal anywhere, because a handle handed out is a handle written through. Now the arrays are this module's own and nothing outside can be handed one, so what a program sorts is this copy because it is the only thing there is to sort. Walking the pairs where they are is `keyAt` and `valueAt`, which copy nothing. ### `keyAt` ```kest fn keyAt(t: Table, at: i32) -> K no.alloc no.host deterministic ``` The pair at a place, which is where a program walks what a table holds. The places are nought up to `count(t)` and they are the order the pairs went in, except where something was taken out and the last pair moved into the hole -- so it is an order, and not one to rely on. Asking past the last of them is reading past the end of an array and says so, the way an array does. These are what `find` answers for: it gives the place a key is kept at, and nothing outside this module can read the arrays it is a place in. A program that wants the pairs walks them here rather than reaching in, because the fields are the module's own. ### `valueAt` ```kest fn valueAt(t: Table, at: i32) -> V no.alloc no.host deterministic ``` ### `slotOf` ```kest fn slotOf(t: Table, key: K) -> i32? no.alloc no.host deterministic ``` Which slot a key is kept in, or nothing. Everything that looks for a key looks here: `find` wants the pair, `remove` wants the slot, and a second probe written for the second of those would be a second place to get the walk past a mark wrong. ### `find` ```kest fn find(t: Table, key: K) -> i32? no.alloc no.host deterministic ``` Where a key is, or nothing. Reads only what is already there, so a lookup costs no allocation whatever the table holds. ### `get` ```kest fn get(t: Table, key: K) -> V? no.alloc no.host deterministic ``` What is under a key, or nothing. It answers the way the builtin `get` on a store answers, because it is the same question asked of a different thing: one name, one meaning. A `fallback: V` beside the key would make a program build a value to throw away, and make a miss read as a hit whose value happened to be that one. The default is `orElse` beside it. ### `orElse` ```kest fn orElse(t: Table, key: K, fallback: V) -> V no.alloc no.host deterministic ``` And what is under a key or this instead, which is a different question and not a second way to ask the first: one asks what is there, and this one says what to use when there is nothing. A program that means "nought when nobody has counted it" says it here rather than at every place it looks. ### `has` ```kest fn has(t: Table, key: K) -> bool no.alloc no.host deterministic ``` ### `place` ```kest fn place(t: Table, key: K, where: i32) no.alloc no.host deterministic ``` Puts a position in the first slot that will hold it, walking past whatever is already there. Nothing is compared: this is only used where the key is known to be new. ### `refill` ```kest fn refill(t: Table, howMany: i32) no.host deterministic ``` That much room, and every key put back where its hash says it goes now. The same array is emptied and refilled, because replacing it would replace the copy's handle and leave the caller's table where it was. The marks go with it: what they were for is a probe that has to carry on past a hole, and after this there are no holes to carry on past. A program that knows how many pairs are coming calls this before it puts them in, and what that saves is all of it: a pair costs 51 bytes of heap in a table that grows into them and nothing at all in one that was told, because `room` makes the slots, the keys and the values once rather than doubling any of them on the way up. Measured by `check-costs.sh`, which prints both. ### `compact` ```kest fn compact(t: Table) -> Table no.host deterministic ``` What a table has held it keeps room for: nothing here frees anything, and making the arrays smaller would make new ones and leave the old where they are. That is the right default -- a table that shrank on every removal would make a frame's cost depend on what that frame took out -- and it is wrong for a world that spikes. A hundred thousand pairs taken down to a thousand still holds 3,244,192 bytes, which is what a hundred thousand need. So this is the cold path, and it answers a new table rather than making this one smaller: a table is a value and replacing a field of it replaces the copy's handle, which is the reason everything here is behind one. The caller writes `by = table.compact(by)`, the way `source = random.next(source)` is written. What it costs is both tables at once for as long as the call takes, and the old one is gone at the next walk. ### `set` ```kest fn set(t: Table, key: K, value: V) no.host deterministic ``` Setting a key that is there writes over it, so a key appears once. A table is refilled while more than half of it is spoken for, because probing past a full one is what makes a lookup slow. A mark counts as spoken for: it is not a pair and a probe does not stop at it, so a table that has had things taken out of it can be all marks and no room while holding almost nothing. Twice the room is for the pairs; the same room again is for the marks, and which of the two is asked is which of them is crowding it. ### `fit` ```kest fn fit(t: Table, key: K, value: V) -> bool no.alloc no.host deterministic ``` `set` with the growth taken out, which is what `fit` is to `push`: it writes where the key already is, answers false where it is not, and never reaches the heap. Without it a table cannot be written to inside a promise at all -- `set` may grow, and a promise cannot be kept by hoping it does not -- so a frame keeping a count per thing had to keep it somewhere that was not a table. A program that means "this key is already here" says so here, and one that does not know calls `refill` before the frame and `set` inside it and keeps neither promise. A value that is not equal to itself is refused the way `set` refuses one, because a key that cannot be found again is a key this cannot write to either. ### `remove` ```kest fn remove(t: Table, key: K) -> bool no.alloc no.host deterministic ``` The one taken out leaves a mark rather than a hole, because a hole would end a probe that has to carry on past it. The last pair moves into its place so the two arrays stay packed. Two slots change and both are found by probing for the key that is kept in them, which is what a hash is for. Walking every slot to find two of them is the whole table for one pair, and a table is walked when it is refilled and not when something is taken out of it. ## `std.text` What every program that reads text writes for itself. Nothing here is a builtin: it is all written in the language, out of `len`, `find`, `slice`, `rest`, `matches` and the bytes. ### `number` ```kest fn number(digits: text) -> i32? no.alloc no.host deterministic ``` The number a piece of text spells, or nothing when it spells something else. Reads nothing but bytes, so it allocates nothing. ### `real` ```kest fn real(digits: text) -> f32? no.alloc no.host deterministic ``` The number with a point in it that a piece of text spells, or nothing when it spells something else. What this reads is what this language writes: `12`, `-0.5` and `3.` are numbers, and so are `1.2216752e-06`, `1e+20`, `inf`, `-inf` and `nan`, because those are what a hole in a string writes for the numbers it cannot spell plainly. A program that writes a number into text and reads it back gets the number it had; it did not, and `1e3` was refused with a rule saying a program that means that can say it another way -- which is not true of a program handed the text by this language. `.5`, `+1.5`, a space in front and a second point are still nothing, because nothing here writes those. Worked out a digit at a time in `f64` and narrowed once, which is the same two roundings every other number in this module goes through. ### `fixed` ```kest fn fixed(value: f32, places: i32) -> text no.host deterministic ``` A number written to a chosen number of places, which is what a line of a file wants: `1.5` and `1.50` are the same number and not the same line. A hole in a string writes the shortest spelling that reads back as the same number, which is the other question and the one a log asks. Places below nought or above nine are held to that, and a number too big to count in whole parts is written the way a hole would write it, because nothing after the point is worth anything at that size. A number that rounds to nothing is written without a sign in front of it: `-0.0` is a number this language has and not a thing anybody wants in a file. ### `right` ```kest fn right(subject: text, width: i32) -> text no.host deterministic ``` Pushed to the right of a column that wide, which is where a number belongs: a column of them lines up on the point when every one is written to the same places and the same width. A width is in bytes, because text is its bytes. `hız` is four of them and `hiz` is three, so two lines holding those do not line up and nothing here pretends otherwise: what a program means by a character is the program's to say. Text already that wide comes back as it is, because losing the end of something to fit a column is worse than a column that does not fit. ### `left` ```kest fn left(subject: text, width: i32) -> text no.host deterministic ``` And to the left of it, which is where a name belongs. ### `contains` ```kest fn contains(subject: text, needle: text) -> bool no.alloc no.host deterministic ``` ### `starts` ```kest fn starts(subject: text, prefix: text) -> bool no.alloc no.host deterministic ``` ### `ends` ```kest fn ends(subject: text, suffix: text) -> bool no.alloc no.host deterministic ``` ### `charBytes` ```kest fn charBytes(first: u8) -> i32 no.alloc no.host deterministic ``` How many bytes the character starting with this byte is written in, and nought when it is not the start of one. UTF-8 says it in the first byte: under 128 is one byte, and above that the number of ones at the top is the number of bytes. A byte in the middle of a character says nothing about where the character began, which is why this answers nought for one rather than guessing. ### `charWidth` ```kest fn charWidth(piece: text) -> i32 no.alloc no.host deterministic ``` How many bytes the character at that place takes, which is what its first byte says unless what follows disagrees. A character three bytes wide is three bytes only if the two after it are the middles of one: a byte that begins a character of its own ends the one before it, and a piece of text that stops sooner ends it too. So this is the width to walk by, and `charBytes` is the question about one byte on its own. ### `charBack` ```kest fn charBack(subject: text, at: i32) -> i32 no.alloc no.host deterministic ``` Where the character before this place begins, counted in bytes. Walking back is what UTF-8 is for: the middle of a character says so in every one of its bytes, so a walk back is at most three steps and needs nothing kept from the walk forwards. What it lands on has to reach where it started from -- bytes that disagree are a byte on its own, which is what walking forwards makes of them too, so the two walks agree about every place in any text at all. ### `chars` ```kest fn chars(subject: text) -> i32 no.alloc no.host deterministic ``` How many characters a piece of text holds, which is not how many bytes it holds and is what a program means when it says how long a word is. Bytes that begin no character are counted as one each, because text that is not UTF-8 is still text and a count that stops at the first of them is a count nobody can use. ### `charsOf` ```kest fn charsOf(subject: text) -> [text] no.host deterministic ``` Every character of it, in order, each as text of its own. Written as a walk with an index rather than as `charAt` in a loop: `charAt` counts from the start every time it is asked, so asking it for every character in turn is the whole of the text walked once per character. This is one walk, and it pays for one piece of text each, which is what a program that wants them all is asking for. ### `charAt` ```kest fn charAt(subject: text, index: i32) -> text? no.alloc no.host deterministic ``` The character at that place, counted in characters rather than in bytes, or nothing when there is no such place. It is text of its own, because a character is not a number here: what a byte means is a program's to say, and what a character means is Unicode's. ### `isSpace` ```kest fn isSpace(byte: u8) -> bool no.alloc no.host deterministic ``` ### `trim` ```kest fn trim(subject: text) -> text no.alloc no.host deterministic ``` Without the spaces at either end. Cuts, so it reaches the heap. ### `split` ```kest fn split(subject: text, separator: text) -> [text] no.host deterministic ``` The pieces between each separator: one more of them than there are separators, always. That is what makes this and `join` the two halves of one thing -- `join(split(s, sep), sep)` is `s` for every `s` -- and it is the rule that says what the ends are: an empty subject is one empty piece, and a subject that ends with a separator has an empty piece after it. Stopping where the text ran out instead lost the last piece whenever it was the empty one, so `split("a,b,", ",")` was two pieces and joining them back gave `a,b`. ### `bytes` ```kest fn bytes(subject: text) -> [u8] no.host deterministic ``` Text is its bytes, so a run of bytes is what it is built from. Gathering them costs nothing and `text(bytes)` pays for the copy once, which is what a loop that builds a string a piece at a time needs. ### `append` ```kest fn append(out: [u8], piece: text) no.host deterministic ``` ### `fitting` ```kest fn fitting(out: [u8], piece: text) -> bool no.alloc no.host deterministic ``` The same, into a buffer that was given room, which is what a frame writing a line every tick wants: `push` may double the block and so can never be inside a promise to reach no heap, and this cannot. It answers whether the piece fitted, and a piece that did not is a buffer that has not changed at all -- all of it goes in or none of it does, because a piece half written is a piece nobody can take back. It used to go in a byte at a time and leave what fitted, which is what a loop can do and a move cannot. ### `fittingNumber` ```kest fn fittingNumber(out: [u8], value: i32) -> bool no.alloc no.host deterministic ``` And a whole number written into one the same way, most significant digit first, without making any text on the way. It is the piece a tally line is mostly made of. ### `join` ```kest fn join(pieces: [text], separator: text) -> text no.host deterministic ``` The pieces with the separator between them, which is what `split` undoes. Measured first and given its room once, so the bytes are moved once rather than again every time the run doubles, and each piece is pushed where it is rather than through a call. ### `repeat` ```kest fn repeat(subject: text, times: i32) -> text no.host deterministic ``` ### `upper` ```kest fn upper(subject: text) -> text no.host deterministic ``` ASCII only, and deliberately: a byte is a byte, and what an upper case `ı` is depends on a language rather than on a table this could carry. ### `lower` ```kest fn lower(subject: text) -> text no.host deterministic ``` ## `std.vec` What is built on the language's `vec2`, `vec3` and `vec4`. The arithmetic is the language's -- `a + b`, `v * k` -- a component at a time; what is here is what is made of it: a dot product, a length, a distance, a direction. Every one is one of those operations after another, so it answers the same bits in the machine and in a release, and each that asks nothing of the host is `deterministic`. ### `dot` ```kest fn dot(a: vec2, b: vec2) -> f32 no.alloc no.host deterministic ``` ### `dot` ```kest fn dot(a: vec3, b: vec3) -> f32 no.alloc no.host deterministic ``` ### `dot` ```kest fn dot(a: vec4, b: vec4) -> f32 no.alloc no.host deterministic ``` ### `lengthSquared` ```kest fn lengthSquared(v: vec2) -> f32 no.alloc no.host deterministic ``` The one that costs nothing, which is the one a frame budget reaches for: comparing two of these orders the same way comparing their lengths does, without the square root. What it hands back is a square, so it runs off the end of the width where a square does -- the square of 1e20 is infinity -- and comparing works up to the size where the squares stop fitting. `length` is the one that answers for every vector this width holds an answer for. ### `lengthSquared` ```kest fn lengthSquared(v: vec3) -> f32 no.alloc no.host deterministic ``` ### `lengthSquared` ```kest fn lengthSquared(v: vec4) -> f32 no.alloc no.host deterministic ``` ### `length` ```kest fn length(v: vec2) -> f32 no.alloc deterministic ``` The square root is the host's, declared by `std.math` and provided by whatever the program runs against. Divided by its largest component first, the way `direction` is and for the same reason: the square of a vector runs off the end of an `f32` long before the vector does. The length of (1e20, 1e20) is 1.41e20, which this width holds perfectly well, and squaring first answered with infinity; at the other end the length of (1e-21, 1e-21) came back a part in five thousand out, because the squares landed among the numbers an `f32` keeps badly. A largest component that is not a number is the answer itself: the length of a vector with an infinite component is infinite, and dividing by it would make that nothing rather than everything. ### `length` ```kest fn length(v: vec3) -> f32 no.alloc deterministic ``` ### `length` ```kest fn length(v: vec4) -> f32 no.alloc deterministic ``` ### `distanceSquared` ```kest fn distanceSquared(a: vec2, b: vec2) -> f32 no.alloc no.host deterministic ``` And the one that costs nothing between two points, which is the question a frame actually asks: what is nearest, and is it inside a radius. Both of those order the same way without the square root, and `lengthSquared` was here for that reason while the two-point form of it was not. ### `distanceSquared` ```kest fn distanceSquared(a: vec3, b: vec3) -> f32 no.alloc no.host deterministic ``` ### `distanceSquared` ```kest fn distanceSquared(a: vec4, b: vec4) -> f32 no.alloc no.host deterministic ``` ### `distance` ```kest fn distance(a: vec2, b: vec2) -> f32 no.alloc deterministic ``` ### `distance` ```kest fn distance(a: vec3, b: vec3) -> f32 no.alloc deterministic ``` ### `distance` ```kest fn distance(a: vec4, b: vec4) -> f32 no.alloc deterministic ``` ### `direction` ```kest fn direction(v: vec2) -> vec2? no.alloc deterministic ``` A vector of nought length points nowhere, and there is no direction to give back. That is a question with no answer rather than a zero to return quietly, so it is an optional. Divided by its largest component before anything is squared, because squaring is where a direction gets lost: a vector of 1e20s squares to infinity and came back as (0, 0), which is not a direction and does not say so, and a vector of 1e-21s squares into what an `f32` keeps badly and came back a thousandth short of a length of one. Dividing first puts every component between -1 and 1 with one of them at 1, so what is squared is between 1 and 3 whatever it was handed. ### `direction` ```kest fn direction(v: vec3) -> vec3? no.alloc deterministic ``` ### `direction` ```kest fn direction(v: vec4) -> vec4? no.alloc deterministic ``` ### `lerp` ```kest fn lerp(a: vec2, b: vec2, amount: f32) -> vec2 no.alloc no.host deterministic ``` ### `lerp` ```kest fn lerp(a: vec3, b: vec3, amount: f32) -> vec3 no.alloc no.host deterministic ``` ### `lerp` ```kest fn lerp(a: vec4, b: vec4, amount: f32) -> vec4 no.alloc no.host deterministic ``` ### `perpendicular` ```kest fn perpendicular(v: vec2) -> vec2 no.alloc no.host deterministic ``` Perpendicular in two, and the one perpendicular to both in three. ### `cross` ```kest fn cross(a: vec3, b: vec3) -> vec3 no.alloc no.host deterministic ``` ### `cross` ```kest fn cross(a: vec2, b: vec2) -> f32 no.alloc no.host deterministic ``` A cross in two dimensions is not a vector: what is perpendicular to both is out of the plane, and the whole of it is the one number saying how far. That number is the `z` the three-dimensional one gives back, and what a program reads off it is which side of `a` the vector `b` is on -- positive one way, negative the other, and nought when they lie along each other. It is `dot` with one of them turned a quarter, which is the other thing this module gives for two dimensions and did not put together.