1447

1 files changed, 216 insertions, 0 deletions

diff --git a/049continuation.cc b/049continuation.cc
new file mode 100644
index 00000000..019c075e
--- /dev/null
+++ b/049continuation.cc
@@ -0,0 +1,216 @@
+//: Continuations are a powerful primitive for constructing advanced kinds of
+//: control *policies* like back-tracking. They're usually provided using a
+//: primitive called 'call-cc': http://en.wikipedia.org/wiki/Call-with-current-continuation)
+//: But in mu 'call-cc' is constructed out of a combination of two primitives:
+//:   'current-continuation', which returns a continuation, and
+//:   'continue-from', which takes a continuation to switch to.
+
+//: todo: implement continuations in mu's memory
+:(before "End Globals")
+map<long long int, call_stack> Continuation;
+long long int Next_continuation_id = 0;
+:(before "End Setup")
+Continuation.clear();
+Next_continuation_id = 0;
+
+:(before "End Mu Types Initialization")
+type_number continuation = Type_number["continuation"] = Next_type_number++;
+Type[continuation].name = "continuation";
+
+:(before "End Primitive Recipe Declarations")
+CURRENT_CONTINUATION,
+:(before "End Primitive Recipe Numbers")
+Recipe_number["current-continuation"] = CURRENT_CONTINUATION;
+:(before "End Primitive Recipe Implementations")
+case CURRENT_CONTINUATION: {
+  // copy the current call stack
+  Continuation[Next_continuation_id] = Current_routine->calls;  // deep copy because calls have no pointers
+  // make sure calling the copy doesn't spawn the same continuation again
+  ++Continuation[Next_continuation_id].front().running_step_index;
+  products.resize(1);
+  products.at(0).push_back(Next_continuation_id);
+  ++Next_continuation_id;
+  trace("current-continuation") << "new continuation " << Next_continuation_id;
+  break;
+}
+
+:(before "End Primitive Recipe Declarations")
+CONTINUE_FROM,
+:(before "End Primitive Recipe Numbers")
+Recipe_number["continue-from"] = CONTINUE_FROM;
+:(before "End Primitive Recipe Implementations")
+case CONTINUE_FROM: {
+  assert(scalar(ingredients.at(0)));
+  long long int c = ingredients.at(0).at(0);
+  Current_routine->calls = Continuation[c];  // deep copy because calls have no pointers
+  // refresh instruction_counter to next instruction after current-continuation
+  instruction_counter = current_step_index()+1;
+  continue;  // skip the rest of this instruction
+}
+
+:(scenario continuation)
+# simulate a loop using continuations
+recipe main [
+  1:number <- copy 0:literal
+  2:continuation <- current-continuation
+  {
+#?     $print 1:number
+    3:boolean <- greater-or-equal 1:number, 3:literal
+    break-if 3:boolean
+    1:number <- add 1:number, 1:literal
+    continue-from 2:continuation  # loop
+  }
+]
++mem: storing 1 in location 1
++mem: storing 2 in location 1
++mem: storing 3 in location 1
+-mem: storing 4 in location 1
+# ensure every iteration doesn't copy the stack over and over
+$current-continuation: 1
+
+:(scenario continuation_inside_caller)
+recipe main [
+  1:number <- copy 0:literal
+  2:continuation <- loop-body
+  {
+    3:boolean <- greater-or-equal 1:number, 3:literal
+    break-if 3:boolean
+    continue-from 2:continuation  # loop
+  }
+]
+
+recipe loop-body [
+  4:continuation <- current-continuation
+  1:number <- add 1:number, 1:literal
+]
++mem: storing 1 in location 1
++mem: storing 2 in location 1
++mem: storing 3 in location 1
+-mem: storing 4 in location 1
+
+//:: A variant of continuations is the 'delimited' continuation that can be called like any other recipe.
+//: In mu, this is constructed out of three primitives:
+//:   'reset-and-call' lays down a 'reset mark' on the call stack
+//:   'current-delimited_continuation' copies the top of the stack until the reset mark
+//:   'call-continuation' calls a delimited continuation like a normal recipe
+
+//: todo: come up with a simpler, more obviously correct test
+:(scenario delimited_continuation)
+# too hacky to distinguish initial call from later calls by #ingredients?
+recipe main [
+#?   $start-tracing
+  1:continuation, 2:number <- reset-and-call f:recipe  # initial call without ingredients
+  2:number <- copy 5:literal
+  {
+    1:continuation, 2:number <- call-continuation 1:continuation, 2:number  # subsequent calls
+    3:boolean <- greater-or-equal 2:number, 8:literal
+    break-if 3:boolean
+    loop
+  }
+]
+
+recipe f [
+  11:continuation, 12:number <- g
+  reply 11:continuation, 12:number
+]
+
+# when constructing the continuation, just returns 0
+# on subsequent calls of the continuation, increments the number passed in
+recipe g [
+  21:continuation <- current-delimited-continuation
+  # calls of the continuation start from here
+  22:number, 23:boolean/found? <- next-ingredient
+  {
+    break-if 23:boolean/found?
+    reply 21:continuation, 0:literal
+  }
+  22:number <- add 22:number, 1:literal
+  reply 21:continuation, 22:number
+]
++mem: storing 0 in location 2
+-mem: storing 4 in location 2
++mem: storing 5 in location 2
++mem: storing 6 in location 2
++mem: storing 7 in location 2
++mem: storing 8 in location 2
+-mem: storing 9 in location 2
+
+//: 'reset-and-call' is like 'call' except it inserts a label to the call stack
+//: before performing the call
+
+:(before "End call Fields")
+bool is_reset;
+:(before "End call Constructor")
+is_reset = false;
+
+//: like call, but mark the current call as a 'reset' call before pushing the next one on it
+
+:(before "End Primitive Recipe Declarations")
+RESET_AND_CALL,
+:(before "End Primitive Recipe Numbers")
+Recipe_number["reset-and-call"] = RESET_AND_CALL;
+:(before "End Primitive Recipe Implementations")
+case RESET_AND_CALL: {
+  Current_routine->calls.front().is_reset = true;
+  ++Callstack_depth;
+  assert(Callstack_depth < 9000);  // 9998-101 plus cushion
+  call callee(Recipe_number[current_instruction().ingredients.at(0).name]);
+  for (long long int i = 0; i < SIZE(ingredients); ++i) {
+    callee.ingredient_atoms.push_back(ingredients.at(i));
+  }
+  Current_routine->calls.push_front(callee);
+  continue;  // not done with caller; don't increment current_step_index()
+}
+
+//: create a copy of the slice of current call stack until a 'reset' call
+//: todo: implement delimited continuations in mu's memory
+:(before "End Globals")
+map<long long int, call_stack> Delimited_continuation;
+long long int Next_delimited_continuation_id = 0;
+:(before "End Setup")
+Delimited_continuation.clear();
+Next_delimited_continuation_id = 0;
+
+:(before "End Primitive Recipe Declarations")
+CURRENT_DELIMITED_CONTINUATION,
+:(before "End Primitive Recipe Numbers")
+Recipe_number["current-delimited-continuation"] = CURRENT_DELIMITED_CONTINUATION;
+:(before "End Primitive Recipe Implementations")
+case CURRENT_DELIMITED_CONTINUATION: {
+  // copy the current call stack until the first reset call
+  for (call_stack::iterator p = Current_routine->calls.begin(); p != Current_routine->calls.end(); ++p) {
+//?     cerr << "copying " << Recipe[p->running_recipe].name << '\n'; //? 1
+    if (p->is_reset) break;
+    Delimited_continuation[Next_delimited_continuation_id].push_back(*p);  // deep copy because calls have no pointers
+  }
+  // make sure calling the copy doesn't spawn the same continuation again
+  ++Delimited_continuation[Next_delimited_continuation_id].front().running_step_index;
+  products.resize(1);
+  products.at(0).push_back(Next_delimited_continuation_id);
+  ++Next_delimited_continuation_id;
+  trace("current-continuation") << "new continuation " << Next_continuation_id;
+  break;
+}
+
+//: copy slice of calls back on to current call stack
+:(before "End Primitive Recipe Declarations")
+CALL_CONTINUATION,
+:(before "End Primitive Recipe Numbers")
+Recipe_number["call-continuation"] = CALL_CONTINUATION;
+:(before "End Primitive Recipe Implementations")
+case CALL_CONTINUATION: {
+  ++Callstack_depth;
+  assert(Callstack_depth < 9000);  // 9998-101 plus cushion
+  assert(scalar(ingredients.at(0)));
+  assert(Delimited_continuation.find(ingredients.at(0).at(0)) != Delimited_continuation.end());
+  const call_stack& new_calls = Delimited_continuation[ingredients.at(0).at(0)];
+  for (call_stack::const_reverse_iterator p = new_calls.rbegin(); p != new_calls.rend(); ++p) {
+//?     cerr << "copying back " << Recipe[p->running_recipe].name << '\n'; //? 1
+    Current_routine->calls.push_front(*p);
+  }
+  for (long long int i = /*skip continuation*/1; i < SIZE(ingredients); ++i) {
+//?     cerr << "copying ingredient " << i << ": " << ingredients.at(i).at(0) << '\n'; //? 1
+    Current_routine->calls.front().ingredient_atoms.push_back(ingredients.at(i));
+  }
+  continue;  // not done with caller; don't increment current_step_index()
+}