Implicit conversion error assigning one SortedRange to another when a function literal has been used

[dlangBugzillaToGithub]

andrei (@andralex) reported this on 2013-08-13T17:48:14Z

Transfered from https://issues.dlang.org/show_bug.cgi?id=10819

CC List

• bearophile_hugs
• hsteoh
• peter.alexander.au (@Poita)
• razvan.nitu1305
• smjg

Description

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.

[dlangBugzillaToGithub]

peter.alexander.au (@Poita) commented on 2013-08-14T08:09:06Z

How would you define equality for lambda functions?

[dlangBugzillaToGithub]

bearophile_hugs commented on 2013-08-14T10:07:22Z

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

[dlangBugzillaToGithub]

peter.alexander.au (@Poita) commented on 2013-08-14T10:33:34Z

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

[dlangBugzillaToGithub]

andrei (@andralex) commented on 2013-08-14T12:04:33Z

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

[dlangBugzillaToGithub]

peter.alexander.au (@Poita) commented on 2013-08-14T13:14:03Z

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

[dlangBugzillaToGithub]

hsteoh commented on 2013-08-30T15:41:46Z

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.

[dlangBugzillaToGithub]

peter.alexander.au (@Poita) commented on 2013-08-31T03:53:53Z

(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?

[dlangBugzillaToGithub]

hsteoh commented on 2013-08-31T15:32:59Z

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?

[dlangBugzillaToGithub]

andrei (@andralex) commented on 2013-08-31T16:12:26Z

Yah, a hash-based solution would be quite good.

[dlangBugzillaToGithub]

smjg commented on 2014-05-24T13:18:56Z

You completely forgot to post the compiler output.  Here's what I get (DMD 2.065 Win32):

bz10189.d(8): Error: cannot implicitly convert expression (c) of type SortedRange!(int[], (a, b) => a > b) to SortedRange!(int[], (a, b) => a > b)

But the two types are the same.

The same occurs when a D1-style function literal is used

----- bz10189a.d -----
void main() {
    import std.range;
    SortedRange!(int[], "a > b") a;
    SortedRange!(int[], "a > b") b;
    b = a;
    SortedRange!(int[], function bool(a, b) { return a > b; }) c;
    SortedRange!(int[], function bool(a, b) { return a > b; }) d;
    d = c;
}
----------
C:\Users\Stewart\Documents\Programming\D\Tests\bugs>dmd bz10189a.d
bz10189a.d(8): Error: cannot implicitly convert expression (c) of type SortedRange!(int[], function bool(a, b)
{
return a > b;
}
) to SortedRange!(int[], function bool(a, b)
{
return a > b;
}
)
----------

[dlangBugzillaToGithub]

razvan.nitu1305 commented on 2023-01-04T14:08:30Z

We now have traits(isSame) that can perform a primitive form of lambda function comparison. This can now be implemented in the opAssign of SortedRange so it's not a compiler issue anymore. Changing component to phobos.