Free cookie consent management tool by TermsFeed Policy Generator

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

Last change on this file since 14744 was 14744, checked in by pkimmesw, 7 years ago

#2665 Renamings due to typos, ManagedPool tests, Skip Noops in Debugger

File size: 30.5 KB
Line 
1/// <summary>
2/// For explicit code manipulation and execution. May also be used as a general list data type.
3/// This type must always be present, as the top level interpreter will push any code to be executed on the
4/// CODE stack prior to execution. However, one may turn off all CODE instructions if code manipulation is not needed.
5/// </summary>
6
7namespace HeuristicLab.Problems.ProgramSynthesis.Push.Expressions {
8  using System;
9  using System.Collections.Generic;
10  using System.Linq;
11
12  using HeuristicLab.Problems.ProgramSynthesis.Push.Attributes;
13  using HeuristicLab.Problems.ProgramSynthesis.Push.Stack;
14
15  using Interpreter;
16
17  /// <summary>
18  ///     Recursively invokes the interpreter on the program on top of the CODE stack. After evaluation the
19  ///     CODE stack is popped; normally this pops the program that was just executed, but if the expression itself
20  ///     manipulates the stack then this final pop may end up popping something else.
21  /// </summary>
22  [PushExpression(StackType.Code, "CODE.DO")]
23  public class CodeDoExpression : StatelessExpression {
24    public override bool Eval(IPushInterpreter interpreter) {
25      // not enough arguments on stack
26      if (interpreter.CodeStack.Count == 0) return false;
27
28      var codePopExpression = ExpressionTable.GetStatelessExpression<CodePopExpression>();
29      interpreter.ExecStack.Push(codePopExpression, interpreter.CodeStack.Top);
30
31      return true;
32    }
33  }
34
35  /// <summary>
36  ///     Like CODE.DO but pops the stack before, rather than after, the recursive execution
37  /// </summary>
38  [PushExpression(StackType.Code, "CODE.DO*")]
39  public class CodeDoXExpression : StatelessExpression {
40    public override bool Eval(IPushInterpreter interpreter) {
41      // not enough arguments on stack
42      if (interpreter.CodeStack.Count == 0) return false;
43
44      var expression = interpreter.CodeStack.Pop();
45      interpreter.ExecStack.Push(expression);
46
47      return true;
48    }
49  }
50
51  /// <summary>
52  ///     Does nothing.
53  /// </summary>
54  [PushExpression(StackType.Code, "CODE.NOOP")]
55  public class CodeNoopExpression : StatelessExpression {
56    public override bool Eval(IPushInterpreter interpreter) {
57      return false;
58    }
59  }
60
61  /// <summary>
62  ///     Specifies that the next expression submitted for execution will instead be pushed literally onto the CODE stack.
63  ///     This can be implemented by moving the top item on the EXEC stack onto the CODE stack.
64  /// </summary>
65  [PushExpression(StackType.Code, "CODE.QUOTE")]
66  public class CodeQuoteExpression : StatelessExpression {
67    public override bool Eval(IPushInterpreter interpreter) {
68      // not enough arguments on stack
69      if (interpreter.ExecStack.Count == 0) return false;
70
71      var expression = interpreter.ExecStack.Pop();
72      interpreter.CodeStack.Push(expression);
73
74      return true;
75    }
76  }
77
78  /// <summary>
79  ///     If the top item of the BOOLEAN stack is TRUE this recursively executes the second item of the CODE stack;
80  ///     otherwise it recursively executes the first item of the CODE stack. Either way both elements of the CODE stack
81  ///     (and the BOOLEAN value upon which the decision was made) are popped.
82  /// </summary>
83  [PushExpression(StackType.Code, "CODE.IF")]
84  public class CodeIfExpression : StatelessExpression {
85    public override bool Eval(IPushInterpreter interpreter) {
86      // not enough arguments on stack
87      if ((interpreter.BooleanStack.Count == 0) || (interpreter.CodeStack.Count < 2)) return false;
88
89      var condition = interpreter.BooleanStack.Pop();
90      var items = interpreter.CodeStack.Pop(2);
91
92      interpreter.ExecStack.Push(condition ? items[0] : items[1]);
93
94      return true;
95    }
96  }
97
98  /// <summary>
99  ///     Pushes the result of appending the top two pieces of code. If one of the pieces of code is a single instruction or
100  ///     literal (that is, something not surrounded by parentheses) then it is surrounded by parentheses first.
101  /// </summary>
102  [PushExpression(StackType.Code, "CODE.APPEND")]
103  public class CodeAppendExpression : StatelessExpression {
104    public override bool Eval(IPushInterpreter interpreter) {
105      if (interpreter.CodeStack.Count < 2) return false;
106
107      var first = interpreter.CodeStack.Pop();
108      var second = interpreter.CodeStack.Top;
109
110      var isFirstList = first.CanExpand;
111      var isSecondList = second.CanExpand;
112
113      Expression[] result = null;
114
115      if (isFirstList) {
116        var expand1 = first as ExecExpandExpression;
117
118        if (isSecondList) {
119          var expand2 = second as ExecExpandExpression;
120          var size = expand2.State.Expressions.Count + expand1.State.Expressions.Count;
121
122          // if size > maxPointsInProgram this expressions results in a NOOP
123          if (size > interpreter.Configuration.MaxPointsInProgram) return false;
124
125          result = new Expression[size];
126
127          Array.Copy(expand2.State.Expressions as Expression[], result, expand2.State.Expressions.Count);
128          Array.Copy(
129              expand1.State.Expressions as Expression[],
130              0,
131              result,
132              expand2.State.Expressions.Count,
133              expand1.State.Expressions.Count);
134        } else {
135          var size = expand1.State.Expressions.Count + 1;
136
137          // if size > maxPointsInProgram this expressions results in a NOOP
138          if (size > interpreter.Configuration.MaxPointsInProgram) return false;
139
140          result = new Expression[size];
141          result[0] = second;
142
143          Array.Copy(expand1.State.Expressions as Expression[], 0, result, 1, expand1.State.Expressions.Count);
144        }
145      } else if (isSecondList) {
146        var expand2 = second as ExecExpandExpression;
147
148        var size = expand2.State.Expressions.Count + 1;
149
150        // if size > maxPointsInProgram this expressions results in a NOOP
151        if (size > interpreter.Configuration.MaxPointsInProgram) return false;
152
153        result = new Expression[size];
154        result[0] = first;
155
156        Array.Copy(expand2.State.Expressions as Expression[], 0, result, 1, expand2.State.Expressions.Count);
157      } else {
158        result = new[] { second, first };
159      }
160
161      var expression = new ExecExpandExpression(result);
162
163      interpreter.CodeStack.SetTop(expression);
164
165      return true;
166    }
167  }
168
169  /// <summary>
170  ///     Pushes TRUE onto the BOOLEAN stack if the top piece of code is a single instruction or a literal,
171  ///     and FALSE otherwise (that is, if it is something surrounded by parentheses).
172  /// </summary>
173  [PushExpression(StackType.Code, "CODE.ATOM")]
174  public class CodeAtomExpression : StatelessExpression {
175    public override bool Eval(IPushInterpreter interpreter) {
176      if (interpreter.CodeStack.Count == 0) return false;
177
178      var expression = interpreter.CodeStack.Pop();
179      var isExpandExpression = expression.CanExpand;
180
181      interpreter.BooleanStack.Push(!isExpandExpression);
182      return true;
183    }
184  }
185
186  /// <summary>
187  ///     Pushes the first item of the list on top of the CODE stack. For example, if the top piece of code is "( A B )"
188  ///     then this pushes "A" (after popping the argument). If the code on top of the stack is not a list then this has no
189  ///     effect.
190  ///     The name derives from the similar Lisp function; a more generic name would be "FIRST".
191  /// </summary>
192  [PushExpression(StackType.Code, "CODE.CAR")]
193  public class CodeCarExpression : StatelessExpression {
194    public override bool Eval(IPushInterpreter interpreter) {
195      if ((interpreter.CodeStack.Count == 0) ||
196          (interpreter.CodeStack.Top.GetType() != typeof(ExecExpandExpression))) return false;
197
198      var expand = interpreter.CodeStack.Top as ExecExpandExpression;
199
200      if (expand.State.IsEmpty) return false;
201      var first = expand.State.Expressions[expand.State.Expressions.Count - 1];
202
203      interpreter.CodeStack.SetTop(first);
204      return true;
205    }
206  }
207
208  /// <summary>
209  ///     Pushes a version of the list from the top of the CODE stack without its first element.
210  ///     For example, if the top piece of code is "( A B )" then this pushes "( B )" (after popping the argument).
211  ///     If the code on top of the stack is not a list then this pushes the empty list ("( )"). The name derives from
212  ///     the similar Lisp function; a more generic name would be "REST".
213  /// </summary>
214  [PushExpression(StackType.Code, "CODE.CDR")]
215  public class CodeCdrExpression : StatelessExpression {
216    public override bool Eval(IPushInterpreter interpreter) {
217      if (interpreter.CodeStack.Count == 0) return false;
218
219      ExecExpandExpression expandExpression;
220      var top = interpreter.CodeStack.Top;
221
222      if (top.CanExpand) {
223        var expand = (ExecExpandExpression)top;
224
225        if (expand.State.IsEmpty) return false;
226        var length = expand.State.Expressions.Count - 1;
227        var newExpressions = new Expression[length];
228
229        Array.Copy((Expression[])expand.State.Expressions, 0, newExpressions, 0, length);
230
231        expandExpression = new ExecExpandExpression(newExpressions);
232      } else {
233        expandExpression = ExecExpandExpression.Empty;
234      }
235
236      interpreter.CodeStack.SetTop(expandExpression);
237      return true;
238    }
239  }
240
241  /// <summary>
242  ///     Pushes the result of "consing" (in the Lisp sense) the second stack item onto the first stack item
243  ///     (which is coerced to a list if necessary). For example, if the top piece of code is "( A B )" and the
244  ///     second piece of code is "X" then this pushes "( X A B )" (after popping the argument).
245  /// </summary>
246  [PushExpression(StackType.Code, "CODE.CONS")]
247  public class CodeConsExpression : StatelessExpression {
248    public override bool Eval(IPushInterpreter interpreter) {
249      if (interpreter.CodeStack.Count < 2)
250        return false;
251
252      ExecExpandExpression result;
253
254      if (interpreter.CodeStack.Top.CanExpand) {
255        var first = (ExecExpandExpression)interpreter.CodeStack.Pop();
256        var size = first.State.Expressions.Count + 1;
257
258        if (size > interpreter.Configuration.MaxPointsInProgram) return false;
259
260        var expressions = new Expression[size];
261
262        expressions[first.State.Expressions.Count] = interpreter.CodeStack.Top;
263        Array.Copy(first.State.Expressions as Expression[], expressions, first.State.Expressions.Count);
264
265        result = new ExecExpandExpression(expressions);
266      } else {
267        result = new ExecExpandExpression(interpreter.CodeStack.Pop(), interpreter.CodeStack.Top);
268      }
269
270      interpreter.CodeStack.SetTop(result);
271      return true;
272    }
273  }
274
275  /// <summary>
276  ///     Pushes the "container" of the second CODE stack item within the first CODE stack item onto the CODE stack.
277  ///     If second item contains the first anywhere (i.e. in any nested list) then the container is the smallest sub-list
278  ///     that contains but is not equal to the first instance. For example, if the top piece of code is "( B ( C ( A ) ) ( D
279  ///     ( A ) ) )"
280  ///     and the second piece of code is "( A )" then this pushes ( C ( A ) ). Pushes an empty list if there is no such
281  ///     container.
282  /// </summary>
283  [PushExpression(StackType.Code, "CODE.CONTAINER")]
284  public class CodeContainerExpression : StatelessExpression {
285    public override bool Eval(IPushInterpreter interpreter) {
286      if ((interpreter.CodeStack.Count < 2) ||
287          (interpreter.CodeStack[interpreter.CodeStack.Count - 2].GetType() !=
288           typeof(ExecExpandExpression))) return false;
289
290      var target = interpreter.CodeStack.Pop();
291      var source = interpreter.CodeStack.Top;
292
293      var container = GetContainer(source as ExecExpandExpression, target);
294      var result = container ?? ExecExpandExpression.Empty;
295
296      interpreter.CodeStack.SetTop(result);
297      return true;
298    }
299
300    private static ExecExpandExpression GetContainer(ExecExpandExpression current, Expression target) {
301      if (current == target)
302        return null;
303
304      var subContainer =
305          current.State.Expressions.Where(e => e.CanExpand)
306              .Select(e => GetContainer(e as ExecExpandExpression, target))
307              .Where(e => e != null);
308
309      var execExpandExpressions = subContainer as IList<ExecExpandExpression> ?? subContainer.ToList();
310      return execExpandExpressions.Any()
311          ? execExpandExpressions.OrderBy(c => c.State.Expressions.Count).LastOrDefault()
312          : current.State.Expressions.Contains(target)
313              ? current
314              : null;
315    }
316  }
317
318  /// <summary>
319  ///     Pushes TRUE on the BOOLEAN stack if the second CODE stack item contains the first CODE stack
320  ///     item anywhere (e.g. in a sub-list).
321  /// </summary>
322  [PushExpression(StackType.Code, "CODE.CONTAINS")]
323  public class CodeContainsExpression : StatelessExpression {
324    public override bool Eval(IPushInterpreter interpreter) {
325      if (interpreter.CodeStack.Count < 2 ||
326         !interpreter.CodeStack[interpreter.CodeStack.Count - 2].CanExpand)
327        return false;
328
329      var values = interpreter.CodeStack.Pop(2);
330      var second = (ExecExpandExpression)values[0];
331      var contains = second.State.Expressions.Contains(values[1]);
332
333      interpreter.BooleanStack.Push(contains);
334
335      return true;
336    }
337  }
338
339  /// <summary>
340  ///     Pushes the definition associated with the top NAME on the NAME stack (if any) onto the CODE stack.
341  ///     This extracts the definition for inspection/manipulation, rather than for immediate execution (although it
342  ///     may then be executed with a call to CODE.DO or a similar instruction).
343  /// </summary>
344  [PushExpression(StackType.Code, "CODE.DEFINITION")]
345  public class CodeDefinitionExpression : StatelessExpression {
346    public override bool Eval(IPushInterpreter interpreter) {
347      if ((interpreter.NameStack.Count == 0) ||
348          !interpreter.CustomExpressions.ContainsKey(interpreter.NameStack.Top)) return false;
349
350      var name = interpreter.NameStack.Pop();
351      var definition = interpreter.CustomExpressions[name];
352
353      interpreter.CodeStack.Push(definition);
354
355      return true;
356    }
357  }
358
359  /// <summary>
360  ///     Pushes a measure of the discrepancy between the top two CODE stack items onto the INTEGER stack. This will be zero
361  ///     if the top two items are equivalent, and will be higher the 'more different' the items are from one another. The calculation
362  ///     is as follows:
363  ///     <list type="bullet">
364  ///         <item>
365  ///             <description>
366  ///                 Construct a list of all of the unique items in both of the lists(where uniqueness is determined by equalp).
367  ///                 Sub-lists and atoms all count as items.
368  ///         </item>
369  ///         <item>
370  ///             <description>Initialize the result to zero.
371  ///         </item>
372  ///         <item>
373  ///             <description>
374  ///                 For each unique item increment the result by the difference between the number of occurrences of the
375  ///                 item in the two pieces of code.
376  ///         </item>
377  ///         <item>
378  ///             <description>Push the result.
379  ///         </item>
380  ///     </list>
381  /// </summary>
382  [PushExpression(StackType.Code, "CODE.DISCREPANCY")]
383  public class CodeDiscrepancyExpression : StatelessExpression {
384    public override bool Eval(IPushInterpreter interpreter) {
385      if (interpreter.CodeStack.Count < 2) return false;
386
387      var expressions = interpreter.CodeStack.Pop(2);
388      var firstItems = new Dictionary<int, int>();
389      var secondItems = new Dictionary<int, int>();
390
391      DetermineUniqueItems(expressions[0], secondItems);
392      DetermineUniqueItems(expressions[1], firstItems);
393
394      var discrepancy = GetDiscrepancy(firstItems, secondItems);
395
396      interpreter.IntegerStack.Push(discrepancy);
397
398      return true;
399    }
400
401    private int GetDiscrepancy(IDictionary<int, int> first, IDictionary<int, int> second) {
402      var discrepancy = 0;
403      var keys = first.Keys.Concat(second.Keys).Distinct();
404
405      foreach (var key in keys)
406        if (first.ContainsKey(key) && second.ContainsKey(key))
407          discrepancy += Math.Abs(first[key] - second[key]);
408        else if (first.ContainsKey(key)) discrepancy += first[key];
409        else discrepancy += second[key];
410
411      return discrepancy;
412    }
413
414    private void DetermineUniqueItems(Expression source, IDictionary<int, int> items) {
415      if (source.CanExpand) {
416        var expand = source as ExecExpandExpression;
417
418        foreach (var e in expand.State.Expressions) {
419          var id = e.GetHashCode();
420          if (!items.ContainsKey(id)) items.Add(id, 1);
421          else items[id]++;
422        }
423      } else {
424        items.Add(source.GetHashCode(), 1);
425      }
426    }
427  }
428
429  /// <summary>
430  ///     Pushes the sub-expression of the top item of the CODE stack that is indexed by the top item of the INTEGER stack.
431  ///     The indexing here counts "points," where each parenthesized expression and each literal/instruction is considered a
432  ///     point,
433  ///     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
434  ///     in the list
435  ///     is at index 1, etc. The integer used as the index is taken modulo the number of points in the overall expression
436  ///     (and its
437  ///     absolute value is taken in case it is negative) to ensure that it is within the meaningful range.
438  /// </summary>
439  [PushExpression(StackType.Code, "CODE.EXTRACT")]
440  public class CodeExtractExpression : StatelessExpression {
441    public override bool Eval(IPushInterpreter interpreter) {
442      if (interpreter.IntegerStack.Count == 0 ||
443          interpreter.CodeStack.Count == 0 ||
444          !interpreter.CodeStack.Top.CanExpand)
445        return false;
446
447      var expression = (ExecExpandExpression)interpreter.CodeStack.Top;
448      var index = (int)Math.Abs(interpreter.IntegerStack.Pop() % expression.State.TotalCount);
449      var result = expression.GetFromTree(index);
450
451      interpreter.CodeStack.SetTop(result);
452
453      return true;
454    }
455  }
456
457  /// <summary>
458  ///     Pops the BOOLEAN stack and pushes the popped item (TRUE or FALSE) onto the CODE stack.
459  /// </summary>
460  [PushExpression(StackType.Code, "CODE.FROMBOOLEAN")]
461  public class CodeFromBooleanExpression : StatelessExpression {
462    public override bool Eval(IPushInterpreter interpreter) {
463      if (interpreter.BooleanStack.Count == 0) return false;
464
465      var value = interpreter.BooleanStack.Pop();
466      var expression = new BooleanPushExpression(value);
467
468      interpreter.CodeStack.Push(expression);
469
470      return true;
471    }
472  }
473
474  /// <summary>
475  ///     Pops the FLOAT stack and pushes the popped item onto the CODE stack.
476  /// </summary>
477  [PushExpression(StackType.Code, "CODE.FROMFLOAT")]
478  public class CodeFromFloatExpression : StatelessExpression {
479    public override bool Eval(IPushInterpreter interpreter) {
480      if (interpreter.FloatStack.Count == 0) return false;
481
482      var value = interpreter.FloatStack.Pop();
483      var expression = new FloatPushExpression(value);
484
485      interpreter.CodeStack.Push(expression);
486
487      return true;
488    }
489  }
490
491  /// <summary>
492  ///     Pops the INTEGER stack and pushes the popped integer onto the CODE stack.
493  /// </summary>
494  [PushExpression(StackType.Code, "CODE.FROMINTEGER")]
495  public class CodeFromIntegerExpression : StatelessExpression {
496    public override bool Eval(IPushInterpreter interpreter) {
497      if (interpreter.IntegerStack.Count == 0) return false;
498
499      var value = interpreter.IntegerStack.Pop();
500      var expression = new IntegerPushExpression(value);
501
502      interpreter.CodeStack.Push(expression);
503
504      return true;
505    }
506  }
507
508  /// <summary>
509  ///     Pops the NAME stack and pushes the popped item onto the CODE stack.
510  /// </summary>
511  [PushExpression(StackType.Code, "CODE.FROMNAME")]
512  public class CodeFromNameExpression : StatelessExpression {
513    public override bool Eval(IPushInterpreter interpreter) {
514      if (interpreter.NameStack.Count == 0) return false;
515
516      var value = interpreter.NameStack.Pop();
517      var expression = new NameDefineXExecExpression(value);
518
519      interpreter.CodeStack.Push(expression);
520
521      return true;
522    }
523  }
524
525  /// <summary>
526  ///     Pushes the result of inserting the second item of the CODE stack into the first item, at the position indexed
527  ///     by the top item of the INTEGER stack (and replacing whatever was there formerly).
528  /// </summary>
529  [PushExpression(StackType.Code, "CODE.CODEINSERT")]
530  public class CodeInsertExpression : StatelessExpression {
531    public override bool Eval(IPushInterpreter interpreter) {
532      if (interpreter.IntegerStack.Count == 0 ||
533          interpreter.CodeStack.Count < 2 ||
534          !interpreter.CodeStack.Top.CanExpand)
535        return false;
536
537      var source = interpreter.CodeStack[interpreter.CodeStack.Count - 2];
538      var target = (ExecExpandExpression)interpreter.CodeStack.Pop();
539      var index = (int)interpreter.IntegerStack.Pop();
540
541      Expression[] newExpressions;
542      if (target.State.Expressions.Count > 0) {
543        index = target.State.Expressions.Count - 1 - Math.Abs(index % target.State.Expressions.Count);
544
545        newExpressions = target.State.CopyExpressions();
546        newExpressions[index] = source.CanExpand
547            ? ((ExecExpandExpression)source).Copy()
548            : source;
549      } else {
550        newExpressions = new[] { source };
551      }
552
553      var result = new ExecExpandExpression(newExpressions);
554      interpreter.CodeStack.SetTop(result);
555
556      return true;
557    }
558  }
559
560  /// <summary>
561  ///     Pushes the length of the top item on the CODE stack onto the INTEGER stack.
562  ///     If the top item is not a list then this pushes a 1. If the top item is a list then this pushes the
563  ///     number of items in the top level of the list; that is, nested lists contribute only 1 to this count, no
564  ///     matter what they contain.
565  /// </summary>
566  [PushExpression(StackType.Code, "CODE.LENGTH")]
567  public class CodeLengthExpression : StatelessExpression {
568    public override bool Eval(IPushInterpreter interpreter) {
569      if (interpreter.CodeStack.Count == 0) return false;
570
571      var expression = interpreter.CodeStack.Pop();
572      var count = 1;
573
574      if (expression.CanExpand)
575        count = ((ExecExpandExpression)expression).State.Expressions.Count;
576
577      interpreter.IntegerStack.Push(count);
578
579      return true;
580    }
581  }
582
583  /// <summary>
584  ///     Pushes a list of the top two items of the CODE stack onto the CODE stack.
585  /// </summary>
586  [PushExpression(StackType.Code, "CODE.LIST")]
587  public class CodeListExpression : StatelessExpression {
588    public override bool Eval(IPushInterpreter interpreter) {
589      if (interpreter.CodeStack.Count < 2) return false;
590
591      var first = interpreter.CodeStack.Pop();
592      var second = interpreter.CodeStack.Top;
593      var expandExpression = new ExecExpandExpression(second, first);
594
595      interpreter.CodeStack.SetTop(expandExpression);
596
597      return true;
598    }
599  }
600
601  /// <summary>
602  ///     Pushes TRUE onto the BOOLEAN stack if the second item of the CODE stack is a member of the first item
603  ///     (which is coerced to a list if necessary). Pushes FALSE onto the BOOLEAN stack otherwise.
604  /// </summary>
605  [PushExpression(StackType.Code, "CODE.MEMBER")]
606  public class CodeMemberExpression : StatelessExpression {
607    public override bool Eval(IPushInterpreter interpreter) {
608      if (interpreter.CodeStack.Count < 2) return false;
609
610      var expressions = interpreter.CodeStack.Pop(2);
611
612      var contains = expressions[1].CanExpand
613          ? ((ExecExpandExpression)expressions[1]).State.Expressions.Contains(expressions[0])
614          : expressions[1].Equals(expressions[0]);
615
616      interpreter.BooleanStack.Push(contains);
617
618      return true;
619    }
620  }
621
622  /// <summary>
623  ///     Pushes the nth element of the expression on top of the CODE stack (which is coerced to a list first if necessary).
624  ///     If the expression is an empty list then the result is an empty list. N is taken from the INTEGER stack and is taken
625  ///     modulo the length of the expression into which it is indexing.
626  /// </summary>
627  [PushExpression(StackType.Code, "CODE.NTH")]
628  public class CodeNthExpression : StatelessExpression {
629    public override bool Eval(IPushInterpreter interpreter) {
630      if ((interpreter.CodeStack.Count == 0) || (interpreter.IntegerStack.Count == 0)) return false;
631
632      var n = interpreter.IntegerStack.Pop();
633      var expression = interpreter.CodeStack.Top;
634
635      Expression nthExpression;
636
637      if (expression.CanExpand) {
638        var subExpression = (ExecExpandExpression)expression;
639
640        if (subExpression.State.IsEmpty) {
641          nthExpression = ExecExpandExpression.Empty;
642        } else {
643          var index = (int)(subExpression.State.Expressions.Count - 1 -
644                             Math.Abs(n % subExpression.State.Expressions.Count));
645
646          nthExpression = subExpression.State.Expressions[index];
647        }
648      } else {
649        nthExpression = expression;
650      }
651
652      interpreter.CodeStack.SetTop(nthExpression);
653
654      return true;
655    }
656  }
657
658  /// <summary>
659  ///     Pushes the nth "CDR" (in the Lisp sense) of the expression on top of the CODE stack (which is coerced to a list
660  ///     first if necessary). If the expression is an empty list then the result is an empty list. N is taken from the
661  ///     INTEGER
662  ///     stack and is taken modulo the length of the expression into which it is indexing. A "CDR" of a list is the list
663  ///     without
664  ///     its first element.
665  /// </summary>
666  [PushExpression(StackType.Code, "CODE.NTHCDR")]
667  public class CodeNthCdrExpression : StatelessExpression {
668    public override bool Eval(IPushInterpreter interpreter) {
669      if ((interpreter.CodeStack.Count == 0) || (interpreter.IntegerStack.Count == 0)) return false;
670
671      var n = interpreter.IntegerStack.Pop();
672      var expression = interpreter.CodeStack.Top;
673
674      Expression nthExpression = null;
675
676      if (expression.CanExpand) {
677        var subExpressions = ((ExecExpandExpression)expression).State.Expressions;
678
679        if (subExpressions.Count < 2) {
680          nthExpression = ExecExpandExpression.Empty;
681        } else {
682          var index = (int)(subExpressions.Count - 2 - Math.Abs(n % (subExpressions.Count - 1)));
683
684          nthExpression = subExpressions[index];
685        }
686      } else {
687        nthExpression = expression;
688      }
689
690      interpreter.CodeStack.SetTop(nthExpression);
691
692      return true;
693    }
694  }
695
696  /// <summary>
697  ///     Pushes TRUE onto the BOOLEAN stack if the top item of the CODE stack is an empty list, or FALSE otherwise.
698  /// </summary>
699  [PushExpression(StackType.Code, "CODE.NULL")]
700  public class CodeNullExpression : StatelessExpression {
701    public override bool Eval(IPushInterpreter interpreter) {
702      if (interpreter.CodeStack.Count == 0) return false;
703
704      var result = interpreter.CodeStack.Pop().Equals(ExecExpandExpression.Empty);
705      interpreter.BooleanStack.Push(result);
706
707      return true;
708    }
709  }
710
711  /// <summary>
712  ///     Pushes onto the INTEGER stack the position of the second item on the CODE stack within the first item
713  ///     (which is coerced to a list if necessary). Pushes -1 if no match is found.
714  /// </summary>
715  [PushExpression(StackType.Code, "CODE.POSITION")]
716  public class CodePositionExpression : StatelessExpression {
717    public override bool Eval(IPushInterpreter interpreter) {
718      if (interpreter.CodeStack.Count < 2) return false;
719
720      var expressions = interpreter.CodeStack.Pop(2);
721      var first = expressions[1];
722      var second = expressions[0];
723
724      var position = -1;
725      if (first.CanExpand) {
726        var expand = (ExecExpandExpression)first;
727        position = expand.State.Expressions.Count - 1
728                   - Array.FindIndex((Expression[])expand.State.Expressions, e => e.Equals(second));
729      } else if (first.Equals(second)) {
730        position = 0;
731      }
732
733      interpreter.IntegerStack.Push(position);
734
735      return true;
736    }
737  }
738
739  /// <summary>
740  ///     Pushes the number of "points" in the top piece of CODE onto the INTEGER stack. Each instruction, literal,
741  ///     and pair of parentheses counts as a point.
742  /// </summary>
743  [PushExpression(StackType.Code, "CODE.SIZE")]
744  public class CodeSizeExpression : StatelessExpression {
745    public override bool Eval(IPushInterpreter interpreter) {
746      if (interpreter.CodeStack.Count == 0) return false;
747
748      var expression = interpreter.CodeStack.Pop();
749      var points = expression.CanExpand
750          ? ((ExecExpandExpression)expression).State.Expressions.Count
751          : 1;
752
753      interpreter.IntegerStack.Push(points);
754
755      return true;
756    }
757  }
758
759  /// <summary>
760  ///     Pushes the result of substituting the third item on the code stack for the second item in the first item.
761  ///     As of this writing this is implemented only in the Lisp implementation, within which it relies on the Lisp "subst"
762  ///     function. As such, there are several problematic possibilities; for example "dotted-lists" can result in certain
763  ///     cases with empty-list arguments. If any of these problematic possibilities occurs the stack is left unchanged.
764  /// </summary>
765  [PushExpression(StackType.Code, "CODE.SUBST")]
766  public class CodeSubstitutionExpression : StatelessExpression {
767    public override bool Eval(IPushInterpreter interpreter) {
768      if ((interpreter.CodeStack.Count < 3) || (interpreter.CodeStack.Top.GetType() !=
769                                                typeof(ExecExpandExpression))) return false;
770
771      var expressions = interpreter.CodeStack.Pop(2);
772      var third = interpreter.CodeStack.Top;
773      var second = expressions[0];
774      var first = expressions[1] as ExecExpandExpression;
775      var newExpressions = new Expression[first.State.Expressions.Count];
776
777      for (var i = 0; i < first.State.Expressions.Count; i++)
778        newExpressions[i] = first.State.Expressions[i].Equals(third)
779            ? second
780            /* no cloning needed here because first is removed and therefore newExpression is the only container of sub expressions */
781            : first.State.Expressions[i];
782
783      var result = new ExecExpandExpression(newExpressions);
784
785      interpreter.CodeStack.SetTop(result);
786
787      return true;
788    }
789  }
790}
Note: See TracBrowser for help on using the repository browser.