På en tidligere version af dotninjas.dk kunne man finde en artikel om hvordan man kompilerer et udtryk til funktioner som kan bruges som plugin i egne beregninger - ved at benytte den indbyggede C# compiler. Jeg vil forsøge at genopfriske lidt for artiklen, men vil denne gang compile Lambda udtryk som f.eks.

   1:  x => x * 2;

Vores specialiserede interface erstattes nu af Expression<T> (i dette tilfælde Expression<Func<double, double>>). Dette er naturligvis intressant hvis man ønsker at arbejde videre med expression træet, f.eks. hvis man ønsker at differentiere udtrykket. Hvis man blot ønsker at beregne funktionsværdier anbefaler jeg at man returnerer Func<double, double> delegaten direkte, idet der skal kaldes Compile på et lambda udtryk for at få delegaten vi skal evaluere med - man kompiler altså i to omgange.

Grundlæggende er det dette stykke kode vi ønsker at compile runtime:

   1:  using System; 
   2:  using System.Linq.Expressions; 
   3:   
   4:  public static class LambdaParser 
   5:  { 
   6:    public static Expression<Func<double,double>> Parse() 
   7:    { 
   8:      return {expression}; 
   9:    } 
  10:  } 

Vi skal blot erstatte {expression} med det ønskede udtryk som skal være en funktion med et enkelt argument af type double og return værdi double, eller f:R->R som man siger på matematisk. Man kunne også lægge sig fast på at variablen hed x og erstatte {expression}; med x=>{expression};

Jeg har valgt C# men man kan også vælge VB eller et andet sprog hvis blot man har en passende CodeDomProvider.

   1:  CSharpCodeProvider provider = new CSharpCodeProvider(); 

Brug evt. en Dictionary med CompilerVersion="v3.5" hvis du har behov for en specific version, ellers brug config filen. Ellers skal vi blot definere vores referencer og kompile koden:

   1:  CompilerParameters cp = new CompilerParameters(); 
   2:  cp.GenerateInMemory = true; 
   3:  cp.ReferencedAssemblies.Add("System.Core.dll"); 
   4:   
   5:  CompilerResults cr = provider.CompileAssemblyFromSource(cp, code); 

Husk at checke for kompilefejl (se cr.Errors.HasErros), for der bliver ikke kastet en exception. Herfra er der 3 linjer kode til vi står med vores lambda udtryk:

   1:  Type parserType = cr.CompiledAssembly.GetType("LambdaParser"); 
   2:  MethodInfo mi = parserType.GetMethod("Parse"); 
   3:  var f = (Expression<Func<double,double>>)mi.Invoke(null, new object[] { })); 

Jeg lader det være op til læseren at indkapsle koden i en genbrugelig klasse og tilføje bells and whistles. Ekstra referencer vil være en oplagt mulighed for udvidelser. En anden oplagt mulighed er at indføre en potens funktion hvad man skal bruge matematiske formler. Det kræver dog at man parser udtrykket lidt mere end blot en søg og erstat, f.eks.

   1:  x+x^2 -> x + Math.Pow(x, 2) 

Her skal Math.Pow funktionen indsættes efter plus tegnet, mens den skal indsættes efter parentens i dette udtryk

   1:  (x+1)^2 -> Math.Pow(x+1,2) 

Heldigvis skal de øvrige operatorer behandles ens, så det kun er parenteser vis skal ta' højde for.

   1:  public static string ReplacePower(string s) 
   2:  { 
   3:    int powerIndex = s.IndexOf('^'); 
   4:    if (powerIndex > 0) 
   5:    { 
   6:      string right = s.Substring(powerIndex + 1); 
   7:      string left = s.Substring(0, powerIndex); 
   8:   
   9:      int leftStart; 
  10:      int rightEnd; 
  11:   
  12:      if (left[left.Length - 1] == ')') 
  13:      { 
  14:        leftStart = FindStartParenthesis(left) - 1; 
  15:      } 
  16:      else 
  17:      { 
  18:        leftStart = left.LastIndexOfAny(opChars); 
  19:      } 
  20:      if (right[0] == '(') 
  21:      { 
  22:        rightEnd = FindEndParenthesis(right); 
  23:      } 
  24:      else 
  25:      { 
  26:        rightEnd = right.LastIndexOfAny(opChars); 
  27:      } 
  28:   
  29:      string s0 = left.Substring(0, leftStart + 1); 
  30:      string s1 = left.Substring(leftStart + 1); 
  31:      string s2 = rightEnd >= 0 ? right.Substring(0, rightEnd) : right; 
  32:      string s3 = rightEnd >= 0 ? right.Substring(rightEnd) : string.Empty; 
  33:   
  34:      return ReplacePower(string.Format("{0}Math.Pow({1},{2}){3}", s0, s1, s2, s3)); 
  35:    } 
  36:    return s; 
  37:  } 
  38:   
  39:  private static char[] opChars = new char[] { '+', '-', '/', '*', ' ', ',' }; 
  40:   
  41:  private static int FindStartParenthesis(string s) 
  42:  { 
  43:    int index = s.Length - 1; 
  44:    int parCount = 0; 
  45:   
  46:    while (index >= 0) 
  47:    { 
  48:      if (s[index] == ')') parCount++; 
  49:      if (s[index] == '(') parCount--; 
  50:      if (parCount == 0) return index; 
  51:      index--; 
  52:    } 
  53:    return index; 
  54:  } 
  55:   
  56:  private static int FindEndParenthesis(string s) 
  57:  { 
  58:    int index = 0; 
  59:    int parCount = 0; 
  60:   
  61:    while (index < s.Length) 
  62:    { 
  63:      if (s[index] == ')') parCount--; 
  64:      if (s[index] == '(') parCount++; 
  65:      if (parCount == 0) return index; 
  66:      index++; 
  67:    } 
  68:    return index; 
  69:  } 

Med FindEndParenthesis metoden skulle det også være nemt at erstatte diverse matematisk funktioner
med deres System.Math ekvivalenter som cos -> Math.Cos og sin -> Math.Sin.

Det var lide kode til at komme igang med din egen runtime expression parser - uden at der er nogen garanti for at det virker. Husk i det mindste at indsætte diverse checks så det ikke brager ned midt i en vigtig beregning.

Her i sommervarmen var det måske på tide at lege lidt med lambda udtryk: 

Expression<Func<double,double>> f = x => x + 1;

Hvis vi ser på lambda udtryk med matematiske briller vil vi ofte gerne differentiere udtrykket for f.eks. at finde maksimum eller nulpunkter. Differentialregning er heldigvis noget med en masse regler og så hårdt arbejde for resten - hvilket jo er computerens speciale. Men hvor nemt er det egentligt at differentiere et lambda udtryk?

Ovenstående udtryk parses til en Expression-træstruktur, som er et standard abstrakt syntaks træ. De enkelte noder i træer repræsenterer operatorer (plus, minus, gange og dividere, men også større end og mindre end), tal (konstanter) og symboler (også kaldet parametre som x ovenfor). Der er en helt række af expression typer (se ExpressionType for komplet liste), men noget kortere liste at klasser som nedarver Expression.

Mange ExpressionType værdier bruger f.eks. BinaryExpression - det gælder bl.a. Add, Subtract, Multiply og Divide, men også diverse boolske operatorer som f.eks. LessThan og GreaterThan (bemærk dog at disse returner bool og ikke double).

Expression finder du i System.Linq.Expression men benyttes også af Dynamic Language Runtime (DLR). Det er specielt udtryk til at styre flow i et program og tildeling af værdier som benyttes af DLR, men det vil vi ignorere i et matematisk setup.

Vi vælger at implementere Derive som en extension metode:

public static Expression Derive(this Expression e, string parameterName)
{
  switch (e.NodeType)
  {
    case ExpressionType.Add:
      ...
      break;
    
    ...
  }
}

Vi skal naturligvis implementere regler for alle værdier ExpressionType som giver matematisk mening, men først lige en metode mere.

public static Expression Derive(this Expression e, string parameterName)
{
  return Expression.Lambda(e.Body.Derive(parameterName), e.Parameters);
}

Denne metode sikrer at vi kan benytte Derive på LambdaExpression og at resultat også bliver en LambdaExpression. Vi har altså vores afledte giver som:

Expression> df = f.Derive("x");

I vores eksempel indgår tre node typer: Parameter, Constant og Add

case ExpressionType.Parameter:
  {
    ParameterExpression pe = (ParameterExpression)e;
    return Expression.Constant(pe.Name == parametername ? 1.0 : 0.0)
  }
  
case ExpressionType.Constant:
  return Expression.Constant(0.0);
  
case ExpressionType.Add:
  {
    BinaryExpressiob be = (BinaryExpression)e;
    return Expression.Add(
      be.Left.Derive(parameterName),
      be.Right.Derive(parameterName)
    );
  }

Hvilket giver os

df = x => 1 + 0;

Bemærk, at vi arbejder med doubles hele vejen igennem, ellers fejler programmet runtime ved at der ikke findes en add-operator som tager int som det ene argument og double som det andet. Resultat fra vores Derive metode er korrekt, men ikke specielt pænt at se på og måske heller ikke optimalt rent beregningsmæssigt. Til det formål foreslår jeg endnu en ekstension metode:

public static Expression Simplify(this Expression e)
{
  ...
}

Men den øvelse gemmer vi til en anden god gang - der er endnu meget arbejde på Derive.

En anden ting man bør bemærke er at der oprettes nye Expression når man skal redigere et udtryk. Det er et underliggende princip at Expression instanserne ikke kan ændres (de er immutable), hvilket man udnytter til Multiply operatoren i Derive:

case ExpressionType.Multiply: // (fg)'=f'g+fg'
  {
    BinaryExpression be = (BinaryExpression)e;
    Expression dleft = be.Left.Derive(parameterName);
    Expression dright = be.Right.Derive(parameterName);
    return Expression.Add(
      Expression.Multiply(dleft, be.Right),
      Expression.Multiply(be.Left, dright)
    );
  }

Vi har altså genbrugt undernoderne i BinaryExpression til et nyt udtryk. Jeg vil overlade det til læseren at implementere Subtract, Divide og Negate (UnaryExpression).

For funktions kald findes typen Call og klassen MethodCallExpression som med Member (MethodInfo) giver os en reference til den funktion som skal kaldes. Det er op til os at implementere den afledte af forskellige kendte funktioner, f.eks.

(Math.Sin)':
  return Expression.Call(null, typeof(Math).GetMethod("Cos"), me.Arguments);
(Math.Cos)':
  return Expression.Negate(Expression.Call(null, typeof(Math).GetMethod("Sin"),   me.Arguments);

hvor me er vores originale MethodCallExpression og me.Arguments således er de originale argumenter til funktionskaldet - jeg lader det være op til læseren at implementere kædereglen ((f(g(x)))'=f'(g(x))*g'(x)).

Endnu en stor ting fra en matematisk vinkel er at implementere potensreglen. C# har ikke nogen potens operator (^ eller ** i andre sprog), så vi skal se på ExpressionType.Call hvor metoden er Math.Pow. Den generelle potens regel er (f^g)'=f^g*(g'ln f+(g/f)*f'), men hvis g er et tal så er det den noget simplere udgave (x^n)'=n*x^(n-1):

Expression e1 = Expression.Multiply(
  me.Arguments[1], // n
  Expression.Power(
    me.Arguments[0], // x
    Expression.Subtract(me.Arguments[1], Expression.Constant(1.0)) // -1
    )
  );

dertil kommer så kædereglen:

return Expression.Multiply(e1, me.Arguments[0].Derive(parameterName));

Bemærk, at Expression.Power(...) funktionen giver os ExpressionType.Power, så hvis resultat skal differentieres igen, så skal vi også tage højde for det. Alternativt kan man benytte Expression.Call med metoden me.Method.

Det skulle være lidt til at komme igang med noget differentialregning. Heldigvis skal man "bare" følge nogle matematiske regler for at få resultatet - som måske kræver en del simplifisering for at se pænt ud, men kompileren dømmer os ikke på skønhed.