type variables

[Paul Backus]

On Sunday, 2 August 2020 at 00:19:46 UTC, Bruce Carneal wrote:
> Current dlang type 'variables' are created in a strictly 
> functional style.  IOW, they come from declarative syntax, CTFE 
> constants, and possibly recursive application of templates.

In D, currently, there are a few different ways you can refer to 
a type.

1) By its name.

     int x; // refers to `int` by name

2) By an alias.

     alias T = int;
     T x; // refers to `int` by the alias `T`

3) By a template parameter.

     template foo(T) {
         T x; // refers to any type by the parameter `T`
     }

4) By a typeof expression.

     typeof(42) x; // refers to `int` by the expression 
`typeof(42)`

5) By a __traits expression.

     struct Node {
         int data;
         __traits(parent, data)* next;
         // refers to `Node` by the expression `__traits(parent, 
data)`
     }

6) By a string mixin.

     mixin("int") x; // refers to `int` by the string mixin 
`mixin("int")`

By "type variables", I am going to assume you mean #2 and #3, 
aliases and template parameters, since they both involve giving 
an existing type a new name.

Currently, these "type variables" are immutable, in the sense 
that once a name is given to a type, the same name cannot later 
be given to a new type. For example, you are not allowed to write 
code like this:

     alias T = int;
     T x = 42;
     T = string; // error: can't assign to an alias
     T s = "hello";

In general, this is a good thing--having `T` refer to two 
different types at two different points in the program makes the 
code harder to read (because you have to keep track of which type 
it refers to) and harder to modify (because you have to make sure 
the changes to `T` and its uses remain in the correct order 
relative to one another).

However, in certain specific contexts, the ability to modify an 
alias or a template parameter can be useful. This is where 
proposals like type functions come in: they provide a context in 
which aliases like `T` can be mutated, while still leaving them 
immutable in "normal" D code.

> Pure functional programming is great wrt correctness, it's 
> working today, but it's not-so-great when it comes to 
> readability/maintainability.  For starters, composition is a 
> challenge.  Unwinding recursions in your head is another 
> challenge.  Debugging is another challenge.

The main issue with recursion is not that it is difficult to 
understand or maintain, but that it has poor performance. In 
order to process an argument list of length N using template 
recursion, N separate template instantiations are required. Using 
mutation instead of recursion would reduce the memory required by 
such templates from O(N) to O(1).

This is the primary motivation behind proposals like Stefan 
Koch's type functions and Manu's `...` operator.

> Additionally, any template recursions extend the type names in 
> a very ugly way.  Yes, the extension will give you a unique 
> (unintelligible ginormous) name but that's about it.  Seems 
> that we should be able to get a unique mangle without the 
> garbage, something that a human could read and have a prayer of 
> understanding while the universe is still warm.

As far as I'm aware, the problem with ginormous names had nothing 
to do with template *recursion*. Rather, it resulted from the 
fact that code making heavy use of templates (for example, UFCS 
chains of std.algorithm and std.range functions) generated names 
in which the *same exact* type names were *repeated* many, many 
times.

If you know of an example of excessively large symbol names 
resulting *specifically* from template recursion, I would be 
interested to hear about it.