__GENTYPE to generate ever different types

[dlangBugzillaToGithub]

bearophile_hugs reported this on 2014-02-07T10:35:50Z

Transferred from https://issues.dlang.org/show_bug.cgi?id=12100

CC List

• Andrej Mitrovic (@AndrejMitrovic)
• Simen Kjaeraas

Description

Currently in std.typecons there is Typedef, that the docs describe with:

template Typedef(T)
struct Typedef(T, T init, string cookie = null); 


The cookie is needed when you want to create different types based on the same type:

alias MyInt1 = Typedef!(int, 0, "A");
alias MyInt2 = Typedef!(int, 0, "B");


To remove the need of the cookie I suggest to add to D something that could be named __GENTYPE, that every time creates a new type:

struct Typedef(T, T init=T.init, NT=__GENTYPE); 


So every instantiation of Typedef is different:

alias MyInt1 = Typedef!int;
alias MyInt2 = Typedef!int;
static assert (!is(MyInt1 == MyInt2));


A __GENTYPE is also a very simple way to implement the "Path Dependent Types" of the Scala language. Here in Scala b1 and b2 have different type:

http://stackoverflow.com/questions/2693067/what-is-meant-by-scalas-path-dependent-types

class A {
    class B {
    }
}

var a1 = new A;
var a2 = new A;
var b1 = a1.new B;
var b2 = a2.new B;


Parametrizing the class A with an unused type, and using __GENTYPE inside a helper function that instantiates A, you can have the same feature in D:

class A(Ghost) {
    class B {
    }
}


The disadvantage is that you have template bloat, so here it becomes useful an idea I suggested to reduce template bloat, templated():

http://www.digitalmars.com/d/archives/digitalmars/D/templated_126655.html


The name __GENTYPE comes from the Lisp gensym that's used to generate new names to be used in macros.

http://en.wikipedia.org/wiki/Hygienic_macro#Strategies_used_in_languages_that_lack_hygienic_macros

http://www.lispworks.com/documentation/HyperSpec/Body/f_gensym.htm#gensym

[dlangBugzillaToGithub]

andrej.mitrovich (@AndrejMitrovic) commented on 2014-04-21T16:41:16Z

How about __uniqueID, which would create a unique string ID? I'd imagine this would be more useful since it's more generic, and you could easily create a wrapper for it via:

-----
template GENTYPE()
{
    mixin("struct %1$s { }; alias GENTYPE = %1$s".format(__uniqueID));
}
-----

[dlangBugzillaToGithub]

andrej.mitrovich (@AndrejMitrovic) commented on 2014-04-21T16:44:17Z

(In reply to Andrej Mitrovic from comment #1)
> How about __uniqueID, which would create a unique string ID? I'd imagine
> this would be more useful since it's more generic, and you could easily
> create a wrapper for it via:
> 
> -----
> template GENTYPE()
> {
>     mixin("struct %1$s { }; alias GENTYPE = %1$s".format(__uniqueID));
> }
> -----

Also __uniqueID would be useful for generating parameter names, and pretty much anywhere where you're using string mixins and need to use some unique names.

[dlangBugzillaToGithub]

bearophile_hugs commented on 2014-04-23T16:04:01Z

(In reply to Andrej Mitrovic from comment #1)
> How about __uniqueID, which would create a unique string ID?

Yes, a progressive integer is enough.

[dlangBugzillaToGithub]

monarchdodra commented on 2014-04-23T21:00:43Z

(In reply to bearophile_hugs from comment #3)
> (In reply to Andrej Mitrovic from comment #1)
> > How about __uniqueID, which would create a unique string ID?
> 
> Yes, a progressive integer is enough.

Well, it still has to be unique cross-compilation run: If you compile several different objects differently, then the integer won't be unique.

[dlangBugzillaToGithub]

monarchdodra commented on 2014-04-23T21:02:04Z

(In reply to Andrej Mitrovic from comment #1)
> How about __uniqueID, which would create a unique string ID? I'd imagine
> this would be more useful since it's more generic, and you could easily
> create a wrapper for it via:
> 
> -----
> template GENTYPE()
> {
>     mixin("struct %1$s { }; alias GENTYPE = %1$s".format(__uniqueID));
> }
> -----

Basically, we're asking for a static PRNG? In this particular case, the final result is a string or type, but at the core, what we need is a compile time PRNG?

[dlangBugzillaToGithub]

bearophile_hugs commented on 2014-04-23T21:12:04Z

(In reply to monarchdodra from comment #5)

> Basically, we're asking for a static PRNG?

No, I am asking for a integer that is incremented every time by 1, and that is exported as a range by every pre-compiled module to avoid duplicatio7ns. (a random number can't be unique, unless you use something like 512 random bits).

[dlangBugzillaToGithub]

andrej.mitrovich (@AndrejMitrovic) commented on 2014-04-23T21:20:47Z

(In reply to monarchdodra from comment #4)
> (In reply to bearophile_hugs from comment #3)
> > (In reply to Andrej Mitrovic from comment #1)
> > > How about __uniqueID, which would create a unique string ID?
> > 
> > Yes, a progressive integer is enough.
> 
> Well, it still has to be unique cross-compilation run: If you compile
> several different objects differently, then the integer won't be unique.

Hmm.. I don't know about that. Really all I wanted was:

auto a = __uniqueID;  // "asdf01"
auto b = __uniqueID;  // "asdf02"

It's just something that's incremented internally, but this can only be done during that compilation run. I'm not sure whether this would cause any problems.

DMD already has something like this that it uses internally, but at runtime (of the DMD executable), Lexer::uniqueId.

[dlangBugzillaToGithub]

monarchdodra commented on 2014-04-23T21:24:05Z

(In reply to bearophile_hugs from comment #6)
> (In reply to monarchdodra from comment #5)
> 
> > Basically, we're asking for a static PRNG?
> 
> No, I am asking for a integer that is incremented every time by 1, and that
> is exported as a range by every pre-compiled module to avoid duplicatio7ns.
> (a random number can't be unique, unless you use something like 512 random
> bits).

Right, I was thinking kind of thinking "UUID unique".

[dlangBugzillaToGithub]

monarchdodra commented on 2014-04-23T21:31:28Z

(In reply to Andrej Mitrovic from comment #7)
> Hmm.. I don't know about that. Really all I wanted was:
> 
> auto a = __uniqueID;  // "asdf01"
> auto b = __uniqueID;  // "asdf02"
> 
> It's just something that's incremented internally, but this can only be done
> during that compilation run. I'm not sure whether this would cause any
> problems.
> 
> DMD already has something like this that it uses internally, but at runtime
> (of the DMD executable), Lexer::uniqueId.

Yeah, but I'm saying that:

//----
module mod_a;

immutable a = __uniqueID;  // "asdf01"
//----
module mod_b;

immutable b = __uniqueID;  // "asdf??"
//----
module main;

import mod_a, mod_d;
static assert(a != b);
//----

dmd -c mod_a.d
dmd -c mod_b.d
dmd mod_d.o mod_b.o main.d

Then a "simple" increment scheme won't work, since you'd have reset between two runs, and have created a duplicate.

But I guess at this point, we agree on the final functionality. The rest is implementation detail.

[dlangBugzillaToGithub]

andrej.mitrovich (@AndrejMitrovic) commented on 2014-04-23T21:33:24Z

(In reply to monarchdodra from comment #9)
> Yeah, but I'm saying that:
> import mod_a, mod_d;
> static assert(a != b);

One workaround for this is to encode the module name in the identifier (hence why a string-based approach might be more useful than just a trait that returns a number).

[dlangBugzillaToGithub]

bearophile_hugs commented on 2014-05-27T16:37:02Z

A temporary workaround (not meant to be left in place forever) could be using lambdas as cookie:

pragma(msg, ((int) => 0).stringof);
pragma(msg, ((int) => 0).stringof);
void main() {}


Output:

__lambda3
__lambda4

[dlangBugzillaToGithub]

bearophile_hugs commented on 2014-09-16T11:31:50Z

VC++ and GCC have "__COUNTER__":

http://stackoverflow.com/questions/652815/has-anyone-ever-had-a-use-for-the-counter-pre-processor-macro
http://msdn.microsoft.com/en-us/library/b0084kay.aspx

[dlangBugzillaToGithub]

simen.kjaras commented on 2016-04-06T03:38:58Z

Here's a PR:

https://github.com/D-Programming-Language/dmd/pull/5633

Notice I have used the name __GENSYM__ due to LISP's precedent.

[dlangBugzillaToGithub]

simen.kjaras commented on 2016-04-10T16:45:21Z

A bit of reasoning behind the choices made in the PR above:

(In reply to bearophile_hugs from comment #12)
> VC++ and GCC have "__COUNTER__"

__COUNTER__ breaks when used with separate compilation, as discussed above. Also:

(In reply to bearophile_hugs from comment #6)
> I am asking for a integer that is incremented every time by 1, and that
> is exported as a range by every pre-compiled module to avoid duplications.

So... how do the other modules know about this range? One'd have to include the other compiled modules on the command line when compiling one module, from what I can see. If not, the compiler won't know of the used values, and chaos would ensue.

For my PR, __GENSYM__ returns a string with a 'G' prefix*, followed by the mangled name of the containing scope, followed by a scope-local counter:

module bar;
struct Ham(string gensym = __GENSYM__) {
    enum s = gensym;
    Eggs!() e;
}

struct Eggs(string gensym = __GENSYM__) {
    enum s = gensym;
}

module foo;
import bar;

struct S {
    static assert(__GENSYM__ == "G3foo1S1");
    static assert(__GENSYM__ == "G3foo1S2");
}

void baz() {
    static assert(__GENSYM__ == "G_D3foo3bazFZv1");
    static assert(__GENSYM__ == "G_D3foo3bazFZv2");
}

static assert(__GENSYM__ == "G3foo1");
static assert(__GENSYM__ == "G3foo2");

void main() {
    static assert(__GENSYM__ == "G_Dmain1");
    static assert(__GENSYM__ == "G_Dmain2");
    static assert(Ham!().s == "G_Dmain3");
    static assert(Ham!().s == "G_Dmain4");
    static assert(Ham!().e.s == "G3bar31__T3HamVAyaa8_475f446d61696e35Z3Ham1");
    static assert(Ham!().e.s == "G3bar31__T3HamVAyaa8_475f446d61696e36Z3Ham1"); // Note that this is not identical to the above (5Z3Ham1 vs 6Z3Ham1)
}

The mangled names should be fairly unique, and I don't think there's a case where the order of instantiation would be different within a single scope, but I'm prepared to be proven wrong on this.
So that should take care of separate compilation.

It's possible that this scheme can return values that are no valid identifiers (if mangleof contains invalid characters). This is currently simply ignored.

* The 'G' prefix is used so that __GENSYM__ should return a valid identifier. The exact character is once again chosen for LISP compatibility.