Search code examples
javalambdajava-8lambda-calculus

Java 8 lambda and alpha equivalence

I am wondering, is any nice way (if it is possible at all) to implement an alpha-equivalence comparison in Java-8?

Obviously these two lambda-s are alpha-equivalent. Let us suppose that for some circumstances we want to detect this fact. How it can be achieved?

Predicate<Integer> l1 = x -> x == 1;
Predicate<Integer> l2 = y -> y == 1;
Solution

  • I'm going out on a limb with this answer, but it may be worth mentioning this:

    There is no way to do this. As Brian Goetz pointed out in an answer to a related question, there are no specified, reliable ways of obtaining the "contents" of a lambda, in that sense.

    But (and now comes the vague, handwaving part) :

    There is no way to do this yet.

    It might be possible to do this in the future. Maybe not with Java 9, but later. The Project Panama has ambituous goals, among them, giving the developer a deeper access to lambdas, aiding in further (runtime) optimizations, translations and processing.

    And recently, Radosław Smogura posted in the mailing list :

    I try to capture lambda expression to get them as expression tree during runtime. I’m able to do it for simple lambdas like (o) -> (var == var) && ((varX == varX) && (someField + 1 == 1)), so later user can use (missing) API to examine tree.

    Right now tree can be accessed with code like this:

    Method m = BasicMatadataTest.class.getDeclaredMethod("lambda$meta0");
Expression e = (Expression) m.invoke(null);
BinaryExpression top = (BinaryExpression) e;
BinaryExpression vars = (BinaryExpression) top.getLefthandExpression(); // represents (var == var)
(VariableExpression) vars.getLefthandExpression() // represents first var, and it’s reference equal to vars.getRighthandExpression() as it’s same variable

    ...

    The key point here may be the comment:

    represents first var, and it’s reference equal to vars.getRighthandExpression() as it’s same variable

    (e.b.m)

    So if I understood your question and this mailing list post correctly, then it might be possible to determine the equivalence between such expressions: Comparing the tree structure would be fairly trivial (given the functionality sketched above). And then it might boil down to treating two VariableExpression as being "equal", regardless of the actual variable name.

    The mailing list message points to the repositories:

    (Disclaimer: I have not tested this, and don't know how to get this running (or whether it works at all) - but to my understanding, it is at least very close to what the question was actually about).