12

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;
nalzok
  • 14,965
  • 21
  • 72
  • 139
Andremoniy
  • 34,031
  • 20
  • 135
  • 241
  • You would need to find a way to obtain a canonical representation of your `Predicate` or to test them over their whole domain, and I don't see any practical way to do either – Aaron Jun 28 '17 at 12:51
  • This may be of some help, but I'm not sure how much - https://stackoverflow.com/questions/24095875/is-there-a-way-to-compare-lambdas – lucasvw Jun 28 '17 at 12:53
  • well you could Serialize the lambda expression and compare the bytes, I have not tried this though – Eugene Jun 28 '17 at 12:59
  • 2
    @holi-java that's not what the OP wants... – Eugene Jun 28 '17 at 13:02
  • @Eugene first of all your idea about some byte code comparison is really interesting and it is exactly what I have been thinking about. Secondly, my goal here is slightly more theoretical, because it is really difficult to describe my practical idea here in brief. – Andremoniy Jun 28 '17 at 13:04
  • 1
    If the case is as simple as in the given example, a comparison of JVM instructions would solve the problem, because you can ignore the variable name and even the generic type, and only compare the list of instructions. A framework like [ASM](https://stackoverflow.com/questions/tagged/java-bytecode-asm) could help interpreting and comparing bytecode instructions, but that's probably alot of work. – SME_Dev Jun 28 '17 at 13:04
  • @Eugene hi, what about the OP meaning ? could you show me a formular ? – holi-java Jun 28 '17 at 13:05
  • @SME_Dev I am sure that any workable solution given as an answer will be much appreciated not only by my self :) Your idea could work – Andremoniy Jun 28 '17 at 13:05
  • @holi-java please, consider learning lambda-calculus theory, this will reveal you the idea of my question – Andremoniy Jun 28 '17 at 13:06
  • @Andremoniy that is hard for me. my english is so bad, sir. – holi-java Jun 28 '17 at 13:07
  • @holi-java in this case I have no idea how to help you understand my question :-) – Andremoniy Jun 28 '17 at 13:07
  • hi, someone has already point it out. compare the instructions. so the question is how java implements the equivalent lambdas. Am I right, sir? – holi-java Jun 28 '17 at 13:10
  • I'd like to know what are your thought. +1 – holi-java Jun 28 '17 at 13:11
  • 2
    @Andremoniy serializeable could be an option, but Im thinking about the order or instructions in a bigger lambda expression, they could be equivalent, but in *different* order... Ill have to try that – Eugene Jun 28 '17 at 13:11
  • 3
    You can use instrumentation to read the lambda class, then use something like the asm library to work out if they are equivalent, which will likely be enough for a trivial example like you provided, but it wont work for more complicated cases. – Magnus Jun 28 '17 at 13:49
  • @Andremoniy I'm surprised that you accepted the answer. Maybe people are still experimenting for a solution based on serialization, bytecode reading or similar approaches ...? – Marco13 Jun 29 '17 at 12:11
  • 1
    @Marco13 Perhaps :) As soon as somebody provides such kind of answer, I will consider to change my decision. – Andremoniy Jun 29 '17 at 12:27

1 Answers1

11

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).

Marco13
  • 53,703
  • 9
  • 80
  • 159
  • 1
    basically the short version would be - no way; *might happen*, but not sooner then jdk-10. *Might* being the keyword. – Eugene Jun 28 '17 at 13:21
  • That's very interesting, thanks! +1 But will still wait for some time if somebody finds any result with serialization – Andremoniy Jun 28 '17 at 13:23
  • 1
    @Andremoniy Sure, this answer is not profound enough to be *acceptable*. There might be options with serialization or ASM or other bytecode magic, and I'd also be curious to see them (even if - and this is likely - they would be somehow implementation dependent or relied on other unspecified details). But I think that eventually, the path sketched in the mailing list (@Eugene ;-)) **might** be one that leads towards a real, proper API for achieving the goal. – Marco13 Jun 28 '17 at 13:28
  • I finally understand what the OP want to do. plus one. he want to compare the lambda body's logic are equivalent . Am I right, sir? but there are many combinations for the same logic. – holi-java Jun 28 '17 at 13:35
  • 4
    @holi-java Yes. The *formal* definition of the equivalence is explained on [Wikipedia: Lambda Calculus Alpha Equivalence](https://en.wikipedia.org/wiki/Lambda_calculus#Alpha_equivalence). To my understanding, one core aspect of the question was whether there is a way to programmatically obtain the "contents" of a lambda (so that one could implement the logic that is described on the Wikipedia site). (I think that the serialization approach would only work for *very* limited cases, if at all, but that's another issue). – Marco13 Jun 28 '17 at 13:54