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

/// <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.Problems.ProgramSynthesis.Push.Expressions {
  using System;
  using System.Collections.Generic;
  using System.Linq;

  using HeuristicLab.Problems.ProgramSynthesis.Push.Attributes;
  using HeuristicLab.Problems.ProgramSynthesis.Push.Stack;

  using 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>
  [PushExpression(StackType.Code, "CODE.DO")]
  public class CodeDoExpression : StatelessExpression {
    public override bool Eval(IPushInterpreter interpreter) {
      // not enough arguments on stack
      if (interpreter.CodeStack.Count == 0) return false;

      var codePopExpression = ExpressionTable.GetStatelessExpression<CodePopExpression>();
      interpreter.ExecStack.Push(codePopExpression, interpreter.CodeStack.Top);

      return true;
    }
  }

  /// <summary>
  ///     Like CODE.DO but pops the stack before, rather than after, the recursive execution
  /// </summary>
  [PushExpression(StackType.Code, "CODE.DO*")]
  public class CodeDoXExpression : StatelessExpression {
    public override bool Eval(IPushInterpreter interpreter) {
      // not enough arguments on stack
      if (interpreter.CodeStack.Count == 0) return false;

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

      return true;
    }
  }

  /// <summary>
  ///     Does nothing.
  /// </summary>
  [PushExpression(StackType.Code, "CODE.NOOP")]
  public class CodeNoopExpression : StatelessExpression {
    public override bool Eval(IPushInterpreter interpreter) {
      return false;
    }
  }

  /// <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(StackType.Code, "CODE.QUOTE")]
  public class CodeQuoteExpression : StatelessExpression {
    public override bool Eval(IPushInterpreter interpreter) {
      // not enough arguments on stack
      if (interpreter.ExecStack.Count == 0) return false;

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

      return true;
    }
  }

  /// <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(StackType.Code, "CODE.IF")]
  public class CodeIfExpression : StatelessExpression {
    public override bool Eval(IPushInterpreter interpreter) {
      // not enough arguments on stack
      if ((interpreter.BooleanStack.Count == 0) || (interpreter.CodeStack.Count < 2)) return false;

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

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

      return true;
    }
  }

  /// <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(StackType.Code, "CODE.APPEND")]
  public class CodeAppendExpression : StatelessExpression {
    public override bool Eval(IPushInterpreter interpreter) {
      if (interpreter.CodeStack.Count < 2) return false;

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

      var isFirstList = first.IsProgram;
      var isSecondList = second.IsProgram;

      PushProgram result;

      if (isFirstList) {
        var program1 = first as PushProgram;

        if (isSecondList) {
          var program2 = second as PushProgram;
          var size = program2.Expressions.Count + program1.Expressions.Count;

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

          result = PushProgram.Merge(interpreter.PushProgramPool, program2, program1);
        } else {
          var size = program1.Expressions.Count + 1;

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

          result = PushProgram.Merge(interpreter.PushProgramPool, second, program1);
        }
      } else if (isSecondList) {
        var program2 = second as PushProgram;
        var size = program2.Expressions.Count + 1;

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

        result = PushProgram.Merge(interpreter.PushProgramPool, first, program2);
      } else {
        result = PushProgram.Create(interpreter.PushProgramPool, second, first);
      }

      interpreter.CodeStack.SetTop(result);

      return true;
    }
  }

  /// <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(StackType.Code, "CODE.ATOM")]
  public class CodeAtomExpression : StatelessExpression {
    public override bool Eval(IPushInterpreter interpreter) {
      if (interpreter.CodeStack.Count == 0) return false;

      var expression = interpreter.CodeStack.Pop();
      var isExpandExpression = expression.IsProgram;

      interpreter.BooleanStack.Push(!isExpandExpression);
      return true;
    }
  }

  /// <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(StackType.Code, "CODE.CAR")]
  public class CodeCarExpression : StatelessExpression {
    public override bool Eval(IPushInterpreter interpreter) {
      if ((interpreter.CodeStack.Count == 0) ||
          (interpreter.CodeStack.Top.GetType() != typeof(PushProgram))) return false;

      var expand = interpreter.CodeStack.Top as PushProgram;

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

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

  /// <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(StackType.Code, "CODE.CDR")]
  public class CodeCdrExpression : StatelessExpression {
    public override bool Eval(IPushInterpreter interpreter) {
      if (interpreter.CodeStack.Count == 0) return false;

      PushProgram result;
      var top = interpreter.CodeStack.Top;

      if (top.IsProgram) {
        var program = (PushProgram)top;

        if (program.IsEmpty) return false;

        result = program.Copy(interpreter.PushProgramPool, 0, program.Expressions.Count - 1);
      } else {
        result = PushProgram.Empty;
      }

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

  /// <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(StackType.Code, "CODE.CONS")]
  public class CodeConsExpression : StatelessExpression {
    public override bool Eval(IPushInterpreter interpreter) {
      if (interpreter.CodeStack.Count < 2)
        return false;

      PushProgram result;

      if (interpreter.CodeStack.Top.IsProgram) {
        var first = (PushProgram)interpreter.CodeStack.Pop();
        var size = first.Expressions.Count + 1;

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

        var expressions = new Expression[size];

        first.CopyExpressionsTo(expressions);
        expressions[first.Expressions.Count] = interpreter.CodeStack.Top;

        result = PushProgram.Create(interpreter.PushProgramPool, expressions);
      } else {
        result = PushProgram.Create(interpreter.PushProgramPool, interpreter.CodeStack.Top);
      }

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

  /// <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(StackType.Code, "CODE.CONTAINER")]
  public class CodeContainerExpression : StatelessExpression {
    public override bool Eval(IPushInterpreter interpreter) {
      if ((interpreter.CodeStack.Count < 2) ||
          (interpreter.CodeStack[interpreter.CodeStack.Count - 2].GetType() !=
           typeof(PushProgram))) return false;

      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);
      return true;
    }

    private static PushProgram GetContainer(PushProgram current, Expression target) {
      if (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(StackType.Code, "CODE.CONTAINS")]
  public class CodeContainsExpression : StatelessExpression {
    public override bool Eval(IPushInterpreter interpreter) {
      if (interpreter.CodeStack.Count < 2 ||
         !interpreter.CodeStack[interpreter.CodeStack.Count - 2].IsProgram)
        return false;

      var values = interpreter.CodeStack.Pop(2);
      var second = (PushProgram)values[0];
      var contains = second.Expressions.Contains(values[1]);

      interpreter.BooleanStack.Push(contains);

      return true;
    }
  }

  /// <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(StackType.Code, "CODE.DEFINITION")]
  public class CodeDefinitionExpression : StatelessExpression {
    public override bool Eval(IPushInterpreter interpreter) {
      if ((interpreter.NameStack.Count == 0) ||
          !interpreter.CustomExpressions.ContainsKey(interpreter.NameStack.Top)) return false;

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

      interpreter.CodeStack.Push(definition);

      return true;
    }
  }

  /// <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>
  [PushExpression(StackType.Code, "CODE.DISCREPANCY")]
  public class CodeDiscrepancyExpression : StatelessExpression {
    public override bool Eval(IPushInterpreter interpreter) {
      if (interpreter.CodeStack.Count < 2) return false;

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

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

      var discrepancy = GetDiscrepancy(firstItems, secondItems);

      interpreter.IntegerStack.Push(discrepancy);

      return true;
    }

    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(StackType.Code, "CODE.EXTRACT")]
  public class CodeExtractExpression : StatelessExpression {
    public override bool Eval(IPushInterpreter interpreter) {
      if (interpreter.IntegerStack.Count == 0 ||
          interpreter.CodeStack.Count == 0 ||
          !interpreter.CodeStack.Top.IsProgram)
        return false;

      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);

      return true;
    }
  }

  /// <summary>
  ///     Pops the BOOLEAN stack and pushes the popped item (TRUE or FALSE) onto the CODE stack.
  /// </summary>
  [PushExpression(StackType.Code, "CODE.FROMBOOLEAN")]
  public class CodeFromBooleanExpression : StatelessExpression {
    public override bool Eval(IPushInterpreter interpreter) {
      if (interpreter.BooleanStack.Count == 0) return false;

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

      interpreter.CodeStack.Push(expression);

      return true;
    }
  }

  /// <summary>
  ///     Pops the FLOAT stack and pushes the popped item onto the CODE stack.
  /// </summary>
  [PushExpression(StackType.Code, "CODE.FROMFLOAT")]
  public class CodeFromFloatExpression : StatelessExpression {
    public override bool Eval(IPushInterpreter interpreter) {
      if (interpreter.FloatStack.Count == 0) return false;

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

      interpreter.CodeStack.Push(expression);

      return true;
    }
  }

  /// <summary>
  ///     Pops the INTEGER stack and pushes the popped integer onto the CODE stack.
  /// </summary>
  [PushExpression(StackType.Code, "CODE.FROMINTEGER")]
  public class CodeFromIntegerExpression : StatelessExpression {
    public override bool Eval(IPushInterpreter interpreter) {
      if (interpreter.IntegerStack.Count == 0) return false;

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

      interpreter.CodeStack.Push(expression);

      return true;
    }
  }

  /// <summary>
  ///     Pops the NAME stack and pushes the popped item onto the CODE stack.
  /// </summary>
  [PushExpression(StackType.Code, "CODE.FROMNAME")]
  public class CodeFromNameExpression : StatelessExpression {
    public override bool Eval(IPushInterpreter interpreter) {
      if (interpreter.NameStack.Count == 0) return false;

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

      interpreter.CodeStack.Push(expression);

      return true;
    }
  }

  /// <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(StackType.Code, "CODE.CODEINSERT")]
  public class CodeInsertExpression : StatelessExpression {
    public override bool Eval(IPushInterpreter interpreter) {
      if (interpreter.IntegerStack.Count == 0 ||
          interpreter.CodeStack.Count < 2 ||
          !interpreter.CodeStack.Top.IsProgram)
        return false;

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

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

        newExpressions = target.CopyExpressions();
        newExpressions[index] = source.IsProgram
            ? ((PushProgram)source).Copy(interpreter.PushProgramPool)
            : source;
      } else {
        newExpressions = new[] { source };
      }

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

      return true;
    }
  }

  /// <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(StackType.Code, "CODE.LENGTH")]
  public class CodeLengthExpression : StatelessExpression {
    public override bool Eval(IPushInterpreter interpreter) {
      if (interpreter.CodeStack.Count == 0) return false;

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

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

      interpreter.IntegerStack.Push(count);

      return true;
    }
  }

  /// <summary>
  ///     Pushes a list of the top two items of the CODE stack onto the CODE stack.
  /// </summary>
  [PushExpression(StackType.Code, "CODE.LIST")]
  public class CodeListExpression : StatelessExpression {
    public override bool Eval(IPushInterpreter interpreter) {
      if (interpreter.CodeStack.Count < 2) return false;

      var first = interpreter.CodeStack.Pop();
      var second = interpreter.CodeStack.Top;
      var expandExpression = PushProgram.Create(interpreter.PushProgramPool, second, first);

      interpreter.CodeStack.SetTop(expandExpression);

      return true;
    }
  }

  /// <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(StackType.Code, "CODE.MEMBER")]
  public class CodeMemberExpression : StatelessExpression {
    public override bool Eval(IPushInterpreter interpreter) {
      if (interpreter.CodeStack.Count < 2) return false;

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

      var contains = expressions[1].IsProgram
          ? ((PushProgram)expressions[1]).Expressions.Contains(expressions[0])
          : expressions[1].Equals(expressions[0]);

      interpreter.BooleanStack.Push(contains);

      return true;
    }
  }

  /// <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(StackType.Code, "CODE.NTH")]
  public class CodeNthExpression : StatelessExpression {
    public override bool Eval(IPushInterpreter interpreter) {
      if ((interpreter.CodeStack.Count == 0) || (interpreter.IntegerStack.Count == 0)) return false;

      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);

      return true;
    }
  }

  /// <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(StackType.Code, "CODE.NTHCDR")]
  public class CodeNthCdrExpression : StatelessExpression {
    public override bool Eval(IPushInterpreter interpreter) {
      if ((interpreter.CodeStack.Count == 0) || (interpreter.IntegerStack.Count == 0)) return false;

      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);

      return true;
    }
  }

  /// <summary>
  ///     Pushes TRUE onto the BOOLEAN stack if the top item of the CODE stack is an empty list, or FALSE otherwise.
  /// </summary>
  [PushExpression(StackType.Code, "CODE.NULL")]
  public class CodeNullExpression : StatelessExpression {
    public override bool Eval(IPushInterpreter interpreter) {
      if (interpreter.CodeStack.Count == 0) return false;

      var result = interpreter.CodeStack.Pop().Equals(PushProgram.Empty);
      interpreter.BooleanStack.Push(result);

      return true;
    }
  }

  /// <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(StackType.Code, "CODE.POSITION")]
  public class CodePositionExpression : StatelessExpression {
    public override bool Eval(IPushInterpreter interpreter) {
      if (interpreter.CodeStack.Count < 2) return false;

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

      var position = -1;
      if (first.IsProgram) {
        var program = (PushProgram)first;
        position = program.Expressions.Count - 1 - program.IndexOf(second);
      } else if (first.Equals(second)) {
        position = 0;
      }

      interpreter.IntegerStack.Push(position);

      return true;
    }
  }

  /// <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(StackType.Code, "CODE.SIZE")]
  public class CodeSizeExpression : StatelessExpression {
    public override bool Eval(IPushInterpreter interpreter) {
      if (interpreter.CodeStack.Count == 0) return false;

      var expression = interpreter.CodeStack.Pop();
      var points = expression.IsProgram
          ? ((PushProgram)expression).Expressions.Count
          : 1;

      interpreter.IntegerStack.Push(points);

      return true;
    }
  }

  /// <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(StackType.Code, "CODE.SUBST")]
  public class CodeSubstitutionExpression : StatelessExpression {
    public override bool Eval(IPushInterpreter interpreter) {
      if ((interpreter.CodeStack.Count < 3) || (interpreter.CodeStack.Top.GetType() !=
                                                typeof(PushProgram))) return false;

      var expressions = interpreter.CodeStack.Pop(2);
      var third = interpreter.CodeStack.Top;
      var second = expressions[0];
      var first = expressions[1] as PushProgram;
      var firstExpressions = first.Expressions;
      var newExpressions = new Expression[firstExpressions.Count];

      for (var i = 0; i < firstExpressions.Count; i++)
        newExpressions[i] = 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];

      var result = PushProgram.Create(interpreter.PushProgramPool, newExpressions);

      interpreter.CodeStack.SetTop(result);

      return true;
    }
  }
}