source: branches/PushGP/HeuristicLab.Algorithms.PushGP/HeuristicLab.Algorithms.PushGP/Expressions/CodeExpressions.cs @ 14513

/// <summary>
/// For explicit code manipulation and execution. May also be used as a general list data type.
/// This type must always be present, as the top level interpreter will push any code to be executed on the
/// CODE stack prior to execution. However, one may turn off all CODE instructions if code manipulation is not needed.
/// </summary>

namespace HeuristicLab.Algorithms.PushGP.Expressions {
  using System;
  using System.Collections.Generic;
  using System.Linq;

  using HeuristicLab.Algorithms.PushGP.Interpreter;

  /// <summary>
  ///     Recursively invokes the interpreter on the program on top of the CODE stack. After evaluation the
  ///     CODE stack is popped; normally this pops the program that was just executed, but if the expression itself
  ///     manipulates the stack then this final pop may end up popping something else.
  /// </summary>
  public class CodeDoExpression : StatelessExpression {
    protected override string InitStringRepresentation() {
      return "CODE.DO";
    }

    public override void Eval(IPushGpInterpreter interpreter) {
      // not enough arguments on stack
      if (interpreter.CodeStack.Count == 0) return;

      interpreter.ExecStack.Push(new CodePopExpression(), interpreter.CodeStack.Top);
    }
  }

  /// <summary>
  ///     Like CODE.DO but pops the stack before, rather than after, the recursive execution
  /// </summary>
  public class CodeDoXExpression : StatelessExpression {
    protected override string InitStringRepresentation() {
      return "CODE.DO*";
    }

    public override void Eval(IPushGpInterpreter interpreter) {
      // not enough arguments on stack
      if (interpreter.CodeStack.Count == 0) return;

      var expression = interpreter.CodeStack.Pop();
      interpreter.ExecStack.Push(expression);
    }
  }

  /// <summary>
  ///     Does nothing.
  /// </summary>
  public class CodeNoopExpression : StatelessExpression {
    protected override string InitStringRepresentation() {
      return "CODE.NOOP";
    }

    public override void Eval(IPushGpInterpreter interpreter) {
      // nothing to do
    }
  }

  /// <summary>
  ///     Specifies that the next expression submitted for execution will instead be pushed literally onto the CODE stack.
  ///     This can be implemented by moving the top item on the EXEC stack onto the CODE stack.
  /// </summary>
  public class CodeQuoteExpression : StatelessExpression {
    protected override string InitStringRepresentation() {
      return "CODE.QUOTE";
    }

    public override void Eval(IPushGpInterpreter interpreter) {
      // not enough arguments on stack
      if (interpreter.ExecStack.Count == 0) return;

      var expression = interpreter.ExecStack.Pop();
      interpreter.CodeStack.Push(expression);
    }
  }

  /// <summary>
  ///     If the top item of the BOOLEAN stack is TRUE this recursively executes the second item of the CODE stack;
  ///     otherwise it recursively executes the first item of the CODE stack. Either way both elements of the CODE stack
  ///     (and the BOOLEAN value upon which the decision was made) are popped.
  /// </summary>
  public class CodeIfExpression : StatelessExpression {
    protected override string InitStringRepresentation() {
      return "CODE.IF";
    }

    public override void Eval(IPushGpInterpreter interpreter) {
      // not enough arguments on stack
      if ((interpreter.BooleanStack.Count == 0) || (interpreter.CodeStack.Count < 2)) return;

      var condition = interpreter.BooleanStack.Pop();
      var items = interpreter.CodeStack.Pop(2);

      interpreter.ExecStack.Push(condition ? items[0] : items[1]);
    }
  }

  /// <summary>
  ///     Pushes the result of appending the top two pieces of code. If one of the pieces of code is a single instruction or
  ///     literal (that is, something not surrounded by parentheses) then it is surrounded by parentheses first.
  /// </summary>
  public class CodeAppendExpression : StatelessExpression {
    protected override string InitStringRepresentation() {
      return "CODE.APPEND";
    }

    public override void Eval(IPushGpInterpreter interpreter) {
      if (interpreter.CodeStack.Count < 2) return;

      var first = interpreter.CodeStack.Pop();
      var second = interpreter.CodeStack.Top;

      var isFirstList = first.GetType() == typeof(ExecExpandExpression);
      var isSecondList = second.GetType() == typeof(ExecExpandExpression);

      Expression[] result = null;

      if (isFirstList) {
        var expand1 = first as ExecExpandExpression;

        if (isSecondList) {
          var expand2 = second as ExecExpandExpression;
          var size = expand2.Expressions.Count + expand1.Expressions.Count;

          // if size > maxPointsInProgram this expressions results in a NOOP
          if (size > interpreter.Configuration.MaxPointsInProgram) return;

          result = new Expression[size];

          Array.Copy(expand2.Expressions as Expression[], result, expand2.Expressions.Count);
          Array.Copy(
            expand1.Expressions as Expression[],
            0,
            result,
            expand2.Expressions.Count,
            expand1.Expressions.Count);
        } else {
          var size = expand1.Expressions.Count + 1;

          // if size > maxPointsInProgram this expressions results in a NOOP
          if (size > interpreter.Configuration.MaxPointsInProgram) return;

          result = new Expression[size];
          result[0] = second;

          Array.Copy(expand1.Expressions as Expression[], 0, result, 1, expand1.Expressions.Count);
        }
      } else if (isSecondList) {
        var expand2 = second as ExecExpandExpression;

        var size = expand2.Expressions.Count + 1;

        // if size > maxPointsInProgram this expressions results in a NOOP
        if (size > interpreter.Configuration.MaxPointsInProgram) return;

        result = new Expression[size];
        result[0] = first;

        Array.Copy(expand2.Expressions as Expression[], 0, result, 1, expand2.Expressions.Count);
      } else {
        result = new[] { second, first };
      }

      var expression = new ExecExpandExpression(result);

      interpreter.CodeStack.SetTop(expression);
    }
  }

  /// <summary>
  ///     Pushes TRUE onto the BOOLEAN stack if the top piece of code is a single instruction or a literal,
  ///     and FALSE otherwise (that is, if it is something surrounded by parentheses).
  /// </summary>
  public class CodeAtomExpression : StatelessExpression {
    protected override string InitStringRepresentation() {
      return "CODE.ATOM";
    }

    public override void Eval(IPushGpInterpreter interpreter) {
      if (interpreter.CodeStack.Count == 0) return;

      var expression = interpreter.CodeStack.Pop();
      var isExpandExpression = expression.GetType() != typeof(ExecExpandExpression);

      interpreter.BooleanStack.Push(isExpandExpression);
    }
  }

  /// <summary>
  ///     Pushes the first item of the list on top of the CODE stack. For example, if the top piece of code is "( A B )"
  ///     then this pushes "A" (after popping the argument). If the code on top of the stack is not a list then this has no
  ///     effect.
  ///     The name derives from the similar Lisp function; a more generic name would be "FIRST".
  /// </summary>
  public class CodeCarExpression : StatelessExpression {
    protected override string InitStringRepresentation() {
      return "CODE.CAR";
    }

    public override void Eval(IPushGpInterpreter interpreter) {
      if ((interpreter.CodeStack.Count == 0) || (interpreter.CodeStack.Top.GetType() != typeof(ExecExpandExpression))) return;

      var expand = interpreter.CodeStack.Top as ExecExpandExpression;

      if (!expand.IsEmpty) {
        var first = expand.Expressions[expand.Expressions.Count - 1];

        interpreter.CodeStack.SetTop(first);
      }
    }
  }

  /// <summary>
  ///     Pushes a version of the list from the top of the CODE stack without its first element.
  ///     For example, if the top piece of code is "( A B )" then this pushes "( B )" (after popping the argument).
  ///     If the code on top of the stack is not a list then this pushes the empty list ("( )"). The name derives from
  ///     the similar Lisp function; a more generic name would be "REST".
  /// </summary>
  public class CodeCdrExpression : StatelessExpression {
    protected override string InitStringRepresentation() {
      return "CODE.CDR";
    }

    public override void Eval(IPushGpInterpreter interpreter) {
      if (interpreter.CodeStack.Count == 0) return;

      Expression expandExpression = null;
      var top = interpreter.CodeStack.Top;

      if (top.GetType() == typeof(ExecExpandExpression)) {
        var expand = top as ExecExpandExpression;

        if (expand.IsEmpty) return;
        var length = expand.Expressions.Count - 1;
        var newExpressions = new Expression[length];

        Array.Copy(expand.Expressions as Expression[], 0, newExpressions, 0, length);

        expandExpression = new ExecExpandExpression(newExpressions);
      } else {
        expandExpression = ExecExpandExpression.Empty;
      }

      interpreter.CodeStack.SetTop(expandExpression);
    }
  }

  /// <summary>
  ///     Pushes the result of "consing" (in the Lisp sense) the second stack item onto the first stack item
  ///     (which is coerced to a list if necessary). For example, if the top piece of code is "( A B )" and the
  ///     second piece of code is "X" then this pushes "( X A B )" (after popping the argument).
  /// </summary>
  public class CodeConsExpression : StatelessExpression {
    protected override string InitStringRepresentation() {
      return "CODE.CONS";
    }

    public override void Eval(IPushGpInterpreter interpreter) {
      if ((interpreter.CodeStack.Count < 2)
          || (interpreter.CodeStack[interpreter.CodeStack.Count - 1].GetType() != typeof(ExecExpandExpression))) return;

      var first = interpreter.CodeStack.Pop() as ExecExpandExpression;

      var size = first.Expressions.Count + 1;

      if (size > interpreter.Configuration.MaxPointsInProgram) return;

      var expressions = new Expression[size];

      expressions[first.Expressions.Count] = interpreter.CodeStack.Top;
      Array.Copy(first.Expressions as Expression[], expressions, first.Expressions.Count);

      var result = new ExecExpandExpression(expressions);
      interpreter.CodeStack.SetTop(result);
    }
  }

  /// <summary>
  ///     Pushes the "container" of the second CODE stack item within the first CODE stack item onto the CODE stack.
  ///     If second item contains the first anywhere (i.e. in any nested list) then the container is the smallest sub-list
  ///     that contains but is not equal to the first instance. For example, if the top piece of code is "( B ( C ( A ) ) ( D
  ///     ( A ) ) )"
  ///     and the second piece of code is "( A )" then this pushes ( C ( A ) ). Pushes an empty list if there is no such
  ///     container.
  /// </summary>
  public class CodeContainerExpression : StatelessExpression {
    protected override string InitStringRepresentation() {
      return "CODE.CONTAINER";
    }

    public override void Eval(IPushGpInterpreter interpreter) {
      if ((interpreter.CodeStack.Count < 2)
          || (interpreter.CodeStack[interpreter.CodeStack.Count - 2].GetType() != typeof(ExecExpandExpression))) return;

      var target = interpreter.CodeStack.Pop();
      var source = interpreter.CodeStack.Top;

      var container = this.GetContainer(null, source as ExecExpandExpression, target);
      var result = container == null ? ExecExpandExpression.Empty : container;

      interpreter.CodeStack.SetTop(result);
    }

    private ExecExpandExpression GetContainer(
      ExecExpandExpression parent,
      ExecExpandExpression current,
      Expression target) {
      var subContainer =
        current.Expressions.Where(e => e.GetType() == typeof(ExecExpandExpression))
          .Select(e => this.GetContainer(current, e as ExecExpandExpression, target))
          .Where(e => e != null);

      if (subContainer.Any()) return subContainer.OrderBy(c => c.Expressions.Count).LastOrDefault();
      return current.Expressions.Contains(target) ? current : null;
    }
  }

  /// <summary>
  ///     Pushes TRUE on the BOOLEAN stack if the second CODE stack item contains the first CODE stack
  ///     item anywhere (e.g. in a sub-list).
  /// </summary>
  public class CodeContainsExpression : StatelessExpression {
    protected override string InitStringRepresentation() {
      return "CODE.CONTAINS";
    }

    public override void Eval(IPushGpInterpreter interpreter) {
      if ((interpreter.CodeStack.Count < 2)
          || (interpreter.CodeStack[interpreter.CodeStack.Count - 2].GetType() != typeof(ExecExpandExpression))) return;

      var values = interpreter.CodeStack.Pop(2);
      var second = values[0] as ExecExpandExpression;

      interpreter.BooleanStack.Push(second.Expressions.Contains(values[1]));
    }
  }

  /// <summary>
  ///     Pushes the definition associated with the top NAME on the NAME stack (if any) onto the CODE stack.
  ///     This extracts the definition for inspection/manipulation, rather than for immediate execution (although it
  ///     may then be executed with a call to CODE.DO or a similar instruction).
  /// </summary>
  public class CodeDefinitionExpression : StatelessExpression {
    protected override string InitStringRepresentation() {
      return "CODE.DEFINITION";
    }

    public override void Eval(IPushGpInterpreter interpreter) {
      if ((interpreter.NameStack.Count == 0) || !interpreter.CustomExpressions.ContainsKey(interpreter.NameStack.Top)) return;

      var name = interpreter.NameStack.Pop();
      var definition = interpreter.CustomExpressions[name];

      interpreter.CodeStack.Push(definition);
    }
  }

  /// <summary>
  ///     Pushes a measure of the discrepancy between the top two CODE stack items onto the INTEGER stack. This will be zero
  ///     if the top
  ///     two items are equivalent, and will be higher the 'more different' the items are from one another. The calculation
  ///     is as follows:
  ///     <list type="bullet">
  ///         <item>
  ///             <description>
  ///                 Construct a list of all of the unique items in both of the lists(where uniqueness is determined by
  ///                 equalp).
  ///                 Sub-lists and atoms all count as items.
  ///         </item>
  ///         <item>
  ///             <description>Initialize the result to zero.
  ///         </item>
  ///         <item>
  ///             <description>
  ///                 For each unique item increment the result by the difference between the number of occurrences of the
  ///                 item in
  ///                 the two pieces of code.
  ///         </item>
  ///         <item>
  ///             <description>Push the result.
  ///         </item>
  ///     </list>
  /// </summary>
  public class CodeDiscrepancyExpression : StatelessExpression {
    protected override string InitStringRepresentation() {
      return "CODE.DISCREPANCY";
    }

    public override void Eval(IPushGpInterpreter interpreter) {
      if (interpreter.CodeStack.Count < 2) return;

      var expressions = interpreter.CodeStack.Pop(2);
      var firstItems = new Dictionary<int, int>();
      var secondItems = new Dictionary<int, int>();

      this.DetermineUniqueItems(expressions[0], secondItems);
      this.DetermineUniqueItems(expressions[1], firstItems);

      var discrepancy = this.GetDiscrepancy(firstItems, secondItems);

      interpreter.IntegerStack.Push(discrepancy);
    }

    private int GetDiscrepancy(IDictionary<int, int> first, IDictionary<int, int> second) {
      var discrepancy = 0;
      var keys = first.Keys.Concat(second.Keys).Distinct();

      foreach (var key in keys)
        if (first.ContainsKey(key) && second.ContainsKey(key)) discrepancy += Math.Abs(first[key] - second[key]);
        else if (first.ContainsKey(key)) discrepancy += first[key];
        else discrepancy += second[key];

      return discrepancy;
    }

    private void DetermineUniqueItems(Expression source, IDictionary<int, int> items) {
      if (source.GetType() == typeof(ExecExpandExpression)) {
        var expand = source as ExecExpandExpression;

        foreach (var e in expand.Expressions) {
          var id = e.GetHashCode();
          if (!items.ContainsKey(id)) items.Add(id, 1);
          else items[id]++;
        }
      } else {
        items.Add(source.GetHashCode(), 1);
      }
    }
  }

  /// <summary>
  ///     Pushes the sub-expression of the top item of the CODE stack that is indexed by the top item of the INTEGER stack.
  ///     The indexing here counts "points," where each parenthesized expression and each literal/instruction is considered a
  ///     point,
  ///     and it proceeds in depth first order. The entire piece of code is at index 0; if it is a list then the first item
  ///     in the list
  ///     is at index 1, etc. The integer used as the index is taken modulo the number of points in the overall expression
  ///     (and its
  ///     absolute value is taken in case it is negative) to ensure that it is within the meaningful range.
  /// </summary>
  public class CodeExtractExpression : StatelessExpression {
    protected override string InitStringRepresentation() {
      return "CODE.EXTRACT";
    }

    public override void Eval(IPushGpInterpreter interpreter) {
      if ((interpreter.IntegerStack.Count == 0) || (interpreter.CodeStack.Count == 0)
          || (interpreter.CodeStack.Top.GetType() != typeof(ExecExpandExpression))) return;

      var expression = interpreter.CodeStack.Top as ExecExpandExpression;
      var index = (int)Math.Abs(interpreter.IntegerStack.Pop() % expression.TotalCount);
      var result = expression.GetFromTree(index);

      interpreter.CodeStack.SetTop(result);
    }
  }

  /// <summary>
  ///     Pops the BOOLEAN stack and pushes the popped item (TRUE or FALSE) onto the CODE stack.
  /// </summary>
  public class CodeFromBooleanExpression : StatelessExpression {
    protected override string InitStringRepresentation() {
      return "CODE.FROMBOOLEAN";
    }

    public override void Eval(IPushGpInterpreter interpreter) {
      if (interpreter.BooleanStack.Count == 0) return;

      var value = interpreter.BooleanStack.Pop();
      var expression = new BooleanPushExpression(value);

      interpreter.CodeStack.Push(expression);
    }
  }

  /// <summary>
  ///     Pops the FLOAT stack and pushes the popped item onto the CODE stack.
  /// </summary>
  public class CodeFromFloatExpression : StatelessExpression {
    protected override string InitStringRepresentation() {
      return "CODE.FROMFLOAT";
    }

    public override void Eval(IPushGpInterpreter interpreter) {
      if (interpreter.FloatStack.Count == 0) return;

      var value = interpreter.FloatStack.Pop();
      var expression = new FloatPushExpression(value);

      interpreter.CodeStack.Push(expression);
    }
  }

  /// <summary>
  ///     Pops the INTEGER stack and pushes the popped integer onto the CODE stack.
  /// </summary>
  public class CodeFromIntegerExpression : StatelessExpression {
    protected override string InitStringRepresentation() {
      return "CODE.FROMINTEGER";
    }

    public override void Eval(IPushGpInterpreter interpreter) {
      if (interpreter.IntegerStack.Count == 0) return;

      var value = interpreter.IntegerStack.Pop();
      var expression = new IntegerPushExpression(value);

      interpreter.CodeStack.Push(expression);
    }
  }

  /// <summary>
  ///     Pops the NAME stack and pushes the popped item onto the CODE stack.
  /// </summary>
  public class CodeFromNameExpression : StatelessExpression {
    protected override string InitStringRepresentation() {
      return "CODE.FROMNAME";
    }

    public override void Eval(IPushGpInterpreter interpreter) {
      if (interpreter.NameStack.Count == 0) return;

      var value = interpreter.NameStack.Pop();
      var expression = new NameDefineXExecExpression(value);

      interpreter.CodeStack.Push(expression);
    }
  }

  /// <summary>
  ///     Pushes the result of inserting the second item of the CODE stack into the first item, at the position indexed
  ///     by the top item of the INTEGER stack (and replacing whatever was there formerly).
  /// </summary>
  public class CodeInsertExpression : StatelessExpression {
    protected override string InitStringRepresentation() {
      return "CODE.INSERT";
    }

    public override void Eval(IPushGpInterpreter interpreter) {
      if ((interpreter.IntegerStack.Count == 0) || (interpreter.CodeStack.Count < 2)
          || (interpreter.CodeStack.Top.GetType() != typeof(ExecExpandExpression))) return;

      var source = interpreter.CodeStack[interpreter.CodeStack.Count - 2];
      var target = interpreter.CodeStack.Pop() as ExecExpandExpression;
      var index = (int)interpreter.IntegerStack.Pop();

      Expression[] newExpressions;
      if (target.Expressions.Count > 0) {
        index = target.Expressions.Count - 1 - Math.Abs(index % target.Expressions.Count);

        newExpressions = target.CopyExpressions();
        newExpressions[index] = source.GetType() == typeof(ExecExpandExpression)
          ? (source as ExecExpandExpression).Copy()
          : source;
      } else {
        newExpressions = new[] { source };
      }

      var result = new ExecExpandExpression(newExpressions);
      interpreter.CodeStack.SetTop(result);
    }
  }

  /// <summary>
  ///     Pushes the length of the top item on the CODE stack onto the INTEGER stack.
  ///     If the top item is not a list then this pushes a 1. If the top item is a list then this pushes the
  ///     number of items in the top level of the list; that is, nested lists contribute only 1 to this count, no
  ///     matter what they contain.
  /// </summary>
  public class CodeLengthExpression : StatelessExpression {
    protected override string InitStringRepresentation() {
      return "CODE.LENGTH";
    }

    public override void Eval(IPushGpInterpreter interpreter) {
      if (interpreter.CodeStack.Count == 0) return;

      var expression = interpreter.CodeStack.Pop();
      var count = 1;

      if (expression.GetType() == typeof(ExecExpandExpression)) count = (expression as ExecExpandExpression).Expressions.Count;

      interpreter.IntegerStack.Push(count);
    }
  }

  /// <summary>
  ///     Pushes a list of the top two items of the CODE stack onto the CODE stack.
  /// </summary>
  public class CodeListExpression : StatelessExpression {
    protected override string InitStringRepresentation() {
      return "CODE.LIST";
    }

    public override void Eval(IPushGpInterpreter interpreter) {
      if (interpreter.CodeStack.Count < 2) return;

      var first = interpreter.CodeStack.Pop();
      var second = interpreter.CodeStack.Top;

      var expandExpression = new ExecExpandExpression(new[] { second, first });

      interpreter.CodeStack.SetTop(expandExpression);
    }
  }

  /// <summary>
  ///     Pushes TRUE onto the BOOLEAN stack if the second item of the CODE stack is a member of the first item
  ///     (which is coerced to a list if necessary). Pushes FALSE onto the BOOLEAN stack otherwise.
  /// </summary>
  public class CodeMemberExpression : StatelessExpression {
    protected override string InitStringRepresentation() {
      return "CODE.MEMBER";
    }

    public override void Eval(IPushGpInterpreter interpreter) {
      if (interpreter.CodeStack.Count < 2) return;

      var expressions = interpreter.CodeStack.Pop(2);

      var contains = expressions[1].GetType() == typeof(ExecExpandExpression)
                       ? (expressions[1] as ExecExpandExpression).Expressions.Contains(expressions[0])
                       : expressions[1].Equals(expressions[0]);

      interpreter.BooleanStack.Push(contains);
    }
  }

  /// <summary>
  ///     Pushes the nth element of the expression on top of the CODE stack (which is coerced to a list first if necessary).
  ///     If the expression is an empty list then the result is an empty list. N is taken from the INTEGER stack and is taken
  ///     modulo the length of the expression into which it is indexing.
  /// </summary>
  public class CodeNthExpression : StatelessExpression {
    protected override string InitStringRepresentation() {
      return "CODE.NTH";
    }

    public override void Eval(IPushGpInterpreter interpreter) {
      if ((interpreter.CodeStack.Count == 0) || (interpreter.IntegerStack.Count == 0)) return;

      var n = interpreter.IntegerStack.Pop();
      var expression = interpreter.CodeStack.Top;

      Expression nthExpression = null;

      if (expression.GetType() == typeof(ExecExpandExpression)) {
        var subExpression = expression as ExecExpandExpression;

        if (subExpression.IsEmpty) {
          nthExpression = ExecExpandExpression.Empty;
        } else {
          var index = (int)(subExpression.Expressions.Count - 1 - Math.Abs(n % subExpression.Expressions.Count));

          nthExpression = subExpression.Expressions[index];
        }
      } else {
        nthExpression = expression;
      }

      interpreter.CodeStack.SetTop(nthExpression);
    }
  }

  /// <summary>
  ///     Pushes the nth "CDR" (in the Lisp sense) of the expression on top of the CODE stack (which is coerced to a list
  ///     first if necessary). If the expression is an empty list then the result is an empty list. N is taken from the
  ///     INTEGER
  ///     stack and is taken modulo the length of the expression into which it is indexing. A "CDR" of a list is the list
  ///     without
  ///     its first element.
  /// </summary>
  public class CodeNthCdrExpression : StatelessExpression {
    protected override string InitStringRepresentation() {
      return "CODE.NTHCDR";
    }

    public override void Eval(IPushGpInterpreter interpreter) {
      if ((interpreter.CodeStack.Count == 0) || (interpreter.IntegerStack.Count == 0)) return;

      var n = interpreter.IntegerStack.Pop();
      var expression = interpreter.CodeStack.Top;

      Expression nthExpression = null;

      if (expression.GetType() == typeof(ExecExpandExpression)) {
        var subExpressions = (expression as ExecExpandExpression).Expressions;

        if (subExpressions.Count < 2) {
          nthExpression = ExecExpandExpression.Empty;
        } else {
          var index = (int)(subExpressions.Count - 2 - Math.Abs(n % (subExpressions.Count - 1)));

          nthExpression = subExpressions[index];
        }
      } else {
        nthExpression = expression;
      }

      interpreter.CodeStack.SetTop(nthExpression);
    }
  }

  /// <summary>
  ///     Pushes TRUE onto the BOOLEAN stack if the top item of the CODE stack is an empty list, or FALSE otherwise.
  /// </summary>
  public class CodeNullExpression : StatelessExpression {
    protected override string InitStringRepresentation() {
      return "CODE.NULL";
    }

    public override void Eval(IPushGpInterpreter interpreter) {
      if (interpreter.CodeStack.Count == 0) return;

      var result = interpreter.CodeStack.Pop().Equals(ExecExpandExpression.Empty);

      interpreter.BooleanStack.Push(result);
    }
  }

  /// <summary>
  ///     Pushes onto the INTEGER stack the position of the second item on the CODE stack within the first item
  ///     (which is coerced to a list if necessary). Pushes -1 if no match is found.
  /// </summary>
  public class CodePositionExpression : StatelessExpression {
    protected override string InitStringRepresentation() {
      return "CODE.POSITION";
    }

    public override void Eval(IPushGpInterpreter interpreter) {
      if (interpreter.CodeStack.Count < 2) return;

      var expressions = interpreter.CodeStack.Pop(2);
      var first = expressions[1];
      var second = expressions[0];

      var position = -1;
      if (first.GetType() == typeof(ExecExpandExpression)) {
        var expand = first as ExecExpandExpression;
        position = expand.Expressions.Count - 1
                   - Array.FindIndex(expand.Expressions as Expression[], e => e.Equals(second));
      } else if (first.Equals(second)) {
        position = 0;
      }

      interpreter.IntegerStack.Push(position);
    }
  }

  /// <summary>
  ///     Pushes the number of "points" in the top piece of CODE onto the INTEGER stack. Each instruction, literal,
  ///     and pair of parentheses counts as a point.
  /// </summary>
  public class CodeSizeExpression : StatelessExpression {
    protected override string InitStringRepresentation() {
      return "CODE.SIZE";
    }

    public override void Eval(IPushGpInterpreter interpreter) {
      if (interpreter.CodeStack.Count == 0) return;

      var expression = interpreter.CodeStack.Pop();
      var points = expression.GetType() == typeof(ExecExpandExpression)
                     ? (expression as ExecExpandExpression).Expressions.Count
                     : 1;

      interpreter.IntegerStack.Push(points);
    }
  }

  /// <summary>
  ///     Pushes the result of substituting the third item on the code stack for the second item in the first item.
  ///     As of this writing this is implemented only in the Lisp implementation, within which it relies on the Lisp "subst"
  ///     function. As such, there are several problematic possibilities; for example "dotted-lists" can result in certain
  ///     cases with empty-list arguments. If any of these problematic possibilities occurs the stack is left unchanged.
  /// </summary>
  public class CodeSubstitutionExpression : StatelessExpression {
    protected override string InitStringRepresentation() {
      return "CODE.SUBST";
    }

    public override void Eval(IPushGpInterpreter interpreter) {
      if ((interpreter.CodeStack.Count < 3) || (interpreter.CodeStack.Top.GetType() != typeof(ExecExpandExpression))) return;

      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.Expressions.Count];

      for (var i = 0; i < first.Expressions.Count; i++)
        newExpressions[i] = first.Expressions[i].Equals(third)
                              ? second
                              /* no cloning needed here because first is removed and therefore newExpression is the
             only container of sub expressions */
                              : first.Expressions[i];

      var result = new ExecExpandExpression(newExpressions);

      interpreter.CodeStack.SetTop(result);
    }
  }
}