digitalmars.D - Beyond the veil: What's after type functions

Stefan Koch (275/275) Jan 04 2021 Good Evening,

Stefan Koch (11/12) Jan 04 2021 I just realized one of the key differences between type functions

Ola Fosheim =?UTF-8?B?R3LDuHN0YWQ=?= (5/11) Jan 06 2021 Hm... I would have thought that a template would be more

Ola Fosheim =?UTF-8?B?R3LDuHN0YWQ=?= (4/8) Jan 06 2021 Unless you constrain the loops in such a way that you can easily

sighoya (12/19) Jan 06 2021 I like the idea of type functions for type calculus only, because

Stefan Koch (19/26) Jan 07 2021 Indeed templates are enough for that.

Jacob Carlborg (18/19) Jan 06 2021 I think this looks like yet another new set of features just to avoid

Ola Fosheim =?UTF-8?B?R3LDuHN0YWQ=?= (5/11) Jan 06 2021 But the DMD AST model isn't really suitable for exposure. So you

Jacob Carlborg (11/14) Jan 06 2021 Why not? It would be code like any other code that can be abstracted

Ola Fosheim =?UTF-8?B?R3LDuHN0YWQ=?= (4/8) Jan 06 2021 Ok, but it would have to map exactly since it would be modified

Jacob Carlborg (6/8) Jan 07 2021 I'm not sure if I follow. But the compiler will convert between the

Ola Fosheim =?UTF-8?B?R3LDuHN0YWQ=?= (11/19) Jan 07 2021 But you are able to traverse the whole external AST tree?

Jacob Carlborg (8/19) Jan 09 2021 I haven't thought of that.

Paul Backus (13/26) Jan 06 2021 You don't need a stable AST API for AST macros, you just need

Jacob Carlborg (6/20) Jan 06 2021 Yes. Here's my suggestion [1] and bottom of [2].

Max Haughton (10/29) Jan 06 2021 I think we should have AST macros but it should be a data

Stefan Koch <uplink.coder googlemail.com> writes:

Good Evening,

I recently had a programming task in my hobby project where I 
needed to interface with a C library that uses manual closures 
using void**.
This quickly lead to bugs where one would forget to deref twice 
for read or accidental double deference on write (causing the 
written value to be invisible).

After that casting to the correct structure was an issue, since 
(void**) trows away typing information.

So I wanted a discriminated union (a "sumtype") to which I would 
use for all closures where the discriminant would tell me the 
rumtime type.

This is what I ended up with:

---
struct UploadClosure
{
     MHD_PostProcessor* pp;
     const (char)* filename;
     FILE* f;
     size_t totalSize;
}

struct KeyServerClosure
{
     bool processing_request;
}

enum ConnectionClosureKind
{
     Invalid,
     UploadClosure,
     KeyServerClosure,
}

ConnectionClosure* newClosure(ConnectionClosureKind kind)
{
     alias Kind = ConnectionClosureKind;
     const closureSize = closureSize(kind);

     ConnectionClosure* result = /*new ConnectionClosure(); //*/ 
cast(ConnectionClosure*)new ubyte[](closureSize).ptr;

     result.kind = kind;

     final switch (kind)
     {
         case Kind.UploadClosure :
         {
             // result.uploadClosure = new UploadClosure();
             result.uploadClosure = cast(UploadClosure*) 
((cast(void*)result) + (*result).sizeof);
         } break;

         case Kind.KeyServerClosure : {
             result.keyServerClosure = cast(KeyServerClosure*) 
((cast(void*)result) + (*result).sizeof);
         } break;

         case Kind.Invalid : {};
     }

     // import std.stdio; writeln(*result);

     return result;
}

struct ConnectionClosure
{
     ConnectionClosureKind kind;
     union
     {
         UploadClosure* uploadClosure;
         KeyServerClosure* keyServerClosure;
     }
}

size_t closureSize (ConnectionClosureKind kind) pure nothrow  nogc
{
     size_t result = ConnectionClosure.sizeof;

     final switch (kind)
     {
         case ConnectionClosureKind.UploadClosure : result += 
UploadClosure.sizeof;
         case ConnectionClosureKind.KeyServerClosure : result += 
KeyServerClosure.sizeof;
         case ConnectionClosureKind.Invalid : {}
     }

     return result;
}
---

You can easily Imagine the 'struct ConnectionClosure' and the 
`new Closure` function to be generate from the `enum 
ConnectionClosureKind` which would reduce the code snippet I 
posted by 54 lines (which is over 70% of the 75 line snippet).

Traditionally in D one would use templates and static foreach, 
which are known to scale awfully with regards to compile time, 
once you base an entire system on them.
Also they will most likely use string mixins in the 
implementation which means you can run into visibility/protection 
and namespace issues.

So I started to sketch what I would want to the compiler to do. 
(And I know it can do it, because these operations are performed 
internally)

And here was what this would look like:

---
alias type = __type__;

/// Compiler interal API looks up a typename in the given 
scope($D lookupScope)
/// Returns: the type named ($D typeName) if found
///          __emptyType otherwise.
type __lookupTypeFromScope (string typeName, __scope lookupScope);

/// compiler internal API returns the current scope
/// Returns: the current scope
__scope __currentScope();

bool hasInvalidMember(type Enum)
{
     static immutable members = __traits(allMembers, Enum);
     return members.length && members[0] == "Invalid";
}

/// given an enum ($ closureEnumType) where all members are 
type-name (execpt for the first member iff that member is called 
'Invalid' return an array of type values which corrospond the 
type names in the enum. By default the names are looked up in the 
current scope, but this can be customized setting optional the 
lookupScope parameter)
type[] getClosureTypes(type closureEnumType, __scope lookupScope 
= __currentScope())
{
     assert(is(closureEnumType == enum), __FUNCTION__ ~ " expects 
an enum to be passed in" ~
         " which has member named equivalent to the types stored 
in the closure union");

     // type function traits don't produce compiler tuples since 
that would mean a shape change.
     immutable string[] enumMembers =
         __traits(allMembers, 
closureEnumType)[hasInvalidMember(closureEnumType)
                  /*strip the first invalid member if there is 
one*/ .. $];

     __type__[] result;
     result.length = enumMembers.length;

     foreach(i,m;enumMembers)
     {
         __type__ t = __lookupTypeFromScope(m, lookupScope);
         // assert that t is not the __emptyType
         debug { assert(is(t), "Could not find a type named: " ~ 
m); }
         else { if (!is(t))  return null; }
         result[i] = t;
     }

     return result;
}

string genSizeEnumerationCases(type closureEnumType, string 
targetVaribleName)
{
     string result;
     auto closureTypes = getClosureTypes(closureEnumType, 
__currentScope());
     assert(closureTypes != null,
         "An error occurred when getting closure types, perhaps 
the types are not visible from current scope");

     immutable string case_prefix = "case " ~ __traits(identifier, 
closureEnumType) ~ ".";
     foreach(t;closureTypes)
     {
         result ~= case_prefix ~ __traits(identifier, t) ~ ": " ~ 
targetVaribleName ~ " = " ~ t.sizeof ~ "; break;\n";
     }

     if (hasInvalidMember(closureEnumType))
         result ~= case_prefix ~ "Invalid : " ~ targetVaribleName 
~ " = 0;\n";
}

size_t closureSize (ConnectionClosureKind kind) pure nothrow  nogc
{
     size_t result = ConnectionClosure.sizeof;

     size_t size;

     final switch (kind)
     {
         mixin(genSizeEnumerationCases(typeof(kind), "size"));
     }

     result += size;

     return result;
}
---

Look at the concise imperative code above.
It does not rely on any library functionality (except if you want 
to call the compiler internal api a 'library').

Now let's write a template which would do the same thing trying 
to reduce compile times as much as we can:

---
template hasInvalidMember(EnumT)
{
     enum hasInvalidMember = __traits(allMembers, EnumT).length > 
1 && __traits(allMembers, EnumT)[0] == "Invaild";
}

/// Note: Be careful about the instantiation context.
/// This can go very poorly of the type names in EnumT are 
locally shadowed, we can't pass a scope in here so we can't fix 
this!
template getClosureTypes(EnumT)
{
     alias getClosureTypes = mixin(() {
     char[] result = cast(char[])"AliasSeq!("; // let's hope this 
template is defined in the destination of the mixin otherwise we 
will error
     // note: we could fix this my nesting a couple more mixins 
but then the code get's even more bloated
     static assert(is(EnumT == enum), __FUNCTION__ ~ " expects an 
enum to be passed in" ~
         " which has member named equivalent to the types stored 
in the closure union");
     // this will be a statically unrolled tuple foreach bloating 
the size of this
     // since we need to do another mixin within here
     // this might be removed before codegen but you do pay the 
price of building the function before codegen even though it's 
only use once by ctfe.
     // and it will be one function per instance of 
getClosureTypes bloating the internal symbol table.
     foreach(i,m;__traits(allMembers, 
enumT)[hasInvalidMember!(enumT) .. $])
     {
         static assert(is(mixin(m)), m ~ " is either not a type, 
or it's not visible here");
         result ~= m ~ ",";
     }
     // replace the last useless ',' with a ')' to close the 
AliasSeq.
     result[$-1] = ')';
} ());
}

template genSizeEnumerationCases(closureEnumType, string 
targetVaribleName)
{
     enum genSizeEnumerationCases = (() {
     string result;
     alias closureTypes = getClosureTypes!(closureEnumType);
     // also note how we can't assert here that getClosureTypes 
not error ...
     // thereby lengthening the instantiation trace if something 
does go wrong
     immutable string case_prefix = "case " ~ __traits(identifier, 
closureEnumType) ~ ".";
     foreach(t;closureTypes)
     // again unrolled tuple foreach bloating this function ...
     // and again we actually have to build an internal function 
and then we have to interpret it. So we pay for the template 
instance and for CTFE...
     {
         result ~= case_prefix ~ __traits(identifier, t) ~ ": " ~ 
targetVaribleName ~ " = " ~ t.sizeof ~ "; break;\n";
     }

     if (hasInvalidMember!(closureEnumType))
         result ~= case_prefix ~ "Invalid : " ~ targetVaribleName 
~ " = 0;\n";

      return result;
}());
}

size_t closureSize (ConnectionClosureKind kind) pure nothrow  nogc
{
     size_t result = ConnectionClosure.sizeof;

     size_t size;

     final switch (kind)
     {
         mixin(genSizeEnumerationCases!(typeof(kind), "size"));
     }

     result += size;

     return result;
}
---

Without the comments the template would probably be somewhat 
shorter.
But again they are dependent on the external template AliasSeq to 
be visible in the template instantiation context.
CTFE can't cache them because they are new symbols every time.
They use unrolled tuple foreaches increasing the size of the body 
that ctfe and semantic has to deal with.
And they have to generate new symbols persistently ... even 
though those might get stripped the compiler has to allocate 
memory for them and spent time to generate them.
Thereby memory consumption and further reducing scalability.

whereas the type function with extended internal compiler API has 
none of these problems.
And does not rely on library functionality.

With this in mind, please tell me what you think :)

Cheers,
Stefan

Jan 04 2021

Stefan Koch <uplink.coder googlemail.com> writes:

On Monday, 4 January 2021 at 19:30:31 UTC, Stefan Koch wrote:
 Good Evening, [....]


I just realized one of the key differences between type functions 
and templates.

type functions are more declarative than templates which are more 
generative.

templates build up stuff and to see what it does you have to 
instantiate it.
templates generally don't allow higher level reasoning.

type functions are by nature pure and state transformations or 
reductions.
Which you can reason about in isolation.

Jan 04 2021

Ola Fosheim =?UTF-8?B?R3LDuHN0YWQ=?= <ola.fosheim.grostad gmail.com> writes:

On Monday, 4 January 2021 at 20:37:46 UTC, Stefan Koch wrote:
 On Monday, 4 January 2021 at 19:30:31 UTC, Stefan Koch wrote:
 Good Evening, [....]


 I just realized one of the key differences between type 
 functions and templates.

 type functions are more declarative than templates which are 
 more generative.

Hm... I would have thought that a template would be more 
declarative?

Anyway, if you allow loops then it isn't declarative. Meaning, it 
will cause problems if you use it for deduction.

Jan 06 2021

Ola Fosheim =?UTF-8?B?R3LDuHN0YWQ=?= <ola.fosheim.grostad gmail.com> writes:

On Wednesday, 6 January 2021 at 14:12:57 UTC, Ola Fosheim Grøstad 
wrote:
 Hm... I would have thought that a template would be more 
 declarative?

 Anyway, if you allow loops then it isn't declarative. Meaning, 
 it will cause problems if you use it for deduction.


Unless you constrain the loops in such a way that you can easily 
turn them into some kind of recursion.

Jan 06 2021

sighoya <sighoya gmail.com> writes:

On Monday, 4 January 2021 at 19:30:31 UTC, Stefan Koch wrote:
 With this in mind, please tell me what you think :)

I like the idea of type functions for type calculus only, because 
it's easier to get the work done and feels more natural as it is 
pure D-code, not a foreign language to talk with.

Though I wouldn't choose them to introduce generics in D, I think 
templates are enough for that part.


templates build up stuff and to see what it does you have to 
instantiate it.
templates generally don't allow higher level reasoning.

type functions are by nature pure and state transformations or 
reductions.
Which you can reason about in isolation.

Both templates and type functions are functions, the former takes 
code and maps them to other code internally over AST Nodes, the 
latter takes first class values and maps them to first class 
values.

Though, type functions are easier to handle than templates as 
templates aren't really first class functions in D.

Jan 06 2021

Stefan Koch <uplink.coder googlemail.com> writes:

On Wednesday, 6 January 2021 at 14:08:15 UTC, sighoya wrote:
 On Monday, 4 January 2021 at 19:30:31 UTC, Stefan Koch wrote:
 With this in mind, please tell me what you think :)

 I like the idea of type functions for type calculus only, 
 because it's easier to get the work done and feels more natural 
 as it is pure D-code, not a foreign language to talk with.

 Though I wouldn't choose them to introduce generics in D, I 
 think templates are enough for that part.

Indeed templates are enough for that.
The issue comes when you want a typefunction to instantiate a 
template
given a type value, since those values are runtime arguments,
(even though they are evaluated by CTFE)
they cannot be a compile time argument to a template.
As that could change the shape of the function body
(which would make caching impossible and require us to copy the 
function body on every call).

I don't see that much of an issue to have 2 ways of doing the 
same thing.
We have that all the time when a lower-level feature gets 
supplemented with a higher level one.
You just chose the right way for your abstraction level and 
performance requirements.

In the end there is not wanted wanting to convince people without 
data.
I am going to run my experiments and we'll see what comes out :)

Jan 07 2021