Free cookie consent management tool by TermsFeed Policy Generator

source: branches/GP-MemoryOperations/HeuristicLab.Problems.DataAnalysis/3.3/Symbolic/SimpleArithmeticExpressionInterpreter.cs @ 5867

Last change on this file since 5867 was 4897, checked in by gkronber, 14 years ago

Implemented set-memory and read-memory operation for GP-based data-analysis. #1290

File size: 11.7 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      public const byte Average = 16;
60
61      public const byte Call = 17;
62
63      public const byte Variable = 18;
64      public const byte LagVariable = 19;
65      public const byte Constant = 20;
66      public const byte Arg = 21;
67
68      public const byte Set = 22;
69      public const byte Read = 23;
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(SetMem), OpCodes.Set },
95      { typeof(ReadMem), OpCodes.Read },
96    };
97    private const int ARGUMENT_STACK_SIZE = 1024;
98    private const int MAX_MEMORY_SIZE = 128;
99
100    private Dataset dataset;
101    private int row;
102    private Instruction[] code;
103    private int pc;
104    private double[] argumentStack = new double[ARGUMENT_STACK_SIZE];
105    private int argStackPointer;
106    private double[] memory = new double[MAX_MEMORY_SIZE];
107
108    public override bool CanChangeName {
109      get { return false; }
110    }
111    public override bool CanChangeDescription {
112      get { return false; }
113    }
114
115    [StorableConstructor]
116    private SimpleArithmeticExpressionInterpreter(bool deserializing) : base(deserializing) { }
117    private SimpleArithmeticExpressionInterpreter(SimpleArithmeticExpressionInterpreter original, Cloner cloner) : base(original, cloner) { }
118
119    public override IDeepCloneable Clone(Cloner cloner) {
120      return new SimpleArithmeticExpressionInterpreter(this, cloner);
121    }
122
123    public SimpleArithmeticExpressionInterpreter()
124      : base() {
125    }
126
127    public IEnumerable<double> GetSymbolicExpressionTreeValues(SymbolicExpressionTree tree, Dataset dataset, IEnumerable<int> rows) {
128      this.dataset = dataset;
129      var compiler = new SymbolicExpressionTreeCompiler();
130      compiler.AddInstructionPostProcessingHook(PostProcessInstruction);
131      code = compiler.Compile(tree, MapSymbolToOpCode);
132      Array.Clear(memory, 0, MAX_MEMORY_SIZE);
133      foreach (var row in rows) {
134        this.row = row;
135        pc = 0;
136        argStackPointer = 0;
137        yield return Evaluate();
138      }
139    }
140
141    private Instruction PostProcessInstruction(Instruction instr) {
142      if (instr.opCode == OpCodes.Variable) {
143        var variableTreeNode = instr.dynamicNode as VariableTreeNode;
144        instr.iArg0 = (ushort)dataset.GetVariableIndex(variableTreeNode.VariableName);
145      } else if (instr.opCode == OpCodes.LagVariable) {
146        var variableTreeNode = instr.dynamicNode as LaggedVariableTreeNode;
147        instr.iArg0 = (ushort)dataset.GetVariableIndex(variableTreeNode.VariableName);
148      } else if (instr.opCode == OpCodes.Set) {
149        var setMemTreeNode = instr.dynamicNode as SetMemTreeNode;
150        instr.iArg0 = (ushort)setMemTreeNode.Address;
151      } else if (instr.opCode == OpCodes.Read) {
152        var readMemTreeNode = instr.dynamicNode as ReadMemTreeNode;
153        instr.iArg0 = (ushort)readMemTreeNode.Address;
154      }
155      return instr;
156    }
157
158    private byte MapSymbolToOpCode(SymbolicExpressionTreeNode treeNode) {
159      if (symbolToOpcode.ContainsKey(treeNode.Symbol.GetType()))
160        return symbolToOpcode[treeNode.Symbol.GetType()];
161      else
162        throw new NotSupportedException("Symbol: " + treeNode.Symbol);
163    }
164
165    private double Evaluate() {
166      Instruction currentInstr = code[pc++];
167      switch (currentInstr.opCode) {
168        case OpCodes.Add: {
169            double s = Evaluate();
170            for (int i = 1; i < currentInstr.nArguments; i++) {
171              s += Evaluate();
172            }
173            return s;
174          }
175        case OpCodes.Sub: {
176            double s = Evaluate();
177            for (int i = 1; i < currentInstr.nArguments; i++) {
178              s -= Evaluate();
179            }
180            if (currentInstr.nArguments == 1) s = -s;
181            return s;
182          }
183        case OpCodes.Mul: {
184            double p = Evaluate();
185            for (int i = 1; i < currentInstr.nArguments; i++) {
186              p *= Evaluate();
187            }
188            return p;
189          }
190        case OpCodes.Div: {
191            double p = Evaluate();
192            for (int i = 1; i < currentInstr.nArguments; i++) {
193              p /= Evaluate();
194            }
195            if (currentInstr.nArguments == 1) p = 1.0 / p;
196            return p;
197          }
198        case OpCodes.Average: {
199            double sum = Evaluate();
200            for (int i = 1; i < currentInstr.nArguments; i++) {
201              sum += Evaluate();
202            }
203            return sum / currentInstr.nArguments;
204          }
205        case OpCodes.Cos: {
206            return Math.Cos(Evaluate());
207          }
208        case OpCodes.Sin: {
209            return Math.Sin(Evaluate());
210          }
211        case OpCodes.Tan: {
212            return Math.Tan(Evaluate());
213          }
214        case OpCodes.Exp: {
215            return Math.Exp(Evaluate());
216          }
217        case OpCodes.Log: {
218            return Math.Log(Evaluate());
219          }
220        case OpCodes.IfThenElse: {
221            double condition = Evaluate();
222            double result;
223            if (condition > 0.0) {
224              result = Evaluate(); SkipBakedCode();
225            } else {
226              SkipBakedCode(); result = Evaluate();
227            }
228            return result;
229          }
230        case OpCodes.AND: {
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.OR: {
241            double result = Evaluate();
242            for (int i = 1; i < currentInstr.nArguments; i++) {
243              if (result > 0.0) SkipBakedCode();
244              else {
245                result = Evaluate();
246              }
247            }
248            return result > 0.0 ? 1.0 : -1.0;
249          }
250        case OpCodes.NOT: {
251            return -Evaluate();
252          }
253        case OpCodes.GT: {
254            double x = Evaluate();
255            double y = Evaluate();
256            if (x > y) return 1.0;
257            else return -1.0;
258          }
259        case OpCodes.LT: {
260            double x = Evaluate();
261            double y = Evaluate();
262            if (x < y) return 1.0;
263            else return -1.0;
264          }
265        case OpCodes.Call: {
266            // evaluate sub-trees
267            // push on argStack in reverse order
268            for (int i = 0; i < currentInstr.nArguments; i++) {
269              argumentStack[argStackPointer + currentInstr.nArguments - i] = Evaluate();
270            }
271            argStackPointer += currentInstr.nArguments;
272
273            // save the pc
274            int nextPc = pc;
275            // set pc to start of function 
276            pc = currentInstr.iArg0;
277            // evaluate the function
278            double v = Evaluate();
279
280            // decrease the argument stack pointer by the number of arguments pushed
281            // to set the argStackPointer back to the original location
282            argStackPointer -= currentInstr.nArguments;
283
284            // restore the pc => evaluation will continue at point after my subtrees 
285            pc = nextPc;
286            return v;
287          }
288        case OpCodes.Arg: {
289            return argumentStack[argStackPointer - currentInstr.iArg0];
290          }
291        case OpCodes.Variable: {
292            var variableTreeNode = currentInstr.dynamicNode as VariableTreeNode;
293            return dataset[row, currentInstr.iArg0] * variableTreeNode.Weight;
294          }
295        case OpCodes.LagVariable: {
296            var lagVariableTreeNode = currentInstr.dynamicNode as LaggedVariableTreeNode;
297            int actualRow = row + lagVariableTreeNode.Lag;
298            if (actualRow < 0 || actualRow >= dataset.Rows) throw new ArgumentException("Out of range access to dataset row: " + row);
299            return dataset[actualRow, currentInstr.iArg0] * lagVariableTreeNode.Weight;
300          }
301        case OpCodes.Constant: {
302            var constTreeNode = currentInstr.dynamicNode as ConstantTreeNode;
303            return constTreeNode.Value;
304          }
305        case OpCodes.Set: {
306            double d = Evaluate();
307            memory[currentInstr.iArg0] = d;
308            return d;
309          }
310        case OpCodes.Read: {
311            return memory[currentInstr.iArg0];
312          }
313        default: throw new NotSupportedException();
314      }
315    }
316
317    // skips a whole branch
318    private void SkipBakedCode() {
319      int i = 1;
320      while (i > 0) {
321        i += code[pc++].nArguments;
322        i--;
323      }
324    }
325  }
326}
Note: See TracBrowser for help on using the repository browser.