1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
|
//! Recursion: fib(5), a call at a time. The debugger's whole context, from
//! one recording of every instruction, and beside it the lens: every call
//! of fib as a tree.
//!
//! How it moves (design/motion.md): the picture is established, then one
//! call is walked in full (the line fires, `rdi` and `rsp` strike, the
//! stack's words, then the backtrace's row and the tree's node; last the
//! marks move on); the way down the first branch is hurried, a run that
//! ramps in and out; the first return is walked (the answer in `rax`, the
//! frame leaving); the rest of the tree is a sprint with the context
//! veiled; and the last return, `fib(5)` itself, is walked again.
const anim = @import("anim");
const canim = @import("canim");
const recordings = @import("recordings");
pub const background = canim.background;
pub const scene = anim.Live(frame, struct {});
fn frame(s: *anim.Frame) void {
const rec = canim.open(recordings.steps);
// The calls of fib, in the order they are made: fib(5), fib(4), fib(3), fib(2), fib(1), fib(0), ...
const call = struct {
fn of(r: *canim.Recording, nth: usize) canim.Recording.Call {
return r.call("fib", nth);
}
}.of;
const split = canim.layout.split.subject;
// From main's line, about to call fib(5), to where fib(5) has returned to it.
var at = canim.cursor(s, rec, rec.lineMoment(10, rec.call("main", 0).enter));
at.levels = .{ .idea = .calls, .source_rows = 8 };
at.journey(.line, call(rec, 0).exit.?);
const ctx = canim.context(s, at, .{ .split = split });
// The lens: every call of fib as a tree, beside the frames they are on the stack.
const tree = canim.callTree(s, .{ .cursor = at, .stage = ctx.stage, .function = "fib", .focus = true });
ctx.map.add(s, canim.CallTree{ .cursor = at, .stage = ctx.map.stage, .function = "fib" });
var says: canim.Narrator = .{};
// Staging: the whole picture, still, before a word; the words, before a step.
const joins = ctx.ties(s);
canim.establish(s, .{ ctx.clock, ctx.registers, ctx.stack, ctx.source, ctx.disasm, tree, joins });
says.line(s, "`fib` calls itself. A call is a frame on the stack and a node\nin the tree; its argument arrives in `rdi`.");
// The call, once, in full; and the two lines that lead to the next one.
at.walk(s, .line, rec.lineMoment(6, call(rec, 0).enter));
s.wait(canim.theme.time.beat);
// Pacing: the same three lines three times more. Seen once, so
// hurried: down the first branch at a run, to the call that does not call.
says.line(s, "Down the first branch: each call the same three lines,\none frame deeper, `n` one less.");
at.hurry(s, .line, rec.lineMoment(5, call(rec, 4).enter), .{});
says.line(s, "`fib(1)` needs no other call. Its answer leaves in `rax`,\nand its frame goes.");
// The return, in full: what recursion is for.
at.walk(s, .line, call(rec, 4).exit.?);
says.line(s, "And so on through every branch: fifteen calls,\nto add up `fib(5)`.");
// The pattern is known: the rest of the tree at a sprint, the tree its
// subject, slowing into the last answers.
at.hurry(s, .line, call(rec, 10).exit.?, .{ .pace = canim.theme.time.sprint });
says.line(s, "The last answers come back up, each added to the one\nbefore it: `fib(5)` is 5, in `rax`, back in `main`.");
at.walk(s, .line, call(rec, 0).exit.?);
says.close(s);
}
|