Expressiestructuren vertalen

In dit artikel leert u hoe u elk knooppunt in een expressiestructuur bezoekt terwijl u een gewijzigde kopie van die expressiestructuur bouwt. U vertaalt expressiestructuren om inzicht te hebben in de algoritmen, zodat deze in een andere omgeving kunnen worden vertaald. U wijzigt het algoritme dat is gemaakt. U kunt logboekregistratie, onderscheppingsmethode-aanroepen toevoegen en deze bijhouden of andere doeleinden.

De code die u bouwt om een expressiestructuur te vertalen, is een uitbreiding van wat u al hebt gezien om alle knooppunten in een boomstructuur te bezoeken. Wanneer u een expressiestructuur vertaalt, gaat u naar alle knooppunten en bouwt u tijdens het bezoeken de nieuwe structuur. De nieuwe structuur kan verwijzingen bevatten naar de oorspronkelijke knooppunten of nieuwe knooppunten die u in de structuur hebt geplaatst.

We gaan een expressiestructuur bezoeken en een nieuwe structuur maken met enkele vervangende knooppunten. In dit voorbeeld gaan we elke constante vervangen door een constante die 10 keer groter is. Anders laat u de expressiestructuur intact. In plaats van de waarde van de constante te lezen en te vervangen door een nieuwe constante, maakt u deze vervanging door het constante knooppunt te vervangen door een nieuw knooppunt dat de vermenigvuldiging uitvoert.

Zodra u een constant knooppunt hebt gevonden, maakt u een nieuw vermenigvuldigingsknooppunt waarvan de onderliggende elementen de oorspronkelijke constante zijn en de constante 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;
}

Maak een nieuwe structuur door het oorspronkelijke knooppunt te vervangen door de vervanging. U controleert de wijzigingen door de vervangen structuur te compileren en uit te voeren.

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);

Het bouwen van een nieuwe boomstructuur is een combinatie van het bezoeken van de knooppunten in de bestaande structuur en het maken van nieuwe knooppunten en het invoegen ervan in de structuur. In het vorige voorbeeld ziet u het belang van expressiestructuren die onveranderbaar zijn. U ziet dat de nieuwe structuur die in de voorgaande code is gemaakt, een combinatie van nieuw gemaakte knooppunten en knooppunten uit de bestaande structuur bevat. Knooppunten kunnen in beide structuren worden gebruikt omdat de knooppunten in de bestaande structuur niet kunnen worden gewijzigd. Het hergebruik van knooppunten resulteert in aanzienlijke geheugenefficiëntie. Dezelfde knooppunten kunnen in een boomstructuur of in meerdere expressiestructuren worden gebruikt. Omdat knooppunten niet kunnen worden gewijzigd, kan hetzelfde knooppunt opnieuw worden gebruikt wanneer dit nodig is.

Doorkruisen en een optellen uitvoeren

Laten we de nieuwe boom controleren door een tweede bezoeker te bouwen die de structuur van optellende knooppunten begeleidt en het resultaat berekent. Breng een paar wijzigingen aan aan de bezoeker die u tot nu toe hebt gezien. In deze nieuwe versie retourneert de bezoeker de gedeeltelijke som van de optelbewerking tot dit punt. Voor een constante expressie is dit gewoon de waarde van de constante expressie. Voor een optelexpressie is het resultaat de som van de linker- en rechteroperanden, zodra deze bomen zijn doorkruist.

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);

Er is hier nogal wat code, maar de concepten kunnen worden benaderd. Deze code bezoekt kinderen in een uitgebreide eerste zoekopdracht. Wanneer het een constant knooppunt tegenkomt, retourneert de bezoeker de waarde van de constante. Nadat de bezoeker beide kinderen heeft bezocht, hebben die kinderen de som berekend voor die substructuur. Het optelknooppunt kan nu de som berekenen. Zodra alle knooppunten in de expressiestructuur zijn bezocht, is de som berekend. U kunt de uitvoering traceren door het voorbeeld uit te voeren in het foutopsporingsprogramma en de uitvoering te traceren.

Laten we het gemakkelijker maken om te traceren hoe de knooppunten worden geanalyseerd en hoe de som wordt berekend door de structuur te doorlopen. Hier volgt een bijgewerkte versie van de statistische methode die nogal wat traceringsgegevens bevat:

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");
}

Als u deze uitvoert op de sum expressie, wordt de volgende uitvoer weergegeven:

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

Traceer de uitvoer en volg deze in de voorgaande code. U moet kunnen uitzoeken hoe de code elk knooppunt bezoekt en de som berekent terwijl deze door de structuur gaat en de som vindt.

Laten we nu eens kijken naar een andere uitvoering, met de expressie die wordt gegeven door sum1:

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

Hier volgt de uitvoer van het onderzoeken van deze expressie:

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

Hoewel het laatste antwoord hetzelfde is, is de doorkruising van de structuur anders. De knooppunten worden in een andere volgorde gereisd, omdat de structuur is samengesteld met verschillende bewerkingen die eerst plaatsvinden.

Een gewijzigde kopie maken

Maak een nieuw consoletoepassingsproject . Voeg een using instructie toe aan het bestand voor de System.Linq.Expressions naamruimte. Voeg de AndAlsoModifier klasse toe aan uw project.

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);
    }
}

Deze klasse neemt de ExpressionVisitor klasse over en is gespecialiseerd in het wijzigen van expressies die voorwaardelijke AND bewerkingen vertegenwoordigen. Deze bewerkingen worden gewijzigd van een voorwaardelijk AND in een voorwaardelijk OR. De klasse overschrijft de VisitBinary methode van het basistype, omdat voorwaardelijke AND expressies worden weergegeven als binaire expressies. Als in de VisitBinary methode de expressie die aan de expressie wordt doorgegeven een voorwaardelijke AND bewerking vertegenwoordigt, wordt met de code een nieuwe expressie gemaakt die de voorwaardelijke OR operator bevat in plaats van de voorwaardelijke AND operator. Als de expressie waaraan wordt doorgegeven VisitBinary geen voorwaardelijke AND bewerking vertegenwoordigt, wordt de methode uitgesteld tot de implementatie van de basisklasse. De basisklassemethoden maken knooppunten die lijken op de expressiestructuren die worden doorgegeven, maar de knooppunten hebben hun substructuren vervangen door de expressiestructuren die recursief door de bezoeker worden geproduceerd.

Voeg een using instructie toe aan het bestand voor de System.Linq.Expressions naamruimte. Voeg code toe aan de Main methode in het Program.cs-bestand om een expressiestructuur te maken en door te geven aan de methode waarmee deze wordt gewijzigd.

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"))
*/

Met de code wordt een expressie gemaakt die een voorwaardelijke AND bewerking bevat. Vervolgens wordt een exemplaar van de AndAlsoModifier klasse gemaakt en wordt de expressie doorgegeven aan de Modify methode van deze klasse. Zowel de oorspronkelijke als de gewijzigde expressiestructuren worden uitgevoerd om de wijziging weer te geven. Compileer de toepassing en voer deze uit.

Meer informatie

In dit voorbeeld ziet u een kleine subset van de code die u zou bouwen om de algoritmen te doorlopen en te interpreteren die worden vertegenwoordigd door een expressiestructuur. Lees deze reeks door Matt Warren voor informatie over het bouwen van een bibliotheek voor algemeen gebruik die expressiestructuren vertaalt in een andere taal. Het gaat uitgebreid in op het vertalen van een code die u in een expressiestructuur kunt vinden.

U hebt nu de ware kracht van expressiestructuren gezien. U bekijkt een set code, breng eventuele wijzigingen aan die code aan en voer de gewijzigde versie uit. Omdat de expressiestructuren onveranderbaar zijn, maakt u nieuwe bomen met behulp van de onderdelen van bestaande bomen. Het hergebruik van knooppunten minimaliseert de hoeveelheid geheugen die nodig is om gewijzigde expressiestructuren te maken.