## 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!

[…] 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 […]

One Y for Any Number of Arguments: version 4 « The Light Cone (Brian's space-time) said this on August 3, 2012 at 2:18 pm |