/** * Algebraic Effects and Handlers as in <a href='http://www.eff-lang.org/'>Eff</a> */ // // Note: // new Continuation() - returns the current function's continuation. // function callcc(f) { return f(new Continuation()) } /** * Implementation of delimited continuation operators given by * <a href='http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.43.8213'>Filinski</a> */ function MetaContinuation() { var metaCont; var self = this function abort(thunk) { var v = thunk(); var k = metaCont; return k(v); } /** * The reset operator sets the limit for the continuation * @param {function} thunk */ this.reset = function(thunk) { var saved = metaCont; var k = new Continuation(); metaCont = function(v){ metaCont = saved; var r = k(v); return r; }; var r = abort(thunk); return r; } /** * The shift operator captures the continuation up to the innermost * enclosing reset */ this.shift = function(f) { var k = new Continuation(); var r = abort(function(){ var r = f(function(v){ var r = self.reset(function(){ var r = k(v); return r; }); return r; }); return r; }); return r; } } /** Factory to create effects */ function Effects() { var metaCont = new MetaContinuation(); var OPS = {}; // Operation records var self = this; // Handler composition function ComposedHandler(h1, h2) { this.h1 = h1; this.h2 = h2; } ComposedHandler.prototype = { handle: function(thunk) { var self = this; return self.h1.handle(function() { return self.h2.handle(thunk); }); }, compose: function(h) { return new ComposedHandler(this, h); } }; /** * Creates a new Effect * @param {string} effect - Name of this effect * @returns {Effect} */ var effectId = 0; this.createEffect = function(effect) { if (undefined == effect) { var id = ++effectId; effect = "Eff#"+id; } return new Effect(effect); } /** * Factory to create operations and handlers: */ function Effect(effect) { var thisEffect = this; /** * Creates a new operation. * @param {string} name - Name of this operation * @returns {function} */ this.createOperation = function(name) { var key = effect +"#"+name; var op = OPS[key]; if (undefined == op) { op = new Op(name); OPS[key] = op; } var result = function() { var args = []; for (var i = 0; i < arguments.length; i++) { args.push(arguments[i]); } // find the handler for this operation and apply it to the arguments of this call together with its continuation var h = op.handler(); var result = metaCont.shift(function(k) { var result = h.call(null, {args: args, k: k}); return result; }); return result; } return result; } /** * Creates a new handler * @param {object} handlers - an object with function properties which may be 'return', 'finally' or * the names of operations * @param {object} resource - optional resource to use with default handler * @returns {function} */ this.createHandler = function(handlers, resource) { var returnHandler = handlers["return"]; var finallyHandler = handlers["finally"]; var ops = []; var hs = []; for (var opName in handlers) { switch (opName) { case "return": case "finally": break; default: var h = handlers[opName]; var key = effect+"#"+opName; var op = OPS[key]; if (undefined == op) { op = new Op(opName); OPS[key] = op; } if (resource) { function installHandler(op, h) { op.handler = function() { return function(opCall) { var args = opCall.args; var k = opCall.k; return h.apply(resource, args.concat(k)); } } } installHandler(op, h); } ops.push(op); hs.push(h); } } return new Handler(returnHandler, finallyHandler, ops, hs); } /** * Creates a new default handler - will be called for top-level operations * @param {object} handlers - an object with function properties which may be 'return', 'finally' or * the names of operations * @param {object} resource - resource to use with this default handler * @returns {function} */ this.createDefaultHandler = function(handlers, resource) { if (undefined == resource) resource = true; return thisEffect.createHandler(handlers, resource); } // Operation record function Op(name) { this.name = name; this.handler = function() { return function() {throw "no handler: "+effect +"#"+name} } this.toString = function() { return effect +"#"+name } } // Handler record function Handler(returnHandler, finallyHandler, ops, hs, resource) { function _return(result) { if (undefined != returnHandler) { result = returnHandler(result); } return result; } function _finally(result) { if (undefined != finallyHandler) { result = finallyHandler(result); } return result; } var self = this; /** * compose - Returns a new handler composed of this and h * @param {Handler} h * @returns {Handler} */ this.compose = function(h) { return new ComposedHandler(self, h); } /** * handle - handles the provided computation * @param {thunk} the computation */ this.handle = function(thunk) { var saved = []; var finalized = false; var finalizing = false; var abort; function installHandler(op, h) { op.handler = function() { return function(opCall) { var returned = false; // operation's arguments var args = opCall.args; // operation's continuation var k = opCall.k; var called = false; var applyCont = function(v) { // apply the operation's continuation //var result = k(v); called = true; var result = k(arguments[0]); // hack: workaround tailspin bug if (!returned) { // return now if we haven't already result = _return(result); } return result; } var result = h.apply(resource, args.concat(applyCont)); // fell thru - continuation not called returned = true; if (!finalizing) { finalizing = true; result = _finally(result); finalized = true; } if (finalized && !called) { // continuation was never called, jump to end of handle abort(result); } return result; } } } // install handlers for (var i = 0; i < ops.length; i++) { var op = ops[i]; saved.push(op.handler); var h = hs[i]; installHandler(op, h); } // perform handling var result = metaCont.shift(function(k) { abort = k; var result = metaCont.reset(function() { var result = thunk(); result = _return(result); return result; }); return k(result); }); // perform finally if (!finalized) { result = _finally(result); } // restore previous handlers for (var i = 0; i < saved.length; i++) { ops[i].handler = saved[i]; } return result; } } } this.toString = function() {return "[Object Eff]"} } function print(x) { console.log(x) } var exit = new Continuation(); var Eff = new Effects(); // An effect which makes a binary choice var Choice = Eff.createEffect("choice"); var decide = Choice.createOperation("decide"); function choice() { var x = decide() ? 40 : 10; var y = decide() ? 0 : 2; return x + y; } var chooseAll = { "return": function(x) { return [x] }, "decide": function(k) { var xs = k(true); var ys = k(false); return xs.concat(ys); } } var h = Choice.createHandler(chooseAll); print(h.handle(choice)); // prints 40,42,10,12 // Exceptions effect var Exceptions = Eff.createEffect("exception"); var raise = Exceptions.createOperation("raise"); function Option() { } function None() { this.prototype = new Option(); this.getOrElse = function(x) { return x } this.toString = function() {return "none"} } function Some(x) { this.prototype = new Option(); this.getOrElse = function(_) { return x } this.toString = function() {return "some: "+JSON.stringify(x)} } var none = new None(); function some(x) { return new Some(x) } var Exit = Exceptions.createHandler({ "raise": function(e, k) { print("caught: "+e); exit(); } }); var Optionalize = Exceptions.createHandler({ "return": function(v) { return some(v) }, "raise": function(v, k) { return (none) } }); var result = Optionalize.handle(function() { return 42 }); print(result); // prints some: 42 result = Optionalize.handle(function() { raise("foo"); return 42 }); print(result); // prints none // State effect var State = Eff.createEffect("state"); var get = State.createOperation("get"); var set = State.createOperation("set"); function state(x) { return { "return": function(v) { return function(s) { return v; } }, "get": function(k) { return function(s) { return k(s)(s) } }, "set": function(v, k) { return function(s) { return k()(v) } }, "finally": function(f) { var r = f(x); return r; } }; } var h = State.createHandler(state(20)) result = h.handle(function() { var q = get(); set(q + 11); var q2 = get(); return q2; }); print(result); // prints 31 // Transactional state function transaction(x) { return { "return": function(v) { return function(s) { return x.value = v; } }, "get": function(k) { return function(s) { return k(s)(s) } }, "set": function(v, k) { return function(s) { return k()(v) } }, "finally": function(f) { var r = f(x.value); return r; } }; } var v = {value: 29}; var Transact = State.createHandler(transaction(v)); result = Optionalize.handle(function() { return Transact.handle(function() { var q = get(); set(q + 11); raise("foo"); var q2 = get(); return q2; }); }); print(result); // prints none print(v.value); // prints 29 h = Optionalize.compose(Transact); // combined handlers - same effect as above result = h.handle(function() { var q = get(); set(q + 11); var q2 = get(); return q2; }); print(result); // prints some: 40 print(v.value); // prints 40 /** * Simulation of Eff Resources - i.e. a default handler with state */ function Ref(v) { var eff = Eff.createEffect(); this.get = eff.createOperation("get"); this.set = eff.createOperation("set"); this.createHandler = eff.createHandler; // state var resource = {value: v}; // create a default handler var h = eff.createDefaultHandler({ get: function(k) { k(resource.value); }, set: function(v, k) { resource.value = v; k(); } }); this.handle = h.handle; this.compose = function(h1) { return new Eff.ComposedHandler(h, h1); } } var ref = new Ref(20); print(ref.get()); // prints 20 ref.handle(function() { print(ref.get()); // prints 20 ref.set(99); print(ref.get()); // prints 99 }); print(ref.get()); // prints 99 h = ref.createHandler({ get: function(k) { k(-1); } }); h.handle(function() { print(ref.get()); // prints -1 ref.handle(function() { print(ref.get()); // prints 99 ref.set(101); }); print(ref.get()); // prints -1 }); print(ref.get()); // prints 101 // Delimited continuations function testDelimitedControl() { var Delimited = Eff.createEffect(); var shift = Delimited.createOperation("shift"); var reset = Delimited.createHandler({ shift: function(f, k) { return f(k) } }).handle; print(reset(function() { return shift(function(k) { return k(k(k(7))) }) * 2 + 1; })); // prints 63 } testDelimitedControl();