Thought Torrent - Fun with Functional JavaScript

My recent reading has included:

• The Secret Art of Futamura Projection
• Parenscript - Lisp dialect that compiles to JavaScript
• Continuations in Mozilla
• Continuations for Curmudgeons

As a result, I'm in a very functional mood now, particularly with regard to JavaScript. I was considering making the "Continuations in Mozilla" code cleaner, but I don't think it's possible with the current language.

I'm going to put everything into a "class," for namespace cleanliness:

function Currier(){};
// instantiate one for demonstration
var c = new Currier();

A lot of this code needs to save and load arguments, passing them to some function. This is a real pain in the ass to do with variable numbers of arguments. So, let's get that out of the way first:

Currier.prototype.callFuncWithArr = function(func, args) {
  // this approach:
  // 1) avoids the overhead of uneval-ing each arg and then eval-ing it
  // 2) makes it work with native junk
  var toeval = [];
  for(var i = 0; i < args.length; i++) {
    toeval.push("args[" + i + "]");
  }
  return eval("func(" + toeval.join(", ") + ");");
}

// example
function foo(str1, str2) {
  return str1 + str2;
}
c.callFuncWithArr(foo, ["hello ", "world"]) // "hello world"

Partial evaluation - specializing functions by holding one or more of their arguments constant
Next, let's write a simple function for "partial evaluation." The term is in quotes because unlike a real partial evaluator, this just saves some parameters and passes them later. Very ghetto. This first version just handles saving the first n arguments, to keep things simple:

Currier.prototype.simplePartialEval = function(func) {
  // save callFuncWithArr
  var cfwa = this.callFuncWithArr;
  // save the current arguments to an array
  var args = [];
  // start at 1 to ignore func
  for(var i = 1; i < arguments.length; i++) {
    args.push(arguments[i]);
  }
  // return a closure that calls func with the saved arguments,
  // plus whatever else was passed in
  return function() {
    for(var i = 0; i < arguments.length; i++) {
      args.push(arguments[i]);
    }
    return cfwa(func, args);
  }
}

// example
function test1(x, y, z) {
  return x + y + z;
}

var tmp = c.simplePartialEval(test1, 20, 1);
tmp(3); // 24

The following version is more general, and therefore more complicated. It lets you specify which arguments you want to save. For example, you could specify the fourth argument now and pass the other three later. I could re-write the simple version using this, but I don't think it's worth it.

Currier.prototype.partialEval = function(func, args) {
  var cfwa = this.callFuncWithArr;
  return function() {
    var newArgs = [];
    var i = 0;
    for(i = 0; i < arguments.length ; i++) {
      while(newArgs.length in args) { newArgs.push(null); }
      newArgs.push(arguments[i]);
    }
    for(var p in args) {
      while(newArgs.length < p) { newArgs.push(null) }
      newArgs[p] = args[p];
    }
    return cfwa(func, newArgs);
  }
}

// example
function test2(x, y, z) {
  return x - y - z;
}

var tmp = c.partialEval(test2, {1: 3});
println(tmp(8, 4)); //  1

Currying - transforming a multi-argument function into a sequence of one argument functions
Combining some of the ideas above with some stack inspection produces a fun auto-curry function. Any function can call it to delay evaluation until the required number of arguments is met. Technically, currying only allows one argument per call and this will take none or several.

Currier.prototype.autocurry = function() {
  var par = this.autocurry.caller;
  if(par && par.arguments.length < par.length) {
    var toeval = [""];
    for(var i = 0; i < par.arguments.length; i++) {
      toeval.push("par.arguments[" + i + "]");
    }
    return eval("this.simplePartialEval(par" + toeval.join(", ") + ");");
  } else {
    return null;
  }
}

// example
function test3(x, y, z) {
  // reusing the global Currier c since it's there
  var tmp = c.autocurry();
  if(tmp) { return tmp; }
  return x + y + z;
}

var r = test3();
r = r(1)
r = r(5);
println(r(7)); // 13
var r = test3();
r = r(1);
r = r(2);
println(r(3)); // 6

Y Combinator - generate recursive anonymous functions

Currier.prototype.Ycombinator = function(X) {
  return (function(procedure) {
   return X(function(arg) {
     return (procedure(procedure))(arg);
   })})(function(procedure) {
   return X(function(arg) {
     return (procedure(procedure))(arg);
   })}
   )
};

// example
(c.Ycombinator(
  // factorial
  function (func_arg) {
    return function(n) {
      if(n == 0) {
        return 1;
      } else {
        return n * func_arg(n-1);
      }
    }
  }
))(5)

It's the applicative order one, nicely explained in this tutorial. I've included each step from the tutorial in (source of) the demo/test page. I also copy and pasted all the code from "Continuations in Mozilla" so you can see it run (okay, I did it for myself, I admit it).

Compatability notes:

• callFuncWithArr(), simplePartialEval(), and partialEval() require that the interpreter provide the arguments object (JS 1.5)
• autocurry() uses the proprietary caller, so it probably won't work outside of Spidermonkey (Firefox, Mozilla, etc.)
• Ycombinator() should work everywhere because it just uses closures.