fix other mandelbrot variants
[mu.git] / archive / 1.vm / 076continuation.cc
blob670fef2fef6980e639ef5a99e9794b307ec5b1a5
1 //: Continuations are a powerful primitive for constructing advanced kinds of
2 //: control *policies* like back-tracking.
3 //:
4 //: In Mu, continuations are first-class and delimited, and are constructed
5 //: out of two primitives:
6 //:
7 //: * 'call-with-continuation-mark' marks the top of the call stack and then
8 //: calls the provided recipe.
9 //: * 'return-continuation-until-mark' copies the top of the stack
10 //: until the mark, and returns it as the result of
11 //: 'call-with-continuation-mark' (which might be a distant ancestor on the
12 //: call stack; intervening calls don't return)
13 //:
14 //: The resulting slice of the stack can now be called just like a regular
15 //: recipe.
16 //:
17 //: See the example programs continuation*.mu to get a sense for the
18 //: possibilities.
19 //:
20 //: Refinements:
21 //: * You can call a single continuation multiple times, and it will preserve
22 //: the state of its local variables at each stack frame between calls.
23 //: The stack frames of a continuation are not destroyed until the
24 //: continuation goes out of scope. See continuation2.mu.
25 //: * 'return-continuation-until-mark' doesn't consume the mark, so you can
26 //: return multiple continuations based on a single mark. In combination
27 //: with the fact that 'return-continuation-until-mark' can return from
28 //: regular calls, just as long as there was an earlier call to
29 //: 'call-with-continuation-mark', this gives us a way to create resumable
30 //: recipes. See continuation3.mu.
31 //: * 'return-continuation-until-mark' can take ingredients to return just
32 //: like other 'return' instructions. It just implicitly also returns a
33 //: continuation as the first result. See continuation4.mu.
34 //: * Conversely, you can pass ingredients to a continuation when calling it,
35 //: to make it available to products of 'return-continuation-until-mark'.
36 //: See continuation5.mu.
37 //: * There can be multiple continuation marks on the stack at once;
38 //: 'call-with-continuation-mark' and 'return-continuation-until-mark' both
39 //: need to pass in a tag to coordinate on the correct mark. This allows us
40 //: to save multiple continuations for different purposes (say if one is
41 //: for exceptions) with overlapping stack frames. See exception.mu.
42 //:
43 //: Inspired by James and Sabry, "Yield: Mainstream delimited continuations",
44 //: Workshop on the Theory and Practice of Delimited Continuations, 2011.
45 //: https://www.cs.indiana.edu/~sabry/papers/yield.pdf
46 //:
47 //: Caveats:
48 //: * At the moment we can't statically type-check continuations. So we raise
49 //: runtime errors for a call that doesn't return a continuation when the
50 //: caller expects, or one that returns a continuation when the caller
51 //: doesn't expect it. This shouldn't cause memory corruption, though.
52 //: There should still be no way to lookup addresses that aren't allocated.
54 :(before "End Mu Types Initialization")
55 type_ordinal continuation = Type_ordinal["continuation"] = Next_type_ordinal++;
56 Type[continuation].name = "continuation";
58 //: A continuation can be called like a recipe.
59 :(before "End is_mu_recipe Atom Cases(r)")
60 if (r.type->name == "continuation") return true;
62 //: However, it can't be type-checked like most recipes. Pretend it's like a
63 //: header-less recipe.
64 :(after "Begin Reagent->Recipe(r, recipe_header)")
65 if (r.type->atom && r.type->name == "continuation") {
66 result_header.has_header = false;
67 return result_header;
70 :(code)
71 void test_delimited_continuation() {
72 run(
73 "recipe main [\n"
74 " 1:continuation <- call-with-continuation-mark 233/mark, f, 77\n" // 77 is an argument to f
75 " 2:num <- copy 5\n"
76 " {\n"
77 " 2:num <- call 1:continuation, 2:num\n" // jump to 'return-continuation-until-mark' below
78 " 3:bool <- greater-or-equal 2:num, 8\n"
79 " break-if 3:bool\n"
80 " loop\n"
81 " }\n"
82 "]\n"
83 "recipe f [\n"
84 " 11:num <- next-ingredient\n"
85 " 12:num <- g 11:num\n"
86 " return 12:num\n"
87 "]\n"
88 "recipe g [\n"
89 " 21:num <- next-ingredient\n"
90 " 22:num <- return-continuation-until-mark 233/mark\n"
91 " 23:num <- add 22:num, 1\n"
92 " return 23:num\n"
93 "]\n"
95 // first call of 'g' executes the part before return-continuation-until-mark
96 CHECK_TRACE_CONTENTS(
97 // first call of 'g' executes the part before return-continuation-until-mark
98 "mem: storing 77 in location 21\n"
99 "run: {2: \"number\"} <- copy {5: \"literal\"}\n"
100 "mem: storing 5 in location 2\n"
101 // calls of the continuation execute the part after return-continuation-until-mark
102 "run: {2: \"number\"} <- call {1: \"continuation\"}, {2: \"number\"}\n"
103 "mem: storing 5 in location 22\n"
104 "mem: storing 6 in location 2\n"
105 "run: {2: \"number\"} <- call {1: \"continuation\"}, {2: \"number\"}\n"
106 "mem: storing 6 in location 22\n"
107 "mem: storing 7 in location 2\n"
108 "run: {2: \"number\"} <- call {1: \"continuation\"}, {2: \"number\"}\n"
109 "mem: storing 7 in location 22\n"
110 "mem: storing 8 in location 2\n"
112 // first call of 'g' does not execute the part after return-continuation-until-mark
113 CHECK_TRACE_DOESNT_CONTAIN("mem: storing 77 in location 22");
114 // calls of the continuation don't execute the part before return-continuation-until-mark
115 CHECK_TRACE_DOESNT_CONTAIN("mem: storing 5 in location 21");
116 CHECK_TRACE_DOESNT_CONTAIN("mem: storing 6 in location 21");
117 CHECK_TRACE_DOESNT_CONTAIN("mem: storing 7 in location 21");
118 // termination
119 CHECK_TRACE_DOESNT_CONTAIN("mem: storing 9 in location 2");
122 :(before "End call Fields")
123 int continuation_mark_tag;
124 :(before "End call Constructor")
125 continuation_mark_tag = 0;
127 :(before "End Primitive Recipe Declarations")
128 CALL_WITH_CONTINUATION_MARK,
129 :(before "End Primitive Recipe Numbers")
130 Recipe_ordinal["call-with-continuation-mark"] = CALL_WITH_CONTINUATION_MARK;
131 :(before "End Primitive Recipe Checks")
132 case CALL_WITH_CONTINUATION_MARK: {
133 if (SIZE(inst.ingredients) < 2) {
134 raise << maybe(get(Recipe, r).name) << "'" << to_original_string(inst) << "' requires at least two ingredients: a mark number and a recipe to call\n" << end();
136 break;
138 :(before "End Primitive Recipe Implementations")
139 case CALL_WITH_CONTINUATION_MARK: {
140 // like call, but mark the current call as a 'base of continuation' call
141 // before pushing the next one on it
142 trace(Callstack_depth+1, "trace") << "delimited continuation; incrementing callstack depth to " << Callstack_depth << end();
143 ++Callstack_depth;
144 assert(Callstack_depth < Max_depth);
145 instruction/*copy*/ caller_instruction = current_instruction();
146 Current_routine->calls.front().continuation_mark_tag = current_instruction().ingredients.at(0).value;
147 Current_routine->calls.push_front(call(ingredients.at(1).at(0)));
148 // drop the mark
149 caller_instruction.ingredients.erase(caller_instruction.ingredients.begin());
150 ingredients.erase(ingredients.begin());
151 // drop the callee
152 caller_instruction.ingredients.erase(caller_instruction.ingredients.begin());
153 ingredients.erase(ingredients.begin());
154 finish_call_housekeeping(caller_instruction, ingredients);
155 continue;
158 :(code)
159 void test_next_ingredient_inside_continuation() {
160 run(
161 "recipe main [\n"
162 " call-with-continuation-mark 233/mark, f, true\n"
163 "]\n"
164 "recipe f [\n"
165 " 10:bool <- next-input\n"
166 "]\n"
168 CHECK_TRACE_CONTENTS(
169 "mem: storing 1 in location 10\n"
173 void test_delimited_continuation_out_of_recipe_variable() {
174 run(
175 "recipe main [\n"
176 " x:recipe <- copy f\n"
177 " call-with-continuation-mark 233/mark, x, true\n"
178 "]\n"
179 "recipe f [\n"
180 " 10:bool <- next-input\n"
181 "]\n"
183 CHECK_TRACE_CONTENTS(
184 "mem: storing 1 in location 10\n"
188 //: save the slice of current call stack until the 'call-with-continuation-mark'
189 //: call, and return it as the result.
190 //: todo: implement delimited continuations in Mu's memory
191 :(before "End Types")
192 struct delimited_continuation {
193 call_stack frames;
194 int nrefs;
195 delimited_continuation(call_stack::iterator begin, call_stack::iterator end) :frames(call_stack(begin, end)), nrefs(0) {}
197 :(before "End Globals")
198 map<long long int, delimited_continuation> Delimited_continuation;
199 long long int Next_delimited_continuation_id = 1; // 0 is null just like an address
200 :(before "End Reset")
201 Delimited_continuation.clear();
202 Next_delimited_continuation_id = 1;
204 :(before "End Primitive Recipe Declarations")
205 RETURN_CONTINUATION_UNTIL_MARK,
206 :(before "End Primitive Recipe Numbers")
207 Recipe_ordinal["return-continuation-until-mark"] = RETURN_CONTINUATION_UNTIL_MARK;
208 :(before "End Primitive Recipe Checks")
209 case RETURN_CONTINUATION_UNTIL_MARK: {
210 if (inst.ingredients.empty()) {
211 raise << maybe(get(Recipe, r).name) << "'" << to_original_string(inst) << "' requires at least one ingredient: a mark tag (number)\n" << end();
213 break;
215 :(before "End Primitive Recipe Implementations")
216 case RETURN_CONTINUATION_UNTIL_MARK: {
217 // I don't know how to think about next-ingredient in combination with
218 // continuations, so seems cleaner to just kill it. Functions have to read
219 // their inputs before ever returning a continuation.
220 Current_routine->calls.front().ingredient_atoms.clear();
221 Current_routine->calls.front().next_ingredient_to_process = 0;
222 // copy the current call stack until the most recent marked call
223 call_stack::iterator find_base_of_continuation(call_stack&, int); // manual prototype containing '::'
224 call_stack::iterator base = find_base_of_continuation(Current_routine->calls, /*mark tag*/current_instruction().ingredients.at(0).value);
225 if (base == Current_routine->calls.end()) {
226 raise << maybe(current_recipe_name()) << "couldn't find a 'call-with-continuation-mark' to return to with tag " << current_instruction().ingredients.at(0).original_string << '\n' << end();
227 raise << maybe(current_recipe_name()) << "call stack:\n" << end();
228 for (call_stack::iterator p = Current_routine->calls.begin(); p != Current_routine->calls.end(); ++p)
229 raise << maybe(current_recipe_name()) << " " << get(Recipe, p->running_recipe).name << '\n' << end();
230 break;
232 trace(Callstack_depth+1, "run") << "creating continuation " << Next_delimited_continuation_id << end();
233 put(Delimited_continuation, Next_delimited_continuation_id, delimited_continuation(Current_routine->calls.begin(), base));
234 while (Current_routine->calls.begin() != base) {
235 --Callstack_depth;
236 assert(Callstack_depth >= 0);
237 Current_routine->calls.pop_front();
239 // return it as the result of the marked call
240 products.resize(1);
241 products.at(0).push_back(Next_delimited_continuation_id);
242 // return any other ingredients passed in
243 copy(/*skip mark tag*/++ingredients.begin(), ingredients.end(), inserter(products, products.end()));
244 ++Next_delimited_continuation_id;
245 break; // continue to process rest of marked call
248 :(code)
249 call_stack::iterator find_base_of_continuation(call_stack& c, int mark_tag) {
250 for (call_stack::iterator p = c.begin(); p != c.end(); ++p)
251 if (p->continuation_mark_tag == mark_tag) return p;
252 return c.end();
255 //: overload 'call' for continuations
256 :(after "Begin Call")
257 if (is_mu_continuation(current_instruction().ingredients.at(0))) {
258 // copy multiple calls on to current call stack
259 assert(scalar(ingredients.at(0)));
260 trace(Callstack_depth+1, "run") << "calling continuation " << ingredients.at(0).at(0) << end();
261 if (!contains_key(Delimited_continuation, ingredients.at(0).at(0)))
262 raise << maybe(current_recipe_name()) << "no such delimited continuation " << current_instruction().ingredients.at(0).original_string << '\n' << end();
263 const call_stack& new_frames = get(Delimited_continuation, ingredients.at(0).at(0)).frames;
264 for (call_stack::const_reverse_iterator p = new_frames.rbegin(); p != new_frames.rend(); ++p)
265 Current_routine->calls.push_front(*p);
266 trace(Callstack_depth+1, "trace") << "calling delimited continuation; growing callstack depth to " << Callstack_depth+SIZE(new_frames) << end();
267 Callstack_depth += SIZE(new_frames);
268 assert(Callstack_depth < Max_depth);
269 // no call housekeeping; continuations don't support next-ingredient
270 copy(/*drop continuation*/++ingredients.begin(), ingredients.end(), inserter(products, products.begin()));
271 break; // record results of resuming 'return-continuation-until-mark' instruction
274 :(code)
275 void test_continuations_can_return_values() {
276 run(
277 "def main [\n"
278 " local-scope\n"
279 " k:continuation, 1:num/raw <- call-with-continuation-mark 233/mark, f\n"
280 "]\n"
281 "def f [\n"
282 " local-scope\n"
283 " g\n"
284 "]\n"
285 "def g [\n"
286 " local-scope\n"
287 " return-continuation-until-mark 233/mark, 34\n"
288 " stash [continuation called]\n"
289 "]\n"
291 CHECK_TRACE_CONTENTS(
292 "mem: storing 34 in location 1\n"
296 void test_continuations_continue_to_matching_mark() {
297 run(
298 "def main [\n"
299 " local-scope\n"
300 " k:continuation, 1:num/raw <- call-with-continuation-mark 233/mark, f\n"
301 " add 1, 1\n"
302 "]\n"
303 "def f [\n"
304 " local-scope\n"
305 " k2:continuation <- call-with-continuation-mark 234/mark, g\n"
306 " add 2, 2\n"
307 "]\n"
308 "def g [\n"
309 " local-scope\n"
310 " return-continuation-until-mark 233/mark, 34\n"
311 " stash [continuation called]\n"
312 "]\n"
314 CHECK_TRACE_CONTENTS(
315 "run: add {1: \"literal\"}, {1: \"literal\"}\n"
317 CHECK_TRACE_DOESNT_CONTAIN("run: add {2: \"literal\"}, {2: \"literal\"}");
320 //: Allow shape-shifting recipes to return continuations.
322 void test_call_shape_shifting_recipe_with_continuation_mark() {
323 run(
324 "def main [\n"
325 " 1:num <- call-with-continuation-mark 233/mark, f, 34\n"
326 "]\n"
327 "def f x:_elem -> y:_elem [\n"
328 " local-scope\n"
329 " load-ingredients\n"
330 " y <- copy x\n"
331 "]\n"
333 CHECK_TRACE_CONTENTS(
334 "mem: storing 34 in location 1\n"
338 :(before "End resolve_ambiguous_call(r, index, inst, caller_recipe) Special-cases")
339 if (inst.name == "call-with-continuation-mark") {
340 if (SIZE(inst.ingredients) > 1 && is_recipe_literal(inst.ingredients.at(/*skip mark*/1))) {
341 resolve_indirect_continuation_call(r, index, inst, caller_recipe);
342 return;
345 :(code)
346 void resolve_indirect_continuation_call(const recipe_ordinal r, int index, instruction& inst, const recipe& caller_recipe) {
347 instruction inst2;
348 inst2.name = inst.ingredients.at(/*skip mark*/1).name;
349 for (int i = /*skip mark and recipe*/2; i < SIZE(inst.ingredients); ++i)
350 inst2.ingredients.push_back(inst.ingredients.at(i));
351 for (int i = /*skip continuation*/1; i < SIZE(inst.products); ++i)
352 inst2.products.push_back(inst.products.at(i));
353 resolve_ambiguous_call(r, index, inst2, caller_recipe);
354 inst.ingredients.at(/*skip mark*/1).name = inst2.name;
355 inst.ingredients.at(/*skip mark*/1).set_value(get(Recipe_ordinal, inst2.name));
358 void test_call_shape_shifting_recipe_with_continuation_mark_and_no_outputs() {
359 run(
360 "def main [\n"
361 " 1:continuation <- call-with-continuation-mark 233/mark, f, 34\n"
362 "]\n"
363 "def f x:_elem [\n"
364 " local-scope\n"
365 " load-ingredients\n"
366 " return-continuation-until-mark 233/mark\n"
367 "]\n"
369 CHECK_TRACE_COUNT("error", 0);
372 void test_continuation1() {
373 run(
374 "def main [\n"
375 " local-scope\n"
376 " k:continuation <- call-with-continuation-mark 233/mark, create-yielder\n"
377 " 10:num/raw <- call k\n"
378 "]\n"
379 "def create-yielder -> n:num [\n"
380 " local-scope\n"
381 " load-inputs\n"
382 " return-continuation-until-mark 233/mark\n"
383 " return 1\n"
384 "]\n"
386 CHECK_TRACE_CONTENTS(
387 "mem: storing 1 in location 10\n"
389 CHECK_TRACE_COUNT("error", 0);
392 :(code)
393 bool is_mu_continuation(reagent/*copy*/ x) {
394 canonize_type(x);
395 return x.type && x.type->atom && x.type->value == get(Type_ordinal, "continuation");
398 // helper for debugging
399 void dump(const int continuation_id) {
400 if (!contains_key(Delimited_continuation, continuation_id)) {
401 raise << "missing delimited continuation: " << continuation_id << '\n' << end();
402 return;
404 delimited_continuation& curr = get(Delimited_continuation, continuation_id);
405 dump(curr.frames);