www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.bugs - [Issue 10819] New: Invalid comparison for equality of lambda functions

reply d-bugmail puremagic.com writes:
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



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: -------
Aug 13 2013
next sibling parent d-bugmail puremagic.com writes:
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



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: -------
Aug 14 2013
prev sibling next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=10819


bearophile_hugs eml.cc changed:

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




 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: -------
Aug 14 2013
prev sibling next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=10819




10:33:34 PDT ---

 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: -------
Aug 14 2013
prev sibling next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=10819




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: -------
Aug 14 2013
prev sibling next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=10819




13:14:03 PDT ---

 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: -------
Aug 14 2013
prev sibling next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=10819


hsteoh quickfur.ath.cx changed:

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



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: -------
Aug 30 2013
prev sibling next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=10819




03:53:53 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.
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: -------
Aug 31 2013
prev sibling next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=10819




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: -------
Aug 31 2013
prev sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=10819




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: -------
Aug 31 2013