Compile time function execution...

[Kevin Bealer]

Walter Bright wrote:
> Andrei Alexandrescu (See Website For Email) wrote:
>> This is by far the least interesting application of this stuff. I 
>> don't even count it when I think of the feature. "Oh, yeah, I could 
>> compile square root at compile time. How quaint."
> 
> I agree. I need a better example. Any ideas?

(Sorry that this got so long -- it kind of turned into a duffel bag of
things I've been thinking about.)

I think the most common case is like the plot for a TV show.  Code that
is semi-interesting, semi-predictable, and semi-repetitive.  If the code
is too interesting, you would need to write it all.  If it was too
repetitive, you could just use a standard D template (boilerplate).

Tasks that are in between -- non-boilerplate, but fairly 'formulaic', 
where the details are not interesting, is the candidate for this.

To me there are a couple special reasons that stick out.

1. You're building complex types and need to base them on standard
    definitions that might change.  I see this with ASN.1 definitions
    at work.  We have a program that builds C++ code from ASN.1 or
    XML schemas.

    A. Some of our programs need to stream 100s of MB of data so this
       code needs to be as fast as possible.

    B. If a field is added to the definition it has to appear in all
       the code objects.

    C. There is additional logic -- i.e. if a 'mandatory' field is
       not assigned, the serializer has to throw an exception.

2. You're building the inner loop in some performance critical
    application and the rules (expressions and conditional logic)
    used there need or benefit from ultra-optimization.

    This is what (in my view) compile time regex is for, I would
    normally use a runtime regex for ordinary things like parsing
    configuration files.

3. You need a lot of code duplication (i.e. to provide stub functions
    something) and don't want to repeat yourself to get it.

---

This is how I imagine it:

Some of these ideas have been kicking around in my head, but I'm not 
sure how practical they are.  When I use the word templates here but I 
mean any kind of code generation.

Starting scenario: Let's say I'm writing a program to solve some
mathematical task.

1. I create a top level class and add some members to it.

2. I add some sub-classes, a dozen or so, mostly just POD stuff.

3. Some of these have associative arrays, user-defined tree stuff,
    regular arrays, hand coded linked lists, etc.

4. I put in a bunch of graph theory code and number crunching stuff.


Uses of metaprogramming:

1. Now let's say that this application is taking a while to run, so I 
decide to run it in steps and checkpoint the results to disk.

- I write a simple template that can take an arbitrary class and
   write the pointer value and the class's data to disk.  (Actual data
   is just strings and integers, so one template should cover all of
   these classes.)

- For each internal container it can run over the members and do
   the same to every object with a distinct memory address.  (one
   more template is needed for each container concept, like AA,
   list or array -- say 4 or 5 more templates.  It only writes each
   object once by tracking pointers in a set.

- Another template that can read this stuff back in, and fix the
   pointers so that they link up correctly.

(** All of this is much easier than normal, because I can generate
types using typelists as a starting point.  I think in C++ this is
a bit trickly because it convolutes the structure definition --
recursively nested structs and all that; but with code generation, the
"struct builder" can take a list of strings and pump out a struct whose
definition looks exactly like a hand coded struct would look, but
maybe with more utilitarian functionality since its cheaper to add
the automated stuff. **)

Three or four templates later, I have a system for checkpointing any
data structure (with a few exceptions like sockets etc.), to a
string or stream.


2. I want to display this stuff to the user.

I bang together another couple of templates that can show these kinds
of code objects in a simple viewer.  It works just like the last one,
finding variable names and values and doing the writefln() types of
tricks to give the user the details.  Some kind of browser lets me
examine the process starting at the top.  Maybe it looks a little like
a flow chart and a little like a debugger's print of a structure.

- I can define hooks in the important kinds of objects so they can
override their own displays but simple data can work without much
help.


3. I want to build a distributed compute farm for this numerical task.

- I just need to change the serialization to stream the data objects
over the web or sockets, or queue the objects in SQL tables.  Some load
balancing, etc.  Another application that has the same class definitions
can pull in the XML or ASN.1 or home-made serialization format.

The trick here is that we need to be able to build templates that can
inspect the objects and trees of objects in complex ways -- does this
class contain a field named "password";  is this other field a computed
value that can be thrown away.  Does this other class override a method 
named 'optimizeForTransport'.

Adding arbitrary attributes and arbitrary bits of code and annotation to 
the classes is not too hard to do, because my original code generation 
functions used typelists and had hooks for specifying special behavior.


4. I decide to allow my ten closest friends to help with the application 
by rewriting important subroutines.

- Each person adds code for the application to an SQL database.  A 
simple script can now pull code from the database and dump it to text 
files.  This code can be imported into classes and run.

- I can generate ten different versions of a critical loop and select 
which one to run at random.  The timing output results is stored in a 
text file.  Later compiles of the code do "arc-profiling" of entire 
algorithms or modules.

Kevin