C# Dynamic Trees for Genetic Programming

Question

I have some public user defined classes with relations between their members and also several methods with specific and generic signatures.

I would like to be able to store and manipulate custom control flow over these classes (plus CLR classes) using basic control statements like if/then/else, foreach, do/while, variable assignments etc.

The custom control flow should be created at runtime and then stored for later use and manipulation. The idea is to have a data representation of the control flow, possibly in the form of a abstract syntax tree, with strongly typed syntax in order to be able to apply genetic operations. The resulting custom code has to be executed as part of another program.

1) What is the preferred code representation for manipulating genetic operations and then execute the code including my classes,

2) Which c# technologies should I use for the above problem? I know there are related technologies like reflection, the new c# 3.0 features (lambda, expression trees), CodeDom, DLR library, etc but which approach or combination is the most efficient.

3) Are there such paradigms or implementations available?

EDIT: The platform is supplied with data of defined c# custom types, both constant and time variable.

Every moment rules are applied to the data (basic conditions or more complicated functions) and it is decided to take some actions.

I would like to be able to:

Represent the rules on a tree or a graph and execute tha flow.

Create custom rule sets by the user via a UI toolkit

Make rearrangement on the tree or graph and apply GP operations

Answer 1

Breeding programs represented in languages such as C# is very tricky - they simply aren't designed to be malleable - you will find that the vast majority of changes you make simply cause the program to fail.

I would recommend one of two alternative approaches:

1. Pseudo-machine language, using pattern-matching on two kinds of NOPs to allow branching or looping;
2. A LISP-link language, using recursion on named functions to allow iteration.

(1) is representable using a linear sequence of instructions and some form of virtual register or stack machine. (2) is representable using a tree, and evaluated using some form of "reduce" algorithm.

Whatever approach you use, you'll need to execute the programs in a sandbox - infinite loops will be common, so you'll need to be able to stop them after a set number of cycles.

Answer 2

Reflection is the technology to inspect already generated types, methods, fields, etc., hence it'll probably not help you much for now.

Expression trees are rather interesting, but AFAIK they will not allow you to create complex program flow since a lambda expression cannot have a body, which would make it rather difficult to create anything moderately complex.

DLR is somewhat in the making. You will get the bits and pieces, but only the next .NET version will have baked-in support for the DLR. That could be an interesting alternative, by creating programs on the fly and executing them.

What you could do now is possibly emitting IL, either in a Dynamic Method or a dynamically generated assembly. All possible constructs should be available to you, but a subsequent manipulation is probably rather difficult.

Even so, there is one project that does quite a bit of IL magic and it may even be something that could be useful to you: LinFu. According to the list you have an implementation of Dynamic Object and can do stuff like dynamicObject.CreateDuck<InterfaceType>()

Another route which may be a bit heavy but also interesting is the WF (Workflow Foundation) Framework. Such workflows should be constructable by program and they may be interesting due to their continuation style working: You can persist a running workflow any time and pick it up just where you left it.

All traditional program structures should be available to you within WF.

Answer 3

the Dynamic Expression [example] API covers ground in this space...

Answer 4

Just output c# (of any other .net language supporting this, f# works great too) and use the CodeDomProvider to compile it on the fly. Force the code supplied to be one source file, to include a type which implements IDynamicEntryPoint (with a static method or an empty constructor which is the entry point and will be invoked post construction)

This should be your first port of call to start with because it is quick to try out at the same time as long term having the best chance of the highest performance (barring dynamic IL output but even then you might not beat the compiler)

This obviously has two possible flaws which may be deal breakers:

• The resulting code is a security nightmare, only code input from fully trusted users should be allowed.
• The dynamically compiled code is fragile with respect to code/interface changes (the set of dll's the code must include might change/might not match) or the signature of the IDynamicEntryPoint might change.

Unless you are interested in writing your own language/parser/compiler for fun use one that's already there.