İfade ağaçlarını çevirme

Bu makalede, bu ifade ağacının değiştirilmiş bir kopyasını oluştururken bir ifade ağacındaki her düğümü ziyaret etmeyi öğreneceksiniz. Algoritmaları anlamak için ifade ağaçlarını çevirerek başka bir ortama çevrilebilmesini sağlarsınız. Oluşturulan algoritmayı değiştirirsiniz. Günlüğe kaydetme, kesme yöntemi çağrıları ekleyebilir ve bunları veya başka amaçlarla izleyebilirsiniz.

İfade ağacını çevirmek için oluşturduğunuz kod, bir ağaçtaki tüm düğümleri ziyaret etmek için gördüklerinizi gösteren bir uzantıdır. Bir ifade ağacını çevirdiğinizde, tüm düğümleri ziyaret eder ve bunları ziyaret ederken yeni ağacı oluşturursunuz. Yeni ağaç, özgün düğümlere veya ağaca yerleştirdiğiniz yeni düğümlere başvurular içerebilir.

Şimdi bir ifade ağacını ziyaret edelim ve bazı yeni düğümlerle yeni bir ağaç oluşturalım. Bu örnekte, herhangi bir sabiti 10 kat daha büyük bir sabitle değiştirelim. Aksi takdirde, ifade ağacını olduğu gibi bırakırsınız. Sabitin değerini okumak ve yeni bir sabitle değiştirmek yerine, sabit düğümü çarpmayı gerçekleştiren yeni bir düğümle değiştirerek bu değişikliği yaparsınız.

Burada sabit bir düğüm bulduğunuzda, alt öğeleri özgün sabit ve sabit 10olan yeni bir çarpma düğümü oluşturursunuz:

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

Özgün düğümü yerine yeni bir ağaç oluşturun. Değiştirilen ağacı derleyip yürüterek değişiklikleri doğrularsınız.

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

Yeni bir ağaç oluşturmak, var olan ağaçtaki düğümleri ziyaret edip yeni düğümler oluşturup bunları ağaca eklemenin bir birleşimidir. Önceki örnekte ifade ağaçlarının sabit olmasının önemi gösterilmektedir. Önceki kodda oluşturulan yeni ağacın yeni oluşturulan düğümlerle var olan ağaçtaki düğümlerin bir karışımını içerdiğine dikkat edin. Mevcut ağaçtaki düğümler değiştirilebildiğinden düğümler her iki ağaçta da kullanılabilir. Düğümlerin yeniden kullanılmaya başlanması önemli bellek verimliliklerine neden olur. Aynı düğümler bir ağaç boyunca veya birden çok ifade ağacında kullanılabilir. Düğümler değiştirilebildiğinden, gerektiğinde aynı düğüm yeniden kullanılabilir.

Ekleme geçişi yapma ve yürütme

Şimdi toplama düğümleri ağacını gösteren ve sonucu hesaplayan ikinci bir ziyaretçi oluşturarak yeni ağacı doğrulayalım. Ziyaretçiye şu ana kadar gördüğünüz birkaç değişiklik yapın. Bu yeni sürümde, ziyaretçi bu noktaya kadar toplama işleminin kısmi toplamını döndürür. Sabit ifade için bu yalnızca sabit ifadenin değeridir. Toplama ifadesi için sonuç, bu ağaçlar geçirildikten sonra sol ve sağ işlenenlerin toplamıdır.

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

Burada oldukça fazla kod var, ancak kavramlara ulaşılabilir. Bu kod, ilk aramada alt öğeleri derinlemesine ziyaret etti. Sabit bir düğümle karşılaştığında, ziyaretçi sabitin değerini döndürür. Ziyaretçi her iki çocuğu da ziyaret ettikten sonra, bu çocuklar bu alt ağaç için hesaplanan toplamı hesaplamıştır. Ekleme düğümü artık toplamını hesaplayabilir. İfade ağacındaki tüm düğümler ziyaret edildikten sonra toplam hesaplanır. Hata ayıklayıcıda örneği çalıştırarak ve yürütmeyi izleyerek yürütmeyi izleyebilirsiniz.

Şimdi ağaçtan geçiş yaparak düğümlerin nasıl çözümlendiğinden ve toplamın nasıl hesaplandığından izlemeyi kolaylaştıralım. Aşağıda, Toplama yönteminin oldukça fazla izleme bilgisi içeren güncelleştirilmiş bir sürümü bulunmaktadır:

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

İfadede çalıştırılırsa sum aşağıdaki çıkış elde edilir:

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

Çıktıyı izleyin ve önceki kodu izleyin. Kodun her düğümü nasıl ziyaret edip toplamı ağaçtan geçerken ve toplamı bulduğunda nasıl hesaplayıp hesaplayabildiğinizi öğrenebilmeniz gerekir.

Şimdi tarafından verilen sum1ifadeyle farklı bir çalıştırmaya bakalım:

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

Bu ifadeyi incelemenin çıktısı aşağıdadır:

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

Son yanıt aynı olsa da, ağaç geçişi farklıdır. Düğümler farklı bir sırada hareket edilir, çünkü ağaç önce gerçekleşen farklı işlemlerle oluşturulur.

Değiştirilmiş kopya oluşturma

Yeni bir Konsol Uygulaması projesi oluşturun. Ad alanı için System.Linq.Expressions dosyasına bir using yönerge ekleyin. sınıfını AndAlsoModifier projenize ekleyin.

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

Bu sınıf sınıfı devralır ExpressionVisitor ve koşullu AND işlemleri temsil eden ifadeleri değiştirmek için özelleşmiştir. Bu işlemleri koşulludan koşulluya ANDORdeğiştirir. Koşullu ifadeler ikili ifadeler VisitBinary olarak temsil edildiğinden, AND sınıfı temel türün yöntemini geçersiz kılar. yöntemindeVisitBinary, ona geçirilen ifade bir koşullu AND işlemi temsil ederse, kod koşullu işleç yerine AND koşullu OR işleci içeren yeni bir ifade oluşturur. geçirilen VisitBinary ifade bir koşullu AND işlemi temsil etmiyorsa, yöntem temel sınıf uygulamasına karşı gelir. Temel sınıf yöntemleri, geçirilen ifade ağaçları gibi düğümler oluşturur, ancak düğümlerin alt ağaçlarının yerine ziyaretçi tarafından özyinelemeli olarak üretilen ifade ağaçları kullanılır.

Ad alanı için System.Linq.Expressions dosyasına bir using yönerge ekleyin. bir ifade ağacı oluşturmak ve bunu değiştiren yönteme geçirmek için Program.cs dosyasındaki yöntemine kod Main ekleyin.

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

Kod, koşullu AND işlem içeren bir ifade oluşturur. Ardından sınıfının bir örneğini AndAlsoModifier oluşturur ve ifadeyi bu sınıfın yöntemine Modify geçirir. Değişikliği göstermek için hem özgün hem de değiştirilmiş ifade ağaçları çıkarılır. Uygulamayı derleyin ve çalıştırın.

Daha fazla bilgi edinin

Bu örnek, bir ifade ağacı tarafından temsil edilen algoritmaları çapraz geçiş yapmak ve yorumlamak için oluşturacağınız kodun küçük bir alt kümesini gösterir. İfade ağaçlarını başka bir dile çeviren genel amaçlı bir kitaplık oluşturma hakkında bilgi için Matt Warren'ın bu serisini okuyun. İfade ağacında bulabileceğiniz kodlardan herhangi birinin nasıl çevrildiği hakkında ayrıntılı bilgi içerir.

İfade ağaçlarının gerçek gücünü gördünüz. Bir kod kümesini inceler, bu kodda istediğiniz değişiklikleri yapar ve değiştirilen sürümü yürütürsiniz. İfade ağaçları sabit olduğundan, mevcut ağaçların bileşenlerini kullanarak yeni ağaçlar oluşturursunuz. Düğümlerin yeniden kullanılması, değiştirilmiş ifade ağaçları oluşturmak için gereken bellek miktarını en aza indirir.