[Programming/C#] Expression Tree

자료 구조에서 말하는 이진 트리 자료 구조라고 생각하면 된다. 각 노드는 부모-자식 관계로 연결된다. 뿌리가 되는 노드를 루트(Root) 노드라고 하며 루트로부터 뻗어 나온 노드 중 가장 끝에 있는 노드를 잎(Leaf) 노드, 또는 단말(Terminal) 노드라고 한다.

평범한 트리 자료 구조에서는 부모 노드가 여러 개의 자식 노드를 가질 수도 있지만, 식 트리는 한 부모 노드가 단 두 개만의 자식 노드를 가질 수 있는 "이진 트리(Binary Tree)"이다.

식 트리(Expression Tree)란, 식을 트리로 표현한 자료 구조를 말한다.

예를 들어 1 * 2 + (7 - 8) 이라는 식을 식 트리로 표현하면 다음과 같다.

식 트리

식 트리에서 연산자는 부모 노드가 되며, 피연산자는 자식 노드가 된다. 위의 그림을 보면 1 * 2에서 *는 부모 노드, 1과 2는 *의 자식 노드가 되었다. 7-8도 마찬가지다. -가 부모 노드, 7과 8은 각각 자식 노드가 되었다.
같은 원리로 1*2+(7-8)은 +연산자가 부모 노드, 피연산자인 1*2와 7-8은 +의 자식 노드이다. 이렇게 식 트리로 표현된 식은 트리의 잎 노드부터 계산해서 루트까지 올라가면 전체 식의 결과를 얻을 수 있다.

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

식 트리를 다루는데 필요한 클래스들은 .NET 프레임워크의 System.Linq.Expressions 네임스페이스 안에 준비되어 있다. 바로 "Expression 클래스와 파생 클래스들"이다.

Expression의 파생 클래스	설명
BinaryExpression	이항 연산자(+, -, *, /, %, &, |, ^, <<, >>, &&, ||, ==, !=, >, >=, <, <=)를 갖는 식을 표현한다.
BlockExpression	변수를 정의할 수 있는 식을 갖는 블록을 표현한다.
ConditionalExpression	조건 연산자가 있는 식을 나타낸다.
ConstantExpression	상수가 있는 식을 나타낸다.
DefaultExpression	형식(type)이나 비어 있는 식의 기본값을 표현한다.
DynamicExpression	동적 작업을 나타낸다.
GotoExpression	return, break, continue, goto와 같은 점프문을 나타낸다.
IndexExpression	배열의 인덱스 참조를 나타낸다.
InvocationExpression	대리자나 람다식 호출을 나타낸다.
LabelExpression	레이블을 나타낸다.
LambdaExpression	람다식을 나타낸다.
ListInitExpression	컬렉션 이니셜라이저가 있는 생성자 호출을 나타낸다.
LoopExpression	무한 루프를 나타낸다. 무한 루프는 break문을 이용해서 종료할 수 있다.
MemberExpression	객체의 필드나 속성을 나타낸다.
MemberInitExpression	생성자를 호출하고 새 객체의 멤버를 초기화하는 동작을 나타낸다.
MethodCallExpression	메소드 호출을 나타낸다.
NewArrayExpression	새 배열의 생성과 초기화를 나타낸다.
NewExpression	생성자 호출을 나타낸다.
ParameterExpression	명명된 매개 변수를 나타낸다.
RuntimeVariablesExpression	변수에 대한 런타임 읽기/쓰기 권한을 제공한다.
SwitchExpression	다중 선택 제어 식을 나타낸다.
TryExpression	try~catch~finally 블록을 나타낸다.
TypeBinaryExpression	형식 테스트를 비롯한 형식(type)과 식(expression)의 연산을 나타낸다.
UnaryExpression	단항 연산자를 갖는 식을 나타낸다.

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

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

팩토리 메소드

팩토리 메소드(Factory Method) 는 클래스의 인스턴스를 생성하는 일을 담당하는 메소드를 가리키는 용어이다. C#에는 객체를 생성하는 생성자 메소드가 있지만 가끔은 이것만으로 충분하지 않을 때가 있다. 객체의 생성에 복잡한 논리가 필요한 경우, 객체 생성 과정을 별도의 메소드에 구현해 놓으면 코드의 복잡도를 상당히 줄일 수 있다. Expression 클래스의 정적 팩토리 메소드들은 Expression 클래스의 파생 클래스인 ConstantExpression, BinaryExpression 클래스 등의 인스턴스를 생성하는 기능을 제공함으로써 수고를 줄여준다.

예를 들어 상수를 표현하는 ConstantExpression 객체 하나와 매개 변수를 표현하는 ParameterExpression 객체 하나를 선언하고, 이 둘에 대해 덧셈연산을 수행하는 BinaryExpression 객체를 선언한다고 해보자. 물론 이들 객체들은 Expression 클래스의 팩토리 메소드를 통해 생성할 것이다.

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

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

ConstantExpression, ParameterExpression, BinaryExpression 은 모두 Expression의 파생 클래스들이다. 그렇기에 Expression 형식의 참조를 통해 가리킬 수 있다. 덕분에 사용자는 각 노드가 어떤 타입인지 신경 쓰지 않고 거침없이 Expression 형식의 참조를 선언해서 사용할 수 있다. 필요한 경우 세부 형식으로 형 변환을 거치면 된다. 이것이 팩토리 메소드 패턴의 매력이다.

식 트리는 결국 "식"을 트리로 표현한 것에 불과하다. 위의 exp는 실행가능한 상태가 아니고 그저 "데이터" 상태에 머물러 있다. exp가 자신의 트리 자료 구조 안에 정의되어 있는 식을 실행할 수 있으려면 람다식으로 컴파일되어야 한다. 
람다식으로의 컴파일은 다음과 같이 Expression<TDelegate> 클래스를 이용한다. 

Expression const1 = Expression.Constant(1);
Expression param1 = Expression.Parameter(typeof(int), "x");

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

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 = 2 이면 1 + 2 이므로 3을 출력
Console.WriteLine(comiledExp(3));

Expression 예제

using System;
using System.Linq.Expressions;

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

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

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

            // x - y
            Expression rightExp = Expression.Subtract(param1, param2);

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

            // 람다식 클래스의 파생 클래스인 Expression<TDelegate>를 사용
            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 test
{
    internal class Program
    {
        public 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)}");
        }
    }
}


/* 결과

1 * 2 + (7 - 8) = 1

*/

지금까지 살펴본 것처럼, 식 트리는 코드를 "데이터"로써 보관할 수 있다. 이것은 파일에 저장할 수도 있고 네트워크를 통해 다른 프로세스에 전달할 수도 있다. 심지어 코드를 담고 있는 식 트리 데이터를 데이터베이스 서버에 보내서 실행시킬 수도 있다. 
데이터베이스 처리를 위한 식 트리는 LINQ(Language INtegrated Query) 에서 사용된다.