source: branches/PushGP/HeuristicLab.PushGP/HeuristicLab.Problems.ProgramSynthesis/Push/Expressions/CodeExpressions.cs @ 14952

/// <summary>
/// For explicit code manipulation and execution. May also be used as a general list data types.
/// This types 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.Problems.ProgramSynthesis.Push.Expressions {
  using System;
  using System.Collections.Generic;
  using System.Linq;
  using Attributes;

  using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;

  using Interpreter;
  using Stack;

  /// <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>
  [PushExpression(StackTypes.Code, "CODE.DO", StackTypes.Exec)]
  [StorableClass]
  public class CodeDoExpression : StatelessExpression {
    public CodeDoExpression() { }
    [StorableConstructor]
    public CodeDoExpression(bool deserializing) : base(deserializing) { }

    public override bool IsNoop(IInternalPushInterpreter interpreter) {
      return interpreter.CodeStack.IsEmpty;
    }

    public override void Eval(IInternalPushInterpreter interpreter) {
      var codePopExpression = ExpressionTable.GetStatelessExpression<CodePopExpression>();
      interpreter.ExecStack.Push(codePopExpression, interpreter.CodeStack.Top);
    }
  }

  /// <summary>
  ///     Like CODE.DO but pops the stack before, rather than after, the recursive execution
  /// </summary>
  [PushExpression(StackTypes.Code, "CODE.DO*", StackTypes.Exec)]
  [StorableClass]
  public class CodeDoXExpression : StatelessExpression {
    public CodeDoXExpression() { }
    [StorableConstructor]
    public CodeDoXExpression(bool deserializing) : base(deserializing) { }

    public override bool IsNoop(IInternalPushInterpreter interpreter) {
      return interpreter.CodeStack.IsEmpty;
    }

    public override void Eval(IInternalPushInterpreter interpreter) {
      var expression = interpreter.CodeStack.Pop();
      interpreter.ExecStack.Push(expression);
    }
  }

  /// <summary>
  ///     Does nothing.
  /// </summary>
  [PushExpression(StackTypes.Code, "CODE.NOOP")]
  [StorableClass]
  public class CodeNoopExpression : StatelessExpression {
    public CodeNoopExpression() { }
    [StorableConstructor]
    public CodeNoopExpression(bool deserializing) : base(deserializing) { }

    public override bool IsNoop(IInternalPushInterpreter interpreter) {
      return true;
    }

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

  /// <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>
  [PushExpression(StackTypes.Code, "CODE.QUOTE", StackTypes.Exec)]
  [StorableClass]
  public class CodeQuoteExpression : StatelessExpression {
    public CodeQuoteExpression() { }
    [StorableConstructor]
    public CodeQuoteExpression(bool deserializing) : base(deserializing) { }

    public override bool IsNoop(IInternalPushInterpreter interpreter) {
      return interpreter.ExecStack.IsEmpty;
    }

    public override void Eval(IInternalPushInterpreter interpreter) {
      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>
  [PushExpression(StackTypes.Code, "CODE.IF", StackTypes.Exec | StackTypes.Boolean)]
  [StorableClass]
  public class CodeIfExpression : StatelessExpression {
    public CodeIfExpression() { }
    [StorableConstructor]
    public CodeIfExpression(bool deserializing) : base(deserializing) { }

    public override bool IsNoop(IInternalPushInterpreter interpreter) {
      return interpreter.BooleanStack.IsEmpty || interpreter.CodeStack.Count < 2;
    }

    public override void Eval(IInternalPushInterpreter interpreter) {
      var condition = interpreter.BooleanStack.Pop();
      var first = interpreter.CodeStack[1];
      var second = interpreter.CodeStack.Top;

      interpreter.CodeStack.Remove(2);
      interpreter.ExecStack.Push(condition ? first : second);
    }
  }

  /// <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>
  [PushExpression(StackTypes.Code, "CODE.APPEND")]
  [StorableClass]
  public class CodeAppendExpression : StatelessExpression {
    public CodeAppendExpression() { }
    [StorableConstructor]
    public CodeAppendExpression(bool deserializing) : base(deserializing) { }

    public override bool IsNoop(IInternalPushInterpreter interpreter) {
      return interpreter.CodeStack.Count < 2;
    }

    public override void Eval(IInternalPushInterpreter interpreter) {
      var first = interpreter.CodeStack.Top;
      var second = interpreter.CodeStack[1];

      PushProgram firstProgram = null;
      PushProgram secondProgram = null;

      if (first.IsProgram) {
        firstProgram = (PushProgram)first;

        if (firstProgram.Depth > interpreter.Configuration.MaxDepth) return;

        if (second.IsProgram) {
          secondProgram = (PushProgram)second;

          if (secondProgram.Depth > interpreter.Configuration.MaxDepth ||
              firstProgram.Count + secondProgram.Count > interpreter.Configuration.MaxPointsInProgram)
            return;
        } else if (firstProgram.Count + 1 > interpreter.Configuration.MaxPointsInProgram) return;
      } else if (second.IsProgram) {
        secondProgram = (PushProgram)second;

        if (secondProgram.Depth > interpreter.Configuration.MaxDepth
            || secondProgram.Count + 1 > interpreter.Configuration.MaxPointsInProgram) return;
      } else if (interpreter.Configuration.MaxPointsInProgram <= 2) {
        return;
      }

      interpreter.CodeStack.Pop();

      PushProgram result;

      if (firstProgram != null) {
        result = secondProgram != null
          ? PushProgram.Merge(interpreter.PoolContainer.PushProgramPool, interpreter.PoolContainer.ExpressionListPool, secondProgram, firstProgram)
          : PushProgram.Merge(interpreter.PoolContainer.PushProgramPool, interpreter.PoolContainer.ExpressionListPool, second, firstProgram);
      } else if (secondProgram != null) {
        result = PushProgram.Merge(interpreter.PoolContainer.PushProgramPool, interpreter.PoolContainer.ExpressionListPool, first, secondProgram);
      } else {
        var expressions = interpreter.PoolContainer.ExpressionListPool.Get();
        expressions.Add(second);
        expressions.Add(first);

        result = PushProgram.Create(interpreter.PoolContainer.PushProgramPool, expressions);
      }

      interpreter.CodeStack.SetTop(result);
    }
  }

  /// <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>
  [PushExpression(StackTypes.Code, "CODE.ATOM", StackTypes.Boolean)]
  [StorableClass]
  public class CodeAtomExpression : StatelessExpression {
    public CodeAtomExpression() { }
    [StorableConstructor]
    public CodeAtomExpression(bool deserializing) : base(deserializing) { }

    public override bool IsNoop(IInternalPushInterpreter interpreter) {
      return interpreter.CodeStack.IsEmpty;
    }

    public override void Eval(IInternalPushInterpreter interpreter) {
      var expression = interpreter.CodeStack.Pop();
      var isExpandExpression = expression.IsProgram;

      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>
  [PushExpression(StackTypes.Code, "CODE.CAR")]
  [StorableClass]
  public class CodeCarExpression : StatelessExpression {
    public CodeCarExpression() { }
    [StorableConstructor]
    public CodeCarExpression(bool deserializing) : base(deserializing) { }

    public override bool IsNoop(IInternalPushInterpreter interpreter) {
      return interpreter.CodeStack.IsEmpty ||
            !interpreter.CodeStack.Top.IsProgram ||
            ((PushProgram)interpreter.CodeStack.Top).IsEmpty;
    }

    public override void Eval(IInternalPushInterpreter interpreter) {
      var expand = (PushProgram)interpreter.CodeStack.Top;
      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>
  [PushExpression(StackTypes.Code, "CODE.CDR")]
  [StorableClass]
  public class CodeCdrExpression : StatelessExpression {
    public CodeCdrExpression() { }
    [StorableConstructor]
    public CodeCdrExpression(bool deserializing) : base(deserializing) { }

    public override bool IsNoop(IInternalPushInterpreter interpreter) {
      return interpreter.CodeStack.IsEmpty ||
             (interpreter.CodeStack.Top.IsProgram && ((PushProgram)interpreter.CodeStack.Top).IsEmpty);
    }

    public override void Eval(IInternalPushInterpreter interpreter) {
      PushProgram result;
      var top = interpreter.CodeStack.Top;

      if (top.IsProgram) {
        var program = (PushProgram)top;
        var expressions = program.CopyExpressions(interpreter.PoolContainer.ExpressionListPool);
        expressions.RemoveAt(expressions.Count - 1);

        result = PushProgram.Create(interpreter.PoolContainer.PushProgramPool, expressions as IReadOnlyList<Expression>);
      } else result = PushProgram.Empty;


      interpreter.CodeStack.SetTop(result);
    }
  }

  /// <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>
  [PushExpression(StackTypes.Code, "CODE.CONS")]
  [StorableClass]
  public class CodeConsExpression : StatelessExpression {
    public CodeConsExpression() { }
    [StorableConstructor]
    public CodeConsExpression(bool deserializing) : base(deserializing) { }

    public override bool IsNoop(IInternalPushInterpreter interpreter) {
      return interpreter.CodeStack.Count < 2 ||
            (interpreter.CodeStack.Top.IsProgram &&
            ((PushProgram)interpreter.CodeStack.Top).Expressions.Count + 1 > interpreter.Configuration.MaxPointsInProgram);
    }

    public override void Eval(IInternalPushInterpreter interpreter) {
      var expressions = interpreter.PoolContainer.ExpressionListPool.Get();
      var first = interpreter.CodeStack.Pop();

      if (first.IsProgram) {
        expressions.AddRange(((PushProgram)first).Expressions);
      } else {
        expressions.Add(first);
      }

      expressions.Add(interpreter.CodeStack.Top);
      var result = PushProgram.Create(interpreter.PoolContainer.PushProgramPool, 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>
  [PushExpression(StackTypes.Code, "CODE.CONTAINER")]
  [StorableClass]
  public class CodeContainerExpression : StatelessExpression {
    public CodeContainerExpression() { }
    [StorableConstructor]
    public CodeContainerExpression(bool deserializing) : base(deserializing) { }

    public override bool IsNoop(IInternalPushInterpreter interpreter) {
      return (interpreter.CodeStack.Count < 2) ||
             (interpreter.CodeStack[1].GetType() != typeof(PushProgram));
    }

    public override void Eval(IInternalPushInterpreter interpreter) {
      var target = interpreter.CodeStack.Pop();
      var source = interpreter.CodeStack.Top;

      var container = GetContainer(source as PushProgram, target);
      var result = container ?? PushProgram.Empty;

      interpreter.CodeStack.SetTop(result);
    }

    private static PushProgram GetContainer(PushProgram current, Expression target) {
      if (Equals(current, target))
        return null;

      var subContainer =
          current.Expressions.Where(e => e.IsProgram)
              .Select(e => GetContainer(e as PushProgram, target))
              .Where(e => e != null);

      var execExpandExpressions = subContainer as IList<PushProgram> ?? subContainer.ToList();
      return execExpandExpressions.Any()
          ? execExpandExpressions.OrderBy(c => c.Expressions.Count).LastOrDefault()
          : 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>
  [PushExpression(StackTypes.Code, "CODE.CONTAINS", StackTypes.Boolean)]
  [StorableClass]
  public class CodeContainsExpression : StatelessExpression {
    public CodeContainsExpression() { }
    [StorableConstructor]
    public CodeContainsExpression(bool deserializing) : base(deserializing) { }

    public override bool IsNoop(IInternalPushInterpreter interpreter) {
      return interpreter.CodeStack.Count < 2 || !interpreter.CodeStack[1].IsProgram;
    }

    public override void Eval(IInternalPushInterpreter interpreter) {
      var second = (PushProgram)interpreter.CodeStack[1];
      var first = interpreter.CodeStack.Top;
      interpreter.CodeStack.Remove(2);

      var contains = second.Expressions.Contains(first);
      interpreter.BooleanStack.Push(contains);
    }
  }

  /// <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>
  [PushExpression(StackTypes.Code, "CODE.DEFINITION", StackTypes.Name)]
  [StorableClass]
  public class CodeDefinitionExpression : StatelessExpression {
    public CodeDefinitionExpression() { }
    [StorableConstructor]
    public CodeDefinitionExpression(bool deserializing) : base(deserializing) { }

    public override bool IsNoop(IInternalPushInterpreter interpreter) {
      return interpreter.NameStack.IsEmpty ||
            !interpreter.CustomExpressions.ContainsKey(interpreter.NameStack.Top);
    }

    public override void Eval(IInternalPushInterpreter interpreter) {
      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 types="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.
  ///             </description>
  ///         </item>
  ///         <item>
  ///             <description>Initialize the result to zero.</description>
  ///         </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.
  ///             </description>
  ///         </item>
  ///         <item>
  ///             <description>Push the result.</description>
  ///         </item>
  ///     </list>
  /// </summary>
  [PushExpression(StackTypes.Code, "CODE.DISCREPANCY", StackTypes.Integer)]
  [StorableClass]
  public class CodeDiscrepancyExpression : StatelessExpression {
    public CodeDiscrepancyExpression() { }
    [StorableConstructor]
    public CodeDiscrepancyExpression(bool deserializing) : base(deserializing) { }

    public override bool IsNoop(IInternalPushInterpreter interpreter) {
      return interpreter.CodeStack.Count < 2;
    }

    public override void Eval(IInternalPushInterpreter interpreter) {
      var second = interpreter.CodeStack[1];
      var first = interpreter.CodeStack.Top;
      interpreter.CodeStack.Remove(2);

      var firstItems = new Dictionary<int, int>();
      var secondItems = new Dictionary<int, int>();

      DetermineUniqueItems(second, secondItems);
      DetermineUniqueItems(first, firstItems);

      var discrepancy = 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.IsProgram) {
        var program = source as PushProgram;
        var expressions = program.Expressions;

        for (var i = 0; i < expressions.Count; i++) {
          var id = expressions[i].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>
  [PushExpression(StackTypes.Code, "CODE.EXTRACT", StackTypes.Integer)]
  [StorableClass]
  public class CodeExtractExpression : StatelessExpression {
    public CodeExtractExpression() { }
    [StorableConstructor]
    public CodeExtractExpression(bool deserializing) : base(deserializing) { }

    public override bool IsNoop(IInternalPushInterpreter interpreter) {
      return interpreter.IntegerStack.IsEmpty ||
             interpreter.CodeStack.IsEmpty ||
            !interpreter.CodeStack.Top.IsProgram;
    }

    public override void Eval(IInternalPushInterpreter interpreter) {
      var expression = (PushProgram)interpreter.CodeStack.Top;
      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>
  [PushExpression(StackTypes.Code, "CODE.FROMBOOLEAN", StackTypes.Boolean)]
  [StorableClass]
  public class CodeFromBooleanExpression : StatelessExpression {
    public CodeFromBooleanExpression() { }
    [StorableConstructor]
    public CodeFromBooleanExpression(bool deserializing) : base(deserializing) { }

    public override bool IsNoop(IInternalPushInterpreter interpreter) {
      return interpreter.BooleanStack.IsEmpty;
    }

    public override void Eval(IInternalPushInterpreter interpreter) {
      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>
  [PushExpression(StackTypes.Code, "CODE.FROMFLOAT", StackTypes.Float)]
  [StorableClass]
  public class CodeFromFloatExpression : StatelessExpression {
    public CodeFromFloatExpression() { }
    [StorableConstructor]
    public CodeFromFloatExpression(bool deserializing) : base(deserializing) { }

    public override bool IsNoop(IInternalPushInterpreter interpreter) {
      return interpreter.FloatStack.IsEmpty;
    }

    public override void Eval(IInternalPushInterpreter interpreter) {
      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>
  [PushExpression(StackTypes.Code, "CODE.FROMINTEGER", StackTypes.Integer)]
  [StorableClass]
  public class CodeFromIntegerExpression : StatelessExpression {
    public CodeFromIntegerExpression() { }
    [StorableConstructor]
    public CodeFromIntegerExpression(bool deserializing) : base(deserializing) { }

    public override bool IsNoop(IInternalPushInterpreter interpreter) {
      return interpreter.IntegerStack.IsEmpty;
    }

    public override void Eval(IInternalPushInterpreter interpreter) {
      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>
  [PushExpression(StackTypes.Code, "CODE.FROMNAME", StackTypes.Name)]
  [StorableClass]
  public class CodeFromNameExpression : StatelessExpression {
    public CodeFromNameExpression() { }
    [StorableConstructor]
    public CodeFromNameExpression(bool deserializing) : base(deserializing) { }

    public override bool IsNoop(IInternalPushInterpreter interpreter) {
      return interpreter.NameStack.IsEmpty;
    }

    public override void Eval(IInternalPushInterpreter interpreter) {
      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>
  [PushExpression(StackTypes.Code, "CODE.CODEINSERT", StackTypes.Integer)]
  [StorableClass]
  public class CodeInsertExpression : StatelessExpression {
    public CodeInsertExpression() { }
    [StorableConstructor]
    public CodeInsertExpression(bool deserializing) : base(deserializing) { }

    public override bool IsNoop(IInternalPushInterpreter interpreter) {
      return interpreter.IntegerStack.IsEmpty ||
             interpreter.CodeStack.Count < 2 ||
            !interpreter.CodeStack.Top.IsProgram;
    }

    public override void Eval(IInternalPushInterpreter interpreter) {
      var source = interpreter.CodeStack[1];
      var target = (PushProgram)interpreter.CodeStack.Pop();
      var index = (int)interpreter.IntegerStack.Pop();

      IList<Expression> newExpressions;
      if (!target.IsEmpty) {
        index = target.Expressions.Count - 1 - Math.Abs(index % target.Expressions.Count);
        newExpressions = target.CopyExpressions(interpreter.PoolContainer.ExpressionListPool);

        newExpressions[index] = source.IsProgram
            ? ((PushProgram)source).Copy(interpreter.PoolContainer.PushProgramPool)
            : source;
      } else {
        newExpressions = interpreter.PoolContainer.ExpressionListPool.Get();
        newExpressions.Add(source);
      }

      var result = PushProgram.Create(interpreter.PoolContainer.PushProgramPool, newExpressions as IReadOnlyList<Expression>);
      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>
  [PushExpression(StackTypes.Code, "CODE.LENGTH", StackTypes.Integer)]
  [StorableClass]
  public class CodeLengthExpression : StatelessExpression {
    public CodeLengthExpression() { }
    [StorableConstructor]
    public CodeLengthExpression(bool deserializing) : base(deserializing) { }

    public override bool IsNoop(IInternalPushInterpreter interpreter) {
      return interpreter.CodeStack.IsEmpty;
    }

    public override void Eval(IInternalPushInterpreter interpreter) {
      var expression = interpreter.CodeStack.Pop();
      var count = 1;

      if (expression.IsProgram)
        count = ((PushProgram)expression).Expressions.Count;

      interpreter.IntegerStack.Push(count);
    }
  }

  /// <summary>
  ///     Pushes a list of the top two items of the CODE stack onto the CODE stack.
  /// </summary>
  [PushExpression(StackTypes.Code, "CODE.LIST")]
  [StorableClass]
  public class CodeListExpression : StatelessExpression {
    public CodeListExpression() { }
    [StorableConstructor]
    public CodeListExpression(bool deserializing) : base(deserializing) { }

    public override bool IsNoop(IInternalPushInterpreter interpreter) {
      return interpreter.CodeStack.Count < 2 ||
            (interpreter.CodeStack.Top.IsProgram && ((PushProgram)interpreter.CodeStack.Top).Depth == interpreter.Configuration.MaxDepth) ||
            (interpreter.CodeStack[1].IsProgram && ((PushProgram)interpreter.CodeStack[1]).Depth == interpreter.Configuration.MaxDepth);
    }

    public override void Eval(IInternalPushInterpreter interpreter) {
      var first = interpreter.CodeStack.Pop();
      var second = interpreter.CodeStack.Top;

      var expressions = interpreter.PoolContainer.ExpressionListPool.Get();
      expressions.Add(second);
      expressions.Add(first);

      var expandExpression = PushProgram.Create(interpreter.PoolContainer.PushProgramPool, expressions);
      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>
  [PushExpression(StackTypes.Code, "CODE.MEMBER", StackTypes.Boolean)]
  [StorableClass]
  public class CodeMemberExpression : StatelessExpression {
    public CodeMemberExpression() { }
    [StorableConstructor]
    public CodeMemberExpression(bool deserializing) : base(deserializing) { }

    public override bool IsNoop(IInternalPushInterpreter interpreter) {
      return interpreter.CodeStack.Count < 2;
    }

    public override void Eval(IInternalPushInterpreter interpreter) {
      var first = interpreter.CodeStack[1];
      var second = interpreter.CodeStack.Top;
      interpreter.CodeStack.Remove(2);

      var contains = second.IsProgram
          ? ((PushProgram)second).Expressions.Contains(first)
          : second.Equals(first);

      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>
  [PushExpression(StackTypes.Code, "CODE.NTH", StackTypes.Integer)]
  [StorableClass]
  public class CodeNthExpression : StatelessExpression {
    public CodeNthExpression() { }
    [StorableConstructor]
    public CodeNthExpression(bool deserializing) : base(deserializing) { }

    public override bool IsNoop(IInternalPushInterpreter interpreter) {
      return interpreter.CodeStack.IsEmpty || interpreter.IntegerStack.IsEmpty;
    }

    public override void Eval(IInternalPushInterpreter interpreter) {
      var n = interpreter.IntegerStack.Pop();
      var expression = interpreter.CodeStack.Top;

      Expression nthExpression;

      if (expression.IsProgram) {
        var subExpression = (PushProgram)expression;

        if (subExpression.IsEmpty) {
          nthExpression = PushProgram.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>
  [PushExpression(StackTypes.Code, "CODE.NTHCDR", StackTypes.Integer)]
  [StorableClass]
  public class CodeNthCdrExpression : StatelessExpression {
    public CodeNthCdrExpression() { }
    [StorableConstructor]
    public CodeNthCdrExpression(bool deserializing) : base(deserializing) { }

    public override bool IsNoop(IInternalPushInterpreter interpreter) {
      return interpreter.CodeStack.IsEmpty || interpreter.IntegerStack.IsEmpty;
    }

    public override void Eval(IInternalPushInterpreter interpreter) {
      var n = interpreter.IntegerStack.Pop();
      var expression = interpreter.CodeStack.Top;

      Expression nthExpression;

      if (expression.IsProgram) {
        var subExpressions = ((PushProgram)expression).Expressions;

        if (subExpressions.Count < 2) {
          nthExpression = PushProgram.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>
  [PushExpression(StackTypes.Code, "CODE.NULL", StackTypes.Boolean)]
  [StorableClass]
  public class CodeNullExpression : StatelessExpression {
    public CodeNullExpression() { }
    [StorableConstructor]
    public CodeNullExpression(bool deserializing) : base(deserializing) { }

    public override bool IsNoop(IInternalPushInterpreter interpreter) {
      return interpreter.CodeStack.IsEmpty;
    }

    public override void Eval(IInternalPushInterpreter interpreter) {
      var top = interpreter.CodeStack.Pop();
      var result = top.IsProgram && ((PushProgram)top).IsEmpty;
      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>
  [PushExpression(StackTypes.Code, "CODE.POSITION", StackTypes.Integer)]
  [StorableClass]
  public class CodePositionExpression : StatelessExpression {
    public CodePositionExpression() { }
    [StorableConstructor]
    public CodePositionExpression(bool deserializing) : base(deserializing) { }

    public override bool IsNoop(IInternalPushInterpreter interpreter) {
      return interpreter.CodeStack.Count < 2;
    }

    public override void Eval(IInternalPushInterpreter interpreter) {
      var second = interpreter.CodeStack[1];
      var first = interpreter.CodeStack.Top;
      interpreter.CodeStack.Remove(2);

      var position = -1;
      if (first.IsProgram) {
        var program = (PushProgram)first;
        position = program.IndexOf(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>
  [PushExpression(StackTypes.Code, "CODE.SIZE", StackTypes.Integer)]
  [StorableClass]
  public class CodeSizeExpression : StatelessExpression {
    public CodeSizeExpression() { }
    [StorableConstructor]
    public CodeSizeExpression(bool deserializing) : base(deserializing) { }

    public override bool IsNoop(IInternalPushInterpreter interpreter) {
      return interpreter.CodeStack.IsEmpty;
    }

    public override void Eval(IInternalPushInterpreter interpreter) {
      var expression = interpreter.CodeStack.Pop();
      var points = expression.IsProgram
          ? ((PushProgram)expression).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>
  [PushExpression(StackTypes.Code, "CODE.SUBST")]
  [StorableClass]
  public class CodeSubstitutionExpression : StatelessExpression {
    public CodeSubstitutionExpression() { }
    [StorableConstructor]
    public CodeSubstitutionExpression(bool deserializing) : base(deserializing) { }

    public override bool IsNoop(IInternalPushInterpreter interpreter) {
      return (interpreter.CodeStack.Count < 3) ||
             (interpreter.CodeStack.Top.GetType() != typeof(PushProgram));
    }

    public override void Eval(IInternalPushInterpreter interpreter) {
      var third = interpreter.CodeStack[2];
      var second = interpreter.CodeStack[1];
      var first = interpreter.CodeStack.Top as PushProgram;
      interpreter.CodeStack.Remove(2);

      var firstExpressions = first.Expressions;
      var newExpressions = interpreter.PoolContainer.ExpressionListPool.Get();

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

        newExpressions.Add(expression);
      }

      var result = PushProgram.Create(interpreter.PoolContainer.PushProgramPool, newExpressions);
      interpreter.CodeStack.SetTop(result);
    }
  }
}