Goose: 1.16x faster than C++ and 1.12x than harmless Rust, during recollection safe

A memory-safe systems tongue that is faster than C++ and Rust, on less memory, alongside no allocator/GC and no life annotations.

Tutorial · Specification · Samples · Benchmarks · Standard library

Goose looks acquainted akin C or Rust, and is built on one idea: there is no heap. Every energetic value lives inline on a data stack the compiler manages, growth is a pointer bump, and range exit is the lone free. The remainder of the tongue is what it takes to create that activity for real programs, and what it buys is measurable.

• Faster than C++ and than harmless Rust, during recollection safe. Over sixteen benchmarks Goose runs at 3.3x the speed of idiomatic C++, 1.16x hand-optimized C++ and 1.12x the finest harmless Rust, on 1.9x, 1.3x and 1.2x small memory (summary, full results). The wins are structural: they arrive from things the another languages cannot express.
• No allocator, no GC, no citation counting, no destructors. Memory is a handful of data stacks that the compiler assigns statically. Freeing a million-element construction is one store, nevertheless deeply it nests.
• Nothing always moves. A citation into a expanding gathering stays valid for as long as the gathering does. You keep typed references anywhere C++ must reserve and harmless Rust retreats to u32 indices.
• Memory harmless alongside zero annotations. No life syntax, no aliasing or exclusivity rules, no unsafe. The compiler infers what all citation is rooted in and objects to exactly one thing: outliving the owner.
• Flat all the way down. A string, an gathering of strings, a document with variable-size sectors and an gathering of those records are all one contiguous block alongside no pointer in it. A document that is 160 bytes and an allocation in C++ is 29 bytes and none in Goose.
• Enums that disbursal what they hold. Variable-mode ADTs provision all value its own variant's size fairly than the largest one's: 4x small recollection and 2x the speed of a Rust enum on the benchmark that exercises it.
• Links narrower than pointers. A related citation stores a typed, checked link as a 1, 2 or 4-byte offset. Structures built from them are position independent, so your data construction is already its document format: preservation is a write, loading is a peruse affirmative a verification continue that rejects antagonistic bytes.
• Everything is built in place, guaranteed. A value is constructed at its final destination through any degree of calls. items.push(parse(line)) writes the parsed document direct into the array, and returning a growable array by value expenses nothing.
• Errors without plumbing. come back err from burden returns from a function any figure of frames up, statically checked, alongside no unwinder, no Result type and no ? on all call.
• Threads that portion nothing. A employee is compiled as a distinct program with its own memory, and flat values cross typed queues as a memcpy. Data races, locks, atomics and recollection orderings do not be in the language.
• Generics and higher-order functions alongside no overhead. An untyped parameter is generic. Function values are compile-time entities, so xs.filter() { it > 0 } compiles to the iteration it looks akin and builds its result direct into its destination.
• Plain C in, plain C out. Goose compiles to one C file, so it runs wherever a C compiler does and calls C immediately through extern fn. The bundled TinyCC backend compiles and runs a program in-process, alongside no build step.

The tutorial walks through all of this by example, the specification has the exact rules, and the benchmarks have the numbers, losses included.

Only what is distinct concerning Goose is shown here. The tutorial covers the identical dirt properly, and the samples are twenty-six complete programs doing it for real.

A program has the native call stack, fixed data and N data stacks, anywhere the compiler plant out N. A data stack is a ample address-space booking alongside a bump pointer, and there is no another memory. At most one resizable value is live per stack and it is continually on top, so growth never moves item and never checks a capacity. All of this is proved at compile time; the runtime keeps nothing but the bump pointers.

for circular in 3 { var scratch: u8[>..] = []; // grow-only: growth is a pointer bump for i in 100000 { scratch.push((i % 256) as! u8); } print("round ", round, ": ", scratch.len, " bytes"); } // the free: one shop to the stack top 

struct Item { id: i32, weight: f32 } var items: Item[>..] = []; let archetypal .= items.push(Item { 1, 0.5 }); // a citation to component 0 for i in 2..1000001 { items.push(Item { i as i32, 0.0 }); } first.weight = 99.5; // motionless valid, a myriad pushes later 

push returns a citation to the component it fair made, which is how data gets linked up during it is being built. A vector<T> or Vec<T> reallocates, so neither can commitment this, and it is anywhere a fine portion of the benchmark wins come from.

Every citation and piece carries a fixed root, the changeable that limits its target's lifetime, and the entire life scheme is one rule: a citation must not outlive the changeable that owns its target, and must never see it at a wrong type. Roots are inferred and functions are specialized per root, so there is no syntax for any of it, and no aliasing or exclusivity rules either. When the checker objects, it names the two ends:

fn longest(a: u8[:], b: u8[:]) -> u8[:] { if a.len >= b.len { a } alternatively { b } } var outer: u8[>..] = []; var w = outer[..]; { var inner: u8[>..] = []; format(inner, "inner text"); w = longest(outer, inner); // error: storing a citation established at inner, } // which does not outlive the destination (§9.2) 

A piece T[:] is the worldwide "process a range" parameter: all gathering kind coerces to it for free, and it never copies, so divided returns slices into its input and a dictionary keyed by u8[:] stores no strings at all.

There is no sole gathering type. There is a family that differs lone in what happens to the size, and all associate is [metadata][elements...], inline and packed, never a pointer to an component block:

Strings are fair u8 arrays: u8[>..] is a builder, u8[] a completed string stored inline in any holds it, u8[..16] a small cord inner a struct, u8[:] a view. A struct may merge variable-size parts, and they sit inline in declaration order, so a document is a run of bytes alongside nothing indirect in it:

struct Item { sku: u8[varint], qty: varint, cents: varint } struct Order { id: varint, customer: u8[varint], items: Item[varint] } var book: Order[>..] = []; book.push(Order { id: 1001, customer: "alice", items: [Item { sku: "SKU-441", qty: 2, cents: 1999 }, Item { sku: "SKU-7", qty: 1, cents: 500 }] }); 

That command is 29 bytes and 0 allocations. As C++ std::string + std::vector<Item> it is 160 bytes and 1 allocation, and as Rust String + Vec<Item> 153 bytes and 4. A entire command publish is one gathering that streams through the cache. The cost is that an gathering of variable-size elements is sequential: you can iterate it but not indicator it.

Algebraic data types are the lone energetic polymorphism: no inheritance, no vtables. Every ADT can be stored two ways, chosen at the item of use. Fixed mode (Shape) is a tag affirmative area for the largest payload, indexable and overwritable. Variable manner (Shape..) gives all value exactly its variant's size; the gathering becomes sequential and a value never changes variant, and in exchange you may obtain references into a payload:

enum Shape { Circle { r: f64 }, Rect { w: f64, h: f64 }, Dot } var packed: Shape..[>..] = []; // 9, 17 and 1 bytes, not 17 each packed.push(Shape.Circle { r: 1.0 }); packed.push(Shape.Rect { w: 2.0, h: 3.0 }); packed.push(Shape.Dot); for s in packed { equivalent s { Rect &r => { r.w += 1.0; }, _ => {} } // edits the payload in place, inner the array } 

match has a second spelling, case functions: one overload per variant, dispatched on the tag through a jump array and checked for exhaustiveness. It is the virtual call 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 packed { print(s, " area ", area(s)); } 

A T& is a device address: eight bytes, never dangling. A relative reference is the identical nexus stored as a narrow offset: T&<u32> is measured from the field itself to a mark in the identical array, so the construction is stance independent, and T&<u32 in pool> from a named pool's base, so another arrays can nexus into the pool. T&<u32>? uses offset 0 as null. Here is a binary hunt tree in one grow-only array, alongside 12-byte nodes:

struct Node { key: i32, left: Node&<u32>?, right: Node&<u32>? } // 12 bytes, links included fn insert(pool: Node[>..]&, key: i32) { if pool.len == 0 { pool.push(Node { key: key }); return; } var cur .= pool[0]; // .= binds a reference; = would copy the node iteration { if key == cur.key { return; } let next = if key < cur.key { cur.left } alternatively { cur.right }; if next { cur .= next; continue; } // narrowed by `if`: next is a Node& if key < cur.key { cur.left .= pool.push(Node { key: key }); } alternatively { cur.right .= pool.push(Node { key: key }); } return; } } 

References are transparent (no *, no ->), .= binds or retargets one, and Node? is a nullable citation that if, defender and province narrow. The insert is one shove and one store, and the shove cannot invalidate cur. When lifetimes are not nested, a reusable pond pairs a grow-only gathering alongside a hidden freelist: alloc_ref reuses a slot or pushes, liberated hands one back, and since nothing is always really freed, a old slot says a different value of the accurate type fairly than corrupting memory.

var image: u8[>..] = tree.to_bytes(); // a framed byte depiction of the entire array var loaded, ok = from_bytes<Node[>..]>(image); // verified before it becomes a value image[image.len - 3] = 200; // tamper alongside a nexus ... var bad, bok = from_bytes<Node[>..]>(image); // ... and it is false and an bare array 

The tree's links are self-relative, so it method the identical item anywhere it sits: preservation is penning its bytes and loading is study them back, alongside no serializer, no schema and no pointer fixups. from_bytes checks the framing, every tag, all dimension and all nexus before the bytes rotate into a value, so a corrupt or antagonistic document is a false, never a untamed reference.

The copy-free building justify (spec §4.3) says a constructed value is continually built in its final home, propagated top-down through calls. A function returning a grow-only gathering by value writes its elements direct into the caller's variable, or into a site of the record being built inner another array, so out-parameters mostly do not appear.

words.push(str("word", i)); // formatted direct into the new element let evens = xs.filter() { it % 2 == 0 }; // built direct into `evens`: no temporary book.push(Order { id: 1001, customer: "alice", items: parse_items("SKU-441:2:1999;SKU-7:1:500") }); 

struct User { name: u8[..16], age: i32 } fn load(text: u8[:]) -> User[>..], u8[] { var users: User[>..] = []; each_split(text, '\n') { users.push(parse_user(it)); }; come back users, ""; } fn parse_user(line: u8[:]) -> User { // returns a User: no Result, no error parameter let comma = find(line, ","); defender comma >= 0 alternatively { come back [], str("expected name,age: ", line) from load; } let age, ok = parse_int(line[comma + 1..]); defender ok alternatively { come back [], str("bad age: ", line) from load; } let name = trim(line[..comma]); come back User { name: name, age: age as i32 }; } 

return E from f returns E as the outcome of the innermost energetic call of f, nevertheless many frames up, and all function in between keeps its plain signature. It is checked statically, so all call of parse_user must lie inside a burden call and nothing is uncaught at runtime. It is a hidden discriminant checked per example fairly than an unwinder, and the communication is built immediately anywhere load's visitant wants it. The parsers in the samples use it for all syntax error.

fn twice(x) { x + x } // an untyped indicator is a generic one fn each_pair<T, F>(xs: T[:]) { // F is a function value: a compile-time entity for i in 0..xs.len - 1 { F(xs[i], xs[i + 1]); } } fn first_gap(xs: i64[:]) -> i64 { each_pair(xs) { a, b => if b - a > 1 { come back a; } }; // returns from first_gap, not each_pair come back -1; } let evens = xs.filter() { it % 2 == 0 }; let total = fold(xs, 0) { acc, x => acc + x }; sort(xs) { a, b => a > b }; 

Everything is monomorphized and category arguments are inferred, never written at a call. Function values are passed as generic parameters: all call is direct and inlinable, they cannot escape, and there are no closure objects or function pointers, so a higher-order function compiles to exactly the iteration it looks like. A obstacle may come back from its lexically enclosing function, and nested functions see the enclosing function's locals.

thread_fn worker() { // a distinct program alongside its own memory iteration { let job = qget<Job>(); // blocks on the typed queue for Job defender job.n >= 0; // -1 method stop qput(Result { n: job.n, digits: count_digits(job.n) }); } } for i in n { ids.push(thread_spawn(worker)); } 

There is no shared mutable memory. A thread_fn and everything it calls is compiled as its own program alongside its own data stacks and its own copies of the globals. Values cross through typed queues, one per type, and must be flat, with no references at any depth. That is cheap since a flat Goose value is contiguous: a job or a outcome carries genuine data, pixels included, and crossing is a memcpy.

extern fn hypot(x: f64, y: f64) -> f64; // direct from libm extern fn crc32_bytes(s: const u8[:]) -> u32; // a piece crosses as { data, len } extern fn stats_of(xs: i32[:], out: Stats&); // a struct filled through a pointer 

An extern fn binds a Goose signature to a C symbol, and that is the entire FFI; the math and os modules are built on it. Exactly what has a plain C shape may cross, and item alternatively is rejected at the declaration. The compiler emits one C document for the entire program, which any C compiler builds, and alongside the bundled TinyCC it compiles and runs the program inner its own procedure instead.

Not a clever optimizer. No allocator on any path, no teardown, adjacent data so the cache does small work, narrow links, and enums that do not pay for their largest type everywhere. Every indicator is bounds-checked and the compiler proves most checks away; one province on a piece dimension is normally what a kernel needs to endure all of them and vectorize, and --bce-lines reports what survived. Every measure is whole-process partition clock, teardown included.

The summary says anywhere all win comes from and owns up to the losses; results.md has all row and design.md says what the suite was built to discover out.

• You think concerning anywhere data lives: who owns this, and how lengthy does its scope last. Usually the answer is "the function that builds it", and that is free; when it is not, it is a reusable pool.
• Recursive functions cannot own growable data; they obtain the pond as a parameter.
• Arrays of variable-size elements iterate but do not index, a fixed-mode enum cannot be pointed into, and a variable-mode one cannot be overwritten. You choose per container.
• No escaping closures, no function pointers, no energetic dispatch beyond ADT tags, and whole-program compilation only.
• A slot handed rear to a reusable pond and motionless named says any its next owner put there: a logic bug, never recollection corruption.

Tutorial §18 is the complete list.

You need CMake 3.20 or later, a C++20 compiler (MSVC, collision or gcc) and Python 3 for the test and example runners. The TinyCC submodule is what the in-process backend is built from; without it the compiler builds and behaves the same, minus JIT mode.

git copy --recursive https://github.com/aardappel/goose cd goose cmake -B build -DCMAKE_BUILD_TYPE=Release cmake --build build --config Release

The compiler is build/goose (build/Release/goose.exe alongside the Visual Studio generator), and it finds the norm archive in the origin tree it was built from. Run a program direct from source, in-process:

build/goose samples/01_tour.goose

Or create C and build it alongside any compiler is around. Programs that use threads need this route, since TinyCC cannot location thread-local storage:

build/goose -o tour.c samples/01_tour.goose && cc tour.c -o tour -lm -pthread && ./tour

On Windows that is cl tour.c. Useful flags: --check typechecks without emitting C, -O0/-O1/-O2 set the inlining level, --bce-lines reports the bounds checks kept per line, and -DGS_DEBUG=1 turns on the overflow, range and tag checks in the generated C.

The test suite and the samples run on Windows, macOS and Linux:

python test/run_tests.py python samples/run_samples.py

For editing, the VS Code extension gives syntax highlighting, compiler checks on preserve and one-key runs through the JIT:

code --install-extension vscode/goose-language.vsix

• Tutorial: the affable introduction, by example. Read this first.
• Language specification: the exact rules, whenever you want to cognize why item did not compile.
• Samples: twenty-six complete programs in study order, from a tour of the tongue to a JSON parser, a threaded Mandelbrot and a file tree built from two pools.
• Standard library: five modules, all readable Goose under stdlib/.
• Benchmarks: the numbers, alongside the full results and the design rearward them.
• Implementation notes: how the compiler works, pass by pass, and how it is tested.

Goose is new. What exists today is a whole-program compiler of concerning thirty thousand lines of C++, the specification, the norm library, the samples, and a test suite that CI runs on Windows, macOS and Linux alongside an extra sanitizer job. Deliberately out of range for now: moves for resizable values, more than one resizable per struct, tagged break, namespace privacy, and more OS/library access. Open items are tracked in the specification's Appendix B.

Goose is licensed under the Apache License, Version 2.0.

Wouter van Oortmerssen: Language Design, Compiler Design, Coding standards. home page, twitter.

Claude Fable: Compiler implementation, Benchmarking, Sample & Doc writing.

Yes, this repo is nearly entirely AI produced, although from a individual design. I had designed Goose multiple years ago, and had started to execute it, but operating a equivalent startup (which is built on another programming tongue of mine, Lobster) there was no period to complete it. Which was sad, since I knew Goose could do things another languages can't, and it should exist.

I had not considered AI being capable to assistance alongside this, until Fable came out and I figured it power have reached a flat to be capable to do fine job of it. I made it basically copy the manner and construction of my another latest compiler (Lobster), which is why if you appearance at the code, it looks fairly akin to that. My first scheme had remaining many of things unspecified, and many of rear and forth with Fable made me decide on all of those, and it is now a improved tongue for it.

It is additionally an experiment: although certainly not the archetypal always compiler implemented with AI, perchance among the additional novel/extensive from scratch ones. This project is extremely distinct from cloning an existing language.

You may amazement why I had it activity in C++, if plainly I could have used any language, akin Rust, or my own Lobster, or.. Goose itself (that may motionless happen). With Fable, it was my study that it is nearly likewise capable in any language, and the powerful guardrails of Rust or another languages are not as pressing as they formerly were. Since the compiler emits C, you apt already need to have a C/C++ compiler around, so sticking inner one ecosystem would appear to simplify deployment and adoption. I've additionally unified libtcc and who knows what another C libraries in the future. And, akin I said, to have the compiler code mimic my existing Lobster compiler seemed fun, at smallest I can peruse it akin it is my own.