source: branches/GP.Symbols (TimeLag, Diff, Integral)/HeuristicLab.Problems.DataAnalysis/3.3/Symbolic/SimpleArithmeticExpressionInterpreter.cs @ 5026

Last change on this file since 5026 was 5026, checked in by mkommend, 11 years ago

Added branched projects for new GP symbols (ticket #1256).

File size: 11.3 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 2002-2010 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
4 *
5 * This file is part of HeuristicLab.
6 *
7 * HeuristicLab is free software: you can redistribute it and/or modify
8 * it under the terms of the GNU General Public License as published by
9 * the Free Software Foundation, either version 3 of the License, or
10 * (at your option) any later version.
11 *
12 * HeuristicLab is distributed in the hope that it will be useful,
13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
15 * GNU General Public License for more details.
16 *
17 * You should have received a copy of the GNU General Public License
18 * along with HeuristicLab. If not, see <http://www.gnu.org/licenses/>.
19 */
20#endregion
21
22using System;
23using System.Collections.Generic;
24using HeuristicLab.Common;
25using HeuristicLab.Core;
26using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;
27using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding.Compiler;
28using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding.Symbols;
29using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
30using HeuristicLab.Problems.DataAnalysis.Symbolic.Symbols;
31
32namespace HeuristicLab.Problems.DataAnalysis.Symbolic {
33  [StorableClass]
34  [Item("SimpleArithmeticExpressionInterpreter", "Interpreter for arithmetic symbolic expression trees including function calls.")]
35  // not thread safe!
36  public sealed class SimpleArithmeticExpressionInterpreter : NamedItem, ISymbolicExpressionTreeInterpreter {
37    private class OpCodes {
38      public const byte Add = 1;
39      public const byte Sub = 2;
40      public const byte Mul = 3;
41      public const byte Div = 4;
42
43      public const byte Sin = 5;
44      public const byte Cos = 6;
45      public const byte Tan = 7;
46
47      public const byte Log = 8;
48      public const byte Exp = 9;
49
50      public const byte IfThenElse = 10;
51
52      public const byte GT = 11;
53      public const byte LT = 12;
54
55      public const byte AND = 13;
56      public const byte OR = 14;
57      public const byte NOT = 15;
58
59
60      public const byte Average = 16;
61
62      public const byte Call = 17;
63
64      public const byte Variable = 18;
65      public const byte LagVariable = 19;
66      public const byte Constant = 20;
67      public const byte Arg = 21;
68
69      public const byte TimeLag = 22;
70    }
71
72    private Dictionary<Type, byte> symbolToOpcode = new Dictionary<Type, byte>() {
73      { typeof(Addition), OpCodes.Add },
74      { typeof(Subtraction), OpCodes.Sub },
75      { typeof(Multiplication), OpCodes.Mul },
76      { typeof(Division), OpCodes.Div },
77      { typeof(Sine), OpCodes.Sin },
78      { typeof(Cosine), OpCodes.Cos },
79      { typeof(Tangent), OpCodes.Tan },
80      { typeof(Logarithm), OpCodes.Log },
81      { typeof(Exponential), OpCodes.Exp },
82      { typeof(IfThenElse), OpCodes.IfThenElse },
83      { typeof(GreaterThan), OpCodes.GT },
84      { typeof(LessThan), OpCodes.LT },
85      { typeof(And), OpCodes.AND },
86      { typeof(Or), OpCodes.OR },
87      { typeof(Not), OpCodes.NOT},
88      { typeof(Average), OpCodes.Average},
89      { typeof(InvokeFunction), OpCodes.Call },
90      { typeof(HeuristicLab.Problems.DataAnalysis.Symbolic.Symbols.Variable), OpCodes.Variable },
91      { typeof(LaggedVariable), OpCodes.LagVariable },
92      { typeof(Constant), OpCodes.Constant },
93      { typeof(Argument), OpCodes.Arg },
94      { typeof(TimeLag), OpCodes.TimeLag},
95    };
96    private const int ARGUMENT_STACK_SIZE = 1024;
97
98    private Dataset dataset;
99    private int row;
100    private Instruction[] code;
101    private int pc;
102    private double[] argumentStack = new double[ARGUMENT_STACK_SIZE];
103    private int argStackPointer;
104
105    public override bool CanChangeName {
106      get { return false; }
107    }
108    public override bool CanChangeDescription {
109      get { return false; }
110    }
111
112    [StorableConstructor]
113    private SimpleArithmeticExpressionInterpreter(bool deserializing) : base(deserializing) { }
114    private SimpleArithmeticExpressionInterpreter(SimpleArithmeticExpressionInterpreter original, Cloner cloner) : base(original, cloner) { }
115
116    public override IDeepCloneable Clone(Cloner cloner) {
117      return new SimpleArithmeticExpressionInterpreter(this, cloner);
118    }
119
120    public SimpleArithmeticExpressionInterpreter()
121      : base() {
122    }
123
124    public IEnumerable<double> GetSymbolicExpressionTreeValues(SymbolicExpressionTree tree, Dataset dataset, IEnumerable<int> rows) {
125      this.dataset = dataset;
126      var compiler = new SymbolicExpressionTreeCompiler();
127      compiler.AddInstructionPostProcessingHook(PostProcessInstruction);
128      code = compiler.Compile(tree, MapSymbolToOpCode);
129      foreach (var row in rows) {
130        this.row = row;
131        pc = 0;
132        argStackPointer = 0;
133        yield return Evaluate();
134      }
135    }
136
137    private Instruction PostProcessInstruction(Instruction instr) {
138      if (instr.opCode == OpCodes.Variable) {
139        var variableTreeNode = instr.dynamicNode as VariableTreeNode;
140        instr.iArg0 = (ushort)dataset.GetVariableIndex(variableTreeNode.VariableName);
141      } else if (instr.opCode == OpCodes.LagVariable) {
142        var variableTreeNode = instr.dynamicNode as LaggedVariableTreeNode;
143        instr.iArg0 = (ushort)dataset.GetVariableIndex(variableTreeNode.VariableName);
144      }
145      return instr;
146    }
147
148    private byte MapSymbolToOpCode(SymbolicExpressionTreeNode treeNode) {
149      if (symbolToOpcode.ContainsKey(treeNode.Symbol.GetType()))
150        return symbolToOpcode[treeNode.Symbol.GetType()];
151      else
152        throw new NotSupportedException("Symbol: " + treeNode.Symbol);
153    }
154
155    private double Evaluate() {
156      Instruction currentInstr = code[pc++];
157      switch (currentInstr.opCode) {
158        case OpCodes.Add: {
159            double s = Evaluate();
160            for (int i = 1; i < currentInstr.nArguments; i++) {
161              s += Evaluate();
162            }
163            return s;
164          }
165        case OpCodes.Sub: {
166            double s = Evaluate();
167            for (int i = 1; i < currentInstr.nArguments; i++) {
168              s -= Evaluate();
169            }
170            if (currentInstr.nArguments == 1) s = -s;
171            return s;
172          }
173        case OpCodes.Mul: {
174            double p = Evaluate();
175            for (int i = 1; i < currentInstr.nArguments; i++) {
176              p *= Evaluate();
177            }
178            return p;
179          }
180        case OpCodes.Div: {
181            double p = Evaluate();
182            for (int i = 1; i < currentInstr.nArguments; i++) {
183              p /= Evaluate();
184            }
185            if (currentInstr.nArguments == 1) p = 1.0 / p;
186            return p;
187          }
188        case OpCodes.Average: {
189            double sum = Evaluate();
190            for (int i = 1; i < currentInstr.nArguments; i++) {
191              sum += Evaluate();
192            }
193            return sum / currentInstr.nArguments;
194          }
195        case OpCodes.Cos: {
196            return Math.Cos(Evaluate());
197          }
198        case OpCodes.Sin: {
199            return Math.Sin(Evaluate());
200          }
201        case OpCodes.Tan: {
202            return Math.Tan(Evaluate());
203          }
204        case OpCodes.Exp: {
205            return Math.Exp(Evaluate());
206          }
207        case OpCodes.Log: {
208            return Math.Log(Evaluate());
209          }
210        case OpCodes.IfThenElse: {
211            double condition = Evaluate();
212            double result;
213            if (condition > 0.0) {
214              result = Evaluate(); SkipBakedCode();
215            } else {
216              SkipBakedCode(); result = Evaluate();
217            }
218            return result;
219          }
220        case OpCodes.AND: {
221            double result = Evaluate();
222            for (int i = 1; i < currentInstr.nArguments; i++) {
223              if (result <= 0.0) SkipBakedCode();
224              else {
225                result = Evaluate();
226              }
227            }
228            return result <= 0.0 ? -1.0 : 1.0;
229          }
230        case OpCodes.OR: {
231            double result = Evaluate();
232            for (int i = 1; i < currentInstr.nArguments; i++) {
233              if (result > 0.0) SkipBakedCode();
234              else {
235                result = Evaluate();
236              }
237            }
238            return result > 0.0 ? 1.0 : -1.0;
239          }
240        case OpCodes.NOT: {
241            return -Evaluate();
242          }
243        case OpCodes.GT: {
244            double x = Evaluate();
245            double y = Evaluate();
246            if (x > y) return 1.0;
247            else return -1.0;
248          }
249        case OpCodes.LT: {
250            double x = Evaluate();
251            double y = Evaluate();
252            if (x < y) return 1.0;
253            else return -1.0;
254          }
255        case OpCodes.Call: {
256            // evaluate sub-trees
257            // push on argStack in reverse order
258            for (int i = 0; i < currentInstr.nArguments; i++) {
259              argumentStack[argStackPointer + currentInstr.nArguments - i] = Evaluate();
260            }
261            argStackPointer += currentInstr.nArguments;
262
263            // save the pc
264            int nextPc = pc;
265            // set pc to start of function 
266            pc = currentInstr.iArg0;
267            // evaluate the function
268            double v = Evaluate();
269
270            // decrease the argument stack pointer by the number of arguments pushed
271            // to set the argStackPointer back to the original location
272            argStackPointer -= currentInstr.nArguments;
273
274            // restore the pc => evaluation will continue at point after my subtrees 
275            pc = nextPc;
276            return v;
277          }
278        case OpCodes.Arg: {
279            return argumentStack[argStackPointer - currentInstr.iArg0];
280          }
281        case OpCodes.Variable: {
282            var variableTreeNode = currentInstr.dynamicNode as VariableTreeNode;
283            return dataset[row, currentInstr.iArg0] * variableTreeNode.Weight;
284          }
285        case OpCodes.LagVariable: {
286            var lagVariableTreeNode = currentInstr.dynamicNode as LaggedVariableTreeNode;
287            int actualRow = row + lagVariableTreeNode.Lag;
288            if (actualRow < 0 || actualRow >= dataset.Rows) throw new ArgumentException("Out of range access to dataset row: " + row);
289            return dataset[actualRow, currentInstr.iArg0] * lagVariableTreeNode.Weight;
290          }
291        case OpCodes.Constant: {
292            var constTreeNode = currentInstr.dynamicNode as ConstantTreeNode;
293            return constTreeNode.Value;
294          }
295        case OpCodes.TimeLag: {
296            var timeLagTreeNode = (LaggedTreeNode)currentInstr.dynamicNode;
297            row += timeLagTreeNode.Lag;
298            if (row < 0 || row >= dataset.Rows) {
299              row -= timeLagTreeNode.Lag;
300              return double.NaN;
301            }
302            double result = Evaluate();
303            row -= timeLagTreeNode.Lag;
304            return result;
305          }
306        default: throw new NotSupportedException();
307      }
308    }
309
310    // skips a whole branch
311    private void SkipBakedCode() {
312      int i = 1;
313      while (i > 0) {
314        i += code[pc++].nArguments;
315        i--;
316      }
317    }
318  }
319}
Note: See TracBrowser for help on using the repository browser.