JFiddle Functional Reactive Program Engineering Challenge

fiddle.css

body {
    padding:0;
    font:15px/1.4 Arial, sans-serif;
    background:#e5e5e5;
}
p {
    margin:1.4em 0 0;
}
ol {
    margin-left: 1em;
    list-style-type: decimal;
}

#notes {
    font-size: small;
}

.container {
    /* See "NOTE 3" */
    position:relative;
    z-index:1;
    width:600px;
    padding:20px;
    margin:20px auto;
    background:#fff;
}
.container h1 {
    position:relative;
    padding:10px 30px;
    margin:0 -30px 20px;
    font-size:28px;
    line-height:32px;
    font-weight:bold;
    text-align:center;
    color:#fff;
    background:#1a2f5a;
    /* css3 extras */
    text-shadow:0 1px 1px rgba(0, 0, 0, 0.2);
    -webkit-box-shadow:0 1px 1px rgba(0, 0, 0, 0.2);
    -moz-box-shadow:0 1px 1px rgba(0, 0, 0, 0.2);
    box-shadow:0 1px 1px rgba(0, 0, 0, 0.2);
    /* See "NOTE 1" */
    zoom:1;
}
.container h1:before, .container h1:after {
    content:"";
    position:absolute;
    /* See "NOTE 2" */
    z-index:-1;
    top:100%;
    left:0;
    border-width:0 10px 10px 0;
    border-style:solid;
    border-color:transparent #647D01;
}
.container h1:after {
    left:auto;
    right:0;
    border-width:0 0 10px 10px;
}

fiddle.html

<div id="instruct" class="container">
    
<h1>Bubba's Engineering Challenge - FRP</h1>

   
    <p>
        For this challenge, we will build a <a target="_blank" href="http://en.wikipedia.org/wiki/Functional_reactive_programming">Functional Reactive System ("FRP")</a>, which allows us to declare <a target="_blank" href="http://conal.net/blog/posts/reactive-values-from-the-future">reactive values ("re-values")</a> that are dependent <em>only</em> on other
    re-values and/or on mutable values ("mu-values", imagine
    these being values stored in a database). Sort of like a
    generalized spreadsheet.

    This system should allow us to recompute re-values in an
    efficient manner when mu-values change.
</p>

<p>
    We start with the most naive implementation possible -- one
    in which re-values are always recomputed on every access.
    The code is structured in a way to measure a certain "cost"
    of computation based on the number of times a re-value is
    computed. The initial cost is 95 and your goal is to bring
    it down while preserving correctness. How low can it go?
</p>
<p>
    <b>Goal:</b>
    <ol>
        <li>Get the cost as low as possible. The initial cost is 95.</li>
    </ol>
</p>
<p>
    <b>Instructions:</b>
    <ol>
        <li>Fork this fiddle.</li>
        <li>In the HTML pane (top left) scroll to the bottom and move the results div to the top.</li>
        <li>Run the fiddle, you should see the output at the top of this pane instead of the instructions.</li>
        <li>Save the fiddle, which effectively forks it into your own user space.</li>
        <li>Modify the code in the JavaScript window to meet the challenge.</li>
    </ol>
</p>   
    
<p>
    <b>Notes:</b>
    <ol id="notes">
        <li>
            JSFiddle <b>does not</b> automatically save your
        file! If you refresh you <b>will</b> lose your work!
        Use 'Save' (to get your own fiddle) and then 'Update' to save the current version to your fiddle and get a new URL.
        </li>
    <li>
        This challenge is in Javascript mainly because JSFiddle makes
        it so easy. We tried to use as little Javascript syntax as
        reasonably possible. If you're new to Javascript, you
            might want to check out 
        <a target="_blank" href="https://developer.mozilla.org/en-US/docs/Web/JavaScript">
            Mozilla Developer Network: Javascript Documentation</a>.
       </li>
        <li>
            This is not a test of your knowledge of Javascript
        nor a test of the performance of your code. 
        </li>
        <li>
            We suggest that you make use of MooTools' extensions to
        <a target="_blank" href="http://mootools.net/docs/core/Types/Array">arrays</a>
        and
        <a target="_blank" href="http://mootools.net/docs/more/Types/Hash">hash tables</a>
        and ask that you refrain from using other Javascript
        libraries.
       </li>
    <li>
            We suggest you use
        <a target="_blank" href="http://google.com/chrome">Google Chrome</a>
        for this, since it has great
        <a target="_blank" href="http://code.google.com/chrome/devtools/docs/overview.html">
            developer tools</a>, such as the
        <a target="_blank" href="http://code.google.com/chrome/devtools/docs/console.html">
            developer console</a>.    
    </li>
    <li>
        Re-values should be assumed to be deterministic and have no
            side effects.
        </li>
        <li>
            We think you should be able to solve this by only
        changing the Javascript in this fiddle, but since
        we're trying to keep this question "real", if you feel
        that you'd suggest a change to SampleApp as well
        we'd be curious to hear about it as well.
        </li>
    <li>
        Please write your code as if you were to commit it.
        If you think there is more work that you could have
        done on it but are not sure if is worth the effort
        in advance, please leave a comment describing what
        future changes you were thinking about.
    </li>
    <li>
        This challenge was originally designed by <a target="_blank" href="https://asana.com/company">
        Asana</a> and they used it in their recruitment campaign. It fell into some disuse at Asana
        and when I asked them about it they encouraged me to fix the challenge and keep it going.
        </li>
        <li>
            To submit your solution, send a link to your fiddle and any other feedback to rob@stechstudio.com.
        </li>
   </ol>
</p>
</div>
         <!-- MOVE THIS TO THE TOP OF THE FILE -->
<div id="result" class="container">
    <h1>Your Results</h1>
    <div id="console"></div>
</div>

fiddle.js

FRP = {
    ///
    /// Mutable Values
    ///
    
    makeMuValue: function(initial_value) {
        return {
            is_mu_value: true,
            value: initial_value
        };        
    },
    
    changeMuValue: function(mu_value, new_value) {
        assert(FRP.isMuValue(mu_value));
        mu_value.value = new_value;
    },
        
    readMuValue: function(mu_value) {
        return mu_value.value;
    },

    isMuValue: function(lunar_value) {
        return lunar_value.is_mu_value;
    },
    
    ///
    /// Reactive Values
    ///
    
    /**
     * @param computeFunc {Function} A function that may compute
     *     other re-values and read other mu-values, returning
     *     the computed value of the created re-value
     */
    makeReValue: function(computeFunc) {
        return {
            is_re_value: true,
            computeFunc: computeFunc
        };
    },
    
    computeReValue: function(re_value) {
        return re_value.computeFunc();
    },

    isRvalue: function(xvalue) {
        assert(FRP.isReValue(mvalue));
        return xvalue.is_re_value;
    }
};

print = function(text) {
    if (text === undefined) {
        text = '';
    }

    document.body.appendChild(document.createTextNode(' ' + text));
    document.body.appendChild(document.createElement('br'));

    // If you have Firebug/Chrome Developer console log there as well.
    if (typeof console !== 'undefined' && typeof console.log !== 'undefined') {
        console.log(text);
    }
};

assert = function(val) {
    if (!val) {
        throw "Assertion Failure";
    }
};

/**
 * A sample reactive app (see the run function). 
 *
 * Creates 5 mu-values with initial values 0, 1, 2, 3, 4. 
 * Then creates 5 re-values calculating the partial sums of these 
 * mu-values, so that they compute to:
 * 0, 1, 3, 6, 10.
 *
 * These re-values are computed recursively.
 *
 * The app computes and prints all of the partial sum re-values 
 * several times, while changing some of the mu-values between
 * the runs.
 */
SampleApp = {
    /**
     * Used to keep track of a fake "cost" for computing rvalues. See 
     * calls to spend for details.
     */
    cost: 0,
    total_cost: 0,

    /**
     * Spend 1 "unit" of cost and add a dot to the page to indicate 
     * that.
     */
    spend: function() {
        document.body.appendChild(document.createTextNode('.'));
        SampleApp.cost += 1;
    },

    number_mu_values: [],
    partial_sum_re_values: [],

    setup: function() {
        for (var i = 0; i < 5; i++) {
            SampleApp.number_mu_values[i] = FRP.makeMuValue(i); 

            // NOTE: This is wrapped in a function because of a javascript
            // "quirk" with creating closures inside of for loops (though this
            // is essentially the case in any language with loops and closures)
            (function(i) {
                SampleApp.partial_sum_re_values[i] = FRP.makeReValue(function() {
                    SampleApp.spend();
                    if (i === 0) {
                        return FRP.readMuValue(SampleApp.number_mu_values[0]);
                    } else {
                        return FRP.readMuValue(SampleApp.number_mu_values[i]) + 
                            FRP.computeReValue(SampleApp.partial_sum_re_values[i-1]);
                    }
                });
            })(i);
        }
    },

    run_index: 1,

    printPartialSums: function() {
        print();
        print('Run #' + SampleApp.run_index);
        SampleApp.run_index++;
        
        var expected_partial_sum = 0;
        for (var i = 0; i < 5; i++) {
            expected_partial_sum += FRP.readMuValue(SampleApp.number_mu_values[i]);
            print(FRP.computeReValue(SampleApp.partial_sum_re_values[i]) + '; expected ' 
                + expected_partial_sum);    
        }

        print('Cost: ' + SampleApp.cost);
        SampleApp.total_cost += SampleApp.cost;
        SampleApp.cost = 0;
    },

    run: function() {
        SampleApp.setup();

        SampleApp.printPartialSums();   
        SampleApp.printPartialSums();   
        FRP.changeMuValue(SampleApp.number_mu_values[0], -10);
        SampleApp.printPartialSums();
        FRP.changeMuValue(SampleApp.number_mu_values[2], -10);
        FRP.changeMuValue(SampleApp.number_mu_values[4], -10);
        SampleApp.printPartialSums();
        FRP.changeMuValue(SampleApp.number_mu_values[0], -9);
        FRP.changeMuValue(SampleApp.number_mu_values[2], -11);
        SampleApp.printPartialSums();
        SampleApp.printPartialSums();
        
        print();
        print('Total cost: ' + SampleApp.total_cost);
    }
};

SampleApp.run();

fiddle.manifest

name: Bubba's FRP Engineering Challenge
description: For this challenge, we will build a Functional Reactive System ("FRP"), which allows us to declare reactive values ("re-values") that are dependent only on other re-values and/or on mutable values ("mu-values", imagine these being values stored in a database). Sort of like a generalized spreadsheet. This system should allow us to recompute re-values in an efficient manner when mu-values change.
authors:
  - Bubba Hines
normalize_css: yes

lib.js

print = function(text) {
    if (text === undefined) {
        text = '';
    }

    document.body.appendChild(document.createTextNode(' ' + text));
    document.body.appendChild(document.createElement('br'));

    // If you have Firebug/Chrome Developer console log there as well.
    if (typeof console !== 'undefined' && typeof console.log !== 'undefined') {
        console.log(text);
    }
};

assert = function(val) {
    if (!val) {
        throw "Assertion Failure";
    }
};

sample_app.js

/**
 * A sample reactive app (see the run function). 
 *
 * Creates 5 mu-values with initial values 0, 1, 2, 3, 4. 
 * Then creates 5 re-values calculating the partial sums of these 
 * mu-values, so that they compute to:
 * 0, 1, 3, 6, 10.
 *
 * These re-values are computed recursively.
 *
 * The app computes and prints all of the partial sum re-values 
 * several times, while changing some of the mu-values between
 * the runs.
 */
SampleApp = {
    /**
     * Used to keep track of a fake "cost" for computing rvalues. See 
     * calls to spend for details.
     */
    cost: 0,
    total_cost: 0,

    /**
     * Spend 1 "unit" of cost and add a dot to the page to indicate 
     * that.
     */
    spend: function() {
        document.body.appendChild(document.createTextNode('.'));
        SampleApp.cost += 1;
    },

    number_mu_values: [],
    partial_sum_re_values: [],

    setup: function() {
        for (var i = 0; i < 5; i++) {
            SampleApp.number_mu_values[i] = FRP.makeMuValue(i); 

            // NOTE: This is wrapped in a function because of a javascript
            // "quirk" with creating closures inside of for loops (though this
            // is essentially the case in any language with loops and closures)
            (function(i) {
                SampleApp.partial_sum_re_values[i] = FRP.makeReValue(function() {
                    SampleApp.spend();
                    if (i === 0) {
                        return FRP.readMuValue(SampleApp.number_mu_values[0]);
                    } else {
                        return FRP.readMuValue(SampleApp.number_mu_values[i]) + 
                            FRP.computeReValue(SampleApp.partial_sum_re_values[i-1]);
                    }
                });
            })(i);
        }
    },

    run_index: 1,

    printPartialSums: function() {
        print();
        print('Run #' + SampleApp.run_index);
        SampleApp.run_index++;
        
        var expected_partial_sum = 0;
        for (var i = 0; i < 5; i++) {
            expected_partial_sum += FRP.readMuValue(SampleApp.number_mu_values[i]);
            print(FRP.computeReValue(SampleApp.partial_sum_re_values[i]) + '; expected ' 
                + expected_partial_sum);    
        }

        print('Cost: ' + SampleApp.cost);
        SampleApp.total_cost += SampleApp.cost;
        SampleApp.cost = 0;
    },

    run: function() {
        SampleApp.setup();

        SampleApp.printPartialSums();   
        SampleApp.printPartialSums();   
        FRP.changeMuValue(SampleApp.number_mu_values[0], -10);
        SampleApp.printPartialSums();
        FRP.changeMuValue(SampleApp.number_mu_values[2], -10);
        FRP.changeMuValue(SampleApp.number_mu_values[4], -10);
        SampleApp.printPartialSums();
        FRP.changeMuValue(SampleApp.number_mu_values[0], -9);
        FRP.changeMuValue(SampleApp.number_mu_values[2], -11);
        SampleApp.printPartialSums();
        SampleApp.printPartialSums();
        
        print();
        print('Total cost: ' + SampleApp.total_cost);
    }
};