Changeset 14745 for branches/PushGP/HeuristicLab.PushGP/HeuristicLab.Problems.ProgramSynthesis

Timestamp:

03/11/17 12:42:31 (8 years ago)

Author:

pkimmesw

Message:

#2665 Merged ExecExpandExpression and PushProgram due to performance reasons, Tested managed object pooling

Location:

branches/PushGP/HeuristicLab.PushGP/HeuristicLab.Problems.ProgramSynthesis

Files:

• HeuristicLab.Problems.ProgramSynthesis.csproj (modified) (1 diff)
• Push/Configuration/IReadonlyPushGpConfiguration.cs (deleted)
• Push/Configuration/PushGpConfiguration.cs (deleted)
• Push/Data/Tree (deleted)
• Push/Expressions/CodeExpressions.cs (modified) (24 diffs)
• Push/Expressions/ExecExpressions.cs (modified) (4 diffs)
• Push/Expressions/Expression.cs (modified) (1 diff)
• Push/Expressions/ExpressionTable.cs (modified) (2 diffs)
• Push/Expressions/PushProgram.bk.cs (added)
• Push/Expressions/PushProgram.cs (modified) (14 diffs)
• Push/Expressions/StatefulExpression.cs (modified) (1 diff)
• Push/Expressions/StatefullExpression.cs (deleted)
• Push/Generators/CodeGenerator.cs (modified) (1 diff)
• Push/Interpreter/IPushGpInterpreter.cs (deleted)
• Push/Interpreter/IPushInterpreter.cs (modified) (1 diff)
• Push/Interpreter/PooledPushGpInterpreter.cs (deleted)
• Push/Interpreter/PushGPInterpreter.cs (deleted)
• Push/Interpreter/PushGpInterpreterPool.cs (deleted)
• Push/Interpreter/PushInterpreter.cs (modified) (3 diffs)
• Push/Parser/PushGPParser.cs (deleted)
• Push/Parser/PushParser.cs (modified) (4 diffs)
• Push/Problem/PushProblem.cs (modified) (1 diff)
• Push/Simplifier/ISimplifier.cs (modified) (1 diff)
• Push/Simplifier/RandomSimplifier.cs (modified) (2 diffs)
• Push/Stack/PushGPStack.cs (deleted)

branches/PushGP/HeuristicLab.PushGP/HeuristicLab.Problems.ProgramSynthesis/HeuristicLab.Problems.ProgramSynthesis.csproj

@@ -138 +138 @@
     <Compile Include="Push\Expressions\NameExpressions.cs" />
     <Compile Include="Push\Expressions\PopExpressions.cs" />
+    <Compile Include="Push\Expressions\PushProgram.bk.cs" />
+    <Compile Include="Push\Expressions\PushExpressions.cs" />
     <Compile Include="Push\Expressions\PushProgram.cs" />
-    <Compile Include="Push\Expressions\PushExpressions.cs" />
     <Compile Include="Push\Expressions\PushResultExpression.cs" />
     <Compile Include="Push\Expressions\RandExpressions.cs" />

branches/PushGP/HeuristicLab.PushGP/HeuristicLab.Problems.ProgramSynthesis/Push/Expressions/CodeExpressions.cs

@@ -114 +114 @@
 
       if (isFirstList) {
-        var expand1 = first as ExecExpandExpression;
+        var expand1 = first as PushProgram;
 
         if (isSecondList) {
-          var expand2 = second as ExecExpandExpression;
-          var size = expand2.State.Expressions.Count + expand1.State.Expressions.Count;
+          var expand2 = second as PushProgram;
+          var size = expand2.State.Length + expand1.State.Length;
 
           // if size > maxPointsInProgram this expressions results in a NOOP
@@ -125 +125 @@
           result = new Expression[size];
 
-          Array.Copy(expand2.State.Expressions as Expression[], result, expand2.State.Expressions.Count);
+          Array.Copy(expand2.State, result, expand2.State.Length);
           Array.Copy(
-              expand1.State.Expressions as Expression[],
+              expand1.State,
               0,
               result,
-              expand2.State.Expressions.Count,
-              expand1.State.Expressions.Count);
+              expand2.State.Length,
+              expand1.State.Length);
         } else {
-          var size = expand1.State.Expressions.Count + 1;
+          var size = expand1.State.Length + 1;
 
           // if size > maxPointsInProgram this expressions results in a NOOP
@@ -141 +141 @@
           result[0] = second;
 
-          Array.Copy(expand1.State.Expressions as Expression[], 0, result, 1, expand1.State.Expressions.Count);
+          Array.Copy(expand1.State, 0, result, 1, expand1.State.Length);
         }
       } else if (isSecondList) {
-        var expand2 = second as ExecExpandExpression;
-
-        var size = expand2.State.Expressions.Count + 1;
+        var expand2 = second as PushProgram;
+
+        var size = expand2.State.Length + 1;
 
         // if size > maxPointsInProgram this expressions results in a NOOP
@@ -154 +154 @@
         result[0] = first;
 
-        Array.Copy(expand2.State.Expressions as Expression[], 0, result, 1, expand2.State.Expressions.Count);
+        Array.Copy(expand2.State as Expression[], 0, result, 1, expand2.State.Length);
       } else {
         result = new[] { second, first };
       }
 
-      var expression = new ExecExpandExpression(result);
+      var expression = new PushProgram(result);
 
       interpreter.CodeStack.SetTop(expression);
@@ -194 +194 @@
     public override bool Eval(IPushInterpreter interpreter) {
       if ((interpreter.CodeStack.Count == 0) ||
-          (interpreter.CodeStack.Top.GetType() != typeof(ExecExpandExpression))) return false;
-
-      var expand = interpreter.CodeStack.Top as ExecExpandExpression;
-
-      if (expand.State.IsEmpty) return false;
-      var first = expand.State.Expressions[expand.State.Expressions.Count - 1];
+          (interpreter.CodeStack.Top.GetType() != typeof(PushProgram))) return false;
+
+      var expand = interpreter.CodeStack.Top as PushProgram;
+
+      if (expand.IsEmpty) return false;
+      var first = expand.State[expand.State.Length - 1];
 
       interpreter.CodeStack.SetTop(first);
@@ -217 +217 @@
       if (interpreter.CodeStack.Count == 0) return false;
 
-      ExecExpandExpression expandExpression;
+      PushProgram expandExpression;
       var top = interpreter.CodeStack.Top;
 
       if (top.CanExpand) {
-        var expand = (ExecExpandExpression)top;
-
-        if (expand.State.IsEmpty) return false;
-        var length = expand.State.Expressions.Count - 1;
+        var expand = (PushProgram)top;
+
+        if (expand.IsEmpty) return false;
+        var length = expand.State.Length - 1;
         var newExpressions = new Expression[length];
 
-        Array.Copy((Expression[])expand.State.Expressions, 0, newExpressions, 0, length);
-
-        expandExpression = new ExecExpandExpression(newExpressions);
+        Array.Copy((Expression[])expand.State, 0, newExpressions, 0, length);
+
+        expandExpression = new PushProgram(newExpressions);
       } else {
-        expandExpression = ExecExpandExpression.Empty;
+        expandExpression = PushProgram.Empty;
       }
 
@@ -250 +250 @@
         return false;
 
-      ExecExpandExpression result;
+      PushProgram result;
 
       if (interpreter.CodeStack.Top.CanExpand) {
-        var first = (ExecExpandExpression)interpreter.CodeStack.Pop();
-        var size = first.State.Expressions.Count + 1;
+        var first = (PushProgram)interpreter.CodeStack.Pop();
+        var size = first.State.Length + 1;
 
         if (size > interpreter.Configuration.MaxPointsInProgram) return false;
@@ -260 +260 @@
         var expressions = new Expression[size];
 
-        expressions[first.State.Expressions.Count] = interpreter.CodeStack.Top;
-        Array.Copy(first.State.Expressions as Expression[], expressions, first.State.Expressions.Count);
-
-        result = new ExecExpandExpression(expressions);
+        expressions[first.State.Length] = interpreter.CodeStack.Top;
+        Array.Copy(first.State as Expression[], expressions, first.State.Length);
+
+        result = new PushProgram(expressions);
       } else {
-        result = new ExecExpandExpression(interpreter.CodeStack.Pop(), interpreter.CodeStack.Top);
+        result = new PushProgram(interpreter.CodeStack.Pop(), interpreter.CodeStack.Top);
       }
 
@@ -286 +286 @@
       if ((interpreter.CodeStack.Count < 2) ||
           (interpreter.CodeStack[interpreter.CodeStack.Count - 2].GetType() !=
-           typeof(ExecExpandExpression))) return false;
+           typeof(PushProgram))) return false;
 
       var target = interpreter.CodeStack.Pop();
       var source = interpreter.CodeStack.Top;
 
-      var container = GetContainer(source as ExecExpandExpression, target);
-      var result = container ?? ExecExpandExpression.Empty;
+      var container = GetContainer(source as PushProgram, target);
+      var result = container ?? PushProgram.Empty;
 
       interpreter.CodeStack.SetTop(result);
@@ -298 +298 @@
     }
 
-    private static ExecExpandExpression GetContainer(ExecExpandExpression current, Expression target) {
+    private static PushProgram GetContainer(PushProgram current, Expression target) {
       if (current == target)
         return null;
 
       var subContainer =
-          current.State.Expressions.Where(e => e.CanExpand)
-              .Select(e => GetContainer(e as ExecExpandExpression, target))
+          current.State.Where(e => e.CanExpand)
+              .Select(e => GetContainer(e as PushProgram, target))
               .Where(e => e != null);
 
-      var execExpandExpressions = subContainer as IList<ExecExpandExpression> ?? subContainer.ToList();
+      var execExpandExpressions = subContainer as IList<PushProgram> ?? subContainer.ToList();
       return execExpandExpressions.Any()
-          ? execExpandExpressions.OrderBy(c => c.State.Expressions.Count).LastOrDefault()
-          : current.State.Expressions.Contains(target)
+          ? execExpandExpressions.OrderBy(c => c.State.Length).LastOrDefault()
+          : current.State.Contains(target)
               ? current
               : null;
@@ -328 +328 @@
 
       var values = interpreter.CodeStack.Pop(2);
-      var second = (ExecExpandExpression)values[0];
-      var contains = second.State.Expressions.Contains(values[1]);
+      var second = (PushProgram)values[0];
+      var contains = second.State.Contains(values[1]);
 
       interpreter.BooleanStack.Push(contains);
@@ -414 +414 @@
     private void DetermineUniqueItems(Expression source, IDictionary<int, int> items) {
       if (source.CanExpand) {
-        var expand = source as ExecExpandExpression;
-
-        foreach (var e in expand.State.Expressions) {
+        var expand = source as PushProgram;
+
+        foreach (var e in expand.State) {
           var id = e.GetHashCode();
           if (!items.ContainsKey(id)) items.Add(id, 1);
@@ -445 +445 @@
         return false;
 
-      var expression = (ExecExpandExpression)interpreter.CodeStack.Top;
-      var index = (int)Math.Abs(interpreter.IntegerStack.Pop() % expression.State.TotalCount);
+      var expression = (PushProgram)interpreter.CodeStack.Top;
+      var index = (int)Math.Abs(interpreter.IntegerStack.Pop() % expression.TotalCount);
       var result = expression.GetFromTree(index);
 
@@ -536 +536 @@
 
       var source = interpreter.CodeStack[interpreter.CodeStack.Count - 2];
-      var target = (ExecExpandExpression)interpreter.CodeStack.Pop();
+      var target = (PushProgram)interpreter.CodeStack.Pop();
       var index = (int)interpreter.IntegerStack.Pop();
 
       Expression[] newExpressions;
-      if (target.State.Expressions.Count > 0) {
-        index = target.State.Expressions.Count - 1 - Math.Abs(index % target.State.Expressions.Count);
-
-        newExpressions = target.State.CopyExpressions();
+      if (target.State.Length > 0) {
+        index = target.State.Length - 1 - Math.Abs(index % target.State.Length);
+
+        newExpressions = target.CopyExpressions();
         newExpressions[index] = source.CanExpand
-            ? ((ExecExpandExpression)source).Copy()
+            ? ((PushProgram)source).Copy()
             : source;
       } else {
@@ -551 +551 @@
       }
 
-      var result = new ExecExpandExpression(newExpressions);
+      var result = new PushProgram(newExpressions);
       interpreter.CodeStack.SetTop(result);
 
@@ -573 +573 @@
 
       if (expression.CanExpand)
-        count = ((ExecExpandExpression)expression).State.Expressions.Count;
+        count = ((PushProgram)expression).State.Length;
 
       interpreter.IntegerStack.Push(count);
@@ -591 +591 @@
       var first = interpreter.CodeStack.Pop();
       var second = interpreter.CodeStack.Top;
-      var expandExpression = new ExecExpandExpression(second, first);
+      var expandExpression = new PushProgram(second, first);
 
       interpreter.CodeStack.SetTop(expandExpression);
@@ -611 +611 @@
 
       var contains = expressions[1].CanExpand
-          ? ((ExecExpandExpression)expressions[1]).State.Expressions.Contains(expressions[0])
+          ? ((PushProgram)expressions[1]).State.Contains(expressions[0])
           : expressions[1].Equals(expressions[0]);
 
@@ -636 +636 @@
 
       if (expression.CanExpand) {
-        var subExpression = (ExecExpandExpression)expression;
-
-        if (subExpression.State.IsEmpty) {
-          nthExpression = ExecExpandExpression.Empty;
+        var subExpression = (PushProgram)expression;
+
+        if (subExpression.IsEmpty) {
+          nthExpression = PushProgram.Empty;
         } else {
-          var index = (int)(subExpression.State.Expressions.Count - 1 -
-                             Math.Abs(n % subExpression.State.Expressions.Count));
-
-          nthExpression = subExpression.State.Expressions[index];
+          var index = (int)(subExpression.State.Length - 1 -
+                             Math.Abs(n % subExpression.State.Length));
+
+          nthExpression = subExpression.State[index];
         }
       } else {
@@ -672 +672 @@
       var expression = interpreter.CodeStack.Top;
 
-      Expression nthExpression = null;
+      Expression nthExpression;
 
       if (expression.CanExpand) {
-        var subExpressions = ((ExecExpandExpression)expression).State.Expressions;
-
-        if (subExpressions.Count < 2) {
-          nthExpression = ExecExpandExpression.Empty;
+        var subExpressions = ((PushProgram)expression).State;
+
+        if (subExpressions.Length < 2) {
+          nthExpression = PushProgram.Empty;
         } else {
-          var index = (int)(subExpressions.Count - 2 - Math.Abs(n % (subExpressions.Count - 1)));
+          var index = (int)(subExpressions.Length - 2 - Math.Abs(n % (subExpressions.Length - 1)));
 
           nthExpression = subExpressions[index];
@@ -702 +702 @@
       if (interpreter.CodeStack.Count == 0) return false;
 
-      var result = interpreter.CodeStack.Pop().Equals(ExecExpandExpression.Empty);
+      var result = interpreter.CodeStack.Pop().Equals(PushProgram.Empty);
       interpreter.BooleanStack.Push(result);
 
@@ -724 +724 @@
       var position = -1;
       if (first.CanExpand) {
-        var expand = (ExecExpandExpression)first;
-        position = expand.State.Expressions.Count - 1
-                   - Array.FindIndex((Expression[])expand.State.Expressions, e => e.Equals(second));
+        var expand = (PushProgram)first;
+        position = expand.State.Length - 1
+                   - Array.FindIndex((Expression[])expand.State, e => e.Equals(second));
       } else if (first.Equals(second)) {
         position = 0;
@@ -748 +748 @@
       var expression = interpreter.CodeStack.Pop();
       var points = expression.CanExpand
-          ? ((ExecExpandExpression)expression).State.Expressions.Count
+          ? ((PushProgram)expression).State.Length
           : 1;
 
@@ -767 +767 @@
     public override bool Eval(IPushInterpreter interpreter) {
       if ((interpreter.CodeStack.Count < 3) || (interpreter.CodeStack.Top.GetType() !=
-                                                typeof(ExecExpandExpression))) return false;
+                                                typeof(PushProgram))) return false;
 
       var expressions = interpreter.CodeStack.Pop(2);
       var third = interpreter.CodeStack.Top;
       var second = expressions[0];
-      var first = expressions[1] as ExecExpandExpression;
-      var newExpressions = new Expression[first.State.Expressions.Count];
-
-      for (var i = 0; i < first.State.Expressions.Count; i++)
-        newExpressions[i] = first.State.Expressions[i].Equals(third)
+      var first = expressions[1] as PushProgram;
+      var newExpressions = new Expression[first.State.Length];
+
+      for (var i = 0; i < first.State.Length; i++)
+        newExpressions[i] = first.State[i].Equals(third)
             ? second
             /* no cloning needed here because first is removed and therefore newExpression is the only container of sub expressions */
-            : first.State.Expressions[i];
-
-      var result = new ExecExpandExpression(newExpressions);
+            : first.State[i];
+
+      var result = new PushProgram(newExpressions);
 
       interpreter.CodeStack.SetTop(result);

branches/PushGP/HeuristicLab.PushGP/HeuristicLab.Problems.ProgramSynthesis/Push/Expressions/ExecExpressions.cs

@@ -1 +1 @@
 namespace HeuristicLab.Problems.ProgramSynthesis.Push.Expressions {
-  using System;
-  using System.Collections.Generic;
-  using System.Linq;
 
   using HeuristicLab.Problems.ProgramSynthesis.Push.Attributes;
@@ -8 +5 @@
 
   using Interpreter;
-
-  public class ExecExpandExpression : StatefulExpression<PushProgram> {
-    public static readonly ExecExpandExpression Empty = new ExecExpandExpression(PushProgram.Empty);
-
-    public ExecExpandExpression(PushProgram program)
-      : base(program) {
-    }
-
-    public ExecExpandExpression(params Expression[] state) : this(new PushProgram(state)) {
-    }
-
-    public ExecExpandExpression(IEnumerable<Expression> state) : this(state.ToArray()) {
-      // TODO: lazy evaluation of ToArray()
-    }
-
-    public override string StringRepresentation { get { return this.State.ToString(); } }
-
-    public ExecExpandExpression Copy() {
-      // as the empty list is a static stateless expression, no copy required
-      return ReferenceEquals(this, Empty) || this.State.IsEmpty
-        ? Empty
-        : new ExecExpandExpression(this.State.Copy());
-    }
-
-    public override bool Eval(IPushInterpreter interpreter) {
-      interpreter.ExecStack.Push(this.State.Expressions);
-      return true;
-    }
-
-    /// <summary>
-    ///     Returns the element with the given index whereby the tree is indexed in depth first manner
-    /// </summary>
-    /// <param name="index">The index of the required element</param>
-    /// <returns>The required element</returns>
-    public Expression GetFromTree(int index) {
-      return GetFromTree(index, (root, parent, child, childIndex, parentIndex) => child);
-    }
-
-    /// <returns>The required element</returns>
-    public T GetFromTree<T>(int index,
-        Func<ExecExpandExpression, ExecExpandExpression, Expression, int, int, T> resolver) {
-      return GetFromTree(index, 0, null, resolver);
-    }
-
-    private T GetFromTree<T>(int index, int parentIndex, ExecExpandExpression parent,
-        Func<ExecExpandExpression, ExecExpandExpression, Expression, int, int, T> resolver) {
-      if (index == 0) return resolver(parent, parent, this, 0, parentIndex);
-
-      var min = State.Expressions.Count - 1;
-      var max = 0;
-      var mid = (min + max) / 2;
-
-      while ((max <= min) && (this.State.TreeIndex[mid] != index)) {
-        if (this.State.TreeIndex[mid] > index) max = mid + 1;
-        else min = mid - 1;
-
-        mid = (min + max) / 2;
-      }
-
-      return this.State.TreeIndex[mid] == index
-          ? resolver(parent, this, State.Expressions[mid], mid, parentIndex)
-          : (State.Expressions[mid + 1] as ExecExpandExpression).GetFromTree(index - this.State.TreeIndex[mid + 1], mid + 1,
-              this, resolver);
-    }
-  }
 
   /// <summary>
@@ -110 +42 @@
       var execYExpression = ExpressionTable.GetStatelessExpression<ExecYExpression>();
 
-      var result = new ExecExpandExpression(top, execYExpression);
+      var result = new PushProgram(top, execYExpression);
 
       interpreter.ExecStack.SetTop(result);
@@ -149 +81 @@
       var c = interpreter.ExecStack.Top;
 
-      var newTop = new ExecExpandExpression(c, b);
+      var newTop = new PushProgram(c, b);
 
       interpreter.ExecStack.SetTop(newTop);

branches/PushGP/HeuristicLab.PushGP/HeuristicLab.Problems.ProgramSynthesis/Push/Expressions/Expression.cs

@@ -8 +8 @@
 
   public abstract class Expression {
-    public bool CanExpand { get { return this.GetType() == typeof(ExecExpandExpression); } }
+    public bool CanExpand { get { return this.GetType() == typeof(PushProgram); } }
 
     public static readonly IReadOnlyCollection<Expression> EmptyContainer = new Expression[0];

branches/PushGP/HeuristicLab.PushGP/HeuristicLab.Problems.ProgramSynthesis/Push/Expressions/ExpressionTable.cs

@@ -123 +123 @@
     }
 
-    public static ExecExpandExpression GetProgram(int[] index) {
+    public static PushProgram GetProgram(int[] index) {
       var expressions = new Expression[index.Length];
 
@@ -130 +130 @@
       }
 
-      var program = new PushProgram(expressions);
-      return new ExecExpandExpression(program);
+      return new PushProgram(expressions);
     }
 

branches/PushGP/HeuristicLab.PushGP/HeuristicLab.Problems.ProgramSynthesis/Push/Expressions/PushProgram.cs

@@ -1 @@
-using System.Collections.Generic;
+using System;
+using System.Collections.Generic;
+using System.Linq;
 
 namespace HeuristicLab.Problems.ProgramSynthesis.Push.Expressions {
   using System.Diagnostics;
-  using System.Linq;
-
-  public class PushProgram {
+
+  using Interpreter;
+
+  public class PushProgram : StatefulExpression<Expression[]> {
+    public static readonly PushProgram Empty = new PushProgram();
 
     private const string Prefix = "(";
@@ -13 +17 @@
     private const string Delimiter = " ";
 
-    public static readonly PushProgram Empty = new PushProgram(new Expression[0]);
-
-    public readonly IReadOnlyList<Expression> Expressions;
-    public bool IsEmpty { get; private set; }
-
-    public PushProgram(Expression[] expressions) {
-      this.Expressions = expressions;
-      this.IsEmpty = expressions.Length == 0;
+    public readonly bool IsEmpty;
+
+    public PushProgram(params Expression[] state) : base(state) {
+      IsEmpty = state.Length == 0;
+    }
+
+    public PushProgram(IEnumerable<Expression> state) : this(state.ToArray()) {
+      // TODO: lazy evaluation of ToArray()
     }
 
     private string stringRepresentation;
-    private string StringRepresentation
+    public override string StringRepresentation
     {
       get
@@ -35 +39 @@
 
     private int depth = -1;
-    private int Depth
+    public int Depth
     {
       get
@@ -44 +48 @@
     }
 
-    private int[] treeIndex = null;
-    public int[] TreeIndex
-    {
-      get
-      {
-        return this.treeIndex ?? (this.treeIndex = this.BuildTreeIndex());
+    private int[] treeIndex;
+    private int[] TreeIndex
+    {
+      get
+      {
+        return treeIndex ?? (treeIndex = BuildTreeIndex());
       }
     }
@@ -61 +65 @@
         return hashCode;
       }
+    }
+
+    //public PushProgram Copy() {
+    //  // as the empty list is a static stateless expression, no copy required
+    //  return ReferenceEquals(this, Empty) || this.State.IsEmpty
+    //    ? Empty
+    //    : new PushProgram(this.State.Copy());
+    //}
+
+    public override bool Eval(IPushInterpreter interpreter) {
+      interpreter.ExecStack.Push(this.State);
+      return true;
     }
 
@@ -87 +103 @@
 
     public IEnumerable<Expression> DepthFirst() {
-      foreach (var expr in this.Expressions) {
+      foreach (var expr in this.State) {
         if (expr.CanExpand) {
-          var expandExpr = (ExecExpandExpression)expr;
-
-          foreach (var sub in expandExpr.State.DepthFirst())
+          var expandExpr = (PushProgram)expr;
+
+          foreach (var sub in expandExpr.DepthFirst())
             yield return sub;
         } else yield return expr;
@@ -98 +114 @@
 
     public PushProgram Copy() {
-      return IsEmpty ? this : new PushProgram((Expression[])Expressions) {
+      return IsEmpty ? this : new PushProgram(State) {
         stringRepresentation = this.stringRepresentation,
         hashCode = this.hashCode,
@@ -106 +122 @@
     }
 
-    public Expression[] CopyExpressions() {
-      var copy = new Expression[this.Expressions.Count];
-      ((Expression[])this.Expressions).CopyTo(copy, Expressions.Count);
+    public Expression[] CopyExpressions()
+    {
+      if (IsEmpty) return Empty.State;
+
+      var copy = new Expression[State.Length];
+      State.CopyTo(copy, 0);
 
       return copy;
@@ -114 +133 @@
 
     private int CalcDepth() {
-      //var subExpressions = Expressions.Where(e => e.CanExpand);
-      //var depth = subExpressions.Any()
-      //    ? subExpressions.Select(e => e as ExecExpandExpression).Max(e => e.State.Depth) + 1
-      //    : 1;
-
-      ////return depth;
-
       var maxDepth = 1;
-      for (var i = 0; i < Expressions.Count; i++) {
-        var expression = Expressions[i];
+      for (var i = 0; i < State.Length; i++) {
+        var expression = State[i];
         if (!expression.CanExpand) continue;
-        var expandExpression = (ExecExpandExpression)expression;
-
-        if (expandExpression.State.Depth > maxDepth)
-          maxDepth = expandExpression.State.Depth;
+        var expandExpression = (PushProgram)expression;
+
+        if (expandExpression.Depth > maxDepth)
+          maxDepth = expandExpression.Depth;
       }
 
@@ -137 +149 @@
       // prevent too big string
       return this.TotalCount > 50
-        ? PrefixReduced + this.Expressions.Count + PostfixReduced
-        : Prefix + string.Join(Delimiter, this.Expressions.Where(e => !string.IsNullOrWhiteSpace(e.StringRepresentation))) + Postfix;
+        ? PrefixReduced + this.State.Length + PostfixReduced
+        : Prefix + string.Join(Delimiter, this.State.Where(e => !string.IsNullOrWhiteSpace(e.StringRepresentation))) + Postfix;
     }
 
     private int[] BuildTreeIndex() {
-      var local_treeIndex = new int[this.Expressions.Count];
+      var local_treeIndex = new int[State.Length];
 
       var next = 1;
 
-      for (var i = this.Expressions.Count - 1; i >= 0; i--) {
-        var subExpression = this.Expressions[i];
+      for (var i = State.Length - 1; i >= 0; i--) {
+        var subExpression = State[i];
 
         local_treeIndex[i] = next;
 
         if (subExpression.CanExpand) {
-          next += ((ExecExpandExpression)subExpression).State.TotalCount;
+          next += ((PushProgram)subExpression).TotalCount;
         } else {
           next++;
@@ -164 +176 @@
       var hash = 19 * 31 + this.GetType().FullName.GetHashCode();
 
-      for (var i = 0; i < this.Expressions.Count; i++) {
-        hash = hash * 31 + this.Expressions[i].GetHashCode();
+      for (var i = 0; i < State.Length; i++) {
+        hash = hash * 31 + State[i].GetHashCode();
       }
 
@@ -171 +183 @@
     }
 
-    private static void CheckIfNested(int level, ExecExpandExpression target, ExecExpandExpression current,
-        IList<ExecExpandExpression> visited) {
+    private static void CheckIfNested(int level, PushProgram target, PushProgram current,
+        IList<PushProgram> visited) {
       if (visited.Any(x => ReferenceEquals(x, current)))
         Debugger.Break();
@@ -183 +195 @@
       }
 
-      for (var i = 0; i < current.State.Expressions.Count; i++) {
-        if (current.State.Expressions[i].CanExpand)
+      for (var i = 0; i < current.State.Length; i++) {
+        if (current.State[i].CanExpand)
           continue;
 
-        var subExpression = current.State.Expressions[i] as ExecExpandExpression;
+        var subExpression = current.State[i] as PushProgram;
 
         if (ReferenceEquals(target, subExpression)) {
@@ -199 +211 @@
       visited.RemoveAt(visited.Count - 1);
     }
+
+    /// <summary>
+    ///     Returns the element with the given index whereby the tree is indexed in depth first manner
+    /// </summary>
+    /// <param name="index">The index of the required element</param>
+    /// <returns>The required element</returns>
+    public Expression GetFromTree(int index) {
+      return GetFromTree(index, (root, parent, child, childIndex, parentIndex) => child);
+    }
+
+    /// <returns>The required element</returns>
+    public T GetFromTree<T>(int index,
+        Func<PushProgram, PushProgram, Expression, int, int, T> resolver) {
+      return GetFromTree(index, 0, null, resolver);
+    }
+
+    private T GetFromTree<T>(int index, int parentIndex, PushProgram parent,
+        Func<PushProgram, PushProgram, Expression, int, int, T> resolver) {
+      if (index == 0) return resolver(parent, parent, this, 0, parentIndex);
+
+      var min = State.Length - 1;
+      var max = 0;
+      var mid = (min + max) / 2;
+
+      while ((max <= min) && (TreeIndex[mid] != index)) {
+        if (TreeIndex[mid] > index) max = mid + 1;
+        else min = mid - 1;
+
+        mid = (min + max) / 2;
+      }
+
+      return TreeIndex[mid] == index
+          ? resolver(parent, this, State[mid], mid, parentIndex)
+          : (State[mid + 1] as PushProgram).GetFromTree(index - TreeIndex[mid + 1], mid + 1,
+              this, resolver);
+    }
   }
 }

branches/PushGP/HeuristicLab.PushGP/HeuristicLab.Problems.ProgramSynthesis/Push/Expressions/StatefulExpression.cs

@@ -1 +1 @@
 namespace HeuristicLab.Problems.ProgramSynthesis.Push.Expressions {
-  using HeuristicLab.Problems.ProgramSynthesis.Push.Data.Pool;
-
-  public abstract class StatefulExpression<T> : Expression
-  {
+  public abstract class StatefulExpression<T> : Expression {
     public readonly T State;
 

branches/PushGP/HeuristicLab.PushGP/HeuristicLab.Problems.ProgramSynthesis/Push/Generators/CodeGenerator.cs

@@ -24 +24 @@
     }
 
-    public static ExecExpandExpression RandomExpandExpression(int maxPoints, IRandom random = null, IReadonlyPushConfiguration pushGpConfiguration = null, IDictionary<string, Expression> customExpressions = null) {
+    public static PushProgram RandomExpandExpression(int maxPoints, IRandom random = null, IReadonlyPushConfiguration pushGpConfiguration = null, IDictionary<string, Expression> customExpressions = null) {
       var program = RandomProgram(maxPoints, random, pushGpConfiguration, customExpressions);
 
-      return new ExecExpandExpression(program);
+      return new PushProgram(program);
     }
 

branches/PushGP/HeuristicLab.PushGP/HeuristicLab.Problems.ProgramSynthesis/Push/Interpreter/IPushInterpreter.cs

@@ -28 +28 @@
     void Clear();
     void Run(string code, bool stepwise = false);
-    void Run(Expression program, bool stepwise = false);
-    void Run(PushProgram program, bool stepwise = false);
-    Task RunAsync(PushProgram program, bool paused = false, CancellationToken token = default(CancellationToken));
-    Task RunAsync(Expression program, bool paused = false, CancellationToken token = default(CancellationToken));
+    void Run(Expression expression, bool stepwise = false);
+    //void Run(PushProgram program, bool stepwise = false);
+    //Task RunAsync(PushProgram program, bool paused = false, CancellationToken token = default(CancellationToken));
+    Task RunAsync(Expression expression, bool paused = false, CancellationToken token = default(CancellationToken));
     Task RunAsync(string code, bool paused = false, CancellationToken token = default(CancellationToken));
     Task AbortAndResetAsync();

branches/PushGP/HeuristicLab.PushGP/HeuristicLab.Problems.ProgramSynthesis/Push/Interpreter/PushInterpreter.cs

@@ -7 +7 @@
   using HeuristicLab.Core;
   using HeuristicLab.Problems.ProgramSynthesis.Push.Configuration;
-  using HeuristicLab.Problems.ProgramSynthesis.Push.Data.Pool;
   using HeuristicLab.Problems.ProgramSynthesis.Push.Expressions;
   using HeuristicLab.Problems.ProgramSynthesis.Push.Parser;
@@ -101 +100 @@
     public bool IsNameQuoteFlagSet { get; set; }
 
+    public Task RunAsync(string code, bool stepwise = false, CancellationToken token = default(CancellationToken)) {
+      var program = PushParser.Parse(code);
+
+      currentTask = RunAsync(program, stepwise, token);
+
+      return currentTask;
+    }
+    public async Task RunAsync(
+      Expression expression,
+      bool stepwise = false,
+      CancellationToken token = default(CancellationToken)) {
+      await Task.Run(() => Run(expression, stepwise), token);
+    }
+
     public void Run(string code, bool stepwise = false) {
       var program = PushParser.Parse(code);
@@ -106 +119 @@
     }
 
-    public Task RunAsync(string code, bool stepwise = false, CancellationToken token = default(CancellationToken)) {
-      var program = PushParser.Parse(code);
-
-      currentTask = RunAsync(program, stepwise, token);
-
-      return currentTask;
-    }
-
-    public async Task RunAsync(
-      PushProgram program,
-      bool stepwise = false,
-      CancellationToken token = default(CancellationToken)) {
-      var expression = new ExecExpandExpression(program);
-
-      await RunAsync(expression, stepwise, token);
-    }
-
-    public async Task RunAsync(
-      Expression program,
-      bool stepwise = false,
-      CancellationToken token = default(CancellationToken)) {
-      await Task.Run(() => Run(program, stepwise), token);
-    }
-
-    public void Run(PushProgram program, bool stepwise = false) {
-      var expression = new ExecExpandExpression(program);
-
-      Run(expression, stepwise);
-    }
 
     public void Run(Expression program, bool stepwise = false) {

branches/PushGP/HeuristicLab.PushGP/HeuristicLab.Problems.ProgramSynthesis/Push/Parser/PushParser.cs

@@ -16 +16 @@
     private static readonly char[] symbolTrim = { '\r', '\n' };
 
-    public static Expression Parse(string source, int startIndex = 0) {
+    public static PushProgram Parse(string source, int startIndex = 0) {
       var symbols = source.Split(delimiter);
 
@@ -23 +23 @@
     }
 
-    private static Expression Parse(string[] symbols, int startIndex, out int endIndex) {
+    private static PushProgram Parse(string[] symbols, int startIndex, out int endIndex) {
       var expressions = new List<Expression>();
 
@@ -39 +39 @@
           case closeBrace:
             endIndex = i;
-            return new ExecExpandExpression(expressions.ToArray());
+            return new PushProgram(expressions.ToArray());
         }
 
@@ -62 +62 @@
       endIndex = symbols.Length - 1;
 
-      return expressions.Count == 1
-        ? expressions[0]
-        : new ExecExpandExpression(expressions.ToArray());
+      return new PushProgram(expressions.ToArray());
     }
 

branches/PushGP/HeuristicLab.PushGP/HeuristicLab.Problems.ProgramSynthesis/Push/Problem/PushProblem.cs

@@ -406 +406 @@
 
       var program = individual.PushProgram(config.EnabledExpressions as IReadOnlyList<string>);
-      var expandExpression = new ExecExpandExpression(program);
+      var expandExpression = new PushProgram(program);
       var results = new List<double>();
 

branches/PushGP/HeuristicLab.PushGP/HeuristicLab.Problems.ProgramSynthesis/Push/Simplifier/ISimplifier.cs

@@ -6 +6 @@
 
   public interface ISimplifier {
-    ExecExpandExpression Simplify(ExecExpandExpression program, IRandom random, Predicate<ExecExpandExpression> isBetter);
+    PushProgram Simplify(PushProgram program, IRandom random, Predicate<PushProgram> isBetter);
   }
 }

branches/PushGP/HeuristicLab.PushGP/HeuristicLab.Problems.ProgramSynthesis/Push/Simplifier/RandomSimplifier.cs

@@ -7 +7 @@
     public int Trys { get; set; }
 
-    public ExecExpandExpression Simplify(ExecExpandExpression program, IRandom random, Predicate<ExecExpandExpression> isBetter) {
+    public PushProgram Simplify(PushProgram program, IRandom random, Predicate<PushProgram> isBetter) {
 
-      if (program.State.TotalCount == 1) {
-        return isBetter(ExecExpandExpression.Empty) ? ExecExpandExpression.Empty : program;
+      if (program.TotalCount == 1) {
+        return isBetter(PushProgram.Empty) ? PushProgram.Empty : program;
       }
 
       var copy = program.Copy();
-      var maxTries = Math.Min(Trys, program.State.TotalCount - 2);
+      var maxTries = Math.Min(Trys, program.TotalCount - 2);
       var successfulRemoves = 0;
 
       for (var i = 0; i < maxTries; i++) {
-        var rndIndex = random.Next(1, program.State.TotalCount - 1 - successfulRemoves);
+        var rndIndex = random.Next(1, program.TotalCount - 1 - successfulRemoves);
         var node = copy.GetFromTree(
           rndIndex,
@@ -28 +28 @@
           });
 
-        var oldParentExpressions = node.Parent.State.Expressions as Expression[];
+        var oldParentExpressions = node.Parent.State;
         var newParentExpressions = RemoveAt(oldParentExpressions, node.ChildIndex);
-        var newParent = new ExecExpandExpression(newParentExpressions);
+        var newParent = new PushProgram(newParentExpressions);
 
-        var superExpressions = (node.Super == null ? copy.State.Expressions : node.Super.State.Expressions) as Expression[];
+        var superExpressions = node.Super == null ? copy.State : node.Super.State;
         superExpressions[node.ParentIndex] = newParent;