C types are inside-out

The simplifying fantasy employed by many C and C++ programmers is that the type constructors * and [] (and, for C++, &) are all postfix operators. It's certainly a seductive theory:

char*[]	array of pointer to char
char**&	reference to pointer to pointer to char
char**const	const pointer to pointer to char
char const**	pointer to pointer to const char

Just read it backwards, and that's what it is. This theory cracks if you try char[]*, which should be a pointer to an array of char, but is in fact a syntax error. (Pointer to array of char is char(*)[]).

A good example of inside out is char*[](). Reading it forward (clearly wrong) would be pointer to array of function, and reading it backward would be function returning array of pointer (plausible). In fact you have to read it bottom-up: the parse of the right hand side goes [], [](), *[](), as in:

[]     (array of ...)
[]()   (array of function returning ...)
*[]()  (array of function returning pointer to ...)

The top-level type constructor ([], array of) is the bottom-level piece in the parse tree. And since there are both prefix and postfix operators, you can't just read it forward or backward. You have to read it inside out.

The bottom-up instead of top-down is because, in the immortal words of the C IAQ, "in C, declaration reflects use, but it's one of those weird distorted mirrors."

This isn't to say that our type patterns have to suffer the same fate. One can avoid the inside out syntax by exclusively using typedefs and only one type constructor at at time:

typedef char T1;
typedef T1 \*T2;
typedef T2 T3();
typedef T3 T4[];

and now T4 is, quite understandably, array of function returning pointer to char. A more plausible example, since an array of functions isn't actually a valid type (the point still holds for valid types, they just make for more complicated examples) is the definition of the Unix signal function:

int (*signal(int(*)(int)))(int)

which sane manual pages write as something like:

typedef int sighandler(int);
sighandler* signal(sighandler*);

or

typedef int (*sighandler)(int);
sighandler signal(sighandler);

One solution (the only reasonable one, I think) is to allow the full C type syntax in the type patterns, and then, just as good C programmers make judicious use of typedefs encourage good extension writers to make judicious use of type variables, so that one could write:

t ~ `{(int(*(int(*)(int)))(int))}

but one would instead choose write one of:

t ~ `{\t1*(\t2*)} && t1 ~ `{int(int)} && t2 ~ `{int(int)}
t ~ `{\t1(\t2)} && t1 ~ `{int(*)(int)} && t2 ~ `{int(*)(int)}

or

t ~ `{\t1*(\t2*)} && t1 ~ `{int(int)} && t2 == t1
t ~ `{\t1(\t2)} && t1 ~ `{int(*)(int)} && t2 == t1

or even, perhaps, one of:

t ~ `{\t1*(\t1*)} && t1 ~ `{int(int)}
t ~ `{\t1(\t1)} && t1 ~ `{int(*)(int)}

I don't really like the implications of the last pair, though I do admit they make for concise notation.