www.digitalmars.com         C & C++   DMDScript  

D - Compile-time meta-programming

reply Bill Cox <bill viasic.com> writes:
Hi.

I've been suggesting we add "support for code generation" to D.  I don't 
think I've described what I meant by this very well.

What I really mean is meta-programming, limited to what can be evaluated 
at compile time.

Langauges like Java have a run-time meta-programming capability, where 
you can dynamically create classes and methods, and then execute them. I 
don't want this ability, as it's inefficient and adds complexity to the 
run-time environment.  It's addition to Java has hindered development of 
good native compilers.

However, if you limit what you can do with meta-programs to what can 
easily be statically compiled, you get something of tremendous value.

For example, here's some things that could go into a standard library if 
staticly compiled meta programs were supported:

- Dramatically improved STL
- Module-level binary load save
- Automaticly generated recursive destructors, or in GC based languages, 
object unhookers?

Templates can't add members to multiple existing classes.  That's what 
you want to implement a linked list.  The majority of all collection 
classes would be implemented better if both classes involved could be 
modified.  The STL would be much better off being implemented as 
compile-time meta programs.

Things like binary load/save are much better when implemented at a 
database level, rather than at an object level.  For example, we can 
write a meta-program that adds an index to each object, and then saves 
these values to disk rather than the pointers to them, and then free the 
memory.  This is really easy in meta programming.

With good compile-time meta-programming support, we could eliminate 
templates from the language, and reduce the overall complexity of the 
language.

Here's how compile-time meta-programming can work:

You still need ways to declare that you want instances of things to be 
created, much like we do with templates.  You could declare, for 
example, an instance of binaryLoadSave<myModule>.  This would cause the 
meta-program (written in D) to be called on the module.  That program 
would travers Java-like mirror classes, and create a function that 
saves/loads the data in the module to disk.

Since the class data being traversed is all known at compile time, there 
is no reason that the meta-program can't be compiled separately, and 
then simply linked into the compiler (as a DLL?).  Thus, the performace 
of the meta-program would be very fast, and there would be exactly 0 
portion of it actually put into the user's exe.  This would work 
especially well for standard libraries, where most of the meta-programs 
would probably live.

Bill
Mar 07 2003
next sibling parent reply Toyotomi <io219 attbi.com> writes:
On Fri, 07 Mar 2003 07:43:31 -0500, Bill Cox <bill viasic.com> wrote:


However, if you limit what you can do with meta-programs to what can 
easily be statically compiled, you get something of tremendous value.

For example, here's some things that could go into a standard library if 
staticly compiled meta programs were supported:

- Dramatically improved STL
- Module-level binary load save
- Automaticly generated recursive destructors, or in GC based languages, 
object unhookers?


I've never been even 1/10th as excited about STL and templates as others.
I really don't understand what is so great about them to be honest. I've
always felt you could design an OO framework to do the same thing in a
more understandable way. But again, I just don't get why they are great.

Anyway, is there any merit to this method of generic programming :

http://www.codemoon.com/cm/artlist.php?index=main

It seems much more understandable.

As far as meta programming, I love it, but only in non-compiled languages.
Mar 07 2003
parent reply Bill Cox <bill viasic.com> writes:
Hi, Toyotomi.

Toyotomi wrote:

 On Fri, 07 Mar 2003 07:43:31 -0500, Bill Cox <bill viasic.com> wrote:
 
 

However, if you limit what you can do with meta-programs to what can 
easily be statically compiled, you get something of tremendous value.

For example, here's some things that could go into a standard library if 
staticly compiled meta programs were supported:

- Dramatically improved STL
- Module-level binary load save
- Automaticly generated recursive destructors, or in GC based languages, 
object unhookers?


 
 
 I've never been even 1/10th as excited about STL and templates as others.
 I really don't understand what is so great about them to be honest. I've
 always felt you could design an OO framework to do the same thing in a
 more understandable way. But again, I just don't get why they are great.
 
 Anyway, is there any merit to this method of generic programming :
 
 http://www.codemoon.com/cm/artlist.php?index=main
 
 It seems much more understandable.
 
 As far as meta programming, I love it, but only in non-compiled languages.


This link shows D's templates, and has some comments on C++'s STL.  Do 
you mean that D's templates are more understandable?

Bill
Mar 07 2003
parent reply Toyotomi <io219 attbi.com> writes:
On Fri, 07 Mar 2003 11:44:27 -0500, Bill Cox <bill viasic.com> wrote:


 Anyway, is there any merit to this method of generic programming :
 
 http://www.codemoon.com/cm/artlist.php?index=main
 
 It seems much more understandable.
 
 As far as meta programming, I love it, but only in non-compiled languages.


This link shows D's templates, and has some comments on C++'s STL.  Do 
you mean that D's templates are more understandable?


I guess so... but that seems fairly normal to me. Do you mean to tell me
that C++'s STL does this same sort of thing? I seem to have been doing
this forever as a usual part of my OO programming, in Java, Delphi AND C.

Is there some glaring problem in C++ which allows such a void to be filled
and thus adored so much, where in other places it is taken for granted?
Mar 07 2003
parent reply Bill Cox <bill viasic.com> writes:
Toyotomi wrote:

 On Fri, 07 Mar 2003 11:44:27 -0500, Bill Cox <bill viasic.com> wrote:
 
 

Anyway, is there any merit to this method of generic programming :

http://www.codemoon.com/cm/artlist.php?index=main

It seems much more understandable.

As far as meta programming, I love it, but only in non-compiled languages.


This link shows D's templates, and has some comments on C++'s STL.  Do 
you mean that D's templates are more understandable?


 
 
 I guess so... but that seems fairly normal to me. Do you mean to tell me
 that C++'s STL does this same sort of thing? I seem to have been doing
 this forever as a usual part of my OO programming, in Java, Delphi AND C.


Well, STL stands for Standard Template Library.  I'm pretty sure it's 
just a bunch of templates.


 Is there some glaring problem in C++ which allows such a void to be filled
 and thus adored so much, where in other places it is taken for granted?


Hm... In languages like Lisp, you basically don't need templates, but in 
statically compiled languages, parameterised code is kind of a big deal. 
  Last I heard, Java still didn't have it, and it is something of a 
glaring hole.

As for meta-programming, it's obviously natural for dynamic languages. 
I think it's one of the primary reasons that Lisp was chosen for AI 
research.

As for running meta-programs during compilation vs run-time, I'd argue 
that during compilation is the far more important of the two.  Running 
meta-programs during execution is much like self-modifying code. 
Basically, you need a really good reason to go there, and those reasons 
are few and far between.  The vast majority of useful meta-programs that 
I can think of can be run during compilation, since their only input is 
the program you wrote, not run-time data.

So, for example, if you want a linked list support in your language, you 
could write a meta-program that looks something like:

LinkedList(Class parentClass, Class childClass, string name) {
     genenerate(parent:parentClass.name, child:childClass.name, name:name) {
         extend class <parent> {
             <child> first<name><child>;
             add<name><child>(<child> child) {
                 child.next<parent><name><child> = first<name><child>;
                 first<name><child> = child;
             }
         }
         extend class <child> {
             <child> next<parent><name><child>;
         }
     }
}

User's could then cause the compiler to call the meta-program with an 
instantiation type of statement like:

class Node {
}

class Edge {
}

instance LinkedList<Node, Edge, "in">;
instance LinkedList<Node, Edge, "out">;

This is much more powerful than templates.  This example barely 
scratches the surface of what can be done.

Bill
Mar 07 2003
parent reply Toyotomi <io219 attbi.com> writes:
On Fri, 07 Mar 2003 13:39:59 -0500, Bill Cox <bill viasic.com> wrote:


 Is there some glaring problem in C++ which allows such a void to be filled
 and thus adored so much, where in other places it is taken for granted?


Hm... In languages like Lisp, you basically don't need templates, but in 
statically compiled languages, parameterised code is kind of a big deal. 
  Last I heard, Java still didn't have it, and it is something of a 
glaring hole.


I still don't get it. You can pass function pointers, you can design with
interfaces, or you can use variants, all depending what language you're in
of course... Templates seem to allow the same, except they require new
syntax and terminology, both of which are very confusing in C++ for me.

eg. How are templates different than an OO implementation with interfaces?


User's could then cause the compiler to call the meta-program with an 
instantiation type of statement like:

class Node {
}

class Edge {
}

instance LinkedList<Node, Edge, "in">;
instance LinkedList<Node, Edge, "out">;

This is much more powerful than templates.  This example barely 
scratches the surface of what can be done.


So the user is writing code? I use embedded languages for that.
If they are not, then can't the system be designed to handle their
changes with a good OO model, with interfaces for generic-ness?

Generating code at runtime for a statically compiled language seems wrong.

*shrug*
Mar 07 2003
next sibling parent Bill Cox <Bill_member pathlink.com> writes:
In article <7lrh6vseucrlqq3be9slslsn964dgbg61i 4ax.com>, Toyotomi 
says...

On Fri, 07 Mar 2003 13:39:59 -0500, Bill Cox <bill viasic.com> wrote:


 Is there some glaring problem in C++ which allows such a void to be 






filled

 and thus adored so much, where in other places it is taken for 






granted?

Hm... In languages like Lisp, you basically don't need templates, but in 
statically compiled languages, parameterised code is kind of a big 




deal. 

  Last I heard, Java still didn't have it, and it is something of a 
glaring hole.


I still don't get it. You can pass function pointers, you can design with
interfaces, or you can use variants, all depending what language you're 


in

of course... Templates seem to allow the same, except they require new
syntax and terminology, both of which are very confusing in C++ for me.

eg. How are templates different than an OO implementation with 


interfaces?

User's could then cause the compiler to call the meta-program with an 
instantiation type of statement like:

class Node {
}

class Edge {
}

instance LinkedList<Node, Edge, "in">;
instance LinkedList<Node, Edge, "out">;

This is much more powerful than templates.  This example barely 
scratches the surface of what can be done.


So the user is writing code? I use embedded languages for that.
If they are not, then can't the system be designed to handle their
changes with a good OO model, with interfaces for generic-ness?

Generating code at runtime for a statically compiled language seems 


wrong.

*shrug*


Er... generating code at run-time would be bad.  How about at compile 
time?
3.023
Mar 07 2003
prev sibling parent Antti Sykari <jsykari gamma.hut.fi> writes:
Toyotomi <io219 attbi.com> writes:

 I still don't get it. You can pass function pointers, you can design with
 interfaces, or you can use variants, all depending what language you're in
 of course... Templates seem to allow the same, except they require new
 syntax and terminology, both of which are very confusing in C++ for me.

 eg. How are templates different than an OO implementation with interfaces?


Templates are for compile-time polymorphism, and object-orientation
and interfaces/abstract classes are for run-time polymorphism.

You can parameterize any type with templates, including built-in
types, which you cannot use with abstract classes without boxing.
With templates you get generally less overhead.  Templates are more
costly to compile, though, since you usually need more access to the
source code.  Typically templates are included as header files, while
you can compile classes separately.

In general, templates do the same thing at compile time as abstract
classes do at run time.  This means that you have complete access to
the type you're using.  You know its size, meaning that you can store
it on the stack, embed it in objects, and copy it as you like.  If you
access an object only through its interface, you only know the
operations it supports and someone has to allocate it on the heap.

So, both have their uses.  However, lately the trend in the mainstream
imperative languages seems to have been towards the object-oriented


A short introduction to C++ templates can be found at:

http://www.codeguru.com/atl/KD062002.html

Generic programming in C++ is a form of object-oriented programming
where the "object-oriented part", the type selection, is done at
compile time.  "Interfaces" are replaced with the notion of
"concepts", which is an abstract concept not specifically supported by
the language.  (In this sense, you could it a programming discipline.) 
An introduction to generic programming (that might not be the most
approachable, though) can be found at

http://www.sgi.com/tech/stl/stl_introduction.html

As to why C++ is not just an object-programming language, please see
"Why C++ is not just an object-oriented programming language":

http://www.research.att.com/resources/articles/oopsla.pdf

I also heartily recommend the book "The C++ Programming Language"
which answers these questions and many more.

Oh, and if you have time to visit your local bookstore and take a look
at the chapter 6 of the book "Generative Programming" by Czarnecki and
Eisenecker, do that.  It provides a thorough comparison between
parametric (compile time/templates) and subtype (run time/interfaces)
polymorphism.

And check out the basics (or at least the introduction) from "C++
Templates - the Complete Guide" by Vandevoorde and Josuttis, while
you're at it.  Happy learning :)

-Antti
Mar 08 2003
prev sibling next sibling parent Ilya Minkov <midiclub 8ung.at> writes:
Dunno where to put *it*. I just stumbled over *it*.

---8<---
OpenC++ is a version of C++ with a Metaobject Protocol. In other words, 
it is a tool of source-code translation for C++. Programmers can easily 
implement various kinds of translation so that they can define new 
syntax, new annotation, and new object behavior. OpenC++ is useful if 
they need, for example,

  - Developing extensions to C++, to provide support for things like 
parallelism, distribution, concurrency, and persistence.
  - Adding domain-, application-, or class-specific compiler optimizations.
  - Building their own version of (runtime) MOP for C++.

--->8---

http://www.csg.is.titech.ac.jp/~chiba/openc++.html

I haven't taken a closer look at it, but i can see following use of it:
  - it could make a D backend.
  - it could teach us how to make compile-time reflection and an 
extensible language. There is a list of related publications on this site.
  - maybe we can even adapt their protocol with little change?

-i.


Bill Cox wrote:

 Hi.
 
 I've been suggesting we add "support for code generation" to D.  I don't 
 think I've described what I meant by this very well.
 
 What I really mean is meta-programming, limited to what can be evaluated 
 at compile time.
 
 Langauges like Java have a run-time meta-programming capability, where 
 you can dynamically create classes and methods, and then execute them. I 
 don't want this ability, as it's inefficient and adds complexity to the 
 run-time environment.  It's addition to Java has hindered development of 
 good native compilers.
 
 However, if you limit what you can do with meta-programs to what can 
 easily be statically compiled, you get something of tremendous value.
 
 For example, here's some things that could go into a standard library if 
 staticly compiled meta programs were supported:
 
 - Dramatically improved STL
 - Module-level binary load save
 - Automaticly generated recursive destructors, or in GC based languages, 
 object unhookers?
 
 Templates can't add members to multiple existing classes.  That's what 
 you want to implement a linked list.  The majority of all collection 
 classes would be implemented better if both classes involved could be 
 modified.  The STL would be much better off being implemented as 
 compile-time meta programs.
 
 Things like binary load/save are much better when implemented at a 
 database level, rather than at an object level.  For example, we can 
 write a meta-program that adds an index to each object, and then saves 
 these values to disk rather than the pointers to them, and then free the 
 memory.  This is really easy in meta programming.
 
 With good compile-time meta-programming support, we could eliminate 
 templates from the language, and reduce the overall complexity of the 
 language.
 
 Here's how compile-time meta-programming can work:
 
 You still need ways to declare that you want instances of things to be 
 created, much like we do with templates.  You could declare, for 
 example, an instance of binaryLoadSave<myModule>.  This would cause the 
 meta-program (written in D) to be called on the module.  That program 
 would travers Java-like mirror classes, and create a function that 
 saves/loads the data in the module to disk.
 
 Since the class data being traversed is all known at compile time, there 
 is no reason that the meta-program can't be compiled separately, and 
 then simply linked into the compiler (as a DLL?).  Thus, the performace 
 of the meta-program would be very fast, and there would be exactly 0 
 portion of it actually put into the user's exe.  This would work 
 especially well for standard libraries, where most of the meta-programs 
 would probably live.
 
 Bill
Mar 07 2003
prev sibling parent reply Mark Evans <Mark_member pathlink.com> writes:
Bill-

My interest in your thoughts is frustrated because I can't follow them.
Hazarding a guess:  they confound multiple issues and eschew standard terms.
The concerns also orbit around a single problem domain: graph classes.
Consequently, I respectfully suggest (a) using industry-standard terms, and (b)
posting your C++ graph classes to the DM FTP area for us.

I doubt that anything discussed merits novel computer science concepts.  For one
thing, many good C++ graph libraries exist:

http://www.boost.org/libs/graph/doc/index.html
http://infosun.fmi.uni-passau.de/GTL/
http://www.math.uni-augsburg.de/opt/goblin.html
http://ls5-www.cs.uni-dortmund.de/projects/METAFrame/plgraph/

More elegant possibilities exist too; I can easily picture a language
tailor-made for graph problems.  My goal is merely to cite that graphs can be
done with stock C++ template programming.

I would also invite you back to my post about Strategic Programming, which
delves into novel data structure traversals:
http://www.digitalmars.com/drn-bin/wwwnews?D/11125

Your phrase 'meta-programming, limited to what can be evaluated at compile time'
(i.e. compile-time meta-programming) means, exactly, 'templates' and 'generic
programming' to every C++ expert that I know.  Using this phrase to connote
something else sows confusion.

The phrase 'run-time meta-programming capability, where you can dynamically
create classes and methods' also puzzles me.  Do you mean 'runtime
introspection' (as in Python)?  Do you mean 'object-based' as described in
http://research.microsoft.com/Users/luca/Slides/PLDI96Tutorial.pdf ?

Perhaps what you are driving at is compile-time 'type inference'?  This is
exactly what the Functional C++ library does.

When you say 'Templates can't add members to multiple existing classes' do you
mean 'aspect-oriented programming' or 'multimethods' or 'generic methods'?
These are all standard terms.  Have a look at Neel's slides on Needle, and the
section headed, "What are generic functions and multimethods?"  These may be
what you want, and I suspect they are exactly what you want, though you don't
know it yet.  I made a post about multimethods some weeks ago!  Neel comments
that "In traditional OO, adding new methods to a class is unmodular even if it's
possible."
http://www.nongnu.org/needle/needle-ll2-talk.pdf
See also the paper at
http://archives.cs.iastate.edu/documents/disk0/00/00/02/08/

The idea of a 'meta-program' that is 'compiled separately' seems weird; does any
known language enable such a thing?

What I'm seeking are points of common reference by which to evaluate your ideas.
When we invent our own terms, there is no such context.

I am *not* asking for verbose descriptions of the mechanics.  We already have
viable terms that I'm sure cover the concept(s).  Tell us what is the closest
thing to your idea(s) using standard terminology.  All of these issues have been
explored before, you just have to connect with that work so we can follow you.

Thanks,
Mark
Mar 07 2003
next sibling parent reply Bill Cox <Bill_member pathlink.com> writes:
My interest in your thoughts is frustrated because I can't follow them.
Hazarding a guess:  they confound multiple issues and eschew standard terms.
The concerns also orbit around a single problem domain: graph classes.
Consequently, I respectfully suggest (a) using industry-standard terms, and (b)
posting your C++ graph classes to the DM FTP area for us.


Well... I can certainly clear up some things quickly.  This post had noting to
do with graphs.  That discussion was about virtual classes.

I don't have any reusable graph code to post.  I've never seen any that were
efficient enough for use in EDA.

I'm using the term "meta-programming" because this feature allows us to write
programs that write programs.  I'm calling it "compile-time meta-programming"
because these meta-programs run during compiliation of a program, rather than
when it runs.

The closest thing to what I'm calling "compile-time meta-programming" that I
know of is code generators, like those in DataDraw.


I doubt that anything discussed merits novel computer science concepts. For one
thing, many good C++ graph libraries exist:

http://www.boost.org/libs/graph/doc/index.html
http://infosun.fmi.uni-passau.de/GTL/
http://www.math.uni-augsburg.de/opt/goblin.html
http://ls5-www.cs.uni-dortmund.de/projects/METAFrame/plgraph/


None of these allows me to reuse efficient graph code.  Should we re-open the
discussion on virtual classes?


More elegant possibilities exist too; I can easily picture a language
tailor-made for graph problems.


Sounds ugly to me.


My goal is merely to cite that graphs can be
done with stock C++ template programming.


How?  Show me.  There's 30 bucks worth of pizza in it for you if you can.  The
links you list don't do the job.


I would also invite you back to my post about Strategic Programming, which
delves into novel data structure traversals:
http://www.digitalmars.com/drn-bin/wwwnews?D/11125


I sometimes go back to that link when I need a good laugh.


Your phrase 'meta-programming, limited to what can be evaluated at compile time'
(i.e. compile-time meta-programming) means, exactly, 'templates' and 'generic
programming' to every C++ expert that I know.  Using this phrase to connote
something else sows confusion.


A meta-program can generate any code.  It's only limited by it's input, which is
the user's program.  Try writing a template that writes out your classes and
their members and methods in formatted HTML with hyper-links and all.  It's easy
in a meta-program.  How about a template that performs a full database check for
dangling pointers, or automatic binary or text based load/save?  DataDraw does
this today.


The phrase 'run-time meta-programming capability, where you can dynamically
create classes and methods' also puzzles me.  Do you mean 'runtime
introspection' (as in Python)?  Do you mean 'object-based' as described in
http://research.microsoft.com/Users/luca/Slides/PLDI96Tutorial.pdf ?


I mean what you can do with Java's mirror classes at run-time.


Perhaps what you are driving at is compile-time 'type inference'?  This is
exactly what the Functional C++ library does.


I don't see what functional programming has to do with this.


When you say 'Templates can't add members to multiple existing classes' do you
mean 'aspect-oriented programming' or 'multimethods' or 'generic methods'?


Definately not any of those.  I mean that templates don't modify existing
classes at all.  Meta programs can.


These are all standard terms.  Have a look at Neel's slides on Needle, and the
section headed, "What are generic functions and multimethods?"


Ok, I checked them.  It's exactly what we've talked about before in this group,
and definitly not meta-programs.


These may be
what you want, and I suspect they are exactly what you want, though you don't
know it yet.


I read all about them, understand them, and their still not meta-programing.


I made a post about multimethods some weeks ago!  Neel comments
that "In traditional OO, adding new methods to a class is unmodular even if it's
possible."
http://www.nongnu.org/needle/needle-ll2-talk.pdf
See also the paper at
http://archives.cs.iastate.edu/documents/disk0/00/00/02/08/


I agree that programs writing programs is not generally good style.  They're
harder to read and debug than templates.  I see them primarily being used in
standard libraries.


The idea of a 'meta-program' that is 'compiled separately' seems weird; does any
known language enable such a thing?


It's weird, and no, I know of no programming language that supports it.
However, we do a ton of it at work, in the form of DataDraw code generators.
It'd be nice to have the same power built into the language.  The benifits we
get from the hacked up generators are huge.


What I'm seeking are points of common reference by which to evaluate your ideas.
When we invent our own terms, there is no such context.


I don't know of any common term that applies.  If there is one, I'd like to know
what it is.


I am *not* asking for verbose descriptions of the mechanics.  We already have
viable terms that I'm sure cover the concept(s).  Tell us what is the closest
thing to your idea(s) using standard terminology.  All of these issues have been
explored before, you just have to connect with that work so we can follow you.


Don't confuse this concept with other concepts I've posted before, other than
"support for code generation" which actually is the same issue.  If it helps, I
can clarify and distinguish some of the issues I've been talking about:

- Compile-time meta-programming (code generator support)
- Dynamic class extension (dynamic inheritance might be a better term)
- Virtual classes, template frameworks, and Sather's "include".
- Advance iterators

Each of these features fill a specific need in our code base at work.  We write
complex EDA applications such as placers and routers.

Just to make sure I'm understood, let me repeat what I see the core ideas and
benifits of these features to be:

Compile-time meta-programs
--------------------------
These are simple programs that generate code for your application.  We currently
use DataDraw, which generates a ton of useful code for us, which I've elaborated
on in earlier posts.  It would be cool if a language could support this kind of
programming natively.  Even Scheme can't do this, since meta-classes describing
data structures aren't available (it's a dynamically typed language).  Java
can't do this, since it's meta-classes (they call them mirror classes) are only
available at run-time.

Dynamic class extensions
------------------------
In C++, Java, and D, how do you attach new data to existing objects in memory?
It's generally done with some hack involving void pointers.  Our DataDraw code
generators do better, providing a mechanism to dynamically add data to objects
in our database cleanly.  This isn't a big deal for most applications, even for
compilers.  However, modern EDA tool suites (for designing chips) have common
object databases.  Every tool reads and writes to it.  The objects are there
when your tool starts, and you have to extend them.

Virtual classes
---------------
We've discussed these at length.  This improves code reuse for mutually
recursive classes, like simple graphs.  We have at least 100 massivly recursive
classes in our EDA database.  I'd simply like to reuse more code.  I prefer
Sather's "include" construct, which provides a superset of this capability,
since it gets around some of the difficult issues discussed concerning virtual
classes.

Advanced iterators
------------------
Walter has this listed as a future enhacement he wants to look into.  We
generate simple iterators with DataDraw, and so I've tried to help in this area.
The Sather iterators are very powerful, but look like they involve
multi-threading.  I suggested a weaker form of iterator construct that can be
done without threads.  We write a lot of data structure traversal routines that
take call-back functions (like depth-first traversals).  Beside the inefficiency
of calling a function via a function pointer, we have to communicate with the
call-back functions through global variables.  The iterator construct I proposed
would eliminate 100% of these functions from our code base, and the code would
run faster.

These aren't pie-in-the sky ideas, or counter to D's efficiency goals.  I'm not
claiming that they are new ideas.  They'd just help us out a lot at work.

Bill
Mar 07 2003
parent Mark Evans <Mark_member pathlink.com> writes:
My goal is merely to cite that graphs can be
done with stock C++ template programming.


How?  Show me.



Read the docs and keep the pizza.  The subject is moot if graphs are not the
topic.




http://www.digitalmars.com/drn-bin/wwwnews?D/11125


I sometimes go back to that [strategic programming] 
link when I need a good laugh.


Uh huh.  You should be getting more than a laugh out of them because......


A meta-program can generate any code.  It's only limited
by it's input, which is the user's program.


...you have described program transformation, which is, in their own words....

..."The prime application domain for strategic programming."

http://www.program-transformation.org/twiki/bin/view/Transform/GenerativeProgramming
"The goal of generative programming is to replace manual search, adaptation, and
assembly of components with the automatic generation of needed components on
demand."



 I don't know of any common term that applies.
 If there is one, I'd like to know what it is.


Try 'automatic code generation' or 'generative programming.' The term
'meta-programming' connotes templates qua templates.



Try writing a template that writes out your classes and
their members and methods in formatted HTML with hyper-links and all.
It's easy in a meta-program.  How about a template that performs a full
>database check for dangling pointers, or automatic binary or text based
load/save?  DataDraw does this today.


From those hilarious clowns at the strategic programming circus,

http://www.program-transformation.org/twiki/bin/view/Transform/ProgramTransformation
"Program transformation is used in many areas of software engineering, including
compiler construction, software visualization, documentation generation, and
automatic software renovation."



'type inference' ... is exactly what the Functional C++ library does.


I don't see what functional programming has to do with this.


Type inference was the point, not functional programming.  You were yakking
about extending types, as far as I could tell.



When you say
'Templates can't add members to multiple existing classes'
do you mean 'aspect-oriented programming' or 'multimethods'
or 'generic methods'?


Definately not any of those.  I mean that templates don't
modify existing classes at all.  Meta programs can.


I'm not 'definitely' sure of anything you're saying.  Your whole problem may be
ill-posed in which case you could have us all chasing our tails.  If you really
need to 'add members to multiple existing classes' then first-class multimethods
are your only hope this side of a dynamically typed and introspective language
or automatic code generation.  I think you should start asking hard questions
about whether class-based encapsultaion is the proper way to structure your
code, since it is getting in your way.

Mark
Mar 08 2003
prev sibling parent reply Antti Sykari <jsykari gamma.hut.fi> writes:
Mark Evans <Mark_member pathlink.com> writes:


 Bill-

 My interest in your thoughts is frustrated because I can't follow
 them.  Hazarding a guess: they confound multiple issues and eschew
 standard terms.


If you'll permit me to present my view of what Bill is wishing for --
I remember that I had a vision of something similar earlier...  I'll
forget about the standard terminology and present the hypothetical
compile-time metaprogramming with a concrete example.

First, by adding a member to multiple classes I believe he means
member variables, not functions.  Hence it's something that resembles
more aspect-oriented programming than multimethods.  But compile-time
metaprogramming could do more by transforming and modifying the syntax
tree in almost any way.

Suppose we have a simple class with member "int x" and getter/setter
member functions.

class X
{
    int get_x() { return x; }
    void set_x(int new_x) { x = new_x; }

private:
    int x;
}

Now we want to make a synchronized version of it.  This one requires a
mutex (reentrant, actually, but that's not the point) in the object
and lock() and release() calls before and after, respectively, the
member functions are called

class Synchronized_X
{
    int get_x() {
        mutex.lock();
        int result = x;
        mutex.release();
        return result;
    }

    void set_x(int new_x) {
        mutex.lock();
        x = new_x;
        mutex_release();
    }

private:
    Mutex mutex;
    int x;
}

A-ha, there's a "cross-cutting aspect", namely, synchronization!
Synchronization is nice, but sometimes we don't want it.  In this
particular case, I want to be able to toggle the synchronization of X
- or actually, all objects - with one change.  Looks like a case for
aspect-oriented programming.  But I never really got that AOP thing,
it seems so complex and I haven't seen a really good hands-on example.
I'd really just prefer to do something like this:

// A metafunction that takes a type as an argument and returns a type
// which behaves as original type but is synchronized.  I use 
// <> to represent the fact that the function is called at
// compile-time, not at run-time -- it has no particular resemblance
// to C++ templates.  At least yet.  "Type type" is treated as if
// passed by value.

Type Synchronized<Type type>
{
    type.insert_private_member("Mutex mutex;");

    for_each (member_function in type.member_functions)
    {
        member_function.insert_statement_at_beginning("mutex.lock();");
        member_function.insert_statement_at_end("mutex.release();");
    }

    return type;
}

(Obviously, this version isn't perfect.  Synchronized<> would need to
traverse all statements in each member function and look for return
statements, and then prepend each return statement with an
introduction of a temporary variable, which would be initialized with
the expression in the return statement.  Also it would have to survive
name clashes if the function also had a "mutex", etc.)

Now that we have Synchronized<>, we can get a synchronized database
connection with:

Synchronized<Database_Connection> db;

Alternatively, we can parameterize all our classes that need to be
synchronized in a manner like this:

global.d:

Type Identity<Type type> { return type; }

version (multi_threaded)
{
    alias Synchronized Synch;
}
else
{
    alias Identity Synch;
}

And then use Synch<Classname> anywhere where multithreading might
potentially cause harm.

(Of course, there's "synchronized" already but let's forget that for
the sake of the example.)

The problem is that the interface to "Type" and possibly other
compile-time things (functions, aliases, symbols, strings, constants,
you name it) probably needs a lot of experimentation before getting it
right.  The change to the language as it is now isn't exactly trivial
and I don't expect to see it in D, at least in the near future.
Actually, these kinds of features would almost need a language of
their own.

Metafunctions should be side-effectless, so that we could be sure that
Function<Type> always means the same thing.  Then the compiler also
wouldn't need to evaluate it more than once per compilation.

Another question is: should metafunctions be compiled?  I was first
thinking about interpreting them, but of course it would be more
efficient to compile them to native code and link them into the
compiler -- Bill has a point there.

In any case, this kind of metaprogramming would be cool, definitely,
and you'd get templates for free if you could define local types in
terms of argument types and return them.  Metaprogramming is a
generalization of templates.  Hard-core C++ guys do "metaprogramming
by templates" with great pain and suffering, but one could do
"templates by metaprogramming" with naturalness and ease:

Type List<Type type>
{
    // a local type definition, using "type";
    struct ListNode
    {
        ListNode<type>* next;
        type item;
    }

    struct List
    {
        ListNode<type>* head;
    }

    return List;
}

f()
{
    List<int> x;
}

And there you go.  Just add member functions.

One would still need a way to manipulate functions in a similar way,
to get generic functions, and automatic type inference would be a
problem.

-Antti
Mar 08 2003
parent Bill Cox <Bill_member pathlink.com> writes:
In article <87d6l1isae.fsf hoastest1-8c.hoasnet.inet.fi>, Antti Sykari says...

Mark Evans <Mark_member pathlink.com> writes:


 Bill-

 My interest in your thoughts is frustrated because I can't follow
 them.  Hazarding a guess: they confound multiple issues and eschew
 standard terms.


If you'll permit me to present my view of what Bill is wishing for --
I remember that I had a vision of something similar earlier...  I'll
forget about the standard terminology and present the hypothetical
compile-time metaprogramming with a concrete example.

First, by adding a member to multiple classes I believe he means
member variables, not functions.  Hence it's something that resembles
more aspect-oriented programming than multimethods.  But compile-time
metaprogramming could do more by transforming and modifying the syntax
tree in almost any way.

Suppose we have a simple class with member "int x" and getter/setter
member functions.

class X
{
    int get_x() { return x; }
    void set_x(int new_x) { x = new_x; }

private:
    int x;
}

Now we want to make a synchronized version of it.  This one requires a
mutex (reentrant, actually, but that's not the point) in the object
and lock() and release() calls before and after, respectively, the
member functions are called

class Synchronized_X
{
    int get_x() {
        mutex.lock();
        int result = x;
        mutex.release();
        return result;
    }

    void set_x(int new_x) {
        mutex.lock();
        x = new_x;
        mutex_release();
    }

private:
    Mutex mutex;
    int x;
}

A-ha, there's a "cross-cutting aspect", namely, synchronization!
Synchronization is nice, but sometimes we don't want it.  In this
particular case, I want to be able to toggle the synchronization of X
- or actually, all objects - with one change.  Looks like a case for
aspect-oriented programming.  But I never really got that AOP thing,
it seems so complex and I haven't seen a really good hands-on example.
I'd really just prefer to do something like this:

// A metafunction that takes a type as an argument and returns a type
// which behaves as original type but is synchronized.  I use 
// <> to represent the fact that the function is called at
// compile-time, not at run-time -- it has no particular resemblance
// to C++ templates.  At least yet.  "Type type" is treated as if
// passed by value.

Type Synchronized<Type type>
{
    type.insert_private_member("Mutex mutex;");

    for_each (member_function in type.member_functions)
    {
        member_function.insert_statement_at_beginning("mutex.lock();");
        member_function.insert_statement_at_end("mutex.release();");
    }

    return type;
}

(Obviously, this version isn't perfect.  Synchronized<> would need to
traverse all statements in each member function and look for return
statements, and then prepend each return statement with an
introduction of a temporary variable, which would be initialized with
the expression in the return statement.  Also it would have to survive
name clashes if the function also had a "mutex", etc.)

Now that we have Synchronized<>, we can get a synchronized database
connection with:

Synchronized<Database_Connection> db;

Alternatively, we can parameterize all our classes that need to be
synchronized in a manner like this:

global.d:

Type Identity<Type type> { return type; }

version (multi_threaded)
{
    alias Synchronized Synch;
}
else
{
    alias Identity Synch;
}

And then use Synch<Classname> anywhere where multithreading might
potentially cause harm.

(Of course, there's "synchronized" already but let's forget that for
the sake of the example.)

The problem is that the interface to "Type" and possibly other
compile-time things (functions, aliases, symbols, strings, constants,
you name it) probably needs a lot of experimentation before getting it
right.  The change to the language as it is now isn't exactly trivial
and I don't expect to see it in D, at least in the near future.
Actually, these kinds of features would almost need a language of
their own.

Metafunctions should be side-effectless, so that we could be sure that
Function<Type> always means the same thing.  Then the compiler also
wouldn't need to evaluate it more than once per compilation.

Another question is: should metafunctions be compiled?  I was first
thinking about interpreting them, but of course it would be more
efficient to compile them to native code and link them into the
compiler -- Bill has a point there.

In any case, this kind of metaprogramming would be cool, definitely,
and you'd get templates for free if you could define local types in
terms of argument types and return them.  Metaprogramming is a
generalization of templates.  Hard-core C++ guys do "metaprogramming
by templates" with great pain and suffering, but one could do
"templates by metaprogramming" with naturalness and ease:

Type List<Type type>
{
    // a local type definition, using "type";
    struct ListNode
    {
        ListNode<type>* next;
        type item;
    }

    struct List
    {
        ListNode<type>* head;
    }

    return List;
}

f()
{
    List<int> x;
}

And there you go.  Just add member functions.

One would still need a way to manipulate functions in a similar way,
to get generic functions, and automatic type inference would be a
problem.

-Antti


I agree with all these points, including that it's not likely to make it into D.
I'm not sure where to go with this idea from here, other than implementing a
proto-type in my little test compiler.

Bill
Mar 08 2003