[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 |
|
---|
| 22 | using System;
|
---|
| 23 | using System.Collections.Generic;
|
---|
| 24 | using HeuristicLab.Common;
|
---|
| 25 | using HeuristicLab.Core;
|
---|
| 26 | using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;
|
---|
| 27 | using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding.Compiler;
|
---|
| 28 | using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding.Symbols;
|
---|
| 29 | using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
|
---|
| 30 | using HeuristicLab.Problems.DataAnalysis.Symbolic.Symbols;
|
---|
| 31 |
|
---|
| 32 | namespace 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 | }
|
---|