Changeset 5396
 Timestamp:
 01/30/11 13:00:18 (14 years ago)
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

trunk/sources/HeuristicLab.Problems.DataAnalysis/3.3/Symbolic/SimpleArithmeticExpressionInterpreter.cs
r5384 r5396 34 34 [Item("SimpleArithmeticExpressionInterpreter", "Interpreter for arithmetic symbolic expression trees including function calls.")] 35 35 public sealed class SimpleArithmeticExpressionInterpreter : NamedItem, ISymbolicExpressionTreeInterpreter { 36 private class InterpreterState { 37 private const int ARGUMENT_STACK_SIZE = 1024; 38 private double[] argumentStack; 39 private int argumentStackPointer; 40 private Instruction[] code; 41 private int pc; 42 public int ProgramCounter { 43 get { return pc; } 44 set { pc = value; } 45 } 46 internal InterpreterState(Instruction[] code) { 47 this.code = code; 48 this.pc = 0; 49 this.argumentStack = new double[ARGUMENT_STACK_SIZE]; 50 this.argumentStackPointer = 0; 51 } 52 53 internal void Reset() { 54 this.pc = 0; 55 this.argumentStackPointer = 0; 56 } 57 58 internal Instruction NextInstruction() { 59 return code[pc++]; 60 } 61 private void Push(double val) { 62 argumentStack[argumentStackPointer++] = val; 63 } 64 private double Pop() { 65 return argumentStack[argumentStackPointer]; 66 } 67 68 internal void CreateStackFrame(double[] argValues) { 69 // push in reverse order to make indexing easier 70 for (int i = argValues.Length  1; i >= 0; i) { 71 argumentStack[argumentStackPointer++] = argValues[i]; 72 } 73 Push(argValues.Length); 74 } 75 76 internal void RemoveStackFrame() { 77 int size = (int)Pop(); 78 argumentStackPointer = size; 79 } 80 81 internal double GetStackFrameValue(ushort index) { 82 // layout of stack: 83 // [0] < argumentStackPointer 84 // [StackFrameSize = N + 1] 85 // [Arg0] < argumentStackPointer  2  0 86 // [Arg1] < argumentStackPointer  2  1 87 // [...] 88 // [ArgN] < argumentStackPointer  2  N 89 // <Begin of stack frame> 90 return argumentStack[argumentStackPointer  index  2]; 91 } 92 } 93 36 94 private class OpCodes { 37 95 public const byte Add = 1; … … 101 159 { typeof(Derivative), OpCodes.Derivative}, 102 160 }; 103 private const int ARGUMENT_STACK_SIZE = 1024; 161 104 162 105 163 public override bool CanChangeName { … … 137 195 } 138 196 } 139 140 double[] argumentStack = new double[ARGUMENT_STACK_SIZE]; 197 var state = new InterpreterState(code); 198 141 199 foreach (var rowEnum in rows) { 142 200 int row = rowEnum; 143 int pc = 0; 144 int argStackPointer = 0; 145 yield return Evaluate(dataset, ref row, code, ref pc, argumentStack, ref argStackPointer); 146 } 147 } 148 149 private double Evaluate(Dataset dataset, ref int row, Instruction[] code, ref int pc, double[] argumentStack, ref int argStackPointer) { 150 Instruction currentInstr = code[pc++]; 201 state.Reset(); 202 yield return Evaluate(dataset, ref row, state); 203 } 204 } 205 206 private double Evaluate(Dataset dataset, ref int row, InterpreterState state) { 207 Instruction currentInstr = state.NextInstruction(); 151 208 switch (currentInstr.opCode) { 152 209 case OpCodes.Add: { 153 double s = Evaluate(dataset, ref row, code, ref pc, argumentStack, ref argStackPointer);154 for (int i = 1; i < currentInstr.nArguments; i++) { 155 s += Evaluate(dataset, ref row, code, ref pc, argumentStack, ref argStackPointer);210 double s = Evaluate(dataset, ref row, state); 211 for (int i = 1; i < currentInstr.nArguments; i++) { 212 s += Evaluate(dataset, ref row, state); 156 213 } 157 214 return s; 158 215 } 159 216 case OpCodes.Sub: { 160 double s = Evaluate(dataset, ref row, code, ref pc, argumentStack, ref argStackPointer);161 for (int i = 1; i < currentInstr.nArguments; i++) { 162 s = Evaluate(dataset, ref row, code, ref pc, argumentStack, ref argStackPointer);217 double s = Evaluate(dataset, ref row, state); 218 for (int i = 1; i < currentInstr.nArguments; i++) { 219 s = Evaluate(dataset, ref row, state); 163 220 } 164 221 if (currentInstr.nArguments == 1) s = s; … … 166 223 } 167 224 case OpCodes.Mul: { 168 double p = Evaluate(dataset, ref row, code, ref pc, argumentStack, ref argStackPointer);169 for (int i = 1; i < currentInstr.nArguments; i++) { 170 p *= Evaluate(dataset, ref row, code, ref pc, argumentStack, ref argStackPointer);225 double p = Evaluate(dataset, ref row, state); 226 for (int i = 1; i < currentInstr.nArguments; i++) { 227 p *= Evaluate(dataset, ref row, state); 171 228 } 172 229 return p; 173 230 } 174 231 case OpCodes.Div: { 175 double p = Evaluate(dataset, ref row, code, ref pc, argumentStack, ref argStackPointer);176 for (int i = 1; i < currentInstr.nArguments; i++) { 177 p /= Evaluate(dataset, ref row, code, ref pc, argumentStack, ref argStackPointer);232 double p = Evaluate(dataset, ref row, state); 233 for (int i = 1; i < currentInstr.nArguments; i++) { 234 p /= Evaluate(dataset, ref row, state); 178 235 } 179 236 if (currentInstr.nArguments == 1) p = 1.0 / p; … … 181 238 } 182 239 case OpCodes.Average: { 183 double sum = Evaluate(dataset, ref row, code, ref pc, argumentStack, ref argStackPointer);184 for (int i = 1; i < currentInstr.nArguments; i++) { 185 sum += Evaluate(dataset, ref row, code, ref pc, argumentStack, ref argStackPointer);240 double sum = Evaluate(dataset, ref row, state); 241 for (int i = 1; i < currentInstr.nArguments; i++) { 242 sum += Evaluate(dataset, ref row, state); 186 243 } 187 244 return sum / currentInstr.nArguments; 188 245 } 189 246 case OpCodes.Cos: { 190 return Math.Cos(Evaluate(dataset, ref row, code, ref pc, argumentStack, ref argStackPointer));247 return Math.Cos(Evaluate(dataset, ref row, state)); 191 248 } 192 249 case OpCodes.Sin: { 193 return Math.Sin(Evaluate(dataset, ref row, code, ref pc, argumentStack, ref argStackPointer));250 return Math.Sin(Evaluate(dataset, ref row, state)); 194 251 } 195 252 case OpCodes.Tan: { 196 return Math.Tan(Evaluate(dataset, ref row, code, ref pc, argumentStack, ref argStackPointer));253 return Math.Tan(Evaluate(dataset, ref row, state)); 197 254 } 198 255 case OpCodes.Power: { 199 double x = Evaluate(dataset, ref row, code, ref pc, argumentStack, ref argStackPointer);200 double y = Math.Round(Evaluate(dataset, ref row, code, ref pc, argumentStack, ref argStackPointer));256 double x = Evaluate(dataset, ref row, state); 257 double y = Math.Round(Evaluate(dataset, ref row, state)); 201 258 return Math.Pow(x, y); 202 259 } 203 260 case OpCodes.Root: { 204 double x = Evaluate(dataset, ref row, code, ref pc, argumentStack, ref argStackPointer);205 double y = Math.Round(Evaluate(dataset, ref row, code, ref pc, argumentStack, ref argStackPointer));261 double x = Evaluate(dataset, ref row, state); 262 double y = Math.Round(Evaluate(dataset, ref row, state)); 206 263 return Math.Pow(x, 1 / y); 207 264 } 208 265 case OpCodes.Exp: { 209 return Math.Exp(Evaluate(dataset, ref row, code, ref pc, argumentStack, ref argStackPointer));266 return Math.Exp(Evaluate(dataset, ref row, state)); 210 267 } 211 268 case OpCodes.Log: { 212 return Math.Log(Evaluate(dataset, ref row, code, ref pc, argumentStack, ref argStackPointer));269 return Math.Log(Evaluate(dataset, ref row, state)); 213 270 } 214 271 case OpCodes.IfThenElse: { 215 double condition = Evaluate(dataset, ref row, code, ref pc, argumentStack, ref argStackPointer);272 double condition = Evaluate(dataset, ref row, state); 216 273 double result; 217 274 if (condition > 0.0) { 218 result = Evaluate(dataset, ref row, code, ref pc, argumentStack, ref argStackPointer); SkipBakedCode(code, ref pc);275 result = Evaluate(dataset, ref row, state); SkipInstructions(state); 219 276 } else { 220 Skip BakedCode(code, ref pc); result = Evaluate(dataset, ref row, code, ref pc, argumentStack, ref argStackPointer);277 SkipInstructions(state); result = Evaluate(dataset, ref row, state); 221 278 } 222 279 return result; 223 280 } 224 281 case OpCodes.AND: { 225 double result = Evaluate(dataset, ref row, code, ref pc, argumentStack, ref argStackPointer);226 for (int i = 1; i < currentInstr.nArguments; i++) { 227 if (result <= 0.0) Skip BakedCode(code, ref pc);282 double result = Evaluate(dataset, ref row, state); 283 for (int i = 1; i < currentInstr.nArguments; i++) { 284 if (result <= 0.0) SkipInstructions(state); 228 285 else { 229 result = Evaluate(dataset, ref row, code, ref pc, argumentStack, ref argStackPointer);286 result = Evaluate(dataset, ref row, state); 230 287 } 231 288 } … … 233 290 } 234 291 case OpCodes.OR: { 235 double result = Evaluate(dataset, ref row, code, ref pc, argumentStack, ref argStackPointer);236 for (int i = 1; i < currentInstr.nArguments; i++) { 237 if (result > 0.0) Skip BakedCode(code, ref pc);292 double result = Evaluate(dataset, ref row, state); 293 for (int i = 1; i < currentInstr.nArguments; i++) { 294 if (result > 0.0) SkipInstructions(state); 238 295 else { 239 result = Evaluate(dataset, ref row, code, ref pc, argumentStack, ref argStackPointer);296 result = Evaluate(dataset, ref row, state); 240 297 } 241 298 } … … 243 300 } 244 301 case OpCodes.NOT: { 245 return Evaluate(dataset, ref row, code, ref pc, argumentStack, ref argStackPointer);302 return Evaluate(dataset, ref row, state); 246 303 } 247 304 case OpCodes.GT: { 248 double x = Evaluate(dataset, ref row, code, ref pc, argumentStack, ref argStackPointer);249 double y = Evaluate(dataset, ref row, code, ref pc, argumentStack, ref argStackPointer);305 double x = Evaluate(dataset, ref row, state); 306 double y = Evaluate(dataset, ref row, state); 250 307 if (x > y) return 1.0; 251 308 else return 1.0; 252 309 } 253 310 case OpCodes.LT: { 254 double x = Evaluate(dataset, ref row, code, ref pc, argumentStack, ref argStackPointer);255 double y = Evaluate(dataset, ref row, code, ref pc, argumentStack, ref argStackPointer);311 double x = Evaluate(dataset, ref row, state); 312 double y = Evaluate(dataset, ref row, state); 256 313 if (x < y) return 1.0; 257 314 else return 1.0; … … 263 320 264 321 row += timeLagTreeNode.Lag; 265 double result = Evaluate(dataset, ref row, code, ref pc, argumentStack, ref argStackPointer);322 double result = Evaluate(dataset, ref row, state); 266 323 row = timeLagTreeNode.Lag; 267 324 return result; 268 325 } 269 326 case OpCodes.Integral: { 270 int nextPc = pc;327 int savedPc = state.ProgramCounter; 271 328 var timeLagTreeNode = (LaggedTreeNode)currentInstr.dynamicNode; 272 329 if (row + timeLagTreeNode.Lag < 0  row + timeLagTreeNode.Lag >= dataset.Rows) … … 275 332 for (int i = 0; i < Math.Abs(timeLagTreeNode.Lag); i++) { 276 333 row += Math.Sign(timeLagTreeNode.Lag); 277 sum += Evaluate(dataset, ref row, code, ref pc, argumentStack, ref argStackPointer);278 pc = nextPc;334 sum += Evaluate(dataset, ref row, state); 335 state.ProgramCounter = savedPc; 279 336 } 280 337 row = timeLagTreeNode.Lag; 281 sum += Evaluate(dataset, ref row, code, ref pc, argumentStack, ref argStackPointer);338 sum += Evaluate(dataset, ref row, state); 282 339 return sum; 283 340 } … … 289 346 case OpCodes.Derivative: { 290 347 if (row  4 < 0) return double.NaN; 291 int nextPc = pc;292 double f_0 = Evaluate(dataset, ref row, code, ref pc, argumentStack, ref argStackPointer); ; row;293 pc = nextPc;294 double f_1 = Evaluate(dataset, ref row, code, ref pc, argumentStack, ref argStackPointer); ; row = 2;295 pc = nextPc;296 double f_3 = Evaluate(dataset, ref row, code, ref pc, argumentStack, ref argStackPointer); ; row;297 pc = nextPc;298 double f_4 = Evaluate(dataset, ref row, code, ref pc, argumentStack, ref argStackPointer); ;348 int savedPc = state.ProgramCounter; 349 double f_0 = Evaluate(dataset, ref row, state); ; row; 350 state.ProgramCounter = savedPc; 351 double f_1 = Evaluate(dataset, ref row, state); ; row = 2; 352 state.ProgramCounter = savedPc; 353 double f_3 = Evaluate(dataset, ref row, state); ; row; 354 state.ProgramCounter = savedPc; 355 double f_4 = Evaluate(dataset, ref row, state); ; 299 356 row += 4; 300 357 … … 303 360 case OpCodes.Call: { 304 361 // evaluate subtrees 305 // push on argStack in reverse order362 double[] argValues = new double[currentInstr.nArguments]; 306 363 for (int i = 0; i < currentInstr.nArguments; i++) { 307 argumentStack[argStackPointer + currentInstr.nArguments  i] = Evaluate(dataset, ref row, code, ref pc, argumentStack, ref argStackPointer); 308 } 309 argStackPointer += currentInstr.nArguments; 364 argValues[i] = Evaluate(dataset, ref row, state); 365 } 366 // push on argument values on stack 367 state.CreateStackFrame(argValues); 310 368 311 369 // save the pc 312 int nextPc = pc;370 int savedPc = state.ProgramCounter; 313 371 // set pc to start of function 314 pc= currentInstr.iArg0;372 state.ProgramCounter = currentInstr.iArg0; 315 373 // evaluate the function 316 double v = Evaluate(dataset, ref row, code, ref pc, argumentStack, ref argStackPointer); 317 318 // decrease the argument stack pointer by the number of arguments pushed 319 // to set the argStackPointer back to the original location 320 argStackPointer = currentInstr.nArguments; 374 double v = Evaluate(dataset, ref row, state); 375 376 // delete the stack frame 377 state.RemoveStackFrame(); 321 378 322 379 // restore the pc => evaluation will continue at point after my subtrees 323 pc = nextPc;380 state.ProgramCounter = savedPc; 324 381 return v; 325 382 } 326 383 case OpCodes.Arg: { 327 return argumentStack[argStackPointer  currentInstr.iArg0];384 return state.GetStackFrameValue(currentInstr.iArg0); 328 385 } 329 386 case OpCodes.Variable: { … … 353 410 354 411 // skips a whole branch 355 private void Skip BakedCode(Instruction[] code, ref int pc) {412 private void SkipInstructions(InterpreterState state) { 356 413 int i = 1; 357 414 while (i > 0) { 358 i += code[pc++].nArguments;415 i += state.NextInstruction().nArguments; 359 416 i; 360 417 }
Note: See TracChangeset
for help on using the changeset viewer.