A Tree Visitor with the Y Combinator in JavaScript

Now, for a real-worldish application of anonymous, recursive functions: consider a typical syntax tree as a JavaScript object. This one represents the expression “1 + 2 * 3” in prefix form, as “Plus[1, Times[2, 3]]”.

var myTree = 
{ head: { sym: "Plus"},
  args: [ { const: 1 },
          { head: { sym: "Times"},
            args: [ { const: 2 },
                    { const: 3 } 
                  ] }
        ] };

Now consider a typical recursive “visit” function that applies a visitor function, f, to any such tree:

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

Go ahead and paste these definitions in a JavaScript console, then try them out as follows:

visit(function (x) {console.log(x); return x;}, myTree);

Notice “visit” calls itself, by name, inside itself. This is a prescription for the Y combinator. We may need to apply a function like “visit” WITHOUT being allowed to define a symbol for it because a server won’t permit definitions to be added to its memory.

Remove the definition and rewrite “visit” as a function that takes “visit” as its first parameter and returns the function of f and tree as its result:

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

Now apply the Y combinator (which we can keyboard in from memory because we remember this prior blog post, this time with the internal arguments of h(h) promoted to a pair of arguments, namely the visitor function f and the tree).

Inline everything: the actual visitor function and the object representing the tree:

(function (f) {
  return (function (h) {
    return f(function (f, tree) {
      return h(h)(f, tree);});})
  (function (h) {
    return f(function (f, tree) {
      return h(h)(f, tree);});});})
(function (visit) {
  return function(f, tree) {
    var result = {};
    if (tree.head) {
      result.head = visit(f, tree.head);
      result.args = [];
      for(var i = 0; i < tree.args.length; i++) {
        result.args.push(visit(f, tree.args[i]));
      }
    } else if (tree.sym) {
      result.sym = f(tree.sym);
    } else if (tree.const) {
      result.sym = f(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 } 
                  ] }
        ] })

Yes, it really works!

Advertisements

~ by rebcabin on July 31, 2012.

One Response to “A Tree Visitor with the Y Combinator in JavaScript”

  1. […] to generate a recursive function of one argument: the factorial function. Then, we had another example of applying the Y combinator to generate a recurive function of two arguments: the tree-visitor pattern. In the two examples, the particular definition of Y was tailored to the […]

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: