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