memoize any given recursive function in JavaScript

Question

I am interested in the scenario where we have some function f which is recursive and which we are not provided the source code to.

I would like a function memoizer: Function -> Function which takes in say f and returns a function g such that g = f (in the sense they return the same value given the same arguments) which when called first checks if the called arguments are in its 'cache' (memory of results it has calculated before) and if so returns the result from this, otherwise it should compute f, should f call itself with some arguments, this is tantamount to calling g with those arguments and I would like that f first check if the cache of g contains those arguments and if so return the result from this, otherwise ...

This is easy (in Javascript) to do given the source code of f, I simply define memoize in the obvious way and do something like

let f = memoize((...args) => {/* source code of f */});

But this doesn't appeal to me at all (mainly because I might want a memoized and non memoized version of the same function and then I'd have to write the same function twice) and won't work if I don't know how to implement f.

In case it's not clear what I'm asking,

I would like a function memoize which takes a function such as

fact = n => n === 0 ? 1 : n * fact(n - 1);

And returns some new function g such that fact(n) = g(n) for all n and which for example when g(10) is computed stores the values of fact(0), ..., fact(10) which are computed while computing g(10) and then if I ask for say g(7) it finds the result in the cache and returns it to me.

I've thought that conceptually it's possible to detect when f is called since I have it's address and maybe I could replace all calls to f with a new function where I compute f and store the result and then pass the value on to where it would normally go. But I don't know how to do this (and it sounds unpleasant).

Answer 1

For the main concern inner recursive call is not going to original function causing the memoize is not working as intended. If we can make original function to take additional argument as same function reference, it will simplify.

// adding "fib" as additional argument
function fib(n, fib) {
  if (n < 2) {
    return n;
  }
  return fib(n - 1) + fib(n - 2);
}

function memoize(fn, argIndex = 0) {
  const track = {};
  return function memFn(...args) {
    if (args[argIndex] in track) {
      console.log("cached value - ", args[argIndex]);
      return track[args[argIndex]];
    }
    console.log("actual call - ", args[argIndex]);
    return (track[args[argIndex]] = fn.call(this, ...args, memFn));
  };
}

const memFib = memoize(fib);

memFib(6);

For the scenario's where we dont have access to original function (fib in this case), We can use Function constructor to have wrapper function to original function to have additional argument.

function memoize(fn, argIndex = 0) {
  const track = {};
  const wrapFn = new Function(
    "return " + fn.toString().replace(")", `,${fn.name})`),
  )();
  return function memFn(...args) {
    if (args[argIndex] in track) {
      console.log("cached value - ", args[argIndex]);
      return track[args[argIndex]];
    }
    console.log("actual call - ", args[argIndex]);
    return (track[args[argIndex]] = wrapFn.call(this, ...args, memFn));
  };
}

function fib(n) {
  if (n < 2) {
    return n;
  }
  return fib(n - 1) + fib(n - 2);
}

const memFib = memoize(fib);

const result = memFib(6)

Answer 2

In my limited experience, we do have access to JavaScript source code. We could thus attempt to generate new source code for the memoized function.

// Redefine Function.prototype.bind
// to provide access to bound objects. 
// https://stackoverflow.com/questions/7616461/generate-a-hash-from-string-in-javascript
var _bind = Function.prototype.apply.bind(Function.prototype.bind);
Object.defineProperty(Function.prototype, 'bind', {
    value: function(obj) {
        var boundFunction = _bind(this, arguments);
        boundFunction.boundObject = obj;
        return boundFunction;
    }
});

// Assumes the parameters for the function,
// f, can be consistently mapped.
function memo(f){
  if (!(f instanceof Function))
    throw TypeError('Argument is not an instance of Function.');
    
  // Generate random variable names
  // to avoid conflicts with unknown
  // source code
  function randomKey(numBytes=8){        
      let ranges = [[48, 10], [65, 26], [97, 26]]; 
      let key = '_';

      for (let i=0; i<numBytes; i++){     
          let idx = Math.floor(Math.random() * ranges.length);
          key += String.fromCharCode(ranges[idx][0] + Math.random() * ranges[idx][1]);
      }   

      return key;
  }

  let fName = f.name;
  let boundObject;
  let fCode;
  
  const nativeCodeStr = '(){[nativecode]}';
  
  // Possible Proxy
  try {
    fCode = f.toString();

  } catch(error){
    if (error.constructor == TypeError){
      if (Function(`return ${ fName }.toString()`)() != nativeCodeStr){
        throw TypeError(`Possible Proxy detected: function has a name but no accessible source code. Consider memoizing the target function, ${ fName }.`);
      
      } else {
        throw TypeError(`Function has a name but no accessible source code. Applying toString() to its name, ${ fName }, returns '[native code]'.`);
      }
    
    } else {
      throw Error('Unexpected error calling toString on the argument.');
    }
  }

  if (!fName){
    throw Error('Function name is falsy.');

  // Bound functions
  // Assumes we've monkey-patched
  // Function.prototype.bind previously
  } else if (fCode.replace(/^[^(]+|\s+/g, '') == nativeCodeStr){
    if (/^bound /.test(fName)){
      fName = fName.substr(6);
      boundObject = f.boundObject;
      // Bound functions return '[native code]' for
      // their toString method call so get the code
      // from the original function.
      fCode = Function(`return ${ fName }.toString()`)();
    
    } else {
      throw Error("Cannot access source code, '[native code]' provided.");
    }
  }

  const fNameRegex = new RegExp('(\\W)' + fName + '(\\W)', 'g');
  const cacheName = randomKey();
  const recursionName = randomKey();
  const keyName = randomKey();

  fCode = fCode.replace(/[^\(]+/,'')
    .replace(fNameRegex, '$1' + recursionName + '$2')
    .replace(/return/g, `return ${ cacheName }[${ keyName }] =`)
    .replace(/{/, `{\n  const ${ keyName } = Array.from(arguments);\n\n  if (${ cacheName }[${ keyName }])\n    return ${ cacheName }[${ keyName }];\n`);
  
  const code = `function(){\nconst ${ cacheName } = {};\n\nfunction ${ recursionName + fCode }\n\nreturn ${ recursionName }.apply(${ recursionName }, arguments);}`;

  let g = Function('"use strict";return ' + code)();

  if (boundObject){
    let h = (g).bind(boundObject);
    h.toString = () => code;
    return h;

  } else {
    return g;
  }
} // End memo function


function fib(n) {
  if (n <= 1) return 1;
  return fib(n - 1) + fib(n - 2);
}

const h = fib.bind({a: 37});
const g = memo(h);
   
console.log(`g(100): ${ g(100) }`);
console.log(`g.boundObject:`, g.boundObject);
console.log(`g.toString():`, g.toString());

try{ 
  memo(function(){});

} catch(e){
  console.log('Caught error memoizing anonymous function.', e)
}

const p = new Proxy(fib, {
  apply: function(target, that, args){
    console.log('Proxied fib called.');
    return target.apply(target, args);
  }
});

console.log('Calling proxied fib.');
console.log(`p(2):`, p(2));

let memoP;

try {
  memoP = memo(p);
  
} catch (e){
  console.log('Caught error memoizing proxied function.', e)
}

Answer 3

maybe I could replace all calls to f with a new function where I compute f and store the result and then pass the value on to where it would normally go.

This is actually very easy to do, as Bergi referred to in a comment.

// https://stackoverflow.com/questions/24488862/implementing-automatic-memoization-returns-a-closured-function-in-javascript/ 
function memoize(func) {
  var memo = {};
  var slice = Array.prototype.slice;

  return function() {
    var args = slice.call(arguments);

    if (args in memo)
      return memo[args];
    else
      return (memo[args] = func.apply(this, args));

  }
}

function fib(n) {
  if (n <= 1) return 1;
  return fib(n - 1) + fib(n - 2);
}

fib = memoize(fib);

console.log(fib(100));

Answer 4

I might want a memoized and non memoized version of the same function and then I'd have to write the same function twice

Yes, you need to. The recursive call to fact(n - 1) inside the function can only refer to one fact function - either a memoized or an unmemoized one.

So what you need to do to avoid code duplication is define fact with the Y combinator:

const makeFact = rec => n => n === 0 ? 1 : n * rec(n - 1);
//               ^^^                           ^^^

const factA = Y(makeFact);
const factB = memoizingY(makeFact);

function Y(make) {
    const f = make((...args) => f(...args)); // const f = make(f) is easier to understand
    return f;                                // but doesn't work with eager evaluation
}

I'll leave the definition of memoizingY as an exercise to the reader :-)

---

Possibly simpler approach:

const makeFact = annotate => {
    const f = annotate(n => n === 0 ? 1 : n * f(n - 1));
    return f;
}

const factA = makeFact(identity);
const factB = makeFact(memoize);