template metaprogramming in C?

[Rui Maciel]

What are your thoughts on adding a standard form of proper template
metaprogramming to the C programming language?


Thanks in advance,
Rui Maciel

 

[Malcolm McLean]

בת×ריך ×™×•× ×©×‘×ª,24 במרס 2012 11:57:11 UTC, מ×ת Rui Maciel:

What are your thoughts on adding a standard form of proper template
metaprogramming to the C programming language?

Standards mean that every plug fits every socket, but only it it's compatible. So a British 3 pin plug with square pins will fit any British mains socket. But it won't fit an American socket, and rightly, because American mains voltage is different and you might damage equipment.

Now in programming, think of the data as the plug and the function interface as the socket. We want any data held be caller to be passed into callee, but only if it's compatible.
So say someone writes

double mean(double *x, int N);

That's not very good if our data is floats, or integers, or if it's the 'salary' field of an array of struct employees. We've got to write special adapter fucntions, just to get the data into a suitable format to pass to mean..

But there are huge problems with a template approach. If we call mean() on an array of floats, we would expect a float back. But the mean of an array of integers is not necessarily an integer. The mean of an array of long doubles or some custome huge integer type might not be representable in double..
Then if you've got a really low precision float type, really you need to sort the input first before summing it. This is likely to be overkill for normal use, however.
There are all sorts of problems, even with this extremely simple function. The problem with templates is that most template systems don't really address these issues. They mean that the function can be passed a double *, int *, or float *, but that's a small win.

 

[Stefan Ram]

What are your thoughts on adding a standard form of proper template
metaprogramming to the C programming language?

With no prior art (i.e., an implementation of this)?

 

[Jens Gustedt]

Am 03/24/2012 12:57 PM, schrieb Rui Maciel:

What are your thoughts on adding a standard form of proper template
metaprogramming to the C programming language?

You mean something going beyond C11's _Generic?

Not going to happen in the near future. First let's digest that one and
see how far we can get.

Jens

 

[Nobody]

What are your thoughts on adding a standard form of proper template
metaprogramming to the C programming language?

My first thought is "If you want C++, you know where to find it".

C++ already has templates and is almost a strict superset of C. What would
be gained from adding templates to C, compared to just using C++? It's not
as if C++ forces you to use OOP or exceptions.

 

[BGB]

What are your thoughts on adding a standard form of proper template
metaprogramming to the C programming language?

I would rather have a standard form of more powerful preprocessor macros.

I had before implemented something like this (as an optional/alternative
preprocessor), which was itself based on the preprocessor used in my
assembler, which was itself partly a mix of the C preprocessor and NASM
macro system (it got some limited use for a few things).


example:
#macro FOO(x, y)
....
multiple...
line...
macro...
#endmacro

unlike a normal macros, you could also put preprocessor directives in it.

#macro FOO(x, y)
#ifdef BAR
....
#else
....
#endif
#endmacro

also,
##...
could be used to create "delayed" preprocessor directives, which would
become further preprocessor directives following the macro expansion (an
could be taken further, as-in, "###...", "####...", ...).

#macro INCLUDE(name)
##include <name>
#endmacro

INCLUDE(stdio.h)

also:
local variables for macros (IIRC, "#deflocal");
"$(...)", which would expand immediately and potentially merge with
adjacent tokens (could be used for variable capture, and macros which
directly compose macro invocations, example: "FOO$(BAR)(x)");
"#assign name pp-expr", which evaluates an expression and assigns it to
a name (a preprocessor variable);
IIRC, also basic looping constructs ("#for()", "#while()", ...).


basically, it could be used in place of (or in addition to) the normal C
preprocessor.


more features are technically possible though.

for example, one could also have:
"#!" syntax (or, "shebang"/"hash-bang");
some sort of list/array/collection feature (so macros can walk lists and
build things);
....

or such...

 

[jacob navia]

Le 24/03/12 12:57, Rui Maciel a écrit :

What are your thoughts on adding a standard form of proper template
metaprogramming to the C programming language?


Thanks in advance,
Rui Maciel

Metaprogramming and templates
-----------------------------

Template metaprogramming has a big drawback: the programming it is done
by the compiler. There is no way for the user to act wthin the template
environment. Even simple things like template argument checking
("concepts" in C++ terminology) is quite impossible: Bjarne has tried
for 3 years or more and wasn't able to get it right.

I have been proposing another approach for a long time, but I have been
bogged down because of my isolation and the lack of support from any
institution. Since I have to earn my life with consulting jobs, I can't
go very far.

The direction I am going is to establish real compile time functions
where you have a rich and controlled environment where you develop your
meta-programs, instead of the incredible limited environment of
templates where you do not have even an if statement!

The central points of my approach are as follows:

1: Event oriented programming. The compiler generates a sequence of
events while compiling: Start/end of function, start/end of line,
statement, etc. Any error generates an event too. You can then, in a
similar way to event oriented programming under windows or Macintosh
"add code" to be run by the compiler *within the compiler itself* that
will generate code according to the arguments of the event. You dispose
in a controlled way all the compilation environment for you. You can
query the types of the arguments, local variables, etc etc.

As a demonstration I added a profiler that uses the RDTSC machine
instruction to generate very detailed and accurate logs of time passed
at each statement/function.

2: Calling template code from within your code. You can use special
syntax to call your own template procedures by writing in your code
ListGen<Var=mylist,Type=mylistType,InitialSize=10>

That is an "undefined variable" error. You subclass that error, and
you are all set, able to generate code for a list as you wish.


The programming language used to program in the metaprogramming
environment is.... well, you guessed! IT IS THE C language. You
program all your meta-programming code in C, you compile it with
lcc-win, and the compiler loads it when it starts.

The input of your function is the program text at the point of the
event, i.e. you will find the text of the template in the code buffer.

The output of your function is text: the generated code for the
functionality you want. That code is re-injected into the compiler input
stream and processed as you wuld have typed it, just as the
templates of C++.

Of curse this is MUCH more advanced. You do not need to bother about
"concepts": you can check your arguments yourself within your
metaprogram: you have all the normal constructs of C99 at your disposal.

You aren't dependent of the compiler "understanding correctly" what you
want since you can EXACTLY generate what you want.

Look, this is not just empty talk. I have added for instance the require
and ensure statements of the Eiffel language to an experimental version
of the compiler to implement the "Design by contract" paradigm.

I started implementing objective C, but it is not ready yet. I have
several customers to serve, and two kids+wife...

The reaction in this group has been abysmal, as always. Anyway, here are
my ideas again

jacob

 

[Ian Collins]

No, but it forces you to cast too much (a tremendous irony given
Stroustrup's stated design goal),

In idiomatic C++, casts are hardly ever used.

doesn't have designated initializers, doesn't have compound literals,

True, designated initialisers are a surprising omission in the latest
C++ standard.

implicitiy typedefs structure definitions,

A good thing!

and several other issues commonly encountered. And that was just compared to
C99. It's a long shot from "almost a strict superset of C".

Unfortunately the two are drifting further apart.

If you're limiting yourself to a common denominator syntax of C and C++,
then you're missing out on much of what each language uniquely has to offer.

Very true.

 

[Ian Collins]

What are your thoughts on adding a standard form of proper template
metaprogramming to the C programming language?

Considering its sanity damaging effects in C++, not a great idea!

You can't do template meta-programming without some form of templates,
which I doubt we will ever see in C.

 

[Guest]

No, but it forces you to cast too much (a tremendous irony given
Stroustrup's stated design goal),

how? I'm a C++ programmer and I don't do a lot of casting.

doesn't have designated initializers,
doesn't have compound literals, implicitiy typedefs structure definitions,

good! One of C++'s better ideas.

and several other issues commonly encountered. And that was just compared to
C99. It's a long shot from "almost a strict superset of C".

no, it's nearer a super-set of C89

 

[Rui Maciel]

Considering its sanity damaging effects in C++, not a great idea!

What are "these sanity damaging effects"?


Rui Maciel

 

[Ian Collins]

What are "these sanity damaging effects"?

Have you ever tried any serous meta-programming in C++?

 

[Rui Maciel]

Have you ever tried any serous meta-programming in C++?

That will depend on your definition of "serious meta-programming". Even
then, I don't see how your opinion on template metaprogramming could vary
depending on someone else's experience with template metaprogramming.


Rui Maciel

 

[Guest]

That will depend on your definition of "serious meta-programming". Even
then, I don't see how your opinion on template metaprogramming could vary
depending on someone else's experience with template metaprogramming.

i suppose he was wondering if you'd dug deeply into TMP if you couldn't see the sanity bending. What was it... concepts they had to drop from the C++ standard because even very smart people were struggling with it.

from wikipedia: "the syntax and idioms of template metaprogramming are esoteric compared to conventional C++ programming, and template metaprograms can be very difficult to understand"

though it goes on to say programs can be shorter and esier to understand by people familiar with TMP

 

[Markus Wichmann]

בת×ריך ×™×•× ×©×‘×ª, 24 במרס 2012 11:57:11 UTC, מ×ת Rui Maciel:
Standards mean that every plug fits every socket, but only it it's
compatible. So a British 3 pin plug with square pins will fit any
British mains socket. But it won't fit an American socket, and
rightly, because American mains voltage is different and you might
damage equipment.

Now in programming, think of the data as the plug and the function
interface as the socket. We want any data held be caller to be passed
into callee, but only if it's compatible. So say someone writes

double mean(double *x, int N);

That's not very good if our data is floats, or integers, or if it's
the 'salary' field of an array of struct employees. We've got to
write special adapter fucntions, just to get the data into a suitable
format to pass to mean.

Then we define the C interface as used for qsort: We need to know:

- How big one array element is
- How big the entire array is
- How to add two array elements
- How to divide an array element by an integer
- Where to store the result

That makes:

void mean(void* res, void* base, size_t size, size_t nmemb, void
(*add)(void*, const void*), void(*div)(*void, size_t));

With the semantics:

res - Where to store the result
base - The start of the array
size - The size of a single array member
nmemb - The number of members
add - Adds two array members and stores the result in the first argument
div - Divides an array member by an integer and stores the result in the
first argument.

With the implementation:

void* mean(void *res, void* base, size_t size, size_t nmemb, void
(*add)(void*, void*), void(*div)(*void, size_t))
{
char* our_base = base;
if (nmemb) memcpy(res, base, size);
for (size_t i = 1; i < nmemb, i++) {
add(res, our_base[i * size]);
}
if (nmemb) div(res, nmemb);
}

So a call to this function for a mean over doubles would be

void double_add(void* a, const void* b)
{
*(double*)a += *(const double*)b;
}

void double_div(void* a, size_t n)
{
*(double*)a /= n;
}

double double_mean(double* b, size_t n) {
double res;
mean(&res, b, sizeof *b, n, double_add, double_div);
return res;
}

Now, _that_'s a simple interface...

Incidentally, this interface is also generic enough to support other
means, like the geometric mean (if you set *add to be code to multiply
and *div to be code to draw the n-th root).

But there are huge problems with a template approach. If we call
mean() on an array of floats, we would expect a float back. But the
mean of an array of integers is not necessarily an integer. The mean
of an array of long doubles or some custome huge integer type might
not be representable in double.

So we could always return long double... but that would require a mean
that could always be expressed in a long double

Then if you've got a really low
precision float type, really you need to sort the input first before
summing it.

So that the really small values can even make a dent in the mean? But if
you mix values in the array which make addition idempotent (meaning if
you have two values a and b, then a + b could still equal the greater
value), the small values won't change the outcome anyway, will they?
They might as well be zero. The only possible thing that can happen is
if you have several of those small values so that when added
together they produce a carry over into bits that will still be in the
result. However, you would need a really big load of those values for
the carry to make it to some significant bits. I always consider a few
of the least significant bits of a floating point value fickle.

This is likely to be overkill for normal use, however.
There are all sorts of problems, even with this extremely simple
function. The problem with templates is that most template systems
don't really address these issues. They mean that the function can be
passed a double *, int *, or float *, but that's a small win.

Right you are. For anything else, you would need to write your own mean
function.

Ciao,
Markus

 

[Philipp Klaus Krause]

So that the really small values can even make a dent in the mean? But if
you mix values in the array which make addition idempotent (meaning if
you have two values a and b, then a + b could still equal the greater
value), the small values won't change the outcome anyway, will they?
They might as well be zero. The only possible thing that can happen is
if you have several of those small values so that when added
together they produce a carry over into bits that will still be in the
result. However, you would need a really big load of those values for
the carry to make it to some significant bits. I always consider a few
of the least significant bits of a floating point value fickle.

Mean of HUGE_VAL, DBL_EPSILON * 4.0, 0.0 and -HUGE_VAL, assuming
HUGE_VAL is not infinity.

Philipp

 

[Philipp Klaus Krause]

The direction I am going is to establish real compile time functions
where you have a rich and controlled environment where you develop your
meta-programs, instead of the incredible limited environment of
templates where you do not have even an if statement!

[…]

Looks a lot like macros in Scheme.

Philipp

 

[Markus Wichmann]

Mean of HUGE_VAL, DBL_EPSILON * 4.0, 0.0 and -HUGE_VAL, assuming
HUGE_VAL is not infinity.

If we sort the above list as:

-HUGE_VAL, 0.0, DBL_EPSILON * 4., HUGE_VAL

The sum would be

s1 = -HUGE_VAL
s2 = -HUGE_VAL
s3 = -HUGE_VAL (because DBL_EPSILON * 4 is most certainly shifted out
completely by that addition)
s4 = 0.0

so in the end the sum would be 0. If we order it a bit differently, though:

-HUGE_VAL, HUGE_VAL, 0.0, DBL_EPSILON * 4

the sum comes around to DBL_EPSILON * 4 (so the mean would be DBL_EPSILON)

There doesn't appear to be an always perfect sorting algorithm for this
problem. At least none I can think of right now. We can't sort by
descending magnitude, because then the effect of the added carry values
might not appear.

Generally, we should try to sort in a way such that the magnitude of the
list sum is maximized... shouldn't we? Damn, what's the real goal here?
Order by descending magnitude, then for each value in the list try to
add as many other values as possible so that the magnitude is minimized?
I mean, like

order_list_by_descending_magnitude(list);
double s = list[0];
unsigned int used = 1;
assert(n < sizeof used * CHAR_BIT);
while (used < (1 << n) - 1) {
int done_any = 0;
for (int i = 1; i < n; i++) {
if (!(used & (1 << i)) && signbit(s) != signbit(list))
{
s += list;
done_any = 1;
used |= 1 << i;
}
}
if (!done_any) break;
}
for (int i = 0; i < n; i++) {
if (!(used & (1 << (n - i - 1)))) s += list[n - i - 1];
}

return s/n;

Philipp

Ciao,
Markus

 

[jacob navia]

Le 27/03/12 21:17, Philipp Klaus Krause a écrit :

The direction I am going is to establish real compile time functions
where you have a rich and controlled environment where you develop your
meta-programs, instead of the incredible limited environment of
templates where you do not have even an if statement!

[…]

Looks a lot like macros in Scheme.

Philipp

???
Scheme macros have if/while statements that allow you to generate code
in loops?

 

[Nils M Holm]

Scheme macros have if/while statements that allow you to generate code
in loops?

Scheme macros are Scheme programs that do whatever you want
at read/compile time. That's part of the beauty of Scheme.