Skip to content

Instantly share code, notes, and snippets.

@unktomi

unktomi/Effects.js

Created December 2, 2015 20:34
Show Gist options
  • Save unktomi/98f64e8ceedcb0342fb8 to your computer and use it in GitHub Desktop.
Save unktomi/98f64e8ceedcb0342fb8 to your computer and use it in GitHub Desktop.
Download ZIP

Revisions

  1. unktomi created this gist Dec 2, 2015.
    323 changes: 323 additions & 0 deletions Effects.js
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,323 @@
    /**
    * Algebraic Effects and Handlers as in <a href='http://www.eff-lang.org/'>Eff</a>
    */

    'use strict'
    //
    // Note:
    // new Continuation() - returns the current function's continuation.
    //

    function callcc(f) {
    return f(new Continuation())
    }

    /**
    * Implementation of delimited continuation operators given by Filinski
    */

    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;

    /**
    * Creates a new Effect
    * @param {string} effect - Name of this effect
    * @returns {Effect}
    */
    this.createEffect = function(effect) {
    return new Effect(effect);
    }

    /**
    * Factory to create operations and handlers:
    */
    function Effect(effect) {

    /**
    * 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
    * @returns {function}
    */

    this.createHandler = function(handlers) {
    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;
    }
    ops.push(op);
    hs.push(h);
    }
    }
    return new Handler(returnHandler, finallyHandler, ops, hs);
    }

    // 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) {
    function _return(result) {
    if (undefined != returnHandler) {
    result = returnHandler(result);
    }
    return result;
    }
    function _finally(result) {
    if (undefined != finallyHandler) {
    result = finallyHandler(result);
    }
    return result;
    }
    this.handle = function(thunk) {
    var saved = [];
    var finalized = false;
    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 applyCont = function(v) {
    // apply the operation's continuation
    //var result = k(v);
    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(null, args.concat(applyCont));
    // fell thru - continuation not called
    returned = true;
    if (!finalized) {
    finalized = true;
    result = _finally(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.reset(function() {
    var result = thunk();
    result = _return(result);
    return 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;
    }
    }

    }
    }

    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