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 function.
  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 call
 12 //:    stack; intervening calls don't return)
 13 //:
 14 //: The resulting slice of the stack can now be called just like a regular
 15 //: function.
 16 
 17 :(before "End Mu Types Initialization")
 18 type_ordinal continuation = Type_ordinal["continuation"] = Next_type_ordinal++;
 19 Type[continuation].name = "continuation";
 20 
 21 //: A continuation can be called like a recipe.
 22 :(before "End is_mu_recipe Atom Cases(r)")
 23 if (r.type->name == "continuation") return true;
 24 
 25 //: However, it can't be type-checked like most recipes. Pretend it's like a
 26 //: header-less recipe.
 27 :(after "Begin Reagent->Recipe(r, recipe_header)")
 28 if (r.type->atom && r.type->name == "continuation") {
 29   result_header.has_header = false;
 30   return result_header;
 31 }
 32 
 33 :(scenario delimited_continuation)
 34 recipe main [
 35   1:continuation <- call-with-continuation-mark f, 77  # 77 is an argument to f
 36   2:number <- copy 5
 37   {
 38   ¦ 2:number <- call 1:continuation, 2:number  # 2 is an argument to g, the 'top' of the continuation
 39   ¦ 3:boolean <- greater-or-equal 2:number, 8
 40   ¦ break-if 3:boolean
 41   ¦ loop
 42   }
 43 ]
 44 recipe f [
 45   11:number <- next-ingredient
 46   12:number <- g 11:number
 47   return 12:number
 48 ]
 49 recipe g [
 50   21:number <- next-ingredient
 51   rewind-ingredients
 52   return-continuation-until-mark
 53   # calls of the continuation start from here
 54   22:number <- next-ingredient
 55   23:number <- add 22:number, 1
 56   return 23:number
 57 ]
 58 # first call of 'g' executes the part before return-continuation-until-mark
 59 +mem: storing 77 in location 21
 60 +run: {2: "number"} <- copy {5: "literal"}
 61 +mem: storing 5 in location 2
 62 # calls of the continuation execute the part after return-continuation-until-mark
 63 +run: {2: "number"} <- call {1: "continuation"}, {2: "number"}
 64 +mem: storing 5 in location 22
 65 +mem: storing 6 in location 2
 66 +run: {2: "number"} <- call {1: "continuation"}, {2: "number"}
 67 +mem: storing 6 in location 22
 68 +mem: storing 7 in location 2
 69 +run: {2: "number"} <- call {1: "continuation"}, {2: "number"}
 70 +mem: storing 7 in location 22
 71 +mem: storing 8 in location 2
 72 # first call of 'g' does not execute the part after return-continuation-until-mark
 73 -mem: storing 77 in location 22
 74 # calls of the continuation don't execute the part before return-continuation-until-mark
 75 -mem: storing 5 in location 21
 76 -mem: storing 6 in location 21
 77 -mem: storing 7 in location 21
 78 # termination
 79 -mem: storing 9 in location 2
 80 
 81 :(before "End call Fields")
 82 bool is_base_of_continuation;
 83 :(before "End call Constructor")
 84 is_base_of_continuation = false;
 85 
 86 :(before "End Primitive Recipe Declarations")
 87 CALL_WITH_CONTINUATION_MARK,
 88 :(before "End Primitive Recipe Numbers")
 89 Recipe_ordinal["call-with-continuation-mark"] = CALL_WITH_CONTINUATION_MARK;
 90 :(before "End Primitive Recipe Checks")
 91 case CALL_WITH_CONTINUATION_MARK: {
 92   break;
 93 }
 94 :(before "End Primitive Recipe Implementations")
 95 case CALL_WITH_CONTINUATION_MARK: {
 96   // like call, but mark the current call as a 'base of continuation' call
 97   // before pushing the next one on it
 98   if (Trace_stream) {
 99   ¦ ++Trace_stream->callstack_depth;
100   ¦ trace("trace") << "delimited continuation; incrementing callstack depth to " << Trace_stream->callstack_depth << end();
101   ¦ assert(Trace_stream->callstack_depth < 9000);  // 9998-101 plus cushion
102   }
103   const instruction& caller_instruction = current_instruction();
104   Current_routine->calls.front().is_base_of_continuation = true;
105   Current_routine->calls.push_front(call(Recipe_ordinal[current_instruction().ingredients.at(0).name]));
106   ingredients.erase(ingredients.begin());  // drop the callee
107   finish_call_housekeeping(caller_instruction, ingredients);
108   continue;
109 }
110 
111 //: save the slice of current call stack until the 'call-with-continuation-mark'
112 //: call, and return it as the result.
113 //: todo: implement delimited continuations in Mu's memory
114 :(before "End Globals")
115 map<long long int, call_stack> Delimited_continuation;
116 long long int Next_delimited_continuation_id = 0;
117 :(before "End Reset")
118 Delimited_continuation.clear();
119 Next_delimited_continuation_id = 0;
120 
121 :(before "End Primitive Recipe Declarations")
122 RETURN_CONTINUATION_UNTIL_MARK,
123 :(before "End Primitive Recipe Numbers")
124 Recipe_ordinal["return-continuation-until-mark"] = RETURN_CONTINUATION_UNTIL_MARK;
125 :(before "End Primitive Recipe Checks")
126 case RETURN_CONTINUATION_UNTIL_MARK: {
127   break;
128 }
129 :(before "End Primitive Recipe Implementations")
130 case RETURN_CONTINUATION_UNTIL_MARK: {
131   // first clear any existing ingredients, to isolate the creation of the
132   // continuation from its calls
133   Current_routine->calls.front().ingredient_atoms.clear();
134   Current_routine->calls.front().next_ingredient_to_process = 0;
135   // copy the current call stack until the most recent marked call
136   call_stack::iterator find_base_of_continuation(call_stack& c);  // manual prototype containing '::'
137   call_stack::iterator base = find_base_of_continuation(Current_routine->calls);
138   if (base == Current_routine->calls.end()) {
139   ¦ raise << maybe(current_recipe_name()) << "couldn't find a 'call-with-continuation-mark' to return to\n" << end();
140   ¦ raise << maybe(current_recipe_name()) << "call stack:\n" << end();
141   ¦ for (call_stack::iterator p = Current_routine->calls.begin();  p != Current_routine->calls.end();  ++p)
142   ¦ ¦ raise << maybe(current_recipe_name()) << "  " << get(Recipe, p->running_recipe).name << '\n' << end();
143   ¦ break;
144   }
145   Delimited_continuation[Next_delimited_continuation_id] = call_stack(Current_routine->calls.begin(), base);
146   while (Current_routine->calls.begin() != base) {
147   ¦ if (Trace_stream) {
148   ¦ ¦ --Trace_stream->callstack_depth;
149   ¦ ¦ assert(Trace_stream->callstack_depth >= 0);
150   ¦ }
151   ¦ Current_routine->calls.pop_front();
152   }
153   // return it as the result of the marked call
154   products.resize(1);
155   products.at(0).push_back(Next_delimited_continuation_id);
156   ++Next_delimited_continuation_id;
157   break;  // continue to process rest of marked call
158 }
159 
160 :(code)
161 call_stack::iterator find_base_of_continuation(call_stack& c) {
162   for (call_stack::iterator p = c.begin(); p != c.end(); ++p)
163   ¦ if (p->is_base_of_continuation) return p;
164   return c.end();
165 }
166 
167 //: overload 'call' for continuations
168 :(after "Begin Call")
169 if (current_instruction().ingredients.at(0).type->atom
170   ¦ && current_instruction().ingredients.at(0).type->name == "continuation") {
171   // copy multiple calls on to current call stack
172   assert(scalar(ingredients.at(0)));
173   if (Delimited_continuation.find(ingredients.at(0).at(0)) == Delimited_continuation.end())
174   ¦ raise << maybe(current_recipe_name()) << "no such delimited continuation " << current_instruction().ingredients.at(0).original_string << '\n' << end();
175   const call_stack& new_calls = Delimited_continuation[ingredients.at(0).at(0)];
176   const call& caller = (SIZE(new_calls) > 1) ? *++new_calls.begin() : Current_routine->calls.front();
177   for (call_stack::const_reverse_iterator p = new_calls.rbegin(); p != new_calls.rend(); ++p)
178   ¦ Current_routine->calls.push_front(*p);
179   if (Trace_stream) {
180   ¦ Trace_stream->callstack_depth += SIZE(new_calls);
181   ¦ trace("trace") << "calling delimited continuation; growing callstack depth to " << Trace_stream->callstack_depth << end();
182   ¦ assert(Trace_stream->callstack_depth < 9000);  // 9998-101 plus cushion
183   }
184   ++current_step_index();  // skip past the return-continuation-until-mark
185   ingredients.erase(ingredients.begin());  // drop the callee
186   finish_call_housekeeping(to_instruction(caller), ingredients);
187   continue;
188 }