diff options
Diffstat (limited to 'archive/1.vm/076continuation.cc')
| -rw-r--r-- | archive/1.vm/076continuation.cc | 406 |
1 files changed, 406 insertions, 0 deletions
diff --git a/archive/1.vm/076continuation.cc b/archive/1.vm/076continuation.cc new file mode 100644 index 00000000..670fef2f --- /dev/null +++ b/archive/1.vm/076continuation.cc @@ -0,0 +1,406 @@ +//: Continuations are a powerful primitive for constructing advanced kinds of +//: control *policies* like back-tracking. +//: +//: In Mu, continuations are first-class and delimited, and are constructed +//: out of two primitives: +//: +//: * 'call-with-continuation-mark' marks the top of the call stack and then +//: calls the provided recipe. +//: * 'return-continuation-until-mark' copies the top of the stack +//: until the mark, and returns it as the result of +//: 'call-with-continuation-mark' (which might be a distant ancestor on the +//: call stack; intervening calls don't return) +//: +//: The resulting slice of the stack can now be called just like a regular +//: recipe. +//: +//: See the example programs continuation*.mu to get a sense for the +//: possibilities. +//: +//: Refinements: +//: * You can call a single continuation multiple times, and it will preserve +//: the state of its local variables at each stack frame between calls. +//: The stack frames of a continuation are not destroyed until the +//: continuation goes out of scope. See continuation2.mu. +//: * 'return-continuation-until-mark' doesn't consume the mark, so you can +//: return multiple continuations based on a single mark. In combination +//: with the fact that 'return-continuation-until-mark' can return from +//: regular calls, just as long as there was an earlier call to +//: 'call-with-continuation-mark', this gives us a way to create resumable +//: recipes. See continuation3.mu. +//: * 'return-continuation-until-mark' can take ingredients to return just +//: like other 'return' instructions. It just implicitly also returns a +//: continuation as the first result. See continuation4.mu. +//: * Conversely, you can pass ingredients to a continuation when calling it, +//: to make it available to products of 'return-continuation-until-mark'. +//: See continuation5.mu. +//: * There can be multiple continuation marks on the stack at once; +//: 'call-with-continuation-mark' and 'return-continuation-until-mark' both +//: need to pass in a tag to coordinate on the correct mark. This allows us +//: to save multiple continuations for different purposes (say if one is +//: for exceptions) with overlapping stack frames. See exception.mu. +//: +//: Inspired by James and Sabry, "Yield: Mainstream delimited continuations", +//: Workshop on the Theory and Practice of Delimited Continuations, 2011. +//: https://www.cs.indiana.edu/~sabry/papers/yield.pdf +//: +//: Caveats: +//: * At the moment we can't statically type-check continuations. So we raise +//: runtime errors for a call that doesn't return a continuation when the +//: caller expects, or one that returns a continuation when the caller +//: doesn't expect it. This shouldn't cause memory corruption, though. +//: There should still be no way to lookup addresses that aren't allocated. + +:(before "End Mu Types Initialization") +type_ordinal continuation = Type_ordinal["continuation"] = Next_type_ordinal++; +Type[continuation].name = "continuation"; + +//: A continuation can be called like a recipe. +:(before "End is_mu_recipe Atom Cases(r)") +if (r.type->name == "continuation") return true; + +//: However, it can't be type-checked like most recipes. Pretend it's like a +//: header-less recipe. +:(after "Begin Reagent->Recipe(r, recipe_header)") +if (r.type->atom && r.type->name == "continuation") { + result_header.has_header = false; + return result_header; +} + +:(code) +void test_delimited_continuation() { + run( + "recipe main [\n" + " 1:continuation <- call-with-continuation-mark 233/mark, f, 77\n" // 77 is an argument to f + " 2:num <- copy 5\n" + " {\n" + " 2:num <- call 1:continuation, 2:num\n" // jump to 'return-continuation-until-mark' below + " 3:bool <- greater-or-equal 2:num, 8\n" + " break-if 3:bool\n" + " loop\n" + " }\n" + "]\n" + "recipe f [\n" + " 11:num <- next-ingredient\n" + " 12:num <- g 11:num\n" + " return 12:num\n" + "]\n" + "recipe g [\n" + " 21:num <- next-ingredient\n" + " 22:num <- return-continuation-until-mark 233/mark\n" + " 23:num <- add 22:num, 1\n" + " return 23:num\n" + "]\n" + ); + // first call of 'g' executes the part before return-continuation-until-mark + CHECK_TRACE_CONTENTS( + // first call of 'g' executes the part before return-continuation-until-mark + "mem: storing 77 in location 21\n" + "run: {2: \"number\"} <- copy {5: \"literal\"}\n" + "mem: storing 5 in location 2\n" + // calls of the continuation execute the part after return-continuation-until-mark + "run: {2: \"number\"} <- call {1: \"continuation\"}, {2: \"number\"}\n" + "mem: storing 5 in location 22\n" + "mem: storing 6 in location 2\n" + "run: {2: \"number\"} <- call {1: \"continuation\"}, {2: \"number\"}\n" + "mem: storing 6 in location 22\n" + "mem: storing 7 in location 2\n" + "run: {2: \"number\"} <- call {1: \"continuation\"}, {2: \"number\"}\n" + "mem: storing 7 in location 22\n" + "mem: storing 8 in location 2\n" + ); + // first call of 'g' does not execute the part after return-continuation-until-mark + CHECK_TRACE_DOESNT_CONTAIN("mem: storing 77 in location 22"); + // calls of the continuation don't execute the part before return-continuation-until-mark + CHECK_TRACE_DOESNT_CONTAIN("mem: storing 5 in location 21"); + CHECK_TRACE_DOESNT_CONTAIN("mem: storing 6 in location 21"); + CHECK_TRACE_DOESNT_CONTAIN("mem: storing 7 in location 21"); + // termination + CHECK_TRACE_DOESNT_CONTAIN("mem: storing 9 in location 2"); +} + +:(before "End call Fields") +int continuation_mark_tag; +:(before "End call Constructor") +continuation_mark_tag = 0; + +:(before "End Primitive Recipe Declarations") +CALL_WITH_CONTINUATION_MARK, +:(before "End Primitive Recipe Numbers") +Recipe_ordinal["call-with-continuation-mark"] = CALL_WITH_CONTINUATION_MARK; +:(before "End Primitive Recipe Checks") +case CALL_WITH_CONTINUATION_MARK: { + if (SIZE(inst.ingredients) < 2) { + 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(); + } + break; +} +:(before "End Primitive Recipe Implementations") +case CALL_WITH_CONTINUATION_MARK: { + // like call, but mark the current call as a 'base of continuation' call + // before pushing the next one on it + trace(Callstack_depth+1, "trace") << "delimited continuation; incrementing callstack depth to " << Callstack_depth << end(); + ++Callstack_depth; + assert(Callstack_depth < Max_depth); + instruction/*copy*/ caller_instruction = current_instruction(); + Current_routine->calls.front().continuation_mark_tag = current_instruction().ingredients.at(0).value; + Current_routine->calls.push_front(call(ingredients.at(1).at(0))); + // drop the mark + caller_instruction.ingredients.erase(caller_instruction.ingredients.begin()); + ingredients.erase(ingredients.begin()); + // drop the callee + caller_instruction.ingredients.erase(caller_instruction.ingredients.begin()); + ingredients.erase(ingredients.begin()); + finish_call_housekeeping(caller_instruction, ingredients); + continue; +} + +:(code) +void test_next_ingredient_inside_continuation() { + run( + "recipe main [\n" + " call-with-continuation-mark 233/mark, f, true\n" + "]\n" + "recipe f [\n" + " 10:bool <- next-input\n" + "]\n" + ); + CHECK_TRACE_CONTENTS( + "mem: storing 1 in location 10\n" + ); +} + +void test_delimited_continuation_out_of_recipe_variable() { + run( + "recipe main [\n" + " x:recipe <- copy f\n" + " call-with-continuation-mark 233/mark, x, true\n" + "]\n" + "recipe f [\n" + " 10:bool <- next-input\n" + "]\n" + ); + CHECK_TRACE_CONTENTS( + "mem: storing 1 in location 10\n" + ); +} + +//: save the slice of current call stack until the 'call-with-continuation-mark' +//: call, and return it as the result. +//: todo: implement delimited continuations in Mu's memory +:(before "End Types") +struct delimited_continuation { + call_stack frames; + int nrefs; + delimited_continuation(call_stack::iterator begin, call_stack::iterator end) :frames(call_stack(begin, end)), nrefs(0) {} +}; +:(before "End Globals") +map<long long int, delimited_continuation> Delimited_continuation; +long long int Next_delimited_continuation_id = 1; // 0 is null just like an address +:(before "End Reset") +Delimited_continuation.clear(); +Next_delimited_continuation_id = 1; + +:(before "End Primitive Recipe Declarations") +RETURN_CONTINUATION_UNTIL_MARK, +:(before "End Primitive Recipe Numbers") +Recipe_ordinal["return-continuation-until-mark"] = RETURN_CONTINUATION_UNTIL_MARK; +:(before "End Primitive Recipe Checks") +case RETURN_CONTINUATION_UNTIL_MARK: { + if (inst.ingredients.empty()) { + raise << maybe(get(Recipe, r).name) << "'" << to_original_string(inst) << "' requires at least one ingredient: a mark tag (number)\n" << end(); + } + break; +} +:(before "End Primitive Recipe Implementations") +case RETURN_CONTINUATION_UNTIL_MARK: { + // I don't know how to think about next-ingredient in combination with + // continuations, so seems cleaner to just kill it. Functions have to read + // their inputs before ever returning a continuation. + Current_routine->calls.front().ingredient_atoms.clear(); + Current_routine->calls.front().next_ingredient_to_process = 0; + // copy the current call stack until the most recent marked call + call_stack::iterator find_base_of_continuation(call_stack&, int); // manual prototype containing '::' + call_stack::iterator base = find_base_of_continuation(Current_routine->calls, /*mark tag*/current_instruction().ingredients.at(0).value); + if (base == Current_routine->calls.end()) { + raise << maybe(current_recipe_name()) << "couldn't find a 'call-with-continuation-mark' to return to with tag " << current_instruction().ingredients.at(0).original_string << '\n' << end(); + raise << maybe(current_recipe_name()) << "call stack:\n" << end(); + for (call_stack::iterator p = Current_routine->calls.begin(); p != Current_routine->calls.end(); ++p) + raise << maybe(current_recipe_name()) << " " << get(Recipe, p->running_recipe).name << '\n' << end(); + break; + } + trace(Callstack_depth+1, "run") << "creating continuation " << Next_delimited_continuation_id << end(); + put(Delimited_continuation, Next_delimited_continuation_id, delimited_continuation(Current_routine->calls.begin(), base)); + while (Current_routine->calls.begin() != base) { + --Callstack_depth; + assert(Callstack_depth >= 0); + Current_routine->calls.pop_front(); + } + // return it as the result of the marked call + products.resize(1); + products.at(0).push_back(Next_delimited_continuation_id); + // return any other ingredients passed in + copy(/*skip mark tag*/++ingredients.begin(), ingredients.end(), inserter(products, products.end())); + ++Next_delimited_continuation_id; + break; // continue to process rest of marked call +} + +:(code) +call_stack::iterator find_base_of_continuation(call_stack& c, int mark_tag) { + for (call_stack::iterator p = c.begin(); p != c.end(); ++p) + if (p->continuation_mark_tag == mark_tag) return p; + return c.end(); +} + +//: overload 'call' for continuations +:(after "Begin Call") +if (is_mu_continuation(current_instruction().ingredients.at(0))) { + // copy multiple calls on to current call stack + assert(scalar(ingredients.at(0))); + trace(Callstack_depth+1, "run") << "calling continuation " << ingredients.at(0).at(0) << end(); + if (!contains_key(Delimited_continuation, ingredients.at(0).at(0))) + raise << maybe(current_recipe_name()) << "no such delimited continuation " << current_instruction().ingredients.at(0).original_string << '\n' << end(); + const call_stack& new_frames = get(Delimited_continuation, ingredients.at(0).at(0)).frames; + for (call_stack::const_reverse_iterator p = new_frames.rbegin(); p != new_frames.rend(); ++p) + Current_routine->calls.push_front(*p); + trace(Callstack_depth+1, "trace") << "calling delimited continuation; growing callstack depth to " << Callstack_depth+SIZE(new_frames) << end(); + Callstack_depth += SIZE(new_frames); + assert(Callstack_depth < Max_depth); + // no call housekeeping; continuations don't support next-ingredient + copy(/*drop continuation*/++ingredients.begin(), ingredients.end(), inserter(products, products.begin())); + break; // record results of resuming 'return-continuation-until-mark' instruction +} + +:(code) +void test_continuations_can_return_values() { + run( + "def main [\n" + " local-scope\n" + " k:continuation, 1:num/raw <- call-with-continuation-mark 233/mark, f\n" + "]\n" + "def f [\n" + " local-scope\n" + " g\n" + "]\n" + "def g [\n" + " local-scope\n" + " return-continuation-until-mark 233/mark, 34\n" + " stash [continuation called]\n" + "]\n" + ); + CHECK_TRACE_CONTENTS( + "mem: storing 34 in location 1\n" + ); +} + +void test_continuations_continue_to_matching_mark() { + run( + "def main [\n" + " local-scope\n" + " k:continuation, 1:num/raw <- call-with-continuation-mark 233/mark, f\n" + " add 1, 1\n" + "]\n" + "def f [\n" + " local-scope\n" + " k2:continuation <- call-with-continuation-mark 234/mark, g\n" + " add 2, 2\n" + "]\n" + "def g [\n" + " local-scope\n" + " return-continuation-until-mark 233/mark, 34\n" + " stash [continuation called]\n" + "]\n" + ); + CHECK_TRACE_CONTENTS( + "run: add {1: \"literal\"}, {1: \"literal\"}\n" + ); + CHECK_TRACE_DOESNT_CONTAIN("run: add {2: \"literal\"}, {2: \"literal\"}"); +} + +//: Allow shape-shifting recipes to return continuations. + +void test_call_shape_shifting_recipe_with_continuation_mark() { + run( + "def main [\n" + " 1:num <- call-with-continuation-mark 233/mark, f, 34\n" + "]\n" + "def f x:_elem -> y:_elem [\n" + " local-scope\n" + " load-ingredients\n" + " y <- copy x\n" + "]\n" + ); + CHECK_TRACE_CONTENTS( + "mem: storing 34 in location 1\n" + ); +} + +:(before "End resolve_ambiguous_call(r, index, inst, caller_recipe) Special-cases") +if (inst.name == "call-with-continuation-mark") { + if (SIZE(inst.ingredients) > 1 && is_recipe_literal(inst.ingredients.at(/*skip mark*/1))) { + resolve_indirect_continuation_call(r, index, inst, caller_recipe); + return; + } +} +:(code) +void resolve_indirect_continuation_call(const recipe_ordinal r, int index, instruction& inst, const recipe& caller_recipe) { + instruction inst2; + inst2.name = inst.ingredients.at(/*skip mark*/1).name; + for (int i = /*skip mark and recipe*/2; i < SIZE(inst.ingredients); ++i) + inst2.ingredients.push_back(inst.ingredients.at(i)); + for (int i = /*skip continuation*/1; i < SIZE(inst.products); ++i) + inst2.products.push_back(inst.products.at(i)); + resolve_ambiguous_call(r, index, inst2, caller_recipe); + inst.ingredients.at(/*skip mark*/1).name = inst2.name; + inst.ingredients.at(/*skip mark*/1).set_value(get(Recipe_ordinal, inst2.name)); +} + +void test_call_shape_shifting_recipe_with_continuation_mark_and_no_outputs() { + run( + "def main [\n" + " 1:continuation <- call-with-continuation-mark 233/mark, f, 34\n" + "]\n" + "def f x:_elem [\n" + " local-scope\n" + " load-ingredients\n" + " return-continuation-until-mark 233/mark\n" + "]\n" + ); + CHECK_TRACE_COUNT("error", 0); +} + +void test_continuation1() { + run( + "def main [\n" + " local-scope\n" + " k:continuation <- call-with-continuation-mark 233/mark, create-yielder\n" + " 10:num/raw <- call k\n" + "]\n" + "def create-yielder -> n:num [\n" + " local-scope\n" + " load-inputs\n" + " return-continuation-until-mark 233/mark\n" + " return 1\n" + "]\n" + ); + CHECK_TRACE_CONTENTS( + "mem: storing 1 in location 10\n" + ); + CHECK_TRACE_COUNT("error", 0); +} + +:(code) +bool is_mu_continuation(reagent/*copy*/ x) { + canonize_type(x); + return x.type && x.type->atom && x.type->value == get(Type_ordinal, "continuation"); +} + +// helper for debugging +void dump(const int continuation_id) { + if (!contains_key(Delimited_continuation, continuation_id)) { + raise << "missing delimited continuation: " << continuation_id << '\n' << end(); + return; + } + delimited_continuation& curr = get(Delimited_continuation, continuation_id); + dump(curr.frames); +} |