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 //:
 38 //: Inspired by James and Sabry, "Yield: Mainstream delimited continuations",
 39 //: Workshop on the Theory and Practice of Delimited Continuations, 2011.
 40 //: https://www.cs.indiana.edu/~sabry/papers/yield.pdf
 41 //:
 42 //: Caveats:
 43 //:  * At the moment we can't statically type-check continuations. So we raise
 44 //:    runtime errors for a call that doesn't return a continuation when the
 45 //:    caller expects, or one that returns a continuation when the caller
 46 //:    doesn't expect it. This shouldn't cause memory corruption, though.
 47 //:    There should still be no way to lookup addresses that aren't allocated.
 48 
 49 :(before "End Mu Types Initialization")
 50 type_ordinal continuation = Type_ordinal["continuation"] = Next_type_ordinal++;
 51 Type[continuation].name = "continuation";
 52 
 53 //: A continuation can be called like a recipe.
 54 :(before "End is_mu_recipe Atom Cases(r)")
 55 if (r.type->name == "continuation") return true;
 56 
 57 //: However, it can't be type-checked like most recipes. Pretend it's like a
 58 //: header-less recipe.
 59 :(after "Begin Reagent->Recipe(r, recipe_header)")
 60 if (r.type->atom && r.type->name == "continuation") {
 61   result_header.has_header = false;
 62   return result_header;
 63 }
 64 
 65 :(scenario delimited_continuation)
 66 recipe main [
 67   1:continuation <- call-with-continuation-mark f, 77  # 77 is an argument to f
 68   2:number <- copy 5
 69   {
 70   ¦ 2:number <- call 1:continuation, 2:number  # jump to 'return-continuation-until-mark' below
 71   ¦ 3:boolean <- greater-or-equal 2:number, 8
 72   ¦ break-if 3:boolean
 73   ¦ loop
 74   }
 75 ]
 76 recipe f [
 77   11:number <- next-ingredient
 78   12:number <- g 11:number
 79   return 12:number
 80 ]
 81 recipe g [
 82   21:number <- next-ingredient
 83   22:number <- return-continuation-until-mark
 84   23:number <- add 22:number, 1
 85   return 23:number
 86 ]
 87 # first call of 'g' executes the part before return-continuation-until-mark
 88 +mem: storing 77 in location 21
 89 +run: {2: "number"} <- copy {5: "literal"}
 90 +mem: storing 5 in location 2
 91 # calls of the continuation execute the part after return-continuation-until-mark
 92 +run: {2: "number"} <- call {1: "continuation"}, {2: "number"}
 93 +mem: storing 5 in location 22
 94 +mem: storing 6 in location 2
 95 +run: {2: "number"} <- call {1: "continuation"}, {2: "number"}
 96 +mem: storing 6 in location 22
 97 +mem: storing 7 in location 2
 98 +run: {2: "number"} <- call {1: "continuation"}, {2: "number"}
 99 +mem: storing 7 in location 22
100 +mem: storing 8 in location 2
101 # first call of 'g' does not execute the part after return-continuation-until-mark
102 -mem: storing 77 in location 22
103 # calls of the continuation don't execute the part before return-continuation-until-mark
104 -mem: storing 5 in location 21
105 -mem: storing 6 in location 21
106 -mem: storing 7 in location 21
107 # termination
108 -mem: storing 9 in location 2
109 
110 :(before "End call Fields")
111 bool is_base_of_continuation;
112 :(before "End call Constructor")
113 is_base_of_continuation = false;
114 
115 :(before "End Primitive Recipe Declarations")
116 CALL_WITH_CONTINUATION_MARK,
117 :(before "End Primitive Recipe Numbers")
118 Recipe_ordinal["call-with-continuation-mark"] = CALL_WITH_CONTINUATION_MARK;
119 :(before "End Primitive Recipe Checks")
120 case CALL_WITH_CONTINUATION_MARK: {
121   break;
122 }
123 :(before "End Primitive Recipe Implementations")
124 case CALL_WITH_CONTINUATION_MARK: {
125   // like call, but mark the current call as a 'base of continuation' call
126   // before pushing the next one on it
127   if (Trace_stream) {
128   ¦ ++Trace_stream->callstack_depth;
129   ¦ trace("trace") << "delimited continuation; incrementing callstack depth to " << Trace_stream->callstack_depth << end();
130   ¦ assert(Trace_stream->callstack_depth < 9000);  // 9998-101 plus cushion
131   }
132   const instruction& caller_instruction = current_instruction();
133   Current_routine->calls.front().is_base_of_continuation = true;
134   Current_routine->calls.push_front(call(Recipe_ordinal[current_instruction().ingredients.at(0).name]));
135   ingredients.erase(ingredients.begin());  // drop the callee
136   finish_call_housekeeping(caller_instruction, ingredients);
137   continue;
138 }
139 
140 //: save the slice of current call stack until the 'call-with-continuation-mark'
141 //: call, and return it as the result.
142 //: todo: implement delimited continuations in Mu's memory
143 :(before "End Types")
144 struct delimited_continuation {
145   call_stack frames;
146   int nrefs;
147   delimited_continuation(call_stack::iterator begin, call_stack::iterator end) :frames(call_stack(begin, end)), nrefs(0) {}
148 };
149 :(before "End Globals")
150 map<long long int, delimited_continuation> Delimited_continuation;
151 long long int Next_delimited_continuation_id = 1;  // 0 is null just like an address
152 :(before "End Reset")
153 Delimited_continuation.clear();
154 Next_delimited_continuation_id = 1;
155 
156 :(before "End Primitive Recipe Declarations")
157 RETURN_CONTINUATION_UNTIL_MARK,
158 :(before "End Primitive Recipe Numbers")
159 Recipe_ordinal["return-continuation-until-mark"] = RETURN_CONTINUATION_UNTIL_MARK;
160 :(before "End Primitive Recipe Checks")
161 case RETURN_CONTINUATION_UNTIL_MARK: {
162   break;
163 }
164 :(before "End Primitive Recipe Implementations")
165 case RETURN_CONTINUATION_UNTIL_MARK: {
166   // I don't know how to think about next-ingredient in combination with
167   // continuations, so seems cleaner to just kill it. Functions have to read
168   // their inputs before ever returning a continuation.
169   Current_routine->calls.front().ingredient_atoms.clear();
170   Current_routine->calls.front().next_ingredient_to_process = 0;
171   // copy the current call stack until the most recent marked call
172   call_stack::iterator find_base_of_continuation(call_stack& c);  // manual prototype containing '::'
173   call_stack::iterator base = find_base_of_continuation(Current_routine->calls);
174   if (base == Current_routine->calls.end()) {
175   ¦ raise << maybe(current_recipe_name()) << "couldn't find a 'call-with-continuation-mark' to return to\n" << end();
176   ¦ raise << maybe(current_recipe_name()) << "call stack:\n" << end();
177   ¦ for (call_stack::iterator p = Current_routine->calls.begin();  p != Current_routine->calls.end();  ++p)
178   ¦ ¦ raise << maybe(current_recipe_name()) << "  " << get(Recipe, p->running_recipe).name << '\n' << end();
179   ¦ break;
180   }
181   trace("run") << "creating continuation " << Next_delimited_continuation_id << end();
182   put(Delimited_continuation, Next_delimited_continuation_id, delimited_continuation(Current_routine->calls.begin(), base));
183   while (Current_routine->calls.begin() != base) {
184   ¦ if (Trace_stream) {
185   ¦ ¦ --Trace_stream->callstack_depth;
186   ¦ ¦ assert(Trace_stream->callstack_depth >= 0);
187   ¦ }
188   ¦ Current_routine->calls.pop_front();
189   }
190   // return it as the result of the marked call
191   products.resize(1);
192   products.at(0).push_back(Next_delimited_continuation_id);
193   // return any other ingredients passed in
194   copy(ingredients.begin(), ingredients.end(), inserter(products, products.end()));
195   ++Next_delimited_continuation_id;
196   break;  // continue to process rest of marked call
197 }
198 
199 :(code)
200 call_stack::iterator find_base_of_continuation(call_stack& c) {
201   for (call_stack::iterator p = c.begin(); p != c.end(); ++p)
202   ¦ if (p->is_base_of_continuation) return p;
203   return c.end();
204 }
205 
206 //: overload 'call' for continuations
207 :(after "Begin Call")
208 if (is_mu_continuation(current_instruction().ingredients.at(0))) {
209   // copy multiple calls on to current call stack
210   assert(scalar(ingredients.at(0)));
211   trace("run") << "calling continuation " << ingredients.at(0).at(0) << end();
212   if (!contains_key(Delimited_continuation, ingredients.at(0).at(0)))
213   ¦ raise << maybe(current_recipe_name()) << "no such delimited continuation " << current_instruction().ingredients.at(0).original_string << '\n' << end();
214   const call_stack& new_frames = get(Delimited_continuation, ingredients.at(0).at(0)).frames;
215   for (call_stack::const_reverse_iterator p = new_frames.rbegin(); p != new_frames.rend(); ++p) {
216   ¦ Current_routine->calls.push_front(*p);
217   ¦ // ensure that the presence of a continuation keeps its stack frames from being reclaimed
218   ¦ increment_refcount(Current_routine->calls.front().default_space);
219   }
220   if (Trace_stream) {
221   ¦ Trace_stream->callstack_depth += SIZE(new_frames);
222   ¦ trace("trace") << "calling delimited continuation; growing callstack depth to " << Trace_stream->callstack_depth << end();
223   ¦ assert(Trace_stream->callstack_depth < 9000);  // 9998-101 plus cushion
224   }
225   // no call housekeeping; continuations don't support next-ingredient
226   copy(/*drop continuation*/++ingredients.begin(), ingredients.end(), inserter(products, products.begin()));
227   break;  // record results of resuming 'return-continuation-until-mark' instruction
228 }
229 
230 :(scenario continuations_can_return_values)
231 def main [
232   local-scope
233   k:continuation, 1:num/raw <- call-with-continuation-mark f
234 ]
235 def f [
236   local-scope
237   g
238 ]
239 def g [
240   local-scope
241   return-continuation-until-mark 34
242   stash [continuation called]
243 ]
244 # entering main
245 +mem: new alloc: 1000
246 +run: {k: "continuation"}, {1: "number", "raw": ()} <- call-with-continuation-mark {f: "recipe-literal"}
247 # entering f
248 +mem: new alloc: 1004
249 # entering g
250 +mem: new alloc: 1007
251 # return control to main
252 +run: return-continuation-until-mark {34: "literal"}
253 # no allocs abandoned yet
254 +mem: storing 34 in location 1
255 # end of main
256 # make sure no memory leaks..
257 +mem: trying to reclaim local k:continuation
258 +mem: automatically abandoning 1007
259 +mem: automatically abandoning 1004
260 +mem: automatically abandoning 1000
261 # ..even though we never called the continuation
262 -app: continuation called
263 
264 //: Allow shape-shifting recipes to return continuations.
265 
266 :(scenario call_shape_shifting_recipe_with_continuation_mark)
267 def main [
268   1:num <- call-with-continuation-mark f, 34
269 ]
270 def f x:_elem -> y:_elem [
271   local-scope
272   load-ingredients
273   y <- copy x
274 ]
275 +mem: storing 34 in location 1
276 
277 :(before "End resolve_ambiguous_call(r, index, inst, caller_recipe) Special-cases")
278 if (inst.name == "call-with-continuation-mark" && first_ingredient_is_recipe_literal(inst)) {
279   resolve_indirect_ambiguous_call(r, index, inst, caller_recipe);
280   return;
281 }
282 
283 :(scenario call_shape_shifting_recipe_with_continuation_mark_and_no_outputs)
284 def main [
285   1:continuation <- call-with-continuation-mark f, 34
286 ]
287 def f x:_elem [
288   local-scope
289   load-ingredients
290   return-continuation-until-mark
291 ]
292 $error: 0
293 
294 //: Ensure that the presence of a continuation keeps its stack frames from being reclaimed.
295 
296 :(scenario continuations_preserve_local_scopes)
297 def main [
298   local-scope
299   k:continuation <- call-with-continuation-mark f
300   call k
301   return 34
302 ]
303 def f [
304   local-scope
305   g
306 ]
307 def g [
308   local-scope
309   return-continuation-until-mark
310   add 1, 1
311 ]
312 # entering main
313 +mem: new alloc: 1000
314 +run: {k: "continuation"} <- call-with-continuation-mark {f: "recipe-literal"}
315 # entering f
316 +mem: new alloc: 1004
317 # entering g
318 +mem: new alloc: 1007
319 # return control to main
320 +run: return-continuation-until-mark
321 # no allocs abandoned yet
322 # finish running main
323 +run: call {k: "continuation"}
324 +run: add {1: "literal"}, {1: "literal"}
325 +run: return {34: "literal"}
326 # now k is reclaimed
327 +mem: trying to reclaim local k:continuation
328 # at this point all allocs in the continuation are abandoned
329 +mem: automatically abandoning 1007
330 +mem: automatically abandoning 1004
331 # finally the alloc for main is abandoned
332 +mem: automatically abandoning 1000
333 
334 :(before "End Increment Refcounts(canonized_x)")
335 if (is_mu_continuation(canonized_x)) {
336   int continuation_id = data.at(0);
337   if (continuation_id == 0) return;
338   if (!contains_key(Delimited_continuation, continuation_id)) {
339   ¦ raise << maybe(current_recipe_name()) << "missing delimited continuation: " << canonized_x.name << '\n';
340   ¦ return;
341   }
342   delimited_continuation& curr = get(Delimited_continuation, continuation_id);
343   trace("run") << "incrementing refcount of continuation " << continuation_id << ": " << curr.nrefs << " -> " << 1+curr.nrefs << end();
344   ++curr.nrefs;
345   return;
346 }
347 
348 :(before "End Decrement Refcounts(canonized_x)")
349 if (is_mu_continuation(canonized_x)) {
350   int continuation_id = get_or_insert(Memory, canonized_x.value);
351   if (continuation_id == 0) return;
352   delimited_continuation& curr = get(Delimited_continuation, continuation_id);
353   assert(curr.nrefs > 0);
354   --curr.nrefs;
355   trace("run") << "decrementing refcount of continuation " << continuation_id << ": " << 1+curr.nrefs << " -> " << curr.nrefs << end();
356   if (curr.nrefs > 0) return;
357   trace("run") << "reclaiming continuation " << continuation_id << end();
358   // temporarily push the stack frames for the continuation to the call stack before reclaiming their spaces
359   // (because reclaim_default_space() relies on the default-space being reclaimed being at the top of the stack)
360   for (call_stack::const_iterator p = curr.frames.begin(); p != curr.frames.end(); ++p) {
361   ¦ Current_routine->calls.push_front(*p);
362   ¦ reclaim_default_space();
363   ¦ Current_routine->calls.pop_front();
364   }
365   Delimited_continuation.erase(continuation_id);
366   return;
367 }
368 
369 :(scenario continuations_can_be_copied)
370 def main [
371   local-scope
372   k:continuation <- call-with-continuation-mark f
373   k2:continuation <- copy k
374   # reclaiming k and k2 shouldn't delete f's local scope twice
375 ]
376 def f [
377   local-scope
378   load-ingredients
379   return-continuation-until-mark
380   return 0
381 ]
382 $error: 0
383 
384 :(code)
385 bool is_mu_continuation(reagent/*copy*/ x) {
386   canonize_type(x);
387   return x.type && x.type->atom && x.type->value == get(Type_ordinal, "continuation");
388 }
389 
390 // helper for debugging
391 void dump(const int continuation_id) {
392   if (!contains_key(Delimited_continuation, continuation_id)) {
393   ¦ raise << "missing delimited continuation: " << continuation_id << '\n' << end();
394   ¦ return;
395   }
396   delimited_continuation& curr = get(Delimited_continuation, continuation_id);
397   dump(curr.frames);
398 }