Getting clever with λ-calculus

[mateogianolio]

Originally posted 2015-12-18.

In this article we will delve into the depths of JavaScript lambda calculus and how it can help us increase both productivity and code brevity.

λ

Lambda calculus (also written as λ-calculus) is a formal system in mathematical logic for expressing computation based on function abstraction and application using variable binding and substitution.

The first requisite of lambda calculus is anonymous functions. JavaScript has featured these as long as I can remember.

function() {
  return 'I am anonymous.';
}

var f = function(x) {
  // anonymous function bound to a variable f
  return x * 2;
}

// anonymous functions can be mapped to an array
[1, 2, 3].map(function(x) { return x * 2; });
[1, 2, 3].map(f);

Anonymous functions can also be (and is extensively) used as closures.

The second simplification that lambda calculus offers is currying, which can be accomplished in JavaScript (see e.g. currying vs partial application). I won't go into detail, because at the time of writing I don't find currying very useful in JavaScript.

Arrow function

A big – well, at least in terms of brevity – problem with anonymous functions: It was necessary to type both function and return, which lead to space issues when passing the functions as function arguments.

Enter the arrow function. Mozilla Developer Network, the #1 JavaScript resource, has a great code snippet of the arrow function's syntax:

// Basic syntax:
(param1, param2, paramN) => { statements }
(param1, param2, paramN) => expression
   // equivalent to:  => { return expression; }

// Parentheses are optional when there's only one argument:
(singleParam) => { statements }
singleParam => { statements }

// A function with no arguments requires parentheses:
() => { statements }

// Advanced:
// Parenthesize the body to return an object literal expression:
params => ({foo: bar})

// Rest parameters are supported
(param1, param2, ...rest) => { statements }

Compare function (x) { return x; } (21 characters, not counting spaces) with x => x (4 characters).

The code

Long introduction? Let's get down to business. We'll build a wrapper to be able to pass arrow functions as arguments. To do this we need some knowledge about the function prototype.

We note that Function.prototype.toString() returns the source code of a function instance. I'll write the wrapper around nBLAS, a Node.js C++ binding I wrote for BLAS (Basic Linear Algebra Subsystems), but you can pick any library you want.

The aim with the wrapper is being able to use the following syntax:

// export is to be able to resolve variable names to variables
var a = exports.a = new Float64Array([1, 2]);
var b = exports.b = new Float64Array([3, 4]);

// addition
λ((a, b) => a += b); // a := [4, 6]
λ((a, b) => a + b); // [4, 6]

// dot product
λ((a, b) => a * b); // 36

// scaling
λ(a => a *= 5); // a:= [20, 30]
λ(a => a * 5); // [20, 30]

I have only implemented the above functionality for demonstrative purposes.

var nblas = require('nblas');

function λ(f) {
  // (a, b) => a + b to ['a,b', 'a+b']
  var args = f
    .toString()
    .replace(/[ \(\)]/g, '')
    .split('=>');

  // get vars from 'a,b', switch 'export' to 'window' for browser
  var vars = args
    .shift()
    .split(',')
    .map(arg => exports[arg])
    .reverse();

  args = args.join('');
  var tmp;

  // hook behaviour
  if (args.indexOf('+=') !== -1) {
    return nblas.axpy(...vars);
  } else if (args.indexOf('+') !== -1) {
    tmp = new vars[0].constructor(vars[1]);
    nblas.axpy(vars[1], tmp);
    return tmp;
  } else if (args.indexOf('*') !== -1) {
    if (vars.length === 2)
      return nblas.dot(...vars);

    if (args.indexOf('=') !== -1)
      return nblas.scal(...args.split('*='));

    tmp = new vars[0].constructor(vars[0]);
    nblas.scal(tmp, Number(args.split('*')[1]));
    return tmp;
  } else
    return f(...vars); // fallback to executing supplied function if no hook found
}

There you go, (kind of) operator overloading in JavaScript! To use the spread operator (...) you'll need to use babel or run the script with node --harmony. Otherwise you can switch f(...x) to f.apply(null, x).

Merry christmas and happy hacking.