Polymorphism at run-time

[tommo97]

Dear all,

I am a relative novice to C++ and was wondering:

if I have a base class is it possible to recursively create new
derived classes from it "on the fly" at runtime? What I mean is that
each derived class will have it's own static members which can be
calculated from the base class using various functions, but that the
number and variation between the derived class and the base class may
(are) not known at compile time.

For example an octree:
Base class is a node;
1st derived class is a root node, the next is derived from this;
2nd - nth derived classes are nodes at the various levels of the tree
- these are derived from one-another;
(n+1)th derived class is the leaf and is derived from the previous
class.

Sorry if this makes no sense. If you have any idea even of the correct
posing of this question please let me know!

Thanks
tm

 

[amrollahi.saeed]

Dear all,

I am a relative novice to C++ and was wondering:

if I have a base class is it possible to recursively create new
derived classes from it "on the fly" at runtime? What I mean is that
each derived class will have it's own static members which can be
calculated from the base class using various functions, but that the
number and variation between the derived class and the base class may
(are) not known at compile time.

For example an octree:
Base class is a node;
1st derived class is a root node, the next is derived from this;
2nd - nth derived classes are nodes at the various levels of the tree
- these are derived from one-another;
(n+1)th derived class is the leaf and is derived from the previous
class.

Sorry if this makes no sense. If you have any idea even of the correct
posing of this question please let me know!

Thanks
tm

Hi

I think it is better you reconsider your design. For designing a
simple
tree (binary tree for example) we have no need to create new class for
each node at
different levels. As a matter of fact you need to create a new object
of the same class.
So you will have a class for whole tree and a class for each node.

Anyway, As a C++ related question, AFAIK, you can't create a class at
runtime, then derive it
from a base class, then create an object from it, ... I think it is
beyond C++ programming
languages facilities.

Regards,
-- Saeed Amrollahi

 

[tommo97]

Hi

I think it is better you reconsider your design. For designing a
simple
tree (binary tree for example) we have no need to create new class for
each node at
different levels. As a matter of fact you need to create a new object
of the same class.
So you will have a class for whole tree and a class for each node.

Anyway, As a C++ related question, AFAIK, you can't create a class at
runtime, then derive it
from a base class, then create an object from it, ... I think it is
beyond C++ programming
languages facilities.

Regards,
  -- Saeed Amrollahi

Hi Saeed,
Thanks for your response!

The reason I am interested in each level of the tree having thier own
derived class is that I would like each derived class to "own" a
static instance of a (large) set of data common to all nodes at that
level, but unique to that level (in fact, if this is/were possible I
would go one further and have data unique to another derived class
representing each octant on each level). The idea is that this data,
being large, takes a while to generate and I have no desire to
duplicate it.

Anyway thanks for your insight.

Regards
Tm

 

[Phlip]

The reason I am interested in each level of the tree having thier own
derived class is that I would like each derived class to "own" a
static instance of a (large) set of data common to all nodes at that
level, but unique to that level (in fact, if this is/were possible I
would go one further and have data unique to another derived class
representing each octant on each level). The idea is that this data,
being large, takes a while to generate and I have no desire to
duplicate it.

Firstly, El Goog returns 2 100 hits for [ogre3d octree], so see what they did.

Secord, when you say "polymorphism" and "derived class", there's no reason to
derive without changing behavior. Yet each octree node has exactly the same
behavior, just different data. Ordinary C++ data structures will handle this
situation easily...

 

[Pascal J. Bourguignon]

Dear all,

I am a relative novice to C++ and was wondering:

if I have a base class is it possible to recursively create new
derived classes from it "on the fly" at runtime? What I mean is that
each derived class will have it's own static members which can be
calculated from the base class using various functions, but that the
number and variation between the derived class and the base class may
(are) not known at compile time.

For example an octree:
Base class is a node;
1st derived class is a root node, the next is derived from this;
2nd - nth derived classes are nodes at the various levels of the tree
- these are derived from one-another;
(n+1)th derived class is the leaf and is derived from the previous
class.

Sorry if this makes no sense. If you have any idea even of the correct
posing of this question please let me know!

C++ doesn't allow you to do anything at run-time. If you really
needed to create classes at run-time, you would have to use a more
powerful programming language, such as Common Lisp.

However, you haven't mentionned an example that would need run-time
class creation. If you just have node objects with variable fields,
you can just store these fields in a dictionnary (eg. a stl::map),
that would be a member of the same Node class.

 

[tommo97]

C++ doesn't allow you to do anything at run-time.  If you really
needed to create classes at run-time, you would have to use a more
powerful programming language, such as Common Lisp.

However, you haven't mentionned an example that would need run-time
class creation.  If you just have node objects with variable fields,
you can just store these fields in a dictionnary (eg. a stl::map),
that would be a member of the same Node class.

Dear all,
Thanks for your input. I will address some of your points in order,
and maybe (hopefully) clarify what I'm trying to achieve.
Jeff (and Philip): I have already got a fully working octree
implementation, with root, branches and leaves. This was hand crafted
(well bodged) by me a few years ago, and is starting to creak a little
in current use (which is as a structure for fast-multipole n-body
problems). The idea of using templates is something I will have a go
at tonight.

Philip: The behaviour with each node (in this case) is strongly
dependant on the level within the tree - ie at different levels there
are different forces (literally) at work. Therefore, it has not been
possible to just pick an octree off the shelf plus in this case speed
is fairly essential so things I need the tree to do are not what
people would generally use octrees for when ray-tracing, for example.

Pascal: At compile time and indeed at run time the user (er.. me) is
not aware of the number of recursions required within the tree, and
therefore the number of combinations of different particle-particle
interaction that may occur. Since the distance cutoff, strenght and
effect of, say, electrostatic potential, gravity and van der Waals
forces are so different, the properties of the node, given it's
location in the tree, must reflect the forces that it's contents have
on it's neighbours. For some reason - probably my ignorance - I
thought there would be some way that instances of the class could be
related in the sense that they are all parts of the same tree, but
different in the sense that a call to a particular member function at
a level would run an appropriate function with the relevent set of
parameters.

All in all, I'm trying to make as much information as possible
implicit within the tree, generally to avoid mistakes on my part, and
specifically to avoid memory issues.

Thanks again for your comments

Tm

 

[Phlip]

Thanks for your input. I will address some of your points in order, and

maybe (hopefully) clarify what I'm trying to achieve. Jeff (and Philip): I
have already got a fully working octree implementation, with root,
branches and leaves. This was hand crafted (well bodged) by me a few years
ago, and is starting to creak a little in current use (which is as a
structure for fast-multipole n-body problems).

If it has no unit tests, add them now. Then refactor, one small edit at a
time, passing all the tests after each edit.

Keep refactoring until the code is DRY - that means it obeys "Don't Repeat
Yourself".

Seriously - when it's DRY, whatever design you get, it's good.

Philip: The behaviour with each node (in this case) is strongly dependant
on the level within the tree - ie at different levels there are different
forces (literally) at work.

This might require the Strategy Pattern, to make the behavior itself
pluggable. How's your /Design Patterns/ foo?

 

[gw7rib]

Dear all,
Thanks for your input. I will address some of your points in order,
and maybe (hopefully) clarify what I'm trying to achieve.
Jeff (and Philip): I have already got a fully working octree
implementation, with root, branches and leaves. This was hand crafted
(well bodged) by me a few years ago, and is starting to creak a little
in current use (which is as a structure for fast-multipole n-body
problems). The idea of using templates is something I will have a go
at tonight.

Philip: The behaviour with each node (in this case) is strongly
dependant on the level within the tree - ie at different levels there
are different forces (literally) at work. Therefore, it has not been
possible to just pick an octree off the shelf plus in this case speed
is fairly essential so things I need the tree to do are not what
people would generally use octrees for when ray-tracing, for example.

Pascal: At compile time and indeed at run time the user (er.. me) is
not aware of the number of recursions required within the tree, and
therefore the number of combinations of different particle-particle
interaction that may occur. Since the distance cutoff, strenght and
effect of, say, electrostatic potential, gravity and van der Waals
forces are so different, the properties of the node, given it's
location in the tree, must reflect the forces that it's contents have
on it's neighbours. For some reason - probably my ignorance - I
thought there would be some way that instances of the class could be
related in the sense that they are all parts of the same tree, but
different in the sense that a call to a particular member function at
a level would run an appropriate function with the relevent set of
parameters.

All in all, I'm trying to make as much information as possible
implicit within the tree, generally to avoid mistakes on my part, and
specifically to avoid memory issues.

As I see it, you don't actually want different code for your "derived"
objects, you just want them to point to different data. I think if you
sort out what the maximum number of different "chunks" of data an
object needs to get at, you should be able to come up with a scheme
whereby you store each bit of data once and each object can find the
ones it needs.

Hope that helps.
Paul.

 

[James Kanze]

C++ doesn't allow you to do anything at run-time.

That's not quite true. All of the C++ implementations I know
support dynamic linking, so you can take the C++ code, compile
it to a dynamic object, and then load it. Not necessarily the
easiest thing in the world, but if you're only targetting a
specific system, and you know where the C++ compiler is
installed, it can be done.

If you really needed to create classes at run-time, you would
have to use a more powerful programming language, such as
Common Lisp.

Or Scheme, or any number of other languages. What this
basically means is that they have a compiler for the language as
part of their runtime. Given the complexities of C++, that
would make for a very heavy runtime.

 

[Pascal J. Bourguignon]

That's not quite true. All of the C++ implementations I know
support dynamic linking, so you can take the C++ code, compile
it to a dynamic object, and then load it. Not necessarily the
easiest thing in the world, but if you're only targetting a
specific system, and you know where the C++ compiler is
installed, it can be done.

Yes, but the ease of implementation/use is a determining psychological
factor allowing or "preventing" the programmer to do it, in practice.
Theorically they're all Turing equivalent, but expressive power
matters in practice.

Or Scheme, or any number of other languages. What this
basically means is that they have a compiler for the language as
part of their runtime. Given the complexities of C++, that
would make for a very heavy runtime.

Which wouldn't matter for most applications given current "standard"
hardware, which also means that C++ is not indicated for most
applications it's used for, but that's another problem.

 

[Pascal J. Bourguignon]

Philip: The behaviour with each node (in this case) is strongly
dependant on the level within the tree - ie at different levels there
are different forces (literally) at work. Therefore, it has not been
possible to just pick an octree off the shelf plus in this case speed
is fairly essential so things I need the tree to do are not what
people would generally use octrees for when ray-tracing, for example.

Pascal: At compile time and indeed at run time the user (er.. me) is
not aware of the number of recursions required within the tree, and
therefore the number of combinations of different particle-particle
interaction that may occur. Since the distance cutoff, strenght and
effect of, say, electrostatic potential, gravity and van der Waals
forces are so different, the properties of the node, given it's
location in the tree, must reflect the forces that it's contents have
on it's neighbours. For some reason - probably my ignorance - I
thought there would be some way that instances of the class could be
related in the sense that they are all parts of the same tree, but
different in the sense that a call to a particular member function at
a level would run an appropriate function with the relevent set of
parameters.

All in all, I'm trying to make as much information as possible
implicit within the tree, generally to avoid mistakes on my part, and
specifically to avoid memory issues.

Ok, so each node may have various facets, and react to messages
according to the facets it has.

This is something that can be implemented trivially in CLOS (Common
Lisp Object System), with multiple inheritance and method
combinations. If there are a lot of class combinations to inherit
from, we may easily create the subclasses at run-time (and we can
change the class of an object on the fly too!).


It would be still easy to implement something like that in
Objective-C, which has only single inheritance, but which is able to
forward or process unknown (or known) messages easily, therefore where
it's easy to implement a delegate pattern. Some other OO programming
language can do the same, like Smalltalk.


In C++ it's still feasible, but it takes a lot more work. You can
define the Node class with the general, public API. Then you can
associate instances of subclasses of a Facet class to these Nodes, and
forward the message received by the node to the facets. The work here
is in painfully (or automatically) write all the forwarding methods.
If you're lucky, you can have a domain with a small number of methods
to forward.

So depending on the Node level, you would add such a such subclasses
of Facet to the Node instances.

+----------+ facets +------------------+
| Node |------------------------------| Facet {abstract} |
+----------+ -- interact -> * +------------------+
|----------| |------------------|
|interact()| | interact() |
+----------+ +------------------+
|
._______________________/_\___.
| |
+----------+ +----------+
| Electron | ... | Graviton |
+----------+ +----------+
|----------| |----------|
|interact()| |interact()|
+----------+ +----------+

It's a variant of the Strategy Design pattern with several strategies.
http://en.wikipedia.org/wiki/Strategy_pattern

Node::interact may combine the results of the various Facet::interact
(eg. vectorial sum of the resulting force).

 

[Steven G. Johnson]

No can do, unless you're willing to generate and compile a separate
program, on the fly, at run-time.  There are programs that do so with
spectacular success (e.g.FFTW), but it's probably not what you need.

(FFTW does not do runtime code generation; all of its code is
generated before compilation. At runtime, it only looks at different
combinations and calling sequences of the compiled code.)

 

[Steven G. Johnson]

Well, far be it for me to argue with the you on this topic, but what
genfft does, IIUC, is effectively run-time code generation of the sort
usually restricted to interpreted languages.  If you call the compiler
on the client machine, you're defying the traditional compile-then-run
ordering.  It's a nice technique, and I'd like to see it used more

Except that it doesn't call the code generator on the client machine.
FFTW doesn't call the code generator at all at runtime for the client
who is computing FFTs. That is the misunderstanding I was pointing
out.

genfft is essentially a special-purpose compiler for a domain-specific
language. But like an ordinary compiler, it is run at build time, or
even before (most users never run genfft at all, and rely on the
generated C code that we ship with FFTW). FFTW indeed has the
"traditional compile-then-run ordering."

(In fact, it's not even possible for FFTW to call the code generator
at runtime, since the code generator is written in OCaml, and FFTW
does not require an OCaml system in order to be compiled or run by end
users.)

Regards,
Steven G. Johnson

 

[James Kanze]

Which wouldn't matter for most applications given current
"standard" hardware,

Are you kidding?

which also means that C++ is not indicated for most
applications it's used for, but that's another problem.

It means that C++ isn't indicated for applications which must
generate code dynamically. For most applications today, the
ability to generate code dynamically would be a weakness, rather
than a feature. And additional source of potential errors,
which you can't really test, and a security hole that you have
to block. It's a vital feature for prototyping and experimental
programming, but something you want to avoid in production code,
which has to be reliable.

 

[Steven G. Johnson]

Well, thanks for setting me straight.  I was under the impression that FFTW required the presence of a C compiler at run-time; was I mistaken?

You were mistaken.

FFTW changes algorithms at runtime, but only by rearranging previously
compiled components and by changing runtime parameters. The trick is
to arrange the code into a series of functions that can be composed in
many ways to express a wide variety of algorithms without recompiling.
FFTW's strategies are described in detail at http://www.fftw.org/fftw-paper-ieee.pdf
and http://cnx.org/content/m16336

 

[Daniel Pitts]

Hi Saeed,
Thanks for your response!

The reason I am interested in each level of the tree having thier own
derived class is that I would like each derived class to "own" a
static instance of a (large) set of data common to all nodes at that
level, but unique to that level (in fact, if this is/were possible I
would go one further and have data unique to another derived class
representing each octant on each level). The idea is that this data,
being large, takes a while to generate and I have no desire to
duplicate it.

Anyway thanks for your insight.

Regards
Tm

When you say the "data" is common to and unique for all nodes at a
level, do you mean the values, or actual structure?

If the structure of the data is the same for all levels, then you only
need one class, but many instances.