One Y for Any Number of Arguments: version 4

We’ve had one example of applying the Y combinator to generate an anonymous recursive function of one argument: the factorial function. Then, we had another example of applying the Y combinator to generate an anonymous recursive function of two arguments: the tree-visitor pattern. In the two examples, the particular definition of Y was tailored to the specific number of arguments. This isn’t the end of the world, since the one-argument Y will work to generate any anonymous recursive function of one argument, and the two-argument Y will work to generate any anonymous recursive function of two arguments. But, will we need a three-argument Y, a four-argument Y, and so on? This is less than ideal, and we’d like to fix it.

So far, our shortest version of the Y combinator is the following:

(function (f) {
  return (function (g) {return g(g);}) 
    (function (h) {
      return f(function (n) {return h(h)(n);});});})

If we read this function out loud in just such a way, it recites its derivation concisely: “This is a function of f that returns another function applied to itself. Call this self-application ‘h(h)’. It returns f applied to a certain function of n — call it g. Now, f must be designed so that f(g) returns the function of n that does the user’s work and may, incidentally, call g. The particular g we supply applies h(h) to n. But h(h) is f(g), so h(h)(n) returns f(g) applied to n, just what we need to do the user’s work.”

As always, check that this works by opening a JavaScript console via F12 in the browser and copy-pasting an example of applying it, such as

(function (f) {
  return (function (g) {return g(g);}) 
    (function (h) {
      return f(function (n) {return h(h)(n);});});})
  (function (g) {return function (n) {return n<2 ? 1 : n*g(n-1);};})(13)

This works if f(g) is a function of a single argument, but suppose we have a complicated function like our tree-visit that takes multiple arguments, say a visitor function and a tree? One possibility, which we took before, is to rewrite the Y combinator to handle a two-argument function,such as, for instance, in the following:

(function (f) {
  return (function (g) {return g(g);}) 
      (function (h) {
        return f(function (visitor, tree) {return h(h)(visitor, tree);});});})
(function (visit) {
  return function(visitor, tree) {
    var result = {};
    if (tree.head) {
      result.head = visit(visitor, tree.head);
      result.args = [];
      for(var i = 0; i < tree.args.length; i++) {
        result.args.push(visit(visitor, tree.args[i]));
      }
    } else if (tree.sym) {
      result.sym = visitor(tree.sym);
    } else if (tree.const) {
      result.sym = visitor(tree.const);
    }
    return result;
  }
})(function (x) {console.log(x); return x;}, 
{ head: { sym: "Plus"},
  args: [ { const: 1 },
          { head: { sym: "Times"},
            args: [ { const: 2 },
                    { const: 3 } 
                  ] }
        ] })

Conceptually, we are “baking in” the signature of the desired anonymous, recursive function into our definition of the Y combinator. We have one version of Y that works for functions of one argument like the recursive factorial function and another version of Y that works for functions of two arguments like the recursive tree-visit function. We would need a different version of Y for recursive functions of each signature with some number of arguments.

The root of the problem is that we did not adequately separate the concerns of arity and anonymous recursion. The provenance of this inadequacy can be traced to Y’s legacy in functional programming where arity is not a dying concern due to ubiquitous Currying. But our world of ordinary programming does not freely support Currying, yet we need anonymous recursion. Let’s fix this.

Recall that the reason for the internal function of n is to “slow down” the self-application h(h). We can’t write

(function (f) {
  return (function (g) {return g(g);}) 
    (function (h) {return f(h(h));});})

because the internal computation of h(h), which happens at the time f is applied, will spin. We need to replace it with an explicit function that computes h(h) just once each time it’s needed. We “jumped the gun” and tailored the combinator to an explicit function of a single argument. Granted it’s general enough to work on ANY function of a single argument, but suppose we want h(h) = f(g) to take multiple arguments? There are a few potential ways out of this: perhaps using JavaScript’s apply or call primitives? But let’s do something else.

Suppose that f were designed so that it takes a function of NO arguments — this is pretty general. But now this function, g, of no arguments must be designed so that when it’s applied internally, in the body of f(g), it must be evaluated on no arguments, just once, like this: g(). In other words, we must write our victim function f not in the old way, as

function (g) {return function (n) {return n<2 ? 1 : n*g(n-1);};}

but as

function (g) {return function (n) {return n<2 ? 1 : n*g()(n-1);};}

and not as

(function (g) {
  return function(visitor, tree) {
    var result = {};
    if (tree.head) {
      result.head = g(visitor, tree.head);
      result.args = [];
      for(var i = 0; i < tree.args.length; i++) {
        result.args.push(g(visitor, tree.args[i]));
      }
    } else if (tree.sym) {
      result.sym = visitor(tree.sym);
    } else if (tree.const) {
      result.sym = visitor(tree.const);
    }
    return result;
  }
})

but as

(function (g) {
  return function(visitor, tree) {
    var result = {};
    if (tree.head) {
      result.head = g()(visitor, tree.head);
      result.args = [];
      for(var i = 0; i < tree.args.length; i++) {
        result.args.push(g()(visitor, tree.args[i]));
      }
    } else if (tree.sym) {
      result.sym = visitor(tree.sym);
    } else if (tree.const) {
      result.sym = visitor(tree.const);
    }
    return result;
  }
})

Wherever we used to write g, we must now write g(). And we must also change Y so that it applies f to a function that, when evaluated on no arguments, returns h(h):

(function (f) {
  return (function (g) {return g(g);})
    (function (h) {
      return f(function () {return h(h);});});})

Check that this works on our new-improved factorial function

(function (f) {
  return (function (g) {return g(g);})
    (function (h) {
      return f(function () {return h(h);});});})
  (function (g) {return function (n) {return n<2 ? 1 : n*g()(n-1);};})(13)

And check that EXACTLY the same Y works on our new-improved tree-visitor

(function (f) {
  return (function (g) {return g(g);})
    (function (h) {
      return f(function () {return h(h);});});})
(function (g) {
  return function(visitor, tree) {
    var result = {};
    if (tree.head) {
      result.head = g()(visitor, tree.head);
      result.args = [];
      for(var i = 0; i < tree.args.length; i++) {
        result.args.push(g()(visitor, tree.args[i]));
      }
    } else if (tree.sym) {
      result.sym = visitor(tree.sym);
    } else if (tree.const) {
      result.sym = visitor(tree.const);
    }
    return result;
  }
})(function (x) {console.log(x); return x;}, 
{ head: { sym: "Plus"},
  args: [ { const: 1 },
          { head: { sym: "Times"},
            args: [ { const: 2 },
                    { const: 3 } 
                  ] }
        ] })
Advertisements

~ by rebcabin on August 3, 2012.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

 
%d bloggers like this: