javascript advanced

  1. recursion
  2. Church
  3. Curry
  4. CPS
  5. .apply and .call (FP)
  6. monads
  7. combinators

  8. js
  9. node

recursion

var n = 0 ;
var rfun = function (i , k)
{
  if (i <= k) { n = n + i ; rfun (++i , k) ; }
  else        { print (n) ;                  }
}

js> load ("recur.js")
js> rfun (1,10);
55
js>


Church

an anonymous, self-invoking function (aka lambda) it's really quite powerful


  js> var a = 5;
  js> var b = 6;
  js> var x = (function() { return a + b; })();
  js> print(x);
   11

we wrap a function in parenthesis and then add in the argument parenthesis. when interpretator comes across this line it will execute the function and put the return value in x. the function existed only long enough to generate 11 and give it to x then it's gone

lets say we have an anonymous factorial function and we want to do it recursively. how do we call a function without a name? well in Javascript the arguments.callee property contains a pointer to the currently executing function which means an anonymous function can, indeed, call itself:


  js> print( (function(n) {
    if (n <= 1) { return 1; }
    else        { return n * arguments.callee(n - 1); }
  })(10));
   3628800


Curry


  function add(a, b) {
    if (arguments.length < 1) {
      return add;
    }
    else if (arguments.length < 2) {
      return function(c) { return a + c; }
    }
    else {
      return a + b;
    }
  }

watch:


  $> js
  js> load("curry.js");
   function load() {[native code]}
  js> add(1,2);
   3
  js> var b = add(1);
  js> b(2);
   3
  js> var c = add();
  js> var d = c(1);
  js> d(2);
   3


continuation-passing style

without CPS:


  function doThing(x) {
    print("doing " + x);
  }

  function doLoop(k) {
    for (i = 1; i < k + 1; i++) doThing(i);
  }

with CPS:


  function doSmth(x, cc) {
    print("doing " + x);
    cc();
  }

  function doIt(k) {
    doWith(1, k);

    function doWith(i, k) {
      if (i < k + 1) doSmth(i, function() { doWith(i + 1, k); });
    }
  }

now:


  js> load("cc.js");
   function load() {[native code]}
  js> doLoop(5);
   doing 1
   doing 2
   doing 3
   doing 4
   doing 5
  js> doIt(5);
   doing 1
   doing 2
   doing 3
   doing 4
   doing 5

the advantage of CPS is that at any point you can use setTimeout() to delay execution of the rest, or wait for user input to be processed


.apply and .call - FP context of JS

every function in JavaScript has a number of attached methods, including .toString (), .call (), and .apply ()

if it sounds odd to you that a function might have its own methods - then remember that every function in JavaScript is an object


var foo = function () {
  this.a = 'Hellow ';
};

var bar = function () {
  foo.apply (this);
  this.b = 'World!'
};

var x = new bar;
x.a + x.b         // 'Hellow World!'

the only difference between call and apply is the manner in which additional arguments are passed

so far the function has taken no arguments using call and apply is exactly the same


var Bob   = { name:"Bob",   age:23, };
var Alice = { name:"Alice", age:32, };

var f = function (x) { "Hi, " + x.name + ", I'm " + this.name; };

f.call (Bob,   Alice);       // "Hi, Alice, I'm Bob"
f.call (Alice, Bob  );       // "Hi, Bob, I'm Alice"

f.apply (Bob,   [ Alice ]);  // "Hi, Alice, I'm Bob"
f.apply (Alice, [ Bob   ]);  // "Hi, Bob, I'm Alice"

notice how the second argument in the apply examples are in brackets. while call accepts an arbitrary number of arguments (the this object followed by any number of args), apply() takes exactly two: the this object and an array of arguments to pass

  • apply lets you invoke the function with arguments as an array
  • call requires the parameters be listed explicitly

    here's a good mnemonic:

  • _A_pply uses _A_rrays and _A_lways takes one or two _A_rguments
  • when you use _C_all you have to _C_ount the number of arguments

    we can use apply () to specify the this reference for an arbitrary target method, and also pass-through an argument list to that target method via the arguments identifier

    it might have looked like the functions were hard-wired to the this object, but then it turned out that the functions can be used by other objects as effectively. isn't that a drastic paradigm shift from OOP?

    in OOP you have objects with tightly bound methods, in this case (functional programming) you have functions that can be tapped by any object and this object can use them as if they were truly its methods!

    that is the magic of apply () and call (). they both can change the context of this and make functions usable by different objects. they allow you to execute functions as methods of different objects


    monads (author - "The If Works")

    Translation from Haskell to JavaScript of selected portions of the best introduction to monads I’ve ever read

    (With apologies to John Gruber and A Neighborhood of Infinity.)

    Monads are more prevalent in Haskell because it only allows pure functions, that is functions that do not have side effects. Pure functions accept input as arguments and emit output as return values, and that’s it. The typical monad introduction will tell you that monads are all about sneaking side effects into this model so you can do I/O, but that’s just one application. Monads are really about composing functions, as we’ll see.

    Suppose you have a function for finding the sine of a number, which in JavaScript would be a simple wrapper around the Math library:

    var sine = function (x) { return Math.sin (x) };

    And you have another function for taking the cube of a number:

    var cube = function (x) { return x * x * x };

    These functions take a number as input and return a number as output, that making them composable: you can use the output of one as the input to the next:

    var sineCubed = cube (sine (x));

    Let’s create a function to encapsulate function composition. This takes two functions f and g and returns another function that computes f (g (x)) :

    var compose = function (f, g) {
      return function (x) {
        return f (g (x));
      };
    };
    
    var sineOfCube = compose (sine, cube);
    var y = sineOfCube (x);

    Next we decide that we need to debug these functions, and we want to log the fact that they have been called. We might do this like so:

    var sine = function (x) {
      console.log ('sine was called.');
      return Math.sin (x);
    };
    
    var cube = function (x) {
      console.log ('cube was called.');
      return x * x * x;
    };

    But we’re not allowed to do this in a system that only allows pure functions: console.log () is neither an argument nor a return value of the function, it is a side effect. If we want to capture this logging information, it must form part of the return value. Let’s modify our functions to return a pair of values - the result, and some debugging information:

    var sine = function (x) { return [Math.sin (x), 'sine was called.']; };
    
    var cube = function (x) { return [x * x * x, 'cube was called.']; };

    But we now find, to our horror, that these functions don’t compose:

    cube (3) // -> [27, 'cube was called.']
    compose (sine, cube)(3) // -> [NaN, 'sine was called.']

    This is broken in two ways: sine is trying to calculate the sine of an array, which results in NaN, and we’re losing the debugging information from the call to cube. We’d expect the composition of these functions to return the sine of the cube of x, and a string stating that both cube and sine were called:

    compose (sine, cube)(3)
    // -> [0.956, 'cube was called.sine was called.']

    A simple composition won’t work here because the return type of cube (an array) is not the same as the argument type to sine (a number). A little more glue is required.

    We could write a function to compose these ‘debuggable’ functions: it would break up the return values of each function and stitch them back together in a meaningful way:

    var composeDebuggable = function (f, g) {
      return function (x) {
        var gx = g (x),      // e.g. cube (3)  -> [27, 'cube was called.']
            y  = gx[0],      //                   27
            s1 = gx[1],      //                   'cube was called.'
            fy = f (y),      //      sine (27) -> [0.956, 'sine was called.']
            z  = fy[0],      //                   0.956
            s2 = fy[1];      //                   'sine was called.'
        
        return [ z, s1 + s2 ];
      };
    };
    
    composeDebuggable (sine, cube)(3)
    // -> [0.956, 'cube was called.sine was called.']

    We’ve composed two functions that take a number and return a number+string pair, and created another function with the same signature, meaning it can be composed further with other debuggable functions.

    To simplify things, I’m going to need to borrow some Haskell notation. The following type signature says that the function cube accepts a number and returns a tuple containing a number and a string:

    cube :: Number -> (Number,String)

    This is the signature that all our debuggable functions and their compositions have.

    Our original functions had the simpler signature Number -> Number; the symmetry of the argument and return types is what makes these functions composable. Rather than writing customized composition logic for our debuggable functions, what if we could simply convert them such that their signature was:

    sine, cube :: (Number,String) -> (Number,String)

    We could then use our original compose function for glueing them together.

    We could do this conversion by hand, and rewrite the source for cube and sine to accept (Number,String) instead of just Number but this doesn’t scale, and you end up writing the same boilerplate in all your functions.

    Far better to let each function just do its job, and provide one tool to coerce the functions into the desired format. We’ll call this tool bind, and its job is to take a Number -> (Number,String) function and return a (Number,String) -> (Number,String) function.

    var bind = function (f) {
      return function (a) {
        var x  = a[0],
            s1 = a[1],
            fx = f (x),
            y  = fx[0],
            s2 = fx[1];
        
        return [ y, s1 + s2 ];
      };
    };

    We can use this to convert our original functions to have composable signatures, and then compose the results:

    var f = compose (bind (sine), bind (cube));
    f ([3, '']);             // -> [0.956, 'cube was called.sine was called.']

    But now all the functions we’re working with take (Number,String) as their argument, and we’d much rather just pass a Number. As well as converting functions, we need a way of converting values to acceptable types, that is we need the following function:

    unit :: Number -> (Number,String)

    The role of unit is to take a value and wrap it in a basic container that the functions we’re working with can consume. For our debuggable functions, this just means pairing the number with a blank string:

    // unit :: Number -> (Number,String)
    var unit = function (x) { return [x, ''] };
    
    var f = compose (bind (sine), bind (cube));
    
    f (unit (3));           // -> [0.956, 'cube was called.sine was called.']
                            // or ...
    compose (f, unit)(3);   // -> [0.956, 'cube was called.sine was called.']

    This unit function also lets us convert any function into a debuggable one, by converting its return value into an acceptable input for debuggable functions:

    // round :: Number -> Number
    var round = function (x) { return Math.round (x) };
    
    // roundDebug :: Number -> (Number,String)
    var roundDebug = function (x) { return unit (round (x)) };

    Again, this type of conversion, from a ‘plain’ function to a debuggable one, can be abstracted into a function we’ll call lift. The type signature says that lift takes a function with signature Number -> Number and returns a function with signature Number -> (Number,String)

    // lift :: (Number -> Number) -> (Number -> (Number,String))
    var lift = function (f) {
      return function (x) { return unit (f (x)); };
    };
    
    // or, more simply:
    var lift = function (f) { return compose (unit, f) };

    Let’s try this out with our existing functions and see if it works:

    var round = function (x) { return Math.round (x) };
    
    var roundDebug = lift (round);
    
    var f = compose (bind (roundDebug), bind (sine));
    f (unit (9));              // -> [0, 'sine was called.']

    We’ve discovered three important abstractions for glueing debuggable functions together:

    These abstractions (well, really just bind and unit), define a monad. In the Haskell standard library it’s called the Writer monad.

    So what is a monad? Well, it’s a design pattern. It says that whenever you have a class of functions that accept one type of thing and return another type of thing, there are two functions that can be applied across this class to make them composable:

    I should stress that this is very hand-waving imprecise definition that ignores the mathematical foundations of monads, which I don’t pretend to understand. But to someone doing the sort of programming I do, it’s a very useful design pattern to be aware of because it helps you spot accidental complexity: code that isn’t dealing directly with the problem at hand, but which is dealing with glueing data types together. Being able to spot and extract such boilerplate can radically improve the clarity of your code.

     

    * * *

    an expression such as product.offering.merchant.name is a pipe. it can be read as “get the value of product; and then get that value’s offering; and then get that value’s merchant; and then get that value’s name“. the dot says two things: (1) evaluate the expression (product) to its left, and then (2) use that as target for the projection function (['offering']) immediately to its right
      var product = ...,
      n = (((product||{}).offering||{}).merchant||{}).name ;
      if (n) displayMerchantName(n) ;
    

    we’ve made up a new construct, (object||{}).property , which is like object.property except that if you put a null in (as the value of object), you get null out (as the value of (object||{}).property). in effect, we’ve replaced dot’s interpretation of “and then”. the interpretation of object.property‘s “and then” includes “and if object is null, then error”. the interpretation of the new “and then” adds “and if object is null, evaluate to null”

    this construct, (object||{}).property, isn’t a monad. it isn’t a monad because it isn’t associative; and it isn’t associative because the property accessor (dot) isn’t either [dot isn't the morphism of a category]. (A.b).c isn’t the same as A.(b.c) — in fact, the latter isn’t even well formed

    however, the class of property projection functions — just the .b part — does form a category. if you consider just the .b.c.d part of A.b.c.d, it doesn’t make any difference whether you read it as “apply the ‘b’ projection, and then apply the application of the ‘d’ projection to the ‘c’ projection, to that”; or “apply the ‘c’ projection to the ‘b’ projection, and then apply the ‘d’ projection to that”


    combinators

    I combinator: \x . x

    
        I = function (x)
        {
          return x
        }; 

    S combinator: \x . \y . \z x . z (y z)

    
        S = function (x)
        {
          return function (y)
          {
            return function (z)
            {
              return x (z) (y (z))
            }
          }
        }; 

    K combinator: \x . \y . x

    
        K = function (x)
        {
          return function () { return x }
        } 

    Y combinator

    
        /*   Y  =  S (K(S(I)(I))) (S(S(K(S))(K)) (K(S(I)(I))))   */
    
    
        Y = function (f)
        {
           var run = function (x) { return f (function (y) { return (x (x)) (y)})}
           return run (run)
        }; 

    should test these lambda-distortions?


    js

    $> js 
    js> load ("filename.js")
    
    js> quit()
    

    node

    node — server-side JavaScript runtime

    execute node without arguments to start a REPL:

    $> node
    > .load filename
    > console.log('Hello, world');
    > .exit
    

    inside the REPL, Control+D will exit. multi-line expressions can be input. tab completion is supported for both global and local variables

    there are a few special REPL commands:
      .break - while inputting a multi-line expression, sometimes you get lost or just
               don't care about completing it. .break will start over
      .clear - resets the context object to an empty object and clears any multi-line expression
      .exit  - close the I/O stream, which will cause the REPL to exit
      .help  - show this list of special commands
      .save  - save the current REPL session to a file
    

    the following key combinations in the REPL have these special effects:


      var r = require ("readline");
      var p = r.createInterface (process.stdin, process.stdout);
      p.question ("How many?", function (x) {
        var m = "";
        if (x > 5) {
          m = "Great!";
        } else {
          m = "You should have at least " + (6 - x) + " more.";
        }
        console.log (m);
        process.exit ();
      });