- 아아... 이거슨 Love Story.

오늘 말씀드릴 내용은 DLR이 왜 Expression Tree(이하 표현나무)를 처음에는 박대하다가 나중에 가서는 "역시 난 니가 아니면 안되나봐 ㅠ_ㅠ"같은 대사를 날리게 되는지 Jim Hugunin의 증언을 통해서 알려드리고자 합니다. 그럼 지금부터 달콤 쌉싸름하고 무슨말인지도 잘 모르겠는 러브스토리를 한번 감상해보시져.


- 누군가가 필요하긴 했어. 하지만 너 아닌 다른 나무라도 괜찮을 거 같았어.

 지난 시간에 말씀드렸듯이 C# 3.0에 표현나무가 추가된 이유는 쿼리가 실행되는 곳이 어디냐에 따라서 최적화를 하기 위해서 컴파일된 IL코드의 형태보다는 자료구조의 형태가 훨씬 수월하기 때문이었습니다. 그리고 DLR은 닷넷 프레임워크에서 실행되는 동적 언어들이 공동으로 사용할 수 있는 기반을 제공해주고, 각 언어들끼리 그리고 정적언어들과도 서로 대화를 주고 받을 수 있도록 해주기 위한 장치인데요. 그렇다면, 언어별로 내부적인 구현의 차이점이 있을 수 있겠고 한 언어에서 작성한 코드를 다른 언어에서도 사용가능하려면, 둘 사이에 변환과정이 있어야 하겠고 그 변환과정을 수월하게 해줄 수 있는 도구가 필요하겠죠. 어떤 가요? DLR과 표현나무의 러브스토리의 윤곽이 좀 잡히시나요?

Jim Hugunin에 따르면 애초에 DLR을 설계할때 코드를 표현할 공통자료구조로 트리형태를 생각하고 있었다고 합니다. 그리고 타입이 없으면서 런타임에 late-bound되는 노드들로 구성된 트리로 구현을 시작했다고 합니다.  그래서 그 당시에 IronPython에 맞게 구현된 트리에는 타입이 있는 노드가 ConstantExpression딱 하나였다고 합니다. 상수 값이면 뭐든지 가지고 있는 노드 말이죠. 그리고 자신들이 생각하고 있는 트리와 표현나무 사이에는 공통점이 없다고 생각했었다고 합니다. 왜냐면 정적언어에서 쓰는 게 동적언어에는 안 맞을거라고 생각했기 때문이라는 군요. 그래서 독립적으로 트리를 구성해 나갔다고 하네요.


- 하지만, 다른 나무들을 만날 수록 니가 그립더라.

하지만, 다른 언어의 구현을 추가하면서, 기존의 DLR트리에 각 언어의 특징을 제대로 표현하기 힘들어졌다고 하는군요. 각 언어의 특징을 지원하기 위한 방법이 필요한데, 그렇다고 해서 직접적으로 그 언어의 특징을 위한 노드를 추가할 수 는 없었다네요. 아마도 DLR트리는 DLR에서 도는 언어들이 공통적으로 공유하게되는 자료구조인데, 특정언어에만 있는 노드를 추가하면, 점점 지저분해 지기 때문이겠죠.

예를 들면, Python의 print문을 보면, 내부적으로 print문은 Python에서 출력에 대한 걸 어떻게 처리할지에 대해 알고 있는 static 메서드를 호출한다고 하는군요. 그래서 DLR트리에 static 메서드 호출노드를 추가했다고 합니다. 그러면 print호출은 static 메서드를 호출하는 걸로 연결할 수 있으니까요.

그리고 이런 작업을 하다보니깐, 그동안 개발팀이 추가해오던 노드들이 정적인 타입이 적용되는 표현나무의 각 노드랑 딱 들어맞는 다는 걸 깨달았다고 합니다. 그래서 처음부터 다시 만드는 대신에 기존에 잘 쓰고 있는 걸 확장하자고 마음을 먹었고, 기존의 표현나무에 동적인 연산이나 변수, 이름 바인딩, 흐름제어등을 위한 노드를 추가했다고 합니다.

그리고 DLR에서 동작하는 언어가 이런 트리형태를 만들어 내게 되면서 각각의 언어에 맞는 최적화를 수행하는게 수월해졌습니다. 지난 포스트에서 설명드렸던 표현나무를 사용하면서 얻는 장점과 매우 동일한 점입니다. 그래서 각 언어의 컴파일러는 코드를 표현나무의 형태로 만들어서 그 표현나무를 DLR에게 전해준다고 하는 군요.


- 그들은 현재 잘 살고 있답니다.

Jim Hugunin의 PDC2008의 "Dynamic Languages In Microsoft .NET"의 슬라이드를 통해서 각 언어별로 나타나는 표현나무의 모양을 보도록 하겠습니다.

C#에서 구현한 팩토리얼을 표현나무로 옮긴다면 아래와 같다고 하는군요.



그리고 이걸 dynamic을 써서 C#에서 작성하면 아래와 같다고 합니다. 붉은 색으로 변화가 있는 부분이 있죠? 이 부분이 동적인 타입을 적용한 부분인데요, 즉 "==", "*", "-"같은 DLR의 표준메세지 객체를 이용해서 모든 언어에서 사용가능하도록 하면서 C#에서 왔다는 걸 표시해서 C# 바인더를 사용할 수 있게 한다고 합니다.



1과 2를 비교해보시면 어떤 노드가 추가됐는지 확일 할 수 있군요. 그리고 동일한 코드로 IronPython에서 만든 표현나무는 아래와 같습니다.



C#대신에 Python바인더를 사용하고 있구요, 메서드 호출부분에서 global field를 참조하는 부분이 있는데요, 이 부분은 닷넷의 프로퍼티를 통한 static field와 거의 완벽하게 들어 맞는다고 하는군요. 그래서 약간의 코드만 추가하면 된다고 합니다. 그리고 아래는 루비의 표현나무입니다.



루비는 함수형언어 개념의 표현식을 기반으로 하는데요 구문이라는게 없고 모든 루비의 코드 한라인 한라인은 값을 리턴하는 구조라고 하는군요. 그래서 return 같은 구문을 안써도 되므로 표현나무와 자연스럽게 어울린다는 군요.

즉, 각 언어에서 나온 트리가 모양이 조금씩 다르긴 한데 전체적으로 비슷한 구조를 유지하고 있습니다. 이런 각 언어에서 나온 표현나무를 분석해서 모든 트리에서 공유하는 폼으로 만들 수 있다는 군요. 아직 어떻게 정확하게 그렇게 할 수 있는지는 명확하게 설명된게 없어서(혹은 제가 못찾아서-_-, 제가 몰라서-_-) 더 설명드리기는 조금 힘들거 같군요.


- 마치면서

확실히 제게는 조금 벅찬 주제일 수도 있지만, 제가 이해한 범위내에서 최대한 명쾌하게 설명드리려고 노력했습니다. 하지만 틀린부분이 있을 수 있겠죠. 그렇다면 여러분의 지식을 공유하시면서 따쓰한 피드백을 주시기 발합니다. 캬캬캬....


- 참고자료

1. http://blogs.msdn.com/hugunin/archive/2007/05/15/dlr-trees-part-1.aspx
2. http://channel9.msdn.com/pdc2008/TL10/

신고
크리에이티브 커먼즈 라이선스
Creative Commons License

- 럭키 세븐 -_-v

기분도 좋게 일곱번째 글이 되는 오늘은 아낌없이 표현해주는 나무, expresion tree를 가지고 이야기 해보도록 하겠습니다. LINQ의 뒤를 든든하게 받치고 있는 요소지만, 전면에 거의 드러나지 않아서 이게 뭔지 알아보려고 노력안하면 볼일이 없는 친구입니다. 저 역시 LINQ로 프로젝트를 진행하면서도 얉은 지식과 호기심으로 인해서 이런게 있다는 것도 모르고 있었는데요. 그리고 6월에 있었던 세미나에서는 '컴파일러같은 툴 개발자들에게나 적합한 기능인거 같다'는 망언을 하기도 했었습니다. 뭐 100% 틀린 말은 아니겠지만, 이해가 부족한 탓에 나온 망언이었던거니 혹시 마음상한 분 있으셨다면 여친한테 밴드라도 붙여달라고 하시면 좋을거 같네요. 여친없으시면 어머니한테라도...


- 표현해주는 나무나 빨랑 설명해봐

일단 expression tree는 실행가능한 코드를 데이터로 변환가능한 방법을 제공해주는 요소입니다. 이렇게 데이터로 변환하게 되면 컴파일하기 전에 코드를 변경한다거나 하는 일이 매우 수월해지는데요. 예를 들면, C#의 LINQ 쿼리식을 sql 데이터베이스같이 다른 프로세스상에서 수행하는 코드로 변환하는 경우 말이죠.

Func<int, int, int> function = (a, b) => a + b;

위와 같은 문장은 머리,가슴,배는 아니지만 세부분으로 구성됩니다.

1. 선언부 : Func<int, int, int> function
2. 등호 연산자 : =
3. 람다 식 : (a, b) => a + b;

현재 변수 function은 두 숫자를 받아서 어떻게 더하는지를 나타내는 코드를 참조하고 있습니다. 그리고 위의 람다 표현식을 메서드로 표현해본다면 대략 아래와 같은 모양이 되겠죠.

public int function(int a, int b)
{
    return a + b;
}

Func는 System네임스페이스에 아래와 같이 선언되어 있습니다.

public delegate TResult Func<in T1, in T2, out TResult>(T1 arg1, T2 arg2); 

이 선언이 우리가 두개의 숫자를 더하는 간단한 람다식을 선언하는 걸 도와준 셈이죠.


- 근데, 어케 코드에서 표현해주는 나무로...?

위에서 우리는 실행가능한 코드를 function이라는 변수를 통해서 참조할 수 있다는걸 봤습니다. 근데, expression tree는 실행가능한 코드나 아니고, 자료구조의 한 형태입니다. 그러면, 어떻게 표현식을(코드를) expression tree로 변환하는 걸까요? 그래서 LINQ가 좋은걸 준비해뒀습니다.

using System.Linq.Expressions;

....

Expression<Func<int, int, int>> expression = (a, b) => a + b; 

위와 같이만 하면, 람다식이 expression tree로 쑉~! 하고 변환이 됩니다. 그럼 이걸 좀 더 눈에 보이게 살펴볼까요? 여기에 가시면, C#으로 구현된 예제들을 받을 수 있는데요, 예제중에 ExpressionTreeVisualizer(이하, ETV)라는게 있습니다. expression tree를 TreeView컨트롤을 이용해서 보기쉽게 쪼개주는 놈이죠. (a, b) => a + b;를 한번 확인해볼까요?



위의 간단한 예제코드는, Expression<TDelegate>클래스를 사용하고 있는데요, 그 클래스의 4가지 프로퍼티를 ETV를 통해서 확인해보실 수 있습니다. 좀 더 확실하게 하기 위해서 '-'를 눌러서 다 접어볼까요?



위 그림을 보시면, 딱 4가지만 남아있죠?

  • Body : expression의 몸체를 리턴한다.
  • Parameters : 람다식의 파라미터를 리턴한다.
  • NodeType : expression tree의 특정노드의 ExpressionType을 리턴한다. ExpressionType은 45가지의 값을 가진 열거형타입인데, expression tree에 속할 수 있는 모든 노드의 목록이 포함되어 있다. 예를 들면, 상수를 리턴하거나, 파라미터를 리턴한다거나, 둘 중에 뭐가 더 큰지 결정한다거나(<,>), 두 값을 더한다거나(+) 하는 것들이 있다.
  • Type : expression의 정적인 타입을 리턴한다. 위의 예제같은 경우에는 Func<int, int, int>가 되겠다.

아래와 같은 코드를 통해서 위의 프로퍼티들의 값을 확인해볼 수 있습니다.

using System;
using System.Linq.Expressions;

namespace ConsoleApplication2
{
    class Program
    {
        static void Main(string[] args)
        {
            Expression<Func<int, int, int>> expr = (a, b) => a + b;

            BinaryExpression body = (BinaryExpression)expr.Body;
            ParameterExpression left = (ParameterExpression)body.Left;
            ParameterExpression right = (ParameterExpression)body.Right;

            Console.WriteLine(expr.Body);
            Console.WriteLine("표현식의 왼쪽 : {0}\n노드의 타입 : {1}"
                + "\n표현식의 오른쪽 : {2}\n몸체의 타입 : {3}",
                left.Name, body.NodeType, right.Name, body.Type);
        }
    }
}


그리고 실행결과는 아래와 같습니다.



결과에서 expression의 모든 요소들이 각각의 노드로 이루어진 자료구조라는 것을 확인해보실 수 있습니다. 그리고 반대로 expression tree를 코드로 변환해서 실행하는 것도 매우 간단합니다. 아래와 같이 딴 한줄이면 됩니다.

int result = expr.Compile() (3,5); 


- 근데 당췌 왜 코드를 나무로 바꾸는건데? 식목일이냥?

이제 expression tree에 대해서는 조금 익숙해지셨을 겁니다. 특히 이 expression tree가 LINQ to SQL에 아주 중요한 역할을 하는데요, 일단 아래의 LINQ to SQL 쿼리문을 보시져~.

var query = from u in db.Users
     where u.nickname == "boram"
     select new { u.uId, u.nickname };


위 쿼리문의 결과로 반환되는 타입을 확인해보면 아래와 같습니다.



넵 바로 IQueryable인데요, IQueryable의 정의를 확인해보면 아래와 같습니다.

public interface IQueryable : IEnumerable
{
    Type ElementType { get; }
    Expression Expression { get; }
    IQueryProvider Provider { get; }

즉, 멤버로 Expression타입의 프로퍼티를 가지고 있습니다. IQueryable의 인스턴스는 expression tree를 가지고 있도록 설계된 거죠. 그 expressio tree가 바로 코드로 작성한 LINQ쿼리문의 자료구조입니다. 그런데, 왜 이렇게 LINQ to SQL쿼리를 expression tree형태로 가지고 있는걸까요? 그 핵심은, A라는 프로그램의 코드에 LINQ to SQL쿼리가 있다고 했을때, 실제로 이 쿼리가 수행되는 곳이 A가 아니라 데이터베이스 서버라는 점에 있습니다. 즉, 프로그램에서 직접실행되는게 아니라 데이터베이스가 알아들을 수 있는 SQL쿼리형태로 변환을 해서, 그 쿼리를 데이터베이스에게 날려서 쿼리된 데이터를 받아온다는 거죠. 위의 LINQ to SQL쿼리는 대략 아래와 같은 SQL문으로 변환이 됩니다.

SELECT [t0].[uId], [t0].[nickname]
FROM [dbo].[Users] AS [t0]
WHERE [t0].[nickname] = @p0 

프로그램내에 존재하는 쿼리표현식은 SQL 쿼리로 변환되어서 다른 프로세스에서 사용되게끔 문자열 형태로 보낸다는 거죠. 그러면, 위에서 설명드린대로 실제 쿼리는 데이터베이스의 프로세스내에서 처리가 되구요. 즉, IL코드를 SQL쿼리로 변환하는 거 보다, expression tree같은 자료구조형태가 변환하기 훨씬 쉬울뿐더러, 최적화 같은 중간처리도 훨씬 용이하다는 겁니다. 하지만 LINQ to Objects를 통해서 쿼리를 해보면 결과의 타입은 IEnumerable<T>입니다. 왜 얘네들은 IQueryable<T>가 아닐까요? IEnumerable<T>의 정의를 보면 아래와 같습니다.

public interface IEnumerable<T> : IEnumerable
{
    IEnumerator<T> GetEnumerator();

즉, Expression타입의 프로퍼티가 없습니다. 왜냐면, LINQ eo Objects는 같은 프로세스내에서 처리될 객체들을 대상으로 쿼리를 하기 때문에 다른 형태로 변환될 필요가 없기 때문입니다. 그렇다면, 굳이 expression tree같은 자료구조로 변환할 필요가 없겠죠. 그래서 대략 아래와 같은 규칙이 성립합니다.
  • 코드가 같은 프로그램(또는 프로세스)내에서 실행되는 경우라면 IEnumerable<T>
  • 쿼리 표현식을 다른 프로그램(또는 프로세스)에서 처리하기 위해서 문자열 형태로 변환해야 한다면 expression tree를 포함하는 IQueryable<T>를 사용 


- 마치면서

일단 오늘은 C# 3.0에 포함되었던 expression tree에 대해서 설명을 드렸습니다. DLR이랑 dynamic이야기 하다가 난데없이 삼천포로 빠진 느낌이 드시겠지만(저는 경남 진주에 살았었는데, 아버지 따라 삼천포 자주 갔었습니다....이 이야기는 왜하는 거지..-_-), DLR에서 expression tree가 중요하게 사용되고, 또한 C# 3.0을 사용해보신 분들이라도 expression tree에 대해서 제대로 못짚고 넘어간 분들도 많으리라 생각합니다. 저 역시 그랬구요. 아무튼, 도움되셨기를 바라면서 다음에 뵙죠!


- 참고자료

1. http://blogs.msdn.com/charlie/archive/2008/01/31/expression-tree-basics.aspx

신고
크리에이티브 커먼즈 라이선스
Creative Commons License

Welcome to Dynamic C#(6) - Return to Dynamic (2)

C# 2009.09.03 13:36 Posted by 뎡바1

- 복습.

지난시간에서 이야기 했던 부분을 조금 이어서 이야기하자면요, dynamic이라는 타입이 생겼고 이 타입은 런타임에 가서야 실제로 담고있는 타입이 뭔지 수행하고자 했던 연산이 존재하는지 등을 알 수 있습니다. 그리고 닷넷 프레임워크 내부적으로는 dynamic이라는 타입은 없으며, object타입에 dynamic 어트리뷰트가 붙어서 런타임에게 적절한 동적 연산을 수행하도록 알려주도록 하고 있었습니다. 그리고 dynamic과 관계된 연산을 만나면, 컴파일러는 DLR의 call site를 이용하는 코드를 생성하구요 DLR에 정의된 기본연산들중에 C#에 알맞도록 상속된 클래스를 생성하고 그 연산을 call site를 통해서 호출하도록 코드를 생성해줍니다.

그러면 잠깐 실제로 동적연산을 호출하면 런타임에 어떤 절차를 거치게 되는지 알아보도록 하겠습니다.


- 복습은 거기까지.

dynamic d = ......;
d.Foo(1, 2, d); 

위와 같은 코드가 실행된다고 할때 대략 아래와 같은 절차를 따르게 됩니다.

1. DLR이 사용자가 넘겨주는 매개변수의 타입(int, int, dynamic)으로 요청받은 액션(InvokeMember)이 캐시되어 있는지 확인합니다. 캐시에 저장이 되어 있다면, 캐시되어있던 걸 리턴합니다.

2. 캐시에 해당되는 내용이 없다면, DLR은 액션을 요청받는 객체가 IDynamicObject(이하 IDO)인지 확인합니다. 이 객체는 스스로 어떻게 동적으로 바인딩하는지를 알고 있는 객체입니다.(COM IDispatch object, 루비나 파이썬의 객체나 IDynamicObject 인터페이스를 구현한 닷넷 객체들 처럼). 만약 IDO라면 DLR은 IDO에게 해당 액션을 바인딩해달라고 요청합니다. IDO에게 바인딩을 요청한 뒤에 받는 결과는 바인딩의 결과를 나타내주는 expression tree입니다.

3. IDO가 아니라면, DLR은 language binder(C#의 경우는 C# runtime binder)에게 해당 액션을 바인딩해줄 것을 요청합니다. 그러면 C# runtime binder가 그 액션을 바인딩하고 바인딩의 결과를 expression tree로 리턴해줍니다.

4. 2번이나 3번이 수행된 다음엔 결과로 받은 expression tree가 DLR의 캐시속으로 통합되고 같은 형태의 요청이 다시 들어온다면 바인딩을 위한 절차를 수행하지 않고 캐시에 저장된 결과를 가지고 실행하게 됩니다.


그리고 이어서 C# runtime binder에 대해서 소개해 드릴텐데요, C# runtime binder는 무엇을 어디에 바인딩할지를 결정하는 심볼테이블을 reflection을 이용해서 생성합니다. 만약에 컴파일타임에 타입이 정해진 매개변수라면 C# 액션의 정보에 해당 타입으로 기록되고 런타임시에 바인딩될때 그 매개변수는 기록된 타입으로 사용될 수 있겠죠. 근데 만약에 컴파일 타임에 dynamic으로 결정된 매개변수라면(dynamic타입의 변수나, dynamic을 리턴하는 표현식), runtime binder는 reflection을 이용해서 그 매개변수의 타입을 알아내고, 알아낸 타입을 그 매개변수의 타입으로 사용하게 됩니다.

- 심볼테이블?

심볼테이블은 컴파일러나 인터프리터가 코드를 번역하기 위해서 사용하는 자료구조인데요. 코드의 변수명, 메서드등의 식별자를 각각 타입이나 범위, 그리고 메모리에서의 위치등을 기록합니다. 아래의 표는 위키피디아에 있는 심볼테이블의 예제인데요, 메모리의 주소와 심볼의 타입과 심볼의 이름으로 구성되어 있습니다. 

Address Type Name
00000020 a T_BIT
00000040 a F_BIT
00000080 a I_BIT
20000004 t irqvec
20000008 t fiqvec
2000000c t InitReset
20000018 T _main
20000024 t End
20000030 T AT91F_US3_CfgPIO_useB
2000005c t AT91F_PIO_CfgPeriph
200000b0 T main
20000120 T AT91F_DBGU_Printk
20000190 t AT91F_US_TxReady



runtime binder는 심볼테이블을 필요할때 필요한 만큼 만드는데요, 위의 짧은 예제에서 처럼 Foo라는 메서드를 호출하는 경우라면 runtime binder는 d의 런타임 타입에 대해서 Foo라는 이름을 가진 멤버들을 모두 로드합니다. 그리고 형변환역시 요구되는 형변환들을 모두 심볼테이블로 로드합니다. 그리고 런타임 바인더는 C# 컴파일러가 하는 것과 동일한 오버로딩 판별알고리즘을 수행합니다. 그리고 컴파일시에 받는 것과 동일한 문법을 사용하며, 동일한 에러, 동일한 예외를 출력합니다. 그리고 마지막으로 이런과정을 거친 결과를 expression tree로 생성하고 DLR에게 리턴해줍니다. 단, 여기서 사용하는 expression tree는 C# 3.0의 expression tree를 확장한 것입니다. 기존의 expression tree에 동적인 연산, 변수, 이름 바인딩, 흐름제어를 위한 노드들이 추가된 거죠.


- 마치면서

뭔가, 짧고 설명도 어색한 포스트인거 같네요;;; 이번시간을 통해서 DLR이 코드를 실행하기 위해서는 코드를 내부적으로 expression tree라는 형태로 가지고 있음을 알아봤습니다. 다음시간엔 C# 3.0에서 처음등장한 expression tree와 DLR에서 사용하는 expression tree에 대해서 설명을 드리도록 하겠습니다.


- 참고자료

1. http://blogs.msdn.com/samng/archive/2008/10/29/dynamic-in-c.aspx
2. http://en.wikipedia.org/wiki/Symbol_table

신고
크리에이티브 커먼즈 라이선스
Creative Commons License


 

티스토리 툴바