Many things have changed in software development since I wrote this series. Back then, LLMs could barely write Python, now they can write tolerable code in most languages, which is especially helpful if you're forced to use something miserable like Rust or Java.
But new programming languages are still being created. And shouldn't it be easier than ever to create your own language now? Just do the design, and ask Claude or Codex to do all the tedious parts like parser and LSP server, and you can have a working prototype much faster than in the olden days. It's not going to be great software, but most hobby languages were prototype quality anyway.
Here's a bonus episode about one new weird language I stumbled upon - Goose. The main feature of Goose is that it doesn't use any memory management - no malloc, no garbage collector, no borrow checker, everything is on a few stacks.
And yes, Goose repo says "This repo was produced almost entirely with AI, from a human language design". It's one of early post-AI languages.
But everything in this post was still human-written. I only used AI for some extra unit tests (not included here), and it struggled with Goose.
FizzBuzz
Let's start with the FizzBuzz:
fn main() {
for i in 1..101 {
if i % 15 == 0 {
print("FizzBuzz");
} else if i % 3 == 0 {
print("Fizz");
} else if i % 5 == 0 {
print("Buzz");
} else {
print(i);
}
}
}
This is pretty decent. Looping uses Python style n+1 convention, but it's all very readable.
Fibonacci
Now let's write a program to print Fibonacci sequence.
import os;
fn main() {
let argv = args();
if argv.len != 2 {
write_stderr("Usage: fib <number>\n");
exit(1);
}
let count = parse_int(argv[1]);
var a = 1;
var b = 1;
for i in 1..count+1 {
print("fib(", i, ")=", a);
var c = a + b;
a = b;
b = c;
}
}
Package os provides args() function. argv works C style, so there's extra argv[0] argument with program name. There's mildly annoying assymetry between print which automatically prints newline and write_stderr which doesn't.
$ goose build fib.goose
parsed ok: 160 top-level declarations, 3 file(s)
typechecked ok: 88 specialization(s), 2 struct/0 enum instance(s); optimized -O2: 1 inlined, 0 base case(s), 3 folded, 2 propagated, 0 tail loop(s), 0 reassociated
bce: elided 5/5 index and 0/1 slice checks
wrote /Users/taw/.goose/build/prog/fib-ccfeaa33/fib.c (68148 bytes)
built fib
$ ./fib
Usage: fib <number>
$ ./fib 10
fib(1)=1
fib(2)=1
fib(3)=2
fib(4)=3
fib(5)=5
fib(6)=8
fib(7)=13
fib(8)=21
fib(9)=34
fib(10)=55
goose compiler is annoyingly verbose, but it all works. But what if we tried something bigger:
$ ./fib 1000 | tail
fib(991)=5473427266748952413
fib(992)=3154021370846500485
fib(993)=8627448637595452898
fib(994)=-6665274065267598233
fib(995)=1962174572327854665
fib(996)=-4703099492939743568
fib(997)=-2740924920611888903
fib(998)=-7444024413551632471
fib(999)=8261794739546030242
fib(1000)=817770325994397771
Well, that's just 64 bit overflow. But that won't do, let's write our own BigInt library.
Unit Testing library
Halfway through writing BigInt library I noticed that goose doesn't have any unit testing library.
There's some vibe coded Python test runner that apparently parses comments to figure out expectations like this:
print(floor(2.7), " ", ceil(2.1), " ", round(2.5), " ", trunc(-2.7)); // 2.0 3.0 3.0 -2.0
I decided to write a very simple one like this:
struct TestRunner {
assertions : u64,
failed : u64,
current_test : u8[>..]
}
let test_runner = TestRunner{
assertions: 0,
failed: 0,
current_test: ""
};
fn start_test(name : u8[:]) {
test_runner.current_test = name;
}
fn assert_equal<T>(actual : T, expected : T) {
test_runner.assertions += 1;
if (expected != actual) {
test_runner.failed += 1;
print("current_test: ", test_runner.current_test, " expected: ", expected, ", actual: ", actual);
}
}
fn report_test_results() {
if test_runner.failed == 0 {
print("test result: ok. ", test_runner.assertions, " assertions")
} else {
print("test result: failed. ", test_runner.assertions, " assertions, ", test_runner.failed, " failed")
}
}
And now we can actually start writing our BigInt library with proper TDD:
import unittest;
import bigint;
fn test_bigint_zero() {
start_test("bigint_zero");
let a = bigint_zero();
assert_equal(a.negative, false);
assert_equal(a.limbs.len, 0);
}
fn test_bigint_new() {
start_test("bigint_new");
let a = bigint_new(0);
assert_equal(a.negative, false);
assert_equal(a.limbs.len, 0);
let b = bigint_new(1234);
assert_equal(b.negative, false);
assert_equal(b.limbs.len, 1);
assert_equal(b.limbs[0], 1234);
let c = bigint_new(-9223372036854775808); // min_int
assert_equal(c.negative, true);
assert_equal(c.limbs.len, 2);
assert_equal(c.limbs[0], 0);
assert_equal(c.limbs[1], 0x80000000);
}
fn main() {
test_bigint_zero();
test_bigint_new();
// and so on
report_test_results()
}
$ goose build bigint_test.goose >/dev/null && ./bigint_test
test result: ok. 11 assertions
Passing variable width arguments
With unit testing out of the way, it was time to implement bigint library. There are some exotic ways, but just a boolean sign and array of "limbs" (I don't know why bigint people call it that), lowest first, seem like a sensible choice.
// Always return normalized forms, so no negative 0, no limbs: [1, 0], or any other such nonsense
struct BigInt {
negative: bool,
limbs: u32[]
}
Unfortunately we're running into a problem right away. Let's say we have some variable declared somewhere like let a = bigint_new(60). We really want to be able to do something like:
let b = bigint_add(a, bigint_new(9));
And other math expressions on our BigInts. But Goose would only allow that for fixed width types, which BigInt decidedly is not.
We can pass by value (fn bigint_add(a: BigInt, b: BigInt) -> BigInt), but it would require copy() everywhere:
let b = bigint_add(copy(a), bigint_new(9));
Or we can pass by reference (fn bigint_add1(a: BigInt&, b: BigInt&) -> BigInt), but then we're forced to save every intermediate value:
let t = bigint_new(9);
let b = bigint_add(a, t);
I can see why it was done this way, but ergonomics of this are just awful either way. I decided to use reference form.
BigInt library
I only implemented parts that are required for properly working Fibonacci. Turning it into a proper BigInt implementation isn't too hard, but this is going to be a lot of code regardless.
Our BigInt is very simple:
// Always return normalized forms, so no negative 0, no limbs: [1, 0], or any other such nonsense
struct BigInt {
negative: bool,
limbs: u32[]
}
It can be constructed as zero, from i64, or from string. I'll leave the last one for later.
fn bigint_zero() -> BigInt {
return BigInt{negative: false, limbs: []};
}
fn bigint_new(arg: i64) -> BigInt {
let is_negative = arg < 0;
var magnitude : u64;
if arg < 0 {
// docs say it's all guaranteed two's complement, so MIN_INT is fine here
magnitude = (-arg) as u64;
} else {
magnitude = arg as u64;
}
let lo : u32 = (magnitude & 0xFFFFFFFF) as u32;
let hi : u32 = (magnitude >> 32) as u32;
if hi != 0 {
return BigInt{negative: is_negative, limbs: [lo, hi]};
}
if lo != 0 {
return BigInt{negative: is_negative, limbs: [lo]};
}
return BigInt{negative: is_negative, limbs: []};
}
The big idea is that result of u32+u32 or u32*u32 fits in u64, so we can cast u32 to u64, do calculations, chop the results, and store back the results. Casting to wider type is lossless so doesn't require any annotations. Casting to narrower type is potentially lossy so it requires explicit as type cast. All of it is perfectly sensible.
Now comparisons and some common simple functions like abs, neg, and is_zero:
fn bigint_abs(a: BigInt&) -> BigInt {
return BigInt{ negative: false, limbs: copy(a.limbs) };
}
fn bigint_is_zero(a: BigInt&) -> bool {
return a.limbs.len == 0;
}
fn bigint_neg(a: BigInt&) -> BigInt {
if bigint_is_zero(a) {
return bigint_zero();
} else {
return BigInt{ negative: !a.negative, limbs: copy(a.limbs) };
}
}
fn bigint_eq(a: BigInt&, b: BigInt&) -> bool {
return a == b;
}
fn bigint_ne(a: BigInt&, b: BigInt&) -> bool {
return a != b;
}
fn bigint_gt(a: BigInt&, b: BigInt&) -> bool {
if a.negative {
if b.negative {
// a > b
// -b > -a
return bigint_magnitude_gt(b.limbs, a.limbs)
} else {
return false
}
} else {
if b.negative {
return true
} else {
// a > b
return bigint_magnitude_gt(a.limbs, b.limbs)
}
}
}
fn bigint_ge(a: BigInt&, b: BigInt&) -> bool {
return !bigint_gt(b, a)
}
fn bigint_lt(a: BigInt&, b: BigInt&) -> bool {
return bigint_gt(b, a)
}
fn bigint_le(a: BigInt&, b: BigInt&) -> bool {
return !bigint_gt(a, b)
}
fn bigint_magnitude_gt(a: u32[]&, b: u32[]&) -> bool {
if a.len > b.len {
return true;
} else if b.len > a.len {
return false;
}
let len = a.len;
for i in len {
let alimb = a[len - 1 - i];
let blimb = b[len - 1 - i];
if alimb > blimb {
return true;
} else if blimb > alimb {
return false;
}
}
return false
}
We enforce canonical form, and Goose can == on any type, so we only really need to implement >. There's a pattern that's going to show up a lot - BigInt version that deals with sign stuff, and u32[] version that deals with two unsigned numbers.
Adding and subtracting numbers. Because we're not on two's complement, we need separate addition and subtraction code, and some sign logic to choose the right one. As usual, we need explicit checks so we don't accidentally create negative zero.
fn bigint_add(a: BigInt&, b: BigInt&) {
if a.negative == b.negative {
return BigInt{
negative: a.negative,
limbs: bigint_magnitude_add(a.limbs, b.limbs)
}
} else if (bigint_magnitude_gt(a.limbs, b.limbs)) {
// |a| > |b|
return BigInt{
negative: a.negative,
limbs: bigint_magnitude_sub(a.limbs, b.limbs)
}
} else if a.limbs == b.limbs {
// |a| == |b|
// special case this, to avoid negative 0
return bigint_zero();
} else {
// |b| > |a|
return BigInt{
negative: b.negative,
limbs: bigint_magnitude_sub(b.limbs, a.limbs)
}
}
}
fn bigint_sub(a: BigInt&, b: BigInt&) -> BigInt {
let bneg = bigint_neg(b);
return bigint_add(a, bneg)
}
fn bigint_magnitude_add(a: u32[]&, b: u32[]&) -> u32[] {
var result = [];
var carry : u64 = 0;
var i = 0;
while carry != 0 || i < a.len || i < b.len {
let alimb : u64 = (if a.len > i { a[i] } else { 0 });
let blimb : u64 = (if b.len > i { b[i] } else { 0 });
carry += alimb + blimb;
result.push((carry & 0xFFFFFFFF) as u32);
carry >>= 32;
i ++;
}
// no normalization needed, zeroes would work fine here
return result
}
// assumption: a > b
fn bigint_magnitude_sub(a: u32[]&, b: u32[]&) -> u32[] {
var result = [];
var borrow: u64 = 0;
var i = 0;
while i < a.len {
let alimb: u64 = a[i];
let blimb = (if b.len > i { b[i] } else { 0 });
let subtrahend : u64 = blimb + borrow;
if alimb < subtrahend {
result.push(((alimb + 0x100000000 - subtrahend) & 0xFFFFFFFF) as u32);
borrow = 1;
} else {
result.push((alimb - subtrahend) as u32);
borrow = 0;
}
i ++;
}
while result.len > 0 && result[result.len - 1] == 0 {
result.pop();
}
return result;
}
And here's multiplication. I need multiplication by 10 for string parsing.
fn bigint_mul(a: BigInt&, b: BigInt&) -> BigInt {
if bigint_is_zero(a) || bigint_is_zero(b) {
return bigint_zero()
}
return BigInt{
negative: a.negative != b.negative,
limbs: bigint_magnitude_mul(a.limbs, b.limbs)
}
}
fn bigint_magnitude_mul(a: u32[]&, b: u32[]&) -> u32[] {
var result : u32[>..] = [];
for i in b.len {
let partial = bigint_magnitude_mul_u32(a, b[i]);
var j = 0;
var carry : u64 = 0;
while carry != 0 || j < partial.len {
if i + j >= result.len {
result.push(0)
}
let plimb : u64 = (if j < partial.len { partial[j] } else { 0 });
carry = carry + result[i + j] + plimb;
result[i + j] = (carry & 0xFFFFFFFF) as u32;
carry >>= 32;
j++;
}
}
return result;
}
fn bigint_magnitude_mul_u32(a: u32[]&, b: u32) -> u32[] {
if b == 0 {
return []
}
let blimb : u64 = b;
var result = [];
var carry : u64 = 0;
var i = 0;
while carry != 0 || i < a.len {
let alimb : u64 = (if i < a.len { a[i] } else { 0 });
carry += alimb * blimb;
result.push((carry & 0xFFFFFFFF) as u32);
carry >>= 32;
i ++;
}
return result;
}
And now string parsing. It would be faster to multiply by 1000000000 and parse 9 digits at a time not one, but I'll leave this exercise to the reader. I skipped error checking to keep this post brief.
// accepts only well formed values
fn bigint_new(arg: u8[]&) -> BigInt {
var i = 0;
var is_negative : bool = (arg[0] == '-');
var result : u32[>..] = [];
if is_negative { i ++; };
while i < arg.len {
let digit : u32[] = [arg[i] - '0'];
var t0 : u32[] = copy(result);
var t1 : u32[] = bigint_magnitude_mul_u32(t0, 10);
var t2 : u32[] = bigint_magnitude_add(t1, digit);
result = copy(t2);
i++;
}
// normalize leading 0 and negative zero
while result.len > 0 && result[result.len - 1] == 0 {
result.pop();
}
if (result.len == 0) {
is_negative = false;
}
return BigInt{negative: is_negative, limbs: result};
}
Here we run into a limitation of Goose design. u32[>..] (growable array) and u32[] (fixed unknown length array) are not the same type, so we need copy both ways to make it work. We can't just declare result as u32[] as it would not allow assigning bigger value to it later, it would just panic the program. And we can't make it big with uninitialized data, as Goose doesn't have uninitialized data the way in C malloc results or char str[128] can contain any garbage until you deal with it.
Maybe there's a way to zero init result to the right capacity, or somehow cleverly avoid this copying.
Stdlib didn't contain any, so I added a helper for reversing an array, it works for any version, fixed, variable, growable etc.
// T is array type not element type, as there are so many array variants
fn array_reverse<T>(a : T&) {
let len = a.len;
var i = 0;
var j = len - 1;
while i < j {
let ai = a[i];
let aj = a[j];
a[i] = aj;
a[j] = ai;
i++;
j--;
}
}
And finally single limb division and to_s:
fn bigint_magnitude_div_u32(a: u32[]&, b: u32) -> u32[], u32 {
if a.len == 0 {
// raise exception here if b == 0?
return [], 0
}
var result : u32[>..] = [];
var remainder : u64 = 0;
for i in a.len {
let j = a.len-i-1;
remainder = (remainder << 32) + a[j];
result.push((remainder / b) as u32);
remainder = remainder % b;
};
array_reverse(result);
while result.len > 0 && result[result.len - 1] == 0 {
result.pop();
}
return result, (remainder as u32);
}
fn bigint_to_s(a: BigInt&) -> u8[] {
if bigint_is_zero(a) {
return "0";
}
var num : u32[>..] = copy(a.limbs);
var result : u8[>..] = [];
while num.len != 0 {
let numvar : u32[] = copy(num);
let rest, digit = bigint_magnitude_div_u32(numvar, 10);
result.push('0' + (digit as u8));
num = copy(rest);
}
if a.negative {
result.push('-');
}
array_reverse(result);
return result;
}
BigInt Fibonacci
You'd think that we'd be almost done here, just simple loop replacing + by bigint_add and so on. But no. We cannot reassign bigint b = c as BigInt is variable size.
Then I thought about just having BigInt[>..], appending some value, and adding last two values. But arrays of variable length elements are packed, and they cannot be indexed only iterated!
After some thinking I figured out that surely .push must return reference to the just pushed element, so I can keep last two references instead of last two values, and work with that. This was almost the solution, but a = b is value reassignment, not reference reassignment. Special a .= b operator is needed to reassign references.
And so we finally have our BigInt Fibonacci:
import os;
import bigint;
fn main() {
let argv = args();
if argv.len != 2 {
write_stderr("Usage: fib <number>\n");
exit(1);
}
let count = parse_int(argv[1]);
let one : u8[] = "1";
var nums : BigInt[>..] = [];
var a : BigInt& = nums.push(bigint_new(one));
var b : BigInt& = nums.push(bigint_new(one));
for i in 1..count+1 {
print("fib(", i, ")=", bigint_to_s(a));
let c : BigInt& = nums.push(bigint_add(a, b));
a .= b;
b .= c;
}
}
$ ./fib2 1000 | tail -n 1
fib(1000)=43466557686937456435688527675040625802564660517371780402481729089536555417949051890403879840079255169295922593080322634775209689623239873322471161642996440906533187938298969649928516003704476137795166849228875
Should you use Goose?
Goose takes an idea of a heapless memory-safe language, and tries to provide as close to normal development experience as possible. I think this is a great idea to play with, it would just be insanity to actually use that in production. Which are also my feelings about Rust.
Goose even has vibe coded VSCode plugin for syntax highlighting, which is more than most of the languages I reviewed.
Its standard library is lacking a lot of basic functionality like unit testing, or even reversing an array, but fundamentals seem to be quite solid.
I definitely recommend playing with it, earning it a place in "E Tier. Enjoy a weekend with them, then move on.". Which are also my feelings about Rust.
For now turning your ideas into a programming language is something barely within LLM's abilities, but over coming years it is likely to become a lot easier. Most of it will be slop like "Brainfuck except X" or "Python except in Albanian", but there will be gems hidden in the slop, Goose is one such gem.
Code
All code examples for the series will be in this repository.
Top comments (0)