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.
 53 
 54 :(before "End Mu Types Initialization")
 55 type_ordinal continuation = Type_ordinal["continuation"] = Next_type_ordinal++;
 56 Type[continuation].name = "continuation";
 57 
 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;
 61 
 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;
 68 }
 69 
 70 :(scenario delimited_continuation)
 71 recipe main [
 72   1:continuation <- call-with-continuation-mark 233/mark, f, 77  # 77 is an argument to f
 73   2:number <- copy 5
 74   {
 75     2:number <- call 1:continuation, 2:number  # jump to 'return-continuation-until-mark' below
 76     3:boolean <- greater-or-equal 2:number, 8
 77     break-if 3:boolean
 78     loop
 79   }
 80 ]
 81 recipe f [
 82   11:number <- next-ingredient
 83   12:number <- g 11:number
 84   return 12:number
 85 ]
 86 recipe g [
 87   21:number <- next-ingredient
 88   22:number <- return-continuation-until-mark 233/mark
 89   23:number <- add 22:number, 1
 90   return 23:number
 91 ]
 92 # first call of 'g' executes the part before return-continuation-until-mark
 93 +mem: storing 77 in location 21
 94 +run: {2: "number"} <- copy {5: "literal"}
 95 +mem: storing 5 in location 2
 96 # calls of the continuation execute the part after return-continuation-until-mark
 97 +run: {2: "number"} <- call {1: "continuation"}, {2: "number"}
 98 +mem: storing 5 in location 22
 99 +mem: storing 6 in location 2
100 +run: {2: "number"} <- call {1: "continuation"}, {2: "number"}
101 +mem: storing 6 in location 22
102 +mem: storing 7 in location 2
103 +run: {2: "number"} <- call {1: "continuation"}, {2: "number"}
104 +mem: storing 7 in location 22
105 +mem: storing 8 in location 2
106 # first call of 'g' does not execute the part after return-continuation-until-mark
107 -mem: storing 77 in location 22
108 # calls of the continuation don't execute the part before return-continuation-until-mark
109 -mem: storing 5 in location 21
110 -mem: storing 6 in location 21
111 -mem: storing 7 in location 21
112 # termination
113 -mem: storing 9 in location 2
114 
115 :(before "End call Fields")
116 int continuation_mark_tag;
117 :(before "End call Constructor")
118 continuation_mark_tag = 0;
119 
120 :(before "End Primitive Recipe Declarations")
121 CALL_WITH_CONTINUATION_MARK,
122 :(before "End Primitive Recipe Numbers")
123 Recipe_ordinal["call-with-continuation-mark"] = CALL_WITH_CONTINUATION_MARK;
124 :(before "End Primitive Recipe Checks")
125 case CALL_WITH_CONTINUATION_MARK: {
126   if (SIZE(inst.ingredients) < 2) {
127     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();
128   }
129   break;
130 }
131 :(before "End Primitive Recipe Implementations")
132 case CALL_WITH_CONTINUATION_MARK: {
133   // like call, but mark the current call as a 'base of continuation' call
134   // before pushing the next one on it
135   if (Trace_stream) {
136     ++Trace_stream->callstack_depth;
137     trace("trace") << "delimited continuation; incrementing callstack depth to " << Trace_stream->callstack_depth << end();
138     assert(Trace_stream->callstack_depth < 9000);  // 9998-101 plus cushion
139   }
140   instruction/*copy*/ caller_instruction = current_instruction();
141   Current_routine->calls.front().continuation_mark_tag = current_instruction().ingredients.at(0).value;
142   Current_routine->calls.push_front(call(Recipe_ordinal[current_instruction().ingredients.at(1).name]));
143   // drop the mark
144   caller_instruction.ingredients.erase(caller_instruction.ingredients.begin());
145   ingredients.erase(ingredients.begin());
146   // drop the callee
147   caller_instruction.ingredients.erase(caller_instruction.ingredients.begin());
148   ingredients.erase(ingredients.begin());
149   finish_call_housekeeping(caller_instruction, ingredients);
150   continue;
151 }
152 
153 :(scenario next_ingredient_inside_continuation)
154 recipe main [
155   call-with-continuation-mark 233/mark, f, 1/true
156 ]
157 recipe f [
158   10:bool <- next-input
159 ]
160 +mem: storing 1 in location 10
161 
162 //: save the slice of current call stack until the 'call-with-continuation-mark'
163 //: call, and return it as the result.
164 //: todo: implement delimited continuations in Mu's memory
165 :(before "End Types")
166 struct delimited_continuation {
167   call_stack frames;
168   int nrefs;
169   delimited_continuation(call_stack::iterator begin, call_stack::iterator end) :frames(call_stack(begin, end)), nrefs(0) {}
170 };
171 :(before "End Globals")
172 map<long long int, delimited_continuation> Delimited_continuation;
173 long long int Next_delimited_continuation_id = 1;  // 0 is null just like an address
174 :(before "End Reset")
175 Delimited_continuation.clear();
176 Next_delimited_continuation_id = 1;
177 
178 :(before "End Primitive Recipe Declarations")
179 RETURN_CONTINUATION_UNTIL_MARK,
180 :(before "End Primitive Recipe Numbers")
181 Recipe_ordinal["return-continuation-until-mark"] = RETURN_CONTINUATION_UNTIL_MARK;
182 :(before "End Primitive Recipe Checks")
183 case RETURN_CONTINUATION_UNTIL_MARK: {
184   break;
185 }
186 :(before "End Primitive Recipe Implementations")
187 case RETURN_CONTINUATION_UNTIL_MARK: {
188   // I don't know how to think about next-ingredient in combination with
189   // continuations, so seems cleaner to just kill it. Functions have to read
190   // their inputs before ever returning a continuation.
191   Current_routine->calls.front().ingredient_atoms.clear();
192   Current_routine->calls.front().next_ingredient_to_process = 0;
193   // copy the current call stack until the most recent marked call
194   call_stack::iterator find_base_of_continuation(call_stack&, int);  // manual prototype containing '::'
195   call_stack::iterator base = find_base_of_continuation(Current_routine->calls, /*mark tag*/current_instruction().ingredients.at(0).value);
196   if (base == Current_routine->calls.end()) {
197     raise << maybe(current_recipe_name()) << "couldn't find a 'call-with-continuation-mark' to return to\n" << end();
198     raise << maybe(current_recipe_name()) << "call stack:\n" << end();
199     for (call_stack::iterator p = Current_routine->calls.begin();  p != Current_routine->calls.end();  ++p)
200       raise << maybe(current_recipe_name()) << "  " << get(Recipe, p->running_recipe).name << '\n' << end();
201     break;
202   }
203   trace("run") << "creating continuation " << Next_delimited_continuation_id << end();
204   put(Delimited_continuation, Next_delimited_continuation_id, delimited_continuation(Current_routine->calls.begin(), base));
205   while (Current_routine->calls.begin() != base) {
206     if (Trace_stream) {
207       --Trace_stream->callstack_depth;
208       assert(Trace_stream->callstack_depth >= 0);
209     }
210     Current_routine->calls.pop_front();
211   }
212   // return it as the result of the marked call
213   products.resize(1);
214   products.at(0).push_back(Next_delimited_continuation_id);
215   // return any other ingredients passed in
216   copy(/*skip mark tag*/++ingredients.begin(), ingredients.end(), inserter(products, products.end()));
217   ++Next_delimited_continuation_id;
218   break;  // continue to process rest of marked call
219 }
220 
221 :(code)
222 call_stack::iterator find_base_of_continuation(call_stack& c, int mark_tag) {
223   for (call_stack::iterator p = c.begin(); p != c.end(); ++p)
224     if (p->continuation_mark_tag == mark_tag) return p;
225   return c.end();
226 }
227 
228 //: overload 'call' for continuations
229 :(after "Begin Call")
230 if (is_mu_continuation(current_instruction().ingredients.at(0))) {
231   // copy multiple calls on to current call stack
232   assert(scalar(ingredients.at(0)));
233   trace("run") << "calling continuation " << ingredients.at(0).at(0) << end();
234   if (!contains_key(Delimited_continuation, ingredients.at(0).at(0)))
235     raise << maybe(current_recipe_name()) << "no such delimited continuation " << current_instruction().ingredients.at(0).original_string << '\n' << end();
236   const call_stack& new_frames = get(Delimited_continuation, ingredients.at(0).at(0)).frames;
237   for (call_stack::const_reverse_iterator p = new_frames.rbegin(); p != new_frames.rend(); ++p)
238     Current_routine->calls.push_front(*p);
239   if (Trace_stream) {
240     Trace_stream->callstack_depth += SIZE(new_frames);
241     trace("trace") << "calling delimited continuation; growing callstack depth to " << Trace_stream->callstack_depth << end();
242     assert(Trace_stream->callstack_depth < 9000);  // 9998-101 plus cushion
243   }
244   // no call housekeeping; continuations don't support next-ingredient
245   copy(/*drop continuation*/++ingredients.begin(), ingredients.end(), inserter(products, products.begin()));
246   break;  // record results of resuming 'return-continuation-until-mark' instruction
247 }
248 
249 :(scenario continuations_can_return_values)
250 def main [
251   local-scope
252   k:continuation, 1:num/raw <- call-with-continuation-mark 233/mark, f
253 ]
254 def f [
255   local-scope
256   g
257 ]
258 def g [
259   local-scope
260   return-continuation-until-mark 233/mark, 34
261   stash [continuation called]
262 ]
263 +mem: storing 34 in location 1
264 
265 :(scenario continuations_continue_to_matching_mark)
266 def main [
267   local-scope
268   k:continuation, 1:num/raw <- call-with-continuation-mark 233/mark, f
269   add 1, 1
270 ]
271 def f [
272   local-scope
273   k2:continuation <- call-with-continuation-mark 234/mark, g
274   add 2, 2
275 ]
276 def g [
277   local-scope
278   return-continuation-until-mark 233/mark, 34
279   stash [continuation called]
280 ]
281 +run: add {1: "literal"}, {1: "literal"}
282 -run: add {2: "literal"}, {2: "literal"}
283 
284 //: Allow shape-shifting recipes to return continuations.
285 
286 :(scenario call_shape_shifting_recipe_with_continuation_mark)
287 def main [
288   1:num <- call-with-continuation-mark 233/mark, f, 34
289 ]
290 def f x:_elem -> y:_elem [
291   local-scope
292   load-ingredients
293   y <- copy x
294 ]
295 +mem: storing 34 in location 1
296 
297 :(before "End resolve_ambiguous_call(r, index, inst, caller_recipe) Special-cases")
298 if (inst.name == "call-with-continuation-mark") {
299   if (SIZE(inst.ingredients) > 1 && is_recipe_literal(inst.ingredients.at(/*skip mark*/1))) {
300   resolve_indirect_continuation_call(r, index, inst, caller_recipe);
301   return;
302   }
303 }
304 :(code)
305 void resolve_indirect_continuation_call(const recipe_ordinal r, int index, instruction& inst, const recipe& caller_recipe) {
306   instruction inst2;
307   inst2.name = inst.ingredients.at(/*skip mark*/1).name;
308   for (int i = /*skip mark and recipe*/2;  i < SIZE(inst.ingredients);  ++i)
309     inst2.ingredients.push_back(inst.ingredients.at(i));
310   for (int i = /*skip continuation*/1;  i < SIZE(inst.products);  ++i)
311     inst2.products.push_back(inst.products.at(i));
312   resolve_ambiguous_call(r, index, inst2, caller_recipe);
313   inst.ingredients.at(/*skip mark*/1).name = inst2.name;
314   inst.ingredients.at(/*skip mark*/1).set_value(get(Recipe_ordinal, inst2.name));
315 }
316 
317 :(scenario call_shape_shifting_recipe_with_continuation_mark_and_no_outputs)
318 def main [
319   1:continuation <- call-with-continuation-mark 233/mark, f, 34
320 ]
321 def f x:_elem [
322   local-scope
323   load-ingredients
324   return-continuation-until-mark 233/mark
325 ]
326 $error: 0
327 
328 :(scenario continuation1)
329 def main [
330   local-scope
331   k:continuation <- call-with-continuation-mark 233/mark, create-yielder
332   10:num/raw <- call k
333 ]
334 def create-yielder -> n:num [
335   local-scope
336   load-inputs
337   return-continuation-until-mark 233/mark
338   return 1
339 ]
340 +mem: storing 1 in location 10
341 $error: 0
342 
343 :(code)
344 bool is_mu_continuation(reagent/*copy*/ x) {
345   canonize_type(x);
346   return x.type && x.type->atom && x.type->value == get(Type_ordinal, "continuation");
347 }
348 
349 // helper for debugging
350 void dump(const int continuation_id) {
351   if (!contains_key(Delimited_continuation, continuation_id)) {
352     raise << "missing delimited continuation: " << continuation_id << '\n' << end();
353     return;
354   }
355   delimited_continuation& curr = get(Delimited_continuation, continuation_id);
356   dump(curr.frames);
357 }