/**
* 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();