source: addons/HeuristicLab.PushGP/HeuristicLab.Problems.ProgramSynthesis/Push/Expressions/CodeExpressions.cs

// 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.

namespace HeuristicLab.Problems.ProgramSynthesis.Push.Expressions {
  using System;
  using System.Collections.Generic;
  using System.Linq;
  using Attributes;

  using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
  using HeuristicLab.Problems.ProgramSynthesis.Push.Extensions;

  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",
    "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.",
    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*",
    "Like CODE.DO but pops the stack before, rather than after, the recursive execution.",
    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",
    "Does nothing.")]
  [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.
  /// </summary>
  [PushExpression(
    StackTypes.Code,
    "CODE.QUOTE",
    "Specifies that the next expression submitted for execution will instead be pushed literally onto the CODE stack.",
    StackTypes.Exec,
    requiredBlockCount: 1)]
  [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",
    "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",
    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",
    "Pushes the result of appending the top two pieces of code.")]
  [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.MaxProgramLength)
            return;
        } else if (firstProgram.Count + 1 > interpreter.Configuration.MaxProgramLength) return;
      } else if (second.IsProgram) {
        secondProgram = (PushProgram)second;

        if (secondProgram.Depth > interpreter.Configuration.MaxDepth
            || secondProgram.Count + 1 > interpreter.Configuration.MaxProgramLength) return;
      } else if (interpreter.Configuration.MaxProgramLength <= 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.Top = 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",
    "Pushes TRUE onto the BOOLEAN stack if the top piece of code is a single instruction or a literal, and FALSE otherwise",
    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", "Pushes the first item of the list on top of the CODE stack.")]
  [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.Top = 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",
    "Pushes a version of the list from the top of the CODE stack without its first element.")]
  [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.Top = 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",
    "Pushes the result of \"consing\" (in the Lisp sense) the second stack item onto the first stack item.")]
  [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.MaxProgramLength);
    }

    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.Top = 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",
    "Pushes the \"container\" of the second CODE stack item within the first CODE stack item onto the CODE stack")]
  [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.Top = 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",
    "Pushes TRUE on the BOOLEAN stack if the second CODE stack item contains the first CODE stack item anywhere.",
    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",
    "Pushes the definition associated with the top NAME on the NAME stack (if any) onto the CODE stack.",
    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",
    "Pushes a measure of the discrepancy between the top two CODE stack items onto the INTEGER stack",
    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",
    "Pushes the sub-expression of the top item of the CODE stack that is indexed by the top item of the INTEGER stack.",
    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 = interpreter.IntegerStack.Pop().AsInt(expression.TotalCount);
      var result = expression.GetFromTree(index);

      interpreter.CodeStack.Top = result;
    }
  }

  /// <summary>
  /// Pops the BOOLEAN stack and pushes the popped item (TRUE or FALSE) onto the CODE stack.
  /// </summary>
  [PushExpression(
    StackTypes.Code,
    "CODE.FROMBOOLEAN",
    "Pops the BOOLEAN stack and pushes the popped item(TRUE or FALSE) onto the CODE stack.",
    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 pool = interpreter.PoolContainer.GetStatefulExpressionPool<BooleanPushExpression>();
      var expression = BooleanPushExpression.Create(pool, 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",
    "Pops the FLOAT stack and pushes the popped item onto the CODE stack.",
    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 pool = interpreter.PoolContainer.GetStatefulExpressionPool<FloatPushExpression>();
      var expression = FloatPushExpression.Create(pool, 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",
    "Pops the INTEGER stack and pushes the popped integer onto the CODE stack.",
    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 pool = interpreter.PoolContainer.GetStatefulExpressionPool<IntegerPushExpression>();
      var expression = IntegerPushExpression.Create(pool, 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",
    "Pops the NAME stack and pushes the popped item onto the CODE stack.",
    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",
    "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.",
    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();

      IList<Expression> newExpressions;
      if (!target.IsEmpty) {
        var index = interpreter.IntegerStack.Pop().AsInt(target.Expressions.Count);
        index = target.Expressions.Count - 1 - index;
        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.Top = 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",
    "Pushes the length of the top item on the CODE stack onto the INTEGER stack.",
    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",
    "Pushes a list of the top two items of the CODE stack onto the CODE stack.")]
  [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.Top = 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",
    "Pushes TRUE onto the BOOLEAN stack if the second item of the CODE stack is a member of the first item, FALSE otherwise.",
    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",
    "Pushes the nth element, whereby n is taken from the INTEGER stack, of the expression on top of the CODE stack.",
    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 = (subExpression.Expressions.Count - 1 - n.AsInt(subExpression.Expressions.Count));

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

      interpreter.CodeStack.Top = 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",
    "Pushes the nth \"CDR\" (in the Lisp sense) of the expression on top of the CODE stack, whereby n is taken from the INTEGER stack.",
    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 = subExpressions.Count - 2 - n.AsInt(subExpressions.Count - 1);

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

      interpreter.CodeStack.Top = 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",
    "Pushes TRUE onto the BOOLEAN stack if the top item of the CODE stack is an empty list, or FALSE otherwise",
    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",
    "Pushes onto the INTEGER stack the position of the second item on the CODE stack within the first item. Pushes -1 if no match is found",
    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",
    "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.",
    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",
    "Pushes the result of substituting the third item on the code stack for the second item in the first item.")]
  [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.Top = result;
    }
  }
}