Appendix C: Solutions to the Exercises
Every solution here was compiled and run like the rest of the book's examples. Most exercises have more than one good answer; these are just one way to do each.
#Chapter 2: Hello, GooseC.1
1. for i in 5 counts from 0 to 4, so print i + 1:
fn main() {
for i in 5 { print(i + 1); }
print("liftoff");
}
1 2 3 4 5 liftoff
2. A u8 counter that starts at 250 and is incremented ten times wraps
past 255 back to 0 and ends at 4. The result is the same with and without
--debug, because unsigned arithmetic wraps by definition in every build;
only signed overflow is checked in debug builds.
fn main() {
var honks: u8 = 250;
for i in 10 { honks += 1; }
print(honks);
}
4
#Chapter 3: Values and TypesC.2
1. It prints 4 260 4 0. a + b is a u8 addition, so 260 wraps to 4.
c + b widens b to i64 and gives 260. -1 % 5 is Euclidean and gives 4,
and -1 / 5 truncates toward zero and gives 0.
fn main() {
let a: u8 = 250;
let b: u8 = 10;
let c: i64 = 250;
print(a + b, " ", c + b, " ", -1 % 5, " ", -1 / 5);
}
4 260 4 0
2. No casts are needed. The i32 converts to a float implicitly as soon
as it meets a float operand, and writing the constants as float literals
makes the division happen in floating point. The literals take the type of
the destination, f32.
fn main() {
let c: i32 = -40;
let f: f32 = c * 9.0 / 5.0 + 32.0;
print(f);
}
-40.0
3. Because % is Euclidean, (h - k) % 24 is always a valid hour, even
when h - k is negative:
fn main() {
let h = 3;
let k = 50;
print((h - k) % 24);
}
1
#Chapter 4: Control Flow as ExpressionsC.3
1. Ranges are half-open, so the arm for an A runs to 101. There is no
open-ended range pattern, so scores outside 0 to 100 need an arm of their
own. The final _ arm, which is required anyway, is a natural place to
catch them.
fn grade(score: i64) -> u8[:] {
match score {
90..101 => "A",
80..90 => "B",
70..80 => "C",
0..70 => "F",
_ => "invalid",
}
}
fn main() {
for s in [95, 85, 75, 12, 100, 101, -5] { print(s, " ", grade(s)); }
}
95 A 85 B 75 C 12 F 100 A 101 invalid -5 invalid
2.
fn main() {
var n = 0;
let smallest = loop {
if n * n > 2026 { break n; }
n += 1;
};
print(smallest);
}
46
3. A square is # when its row and column add up to an even number:
fn main() {
for r in 4 {
print(if r % 2 == 0 { "#" } else { "." },
if r % 2 == 1 { "#" } else { "." },
if r % 2 == 0 { "#" } else { "." },
if r % 2 == 1 { "#" } else { "." });
}
}
#.#. .#.# #.#. .#.#
#Chapter 5: FunctionsC.4
1.
fn min_max(a: i64, b: i64, c: i64) -> i64, i64 {
var lo = a;
var hi = a;
if b < lo { lo = b; }
if c < lo { lo = c; }
if b > hi { hi = b; }
if c > hi { hi = c; }
return lo, hi;
}
fn main() {
let lo, hi = min_max(7, -2, 4);
print(lo, " ", hi);
}
-2 7
2. The first argument goes before the dot, and the defaults fill in whatever is left out:
fn clamp_weight(w: f64, lo: f64 = 2.0, hi: f64 = 8.0) -> f64 {
if w < lo { lo } else if w > hi { hi } else { w }
}
fn main() {
print(9.5.clamp_weight(), " ", 1.0.clamp_weight(), " ", 5.0.clamp_weight(6.0, 7.0));
}
8.0 2.0 6.0
3.
recursive fn digits(n: i64) -> i64 {
if n < 10 { 1 } else { 1 + digits(n / 10) }
}
fn main() {
print(digits(0), " ", digits(7), " ", digits(2026), " ", digits(1000000));
}
1 1 4 7
#Chapter 6: Where Values LiveC.5
1. The array is built directly in the caller's destination. While
squares runs, its local out already is the variable or argument slot
that receives the result, so return out copies nothing. Here the
destination is the argument of print, a temporary that lasts until the end
of the statement.
fn squares(n: i64) -> i64[>..] {
var out: i64[>..] = [];
for i in 1..n + 1 { out.push(i * i); }
return out;
}
fn main() { print(squares(6)); }
[1, 4, 9, 16, 25, 36]
2. b is not a copy, it names the same array as a, so pushes through
either one land in the same place. c is a real copy, taken while the array
held only 1.
fn main() {
var a: i64[>..] = [1];
let b = a;
var c = copy(a);
b.push(2);
c.push(3);
a.push(4);
print(a, " ", b, " ", c);
}
[1, 2, 4] [1, 2, 4] [1, 3]
3. Three: one for a, one for the copy in c, and one for the text
print builds. b is only a reference to a, so it needs no storage of its
own.
fn main() {
var a: i64[>..] = [1];
let b = a;
var c = copy(a);
b.push(2);
c.push(3);
a.push(4);
print(a, " ", b, " ", c);
}
data stacks: 2 GB reserved per stack, 1 MB guard gap, 32 TB budget: 16376 regions, GS_MAX_STACKS 1024 main program: 3 data stacks + 0 global stacks = 3 regions thread cap: none, no workers fn main: 3 own, 3 with callees
#Chapter 7: The Array FamilyC.6
1. A u8[..8] always takes the same number of bytes (a length byte and
room for 8 bytes), whatever name it holds, so every element of the array
has the same size and the third one starts at a known offset. A u8[]
takes as many bytes as its text, which makes an array of them sequential.
fn main() {
var names: u8[..8][>..] = [];
names.push("Ada");
names.push("Grace");
names.push("Linus");
print(names[1]);
}
Grace
2. The pops take 10, 9 and then 8, at which point the sum is 27:
fn main() {
var stack: i64[>..<] = [];
for i in 1..11 { stack.push(i); }
var sum = 0;
while sum <= 20 { sum += stack.pop(); }
print(sum, " ", stack);
}
27 [1, 2, 3, 4, 5, 6, 7]
3. A i64[..8] has room for only eight elements, so the ninth push stops
the program:
fn main() {
var stack: i64[..8] = [];
for i in 1..11 { stack.push(i); }
}
goose runtime error: limited array capacity exceeded
#Chapter 8: References and SlicesC.7
1. best is a reference variable that is rebound with .= as the loop
finds larger elements. for &x makes each x a reference to the element,
not a copy, so best .= x points at the array itself. The result is rooted
at the caller's array, so it may be returned.
fn largest(xs: i64[:]) -> i64& {
var best .= xs[0];
for &x in xs { if x > best { best .= x; } }
return best;
}
fn main() {
var xs: i64[3] = [3, 9, 4];
let big .= largest(xs);
big *= 2;
print(xs);
}
[3, 18, 4]
2. The returned slice views the caller's argument, so it is rooted at
whatever the caller passed in, which outlives the call. first_three
returned a view of its own local buf, which dies when the function returns.
fn middle(s: u8[:]) -> u8[:] {
if s.len < 2 { return s[..0]; }
return s[1..s.len - 1];
}
fn main() {
var b: u8[>..] = [];
b.append("gosling");
print(middle("goose"), " ", middle(b), " [", middle("x"), "]");
}
oos oslin []
3. Either print first before the clear, or give it bytes of its own.
A variable of type u8[] is a finished string that owns its bytes, so
initializing one from a slice copies the bytes:
fn main() {
var line: u8[>..] = [];
line.append("honk honk");
let first: u8[] = line[..4];
line.clear();
print(first);
}
honk
#Chapter 9: Strings Are BytesC.8
1. each_word hands each word to the block as a slice, and push adds a
single byte to the builder:
import std;
fn initials(full_name: u8[:]) -> u8[>..] {
var out: u8[>..] = [];
each_word(full_name) { out.push(it[0]); };
return out;
}
fn main() { print(initials("ada byron lovelace")); }
abl
2.
import std;
fn main() {
var total = 0;
each_split("Ada,4200;Bea,3900;Cleo,4600", ';') {
let fields = split(it, ',');
let grams, ok = parse_int(fields[1]);
if ok { total += grams; }
};
print(total);
}
12700
3.
struct Egg { day: i32, grams: f32 }
fn format(out: u8[>..]&, e: Egg) { format(out, "day ", e.day, ": ", e.grams, " g"); }
fn main() { print([Egg { 3, 61.5 }, Egg { 4, 72.0 }]); }
[day 3: 61.5 g, day 4: 72.0 g]
#Chapter 10: Structs and Inline DataC.9
1.
struct Nest { owner: u8[..12], eggs: i32 = 0, warm: bool = true }
fn main() {
let n1 = Nest { owner: "Ada", eggs: 4 };
let n2 = Nest { "Bea", 2, false };
let n3 = Nest { owner: "Cleo", .. };
print(n1, " ", n2, " ", n3);
}
Nest { "Ada", 4, true } Nest { "Bea", 2, false } Nest { "Cleo", 0, true }
2. Both take 10 bytes: 8 for the i64 and one each for the bool and
the u8. Goose packs fields without padding, so their order makes no
difference to the size. In C the first layout would take 24 bytes and the
second 16.
struct A { flag: bool, count: i64, small: u8 }
struct B { count: i64, flag: bool, small: u8 }
fn main() {
var a: A[>..] = [A { true, 1, 2 }];
var b: B[>..] = [B { 1, true, 2 }];
print(bytes_of(a).len, " ", bytes_of(b).len);
}
10 10
3. Put paid first, before any variable-size field, so that its offset
is a constant. It is a fixed-size field, so it can be assigned after the
order is built:
struct Item { sku: u8[varint], qty: varint, cents: varint }
struct Order { paid: bool, id: varint, customer: u8[varint], items: Item[varint] }
fn main() {
var book: Order[>..] = [];
book.push(Order { paid: false, id: 1, customer: "ada",
items: [Item { sku: "OATS", qty: 1, cents: 900 }] });
for o in book { o.paid = true; }
for o in book { print(o.customer, " paid: ", o.paid); }
}
ada paid: true
#Chapter 11: OptionalsC.10
1. for &g binds each element by reference, so returning g returns a
reference into the caller's array. Comparing a u8[..12] field with a slice
works because arrays of different kinds compare as slices.
struct Goose { name: u8[..12], weight: f32 }
fn find_name(flock: Goose[:], name: u8[:]) -> Goose? {
for &g in flock { if g.name == name { return g; } }
return null;
}
fn main() {
var flock: Goose[>..] = [Goose { "Ada", 4.5 }, Goose { "Bea", 5.25 }];
let g = find_name(flock, "Bea");
if g { g.name = "Beatrix"; }
print(flock);
}
[Goose { "Ada", 4.5 }, Goose { "Beatrix", 5.25 }]
2. Keep an optional and rebind it each time a negative element turns up:
fn last_negative(xs: i64[:]) -> i64? {
var found: i64? = null;
for &x in xs { if x < 0 { found .= x; } }
return found;
}
fn main() {
let xs: i64[5] = [3, -1, 4, -5, 9];
let ys: i64[2] = [1, 2];
let n = last_negative(xs);
if n { print(n); }
print(last_negative(ys) == null);
}
-5 true
3. An optional is a reference, and x is a local of make that dies
when the function returns, so the reference would dangle. A function that
computes a new value should return the value itself, usually with a bool:
fn make() -> i64, bool {
let x = 5;
return x, true;
}
fn main() {
let v, ok = make();
print(v, " ", ok);
}
5 true
#Chapter 12: Enums in Two SizesC.11
1. Both versions behave the same. Note the type on meals: an array
literal with no destination type takes its element type from its first
element, which here would be the variant type Feed.Grain, and the other
variants would not fit.
enum Feed { Grain { grams: i32 }, Grass, Bread { slices: i32 } }
fn health(f: Feed) -> i64 {
match f {
Grain g => if g.grams > 200 { 6 } else { 8 },
Grass => 10,
Bread b => 2,
}
}
fn health2(f: Feed.Grain) -> i64 { if f.grams > 200 { 6 } else { 8 } }
fn health2(f: Feed.Grass) -> i64 { 10 }
fn health2(f: Feed.Bread) -> i64 { 2 }
fn main() {
let meals: Feed[3] = [Feed.Grain { grams: 150 }, Feed.Grass, Feed.Bread { slices: 2 }];
for m in meals { print(health(m), " ", health2(m)); }
}
8 8 10 10 2 2
2. In fixed mode every meal takes a tag and four bytes of payload room,
5 bytes in all. In variable mode a Grass takes only its one-byte tag.
enum Feed { Grain { grams: i32 }, Grass, Bread { slices: i32 } }
fn main() {
var fixed: Feed[>..] = [];
var packed: Feed..[>..] = [];
for i in 50 {
fixed.push(Feed.Grass);
fixed.push(Feed.Grain { grams: 100 });
packed.push(Feed.Grass);
packed.push(Feed.Grain { grams: 100 });
}
print(bytes_of(fixed).len, " ", bytes_of(packed).len);
}
500 300
3.
enum Feed { Grain { grams: i32 }, Grass, Bread { slices: i32 } }
fn main() {
var meals: Feed..[>..] = [];
meals.push(Feed.Bread { slices: 1 });
meals.push(Feed.Grass);
meals.push(Feed.Bread { slices: 3 });
for f in meals {
match f { Bread &b => { b.slices *= 2; }, _ => {} }
}
print(meals);
}
[Bread { 2 }, Feed.Grass, Bread { 6 }]
#Chapter 13: Links Without PointersC.12
1. When a node is not lighter than w, nothing in its right subtree can
be lighter either, so only the left side needs visiting. Taking the node as
a Node? lets the recursion pass the links straight through:
struct Node { name: u8[..8], weight: i32, left: Node&<u32>?, right: Node&<u32>? }
fn insert(tree: Node[>..]&, name: u8[:], weight: i32) {
if tree.len == 0 { tree.push(Node { name: name, weight: weight }); return; }
var cur .= tree[0];
loop {
if weight < cur.weight {
let l = cur.left;
if l { cur .= l; continue; }
cur.left .= tree.push(Node { name: name, weight: weight });
return;
}
let r = cur.right;
if r { cur .= r; continue; }
cur.right .= tree.push(Node { name: name, weight: weight });
return;
}
}
recursive fn count_lighter(n: Node?, w: i32) -> i64 {
guard n else { return 0; }
if n.weight >= w { return count_lighter(n.left, w); }
return 1 + count_lighter(n.left, w) + count_lighter(n.right, w);
}
fn main() {
var tree: Node[>..] = [];
for p in [45, 52, 38, 41, 60] { insert(tree, "g", p as i32); }
print(count_lighter(tree[0], 50), " ", count_lighter(tree[0], 39), " ",
count_lighter(tree[0], 100));
}
3 1 5
2. Keep a reference to the last link and move it along as you push:
struct Link { v: i64, next: Link&<u32>? }
fn main() {
var list: Link[>..] = [Link { v: 1 }];
var last .= list[0];
for i in 2..6 {
let n .= list.push(Link { v: i });
last.next .= n;
last .= n;
}
var cur: Link? = list[0];
var out: u8[>..] = [];
while cur { format(out, cur.v, " "); cur .= cur.next; }
print(out);
}
1 2 3 4 5
3. A self-relative link must point into the same array as the field that
holds it. The elements of by_age live in by_age, but the geese live in
flock, so the store is rejected:
struct Goose { name: u8[..8], mate: Goose&<u16>? }
var flock: Goose[>..] = [];
var by_age: (Goose&<u32>)[>..] = [];
fn main() {
flock.push(Goose { name: "Ada", .. });
by_age.push(flock[0]);
}
error: a relative reference must point within the same root as its location (§3.9); this reference is rooted at flock
#Chapter 14: Pools for Lifetimes That Don't NestC.13
1. Unlink the patient exactly as leave does, but instead of freeing the
slot, link it back in between head and the first patient:
struct Patient { name: u8[..8], prev: Patient&<u32 in queue>, next: Patient&<u32 in queue> }
reusable var queue: Patient[>..] = [];
let head = queue.alloc_index(Patient { name: "", prev: self, next: self });
fn arrive(name: u8[:]) -> Patient& {
let tail .= queue[head].prev;
let p .= queue.alloc_ref(Patient { name: name, prev: tail, next: queue[head] });
tail.next .= p;
queue[head].prev .= p;
return p;
}
fn jump_queue(p: Patient&) {
p.prev.next .= p.next;
p.next.prev .= p.prev;
let first .= queue[head].next;
p.prev .= queue[head];
p.next .= first;
first.prev .= p;
queue[head].next .= p;
}
fn show() {
var out: u8[>..] = [];
var cur .= queue[head].next;
while cur .!= queue[head] { format(out, cur.name, " "); cur .= cur.next; }
print(out);
}
fn main() {
arrive("Ada");
arrive("Bea");
let cleo .= arrive("Cleo");
jump_queue(cleo);
show();
}
Cleo Ada Bea
2. When every egg is freed straight away, every allocation after the first reuses slot 0, so the pool ends with one slot. When only every other egg is freed, each freed slot is taken by the next allocation and then kept, so every two allocations add one slot: 500 in all.
struct Egg { day: i32 }
fn main() {
reusable var tray: Egg[>..] = [];
for i in 1000 { let s = tray.alloc_index(Egg { i as i32 }); tray.free(s); }
print(tray.len);
reusable var tray2: Egg[>..] = [];
for i in 1000 {
let s = tray2.alloc_index(Egg { i as i32 });
if i % 2 == 0 { tray2.free(s); }
}
print(tray2.len);
}
1 500
3. A pool never gives its memory back and only holds fixed-size values
of one type, so a freed slot is always a valid value of the element type,
and a reference to it can only ever read such a value. A grow-shrink array
does give memory back: after a pop, the space above the new top belongs
to its data stack again and can be reused for a value of a completely
different type. A reference kept across the pop could then read memory at
the wrong type. That is why the compiler only allows references into a
grow-shrink array in local variables, where it can check every one of them
at each shrink.
#Chapter 15: ErrorsC.14
1.
fn safe_divide(a: i64, b: i64) -> i64, bool {
if b == 0 { return 0, false; }
return a / b, true;
}
fn main() {
for geese in [0, 4] {
let each, ok = safe_divide(12, geese);
print(each, " ", ok);
}
}
0 false 3 true
2. Only parse_goose changes: one more guard. Nothing between it and
load needs to know that a new kind of error exists.
import std;
struct Goose { name: u8[..12], weight: f32 }
fn load(text: u8[:]) -> Goose[>..], u8[] {
var flock: Goose[>..] = [];
var line_no = 0;
each_split(text, '\n') {
line_no++;
if trim(it).len > 0 { flock.push(parse_goose(it, line_no)); }
};
return flock, "";
}
fn parse_goose(line: u8[:], line_no: i64) -> Goose {
let fields = split(line, ',');
guard fields.len == 2 else {
return [], str("line ", line_no, ": expected name,weight") from load;
}
let w, ok = parse_flt(trim(fields[1]));
guard ok else { return [], str("line ", line_no, ": bad weight") from load; }
guard w <= 15.0 else { return [], str("line ", line_no, ": impossibly heavy") from load; }
return Goose { name: trim(fields[0]), weight: w as f32 };
}
fn main() {
let flock, err = load("Ada, 4.5\nBig, 40\n");
print(flock.len, " ", err);
}
0 line 2: impossibly heavy
3. The error type is u8[], owned text. The loading code becomes a
nested function, so that it can fill in the caller's flock and be passed
to try by name:
import std;
import exception;
struct Goose { name: u8[..12], weight: f32 }
fn parse_goose(line: u8[:], line_no: i64) -> Goose {
let fields = split(line, ',');
guard fields.len == 2 else { exception::throw(str("line ", line_no, ": expected name,weight")); }
let w, ok = parse_flt(trim(fields[1]));
guard ok else { exception::throw(str("line ", line_no, ": bad weight")); }
return Goose { name: trim(fields[0]), weight: w as f32 };
}
fn report(text: u8[:]) {
var flock: Goose[>..] = [];
fn body() {
var line_no = 0;
each_split(text, '\n') {
line_no++;
if trim(it).len > 0 { flock.push(parse_goose(it, line_no)); }
};
print("loaded ", flock.len, ": ", flock);
}
exception::try<u8[]>(body) { err => print("error: ", err); };
}
fn main() {
report("Ada, 4.5\nBea, 5.25\n");
report("Ada\n");
}
loaded 2: [Goose { "Ada", 4.5 }, Goose { "Bea", 5.25 }]
error: line 1: expected name,weight
#Chapter 16: Generics and BlocksC.15
1. The literal bounds adapt to the element type of each instantiation:
fn clamp_all<T>(xs: T[:], lo: T, hi: T) {
for &x in xs { if x < lo { x = lo; } else if x > hi { x = hi; } }
}
fn main() {
var a: i64[4] = [-5, 3, 12, 7];
var b: f32[3] = [0.5, -1.0, 2.5];
clamp_all(a, 0, 10);
clamp_all(b, 0.0, 1.0);
print(a, " ", b);
}
[0, 3, 10, 7] [0.5, 0.0, 1.0]
2.
import std;
fn each_window<T, F>(xs: T[:], n: i64) {
for i in 0..xs.len - n + 1 { F(xs[i..i + n]); }
}
fn main() {
let xs: i64[5] = [1, 2, 3, 4, 5];
each_window(xs, 3) { print(sum(it)); };
}
6 9 12
3. The calls chain with method-call syntax. filter returns a new array,
and map is called on it:
import std;
fn main() {
let eggs: i64[5] = [61, 72, 58, 66, 70];
let kg = eggs.filter() { it > 60 }.map() { it as f64 / 1000.0 };
print(kg);
}
[0.061, 0.072, 0.066, 0.07]
#Chapter 17: RecursionC.16
1. Recurse first, then push, so the most significant digit comes out first. The builder belongs to the caller, so it may be passed down:
recursive fn binary(n: i64, out: u8[>..]&) {
if n >= 2 { binary(n / 2, out); }
out.push(('0' + n % 2) as u8);
}
fn main() {
for n in [0, 5, 10, 255] {
var out: u8[>..] = [];
binary(n, out);
print(out);
}
}
0 101 1010 11111111
2. A slice is fixed-size: it is a pointer and a count, sixteen bytes whatever it views. Holding slices across the recursive calls is therefore fine.
recursive fn halves(xs: i64[:]) -> i64 {
if xs.len == 0 { return 0; }
if xs.len == 1 { return xs[0]; }
let mid = xs.len / 2;
return halves(xs[..mid]) + halves(xs[mid..]);
}
fn main() {
let xs: i64[7] = [1, 2, 3, 4, 5, 6, 7];
print(halves(xs));
}
28
3. The count comes from a second recursive walk of the subtree, which
returns an integer, so it needs nothing beyond the native stack. (Having
draw return its own count would also work, but the count must be printed
before the children are drawn.)
struct Place { name: u8[..8], inside: i64[..4] }
struct Ctx { places: Place[>..]&, out: u8[>..]& }
recursive fn count(c: Ctx&, i: i64) -> i64 {
var t = 0;
for k in c.places[i].inside { t += 1 + count(c, k); }
return t;
}
recursive fn draw(c: Ctx&, i: i64, depth: i64) {
for d in depth { c.out.append(" "); }
format(c.out, c.places[i].name, " (", count(c, i), ")\n");
for k in c.places[i].inside { draw(c, k, depth + 1); }
}
fn main() {
var places: Place[>..] = [];
for n in ["farm", "pond", "barn", "Ada", "Bea"] { places.push(Place { name: n, inside: [] }); }
places[0].inside.push(1);
places[0].inside.push(2);
places[1].inside.push(3);
places[2].inside.push(4);
var out: u8[>..] = [];
var c = Ctx { places: places, out: out };
draw(c, 0, 0);
print(out);
}
farm (4)
pond (1)
Ada (0)
barn (1)
Bea (0)
#Chapter 18: A Tour of the Standard LibraryC.17
1. update counts each weight. The block given to each can write the
enclosing function's locals, so it can track the best entry as it goes:
import dictionary;
fn main() {
var counts = dictionary<i64, i64> {};
for w in [61, 72, 61, 58, 72, 61] { counts.update(w, 0) { it += 1; }; }
var best = 0;
var best_n = 0;
counts.each() { w, n => if n > best_n { best = w; best_n = n; } };
print(best, " appears ", best_n, " times");
}
61 appears 3 times
2.
import std;
import os;
import csv;
fn main() {
write_file("nests.csv", "Ada,3\nBea,1\nCleo,4\n");
var text: u8[>..] = [];
if !read_file("nests.csv", text) { abort("cannot read nests.csv"); }
var total = 0;
csv::each_record(text) { f =>
let n, ok = parse_int(f[1]);
if ok { total += n; }
};
delete_file("nests.csv");
print(total, " eggs");
}
8 eggs
3. Give two geese the same weight, in a known order. After the sort, Ada still comes before Cleo, as she did in the input:
import std;
struct Goose { name: u8[..8], weight: i64 }
fn main() {
var flock: Goose[>..] = [Goose { "Ada", 45 }, Goose { "Bea", 52 },
Goose { "Cleo", 45 }, Goose { "Dot", 38 }];
stable_sort(flock) { a, b => a.weight < b.weight };
print(flock);
}
[Goose { "Dot", 38 }, Goose { "Ada", 45 }, Goose { "Cleo", 45 }, Goose { "Bea", 52 }]
#Chapter 19: Programs, Namespaces and PackagesC.18
1. Naming the type in a literal needs the prefix, geese::Goose { … }.
Printing a goose and calling its functions with a dot need none, because
the format hook and method-style calls are looked up in the namespace of
the value's type.
namespace geese;
struct Goose { name: u8[..12], weight: f32 }
fn format(out: u8[>..]&, g: Goose) { format(out, g.name, " (", g.weight, " kg)"); }
fn heavier(g: Goose, kg: f32) -> Goose { Goose { name: g.name, weight: g.weight + kg } }
fn ::main() { print(geese::Goose { "Test", 1.0 }); }
import geese;
fn main() {
let g = geese::Goose { "Ada", 4.5 };
print(g, " ", g.heavier(0.5));
}
Ada (4.5 kg) Ada (5.0 kg)
2. The fn ::main() above prints Test (1.0 kg) when you run
geese.goose directly. When the root file imports geese.goose, the
library's main is ignored, and only the root's main runs, as the output
above shows. (A plain fn main() inside the namespace would be
geese::main, which is not an entry point at all.)
3. Both functions end up in the global namespace with the same signature, so every call is ambiguous:
fn load(path: u8[:]) -> i64 { 1 }
fn load(path: u8[:]) -> i64 { 2 }
import a;
import b;
fn main() { print(load("x")); }
error: ambiguous call to load: multiple overloads match equally well
Putting each library in a namespace of its own avoids the clash.
#Chapter 20: Threads That Share NothingC.19
1. Pass each worker its half of the range as arguments. The two results can arrive in either order, which does not matter for a sum:
struct Part { sum: i64 }
thread_fn summer(lo: i64, hi: i64) {
var s = 0;
for i in lo..hi { s += i; }
qput(Part { sum: s });
}
fn main() {
let a = thread_spawn(summer, 1, 500001);
let b = thread_spawn(summer, 500001, 1000001);
let total = qget<Part>().sum + qget<Part>().sum;
thread_wait(a);
thread_wait(b);
print(total);
}
500000500000
2. The weights travel inside the message, as part of one flat value:
struct Batch { weights: f32[] }
struct Avg { value: f32 }
thread_fn averager() {
let b = qget<Batch>();
var t: f32 = 0.0;
for w in b.weights { t += w; }
qput(Avg { value: t / b.weights.len });
}
fn main() {
let w = thread_spawn(averager);
qput(Batch { weights: [4.5, 5.25, 3.0, 4.0, 4.75] });
print(qget<Avg>().value);
thread_wait(w);
}
4.3
3. The worker increments its own copy, taken when it was spawned, so it
reports one more than main had, and main's global is unchanged:
struct Count { value: i64 }
var counter = 0;
thread_fn bumper() {
counter += 1;
qput(Count { value: counter });
}
fn main() {
counter = 41;
let c = thread_spawn(bumper);
print("worker says ", qget<Count>().value, ", main still has ", counter);
thread_wait(c);
}
worker says 42, main still has 41
#Chapter 21: Saving and Loading BytesC.20
1. The loaded diary is an ordinary grow-only array, so it can be pushed to like any other:
import os;
struct Entry { day: varint, note: u8[varint] }
fn main() {
var diary: Entry[>..] = [];
diary.push(Entry { day: 1, note: "first egg" });
diary.push(Entry { day: 3, note: "two eggs" });
print(write_file_atomic("diary.bin", diary.to_bytes()));
var disk: u8[>..] = [];
read_file("diary.bin", disk);
var back, ok = from_bytes<Entry[>..]>(disk);
back.push(Entry { day: 4, note: "a goose stole the bread" });
print(ok, " ", back);
delete_file("diary.bin");
}
true
true [Entry { 1, "first egg" }, Entry { 3, "two eggs" }, Entry { 4, "a goose stole the bread" }]
2. The first byte, 22, is the image's length. Each word follows as a
four-byte little-endian length (4 0 0 0, 2 0 0 0) and then its
characters, because the elements are u8[], whose length is a u32:
fn main() {
var words: u8[][>..] = [];
for w in ["honk", "hi", "flap"] { words.push(w); }
var out: u8[>..] = [];
for b in words.to_bytes() { format(out, b, " "); }
print(out);
}
22 4 0 0 0 104 111 110 107 2 0 0 0 104 105 4 0 0 0 102 108 97 112
3. An empty file is not a valid image (it does not even have a length),
so from_bytes rejects it. A file that cannot be read gives false too.
Since from_bytes already returns an array and a bool, the function can
return its results directly:
import os;
struct Goose { name: u8[..8], weight: i32 }
fn load_geese(path: u8[:]) -> Goose[>..], bool {
var disk: u8[>..] = [];
if !read_file(path, disk) { return [], false; }
return from_bytes<Goose[>..]>(disk);
}
fn main() {
write_file("empty.bin", "");
let e, eok = load_geese("empty.bin");
let m, mok = load_geese("missing.bin");
var flock: Goose[>..] = [Goose { "Ada", 45 }];
write_file("geese.bin", flock.to_bytes());
let g, gok = load_geese("geese.bin");
print(eok, " ", mok, " ", gok, " ", g);
delete_file("empty.bin");
delete_file("geese.bin");
}
false false true [Goose { "Ada", 45 }]
#Chapter 22: Talking to CC.21
1. C's fmod truncates, so its result has the sign of the dividend,
and Goose's float % is fmod. Integer % is different: it is
Euclidean (Chapter 3), so -7 % 3 is 2, the value that pairs with
rounding -7 / 3 down, as floor does:
extern fn floor(x: f64) -> f64;
extern fn fmod(x: f64, y: f64) -> f64;
fn main() {
print(fmod(-7.0, 3.0), " ", -7.0 % 3.0, " ", -7 % 3);
print(floor(-7.0 / 3.0));
}
-1.0 -1.0 2 -3.0
2. The C file declares the slice struct and writes the count through the pointer:
#include <stdint.h>
typedef struct { const uint8_t *data; int64_t len; } u8_slice;
void count_vowels(u8_slice s, int64_t *out) {
int64_t n = 0;
for (int64_t i = 0; i < s.len; i++) {
switch (s.data[i] | 0x20) {
case 'a': case 'e': case 'i': case 'o': case 'u': n++;
}
}
*out = n;
}
c_sources = ["vowels.c"];
On the Goose side, an i64& crosses as an int64_t *:
extern fn count_vowels(s: const u8[:], out: i64&);
fn main() {
for w in ["goose", "Honk", "aeiou", "rhythm"] {
var n: i64 = 0;
count_vowels(w, n);
print(w, ": ", n);
}
}
goose: 3 Honk: 1 aeiou: 5 rhythm: 0
3. Neither has a plain C shape. A Goose? has a presence flag whose
layout is the compiler's business, and a u8[] stores its bytes inline
after a length, so its size is not known to C. Pass the parts instead: a
bool and a Goose (or a Goose&) for the optional, and a const u8[:]
slice for the string, which C sees as { data, len }.
#Chapter 23: PerformanceC.22
1. Whether the version without an assert keeps checks depends on its
callers. Called only with arrays whose lengths the compiler can see are
equal, it keeps none, since facts cross calls. Called with arrays from
fill(n) (as in the chapter), it keeps the checks on a[i] and b[i].
With the assert, it keeps none whoever calls it:
fn add(a: f32[:], b: f32[:], out: f32[:]) {
assert(a.len == out.len && b.len == out.len);
for i in out.len { out[i] = a[i] + b[i]; }
}
fn main() {
var a: f32[>..] = [1.0, 2.0, 3.0];
var b: f32[>..] = [10.0, 20.0, 30.0];
var out: f32[>..] = [0.0, 0.0, 0.0];
add(a, b, out);
print(out);
}
bce-line: main.goose:3: 3 elided, 0 kept
[11.0, 22.0, 33.0]
2. With the assert, checkfree fn add compiles. Without it, it does
not, even though every call in the program passes three arrays of the same
length, because a checkfree function must prove its checks unnecessary
on its own:
checkfree fn add(a: f32[:], b: f32[:], out: f32[:]) {
for i in out.len { out[i] = a[i] + b[i]; }
}
fn main() {
let a: f32[3] = [1.0, 2.0, 3.0];
let b: f32[3] = [10.0, 20.0, 30.0];
var out: f32[3] = [0.0, 0.0, 0.0];
add(a, b, out);
print(out);
}
main.goose:2: error: checkfree fn add keeps a bounds check: nothing shows i < a.len main.goose:2: error: checkfree fn add keeps a bounds check: nothing shows i < b.len
3. Each node keeps the range of its edges as two bound types, and each
edge is a NodeId. All the nodes are pushed first, so that every edge can
be converted to a NodeId when it is pushed:
struct Node { weight: i32, lo: u32 upto edges, hi: u32 upto edges }
var nodes: Node[>..] = [];
type NodeId = u32 in nodes;
var edges: NodeId[>..] = [];
checkfree fn neighbour_weight(n: NodeId) -> i64 {
let node = nodes[n];
var t = 0;
for k in node.lo..node.hi { t += nodes[edges[k]].weight; }
return t;
}
fn main() {
let none = 0 as (u32 upto edges);
for w in [5, 3, 8, 1] {
nodes.push(Node { weight: w as i32, lo: none, hi: none });
}
let links: i64[2][4] = [[1, 2], [2, 3], [3, 0], [0, 1]];
for v in nodes.len {
nodes[v].lo = edges.len as (u32 upto edges);
for t in links[v] { edges.push(t as NodeId); }
nodes[v].hi = edges.len as (u32 upto edges);
}
for v in nodes.len {
print("node ", v, ": ", neighbour_weight(v as NodeId));
}
}
node 0: 11 node 1: 9 node 2: 6 node 3: 8
The loop for k in node.lo..node.hi gives k the index type of edges,
since both of its bounds are bound types of edges, so edges[k] needs no
check, and edges[k] is a NodeId, so nodes[edges[k]] needs none either.
#Chapter 24: A Word CounterC.23
The solutions for this chapter and the next show only the parts of the program that change. The rest is as printed in the chapter.
1. Only the test in count_words changes. total now counts the
words that were kept:
fn count_words(text: const u8[:], counts: Counts&) -> i64 {
var total = 0;
var i = 0;
while i < text.len {
while i < text.len && !is_word_byte(text[i]) { i += 1; }
let start = i;
while i < text.len && is_word_byte(text[i]) { i += 1; }
if i - start > 2 {
counts.update(text[start..i], 0) { it += 1; };
total += 1;
}
}
return total;
}
47 words, 21 different
11 the
7 goose
4 and
3 eggs
3 farmer
3 kept
2. Every entry of list has its count, so a loop after the table
finds them. The output below shows the top three:
fn main() {
let a = args();
guard a.len >= 2 else {
print("usage: words file [how-many]");
exit(2);
}
var top = 10;
if a.len >= 3 {
let n, ok = parse_int(a[2]);
guard ok && n > 0 else {
print("not a count: ", a[2]);
exit(2);
}
top = n;
}
var text: u8[>..] = [];
guard read_file(a[1], text) else {
print("cannot read ", a[1]);
exit(1);
}
to_lower(text);
var counts = Counts {};
let total = count_words(text, counts);
let list = ranked(counts);
print(total, " words, ", counts.count, " different");
for c in list[..min(top, list.len)] {
var line: u8[>..] = [];
format_int(line, c.n, 10, 5, ' ');
format(line, " ", c.word);
print(line);
}
var once = 0;
for c in list { if c.n == 1 { once += 1; } }
print(once, " words occur once");
}
53 words, 24 different
11 the
7 goose
4 and
15 words occur once
3. Nothing else has to change. main passes text, which is writable, so
it can be passed as either kind of slice. Inside count_words, the
slices text[start..i] are now writable, and a writable slice converts to
the dictionary's read-only key type where it is inserted. The conversion
only goes that way: a const u8[:] cannot be passed where a u8[:] is
expected. So the const version is the better signature, since it accepts
both kinds of text.
fn count_words(text: u8[:], counts: Counts&) -> i64 {
var total = 0;
var i = 0;
while i < text.len {
while i < text.len && !is_word_byte(text[i]) { i += 1; }
let start = i;
while i < text.len && is_word_byte(text[i]) { i += 1; }
if i > start {
counts.update(text[start..i], 0) { it += 1; };
total += 1;
}
}
return total;
}
53 words, 24 different
11 the
7 goose
4. The program now reads standard input when there is no file name, or
when the name is -, the usual convention, which also lets a count be
given with standard input: goose words.goose -- - 3 < geese.txt.
fn main() {
let a = args();
var top = 10;
if a.len >= 3 {
let n, ok = parse_int(a[2]);
guard ok && n > 0 else {
print("not a count: ", a[2]);
exit(2);
}
top = n;
}
var text: u8[>..] = [];
if a.len < 2 || a[1] == "-" {
read_stdin(text);
} else {
guard read_file(a[1], text) else {
print("cannot read ", a[1]);
exit(1);
}
}
to_lower(text);
var counts = Counts {};
let total = count_words(text, counts);
let list = ranked(counts);
print(total, " words, ", counts.count, " different");
for c in list[..min(top, list.len)] {
var line: u8[>..] = [];
format_int(line, c.n, 10, 5, ' ');
format(line, " ", c.word);
print(line);
}
}
53 words, 24 different
11 the
7 goose
4 and
#Chapter 25: A CalculatorC.24
1. % joins / in product, sharing its check for zero. The version
below uses Goose's float %, which is C's fmod: the result has the sign
of the dividend, so -7 % 3 is -1. A calculator for people rather than
programmers might prefer the Euclidean result, 2, which v - d *
floor(v / d) gives for a positive d. Either is defensible, as long as
the choice is documented.
7 % 3
-7 % 3
7.5 % 2
2 * 7 % 4
1 % 0
recursive fn sum() -> f64 {
var v = product();
loop {
if eat('+') { v += product(); }
else if eat('-') { v -= product(); }
else { return v; }
}
}
fn product() -> f64 {
var v = power();
loop {
if eat('*') { v *= power(); }
else if eat('/') || eat('%') {
let op = src[pos - 1];
let at = here();
let d = power();
if d == 0.0 {
return fail(at, "division by zero");
}
if op == '/' { v /= d; } else { v = v % d; }
}
else { return v; }
}
}
1.0 -1.0 1.5 2.0 error: column 5: division by zero
2. A call gets a function of its own, call, which reads one argument
or two. group is still used for plain parentheses, so (1, 2) remains
an error. call is part of the recursion cycle through sum, and it
keeps the depth count, like group:
max(2, 3) * min(4, 5)
max(1, -max(2, 3))
sqrt(4, 9)
max(1, 2
fn atom() -> f64 {
let c = peek();
let at = pos; // after the spaces
if eat('(') { return group(at); }
if is_digit(c) || c == '.' { return number(); }
if c == 0 { return fail(at, "unexpected end of line"); }
if !is_letter(c) {
return fail(at, str("unexpected ", src[at..at + 1]));
}
let n = word();
if eat('(') { return call(at, n); }
let v = vars.get(n);
if v { return v; }
return fail(at, str("unknown name ", n));
}
// After the '(' of f(: one argument or two, then ')'.
fn call(at: i64, f: u8[:]) -> f64 {
12.0 1.0 error: column 1: no function of two arguments called sqrt error: column 9: expected )
3. main stores each value it prints. A line that fails leaves ans
as it was, which is what a user would expect:
6 * 7
ans / 2
ans + ans
let x = 1 / 0
ans
fn main() {
var vars = Vars {};
vars.insert("pi", PI);
var line: u8[>..] = [];
while read_line(line) {
if trim(line).len > 0 {
let v, err = evaluate(line, vars);
if err.len > 0 {
print("error: ", err);
} else {
print(v);
vars.insert("ans", v);
}
}
line.clear();
}
}
42.0 21.0 42.0 error: column 13: division by zero 42.0
4. The column becomes a result of its own instead of part of the text,
so that main can use it. fail returns the position, and main prints
the line, then a ^ under that position:
1 / (2 - 2)
2 * (3 + 4
wings + 1
// One line of input: `let name = expr`, or an expression. Returns
// the value, -1 and "", or 0.0, the position of the error and
// what went wrong.
fn evaluate(src: const u8[:], vars: Vars&) -> f64, i64, u8[] {
fn fail(at: i64, what: u8[:]) -> f64 {
return 0.0, at, str(what) from evaluate;
}
return statement(), -1, "";
fn main() {
var vars = Vars {};
vars.insert("pi", PI);
var line: u8[>..] = [];
while read_line(line) {
if trim(line).len > 0 {
let v, at, err = evaluate(line, vars);
if err.len == 0 { print(v); }
else {
var mark: u8[>..] = [];
for k in at { mark.push(' '); }
mark.push('^');
print(line, "\n", mark, " ", err);
}
}
line.clear();
}
}
1 / (2 - 2)
^ division by zero
2 * (3 + 4
^ expected )
wings + 1
^ unknown name wings