template metaprogramming in C?

[James Kuyper]

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?

The following is not my idea, but I don't know who the true originator was.

Roundoff error is dominated by the magnitude of the larger item being
added. Therefore, you want to arrange as much cancellation as possible,
to keep the magnitudes small. At each step in the sum, add the item not
previously included which will make the next partial sum have the
smallest magnitude. One way to implement this is to sort the list, and
then set two pointers to point at the smallest positive and negative
values in that list. Add either the positive or negative value,
whichever is opposite to the sign of the current sum, moving the
corresponding pointer away from the other one. When either end of the
list is used up, add in the remaining items from the other end of the
list in order of increasing magnitude.

 

[Willem]

Nils M Holm wrote:
)> 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.

I thought they worked on parse trees, not on textual code?
(And yes, that's actually better, I know.)


SaSW, Willem
--
Disclaimer: I am in no way responsible for any of the statements
made in the above text. For all I know I might be
drugged or something..
No I'm not paranoid. You all think I'm paranoid, don't you !
#EOT

 

[Nils M Holm]

Nils M Holm wrote:
) Scheme macros are Scheme programs that do whatever you want
) at read/compile time. That's part of the beauty of Scheme.

I thought they worked on parse trees, not on textual code?

Yes, they do. Talking about "Scheme macros" is not helpful for
further investigation, though, because there are different Scheme
macro systems using different approaches. Ancient Scheme systems
used "low-level" macros, which were basically Scheme programs that
ran at parse time/compile time instead of run time. E.g. the Scheme
function

(define (sq x) (* x x))

would compute the square of X at run time and the macro

(define-macro (sq x) (* x x))

would do the same, but at compile time. The output of a macro
is another syntax tree that is then compiled and executed. So we
can create control structures with macros:

(define-macro (WHEN p . body)
`(if ,p (begin ,@body)))

WHEN implements an IF without an alternative and a variable
number of conditional statements. The `(...) is a template
in which every expression introduced with a "," will be replaced
by the value of that expression. So

(when (= 1 1) (display "foo") (newline)))

would expand to

(if (= 1 1) (begin (display "foo") (newline)))

There are actually no limits on things that macros can do. For
instance, the following macro would generate a program that would
print some stripped-down 99-bottles-of-beer lyrics at run time:

(define-macro (bottles x)
(let loop ((n 0)
(out '()))
(if (> n x)
`(for-each (lambda (x)
(display x) (newline))
',out)
(loop (+ n 1)
(cons (string-append (number->string n)
" bottles of beer")
out)))))

Given this definition,

(bottles 99)

would expand to

(for-each
(lambda (x)
(display x)
(newline))
'("99 bottles of beer" "98 bottles of beer"
"97 bottles of beer" "96 bottles of beer"
...
"1 bottles of beer" "0 bottles of beer"))

Note that the complete lyrics would be generated a compile time.

Modern Scheme systems use pattern-matching and rewriting macro
systems, like SYNTAX-RULES or SYNTAX-CASE, but they are much more
complex, and this off-topic posting is probably long enough already.

 

[Kaz Kylheku]

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?

In general, Lisp macros have been doing this since the 1960's.

Scheme macros are distinguished by pioneering lexical scoping with automatic
hygiene. Macro code templates, into which arbitrary user code is inserted, can
simply declare local variables in a straightforward way; yet the inserted code
does not have visibility into these variables. A hidden renaming process
eliminates the potential for a clash.

Common Lisp macros are more "nuts-and-bolts"; hygiene is DIY, but with more
flexibilities.

The object system is based on macros: class defining, method defining.

The standard LOOP macro is an entire sublanguage for iteration, expanded by a
macro, and makes a good macro demo:

(loop for x in '(1 2 3 5)
summing (* x x) into sum-of-squares
counting x into n
finally (return (sqrt (/ sum-of-squares n))))

-> 3.122499

View the (implementation-specific, not portable Lisp) expansion:

(macroexpand '(loop for x in '(1 2 3 5)
summing (* x x) into sum-of-squares
counting x into n
finally (return (sqrt (/ sum-of-squares n)))))

->

(MACROLET ((LOOP-FINISH NIL (SYSTEM::LOOP-FINISH-ERROR)))
(BLOCK NIL
(LET ((#:LIST-8731 '(1 2 3 5)))
(PROGN
(LET ((X NIL))
(LET ((N 0) (SUM-OF-SQUARES 0))
(MACROLET ((LOOP-FINISH NIL '(GO SYSTEM::END-LOOP)))
(TAGBODY SYSTEM::BEGIN-LOOP (WHEN (ENDP #:LIST-8731) (LOOP-FINISH))
(SETQ X (CAR #:LIST-8731))
(PROGN (SETQ SUM-OF-SQUARES (+ SUM-OF-SQUARES (* X X)))
(WHEN X (INCF N)))
(PSETQ #:LIST-8731 (CDR #:LIST-8731)) (GO SYSTEM::BEGIN-LOOP)
SYSTEM::END-LOOP
(MACROLET
((LOOP-FINISH NIL (SYSTEM::LOOP-FINISH-WARN) '(GO SYSTEM::END-LOOP)))
(PROGN (RETURN (SQRT (/ SUM-OF-SQUARES N))))))))))))) ;

 

[jacob navia]

Le 28/03/12 20:32, Kaz Kylheku a écrit :

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

On 25.03.2012 01:21, jacob navia wrote:


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?

In general, Lisp macros have been doing this since the 1960's.

OK, it is high time then that we get similar capabilities in C.

Compile time functions can access the compiler environment in a
controlled way. (Probably Scheme macros too). The practical usage is
that you can decide your container structure based on the
characteristics of the object being stored, for instance.

Let's say you have a list. Instead of having a pointer to the data, you
can check if sizeof(data) is less or equal than sizeof(void *). If that
is the case it is just much better to store the data directly in the
space the pointer would occupy, saving sizeof(void *) bytes and
an indirection.

Etc. That is the idea.

 

[Kaz Kylheku]

Le 28/03/12 20:32, Kaz Kylheku a écrit :

OK, it is high time then that we get similar capabilities in C.

Compile time functions can access the compiler environment in a
controlled way. (Probably Scheme macros too). The practical usage is
that you can decide your container structure based on the
characteristics of the object being stored, for instance.

Let's say you have a list. Instead of having a pointer to the data, you
can check if sizeof(data) is less or equal than sizeof(void *). If that
is the case it is just much better to store the data directly in the
space the pointer would occupy, saving sizeof(void *) bytes and
an indirection.

Etc. That is the idea.

There is a project called GCC MELT which provides a Lisp dialect for writing
plugins for GCC to do this type of stuff.

http://gcc-melt.org/

It doesn't seem like the easiest thing in the world to use.

http://gcc.gnu.org/wiki/MELT tutorial

The plugins you write are not really integrated into your program; they get
compiled into modules that go into the compiler (but I suppose it can be
close enough for some practical purposes).

 

[Nobody]

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

A Lisp macro is essentially a function which returns Lisp code (a
fundamental feature of Lisp is that code is data, making it ideal for
metaprogramming). When compiling Lisp functions, macros are expanded by
evaluating the macro body and compiling the returned code. Unlike normal
function calls, the macro's arguments are passed verbatim (as expressions)
rather than being evaluated first.

 

[jacob navia]

Le 29/03/12 17:30, Nobody a écrit :

A Lisp macro is essentially a function which returns Lisp code (a
fundamental feature of Lisp is that code is data, making it ideal for
metaprogramming). When compiling Lisp functions, macros are expanded by
evaluating the macro body and compiling the returned code. Unlike normal
function calls, the macro's arguments are passed verbatim (as expressions)
rather than being evaluated first.

Then, I am doing exactly that: A meta programming C function is a
function that inputs text and outputs text. The text that is the input
of the function is the stream of text that is before the compiler
parsing point. The output of the meta-programming function is text that
is inserted at the point of call into the compiler stream.

Note that the inserted text will generate further events that could
call further events functions.

Of course a meta-function doesn't need to generate text. It could just
record some event for later use, for instance to give a list of all
objects defined in a compilation unit, or whatever.

 

[BartC]

Le 29/03/12 17:30, Nobody a écrit :

Then, I am doing exactly that: A meta programming C function is a function
that inputs text and outputs text. The text that is the input of the
function is the stream of text that is before the compiler parsing point.
The output of the meta-programming function is text that is inserted at
the point of call into the compiler stream.

C isn't known for it's text-processing abilities, but you're using it to
transform one stream of text into another?

I'd imagine also that using the same language for the meta-programming as
both the input and output languages, things could get a trifle confusing.

However it would be interesting to see how it works in practice.

 

[Kaz Kylheku]

Le 29/03/12 17:30, Nobody a écrit :

Then, I am doing exactly that: A meta programming C function is a
function that inputs text and outputs text.

Then, you're doing it wrong. Firstly, C is one of the lousiest languages in the
world for metaprogramming. If you want to do anything "meta" in C,
you don't want to do it in C. Lisp is used for metaprogramming Lisp, not
simply for the sake of making the metaprogramming language the same as
the meta-programmed language. The metaproramming happens because Lisp is an
excellent language for metaprogramming (which evoled along with the
language right from the beginning).

Look at that GCC MELT project: they are not using C as the meta-programming
language, for good reasons.

Secondly, the Lisp macro is not a text to text mapping. It filters an AST
data structure to to an AST data structure: it is tree to tree rewriting. Text
to text mapping is the same as the C preprocessor, or tools like m4. If you
just want text to text mapping that's better than the preprocessor, just pull
m4 off the shelf. m4 has all that cruft missing from the C preprocessor, like
looping over lists of things, if/then/else decisions, etc.

 

[Stefan Ram]

If you want to do anything "meta" in C,
you don't want to do it in C.

My simple metaprogram in C:

#include <stdio.h>

int main( void )
{ char const * const names[] ={ "maxi", "maxd" };
char const * const types[] ={ "int", "double" };
printf( "#include <stdio.h>\n\n" );
for( unsigned i = 0; i < sizeof types / sizeof 0[ types ]; ++i )
{ char const * type = i[ types ];
printf
( "%s %s( %s const a, %s const b ){ return a > b ? a : b; }\n",
type, i[ names], type, type ); }
printf( "\nint main( void )\n" );
printf( "{ printf( \"%%d\\n\", maxi( 2, 3 ));\n" );
printf( " printf( \"%%g\\n\", maxd( 2.0, 3.0 )); }\n" ); }

It contains the pattern "a > b ? a : b" to find a maximum and then
applies this pattern to the types of »int« and »double«.

 

[Kaz Kylheku]

I'd imagine also that using the same language for the meta-programming as
both the input and output languages, things could get a trifle confusing.

It only gets confusing if you do it right.

If the metaprogramming language is the same as the metaprogrammed language, but
the trees of the metaprogrammed language appear only as encapsulated data
structures, there is no such confusion. But that situation extremely
inconvenient.

Early Lisp metaprogramming was done by writing very clumsy code which analyzed
and constructed code. If you wanted to construct the expression (+ left right)
but where the left and right are pieces of code that you have in variables
x and y, something like (LIST '+ X Y). Make a list of out of the symbol +, and
the values of X and Y.

Then the backquote was invented which allowed code to be generated with a
constructor notation that much more closely resembles the language:

`(+ ,x ,y)

You write the template as a literal: you quote a piece of the meta-programming
program with the backquote, and then you nidicate the variable parts with
unquotes and splices denoted by , and ,@.

Backquotes can nest, and occur in the unquotes and splices, so very complicated
situations can be hard to understand because of the level confusion: what is
meta and what isn't.

But the overwhelming convenience and notational clarity of backquote trumps
these issues. (And the confusion can be combated by refactoring code into
small functional chunks instead of nesting a whole lot of stuff in one place.)

You basically want the meta-language to be the same as the language precisely
so that you can just quote any construct in the meta-language to obtain a piece
of AST, into which you can substitute things.

It's easier because you're just dealing with one language, and then keeping in
mind what is in the metaprogram and what is in the program. (Or, sometimes,
what is in the meta-meta-program, what is in the meta-program and what is in
the program.)

It's easier to shift between these levels, too. Somtimes you put something into
the program being generated, but then later you want to hoist it back into the
metaprogram: i.e. make it a compile-time calculation. If the two languages
are the same, it's easy to do this while keeping most of the code the same,
or very similar.

Also, sometimes you want to evaluate parts of the meta-material at
macro-expansion time. This is easy if the language is the same: just pass the
tree to the built-in eval function. You don't need a separate eval function for
the target language.

Probably the main reason for using one language is that there are multiple
levels of metaprogramming, not only one. The meta-programming macros themselves
use macros, and those macros can be written using macros: i.e. the
meta-language is applied to itself to create better metaprogramming: it is
turned in on itself. You don't want N different languages for N different
meta-levels; it's simply not practical, and not even possible when N is
unbounded.

 

[Ian Collins]

Le 29/03/12 17:30, Nobody a écrit :

Then, I am doing exactly that: A meta programming C function is a
function that inputs text and outputs text. The text that is the input
of the function is the stream of text that is before the compiler
parsing point. The output of the meta-programming function is text that
is inserted at the point of call into the compiler stream.

Is that meta-programming, or emulation the eval() function common to
scripting languages? Or is eval() meta-programming?

 

[BartC]

#include <stdio.h>

int main( void )
{ char const * const names[] ={ "maxi", "maxd" };
char const * const types[] ={ "int", "double" };
printf( "#include <stdio.h>\n\n" );
for( unsigned i = 0; i < sizeof types / sizeof 0[ types ]; ++i )
{ char const * type = i[ types ];
printf
( "%s %s( %s const a, %s const b ){ return a > b ? a : b; }\n",
type, i[ names], type, type ); }
printf( "\nint main( void )\n" );
printf( "{ printf( \"%%d\\n\", maxi( 2, 3 ));\n" );
printf( " printf( \"%%g\\n\", maxd( 2.0, 3.0 )); }\n" ); }

It contains the pattern "a > b ? a : b" to find a maximum and then
applies this pattern to the types of »int« and »double«.

Is this meta-programming, or just programming? It looks like something that
would be run as an external utility, rather than a piece of meta-code
encountered within a normal program, and the output of which is then
available to the rest of the source code.

(And if run as an external program, then anything slightly more complex
would be less painful to write with any scripting language.)

And even as a C meta-program, if shows the limitations of using C: you
really want to loop through all the numeric types, and have access to the
names of those types, as well as literals in each of those types, without
having to manually enumerate each.

Try out a real task (which I have a use for myself, and currently use
external utilities for, generating include files):

You have a number of functions in a module, some of which have textual
meta-data (in the form of a stylised comment for example); scan those
functions with a specific kind of meta-data, read the values listed in the
metadata, and create a table (an initialised array of structs perhaps),
containing pointers to those functions, the names of the functions, and the
values for those functions.

And put the table at the location where the meta-program is encountered.

As an added bonus, create a list of prototype declarations suitable for
adding to a header (not strictly necessary, as you might expect to create
such prototypes yourself at the same time as you write each function).

(Actually, this is not very easy. It would require a separate pass of it's
own from the compiler. It might get recursive, if the meta-program adds new
functions which themselves have meta-data! Or if the meta-program generates
a new version of itself. However, if this was possible, it would be great:
forget my example; you can create a meta-program macro which automatically
generates function prototypes for example.)

 

[Malcolm McLean]

בת×ריך ×™×•× ×©×™×©×™, 30 במרס 2012 04:32:50 UTC+1, מ×תIan Collins:

Is that meta-programming, or emulation the eval() function common to
scripting languages? Or is eval() meta-programming?

It's meta programming is you generate the string to be evaluated on the fly.. If you hardcode it, it's just using an interpreted rather than a compiledlanguage.

If the string is entered by the user, it raises the question of where the biundary lies between using an application and programming. Complex and flexible applications have a tendency to turn into programming languages in their own right.

 

[jacob navia]

Le 30/03/12 11:52, BartC a écrit :

Try out a real task (which I have a use for myself, and currently use
external utilities for, generating include files):

You have a number of functions in a module, some of which have textual
meta-data (in the form of a stylised comment for example); scan those
functions with a specific kind of meta-data, read the values listed in
the metadata, and create a table (an initialised array of structs
perhaps), containing pointers to those functions, the names of the
functions, and the values for those functions.

The "meta-comment" is the sequence /*@ */. This sequence generates an
event that can be subclassed.

Your function then, just parses the comment since all the input is
available.

And put the table at the location where the meta-program is encountered.

You generate code that builds those structures. Obviously you have to
take care WHERE you put the meta comment, for instance you can't put it
in the middle of an expression:

double d = (sqrt(s+3.14)/25/*@metacomment*/*m;

You can put it only in a place where a structure definition is possible,
i.e. at the beginning of a statement.

As an added bonus, create a list of prototype declarations suitable for
adding to a header (not strictly necessary, as you might expect to
create such prototypes yourself at the same time as you write each
function).

Well, lcc can already parse a file and write the prototypes at the end
of the compilation and I thought that in the meta-programming
environment this could be just a function call away:

char *proto = MakeProto(function_type);

(Actually, this is not very easy. It would require a separate pass of
it's own from the compiler. It might get recursive, if the meta-program
adds new functions which themselves have meta-data!

When code is injected into the compiler stream, the event that has fired
is disabled, and the generated code can't generate the same event. It
can generate OTHER events though.

Or if the
meta-program generates a new version of itself. However, if this was
possible, it would be great: forget my example; you can create a
meta-program macro which automatically generates function prototypes for
example.)

Yes

 

[James Dow Allen]

Simple operations are too simple to benefit from
"metaprogramming" and complicated operations are too
complicated to benefit. There is a smallish set of
problems of intermediate complexity (e.g. graph traversal)
which might benefit.

void mean(void* res, void* base, size_t size, size_t nmemb, void
(*add)(void*, const void*), void(*div)(*void, size_t));
...
Now, _that_'s a simple interface...

I *think* this is a sort of parody and you're taking
my side in the debate.

Incidentally, those worried about precision loss in
summing floating point numbers might want to Google
Kahan summation algorithm

James