Velocity Reviews > template metaprogramming in C?

# template metaprogramming in C?

James Kuyper
Guest
Posts: n/a

 03-28-2012
On 03/28/2012 03:25 AM, Markus Wichmann wrote:
> On 27.03.2012 21:09, Philipp Klaus Krause wrote:
>
>> 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
> 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.
--
James Kuyper

Willem
Guest
Posts: n/a

 03-28-2012
Nils M Holm wrote:
) jacob navia <(E-Mail Removed)> 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
Guest
Posts: n/a

 03-28-2012
Willem <(E-Mail Removed)> wrote:
> 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?

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.

--
Nils M Holm < n m h @ t 3 x . o r g > www.t3x.org

Kaz Kylheku
Guest
Posts: n/a

 03-28-2012
On 2012-03-28, jacob navia <(E-Mail Removed)> wrote:
> 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.

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
Guest
Posts: n/a

 03-28-2012
Le 28/03/12 20:32, Kaz Kylheku a écrit :
> On 2012-03-28, jacob navia<(E-Mail Removed)> wrote:
>> 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
Guest
Posts: n/a

 03-28-2012
On 2012-03-28, jacob navia <(E-Mail Removed)> wrote:
> Le 28/03/12 20:32, Kaz Kylheku a écrit :
>> 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.

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%20tutorial

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
Guest
Posts: n/a

 03-29-2012
On Wed, 28 Mar 2012 11:10:52 +0200, jacob navia wrote:

>> Looks a lot like macros in Scheme.
>>
>> Philipp
>>
>>

>
> ???
> 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
Guest
Posts: n/a

 03-29-2012
Le 29/03/12 17:30, Nobody a écrit :
> On Wed, 28 Mar 2012 11:10:52 +0200, jacob navia wrote:
>
>>> Looks a lot like macros in Scheme.
>>>
>>> Philipp
>>>
>>>

>>
>> ???
>> 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.
>

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
Guest
Posts: n/a

 03-29-2012

"jacob navia" <(E-Mail Removed)> wrote in message
news:jl2kq2\$isg\$(E-Mail Removed)...
> 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.

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.

--
Bartc

Kaz Kylheku
Guest
Posts: n/a

 03-30-2012
On 2012-03-29, jacob navia <(E-Mail Removed)> wrote:
> Le 29/03/12 17:30, Nobody a écrit :
>> On Wed, 28 Mar 2012 11:10:52 +0200, jacob navia wrote:
>>
>>>> Looks a lot like macros in Scheme.
>>>>
>>>> Philipp
>>>>
>>>>
>>>
>>> ???
>>> 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.
>>

>
> 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.