식 트리 변환
이 문서에서는 식 트리의 각 노드를 방문하고 해당 식 트리의 수정된 복사본을 작성하는 방법을 알아봅니다. 다른 환경으로 변환할 수 있도록 식 트리를 변환하여 알고리즘을 이해합니다. 생성된 알고리즘을 변경합니다. 로깅을 추가하고, 메서드 호출을 가로채고, 추적하거나, 다른 용도로 사용할 수 있습니다.
식 트리를 변환하기 위해 작성하는 코드는 트리의 모든 노드를 방문하기 위해 이미 살펴본 코드의 확장입니다. 식 트리를 변환할 때는 모든 노드를 방문하고 노드를 방문하는 동안 새 트리를 작성합니다. 새 트리에는 원래 노드에 대한 참조 또는 트리에 배치한 새 노드가 포함될 수 있습니다.
식 트리를 방문하여 일부 대체 노드가 있는 새 트리를 만들어 보겠습니다. 이 예제에서는 특정 상수를 10배 더 큰 상수로 대체합니다. 그러지 않으면 식 트리를 그대로 유지합니다. 상수의 값을 읽고 새 상수로 대체하는 대신 곱하기를 수행하는 새 노드로 상수 노드를 대체하여 이를 대체합니다.
여기에서 상수 노드를 찾은 다음에는 자식이 원래 상수 및 상수 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;
}
원래 노드를 대체 노드로 바꿔 새 트리를 만듭니다. 대체된 트리를 컴파일하고 실행하여 변경 내용을 확인합니다.
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);
새 트리 작성은 기존 트리의 노드를 방문하고 새 노드를 만들어 트리에 삽입하는 작업의 조합니다. 이전 예제에서는 변경할 수 없는 식 트리의 중요도를 보여 줍니다. 이전 코드에서 만든 새 트리에는 새로 만든 노드와 기존 트리의 노드가 함께 포함됩니다. 기존 트리의 노드를 수정할 수 없으므로 두 트리에서 노드를 사용할 수 있습니다. 노드를 다시 사용하면 상당한 메모리 효율성이 발생합니다. 트리 전체 또는 여러 식 트리에서 같은 노드를 사용할 수 있습니다. 노드는 수정할 수 없기 때문에 필요할 때마다 같은 노드를 다시 사용할 수 있습니다.
추가 트래버스 및 실행
추가 노드의 트리를 이동하고 결과를 계산하는 두 번째 방문자를 작성하여 확인해 보겠습니다. 지금까지 본 방문자를 몇 가지 수정합니다. 이 새 버전에서 방문자는 이 지점까지 더하기 작업의 부분합을 반환합니다. 상수 식의 경우 단순히 상수 식의 값입니다. 더하기 식의 경우 해당 트리가 트래버스된 후의 결과는 왼쪽 및 오른쪽 피연산자의 합계입니다.
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);
코드는 상당히 많지만 개념은 쉽게 이해할 수 있습니다. 이 코드는 깊이 우선 검색으로 자식을 방문합니다. 상수 노드가 나타나면 방문자는 상수의 값을 반환합니다. 방문자가 두 자식을 방문한 후에 자식은 해당 하위 트리에 대해 계산된 합계를 계산합니다. 이제 더하기 노드에서 해당 합계를 컴퓨팅할 수 있습니다. 식 트리의 모든 노드를 방문하면 합계가 계산됩니다. 디버거에서 샘플을 실행하고 실행을 추적하여 실행을 추적할 수 있습니다.
노드가 분석되는 방법 및 트리를 트래버스하여 합계를 계산하는 방법을 더 쉽게 추적할 수 있도록 만들어 보겠습니다. 다음은 매우 많은 추적 정보를 포함하는 집계 메서드의 업데이트된 버전입니다.
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");
}
sum 식에서 이 메서드를 실행하면 다음과 같이 출력됩니다.
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
출력을 추적하고 이전 코드에서 따릅니다. 코드가 트리를 이동하고 합계를 찾을 때 각 노드를 방문하고 합계를 계산하는 방법을 이해할 수 있어야 합니다.
이제 sum1에 지정된 식을 사용하여 다른 실행을 살펴보겠습니다.
Expression<Func<int>> sum1 = () => 1 + (2 + (3 + 4));
이 식을 검사한 출력은 다음과 같습니다.
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
최종 해답은 같지만 트리 탐색은 다릅니다. 먼저 발생하는 다른 작업으로 트리가 생성되었기 때문에 다른 순서로 노드를 이동합니다.
수정된 복사본 만들기
콘솔 애플리케이션 프로젝트를 새로 만듭니다. System.Linq.Expressions 네임스페이스에 대한 using 지시문을 파일에 추가합니다. 프로젝트에 AndAlsoModifier 클래스를 추가합니다.
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);
}
}
이 클래스는 ExpressionVisitor 클래스를 상속하며, 조건부 AND 작업을 나타내는 식을 수정하도록 특수화되었습니다. 해당 작업을 조건부 AND에서 조건부 OR로 변경합니다. 조건부 AND 식은 이진 식으로 표현되기 때문에 클래스는 기본 형식의 VisitBinary 메서드를 재정의합니다. VisitBinary 메서드에서 전달된 식이 조건부 AND 작업을 나타내는 경우 코드는 조건부 AND 연산자 대신 조건부 OR 연산자가 포함된 새 식을 생성합니다. VisitBinary에 전달된 식이 조건부 AND 작업을 나타내지 않는 경우 메서드는 기본 클래스 구현을 따릅니다. 기본 클래스 메서드는 전달된 식 트리와 유사한 노드를 생성하지만 노드의 하위 트리가 방문자에 의해 재귀적으로 생성된 식 트리로 바뀌었습니다.
System.Linq.Expressions 네임스페이스에 대한 using 지시문을 파일에 추가합니다. Program.cs 파일의 Main 메서드에 코드를 추가하여 식 트리를 만들고 이 식 트리를 수정할 메서드에 전달합니다.
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"))
*/
코드에서 조건부 AND 작업이 포함된 식을 만듭니다. 그런 다음 AndAlsoModifier 클래스 인스턴스를 만들고 이 클래스의 Modify 메서드에 식을 전달합니다. 원본 및 수정된 식 트리가 둘 다 출력되어 변경 내용을 표시합니다. 애플리케이션을 컴파일하고 실행합니다.
자세한 정보
이 샘플에서는 식 트리로 표시되는 알고리즘을 트래버스하고 해석하기 위해 작성하는 코드의 작은 하위 집합을 보여 줍니다. 식 트리를 다른 언어로 번역하는 범용 라이브러리를 빌드하는 방법에 대한 자세한 내용은 Matt Warren의 이 시리즈를 참조하세요. 이 시리즈는 식 트리에서 찾을 수 있는 코드를 변환하는 방법에 대해 상세히 설명합니다.
이제 식 트리의 진정한 기능을 살펴보았습니다. 코드 집합을 검사하고, 해당 코드를 원하는 대로 변경하고, 변경된 버전을 실행합니다. 식 트리는 변경할 수 없기 때문에 기존 트리의 구성 요소를 사용하여 새 트리를 만듭니다. 노드를 다시 사용하면 수정된 식 트리를 만드는 데 필요한 메모리 양이 최소화됩니다.
.NET
피드백
출시 예정: 2024년 내내 콘텐츠에 대한 피드백 메커니즘으로 GitHub 문제를 단계적으로 폐지하고 이를 새로운 피드백 시스템으로 바꿀 예정입니다. 자세한 내용은 다음을 참조하세요. https://aka.ms/ContentUserFeedback
다음에 대한 사용자 의견 제출 및 보기