Free cookie consent management tool by TermsFeed Policy Generator

Ignore:
Timestamp:
01/30/11 13:00:18 (14 years ago)
Author:
gkronber
Message:

#1400. Refactored interpreter for symbolic expression trees.

File:
1 edited

Legend:

Unmodified
Added
Removed

  • trunk/sources/HeuristicLab.Problems.DataAnalysis/3.3/Symbolic/SimpleArithmeticExpressionInterpreter.cs

    r5384 r5396  
    3434  [Item("SimpleArithmeticExpressionInterpreter", "Interpreter for arithmetic symbolic expression trees including function calls.")]
    3535  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
    3694    private class OpCodes {
    3795      public const byte Add = 1;
    … …  
    101159      { typeof(Derivative), OpCodes.Derivative},
    102160    };
    103     private const int ARGUMENT_STACK_SIZE = 1024;
     161
    104162
    105163    public override bool CanChangeName {
    … …  
    137195        }
    138196      }
    139 
    140       double[] argumentStack = new double[ARGUMENT_STACK_SIZE];
     197      var state = new InterpreterState(code);
     198
    141199      foreach (var rowEnum in rows) {
    142200        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();
    151208      switch (currentInstr.opCode) {
    152209        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);
    156213            }
    157214            return s;
    158215          }
    159216        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);
    163220            }
    164221            if (currentInstr.nArguments == 1) s = -s;
    … …  
    166223          }
    167224        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);
    171228            }
    172229            return p;
    173230          }
    174231        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);
    178235            }
    179236            if (currentInstr.nArguments == 1) p = 1.0 / p;
    … …  
    181238          }
    182239        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);
    186243            }
    187244            return sum / currentInstr.nArguments;
    188245          }
    189246        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));
    191248          }
    192249        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));
    194251          }
    195252        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));
    197254          }
    198255        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));
    201258            return Math.Pow(x, y);
    202259          }
    203260        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));
    206263            return Math.Pow(x, 1 / y);
    207264          }
    208265        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));
    210267          }
    211268        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));
    213270          }
    214271        case OpCodes.IfThenElse: {
    215             double condition = Evaluate(dataset, ref row, code, ref pc, argumentStack, ref argStackPointer);
     272            double condition = Evaluate(dataset, ref row, state);
    216273            double result;
    217274            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);
    219276            } else {
    220               SkipBakedCode(code, ref pc); result = Evaluate(dataset, ref row, code, ref pc, argumentStack, ref argStackPointer);
     277              SkipInstructions(state); result = Evaluate(dataset, ref row, state);
    221278            }
    222279            return result;
    223280          }
    224281        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) SkipBakedCode(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);
    228285              else {
    229                 result = Evaluate(dataset, ref row, code, ref pc, argumentStack, ref argStackPointer);
     286                result = Evaluate(dataset, ref row, state);
    230287              }
    231288            }
    … …  
    233290          }
    234291        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) SkipBakedCode(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);
    238295              else {
    239                 result = Evaluate(dataset, ref row, code, ref pc, argumentStack, ref argStackPointer);
     296                result = Evaluate(dataset, ref row, state);
    240297              }
    241298            }
    … …  
    243300          }
    244301        case OpCodes.NOT: {
    245             return -Evaluate(dataset, ref row, code, ref pc, argumentStack, ref argStackPointer);
     302            return -Evaluate(dataset, ref row, state);
    246303          }
    247304        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);
    250307            if (x > y) return 1.0;
    251308            else return -1.0;
    252309          }
    253310        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);
    256313            if (x < y) return 1.0;
    257314            else return -1.0;
    … …  
    263320
    264321            row += timeLagTreeNode.Lag;
    265             double result = Evaluate(dataset, ref row, code, ref pc, argumentStack, ref argStackPointer);
     322            double result = Evaluate(dataset, ref row, state);
    266323            row -= timeLagTreeNode.Lag;
    267324            return result;
    268325          }
    269326        case OpCodes.Integral: {
    270             int nextPc = pc;
     327            int savedPc = state.ProgramCounter;
    271328            var timeLagTreeNode = (LaggedTreeNode)currentInstr.dynamicNode;
    272329            if (row + timeLagTreeNode.Lag < 0 || row + timeLagTreeNode.Lag >= dataset.Rows)
    … …  
    275332            for (int i = 0; i < Math.Abs(timeLagTreeNode.Lag); i++) {
    276333              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;
    279336            }
    280337            row -= timeLagTreeNode.Lag;
    281             sum += Evaluate(dataset, ref row, code, ref pc, argumentStack, ref argStackPointer);
     338            sum += Evaluate(dataset, ref row, state);
    282339            return sum;
    283340          }
    … …  
    289346        case OpCodes.Derivative: {
    290347            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); ;
    299356            row += 4;
    300357
    … …  
    303360        case OpCodes.Call: {
    304361            // evaluate sub-trees
    305             // push on argStack in reverse order
     362            double[] argValues = new double[currentInstr.nArguments];
    306363            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);
    310368
    311369            // save the pc
    312             int nextPc = pc;
     370            int savedPc = state.ProgramCounter;
    313371            // set pc to start of function 
    314             pc = currentInstr.iArg0;
     372            state.ProgramCounter = currentInstr.iArg0;
    315373            // 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();
    321378
    322379            // restore the pc => evaluation will continue at point after my subtrees 
    323             pc = nextPc;
     380            state.ProgramCounter = savedPc;
    324381            return v;
    325382          }
    326383        case OpCodes.Arg: {
    327             return argumentStack[argStackPointer - currentInstr.iArg0];
     384            return state.GetStackFrameValue(currentInstr.iArg0);
    328385          }
    329386        case OpCodes.Variable: {
    … …  
    353410
    354411    // skips a whole branch
    355     private void SkipBakedCode(Instruction[] code, ref int pc) {
     412    private void SkipInstructions(InterpreterState state) {
    356413      int i = 1;
    357414      while (i > 0) {
    358         i += code[pc++].nArguments;
     415        i += state.NextInstruction().nArguments;
    359416        i--;
    360417      }
Note: See TracChangeset for help on using the changeset viewer.