Kifejezésfák fordítása

Ebből a cikkből megtudhatja, hogyan látogathatja meg a kifejezésfában lévő csomópontokat, miközben a kifejezésfának egy módosított példányát készíti el. A kifejezésfákat lefordítva megismerheti az algoritmusokat, hogy az egy másik környezetbe is lefordítható legyen. Ön módosítja a létrehozott algoritmust. Hozzáadhat naplózást, elfoghatja a metódushívásokat, és nyomon követheti őket, vagy egyéb célokra.

A kifejezésfa fordításához létrehozott kód annak a bővítménye, amelyet már látott a fa összes csomópontjának felkereséséhez. Amikor lefordít egy kifejezésfát, az összes csomópontot felkeresi, és a meglátogatásuk során létrehozza az új fát. Az új fa tartalmazhat hivatkozásokat az eredeti csomópontokra vagy a fába helyezett új csomópontokra.

Látogassunk el egy kifejezésfára, és hozzunk létre egy új fát néhány cserecsomóponttal. Ebben a példában minden állandót helyettesítsünk 10-szer nagyobb állandóval. Ellenkező esetben a kifejezésfát érintetlenül hagyja. Ahelyett, hogy beolvassa az állandó értékét, és lecseréli egy új állandóra, ezt a cserét úgy hajtja végre, hogy az állandó csomópontot egy új csomópontra cseréli, amely elvégzi a szorzást.

Itt, ha megtalálta az állandó csomópontot, létrehoz egy új szorzási csomópontot, amelynek gyermekei az eredeti állandó és az állandó 10:

private static Expression ReplaceNodes(Expression original)
{
    if (original.NodeType == ExpressionType.Constant)
    {
        return Expression.Multiply(original, Expression.Constant(10));
    }
    else if (original.NodeType == ExpressionType.Add)
    {
        var binaryExpression = (BinaryExpression)original;
        return Expression.Add(
            ReplaceNodes(binaryExpression.Left),
            ReplaceNodes(binaryExpression.Right));
    }
    return original;
}

Hozzon létre egy új fát úgy, hogy az eredeti csomópontot lecseréli a helyettesítőre. A változtatásokat a lecserélt fa összeállításával és végrehajtásával ellenőrizheti.

var one = Expression.Constant(1, typeof(int));
var two = Expression.Constant(2, typeof(int));
var addition = Expression.Add(one, two);
var sum = ReplaceNodes(addition);
var executableFunc = Expression.Lambda(sum);

var func = (Func<int>)executableFunc.Compile();
var answer = func();
Console.WriteLine(answer);

Az új fa létrehozása a meglévő fa csomópontjainak felkeresése, új csomópontok létrehozása és a fába való beszúrásuk kombinációja. Az előző példa azt mutatja be, hogy a kifejezésfák nem módosíthatók. Figyelje meg, hogy az előző kódban létrehozott új fa az újonnan létrehozott csomópontok és a meglévő fa csomópontjainak keverékét tartalmazza. A csomópontok mindkét fán használhatók, mert a meglévő fa csomópontjai nem módosíthatók. A csomópontok újrafelhasználása jelentős memória-hatékonyságot eredményez. Ugyanazokat a csomópontokat használhatja egy fa egészében, vagy több kifejezésfában is. Mivel a csomópontok nem módosíthatók, ugyanazt a csomópontot bármikor újra felhasználhatja, amikor szükség van rá.

Bejárás és hozzáadás végrehajtása

Ellenőrizzük az új fát úgy, hogy létrehozunk egy második látogatót, aki végigvezeti az összeadási csomópontok fáját, és kiszámítja az eredményt. Végezze el néhány módosítást a látogatón, amit eddig látott. Ebben az új verzióban a látogató az összeadási művelet részleges összegét adja vissza eddig a pontig. Állandó kifejezés esetén ez egyszerűen az állandó kifejezés értéke. Egy hozzáadási kifejezés esetében az eredmény a bal és a jobb operandusok összege, miután a fák áthaladtak.

var one = Expression.Constant(1, typeof(int));
var two = Expression.Constant(2, typeof(int));
var three = Expression.Constant(3, typeof(int));
var four = Expression.Constant(4, typeof(int));
var addition = Expression.Add(one, two);
var add2 = Expression.Add(three, four);
var sum = Expression.Add(addition, add2);

// Declare the delegate, so you can call it
// from itself recursively:
Func<Expression, int> aggregate = null!;
// Aggregate, return constants, or the sum of the left and right operand.
// Major simplification: Assume every binary expression is an addition.
aggregate = (exp) =>
    exp.NodeType == ExpressionType.Constant ?
    (int)((ConstantExpression)exp).Value :
    aggregate(((BinaryExpression)exp).Left) + aggregate(((BinaryExpression)exp).Right);

var theSum = aggregate(sum);
Console.WriteLine(theSum);

Itt elég sok kód található, de a fogalmak megközelíthetők. Ez a kód először részletes kereséssel keresi fel a gyermekeket. Ha állandó csomópontba ütközik, a látogató visszaadja az állandó értékét. Miután a látogató meglátogatta mindkét gyermeket, ezek a gyerekek kiszámítják az adott részösszegre kiszámított összeget. Az összeadási csomópont mostantól kiszámíthatja az összegét. Miután a kifejezésfa összes csomópontja meg lett látogatva, a rendszer kiszámította az összeget. A végrehajtás nyomon követéséhez futtassa a mintát a hibakeresőben, és kövesse nyomon a végrehajtást.

Megkönnyítjük a csomópontok elemzésének és az összeg kiszámításának nyomon követését a fa bejárásával. Az Összesítés metódus frissített verziója, amely elég sok nyomkövetési információt tartalmaz:

private static int Aggregate(Expression exp)
{
    if (exp.NodeType == ExpressionType.Constant)
    {
        var constantExp = (ConstantExpression)exp;
        Console.Error.WriteLine($"Found Constant: {constantExp.Value}");
        if (constantExp.Value is int value)
        {
            return value;
        }
        else
        {
            return 0;
        }
    }
    else if (exp.NodeType == ExpressionType.Add)
    {
        var addExp = (BinaryExpression)exp;
        Console.Error.WriteLine("Found Addition Expression");
        Console.Error.WriteLine("Computing Left node");
        var leftOperand = Aggregate(addExp.Left);
        Console.Error.WriteLine($"Left is: {leftOperand}");
        Console.Error.WriteLine("Computing Right node");
        var rightOperand = Aggregate(addExp.Right);
        Console.Error.WriteLine($"Right is: {rightOperand}");
        var sum = leftOperand + rightOperand;
        Console.Error.WriteLine($"Computed sum: {sum}");
        return sum;
    }
    else throw new NotSupportedException("Haven't written this yet");
}

A kifejezésen való sum futtatás a következő kimenetet eredményezi:

10
Found Addition Expression
Computing Left node
Found Addition Expression
Computing Left node
Found Constant: 1
Left is: 1
Computing Right node
Found Constant: 2
Right is: 2
Computed sum: 3
Left is: 3
Computing Right node
Found Addition Expression
Computing Left node
Found Constant: 3
Left is: 3
Computing Right node
Found Constant: 4
Right is: 4
Computed sum: 7
Right is: 7
Computed sum: 10
10

Kövesse nyomon a kimenetet, és kövesse az előző kódban. Meg kell tudnia tudnia, hogy a kód hogyan látogatja meg az egyes csomópontokat, és kiszámítja az összeget, miközben végighalad a fán, és megkeresi az összeget.

Most nézzük meg a következőt sum1:

Expression<Func<int>> sum1 = () => 1 + (2 + (3 + 4));

A kifejezés vizsgálatának kimenete a következő:

Found Addition Expression
Computing Left node
Found Constant: 1
Left is: 1
Computing Right node
Found Addition Expression
Computing Left node
Found Constant: 2
Left is: 2
Computing Right node
Found Addition Expression
Computing Left node
Found Constant: 3
Left is: 3
Computing Right node
Found Constant: 4
Right is: 4
Computed sum: 7
Right is: 7
Computed sum: 9
Right is: 9
Computed sum: 10
10

Bár a végső válasz ugyanaz, a fa bejárása más. A csomópontok más sorrendben haladnak, mivel a fa először különböző műveletekkel lett létrehozva.

Módosított másolat létrehozása

Hozzon létre egy új konzolalkalmazás-projektet . Adjon hozzá egy direktívát using a System.Linq.Expressions névtér fájlhoz. Adja hozzá az AndAlsoModifier osztályt a projekthez.

public class AndAlsoModifier : ExpressionVisitor
{
    public Expression Modify(Expression expression)
    {
        return Visit(expression);
    }

    protected override Expression VisitBinary(BinaryExpression b)
    {
        if (b.NodeType == ExpressionType.AndAlso)
        {
            Expression left = this.Visit(b.Left);
            Expression right = this.Visit(b.Right);

            // Make this binary expression an OrElse operation instead of an AndAlso operation.
            return Expression.MakeBinary(ExpressionType.OrElse, left, right, b.IsLiftedToNull, b.Method);
        }

        return base.VisitBinary(b);
    }
}

Ez az osztály örökli az ExpressionVisitor osztályt, és a feltételes AND műveleteket képviselő kifejezések módosítására specializálódott. Ezeket a műveleteket feltételesről AND feltételesre ORmódosítja. Az osztály felülbírálja az VisitBinary alaptípus metódusát, mert a feltételes AND kifejezések bináris kifejezésként jelennek meg. VisitBinary A metódusban, ha a neki átadott kifejezés feltételes AND műveletet jelöl, a kód egy új kifejezést hoz létre, amely a feltételes OR operátort tartalmazza a feltételes AND operátor helyett. Ha az átadott VisitBinary kifejezés nem jelent feltételes AND műveletet, a metódus az alaposztály implementációjának ellenáll. Az alaposztály metódusai olyan csomópontokat hoznak létre, mint az átadott kifejezésfák, de a csomópontok alfáit lecserélik a látogató által rekurzív módon előállított kifejezésfákra.

Adjon hozzá egy direktívát using a System.Linq.Expressions névtér fájlhoz. Adjon hozzá kódot a Main metódushoz a Program.cs fájlban, hogy létrehozhasson egy kifejezésfát, és átadhassa azt a módosító metódusnak.

Expression<Func<string, bool>> expr = name => name.Length > 10 && name.StartsWith("G");
Console.WriteLine(expr);

AndAlsoModifier treeModifier = new AndAlsoModifier();
Expression modifiedExpr = treeModifier.Modify((Expression)expr);

Console.WriteLine(modifiedExpr);

/*  This code produces the following output:

    name => ((name.Length > 10) && name.StartsWith("G"))
    name => ((name.Length > 10) || name.StartsWith("G"))
*/

A kód létrehoz egy feltételes AND műveletet tartalmazó kifejezést. Ezután létrehozza az AndAlsoModifier osztály egy példányát, és átadja a kifejezést az Modify osztály metódusának. A rendszer az eredeti és a módosított kifejezésfákat is megjeleníti a módosítás megjelenítéséhez. Állítsa össze és futtassa az alkalmazást.

További információ

Ez a minta a kód egy kis részhalmazát mutatja be, amelyet a kifejezésfa által képviselt algoritmusok megfordítására és értelmezésére hozna létre. A kifejezésfákat egy másik nyelvre fordító általános célú könyvtár létrehozásával kapcsolatos információkért olvassa el Matt Warren sorozatát . Részletesen bemutatja, hogyan fordíthatja le a kifejezésfában található kódokat.

Most már látta a kifejezésfák valódi erejét. Megvizsgál egy kódkészletet, végrehajtja a kód módosításait, és végrehajtja a módosított verziót. Mivel a fák kifejezés nem módosítható, új fákat hozhat létre a meglévő fák összetevőinek használatával. A csomópontok újrafelhasználása minimálisra csökkenti a módosított kifejezésfák létrehozásához szükséges memória mennyiségét.