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 //:
 35 //: Caveats:
 36 //:  * At the moment we can't statically type-check continuations. So we raise
 37 //:    runtime errors for a call that doesn't return a continuation when the
 38 //:    caller expects, or one that returns a continuation when the caller
 39 //:    doesn't expect it. This shouldn't cause memory corruption, though.
 40 //:    There should still be no way to lookup addresses that aren't allocated.
 41 
 42 :(before "End Mu Types Initialization")
 43 type_ordinal continuation = Type_ordinal["continuation"] = Next_type_ordinal++;
 44 Type[continuation].name = "continuation";
 45 
 46 //: A continuation can be called like a recipe.
 47 :(before "End is_mu_recipe Atom Cases(r)")
 48 if (r.type->name == "continuation") return true;
 49 
 50 //: However, it can't be type-checked like most recipes. Pretend it's like a
 51 //: header-less recipe.
 52 :(after "Begin Reagent->Recipe(r, recipe_header)")
 53 if (r.type->atom && r.type->name == "continuation") {
 54   result_header.has_header = false;
 55   return result_header;
 56 }
 57 
 58 :(scenario delimited_continuation)
 59 recipe main [
 60   1:continuation <- call-with-continuation-mark f, 77  # 77 is an argument to f
 61   2:number <- copy 5
 62   {
 63   ¦ 2:number <- call 1:continuation, 2:number  # 2 is an argument to g, the 'top' of the continuation
 64   ¦ 3:boolean <- greater-or-equal 2:number, 8
 65   ¦ break-if 3:boolean
 66   ¦ loop
 67   }
 68 ]
 69 recipe f [
 70   11:number <- next-ingredient
 71   12:number <- g 11:number
 72   return 12:number
 73 ]
 74 recipe g [
 75   21:number <- next-ingredient
 76   rewind-ingredients
 77   return-continuation-until-mark
 78   # calls of the continuation start from here
 79   22:number <- next-ingredient
 80   23:number <- add 22:number, 1
 81   return 23:number
 82 ]
 83 # first call of 'g' executes the part before return-continuation-until-mark
 84 +mem: storing 77 in location 21
 85 +run: {2: "number"} <- copy {5: "literal"}
 86 +mem: storing 5 in location 2
 87 # calls of the continuation execute the part after return-continuation-until-mark
 88 +run: {2: "number"} <- call {1: "continuation"}, {2: "number"}
 89 +mem: storing 5 in location 22
 90 +mem: storing 6 in location 2
 91 +run: {2: "number"} <- call {1: "continuation"}, {2: "number"}
 92 +mem: storing 6 in location 22
 93 +mem: storing 7 in location 2
 94 +run: {2: "number"} <- call {1: "continuation"}, {2: "number"}
 95 +mem: storing 7 in location 22
 96 +mem: storing 8 in location 2
 97 # first call of 'g' does not execute the part after return-continuation-until-mark
 98 -mem: storing 77 in location 22
 99 # calls of the continuation don't execute the part before return-continuation-until-mark
100 -mem: storing 5 in location 21
101 -mem: storing 6 in location 21
102 -mem: storing 7 in location 21
103 # termination
104 -mem: storing 9 in location 2
105 
106 :(before "End call Fields")
107 bool is_base_of_continuation;
108 :(before "End call Constructor")
109 is_base_of_continuation = false;
110 
111 :(before "End Primitive Recipe Declarations")
112 CALL_WITH_CONTINUATION_MARK,
113 :(before "End Primitive Recipe Numbers")
114 Recipe_ordinal["call-with-continuation-mark"] = CALL_WITH_CONTINUATION_MARK;
115 :(before "End Primitive Recipe Checks")
116 case CALL_WITH_CONTINUATION_MARK: {
117   break;
118 }
119 :(before "End Primitive Recipe Implementations")
120 case CALL_WITH_CONTINUATION_MARK: {
121   // like call, but mark the current call as a 'base of continuation' call
122   // before pushing the next one on it
123   if (Trace_stream) {
124   ¦ ++Trace_stream->callstack_depth;
125   ¦ trace("trace") << "delimited continuation; incrementing callstack depth to " << Trace_stream->callstack_depth << end();
126   ¦ assert(Trace_stream->callstack_depth < 9000);  // 9998-101 plus cushion
127   }
128   const instruction& caller_instruction = current_instruction();
129   Current_routine->calls.front().is_base_of_continuation = true;
130   Current_routine->calls.push_front(call(Recipe_ordinal[current_instruction().ingredients.at(0).name]));
131   ingredients.erase(ingredients.begin());  // drop the callee
132   finish_call_housekeeping(caller_instruction, ingredients);
133   continue;
134 }
135 
136 //: save the slice of current call stack until the 'call-with-continuation-mark'
137 //: call, and return it as the result.
138 //: todo: implement delimited continuations in Mu's memory
139 :(before "End Globals")
140 map<long long int, call_stack> Delimited_continuation;
141 long long int Next_delimited_continuation_id = 1;  // 0 is null just like an address
142 :(before "End Reset")
143 Delimited_continuation.clear();
144 Next_delimited_continuation_id = 1;
145 
146 :(before "End Primitive Recipe Declarations")
147 RETURN_CONTINUATION_UNTIL_MARK,
148 :(before "End Primitive Recipe Numbers")
149 Recipe_ordinal["return-continuation-until-mark"] = RETURN_CONTINUATION_UNTIL_MARK;
150 :(before "End Primitive Recipe Checks")
151 case RETURN_CONTINUATION_UNTIL_MARK: {
152   break;
153 }
154 :(before "End Primitive Recipe Implementations")
155 case RETURN_CONTINUATION_UNTIL_MARK: {
156   // first clear any existing ingredients, to isolate the creation of the
157   // continuation from its calls
158   Current_routine->calls.front().ingredient_atoms.clear();
159   Current_routine->calls.front().next_ingredient_to_process = 0;
160   // copy the current call stack until the most recent marked call
161   call_stack::iterator find_base_of_continuation(call_stack& c);  // manual prototype containing '::'
162   call_stack::iterator base = find_base_of_continuation(Current_routine->calls);
163   if (base == Current_routine->calls.end()) {
164   ¦ raise << maybe(current_recipe_name()) << "couldn't find a 'call-with-continuation-mark' to return to\n" << end();
165   ¦ raise << maybe(current_recipe_name()) << "call stack:\n" << end();
166   ¦ for (call_stack::iterator p = Current_routine->calls.begin();  p != Current_routine->calls.end();  ++p)
167   ¦ ¦ raise << maybe(current_recipe_name()) << "  " << get(Recipe, p->running_recipe).name << '\n' << end();
168   ¦ break;
169   }
170   trace("run") << "creating continuation " << Next_delimited_continuation_id << end();
171   Delimited_continuation[Next_delimited_continuation_id] = call_stack(Current_routine->calls.begin(), base);
172   while (Current_routine->calls.begin() != base) {
173   ¦ if (Trace_stream) {
174   ¦ ¦ --Trace_stream->callstack_depth;
175   ¦ ¦ assert(Trace_stream->callstack_depth >= 0);
176   ¦ }
177   ¦ Current_routine->calls.pop_front();
178   }
179   // return it as the result of the marked call
180   products.resize(1);
181   products.at(0).push_back(Next_delimited_continuation_id);
182   // return any other ingredients passed in
183   copy(ingredients.begin(), ingredients.end(), inserter(products, products.end()));
184   ++Next_delimited_continuation_id;
185   break;  // continue to process rest of marked call
186 }
187 
188 :(code)
189 call_stack::iterator find_base_of_continuation(call_stack& c) {
190   for (call_stack::iterator p = c.begin(); p != c.end(); ++p)
191   ¦ if (p->is_base_of_continuation) return p;
192   return c.end();
193 }
194 
195 //: overload 'call' for continuations
196 :(after "Begin Call")
197 if (current_instruction().ingredients.at(0).type->atom
198   ¦ && current_instruction().ingredients.at(0).type->name == "continuation") {
199   // copy multiple calls on to current call stack
200   assert(scalar(ingredients.at(0)));
201   trace("run") << "calling continuation " << ingredients.at(0).at(0) << end();
202   if (Delimited_continuation.find(ingredients.at(0).at(0)) == Delimited_continuation.end())
203   ¦ raise << maybe(current_recipe_name()) << "no such delimited continuation " << current_instruction().ingredients.at(0).original_string << '\n' << end();
204   const call_stack& new_calls = Delimited_continuation[ingredients.at(0).at(0)];
205   const call& caller = (SIZE(new_calls) > 1) ? *++new_calls.begin() : Current_routine->calls.front();
206   for (call_stack::const_reverse_iterator p = new_calls.rbegin(); p != new_calls.rend(); ++p) {
207   ¦ Current_routine->calls.push_front(*p);
208   ¦ // ensure that the presence of a continuation keeps its stack frames from being reclaimed
209   ¦ int space_address = Current_routine->calls.front().default_space;
210   ¦ if (space_address != 0) {
211   ¦ ¦ int refcount = get_or_insert(Memory, space_address);
212   ¦ ¦ trace("mem") << "incrementing refcount of " << space_address << ": " << refcount << " -> " << refcount+1 << end();
213   ¦ ¦ put(Memory, space_address, refcount+1);
214   ¦ }
215   }
216   if (Trace_stream) {
217   ¦ Trace_stream->callstack_depth += SIZE(new_calls);
218   ¦ trace("trace") << "calling delimited continuation; growing callstack depth to " << Trace_stream->callstack_depth << end();
219   ¦ assert(Trace_stream->callstack_depth < 9000);  // 9998-101 plus cushion
220   }
221   ++current_step_index();  // skip past the return-continuation-until-mark
222   ingredients.erase(ingredients.begin());  // drop the callee
223   finish_call_housekeeping(to_instruction(caller), ingredients);
224   continue;
225 }
226 
227 //: Ensure that the presence of a continuation keeps its stack frames from being reclaimed.
228 
229 :(scenario continuations_preserve_local_scopes)
230 def main [
231   local-scope
232   k:continuation <- call-with-continuation-mark f
233   call k
234   return 34
235 ]
236 def f [
237   local-scope
238   g
239 ]
240 def g [
241   local-scope
242   return-continuation-until-mark
243   add 1, 1
244 ]
245 # entering main
246 +mem: new alloc: 1000
247 +run: {k: "continuation"} <- call-with-continuation-mark {f: "recipe-literal"}
248 # entering f
249 +mem: new alloc: 1004
250 # entering g
251 +mem: new alloc: 1007
252 # return control to main
253 +run: return-continuation-until-mark
254 # no allocs abandoned yet
255 # finish running main
256 +run: call {k: "continuation"}
257 +run: add {1: "literal"}, {1: "literal"}
258 +run: return {34: "literal"}
259 # now k is reclaimed
260 +mem: trying to reclaim local k:continuation
261 # at this point all allocs in the continuation are abandoned
262 +mem: automatically abandoning 1007
263 +mem: automatically abandoning 1004
264 # finally the alloc for main is abandoned
265 +mem: automatically abandoning 1000
266 
267 :(after "Begin Decrement Refcounts(canonized_x)")
268 if (is_mu_continuation(canonized_x)) {
269   int continuation_id = get_or_insert(Memory, canonized_x.value);
270   trace("run") << "reclaiming continuation " << continuation_id << end();
271   if (continuation_id == 0) return;
272   const call_stack& continuation_calls = get(Delimited_continuation, continuation_id);
273   // temporarily push the stack frames for the continuation one last time on to the call stack
274   for (call_stack::const_reverse_iterator p = continuation_calls.rbegin(); p != continuation_calls.rend(); ++p)
275   ¦ Current_routine->calls.push_front(*p);
276   // reclaim their spaces while popping them
277   // (because reclaim_default_space() relies on the default-space being reclaimed being at the top of the stack)
278   for (call_stack::const_iterator p = continuation_calls.begin(); p != continuation_calls.end(); ++p) {
279   ¦ reclaim_default_space();
280   ¦ Current_routine->calls.pop_front();
281   }
282   return;
283 }
284 
285 :(code)
286 bool is_mu_continuation(reagent/*copy*/ x) {
287   canonize_type(x);
288   return x.type && x.type->atom && x.type->value == get(Type_ordinal, "continuation");
289 }
290 
291 :(scenario continuations_can_return_values)
292 def main [
293   local-scope
294   k:continuation, 1:num/raw <- call-with-continuation-mark f
295 ]
296 def f [
297   local-scope
298   g
299 ]
300 def g [
301   local-scope
302   return-continuation-until-mark 34
303   stash [continuation called]
304 ]
305 # entering main
306 +mem: new alloc: 1000
307 +run: {k: "continuation"}, {1: "number", "raw": ()} <- call-with-continuation-mark {f: "recipe-literal"}
308 # entering f
309 +mem: new alloc: 1004
310 # entering g
311 +mem: new alloc: 1007
312 # return control to main
313 +run: return-continuation-until-mark {34: "literal"}
314 # no allocs abandoned yet
315 +mem: storing 34 in location 1
316 # end of main
317 # make sure no memory leaks..
318 +mem: trying to reclaim local k:continuation
319 +mem: automatically abandoning 1007
320 +mem: automatically abandoning 1004
321 +mem: automatically abandoning 1000
322 # ..even though we never called the continuation
323 -app: continuation called