http://d.puremagic.com/issues/show_bug.cgi?id=10819

           Summary: Invalid comparison for equality of lambda functions
           Product: D
           Version: D2
          Platform: All
        OS/Version: All
            Status: NEW
          Severity: normal
          Priority: P2
         Component: DMD
        AssignedTo: nobody@puremagic.com
        ReportedBy: andrei@erdani.com


--- Comment #0 from Andrei Alexandrescu <andrei@erdani.com> 2013-08-13 17:48:14 PDT ---
Consider:

void main() {
    import std.range;
    SortedRange!(int[], "a > b") a;
    SortedRange!(int[], "a > b") b;
    b = a;
    SortedRange!(int[], (a, b) => a > b) c;
    SortedRange!(int[], (a, b) => a > b) d;
    d = c;
}

The last line does not compile.

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------

http://d.puremagic.com/issues/show_bug.cgi?id=10819


Peter Alexander <peter.alexander.au@gmail.com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |peter.alexander.au@gmail.co
                   |                            |m


--- Comment #1 from Peter Alexander <peter.alexander.au@gmail.com> 2013-08-14 08:09:06 PDT ---
How would you define equality for lambda functions?

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------

http://d.puremagic.com/issues/show_bug.cgi?id=10819


bearophile_hugs@eml.cc changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |bearophile_hugs@eml.cc


--- Comment #2 from bearophile_hugs@eml.cc 2013-08-14 10:07:22 PDT ---
(In reply to comment #1)
> How would you define equality for lambda functions?

You don't compute in general the equivalence of two programs. Currently if you use the "string lambdas" then for the "a > b" and "a >b" the D compiler can't tell they are the same. So as usual you look for a rough solution. This means you take the expression threes of the lambdas and test if they are exactly the same (minus whitespace and stripping away documentation comments).


Related: elsewhere people have proposed a __trait(ast, some_code_here) that returns the syntax tree of some given code. The tree is composed of structs and other types defined in Phobos or elsewhere, and you can process such tree through regular user D code. I think this allows poor's man macros almost entirely implemented in library D code. And they become a bit nicer once "__traits(ast, ...)" is written like meta.ast(...).

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------

http://d.puremagic.com/issues/show_bug.cgi?id=10819



--- Comment #3 from Peter Alexander <peter.alexander.au@gmail.com> 2013-08-14 10:33:34 PDT ---
(In reply to comment #2)
> you take the expression threes of the lambdas and test if they are exactly the same (minus whitespace and stripping away documentation comments).

But how does that work across modules?

Lambdas are mangled as modulenameN__lambdaX, where X is just an increasing integer for each lambda in the module.

If lambdas are to be equal then they must also mangle equal. Currently lambdas in different modules will mangle differently, regardless of the AST, and separate compilation ensures this.

You could possibly work around this by mangling lambdas as just __lambdaXXXXXXXX where the Xs are a hash of the lambda AST (hope for no collisions). This does mean however that lambda types are moduleless... I'm not sure how that would affect other parts of the language and runtime.

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------

http://d.puremagic.com/issues/show_bug.cgi?id=10819



--- Comment #4 from Andrei Alexandrescu <andrei@erdani.com> 2013-08-14 12:04:33 PDT ---
We can assume the bodies of the lambdas compared are always available, which makes comparisons easier. Then it's a matter of how precise we want to be about it all. One possibility:

* parameter types must be identical, or both alias/type parameter - for each
position
* bodies must be identical up to alpha renaming of parameters. E.g. (a) => a +
1 should compare equal to (b) => b + 1
* no more effort beyond that, e.g. (a) => a + 1 is not equal to (a) => 1 + a

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------

http://d.puremagic.com/issues/show_bug.cgi?id=10819



--- Comment #5 from Peter Alexander <peter.alexander.au@gmail.com> 2013-08-14 13:14:03 PDT ---
(In reply to comment #4)
> We can assume the bodies of the lambdas compared are always available, which makes comparisons easier.

This doesn't avoid the name mangling problem:

-------------------------------------------
module A;
struct S(alias F)
{
    static immutable string s = F.mangleof;
}
-------------------------------------------
module B;
S!(a => a) foo;
-------------------------------------------
module C;
S!(a => a) bar;
-------------------------------------------

If I've understood correctly, you want foo and bar to be of the same type, but they can't be because the static s member must have a different value for each type.

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------

http://d.puremagic.com/issues/show_bug.cgi?id=10819


hsteoh@quickfur.ath.cx changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |hsteoh@quickfur.ath.cx


--- Comment #6 from hsteoh@quickfur.ath.cx 2013-08-30 15:41:46 PDT ---
This is probably total overkill, but what about instead of mangling to __lambda + an incrementing integer, replace the integer with the SHA hash of the lambda's AST tree? As Andrei said, we cater only to the case where the two lambdas are token-for-token identical, because the general problem of equivalence between two arbitrary lambdas is uncomputable.

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------

http://d.puremagic.com/issues/show_bug.cgi?id=10819



--- Comment #7 from Peter Alexander <peter.alexander.au@gmail.com> 2013-08-31 03:53:53 PDT ---
(In reply to comment #6)
> This is probably total overkill, but what about instead of mangling to __lambda + an incrementing integer, replace the integer with the SHA hash of the lambda's AST tree? As Andrei said, we cater only to the case where the two lambdas are token-for-token identical, because the general problem of equivalence between two arbitrary lambdas is uncomputable.

That works but is it OK for the lambda type to not have a module?

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------

http://d.puremagic.com/issues/show_bug.cgi?id=10819



--- Comment #8 from hsteoh@quickfur.ath.cx 2013-08-31 15:32:59 PDT ---
Hmm you're right. We can't drop the module, otherwise lambdas with static variables will be wrongly conflated. :-/ But is this still doable for lambdas within the same module?

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------

http://d.puremagic.com/issues/show_bug.cgi?id=10819



--- Comment #9 from Andrei Alexandrescu <andrei@erdani.com> 2013-08-31 16:12:26 PDT ---
Yah, a hash-based solution would be quite good.

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------