Higher-order function of recursive functions?

Question

Is there some way to "wrap" a recursive function via a higher-order function, so that the recursive call is also wrapped? (e.g. to log the arguments to the function on each call.)

For example, suppose we have a function, sum(), that returns the sum of a list of numbers by adding the head to the sum of the tail:

function sum(a) {
    if (a.length === 0) {
        return 0;
    } else {
        return a[0] + sum(a.slice(1));
    }
}

Is there some way to write a higher-order function, logging(), that takes the sum() function as input, and returns a function that outputs the arguments to sum() on each recursive call?

The following does not work:

function logging(fn) {
    return function(a) {
        console.log(a);
        return fn(a);
    }
}

sum2 = logging(sum);
sum2([1, 2, 3]);

Actual output:

[1, 2, 3]
-> 6

Expected output:

[1, 2, 3]
[2, 3]
[3]
[]
-> 6

Is this even possible if sum() is rewritten so that it can be used with Y Combinator-style "recursion"?

function sum_core(g) {
    return function (a) {
        if (a.length === 0) {
            return 0;
        } else {
            return a[0] + g(a.slice(1));
        }
    };
}

sum = Y(sum_core);
sum([1, 2, 3]);
// -> 6

Answer 1

Let's start backwards. Say you want a function traceSum:

> traceSum([1, 2, 3]);
[1, 2, 3]
[2, 3]
[3]
[]
6

You could implement traceSum as follows:

function traceSum(a) {
    console.log(a);
    if (a.length === 0) return 0;
    else return a[0] + traceSum(a.slice(1));
}

From this implementation we can create a generalized trace function:

function trace(f) {
    return function (a) {
        console.log(a);
        return f(trace(f), a);
    };
}

This is similar to the way the Y combinator is implemented in JavaScript:

function y(f) {
    return function (a) {
        return f(y(f), a);
    };
}

Your traceSum function can now be implemented as:

var traceSum = trace(function (traceSum, a) {
    if (a.length === 0) return 0;
    else return a[0] + traceSum(a.slice(1));
});

Unfortunately if you can't modify the sum function then you can't trace it since you need some way to specify which function to callback dynamically. Consider:

function sum(a) {
    if (a.length === 0) return 0;
    else return a[0] + sum(a.slice(1));
}

You cannot trace the above function because inside the function sum will always refer to the function itself. There's no way to specify the value of sum dynamically.

Answer 2

I know this is kind of a non-answer but what you want is much easier to do if you use objects and dynamically dispatched methods. Essentially, we store "rec" in a mutable cell instead of having to pass it around.

It would be kind of similar to sum = logging(sum) (instead of sum2 =) but is more idiomatic and doesn't hardcode the name for the mutable reference we dispatch on.

var obj = {
  sum : function(a){
    if (a.length === 0) {
      return 0;
    } else {
      return a[0] + this.sum(a.slice(1)); // <-- dispatch on `this`
    }
  }
}

function add_logging(obj, funcname){
   var oldf = obj[funcname];
   obj[funcname] = function(/**/){
     console.log(arguments);
     return oldf.apply(this, arguments);
   }
}

add_logging(obj, 'sum');

Answer 3

function sum(a) {
    if (a.length === 0) {
        return 0;
    } else {
        return a[0] + sum(a.slice(1));
    }
}

var dummySum = sum, sum = function(args) {
    console.log(args);
    return dummySum(args);
};
console.log(sum([1, 2, 3]));

Output

[ 1, 2, 3 ]
[ 2, 3 ]
[ 3 ]
[]
6

Answer 4

If you insist on using regular functions without using "this", the only way I can think of is applying the logging combinator before you tie the knot with the recursion (Y) combinator. Basically, we need to use dynamic dispatching in the logger just like we used dynamic dispatching in the sum function itself.

// f: function with a recursion parameter
// rec: function without the recursion parameter  

var sum = function(rec, a){
  if (a.length === 0) {
    return 0;
  } else {
    return a[0] + rec(a.slice(1));
  }
};

var logging = function(msg, f){
  return function(rec, x){
    console.log(msg, x);
    return f(rec, x);
  }
}

var Y = function(f){
  var rec = function(x){
    return f(rec, x);
  }
  return rec;
}

//I can add a bunch of wrappers and only tie the knot with "Y" in the end:
console.log( Y(logging("a", logging("b", sum)))([1,2,3]) );

Output

a [1, 2, 3]
b [1, 2, 3]
a [2, 3]
b [2, 3]
a [3]
b [3]
a []
b []
6

We could also extend Y and logging to be variadic but it would make the code a bit more complicated.

Answer 5

If you cannot change the sum function

function sum(a) {
    if (a.length === 0) {
        return 0;
    } else {
        return a[0] + sum(a.slice(1));
    }
}

then it's impossible. Sorry

edit

Ugly but works. Don't do that ^^

function rest(a) {
console.log(a);
    sum(a, rest);
}

function sum(a, rest) {
    if (a.length === 0) {
        return 0;
    } else {
        return a[0] + rest(a.slice(1));
    }
}

But looks at http://www.nczonline.net/blog/2009/01/20/speed-up-your-javascript-part-2/

Search for memoizer, I'll read it too.

Answer 6

It is not possible in JavaScript without modifying the function. If you don't want the manual work, your best bet is something like that:

function logged(func){
    return eval("("+func.toString().replace(/function(.*){(.*)/g,"function$1{console.log(arguments);$2")+")");
};

Then you can use it like:

function sum(a) {
   if (a.length === 0) {
        return 0;
    } else {
        return a[0] + sum(a.slice(1));
    }
}

console.log(logged(sum)([1,2,3,4]));

Which outputs:

{ '0': [ 1, 2, 3, 4 ] }
{ '0': [ 2, 3, 4 ] }
{ '0': [ 3, 4 ] }
{ '0': [ 4 ] }
{ '0': [] }
10

logged itself is very slow because it recompiles the function (with eval), but the resulting function is as fast as if you defined it manually. So, use logged only once per function and you are fine.

Answer 7

Scope issue. Try to do the following:

function logging(fn) {
    var _fn = fn; // local cached copy
    return function(a) {
        console.log(a);
        return _fn(a);
    }
}