tour - touring some programming systems

diff options

Diffstat (limited to 'js/games/nluqo.github.io/~bh/v2ch13/plot3skip1.gif')

0 files changed, 0 insertions, 0 deletions

//: 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_ordinal continuation = Type_ordinal["continuation"] = Next_type_ordinal++; Type[continuation].name = "continuation"; :(before "End Primitive Recipe Declarations") CURRENT_CONTINUATION, :(before "End Primitive Recipe Numbers") Recipe_ordinal["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 << end(); break; } :(before "End Primitive Recipe Declarations") CONTINUE_FROM, :(before "End Primitive Recipe Numbers") Recipe_ordinal["continue-from"] = CONTINUE_FROM; :(before "End Primitive Recipe Implementations") case CONTINUE_FROM: { if (!scalar(ingredients.at(0))) { raise << current_recipe_name() << ": first ingredient of 'continue-from' should be a continuation id generated by 'current-continuation', but got " << current_instruction().ingredients.at(0).original_string << '\n' << end(); break; } long long int c = ingredients.at(0).at(0); Current_routine->calls = Continuation[c]; // deep copy; calls have no pointers continue; // skip rest of this instruction } :(scenario continuation) # simulate a loop using continuations recipe main [ 1:number <- copy 0 2:continuation <- current-continuation { #? $print 1:number 3:boolean <- greater-or-equal 1:number, 3 break-if 3:boolean 1:number <- add 1:number, 1 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) #? % Trace_stream->dump_layer = "all"; #? 1 recipe main [ 1:number <- copy 0 2:continuation <- loop-body { 3:boolean <- greater-or-equal 1:number, 3 break-if 3:boolean continue-from 2:continuation # loop } ] recipe loop-body [ 4:continuation <- current-continuation 1:number <- add 1:number, 1 ] +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 two primitives: //: //: * 'create-delimited-continuation' lays down a mark on the call //: stack and calls the provided function (it is sometimes called 'prompt') //: * 'reply-current-continuation' copies the top of the stack until the //: mark, and returns it as the response of create-delimited-continuation //: (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 //: function. :(scenario delimited_continuation) recipe main [ 1:continuation <- create-delimited-continuation f:recipe 12 # 12 is an argument to f 2:number <- copy 5 { 2:number <- call 1:continuation, 2:number # 2 is an argument to g, the 'top' of the continuation 3:boolean <- greater-or-equal 2:number, 8 break-if 3:boolean loop } ] recipe f [ 11:number <- next-ingredient 12:number <- g 11:number reply 12:number ] recipe g [ 21:number <- next-ingredient rewind-ingredients reply-delimited-continuation # calls of the continuation start from here 22:number <- next-ingredient 23:number <- add 22:number, 1 reply 23:number ] #? ? # first call of 'g' executes the part before reply-delimited-continuation +mem: storing 12 in location 21 +run: 2:number <- copy 5 +mem: storing 5 in location 2 # calls of the continuation execute the part after reply-delimited-continuation +run: 2:number <- call 1:continuation, 2:number +mem: storing 5 in location 22 +mem: storing 6 in location 2 +run: 2:number <- call 1:continuation, 2:number +mem: storing 6 in location 22 +mem: storing 7 in location 2 +run: 2:number <- call 1:continuation, 2:number +mem: storing 7 in location 22 +mem: storing 8 in location 2 # first call of 'g' does not execute the part after reply-delimited-continuation -mem: storing 12 in location 22 # calls of the continuation don't execute the part before reply-delimited-continuation -mem: storing 5 in location 21 -mem: storing 6 in location 21 -mem: storing 7 in location 21 # termination -mem: storing 9 in location 2 //: 'create-delimited-continuation' is like 'call' except it adds a 'reset' mark to //: the call stack :(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") CREATE_DELIMITED_CONTINUATION, :(before "End Primitive Recipe Numbers") Recipe_ordinal["create-delimited-continuation"] = CREATE_DELIMITED_CONTINUATION; :(before "End Primitive Recipe Implementations") case CREATE_DELIMITED_CONTINUATION: { Current_routine->calls.front().is_reset = true; Current_routine->calls.push_front(call(Recipe_ordinal[current_instruction().ingredients.at(0).name])); ingredients.erase(ingredients.begin()); // drop the callee goto call_housekeeping; } //: save the slice of current call stack until the 'create-delimited-continuation' //: call, and return it as the result. //: 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") REPLY_DELIMITED_CONTINUATION, :(before "End Primitive Recipe Numbers") Recipe_ordinal["reply-delimited-continuation"] = REPLY_DELIMITED_CONTINUATION; :(before "End Primitive Recipe Implementations") case REPLY_DELIMITED_CONTINUATION: { // first clear any existing ingredients, to isolate the creation of the // continuation from its calls 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 'reset' call call_stack::iterator find_reset(call_stack& c); // manual prototype containing '::' call_stack::iterator reset = find_reset(Current_routine->calls); if (reset == Current_routine->calls.end()) { raise << current_recipe_name() << ": couldn't find a 'reset' call to jump out to\n" << end(); break; } Delimited_continuation[Next_delimited_continuation_id] = call_stack(Current_routine->calls.begin(), reset); while (Current_routine->calls.begin() != reset) { --Callstack_depth; Current_routine->calls.pop_front(); } // return it as the result of the 'reset' call products.resize(1); products.at(0).push_back(Next_delimited_continuation_id); ++Next_delimited_continuation_id; break; // continue to process rest of 'reset' call } :(code) call_stack::iterator find_reset(call_stack& c) { for (call_stack::iterator p = c.begin(); p != c.end(); ++p) if (p->is_reset) return p; return c.end(); } //: overload 'call' for continuations :(after "Begin Call") if (!current_instruction().ingredients.at(0).properties.empty() && !current_instruction().ingredients.at(0).properties.at(0).second.empty() && current_instruction().ingredients.at(0).properties.at(0).second.at(0) == "continuation") { // copy multiple calls on to current call stack assert(scalar(ingredients.at(0))); if (Delimited_continuation.find(ingredients.at(0).at(0)) == Delimited_continuation.end()) { raise << current_recipe_name() << ": no such delimited continuation " << current_instruction().ingredients.at(0).original_string << '\n' << 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) Current_routine->calls.push_front(*p); ++current_step_index(); // skip past the reply-delimited-continuation ingredients.erase(ingredients.begin()); // drop the callee goto call_housekeeping; }


context:
space:
mode: