Goose

Goose, by example

This tutorial introduces Goose through examples. It assumes some experience with C, C++, Rust, Go, or a similar language and focuses on Goose's differences. Start here, go on to the language reference for the whole language topic by topic, consult the specification for exact rules, and see samples/ for complete programs.

Much of the syntax is familiar: braces, let, fn, struct, and match. The main difference is how arrays store and manage data. We start with where values live, since that explains many of the language's other choices.

1. The one idea

Here is an array of strings.

var words: u8[][>..] = [];
for i in 5 { words.push(str("word", i)); }

In C++ that is a vector<string>: one heap allocation for the vector, one per string, a pointer and a capacity per element, and a walk over all of them when it goes out of scope. In Rust it is a Vec<String> with the same shape.

In Goose it is one contiguous block of bytes — a length, then five back-to-back (length, characters) runs — that came into existence by bumping a pointer, and that disappears when the enclosing scope ends by moving that pointer back. No heap allocator or per-string deallocation is needed, and the block contains no pointers.

words:  05 00 00 00 | 05 w o r d 0 | 05 w o r d 1 | 05 w o r d 2 | ...

The memory model has four main properties:

This model has limitations, listed in section 18 with the rules that impose them and how to work with each, and measurable benefits: over sixteen benchmarks Goose runs at about 3.3x the speed of idiomatic C++, roughly level with hand-tuned C++ and with the best safe Rust, on 1.9x less memory than the C++ and 1.2x less than the Rust (bench/summary.md). Most of the gains come from differences in data layout and memory management.

2. Running something

Goose compiles the whole program to C and builds that with whatever C compiler is around, into an executable beside the source:

goose build hello.goose && ./hello

(goose -o hello.c hello.goose writes the C for you to build yourself, and goose build --dry-run hello.goose prints the commands. packages.md has the rest of goose build, and how a program uses libraries from other repositories.)

The bundled TinyCC backend skips the C compiler: with no verb, or with goose run, the program is compiled into the compiler's own process and run there, which is what you want while you are reading this:

goose hello.goose

Here is a minimal program:

fn main() {
    print("hello, goose");
}

print takes any number of arguments of any type, renders each as text and writes the lot as a single line (a single write, so two threads never interleave). There is no format string and no <<.

print("answer=", 42, " ratio=", 0.75, " yes=", 3 > 2);

Everything renders, not just scalars: arrays print as [1, 2, 3], structs as Point { 1, 2 }, a u8 array as its bytes. This is why the samples print so much — printing is a convenient way to inspect values.

3. Familiar syntax

let creates a binding that cannot be reassigned; var allows reassignment. Neither makes the contents read-only: use const for that. Types follow the name and can usually be inferred:

let answer = 42;
var count: i32 = 0;
let ratio = 0.75;
count += 1;
count++;              // a statement, not an expression

A struct literal names its fields or lists them in order, and may leave out those that declare a default. Ending it in .. leaves out any field: one without a declared default gets its type's own (zero, an empty array or string, null). Globals are declared like locals, and a var global given only a type starts out the same way:

struct Unit { kind: i32, hp: i32 = 100, x: f32, y: f32, name: u8[] }

let scout = Unit { kind: 2, x: 1.5, .. };   // hp 100, y 0, name ""
var selected: Unit;                         // kind 0, hp 100, x 0, y 0, name ""
var log: u8[][>..];                         // empty

Functions are free functions. There are no methods and no impl blocks, but x.f(a) is exactly f(x, a), so you can write method-call syntax wherever it reads better:

fn total(xs: i64[:]) -> i64 {
    var t = 0;
    for x in xs { t += x; }
    return t;
}

if, match, block and { } are expressions — a block's value is its trailing expression — so there is no ternary and no "declare it then assign in every branch":

let kind  = if hp > 50 { "healthy" } else { "hurt" };
let level = match hp { 0 => "dead", 1..50 => "low", _ => "fine" };

guard states what the rest of its block depends on: guard c; runs the rest of the block only where c holds, and guard c else { … } runs the else block instead, which is where a return, break or continue leaves more than the block. block gives break a target without a loop, so a chain of checks can bail out with a value:

let verdict = block {
    guard p.alive else { break "gone"; }
    guard p.hp > 0 else { break "dead"; }
    "standing"
};

Loops are for x in range_or_array, while, and loop:

for i in 3 { }              // 0, 1, 2
for i in 10..13 { }         // 10, 11, 12
for i: i32 in 0..n { }      // i is an i32; n must widen to one
for i: u8 in 0..256 { }     // every u8
for x in xs { }             // copies, for fixed-size elements
for &x in xs { x *= 2; }    // references: the mutation form
for x, i in xs { }          // with the index

Several return values are a calling convention, not a tuple type — there is no tuple type — and by custom a trailing bool says whether the rest means anything:

fn divide(a: i64, b: i64) -> i64, bool {
    if b == 0 { return 0, false; }
    return a / b, true;
}

let q, ok = divide(7, 2);

Variables (or fields, or elements) that already exist take them with =: q, ok = divide(9, 3);.

Only return and a call's results carry several values, so a branch can't end in a, b: return if c { 1, 2 } else { 3, 4 }; is an error, and each branch returns on its own, as divide does.

Trailing parameters can have defaults, which a call may leave out:

fn limit(x: i64, lo: i64 = 0, hi: i64 = 100) -> i64 {
    if x < lo { lo } else if x > hi { hi } else { x }
}

print(limit(250), " ", limit(-5, -10));   // 100 -5

A default is evaluated at each call that leaves it out. It names what a top-level declaration can — globals, constants, functions — and never the caller's variables, whatever their names.

Three arithmetic rules need particular attention:

Arithmetic happens at the operands' own width. u8 + u8 is an 8-bit add. A narrower type widens into a wider one implicitly; nothing narrows without as (range-checked in debug) or as! (never checked). u32 + i32 is a compile error asking which one you meant — the language will not silently promote both to 64 bits. The declared widths determine the operation. Integers become floats implicitly, so n * x with x: f32 is an f32 multiply; a float becomes an integer only through as. A float literal has no width of its own, and neither does an expression of float literals and integers: n * 0.5 is computed in f32 when it is passed to an f32 parameter, and is an f64 in let h = n * 0.5;. An if or match whose branches are all literals adapts as a literal does, and a literal branch takes the other branches' type: if big { x } else { 0.5 } is an f32 for an x: f32.

A cast that changes nothing is a warning, so the compiler points out the ones these rules make unnecessary: with b: u8, let w: i64 = b as i64; says redundant `as i64`: a u8 converts to i64 implicitly here. A cast that picks a type or an operation's width, as in let id = b as i32; or (a as i64) * b, is no such cast.

% is Euclidean. The result is in [0, |b|) and never negative, at every integer type. So x % n is a valid index into a length-n array for any x, and the compiler can drop the bounds check instead of demanding a guard you know is redundant.

print(-7 % 3, " ", 7 % -3);       // 2 1

Integer / truncates toward zero: -7 / 3 is -2. It does not pair with Euclidean % for negative dividends. Import std for rem(a, b), the remainder that pairs with /, and div_euclid(a, b), the quotient that pairs with %. For example, a coordinate of -1 in tiles 10 wide has tile div_euclid(-1, 10) == -1 and offset -1 % 10 == 9.

Unsigned arithmetic wraps, in every build, by definition — that is what hashes and PRNGs mean by unsigned math. Signed overflow aborts in debug and wraps in release.

4. Where values live

A Goose program has the native call stack, some static data, and N data stacks, where N is a small number the compiler works out for your program. A data stack is a multi-gigabyte address-space reservation with a bump pointer. That is the entire memory system. There is no malloc, no free list, no GC, no reference counting, no destructors.

So every dynamic value is owned by a variable, and the rules that make this work are:

  1. Values are pushed in lifetime order and popped en masse when the owning scope exits.
  2. At most one resizable value is live per stack, and it is the topmost thing on that stack for its entire lifetime. So growth is a pointer bump with no capacity check and no move, ever.

The compiler proves all of this statically. There is no runtime bookkeeping beyond the bump pointers.

"One resizable per stack" sounds alarming until you notice the plural in "N data stacks": three growable arrays alive at once simply get three stacks, and stacks are recycled the moment a scope frees one. N is whatever the deepest point of your program needs, computed once at compile time. An unused stack needs only reserved address space. You never write any of this down — there is no syntax for a stack anywhere in the language.

Scope exit is the free

for round in 3 {
    var scratch: u8[>..] = [];
    for i in 100000 { scratch.push((i % 256) as! u8); }
    print("round ", round, ": ", scratch.len, " bytes of scratch");
}

Each iteration gets a fresh 100 KB buffer, and at the closing brace the stack's top goes back to where it was. No destructor runs. No list is walked. The cost of "freeing" that buffer is one store.

Nothing moves, so references survive growth

struct Item { id: i32, weight: f32 }

var items: Item[>..] = [];
let first .= items.push(Item { 1, 0.5 });          // a reference to element 0
for i in 2..1000001 { items.push(Item { i as i32, 0.0 }); }
first.weight = 99.5;                               // still valid, a million pushes later
print(items.len, " items, first is ", items[0]);
1000000 items, first is Item { 1, 99.5 }

A vector<T> cannot promise that and a Vec<T> cannot either: both reallocate, so both invalidate. This single property is why so much Goose code holds typed references where the equivalent Rust holds u32 indices into an arena — and it is where a good share of the benchmark wins come from.

push returns a reference to the element it just made, which is the idiomatic way to link up data you are building.

Copies are visible

Fixed-size values (scalars, structs, fixed arrays, references, slices) copy silently on assignment, like C. Non-fixed values never copy implicitly, because that copy is O(size) and you should see it:

var a: i64[>..] = [1, 2, 3];
var b = copy(a);      // an explicit, visible O(n) copy
b.push(4);

Without the copy, var b = a; binds b to a by reference. Same at a call: f(xs) hands a growable array to fn f(xs: i64[:]), to fn f(xs: i64[>..]&) and to an untyped fn f(xs) alike, all by reference, without copying the elements. A function that needs its own copy uses copy.

5. The array family

There is no one "array type". There are several, and they differ in exactly one respect: what happens to the size.

Spelling What it is Metadata
T[k] fixed size, known at compile time none
T[] sized at construction, frozen after a length
T[varint] the same, with a variable-length length 1–2 bytes usually
T[..k] capacity k inline, grows and shrinks within it a small length
T[..] capacity chosen at construction length + capacity
T[>..] grow-only: the workhorse a length
T[>..<] grow-shrink: stacks, queues, heaps a length

In every one of them the representation is [metadata][elements...], inline and packed. There is never a pointer to an element block.

var fixed: i32[4] = [1, 2, 3, 4];
let zeros: f64[8] = [0.0; 8];      // fill form
let frozen: i64[] = [7, 8, 9];     // sized once, never changes

var grow: i64[>..] = [];           // arenas, builders, pools, tree storage
for i in 5 { grow.push(i * i); }

var stack: i64[>..<] = [];         // the one that pops
stack.push(1); stack.push(2); stack.push(3);
let top = stack.pop();
stack.pop_n(2);                    // drops the last two at once

var small: u8[..8] = [];           // lives inline anywhere a fixed value can
small.push('h'); small.push('i');

Which to reach for:

Only [>..] and [>..<] are "resizable", and it is those that the one-per-stack rule applies to. Everything else can go anywhere.

6. Strings are just byte arrays

There is no string type. A string is any array-family type with u8 elements, and which one you pick says what you want:

var s: u8[>..] = [];
s.append("hello");
s.push(',');
format(s, " world! ", 6 * 7);       // format appends the text of anything
print(s, " [", s.len, " bytes]");
hello, world! 42 [16 bytes]

Text that spans lines is a """ string. It is raw, with no escapes, and the indentation of its closing """ comes off every line, so it sits in the code at the code's own indentation:

print("""
    usage: wc [-l] file
      -l   count lines only
    """);
usage: wc [-l] file
  -l   count lines only

str(...) formats into a fresh string built directly at its destination:

words.push(str("word", i));         // written straight into the new element

There is no temporary string that is then copied into the array. The copy-free construction guarantee (spec §4.3) says a constructed value is always built in its final home, propagated top-down through calls, and the compiler is required not to need a fallback.

Slicing text costs nothing, because a slice is a pointer and a count into bytes that already exist:

let line = "  key = some value  ";
let body = trim(line);
let eq   = find(body, "=");
print("'", trim(body[..eq]), "' -> '", trim(body[eq + 1..]), "'");
'key' -> 'some value'

split gives you an array of slices into the input — a few bytes per part, with no text copied, where most languages hand back a list of freshly allocated strings:

let parts = split("alice,30,paris", ',');
print(parts.len, " parts: ", parts);      // 3 parts: ["alice", "30", "paris"]

words splits at runs of whitespace instead, and drops the empty parts, as a command line wants:

let cmd = words("  go   north ");
print(cmd.len, " words: ", cmd);          // 2 words: ["go", "north"]

And a struct can hold its strings inline, so an array of them is one block you can sort and copy as plain data:

struct Person { name: u8[..16], age: i32 }

// A `format` overload makes print/str/format render a Person your way.
fn format(out: u8[>..]&, p: Person) { format(out, p.name, " (", p.age, ")"); }

var people: Person[>..] = [];
people.push(Person { name: "ada", age: 36 });
people.push(Person { name: "grace", age: 45 });
var p = Person { name: "", age: 20 };
format(p.name, "linus");        // a limited array is a builder too, up to capacity
people.push(p);
print(people);
[ada (36), grace (45), linus (20)]

A value that is one string or another is a view of whichever it is: where one branch is a slice, as a literal is, a branch giving such a field gives a whole-array slice of it, with nothing copied, and the if is a const u8[:]:

let who = if people.len > 3 { "a crowd" } else { people[1].name };
print(who);                             // grace

7. Slices that cannot dangle

T[:] is a reference plus a count: C++'s span/string_view, or Rust's &[T], and lets a function process a range from any array kind without copying its elements.

fn total(xs: i64[:]) -> i64 { var t = 0; for x in xs { t += x; } return t; }

total(fixed);         // a T[k]
total(grow);          // a T[>..]
total(grow[1..4]);    // a sub-range
total(grow[^2..]);    // ^k counts from the end

Any slice-typed destination takes an array that way, not only a parameter: a variable, a field, an element or a return. The slice views the array itself, as fixed[..] would, and is const where the array is:

let view: const i64[:] = fixed;   // fixed itself, not a copy
fixed[0] = 99;
print(view[0]);                   // 99

The difference from string_view is that this one is checked. Every reference and slice carries a static root — the variable that bounds the lifetime of what it points at — and the entire lifetime system is one rule:

A reference must not outlive the variable that owns its target, and must never observe its target at a wrong type.

There are no lifetime annotations anywhere in the language. Roots are inferred, and functions are specialized per root, which gets you Rust-lifetime precision through monomorphization with zero syntax. There are also no aliasing or exclusivity rules — two references to the same thing are fine, because without shared-memory concurrency aliasing alone cannot break type safety here. The checker tracks lifetimes and valid access; it does not require references to be exclusive.

A lifetime error identifies both the reference's root and its destination:

var line: u8[>..] = [];
// ...
let w = line[..5];
print(w);
line.clear();        // fine: w's last use is behind the clear

A scratch buffer that is refilled per iteration hands out slices of itself freely. "Reusable scratch" and "structure I can point into" are the same type.

Because a slice never copies, it is also the natural key. The library's dictionary keyed by u8[:] stores no strings at all — just addresses and lengths into text you already have:

let text = "the quick brown fox jumps over the lazy dog the fox";
var counts = dictionary<const u8[:], i32> {};
each_split(text, ' ') { counts.update(it, 0) { it += 1; }; };
print(counts.count, " distinct words");

That is the whole of word-frequency counting, with nothing copied: the file is read once into one buffer, and every key, every table row and every line of the final report points into it (15_word_freq does exactly this over a book).

The const qualifier describes writability. Writability is inferred rather than annotated: a string literal is read-only, &x of a var is writable, and a slot — a field, an element, a global — has to say which kind it holds. dictionary<const u8[:], i32> says "these keys may be read-only views", which allows literals and other read-only views to be keys. Parameters are generic over constness, so you almost never write const except on a slot that must accept read-only data, and on a parameter you want to document as read-only.

8. Nested data stays inline

A struct may contain variable-size parts, and they sit inline, in declaration order. Combine that with varint fields — a LEB128 integer that takes as many bytes as its value needs — and a record becomes a run of bytes with nothing indirect in it at all:

struct Item  { sku: u8[varint], qty: varint, cents: varint }
struct Order { id: varint, customer: u8[varint], items: Item[varint] }

In most languages Order is a struct owning a String and a Vec<Item>, each Item owning another String. Here an order is its header followed by its items, laid end to end, and the whole order book is one array of those.

// "SKU:qty:cents;..." -> items, built straight into the field that gets them
fn parse_items(field: u8[:]) -> Item[>..] {
    var items: Item[>..] = [];
    each_split(field, ';') {
        let p = split(it, ':');
        let qty, ok1 = parse_int(p[1]);
        let cents, ok2 = parse_int(p[2]);
        assert(ok1 && ok2);
        items.push(Item { sku: p[0], qty: qty, cents: cents });
    };
    return items;
}

var book: Order[>..] = [];
book.push(Order { id: 1001, customer: "alice",
                  items: parse_items("SKU-441:2:1999;SKU-7:1:500") });

for o in book {
    var t = 0;
    for it in o.items { t += it.qty * it.cents; }
    print(o.customer, " owes ", t, " cents over ", o.items.len, " items");
}
alice owes 4498 cents over 2 items

It is worth counting the bytes, because this is the sort of record a real program has millions of. That order — id 1001, customer alice, two items with 5 and 7-character SKUs — is:

bytes allocations
Goose, as declared above 29 0
C++ std::string + std::vector<Item> 160 1
Rust String + Vec<Item> 153 4

The C++ and Rust figures are sizeof plus the blocks actually allocated, measured with MSVC and rustc; they do not include the allocator's own per-block header and rounding, which would add more. C++ gets off lightly here only because all three strings are short enough for the small-string optimization — one character more in a SKU and it is four allocations too.

The smaller layout reduces cache traffic when traversing the order book. And id, qty and cents cost one byte each rather than eight, because a varint is as wide as its value needs.

Note also parse_items returning a growable array by value and that costing nothing: the callee is compiled knowing its destination and writes the items directly into the order's field, inside the book. Returning a built-up value and out-parameter style are the same cost in Goose, which is why the out-parameter style mostly does not appear.

The price of variable-size elements is that the array becomes sequential: offsets are data-dependent, so you can iterate it but not index it.

for o in book { print(o); }     // fine
print(book[0]);                 // error: arrays of variable-size elements
                                // cannot be indexed, only iterated

That is a real restriction, and it is why the array family has both kinds. Use variable elements for things you walk (records, parsed nodes, log lines); use fixed elements, with a u8[..k] for the string part, for things you index and sort. When you need both, keep an index beside the compact array: a second array of references to its elements can be indexed and sorted while the elements stay packed where they are. Section 10 ends with one.

9. Enums, in two sizes

Algebraic data types are the only dynamic polymorphism in the language. No inheritance, no traits, no vtables.

enum Shape { Circle { r: f64 }, Rect { w: f64, h: f64 }, Dot }

What is unusual is that every ADT type can be stored two ways, chosen at the point of use:

Fixed mode (Shape) is what Rust's enum and C++'s variant do: a tag plus room for the largest payload, here 1 + 16 = 17 bytes for every value, Dot included. In exchange it is indexable and you may overwrite an element with a different variant.

var shapes: Shape[>..] = [];
shapes.push(Shape.Circle { r: 1.0 });
shapes.push(Shape.Rect { w: 2.0, h: 3.0 });
shapes.push(Shape.Dot);
shapes[2] = Shape.Rect { w: 1.0, h: 1.0 };      // a different variant, in place

Variable mode (Shape.. — note the trailing dots) gives each value exactly its own variant's size: a Dot is 1 byte, a Circle 9, a Rect 17. The price is that the elements are packed against each other, so the array is sequential (short of an index you keep beside it, section 10) and a value can never change variant. In exchange you may take references into a payload:

var packed: Shape..[>..] = [];
packed.push(Shape.Circle { r: 1.0 });
packed.push(Shape.Dot);
packed.push(Shape.Rect { w: 2.0, h: 3.0 });

for s in packed {
    match s {
        Rect &r => { r.w += 1.0; },     // edits the payload in place, inside the array
        _ => {},
    }
}

The two modes offer different guarantees: fixed-mode values can change variant; variable-mode values allow references into their payloads. A fixed-mode value can be overwritten with another variant, so nothing may point inside it; a variable-mode value can be pointed into, so it can never be overwritten. That is what keeps it sound, and it is why &-binders in a match are legal only on variable-mode payloads.

For a tree of mostly-small nodes the memory difference is large. It is the single biggest source of the memory column in the benchmarks: the records benchmark uses 4.0x less memory than a Rust enum whose every element is sized for its String arm, and runs 2.0–2.3x faster for the same reason — the cache does less work.

match, and match written as functions

The inline form is what you expect:

fn name(s: Shape) -> u8[:] {
    match s {
        Circle c => "circle",
        Rect r => if r.w == r.h { "square" } else { "rectangle" },
        _ => "other",
    }
}

An arm may list several variants, as in Circle, Dot => "round", and then binds no payload: each variant's payload is a type of its own.

A match on an integer takes literals, half-open ranges and named constants (let globals, ns::NAME from another namespace), so a program's own codes read as names there too; one arm may list several of them. Whether a bare name is a variant or a constant is up to the scrutinee's type:

let GROUND = 0;
let SHALLOW = 1;
let DEEP = 4;
let LAVA = 7;

fn terrain(t: i64) -> u8[:] {
    match t {
        GROUND => "ground",
        SHALLOW..DEEP => "water",
        LAVA, 10..12 => "hot",
        _ => "rock",
    }
}

The other form is case functions: one overload per variant, called with the enum. This is the virtual-call idiom, without the vtable:

fn area(s: Shape.Circle) -> f64 { 3.14159 * s.r * s.r }
fn area(s: Shape.Rect) -> f64   { s.w * s.h }
fn area(s: Shape.Dot) -> f64    { 0.0 }

for s in shapes { print(s, " area ", area(s)); }

The call dispatches on the tag through a jump table, and exhaustiveness is checked exactly as for a match — add a variant and this stops compiling until it gets its case. Variant types (Shape.Circle) are ordinary types you can name and pass around.

10. Linking things without pointers

A T& is a machine address: eight bytes, no arithmetic, no casts, never dangling. For a data structure with a lot of links, eight bytes per link is often more than you want, and an address is not something you can save to a file.

So Goose also has relative references, which are a link stored as a narrow offset:

Widths are u8, u16, u32, u64 or varint. Loading either form gives you an ordinary T&; storing one re-encodes. T&<u32>? uses offset 0 as null, so a link costs four bytes including its null.

Here is a binary search tree living in one grow-only array, with 4-byte self-relative children:

struct Node { key: i32, count: i32 = 1, left: Node&<u32>?, right: Node&<u32>? }

fn insert(pool: Node[>..]&, key: i32) {
    if pool.len == 0 { pool.push(Node { key: key }); return; }
    var cur .= pool[0];                  // .= binds the element; = would copy it
    loop {
        if key == cur.key { cur.count += 1; return; }
        if key < cur.key {
            let l = cur.left;
            if l { cur .= l; continue; }             // narrowed by `if`: l is a Node&
            cur.left .= pool.push(Node { key: key });   // the push cannot move cur
            return;
        }
        let r = cur.right;
        if r { cur .= r; continue; }
        cur.right .= pool.push(Node { key: key });
        return;
    }
}

The example uses three reference features:

.= binds and rebinds a reference. Since references are transparent — an expression that denotes a reference behaves as its target everywhere, with no * and no -> — there has to be some way to say "I mean the reference itself", and .= is it. var cur .= pool[0]; names the element; cur .= l; retargets. (.== is the matching identity test: == compares the two nodes, .== asks whether they are the same node.)

Optionals are references that can be null, narrowed by flow. Node? is a nullable Node& — address 0, no space cost. You cannot touch it until an if, while, guard or assert has narrowed it, and inside that region it simply is a Node&.

The insert is one store. cur.left .= pool.push(...) pushes the node and writes the offset, and the push cannot invalidate cur because nothing moves. In safe Rust this is where you switch to Vec<Node> plus u32 indices.

The node is 16 bytes: two i32s and two 4-byte links, where a tree of Box<Node> or unique_ptr<Node> would be 24 bytes of node plus an allocation header per node. A thousand random inserts:

442 nodes, 7072 bytes of tree, no allocator involved

self, and sentinels

A non-optional relative reference has no null, so a structure whose links point back at itself could never be constructed — there is nothing yet to point at. self, legal only as the whole initializer of such a field, means "the value this literal is constructing":

struct Node { val: i64, prev: Node&<u32 in pool>, next: Node&<u32 in pool> }

reusable var pool: Node[>..] = [];
let head = pool.alloc_index(Node { val: 0, prev: self, next: self });

That is a circular doubly-linked list's sentinel, allocated before main runs. Because the sentinel exists, no link in the whole list is ever null, every insert and remove is the same four stores with no special cases, and every link load is a plain add rather than an add plus a null test.

fn insert_after(p: Node&, v: i64) -> Node& {
    let n .= pool.alloc_ref(Node { val: v, prev: p, next: p.next });
    n.next.prev .= n;
    p.next .= n;
    return n;
}

fn remove(n: Node&) {
    n.prev.next .= n.next;
    n.next.prev .= n.prev;
    pool.free(pool.index_of(n));
}

fn is_end(n: Node&) -> bool { n .== pool[head] }

A node is 8 + 4 + 4 = 16 bytes, against a std::list node plus a map node in the C++ version of the same thing — which is most of why the lru benchmark uses 3.2x less memory.

An index for variable-size elements

Section 8 said an array of variable-size elements can be walked but not indexed: where an element starts depends on every element before it. Since other arrays can hold links into a pool, you can keep the index yourself — a second array with one 4-byte link per element, pushed alongside it:

enum Mark {
    Circle { r: f64 },
    Rect { w: f64, h: f64 },
    Label { text: u8[varint] },
    Dot,
}

var marks: Mark..[>..] = [];
var mark_at: (Mark..&<u32 in marks>)[>..] = [];

fn main() {
    mark_at.push(marks.push(Mark.Label { text: "hello, goose" }));
    mark_at.push(marks.push(Mark.Circle { r: 1.5 }));
    mark_at.push(marks.push(Mark.Dot));
    mark_at.push(marks.push(Mark.Rect { w: 2.0, h: 3.0 }));
    mark_at.push(marks.push(Mark.Label { text: "x" }));
    for i in [3, 0, 4, 1, 2] {
        match mark_at[i] {
            Circle c => print(i, ": circle ", c.r),
            Rect r => print(i, ": rect ", r.w, " by ", r.h),
            Label l => print(i, ": label \"", l.text, "\""),
            Dot => print(i, ": dot"),
        }
    }
}
3: rect 2 by 3
0: label "hello, goose"
4: label "x"
1: circle 1.5
2: dot

push builds each mark in place at the end of marks and returns a reference to it; stored in mark_at, that reference becomes the mark's offset from the base of marks. mark_at[i] is then a load and an add, in any order.

Look at what marks holds. A Label is its tag, a one-byte length and its text, all inside the element: hello, goose makes it 14 bytes, and the next mark starts where the text ends. The five marks, strings included, are 44 bytes in one block, with no pointer and no allocation anywhere. An enum in Rust or C++ has one fixed size, so a string variant holds a fixed-size string object that keeps whatever text does not fit in it somewhere else, and every element is as large as the largest variant. Here each value is exactly as long as its contents, and the index still reaches any of them for 4 bytes an element.

The array an in offset is measured from has to be a global. An array local to a function is indexed the same way with plain references, (Mark..&)[>..], at 8 bytes an entry. 05_shapes ends with this example.

11. When lifetimes really are not nested

Some data has lifetimes that do not nest: cache entries, mutable graph nodes, or files deleted in arbitrary order. Goose supports these uses with a reusable pool: a grow-only array the compiler pairs with a hidden freelist.

reusable var pool: Item[>..] = [];

let s0 = pool.alloc_index(Item { 10, 1.0 });
let s1 = pool.alloc_index(Item { 11, 1.0 });
pool.free(s0);
let s2 = pool.alloc_index(Item { 12, 2.0 });   // takes slot s0 back

alloc_index / alloc_ref take a free slot if there is one and push otherwise; free(i) records a slot for reuse. That looks like an allocator, so it is worth being precise about what free does and does not do:

All elements remain valid at all times. free does not release any memory and does not end any lifetime — it adds an index to a freelist. The slot is still a live, well-typed Item afterwards, and it still belongs to the pool, which still belongs to its owning scope.

Reuse preserves memory and type safety. A reference to a freed-and-reused slot reads a different Item — a perfectly good one, just not the one you were thinking of. That is the same class of mistake as keeping an index into an array you have since overwritten: a logic bug, and one you can reason about locally. Memory is never accessed at a type it was not written with, and nothing goes out of bounds, because nothing was freed.

Within a pool, the program manages slot reuse independently of scope. After returning a slot, stop using references to its old contents: they remain memory safe but may read a replacement value.

Running the linked list above through it:

built: 10 20 30 40 50   (6 slots)
evens removed: 10 30 50   (6 slots)
two more, both from the freelist: 10 30 50 7 8   (6 slots)

There is a second flavour, reusable[], that hands out runs of elements rather than single slots — alloc_slice(n), realloc_slice(s, n), free_slice(s) — with a freelist of spans that merges neighbours. That is what you use for the child lists of an n-ary tree, where each node's entries want to be one contiguous run you can walk as a plain slice (26_file_tree builds a whole mkdir/mv/ rm -r file tree out of the two pools together).

12. Errors, and return … from

There is no exception mechanism and no Result type, and no specified error convention either — it is the application's choice. For a call with two outcomes the trailing bool you have already seen is enough (let age, ok = parse_age(s);), and for "found or not" it is a T?, which costs nothing because it is a reference into the input. Both are ordinary return values.

The one that is not obvious is return E from f: it returns E as the result of the innermost active call of f, unwinding every frame in between. It is the language's lightweight exception, and it exists because the two idioms above scale badly — a failure eight frames deep inside a parser would otherwise mean eight signatures carrying an error they have nothing to do with.

fn load(text: u8[:]) -> User[>..], u8[] {
    var users: User[>..] = [];
    var lineno = 0;
    each_split(text, '\n') {
        lineno++;
        if it.len > 0 { users.push(parse_record(it, lineno)); }
    };
    return users, "";
}

fn parse_record(line: u8[:], lineno: i64) -> User {
    let comma = find(line, ",");
    guard comma >= 0 else { return [], str("line ", lineno, ": expected name,age") from load; }
    let age, ok = parse_age(line[comma + 1..]);
    guard ok else { return [], str("line ", lineno, ": bad age") from load; }
    return User { name: trim(line[..comma]), age: age };
}
loaded 2 users
error: line 2: expected name,age
error: line 1: bad age

Look at what parse_record does not have. Its return type is User — not Result<User, E>, not (User, bool). It has no error parameter, no ? on the calls it makes, and nothing to propagate. The same is true of every function between it and load, however many there are. All the error handling in the program is the two guards that produce a message and the one if err.len > 0 that reports it.

Three properties keep the cost low:

So the happy path pays for a flag check per frame on the way out and nothing else, which is why the parsers in the samples use this for every syntax error rather than reserving it for catastrophes (17_calc, 18_json — a bad token, a missing bracket and a bad escape are all one line each).

The exception module packages this mechanism as exception::try<E>(body) { error => ... } and exception::throw(value). It can catch owned text or application-defined error values without naming the application's outer function at each throw site. See its reference for the ownership and recursion restrictions; it does not provide finally.

The same machinery is what lets a block return from its enclosing function rather than from the HOF calling it (section 13), which is the other place you will meet it.

And the ones that stop the program rather than reporting: assert(c) for invariants, abort(msg) with a message, exit(code). The checker knows the last two never return, so a branch ending in either gives no value. That knowledge also propagates through ordinary calls, including wrappers around exception::throw: a value-returning function can end by calling one, without a dummy result afterward. Statements and a trailing expression after a proven exit are not typechecked. Unknown recursive calls are conservatively assumed to return.

13. Generics, and blocks that disappear

An untyped parameter is generic:

fn twice(x) { x + x }
fn span<T>(a: T, b: T) -> T { if a > b { a - b } else { b - a } }

<T> says that two parameters must agree, or names a type no parameter carries. Type arguments are normally inferred from the arguments, as in foo(1). An explicit list such as foo<i64>(1) can supply leading type arguments; it is required for a type variable that no argument determines:

fn zero<T>() -> T { default<T>() }   // T's default value

let half = zero<f64>() + 0.5;

Everything is monomorphized, so there is nothing abstract to typecheck: a generic body is only ever checked at an instantiation where every type is concrete, and errors come with the compile-time call chain that produced them.

Overloads resolve on argument types, and a slice parameter takes any array kind:

fn describe(x: i64) -> u8[>..]     { str("int ", x) }
fn describe(x: f64) -> u8[>..]     { str("float ", x) }
fn describe(xs: i64[:]) -> u8[>..] { str(xs.len, " ints, first ", xs[0]) }

print(describe(7), "; ", 2.5.describe(), "; ", xs.describe(), "; ", describe(xs[2..]));

Function values are compile-time entities. They are passed as generic parameters, every call is direct and inlinable, and they cannot escape — storing one, returning one or putting one in data is a compile error. There are no closures-as-objects and no runtime function pointers. A higher-order function can therefore compile to a direct loop:

fn each_pair<T, F>(xs: T[:]) {
    for i in 0..xs.len - 1 { F(xs[i], xs[i + 1]); }
}

var gaps: i64[>..] = [];
each_pair(xs) { a, b => gaps.push(b - a); };     // writes an enclosing local

{ ... } after a call is the trailing-block sugar, with it as the implicit parameter or a, b => for named ones. The standard library is written this way throughout, and filter/map build their results straight into the variable receiving them — no intermediate array, no allocation:

let evens   = xs.filter() { it % 2 == 0 };
let squares = xs.map()    { it * it };
let total   = fold(xs, 0) { acc, x => acc + x };
sort(xs) { a, b => a > b };

A block may also return from the lexically enclosing function, not from the HOF calling it — implemented with the same return from machinery — so a hand-written iterator has the same structuring power as a for loop:

fn each_step<F>(lo: i64, hi: i64, step: i64) {
    var i = lo;
    while i < hi { F(i); i += step; }
}

fn first_multiple_of_7(lo: i64, hi: i64) -> i64 {
    each_step(lo, hi, 3) { if it % 7 == 0 { return it; } };   // returns from first_multiple_of_7,
                                                              // not from each_step
    return -1;
}

Nested functions see the enclosing function's locals, which is how the parsers in the samples are written: parse's input, cursor and pools are its locals, and the recursive descent functions nested inside it use them as free variables instead of passing a state struct around (17_calc, 18_json).

One thing to know about recursion: it is opt-in and annotated. The entry of a recursive cycle is a recursive fn, every function in the cycle needs an explicit signature, and no function in a cycle may hold growable data across a call back into the cycle — every activation would need a data stack of its own. So a recursive builder takes the pool it grows as a parameter:

recursive fn in_order(n: Node&, out: i32[>..]&) {
    let l = n.left;
    if l { in_order(l, out); }
    out.push(n.key);
    let r = n.right;
    if r { in_order(r, out); }
}

A function in a cycle may still own scratch it is done with before it recurses, as long as the scratch's scope ends before the call. Here each line is built and printed in a block, so its stack is free again when the recursive calls start:

recursive fn show(n: Node&, depth: i64) {
    {
        var line: u8[>..] = [];
        for i in depth { line.append("  "); }
        line.append(str(n.key));
        print(line);
    }
    let l = n.left;
    if l { show(l, depth + 1); }
    let r = n.right;
    if r { show(r, depth + 1); }
}

That is a real constraint on how you write recursive code, and it is also most of why recursion depth costs nothing but native stack.

Several tables, one context

A compiler or a simulation keeps its state in several growable tables (nodes, symbols, output) and wants to hand them around as one thing. A struct cannot own them, since it holds at most one resizable array, as its last field, and a recursive function cannot keep them across its recursive calls. What works is to make each table a local of a driver function, and to pass the code that works on them one struct of references:

struct Node { at: i64, first: i64, next: i64 }   // a source offset, first child, next sibling

struct Ctx {                 // a slice and three references: fixed-size, cheap to pass
    source: const u8[:],
    nodes: Node[>..]&,
    text: u8[>..]&,
    scratch: i64[>..<]&,     // the recursion's working stack
}

recursive fn walk(c: Ctx&, n: i64, depth: i64) -> i64 {
    let mark = c.scratch.len;
    c.scratch.push(depth);                 // this activation's entries, above its callers'
    c.text.push(c.source[c.nodes[n].at]);
    var total = c.scratch[mark];
    var e = c.nodes[n].first;
    while e >= 0 {
        total += walk(c, e, depth + 1);
        e = c.nodes[e].next;
    }
    c.scratch.resize(mark);                // gone again before it returns
    return total;
}

fn compile(source: const u8[:]) -> i64 {
    var nodes: Node[>..] = [];
    var text: u8[>..] = [];
    var scratch: i64[>..<] = [];
    nodes.push(Node { at: 0, first: 1, next: -1 });   // a root with two children
    nodes.push(Node { at: 1, first: -1, next: 2 });
    nodes.push(Node { at: 2, first: -1, next: -1 });
    var c = Ctx { source: source, nodes: nodes, text: text, scratch: scratch };
    let r = walk(c, 0, 1);
    print(text, " ", scratch.len);
    return r;
}

compile("abc") prints abc 0 and returns 5. walk pushes into, indexes and shrinks the tables through c as it would through separate reference parameters, and they are compile's locals, owned outside the cycle and outliving every activation of walk. The grow-shrink scratch is a stack the whole recursion shares: each activation pushes above its callers' entries and truncates back to its mark before it returns.

The context lives for one call of compile. A second call, for another file in the same process, starts from fresh tables, and each call's scope exit frees its tables at once, so there is no global state to reset. Where the code that works on the tables is small enough to live inside the driver, nested functions reach them as free variables with no struct at all, as the samples' parsers do; the struct is for code spread over many functions or files.

14. Threads that share nothing

There is no shared mutable memory, at all. A worker is declared thread_fn, and the compiler compiles it and everything it calls as a separate program with its own data stacks and its own copies of the globals it uses.

Values cross between them through typed queues — one queue per type, selected by the type — and the values that may cross must be flat: no references, no slices, at any depth. Which is cheap, because a flat Goose value is contiguous, so "copy it into the queue" is a memcpy.

struct Job    { n: i32 }
struct Result { n: i32, digits: i32 }

thread_fn worker() {
    loop {
        let job = qget<Job>();           // blocks
        guard job.n >= 0 else { break; } // -1 means stop
        qput(Result { n: job.n, digits: count_digits(job.n) });
    }
}

fn main() {
    let n = max(1, hardware_threads());
    for i in 8 { qput(Job { n: (1 << (i * 3)) as i32 }); }
    for i in n { qput(Job { n: -1 }); }              // one quit job per worker
    var ids: i64[>..] = [];
    for i in n { ids.push(thread_spawn(worker)); }
    var total = 0;
    for i in 8 { let r = qget<Result>(); total += r.digits; }
    for id in ids { thread_wait(id); }
    print(n, " workers, ", total, " digits in total");
}

Because a "flat value" includes variable-size parts, a job or a result can carry real data rather than a handle to it — a struct Row { y: i32, cells: u8[] } crosses the queue as one copy, pixels included, which is exactly what 23_mandelbrot_threads does.

A worker that increments a global increments its own copy; main's is untouched. If that sounds restrictive, notice what it removes: there are no data races to have, and no locks, atomics or memory ordering anywhere in the language.

(Threads need a real C compiler — the TinyCC in-process backend cannot place thread-local storage, so compile with -o for these.)

15. Your data is already a file format

If a structure's links are self-relative offsets, it means the same thing wherever it sits in memory. So saving it is a write of its bytes, and loading it is a read. No serializer, no schema, no pointer fixups, no allocation per node.

struct Node { word: u8[..24], count: i32, left: Node&<u32>?, right: Node&<u32>? }

var index: Node[>..] = [];
// ... build the tree ...

var image: u8[>..] = index.to_bytes();      // a framed image of the array
var loaded, ok = from_bytes<Node[>..]>(image);
print("loaded ", ok, ", ", loaded.len, " nodes, 'fox' = ", lookup(loaded, "fox"));

bytes_of(a) is the same thing without the copy — a read-only view of the element region, which you can hand straight to write_file.

The interesting half is from_bytes. Bytes arriving from outside the program are the one place a reference could enter without the compiler having proved it, so from_bytes verifies before the bytes become a value: the framing, every tag, every length, and every link landing on an element start of that same image. A corrupt or hostile file is a false and an empty array, never a wild reference.

image[image.len - 3] = 200;                  // tamper with a link
var bad, bok = from_bytes<Node[>..]>(image);
print("accepted: ", bok, ", nodes ", bad.len);
loaded true, 9 nodes, 'fox' = 4
accepted: false, nodes 0

What it verifies is safety, not integrity — an image whose data bytes were edited still describes a well-formed structure, and it is a checksum, not the verifier, that tells you the file is the one you wrote. What comes back is an ordinary array: it indexes, it grows, references into it are ordinary references, and the lifetime system needs no new rule for it.

16. Calling C

An extern fn binds a Goose signature to a C symbol. The math and os modules use this foreign-function interface.

extern "cbrt" fn cube_root(x: f64) -> f64;
extern fn hypot(x: f64, y: f64) -> f64;

extern fn crc32_bytes(s: const u8[:]) -> u32;   // a slice in, a scalar out
extern fn stats_of(xs: i32[:], out: Stats&);    // a struct filled through a reference
extern fn c_version(out: u8[>..]&);             // a builder C appends to

What may cross is exactly what has a plain C shape: the scalars and bool, flat fixed-size structs and arrays (by value, or through a reference as a pointer), slices of those (as a { data, len } struct), and a u8[>..]& builder. Anything else is rejected at the declaration rather than mis-marshalled at the call. A call compiles to a direct C call with no calling-convention extras. Your own C arrives with --include header.h.

17. About the speed

Goose's performance depends on both its memory model and compiler optimization. The distinction helps when choosing data layouts and tuning loops.

Benefits of the memory model. No allocator on any path. No teardown — a scope exit is a pointer store, not a walk. Contiguous data, so the cache does less work: an array of records is one block, not one block per record. Narrow links: 2 and 4-byte offsets where a pointer would be 8. And variable-mode enums, where a tree of mostly-small nodes stops paying for its largest variant everywhere.

Where it does need the optimizer, and where you can help it. Every index is bounds-checked, and the compiler proves most of them away — but "most" is not "all", and what it fails to prove stays in the program. The idiom that works is to give the analysis a length it can use. Here is a blur kernel over row slices:

let W = 512;

// Each row of the image is a slice; the caller passes three source rows and
// one destination row per output row.
fn blur_row(above: u8[:], here: u8[:], below: u8[:], out: u8[:]) {
    assert(above.len == W && here.len == W && below.len == W && out.len == W);
    for x in 1..W - 1 {
        let sum = above[x - 1] as i64 + above[x] + above[x + 1] +
                  here[x - 1]  + here[x]  + here[x + 1] +
                  below[x - 1] + below[x] + below[x + 1];
        out[x] = (sum / 9) as! u8;
    }
}
bce: elided 11/11 index and 0/4 slice checks

One assert per row, and every index inside the pixel loop is a loop counter plus a constant against a known length, so all eleven checks go and the C backend sees the loop it would have seen from C. Without it, none of them do, and the loop does not vectorize. --bce-lines will tell you, per line, exactly which checks survived — use it when a kernel is slower than you expect.

Two language rules also help the analysis: a grow-only array can only shrink at a pop/pop_n/resize/clear the compiler can see, so a bound established before a push still holds after it; and % being Euclidean means a reduction is in range by construction.

What the numbers actually say (bench/summary.md, bench/results.md): 3.3x the speed of idiomatic C++, 1.16x hand-optimized C++, 1.05–1.11x the best safe Rust, on 1.9x/1.3x/1.2x less memory, over sixteen benchmarks. Read the losses too — they are in there, with explanations. particles is a flat float kernel where the design never predicted an advantage and there is none. calc, at 0.82x against Rust, is the one loss the summary attributes to Goose's own design rather than to a backend, and it says exactly which three things cost it. Every measurement is whole-process wall clock including teardown, which is a real cost the other languages pay and Goose does not.

18. What it costs you

You will meet all of these. Each one links to the section above that shows how to work with it, where there is one, and to the specification rule that imposes it.

19. Calling Goose from C

extern fn goes the other way: export fn makes a Goose function callable from C, so a Goose module can be linked into a C or C++ program as a library.

var calls: i32 = 0;

export fn hello_world() -> const u8[:] {
    calls += 1;
    return "Hello, world!"
}

export "c_add" fn add(a: i32, b: i32) -> i32 { a + b }

fn main() {
    calls = 100;    // runs once, inside goose_init
}

An export fn is an ordinary Goose function; the compiler adds a C wrapper for it. The optional string picks the C symbol, and otherwise the Goose name is used. Ask for a header and the compiler builds the C for a C host, with no main of its own:

goose --standalone --header hello.h -o hello.c hello.goose
cc hello.c app.c -o app
#include "hello.h"
#include <stdio.h>

int main(int argc, char **argv) {
    int64_t length;
    goose_init(argc, argv);
    const uint8_t *message = hello_world(&length);
    fwrite(message, 1, (size_t)length, stdout);   // not NUL-terminated
    putchar('\n');
    printf("%d\n", c_add(20, 22));
    return 0;
}

The host calls goose_init once before anything else. It sets up the runtime and the globals and then runs your Goose fn main(), so main is the place for a library's own start-up code. A library with nothing to start up may leave main out. A const u8[:] result comes back as a pointer plus an extra int64_t * parameter that receives its length; scalars and flat fixed-size values are returned by value. The generated functions are not thread-safe: call them from the thread that called goose_init. The signatures that may cross are the ones from section 16, with a few more limits; see spec §7.11.

20. Where to go next

One last piece of advice: when the checker rejects something, read the whole error. It names both ends — the reference and where it was bound, the holder and the line that stored into it, the instantiation and the call chain that produced it. Use those locations to decide which binding, store, or scope needs to change.