lib/mprompt/src/root.zig

daab053ee43316e1809a84551d573ddd1e5bf3d2

 1 //! The package lets a Zig function stop partway through, hand control back to an earlier point on
 2 //! the call stack, and later continue from where it stopped, with a value passed in. Capturing a
 3 //! running computation's stack segment and resuming it later gives the package delimited
 4 //! continuations, and on top of them typed algebraic effect handlers. It has two layers: functions
 5 //! with the C calling convention that pass raw pointers, and a typed Zig API whose value types the
 6 //! compiler checks. The runtime keeps each thread's running computations, cached stacks and
 7 //! handlers in per-thread state.
 8 //!
 9 //! Generators, workers that wait for their next request, backtracking searches, and interpreters
10 //! that pause to ask their host for a value all need a computation that stops in the middle and
11 //! continues later. The code that started such a computation needs to learn whether it finished or
12 //! paused, and then continue it once, continue it more than once, or abandon it.
13 //!
14 //! A paused computation needs every frame between the pause and its starting point kept alive, with
15 //! its locals and return addresses, and an ordinary call stack discards those frames when the
16 //! function returns. Continuing twice from one pause needs the frames as they were at the pause,
17 //! and running the rest of the computation the first time overwrites them. Each paused computation
18 //! needs a stack of its own, and programs hold many at once: a test keeps 16 workers paused, and
19 //! the profiling workload runs 10,000. So an idle stack has to cost little memory, and a busy one
20 //! has to stay within a bound. Moving from one stack to another means saving and restoring the
21 //! processor's registers, which takes code written for each processor.
22 //!
23 //! Daan Leijen's paper [Implementing Algebraic Effects in
24 //! C](https://www.microsoft.com/en-us/research/publication/implementing-algebraic-effects-c/) and
25 //! his [libmprompt](https://github.com/koka-lang/libmprompt) library, from the Koka project,
26 //! implement multi-prompt delimited continuations and algebraic effect handlers. The package keeps
27 //! libmprompt's execution model: code runs on stacks of its own, suspends to a marked point, and
28 //! resumes through a handle, and handlers move control the same way. The package's reference
29 //! benchmark reruns libmprompt's reference workloads at release sizes, and a test runs the effect
30 //! counter at the upstream debug workload size.
31 //!
32 //! Each resumable computation runs on a stack of its own, a stacklet, reserved at a fixed size (8
33 //! MiB by default) with an unmapped gap at each end, and its pages become usable only as the stack
34 //! grows into them. The runtime marks the point where a computation enters its stacklet as the
35 //! computation's prompt, the computation suspends back to that point, and the stacklet keeps the
36 //! suspended frames as they were. Suspending hands back a handle to the suspended computation, a
37 //! resumption. Resuming the resumption makes the suspending call return the value passed in. One
38 //! form is a resumption that runs once (*one-shot*): it returns control to the point where the
39 //! computation suspended, and the computation continues on the same stacklet with no copy. The
40 //! other form is a resumption that may run more than once (*multi-shot*): it keeps a reference
41 //! count, and the runtime saves the stacklet's segments to the heap and restores them when it needs
42 //! to, so the handle can resume again and again. Duplicating such a handle adds one reference and
43 //! copies no stack memory at that moment. The Zig API keeps ownership explicit: `run` and
44 //! `SuspendedRun` keep the body's result where the caller reads it, and a caller that abandons a
45 //! paused run drops its handle. The Zig API has the compiler check the type of every value that
46 //! crosses between stacks, and error unions pass through unchanged. Stacklet memory is bounded: the
47 //! process takes stacklets from shared pool regions of at most 32,000 blocks each, 256 GiB of
48 //! address space by default, and each thread keeps at most four freed stacklets for reuse by
49 //! default. The stack switch exists for x86_64 and aarch64 targets other than Windows, and the
50 //! package compiles only for 64-bit targets, because every stacklet reserves address space of its
51 //! own.
52 
53 const raw = @import("prompt.zig");
54 
55 pub const effect = @import("effect.zig");
56 pub const zig_api = @import("api.zig");
57 
58 pub const Continuation = zig_api.Continuation;
59 pub const PromptOutcome = zig_api.PromptOutcome;
60 pub const SuspendedPrompt = zig_api.SuspendedPrompt;
61 pub const SuspendedRun = zig_api.SuspendedRun;
62 pub const EffectContinuation = effect.EffectContinuation;
63 pub const EffectDefinition = effect.EffectDefinition;
64 pub const run = zig_api.run;
65 pub const runWithoutContext = zig_api.runWithoutContext;
66 pub const suspendPrompt = zig_api.suspendPrompt;
67 pub const yieldWith = zig_api.yieldWith;
68 pub const operation = effect.operation;
69 pub const on = effect.on;
70 pub const forward = effect.forward;
71 
72 pub const StartFn = raw.StartFn;
73 pub const YieldFn = raw.YieldFn;
74 pub const Config = raw.Config;
75 pub const Prompt = raw.Prompt;
76 pub const Resume = raw.Resume;
77 
78 pub const init = raw.init;
79 pub const configDefault = raw.configDefault;
80 pub const prompt = raw.prompt;
81 pub const promptCreate = raw.promptCreate;
82 pub const promptEnter = raw.promptEnter;
83 pub const promptTop = raw.promptTop;
84 pub const promptParent = raw.promptParent;
85 pub const yieldPrompt = raw.yieldPrompt;
86 pub const resumePrompt = raw.resumePrompt;
87 pub const resumeTailPrompt = raw.resumeTailPrompt;
88 pub const resumeDrop = raw.resumeDrop;
89 pub const resumeMulti = raw.resumeMulti;
90 pub const resumeDup = raw.resumeDup;
91 pub const resumeResumeCount = raw.resumeResumeCount;
92 pub const resumeShouldUnwind = raw.resumeShouldUnwind;
93 pub const captureBacktrace = raw.captureBacktrace;
94 pub const processAllocator = raw.processAllocator;