[고급문법 익히기] 14.5장 식 트리

기록은 기억을 지배한다.·2023년 7월 4일

이것이 C#이다

목록 보기

25/26

Linq를 이해 하는데 도움이 될수있는 내용입니다.

14.5 식 트리(Expression Tree)

14.5.1 트리란?

트리는 다음과 같이 노드(Node)로 구성되며, 각 노드는 서로 부모-자식 관계로 연결 됩니다.

그림에서 A,B,C,D,E,F,G는 트리를 이루는 노드이며, 최상위노드인 A를 트리의 뿌리가되는 루트(Root)노드라고 합니다.
그리고 루트로부터 뻗어나온 노드 중 가장 끝에 있는 D,E,F,G와 같은 노드를 잎(Leaf)노드, 또는 단말(Terminal)노드라고 합니다.

참고로 부모-자식관계는 A(부모) -- B(자식), B(부모) -- D(자식), C(부모) -- F(자식)과 같이 이어져있는 노드를 말합니다.

14.5.2 식 트리란?

식 트리는 한 부모 노드가 단 두개의 자식 노드를 가질수 있는 이진트리(Binary Tree)입니다.

식 트리란, 식을 트리로 표현한 자료구조를 말합니다.
예를 들어 1x2 + (7-8)이라는 식을 식 트리로 표현하면 다음과 같습니다.

식 트리에서 연산자는 부모 노드가 되며, 피연산자는 자식 노드가 됩니다.(연산자 : +-x/)(피연산자 : ex)1,2,7,8)

위와 같은 원리로
1x2 + (7-8)은 + 연산자가 부모 노드, 피연산자인 1x2와 7+8은 +의 자식 노드입니다. 이렇게 식 트리로 표현된 식은 트리의 잎 노드부터 계산해서 루트까지 올라가면 전체 식의 결과를 얻을 수 있습니다.

식 트리 자료구조는 컴파일러나 인터프리터를 제작하는 데도 응용됩니다.
컴파일러는 프로그래밍 언어의 문법을 따라 작성된 소스 코드를 분석해서 식 트리로 만든 후 이를 바탕으로 실행 파일을 만듭니다. 완전한 C# 컴파일러는 아니지만, C#은 프로그래머가 코드 안에서 직접 식 트리를 조립하고 컴파일해서 사용할 수 있는 기능을 제공합니다.
즉, 프로그램 실행 중에 동적으로 무명 함수를 만들어 사용할 수 있게 해준다 는 이야기 입니다.

코드를 트리 자료구조로 표현한 것
C#에서는 런타임에 식 트리를 생성하고 실행할 수 있음
=>프로그램 실행 중에 추가적인 코드를 생성하여 실행 가능
앞으로 배울 Linq, DLR에 사용됨
식 트리 구축에 주로 람다식을 사용함

14.5.3 Expression 클래스

식 트리를 다루는 데 필요한 클래스들은 System.Linq.Expression 네임 스페이스 안에 준비되어있습니다. 바로 Expression 클래스와 파생클래스들 입니다.

이 표의 클래스들은 Expression 클래스의 파생 클래스입니다.

Expression 클래스는 식 트리를 구성하는 노드를 표현합니다.
Expression을 상속 받는 클래스들은 식 트리의 각 노드를 표현할 수 있게 됩니다.
Expression 클래스는 앞의 표에 열거된 클래스들의 객체를 생성하는 역할도 담당합니다.
Expression 클래스 자신은 abstruct로 선언되어 자신의 인스턴스는 만들 수 없지만, 파생 클래스의 인스턴스를 생성하는 정적 팩토리 메소드를 제공합니다.

팩토리 메소드란?
펙토리 메소드는 클래스의 인스턴스를 생성하는 일을 담당하는 메소드입니다. C#에는 객체를 생성하는 생성자 메소드가 있지만,
객체의 생성에 복잡한 논리가 필요한 경우, 객체 생성 과정을 별도의 메소드에 구현해놓으면 코드에 복잡도를 상당히 줄일수 있습니다.
Expression 클래스의 정적 팩토리 메소드들은 Experssion 클래스의 파생 클래스인 ConstantExpression,BinaryExpression 클래스 등의 인스턴스를 생성하는 기능을 제공 함으로써 수고를 덜어줍니다.

예를 들어서 팩토리 메소드를 사용해서
상수를 표현하는 ConstantExpression 객체와
매개변수를 표현하는 ParameterExpression 객체를 선언하고,
이 둘에 대해 덧셈 연산을 수행하는 BinaryExpression 객체를 선언합니다.

Expression const1 = Expression.Constant(1);					// 상수 1
Expression param1 = Expression.Paramter(typeof(int), "x");	// 매개변수 x

Expression exp = Expression.Add(const1, param1);			// 1 + x

팩토리 메소드를 사용하여 파생클래스 객체를 생성한것까지는 이해하였지만,
파생클래스를 담는 참조가 Expression 형식으로 선언 되었습니다.
ConstantExpression 형식같은 파생클래스 형식은 Expression을 상속하기 때문에 Expression형식의 참조를 통해 가리킬수 있습니다.

덕분에 프로그래머는 각 노드가 어떤 타입인지 신경 쓰지 않고 Expression 형식의 참조를 선언해서 사용할 수 있습니다. 필요한 경우에는 각 세부 형식으로 형식 변환을 하면 되니까요.
이것이 팩토리 메소드 패턴의 매력입니다.

14.5.3 식 트리 람다식으로 컴파일 하기

아무튼

식 트리는 결국 식을 트리로 표현한 것에 불과합니다.
앞에 exp는 아직 실행 가능한 상태가 아니고 그저 데이터 상태에 머물러있습니다.
exp가 자신의 트리 자료구조 안에 정의된 식을 사용할 수 있으려면 람다식으로 컴파일 되어야 합니다.

람다식으로 컴파일은 다음과 같이 Expression< TDelegate > 클래스를 이용합니다.
(Expression< TDelegate >)는 앞의 표에도 나타나 있는 LambdaExpression 클래스의 파생 클래스입니다.

Expression cost1 = Expression.Constant(1);					// 상수 1
Expression param1 = Expression.Parameter(typeof(int),"x");	// 매개변수 x

Expression exp = Expression.Add(const1,param1);

//람다식 클래스의 파생 클래스인 Expression<TDelegate>를 사용합니다.
Expression<Func<int,int>> lambda1 = 
    Expression<Func<int,int>>.Lambda<Func<int,int>>(
        exp,new ParameterExpression[]{
            (ParameterExpression)param1 });
        
Func<int,int> compiledExp = lambda1.Compile();				// 실행가능한 코드로 컴파일

// x = 3
Console.WriteLine(compiledExp(3));							// 컴파일한 무명 함수 실행

예제 프로그램을 만들어 보겠습니다.
다음 예제는 1*2+(x-y) 식을 코드 안에서 식 트리로 만든후, 이를 컴파일 하여 실행합니다.

using System;
using System.Linq.Expressions;

namespace UsingExpressionTree
{
    class MainApp
    {   
        static void Main(string[] args)
        {
            //1*2+(x-y)
            Expression const1 = Expression.Constant(1);
            Expression const2 = Expression.Constant(2);

            Expression leftExp = Expression.Multiply(const1,const2);    //1*2

            Expression param1 = 
                Expression.Parameter(typeof(int));  //x를 위한 변수
            Expression param2 = 
                Expression.Parameter(typeof(int));  //y를 위한 변수
            
            Expression rightExp = Expression.Subtract(param1,param2);   //x-y

            Expression exp = Expression.Add(leftExp,rightExp);

            //지금까지 exp라는 식 트리를 데이터 상태로 만들어 두었습니다.
            //exp를 람다식으로 컴파일해 보겠습니다.

            Expression<Func<int,int,int>> expression = 
                Expression<Func<int,int,int>>.Lambda<Func<int,int,int>>(
                    exp,new ParameterExpression[]{
                        (ParameterExpression)param1,
                        (ParameterExpression)param2});
                    
            Func<int,int,int> func = expression.Compile();

            //x = 7, y = 8
            Console.WriteLine($"1*2+({7}-{8}) = {func(7,8)}");   
        }
    }
}

출력
1*2+(7-8) = 1

람다식을 이용하면 더 간편하게 식 트리를 만들 수 있습니다.
다만 이 경우에는 "동적으로" 식 트리를 만들기는 어려워 집니다.
Expression 형식은 불변(Immutable)이기 때문에 인스턴스가 한번 만들어딘 후에는 변경할 수가 없기 때문입니다.

다음 예제는 람다식을 이용하여 식 트리를 만드는 예를 보여줍니다.

using System;
using System.Linq.Expressions;

namespace ExpressionTreeViaLambda
{
    internal class MainApp
    {
        static void Main(string[] args)
        {
            Expression<Func<int,int,int>> expression = 
                (a,b) => 1*2 + (a-b);
            Func<int,int,int> func = expression.Compile();
            
            // x = 7, y =8
            Console.WriteLine($"1*2+(7+8) = {func(7,8)}");
        }
    }
}