Free cookie consent management tool by TermsFeed Policy Generator

source: branches/DataAnalysis.PopulationDiversityAnalysis/HeuristicLab.Problems.DataAnalysis/3.3/Symbolic/SimpleArithmeticExpressionInterpreter.cs @ 14544

Last change on this file since 14544 was 4951, checked in by swinkler, 14 years ago

Branched DataAnalysis plugin into DataAnalysis.PopulationDiversity branch. (#1278)

File size: 10.8 KB
RevLine 
[4951]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
70    private Dictionary<Type, byte> symbolToOpcode = new Dictionary<Type, byte>() {
71      { typeof(Addition), OpCodes.Add },
72      { typeof(Subtraction), OpCodes.Sub },
73      { typeof(Multiplication), OpCodes.Mul },
74      { typeof(Division), OpCodes.Div },
75      { typeof(Sine), OpCodes.Sin },
76      { typeof(Cosine), OpCodes.Cos },
77      { typeof(Tangent), OpCodes.Tan },
78      { typeof(Logarithm), OpCodes.Log },
79      { typeof(Exponential), OpCodes.Exp },
80      { typeof(IfThenElse), OpCodes.IfThenElse },
81      { typeof(GreaterThan), OpCodes.GT },
82      { typeof(LessThan), OpCodes.LT },
83      { typeof(And), OpCodes.AND },
84      { typeof(Or), OpCodes.OR },
85      { typeof(Not), OpCodes.NOT},
86      { typeof(Average), OpCodes.Average},
87      { typeof(InvokeFunction), OpCodes.Call },
88      { typeof(HeuristicLab.Problems.DataAnalysis.Symbolic.Symbols.Variable), OpCodes.Variable },
89      { typeof(LaggedVariable), OpCodes.LagVariable },
90      { typeof(Constant), OpCodes.Constant },
91      { typeof(Argument), OpCodes.Arg },
92    };
93    private const int ARGUMENT_STACK_SIZE = 1024;
94
95    private Dataset dataset;
96    private int row;
97    private Instruction[] code;
98    private int pc;
99    private double[] argumentStack = new double[ARGUMENT_STACK_SIZE];
100    private int argStackPointer;
101
102    public override bool CanChangeName {
103      get { return false; }
104    }
105    public override bool CanChangeDescription {
106      get { return false; }
107    }
108
109    [StorableConstructor]
110    private SimpleArithmeticExpressionInterpreter(bool deserializing) : base(deserializing) { }
111    private SimpleArithmeticExpressionInterpreter(SimpleArithmeticExpressionInterpreter original, Cloner cloner) : base(original, cloner) { }
112
113    public override IDeepCloneable Clone(Cloner cloner) {
114      return new SimpleArithmeticExpressionInterpreter(this, cloner);
115    }
116
117    public SimpleArithmeticExpressionInterpreter()
118      : base() {
119    }
120
121    public IEnumerable<double> GetSymbolicExpressionTreeValues(SymbolicExpressionTree tree, Dataset dataset, IEnumerable<int> rows) {
122      this.dataset = dataset;
123      var compiler = new SymbolicExpressionTreeCompiler();
124      compiler.AddInstructionPostProcessingHook(PostProcessInstruction);
125      code = compiler.Compile(tree, MapSymbolToOpCode);
126      foreach (var row in rows) {
127        this.row = row;
128        pc = 0;
129        argStackPointer = 0;
130        yield return Evaluate();
131      }
132    }
133
134    private Instruction PostProcessInstruction(Instruction instr) {
135      if (instr.opCode == OpCodes.Variable) {
136        var variableTreeNode = instr.dynamicNode as VariableTreeNode;
137        instr.iArg0 = (ushort)dataset.GetVariableIndex(variableTreeNode.VariableName);
138      } else if (instr.opCode == OpCodes.LagVariable) {
139        var variableTreeNode = instr.dynamicNode as LaggedVariableTreeNode;
140        instr.iArg0 = (ushort)dataset.GetVariableIndex(variableTreeNode.VariableName);
141      }
142      return instr;
143    }
144
145    private byte MapSymbolToOpCode(SymbolicExpressionTreeNode treeNode) {
146      if (symbolToOpcode.ContainsKey(treeNode.Symbol.GetType()))
147        return symbolToOpcode[treeNode.Symbol.GetType()];
148      else
149        throw new NotSupportedException("Symbol: " + treeNode.Symbol);
150    }
151
152    private double Evaluate() {
153      Instruction currentInstr = code[pc++];
154      switch (currentInstr.opCode) {
155        case OpCodes.Add: {
156            double s = Evaluate();
157            for (int i = 1; i < currentInstr.nArguments; i++) {
158              s += Evaluate();
159            }
160            return s;
161          }
162        case OpCodes.Sub: {
163            double s = Evaluate();
164            for (int i = 1; i < currentInstr.nArguments; i++) {
165              s -= Evaluate();
166            }
167            if (currentInstr.nArguments == 1) s = -s;
168            return s;
169          }
170        case OpCodes.Mul: {
171            double p = Evaluate();
172            for (int i = 1; i < currentInstr.nArguments; i++) {
173              p *= Evaluate();
174            }
175            return p;
176          }
177        case OpCodes.Div: {
178            double p = Evaluate();
179            for (int i = 1; i < currentInstr.nArguments; i++) {
180              p /= Evaluate();
181            }
182            if (currentInstr.nArguments == 1) p = 1.0 / p;
183            return p;
184          }
185        case OpCodes.Average: {
186            double sum = Evaluate();
187            for (int i = 1; i < currentInstr.nArguments; i++) {
188              sum += Evaluate();
189            }
190            return sum / currentInstr.nArguments;
191          }
192        case OpCodes.Cos: {
193            return Math.Cos(Evaluate());
194          }
195        case OpCodes.Sin: {
196            return Math.Sin(Evaluate());
197          }
198        case OpCodes.Tan: {
199            return Math.Tan(Evaluate());
200          }
201        case OpCodes.Exp: {
202            return Math.Exp(Evaluate());
203          }
204        case OpCodes.Log: {
205            return Math.Log(Evaluate());
206          }
207        case OpCodes.IfThenElse: {
208            double condition = Evaluate();
209            double result;
210            if (condition > 0.0) {
211              result = Evaluate(); SkipBakedCode();
212            } else {
213              SkipBakedCode(); result = Evaluate();
214            }
215            return result;
216          }
217        case OpCodes.AND: {
218            double result = Evaluate();
219            for (int i = 1; i < currentInstr.nArguments; i++) {
220              if (result <= 0.0) SkipBakedCode();
221              else {
222                result = Evaluate();
223              }
224            }
225            return result <= 0.0 ? -1.0 : 1.0;
226          }
227        case OpCodes.OR: {
228            double result = Evaluate();
229            for (int i = 1; i < currentInstr.nArguments; i++) {
230              if (result > 0.0) SkipBakedCode();
231              else {
232                result = Evaluate();
233              }
234            }
235            return result > 0.0 ? 1.0 : -1.0;
236          }
237        case OpCodes.NOT: {
238            return -Evaluate();
239          }
240        case OpCodes.GT: {
241            double x = Evaluate();
242            double y = Evaluate();
243            if (x > y) return 1.0;
244            else return -1.0;
245          }
246        case OpCodes.LT: {
247            double x = Evaluate();
248            double y = Evaluate();
249            if (x < y) return 1.0;
250            else return -1.0;
251          }
252        case OpCodes.Call: {
253            // evaluate sub-trees
254            // push on argStack in reverse order
255            for (int i = 0; i < currentInstr.nArguments; i++) {
256              argumentStack[argStackPointer + currentInstr.nArguments - i] = Evaluate();
257            }
258            argStackPointer += currentInstr.nArguments;
259
260            // save the pc
261            int nextPc = pc;
262            // set pc to start of function 
263            pc = currentInstr.iArg0;
264            // evaluate the function
265            double v = Evaluate();
266
267            // decrease the argument stack pointer by the number of arguments pushed
268            // to set the argStackPointer back to the original location
269            argStackPointer -= currentInstr.nArguments;
270
271            // restore the pc => evaluation will continue at point after my subtrees 
272            pc = nextPc;
273            return v;
274          }
275        case OpCodes.Arg: {
276            return argumentStack[argStackPointer - currentInstr.iArg0];
277          }
278        case OpCodes.Variable: {
279            var variableTreeNode = currentInstr.dynamicNode as VariableTreeNode;
280            return dataset[row, currentInstr.iArg0] * variableTreeNode.Weight;
281          }
282        case OpCodes.LagVariable: {
283            var lagVariableTreeNode = currentInstr.dynamicNode as LaggedVariableTreeNode;
284            int actualRow = row + lagVariableTreeNode.Lag;
285            if (actualRow < 0 || actualRow >= dataset.Rows) throw new ArgumentException("Out of range access to dataset row: " + row);
286            return dataset[actualRow, currentInstr.iArg0] * lagVariableTreeNode.Weight;
287          }
288        case OpCodes.Constant: {
289            var constTreeNode = currentInstr.dynamicNode as ConstantTreeNode;
290            return constTreeNode.Value;
291          }
292        default: throw new NotSupportedException();
293      }
294    }
295
296    // skips a whole branch
297    private void SkipBakedCode() {
298      int i = 1;
299      while (i > 0) {
300        i += code[pc++].nArguments;
301        i--;
302      }
303    }
304  }
305}
Note: See TracBrowser for help on using the repository browser.