On Thursday, 1 October 2020 at 21:04:29 UTC, Walter Bright wrote:
> Does the same thing, works today:

I think it is actually a mistake to focus too much on types.

The "type function" concept might be useful if it provides a way to work with compiler tuples in general. Then it might be able to do things that are basically impossible right now (well at least not without a dose of string mixin) and do it efficiently.

I've been playing with a variety of other implementations and they keep ending up slow. A tuple foreach unrolls into a bunch of code. Perhaps this can be further optimized with a few tweaks:

1) make a function an any temporaries coming from it as CTFE only so it isn't codegen'd, optimized in any way, or emitted to the object file.

2) maybe borrow part of Stefan's implementation to avoid unrolling certain tuple looks so it runs faster. We already have `foreach(alias t; T)` so maybe it can just be optimized.

But then we still have the difficulty of translating the result tuple back into something we can use. The only facilities the language provides right now are some kind of recursive template and/or some kind of string mixin.

These get expensive again (especially for long and/or varied argument lists) and may hit other arbitrary limitations like runtime/compile time barriers. And it is a bit obnoxious because the compiler already knows all this stuff, but instead of saying "reuse that please" we have to say "turn that into a string, then turn the string into a template, then turn the template into a tuple".

So some facility to turn a ctfe array back into a tuple - the dereifiy step basically - with compiler assistance I think will be practical.


And you know, I'm still a little skeptical of the type functions, but I do think they have potential when we start looking at them as tuple manipulators more than as template replacements. Tuples are this weird thing that are half in the language and half not... and bringing them more in would actually be pretty nice.

Would it solve Variant's needs? Well ... I think that's separate, we actually can do that in today's D. You can make a list of conversion targets in opAssign, make one in get, and compare them at runtime. Maybe I'll implement later but she's fussing again ttyl

On 10/1/2020 1:57 AM, Stefan Koch wrote:
> However there is a difference in file size.
> 
> Type function version:
> 
> stat  makeConvMatrix.o
>    File: 'makeConvMatrix.o'
>    Size: 2876
> 
> VS template version
> 
> stat  makeConvMatrix_tmpl.o
>    File: 'makeConvMatrix_tmpl.o'
>    Size: 11760

Indeed there is, as the compiler generates code for the function and writes the code to the object file. The code it generates is placed into a COMDAT section which, since it is unreferenced, is supposed to be elided by the linker.

However, many linkers don't seem to do that, and besides, the compiler is wasting effort generating unused code. This is a more general inefficiency in the design of the compiler internals, and is not necessarily a language design defect.

Internally, there is a function called `needsCodegen()` which decides if a template instantiation needs code generated for it (duh!). It clearly errs on the side of being a bit too conservative.

I suggest an improvement to it where it will return false if the only use of a template instantiation is in CTFE. If that is unimplementable (the separate compilation model may make it impractical), a fallback position is to have a pragma or some other mechanism that says "don't generate code for this function".

I suspect such a compiler improvement would produce considerable benefit to existing template-heavy code.

On Thursday, 1 October 2020 at 21:34:54 UTC, Walter Bright wrote:
> I suggest an improvement to it where it will return false if the only use of a template instantiation is in CTFE. If that is unimplementable (the separate compilation model may make it impractical), a fallback position is to have a pragma or some other mechanism that says "don't generate code for this function".

Yes! Stefan actually already wrote this too

https://github.com/dlang/dmd/pull/11007

just a few minor tweaks and it can work to help out. The `assert(__ctfe)` pattern is already used in some code in the wild.

On Thursday, 1 October 2020 at 19:15:10 UTC, Andrei Alexandrescu wrote:
> Problem definition: Implement Variant.get correctly. :o)
>
> E.g. this produces a type error somewhere in the innards of std.variant: https://run.dlang.io/is/joIbeV. I'm not sure how many other cases are out there.


So here's my proof of concept that this is doable today:


---------------

import std.typecons; // for Rebindable

interface MyTypeInfo {
	const pure nothrow: // yadda yadda yada
	bool implicitlyConvertsTo(const MyTypeInfo t);
	bool isNullable();
	string toiString();
}

interface MyTypeInfoFunction {
	const pure nothrow:

	immutable(MyTypeInfo) returnType();
	immutable(MyTypeInfo)[] paramsTypes();
}

interface MyTypeInfoClass {
	const pure nothrow:

	immutable(MyTypeInfo)[] bases();
}

class MyTypeInfoImpl_FunctionPointer(T) : MyTypeInfo, MyTypeInfoFunction {
	const:
	bool isNullable() { return true; }
	string toiString() { return T.stringof; }

	static if(is(T == R function(Params), R, Params...)) {
		immutable(MyTypeInfo) returnType() {
			return mytypeid!R;
		}

		immutable(MyTypeInfo)[] paramsTypes() pure nothrow {
			import std.meta; // I wouldn't normally use this but meh it is a demo
			static immutable MyTypeInfo[] result = [staticMap!(mytypeid, Params)];

			return result[];
		}
	} else static assert(0, "mistake in " ~ T.stringof);

	bool implicitlyConvertsTo(const MyTypeInfo t) {
		if(this is t)
			return true;

		if(t is mytypeid!(typeof(null)))
			return true;

		auto fp = cast(MyTypeInfoFunction) t;
		if(fp is null)
			return false;

		if(!returnType.implicitlyConvertsTo(fp.returnType))
			return false;

		if(paramsTypes.length != fp.paramsTypes.length)
			return false;

		foreach(idx, arg; fp.paramsTypes)
			if(!arg.implicitlyConvertsTo(paramsTypes[idx]))
				return false;

		return true;
	}
}

class MyTypeInfoImpl_Class(T) : MyTypeInfo, MyTypeInfoClass {
	bool isNullable() const { return true; }
	string toiString() const { return T.stringof; }

	static if(is(T Super == super))
	immutable(MyTypeInfo)[] bases() const {
		import std.meta;
		static immutable MyTypeInfo[] result = [staticMap!(mytypeid, Super)];
		return result[];
	}

	bool implicitlyConvertsTo(const MyTypeInfo t) const {
		if(this is t)
			return true;

		if(t is mytypeid!(typeof(null)))
			return true;

		foreach(base; bases)
			if(t is base)
				return true;
		return false;
	}
}

class MyTypeInfoImpl(T) : MyTypeInfo {
	bool isNullable() const {
		return is(typeof(null) : T);
	}

	string toiString() const {
		return T.stringof;
	}

	bool implicitlyConvertsTo(const MyTypeInfo t) const {
		static if(is(T == typeof(null)))
			return t.isNullable();
		return this is t;
	}
}

template mytypeid(T) {
	static if(is(T == return))
		immutable MyTypeInfo mytypeid = new immutable MyTypeInfoImpl_FunctionPointer!T;
	else static if(is(T == class))
		immutable MyTypeInfo mytypeid = new immutable MyTypeInfoImpl_Class!T;
	else {
		//pragma(msg, "generic " ~ T.stringof);
		immutable MyTypeInfo mytypeid = new immutable MyTypeInfoImpl!T;
	}
}

struct MyVariant {
	this(T)(T t) {
		opAssign(t);
	}

	void opAssign(T)(T t) {
		storedType = mytypeid!T;

		// I know this impl sux but std.variant already solved it so not the point here.
		union SD {
			StoredData sd;
			T b;
		}
		SD sd;
		sd.b = t;
		storedData = sd.sd;
	}

	T get(T)() {
		if(storedType is null)
			static if(is(T : typeof(null)))
				return null;
			else
				throw new Exception("null cannot become " ~ T.stringof);
		if(storedType.implicitlyConvertsTo(mytypeid!(T))) {
			union SD {
				StoredData sd;
				T b;
			}
			SD sd;
			sd.sd = storedData;
			return sd.b;
		} else
			throw new Exception(storedType.toiString() ~ " cannot become " ~ T.stringof);
	}

	Rebindable!(immutable(MyTypeInfo)) storedType;
	// std.variant already has a better impl of this
	struct StoredData {
		void* b1;
		void* b2;
	}
	StoredData storedData;
}


class A {}
class B : A {}
import std.stdio;
A func() { writeln("func A"); return null; }
B func2() { writeln("func2 B"); return null; }

void main() {
	MyVariant v = &func2;
	auto test = &func2;
	typeof(&func) test2 = test;
	A function() a = v.get!(typeof(&func));

	a();
	test2();
}

----------------


I understand that's a decent chunk of code and it is very incomplete - it is basically the minimum to achieve the challenge. And I think I missed up the contravariant parameter implementation there, I always forget the exact rule without looking it up. But nevertheless that's an implementation bug, not a language barrier.

I hope it shows that this isn't hopeless with today's D. All that compile time knowledge we need *is* available to Variant itself, it just needs to dig a little deeper to put it together.... and then reimplement the compiler's rules, hopefully correctly.

Of course it would be better if we could just reuse dmd's implementation! But *that* I don't think is possible because Variant crosses the runtime barrier.... even with a type function I think it'd need a *pointer* to a typefunction which again hits that RT/CT barrier.

On Thursday, 1 October 2020 at 21:34:50 UTC, Adam D. Ruppe wrote:
>
> So some facility to turn a ctfe array back into a tuple - the dereifiy step basically - with compiler assistance I think will be practical.

What if we could just mutate tuples locally?

template staticMap(alias F, Args...) {
    static foreach(ref Arg; Args)
        Arg = F!Arg;
    alias staticMap = Args;
}

The obvious objection is "the spec says order of declarations doesn't matter", but this is a case where the spec is just flat-out wrong (see previous discussion of "compile-time race conditions" [1]). So, given that declaration order is in fact significant in D, we may as well officially acknowledge it and reap the benefits.

[1] https://forum.dlang.org/thread/swbmgrhtoiqtqokmqniu@forum.dlang.org?page=2#post-rccfbm:24sjv:241:40digitalmars.com

On 10/1/20 7:10 PM, Paul Backus wrote:
> On Thursday, 1 October 2020 at 21:34:50 UTC, Adam D. Ruppe wrote:
>>
>> So some facility to turn a ctfe array back into a tuple - the dereifiy step basically - with compiler assistance I think will be practical.
> 
> What if we could just mutate tuples locally?
> 
> template staticMap(alias F, Args...) {
>      static foreach(ref Arg; Args)
>          Arg = F!Arg;
>      alias staticMap = Args;
> }

Interesting - this is akin to D's relaxed purity whereby a pure function can mutate its arguments. I'm trying to wrap my head around it, e.g. is Args considered a private copy of the argument much like a static array passed by value?

> The obvious objection is "the spec says order of declarations doesn't matter", but this is a case where the spec is just flat-out wrong (see previous discussion of "compile-time race conditions" [1]). So, given that declaration order is in fact significant in D, we may as well officially acknowledge it and reap the benefits.
> 
> [1] https://forum.dlang.org/thread/swbmgrhtoiqtqokmqniu@forum.dlang.org?page=2#post-rccfbm:24sjv:241:40digitalmars.com 

I don't get the interaction. How does mutating the argument affect order of declaration?

On 10/1/20 7:02 PM, Adam D. Ruppe wrote:
> On Thursday, 1 October 2020 at 19:15:10 UTC, Andrei Alexandrescu wrote:
>> Problem definition: Implement Variant.get correctly. :o)
>>
>> E.g. this produces a type error somewhere in the innards of std.variant: https://run.dlang.io/is/joIbeV. I'm not sure how many other cases are out there.
> 
> 
> So here's my proof of concept that this is doable today:
[snip]

Is this a visitation/double dispatch?

On 10/1/20 5:22 PM, Walter Bright wrote:
> On 10/1/2020 2:04 PM, Walter Bright wrote:
>> Does the same thing, works today:
> 
> Yes, I see another message posted the same thing.

Separation of concerns applies to ctfe code as well. The function should just fetch the bool matrix. Formatting should not be mixed with that, but rather done later either at compile- or run-time:

auto makeConvMatrix(Ts...)() {
    bool[T.length[T.length] result;
    static foreach (i, T : Ts)
        static foreach (j, U : Ts)
            result[i][j] = is(T : U);
    return result;
}

On Friday, 2 October 2020 at 02:27:40 UTC, Andrei Alexandrescu wrote:
> On 10/1/20 5:22 PM, Walter Bright wrote:
>> On 10/1/2020 2:04 PM, Walter Bright wrote:
>>> Does the same thing, works today:
>> 
>> Yes, I see another message posted the same thing.
>
> Separation of concerns applies to ctfe code as well. The function should just fetch the bool matrix. Formatting should not be mixed with that, but rather done later either at compile- or run-time:
>
I reserve the right to post the example that I post.
Thank you very much.

For the code I posted the type function produces a binary which is
 - 4 times smaller than the template,
 - a lot has less symbols
 - and works at betterC.
 - does not relay on static foreach expansion

On Thursday, 1 October 2020 at 21:04:29 UTC, Walter Bright wrote:
> Does the same thing, works today:
>
> string makeConvMatrix(T...)()
> {
>     string result;
>     static foreach(t; T)
>     {
>         result ~= "\t" ~ t.stringof;
>     }
>     result ~= "\n";
>     static foreach(t1; T)
>     {
>         result ~= t1.stringof;
>         static foreach(t2; T)
>         {
>             result ~=  "\t" ~ (is(t1:t2) ? "yes" : "no");
>         }
>         result ~= "\n";
>     }
>     return result;
> }
>
> void main()
> {
>     import core.stdc.stdio;
>     static immutable convMatrix = makeConvMatrix!(byte, ubyte, short, ushort, int, uint, long, ulong)();
>
>     printf("%s\n", convMatrix.ptr);
> }

This code produces a binary which
 - is 4 times biggger
 - has more symobls.
 - doesn't work for -betterC

See: https://forum.dlang.org/post/wdaamjqqvjlnwaopamzn@forum.dlang.org
Where I address the differences.