-----------------------------------------------------------------------------------------------
출처: http://zmeun.tistory.com/80
-----------------------------------------------------------------------------------------------
이 글은 나의 함수 프로그래밍(Functional Programming)에 대한 생각을 이야기하는 시리즈
글이다. 이 시리즈 글 진행 중에 여러분이 한가지 유념해야 할 것은, 나는 가급적 C# 3.0 문법 코드를
사용하지 않을 것이란 사실이다.
내가 이야기하는 함수 프로그래밍을 설명하기 위해 많은 사람들이 C# 3.0 문법을 사용하여
설명하는 것이 요즘의 트렌드이지만, 그렇다고 C# 3.0 문법을 사용하지 않고 이 내용을 설명하는 것이 틀린 것은 아니며, 이런 이유로 이 글을 읽는 독자들이 간혹 혼란스러워 할 수 도 있다.
우리들 중 몇 명(Bill Wagner를 제외하고)은 C# 3.0이 정말로 편리하다고 생각하고 있다.
그래서 아래 이어질 설명을 이해하기 위해서, 우리는 먼저 C# 3.0과 2.0 문법의 작은 차이점을
알아야 한다. 그렇기 때문에, 나는 이 글의 내용을 C# 2.0으로 소개 하려고 한다.
이 부분에 대해서 많은 개발자들이 C# 3.0에 능숙해져야만 한다는 생각하고 있지만,
나는 이(C# 2.0의) 문법들이 함수 프로그래밍의 개념을 명확하게 설명할 수 있고,
독자들이 C# 3.0의 간결해진 문법을 이해하는데 도움을 줄 것이다 라고 생각한다.
후반부에 나는 C# 3.0 문법을 소개할 것이지만 그것에 대한 개념을 설명하는 부분까지는
언급하지 않을 것이다.
이전 글에서, 나는 closure의 조금 더 자세한 내부 동작까지 소개하기로 이야기했었다.
그럼 그 전에 첫 번째로 정확히 closure가 무엇인지 다시 한번 우리의 기억을 상기시켜 보자.
What’s A Closure?
Closure는 자신의 코드 블록 상위에 선언된 코드를 포함하는 함수이다.
따라서 함수는 자신의 코드 블록이 포함되어 있는 상위 요소를 참조한다.
이 경우 C# 2.0에서는 익명 메소드(anonymous method)가 해당되고,
이 익명 메소드는 자신의 코드 블록 상위의 메소드에 포함된다.
이것은 부모 메소드에 존재하는 지역 변수를 익명 메소드의 코드 블록에 참조 할 수 있다는 것을
의미한다. 아래의 코드는 우리가 예상하는 것과 같이 콘솔 창에 0을 출력하게 된다.
|
delegate void Action(); |
대부분의 개발자들은 위 코드에 대해서 아무런 의문도 갖지 않는다.
지역변수 “x”는 선언되자마자 0으로 초기화 되었고, 그리고 나서 Action 타입의 delegate 변수
“a”가 선언 된 후, 콘솔 창에 변수 “x”를 출력하는 익명 메소드로 할당 되었다.
코드는 마지막으로 “a”를 호출하면서, 그 결과로 콘솔에 변수 “x”의 값을 출력한다.
여기에서 문제는 코드가 아래처럼 변경되었을 때 나타난다.
|
delegate void Action(); |
현재 “x”는 delegate 변수 “a”가 호출되기 이전에 값 1로 다시 할당되었다.
그렇다면 콘솔 창에 출력되는 값은 무엇일까?
정답은 0이 아니라 1이다.
이렇게 된 이유는, 익명 메소드는 closure이고 반드시 부모 메소드의 코드 블록 안에 위치해야 하며, 지역 변수를 자신의 코드 블록 안에 포함해야 한다.
중요한 차이점은 그것은 반드시 값이 아닌 변수를 참조한다는 것이다.
다른 말로 “x”의 값은 “a”가 익명 메소드로 할당 된 후에 “x”의 값이 복사되지 않고 “x”의 참조가
사용된다. 그렇기 때문에 “a”는 항상 “a”가 호출되기 전에 가장 마지막으로 할당된 “x”의 값을
사용 할 것이다. 사실 “x”의 참조는 “x”가 포함 된 코드블럭을 벗어난다 해도 지속될 것이다.
아래 코드를 살펴보자.
|
delegate void Action(); |
위 코드는 “a”가 호출되는 시점에서 변수 “x”의 실행 범위가 끝났다 하더라도, 호출된 “a”의 결과값은, 어김없이 콘솔 창에 1을 출력할 것이다. 어떻게 이렇게 되었을까? 이것은 컴파일러를 통해
처리되었다. 런타임은 closure를 처리하기 위해 아무런 지원도 하지 않는다.
이 말은 여러분은 익명 메소드의 사용 없이도 closure를 처리하기 위해 컴파일러가 처리하는 것과 같은 동일한 방법을 사용 할 수 있다는 것이다. 실제로 이 방법은 C# 1.0에서도 동작한다.
How’s It Work?
“ ‘a’가 ‘x’의 가장 마지막 값을 사용하기 위해 ‘x’를 참조해서 사용한다.”라는 내용을
앞에서 말한 것에 대해, 이 closure가 어떻게 동작했는지에 대해서 간단히 설명 드리면,
요점은 값이 아닌 참조를 사용했다는 것이다.
변수 “x”는 어떤 방법으로 스택에서 힙으로 이동된다. 그리고 이런 이동은 “x”의 사용 범위를
바깥 범위로 확대 시킨다. 그러면 변수 “x”는 참조 타입으로 boxing하지 않고서도 closure와 같이
처리할 수 있다.
이것을 가능하게 하기 위해, C# 컴파일러는 특별한 Helper 클래스를 생성한다.
변수 “x”는 이 Helper 클래스의 필드가 되고 익명 메소드는 이 클래스의 인스턴스 메소드가
되도록 할당된다. 이런 절차는 아래 코드와 같다.
|
delegate void Action(); |
“GetAction” 메소드의 처리내용은 이와 같다.
1. 메소드가 시작되는 시점에서, “ActionClosure” 클래스의 인스턴스가 생성된다.
(주의: 여기서 정확한 의미전달을 위해 “ActionClosure”와 “AnonMethod”라는 이름을 사용했지만, 실제로 컴파일러는 충돌을 방지하기 위한 명명규칙을 사용한다.)
2. “GetAction” 메소드 안의 지역 변수 “x”의 모든 참조는 “ActionClosure” 인스턴스의 필드 “x”를 참조하는 것으로 변경되었다.
3. Delegate “a”는 “ActionClosure” 인스턴스 내부에서 “AnonMethod”를 참조하는 delegate로 할당 되었다.
내가 재미있게 생각하는 점은 이 코드는 C# 1.0에서도 컴파일 된다는 것이고 익명 메소드를
사용하는 코드와 동일하게 동작한다는 것이다.
모든 컴파일러의 동작은 마치 마술 같고 C# 2.0 개발자들을 완벽하게 지원한다.
Why Do I Care?
마이크로소프트는 코드를 훌륭히 개선했고, 좀더 견고하게 만들었다.
많은 개발자들은 C# 2.0의 익명 메소드를 그리 인정하지 않는다.
왜냐하면 그들은 이 기능을 제대로 사용하지 못하고 있기 때문이다.
하지만 나중에는, 익명 메소드를 통해 그들의 스파게티 코드를 빠르게 고칠 수 있다는 것을
그리 어렵지 않게 생각할 수 있을 것이다.
그러나 나의 경험으로 많은 개발자들은 이런 것들을 쉽게 무시해 버릴 것이다.
왜냐하면, 그들은 closure가 내부적으로 얼마나 효율적으로 구동되는지를 아직 이해하지 못하고
있기 때문이다.
아래 예제코드를 한번 보자
|
static List<string> g_Names = new List<string>( |
이 예제 코드는 이름이 나열된 리스트를 생성하고 이것들을 콘솔 창에 출력한다.
이 코드는 아무런 문제없이 잘 실행된다.
그럼 이제 우리는 이 코드에서 특정 문자로 시작하는 이름을 조회해야 하는 기능이 필요하다고
가정해 보자. 이것을 구현하기는 아주 쉽다.
왜냐하면 List<T>는 편리하게도 delegate를 인자로 받아 List<T>의 각 요소에 대해 delegate가
참조하는 메소드를 실행한 결과를 다시 List<T> 형태로 리턴해주는 FildAll 메소드를 사용하면
되기 때문이다.
이렇게 추가된 코드는 아래와 같다.
|
static string g_StartingText; |
이렇게 구현된 코드는 고객이 새로운 요구사항을 추가하기 전까지는 잘 동작한다.
만약 이 코드에서 고객이 “쓰레드에 안전해야만 하오!”라고 이야기 한다면,
즉, 다중 쓰레드에서 호출 되었을 때도 유효한 값이 조회가 되어야 한다 라고 했을 경우
이것은 문제가 될 수 있다.
왜냐하면 만약 하나의 쓰레드에서 “D”로 시작하는 모든 이름을 찾아야 한다고 했는데,
다른 쓰레드에서 “D”가 아닌 다른 문자로 시작되는 코드로 이 코드를 실행한다면,
실행결과는 유효하지 못한 결과를 리턴하게 된다.
이 문제를 해결하기 위한 한가지 해결책은 “g-StartingText”를 잠금(lock) 처리하는 것이다.
이것은 확실히 쓰레드에 안전한 메소드를 만들 수 있다. 하지만 이것은 몇 가지 문제점을 가진다.
그 중 가장 큰 문제점은 쓰레드는 이 메소드에 동시적으로 접근 할 수 없을 것이다.
만약 하나의 쓰레드가 잠금(lock)을 획득했다면, 다른 모든 쓰레드는 그 쓰레드가 종료될 때까지
기다려야 한다. 다른 말로 이 메소드는 잠정적으로 병목현상을 유발할 수 있다 라고 이야기 할 수
있다.
왜냐하면 단지 하나의 쓰레드만이 이 메소드에 실시간으로 접근할 수 있고,
만약 같은 machine에 다른 프로세스가 추가된다면, 아마 추가된 프로세스는 사용할 수 없게 될
것이다.
이 문제에 대한 해결 방법은, 익명 메소드를 사용하기 위해 closure를 생성해야 하고
공유 상태를 제거해야 한다.
|
static List<string> GetNamesStartingWith(string startingText) |
익명 메소드를 통해, 이 코드는 매우 간결해졌다. 그리고 “g_Names”가 절대 변경되지 않는다고
가정한다면, 이 메소드는 다중 쓰레드 상태에서도 동시 접근이 가능하며 어떤 동기화 없이도
다중 작업이 가능하다.
사실 여기서 예로 사용된 코드는 극기 가정적이다.
하지만 규모가 큰 프로젝트에서 이와 동일한 상황은 쉽게 발생 할 수 있다.
Closure는 함수 프로그래밍에서 매우 중요하다. Closure를 제외하고 currying와 memorization (앞으로 article로 진행 될 기능임)와 같은 몇몇 기술들은 이렇게 동작하지 않는다.
그리고 closure의 동작 방식을 이해하지 않고서는 C# 3.0의 기능을 적합하게 사용 할 수 없을 것이다. 그렇다고 굳이 C#에서 메소드 지향적인 프로그래밍의 가치를 고집할 필요는 없다.
왜냐하면 다른 언어들도 이와 동일한 기능을 제공하고 있기 때문이다.
우리는 앞으로의 글을 통해 이 내용을 계속 사용할 것이다. 그렇게 때문에 closure를 이해하는 것은 상당히 중요하다. 만약 아직 이 내용을 이해하고 있지 않다면, 앞으로 여러 부분에서 당신의 머리를 골치 아프게 할 것이다. Until next time….
This article continues my series on functional programming notions. one thing that you will notice as this series progresses is that I am trying to resist the temptation to use C# 3.0 syntax. A trend that I've noticed is that many are using C# 3.0 to explain functional programming and, while there's nothing terribly wrong with this, it can potentially confuse the reader. Few of us (with the exception of Bill Wagner) are truly comfortable with C# 3.0 yet. So, to understand these explanations, we have to first unravel the C# 3.0 syntax to get at the subtleties of the meat. Therefore, I am attempting to present this information in C# 2.0. It is arguable that many developers have yet to become proficient with C# 2.0 but I think its slightly more verbose syntax will help to make the concepts clear and to prepare the reader for the conciseness of C# 3.0. Later on, I will introduce C# 3.0 syntax but I'll try not to do it until the concepts are explained.
In my previous article, I promised that I would look a bit more deeply into the internals of closures. But first, let's refresh our memories as to what exactly a closure is.
What's A Closure?
A closure is a function that is bound to the environment in which it is declared. Thus, the function can reference elements from the environment within it's body. In the case of a C# 2.0 anonymous method, the environment to which it is bound is its parenting method body. This means that local variables from the parenting method body can be referenced within the anonymous method's body. So, this code prints 0 to the console as expected:
static void Main(string[] args)
{
int x = 0;
Action a = delegate { Console.WriteLine(x); };
a();
}
Most developers don't have any problem with the code above. A local variable "x" is declared and initialized to 0. Then, a new delegate "a" of type Action is declared and assigned to an anonymous method that writes "x" to the console. Finally, "a" is called and the value of "x" (0) is printed to the console. The rub occurs when the code is changed like this:
static void Main(string[] args)
{
int x = 0;
Action a = delegate { Console.WriteLine(x); };
x = 1;
a();
}
Now, "x" is reassigned to a value of 1 before "a" is called. What will be output to the console?
(NOTE: This has actually been the cause of misunderstanding and controversy. There has even been confusion by some at Microsoft itself about this issue. You can read about it here and here. Make sure that you read the comments on these blog posts to get the full flavor of the debate. If you're looking for a blog post by a .NET legendary figure that ends the debate, look no further.)
It turns out that the answer is 1, not 0. The reason for this is that the anonymous method is a closure and is bound to its parenting method body and the local variables in it. The important distinction is that it is bound to variables, not to values. In other words, the value of "x" is not copied in when "a" is declared. Instead, a reference to "x" is used so that "a" will always use the most recent value of "x". In fact, this reference to "x" will be persisted even if "x" goes out of scope. Consider this code:
static Action GetAction()
{
int x = 0;
Action a = delegate { Console.WriteLine(x); };
x = 1;
return a;
}
static void Main(string[] args)
{
Action a = GetAction();
a();
}
That will still print 1 to the console even though "x" is out of scope by the time that "a" is called. So, how is this achieved? Well, the good news is that this is handled through compiler magic. There isn't any runtime support for closures. That means that you could use the same techniques to create a closure without using an anonymous method. In fact, it is so simple that you could even do it with C# 1.0.
How's It Work?
I hinted at how closures work earlier when said "a reference to 'x' is used so that 'a' will always use the most recent value of 'x'". The key here is that a reference is used and not a value. The variable "x" is promoted from the stack to the heap in some way. And that promotion is made in such a way that the scope of "x" can be increased from its local scope. Oh, and this is done without boxing "x" to a reference type.
To make all of this possible, the C# compiler generates a special helper class. "x" becomes a field of that class and the anonymous method assigned to "a" becomes an instance method of that class. In code, it looks something like this:
sealed class ActionClosure
{
public int x;
public void AnonMethod()
{
Console.WriteLine(x);
}
}
static Action GetAction()
{
ActionClosure closure = new ActionClosure();
closure.x = 0;
Action a = new Action(closure.AnonMethod);
closure.x = 1;
return a;
}
static void Main(string[] args)
{
Action a = GetAction();
a();
}
The "GetAction" method is really where the magic happens:
- At the beginning of method, an instance of the "ActionClosure" class is created. (Note that I chose to use the names "ActionClosure" and "AnonMethod" for clarity. In reality, the compiler generates names to prevent name collision.)
- All references to the local variable "x" in the "GetAction" method have been replaced with references to the "x" field on the "ActionClosure" instance.
- The delegate "a" is now assigned to a new delegate instance for "AnonMethod" on the "ActionClosure" instance.
The cool thing to me is that this code will compile under C# 1.0 and work the same as the code using an anonymous method. It's all compiler magic and completely transparent to a C# 2.0 programmer.
Why Do I Care?
The biggest sell for closures is that they can dramatically improve code and make it more robust. Many developers have voiced a mistrust of C# 2.0 anonymous methods because of their potential for abuse. After all, it's not too hard to imagine anonymous methods turning quickly into spaghetti code. But in my experience, many developers have dismissed them simply because they don't understand the power behind them: closures.
Let's look at an example:
new string[] {
"Bill Gates",
"Dustin Campbell",
"Dustin's Trophy Wife",
"Foster the Dog"
});
static void Print(List<string> items)
{
foreach (string item in items)
Console.WriteLine(item);
}
static void Main(string[] args)
{
Print(g_Names);
}
This application simply creates a list of names and then outputs them to the console. It works perfectly well.
Now, let's assume that we need to add the ability to retrieve a list of names that starts with some particular text. This is pretty easy to implement because there is a handy method on List<T> called FindAll that simply takes a Predicate delegate and produces a new List<T> containing all of the items that the Predicate returns true for. We can add this new function like so:
static bool NameStartsWith(string name)
{
return name.StartsWith(g_StartingText);
}
static List<string> GetNamesStartingWith(string startingText)
{
g_StartingText = startingText;
return g_Names.FindAll(NameStartsWith);
}
Everything is working fine until our client calls and says that there is a new requirement for this function: it must be thread-safe. In other words, the function must produce valid results even if it is called by multiple threads. This is problematic because, while one thread is finding all names starting with "D", another thread could change "g_StartingText" to something else and bad results would be returned.
One possibility might be tempting to place a lock on "g_StartingText". This would certainly make the function thread-safe but it has some drawbacks. The biggest issue with this approach is that threads will not be able to access this function concurrently. If a thread acquires the lock, all other threads must wait until that thread is finished. In other words, this method becomes a potential bottleneck because only one thread can access it at a time and if there any additional processors on the machine they won't be used.
The solution is to use an anonymous method to create a closure and remove the shared state:
{
return g_Names.FindAll(
delegate(string name)
{
return name.StartsWith(startingText);
});
}
Even with the verbosity of anonymous methods, the code has been greatly reduced. And, assuming that "g_Names" will never be modified, this function could run concurrently on multiple threads and multiple cores without any synchronization.
Admittedly, my example is highly-contrived but it's not too hard to imagine the same situation in larger scale applications.
Closures are critical to functional programming. Without closures, several techniques like currying and memoization (more on these in future articles) don't work. And, without understanding the subtleties of closures, you won't be able to use the features of C# 3.0 properly. I don't need to defend the value of functional programming in C# because others have done that extremely well.
We will be building on this knowledge in future articles so understanding closures is important. Things will quickly start to make your head spin if you don't understand this concept.
Using Automatic Memoization
오늘 나는 이전 글에서 이야기한 피보나치 수열 함수를 다시 한번 확인해 볼 것이다.
그리고 다른 함수 프로그래밍(Functional Programming) 기술로 인해 조금 더 개선될 수 있는지도 알아볼 것이다.
|
delegate int FibonacciCalculator(int n); |
만약 여러분이 closure에 대한 글을 통해 나와 함께 이 내용에 대해서 고민해봤다면,
여러분은 closure가 함수에 의해 생성되었다는 것을 알아야 한다. 왜냐하면 지역변수 “results”는
비록 자신이 익명 메소드의 코드 블록 바깥에 선언되었다 할지라도 익명 메소드와 함께 사용되기 때문이다.
그렇게 하기 위해서, C# 컴파일러는 지역변수 “results”를 컴파일러에 의해 생성된 helper 클래스 안에서 필드로 바꾼다. 또한 “calculator”도 익명 메소드 바깥에 지역변수로 선언되었지만
익명 메소드 내부에서 함께 사용된다. 만약 여러분이 이 부분을 보지 못했다면, 다시 한번 확인해보기 바란다.
“calculator”는 메소드 호출이 아니다. 실제로 이것은 재귀적으로 실행되는 결과를 참조하기 위한 FibonacciCalculator delegate 타입의 변수다. 이것은 그리 자세하게 설명되었다고 보이지 않을 수 있으나, 사실 대단히 중요한 부분이다. 컴파일러는 실제로 아래와 같은 코드를 생성한다.
|
delegate int FibonacciCalculator(int n); |
컴파일러에 의해 생성된 코드를 보는 것은 이 내용을 명확히 이해하는데 도움을 준다.
만약 여러분이 위의 코드에서 “CalculatorMethod” 메소드를 봤다면, 여러분은 이 코드가
자기 자신을 재귀적으로 호출하는 것이 아니라는 것을 알 수 있을 것이다.
대신 이 메소드는 “calculator” delegate를 호출하고 그 영향으로 자기 자신을 재귀적으로 호출하게 된다. 이것은 코드를 착각하게 만드는 요소들 중에 중요한 부분이다.
이제 우리는 이렇게 짧은 순간 동안 발생하는 동작에 대해 알게 될 것이다.
첫 번째, 피보나치 함수에 대한 원본 글에서 나는 caching과 같이 어떤 값을 나중에 조회하기 위한 함수로부터 결과를 저장하는 기술을 사용했다. 나는 이것에 대해 일반적인 용어를 사용했지만,
사실 이것은 “Menoizition”라는 용어로 정의된다. 지금 몇몇 실력이 좋은 객체지향 개발자들은
이 “menoization”이 재사용하기 위한 방법이었다는 것을 기억할 수 있을 것이다.
어쩌면 몇 개의 추상클래스의 분류가 이 문제를 해결하기 위해 생성될 수 있을까? 클래스는 테이블 탐색을 지속하고 테이블 탐색의 결과가 리턴된 후 함수가 호출될 때, 이 로직을 처리한다.
과연 이렇게 동작 했을까? 음~ 글쎄.. 그럴수도 있다. 하지만 내가보기엔 이것은 괜한 노력이 많이 소비됐고 재사용하기 위한 방법으로는 서투르게 보인다. 나는 이 문제를 해결하기 위한 훨씬 더 좋은 방법(재사용 가능한)을 알고 있다. 그것은 바로 또 다른 closure를 사용하는 것이다.
우리는 이것을 C# 2.0으로 살펴볼 것이다.
|
static FibonacciCalculator Memoize(FibonacciCalculator function) |
이 메소드가 무엇인지 잘 살펴보기 바란다.
이 메소드는 “FibonacciCalculator” 타입의 delegate를 하나 받고 같은 타입의 새로운 delegate를 하나 리턴 한다. 이 새로운 delegate는 익명 메소드이고 인자로 넘겨진 “function”의 결과를
저장하고 조회하기 위해 Dictionary를 사용한다. 또한 이 새 delegete는 closure다.
왜냐하면 이것은 지역변수 “results”와 “function”을 참조하기 때문이다. 이것은 참조하고 있는
변수들의 실행 범위가 확대 될 것이고 Memoize function 바깥에 존재할 것이다.
(이 내용에 대해 이해가 필요하다면 이전 글을 참고하기 바란다.)
이것을 토대로 피보나치 함수가 어떻게 바뀌었는지 한번 보자.
|
int Fibonacci(int n) |
이것은 여러분이 이런 기술을 처음 보는 것처럼 착각하게 만든다.
이런 방법은 함수 프로그래밍과 조금 유사하면서, 컴파일러에 의해 생성된 클래스의 코드를
쉽게 이해할 수 있게 한다.
|
delegate int FibonacciCalculator(int n); |
다시, 실제로 어떻게 동작하는지 알기 위해 코드를 주의 깊게 살펴보자.
이 방법은 memorization 기능을 추가한 피보나치 메소드를 감싸는 Wrapper 메소드를 생성했다.
이렇게 한 이유는 피보나치 메소드는 자기 자신을 곧바로 호출하는 것 대신에 재귀적 호출 방법을 사용하기 위해 delegate(“calculator”)를 사용하기 때문이다. 이 delegate는 새로운 “memoized”
메소드에 할당되었기 때문에, 피보나치 메소드가 실제로 호출된다.
만약 여러분이 이 코드를 실행해봤다면, 여러분은 이것이 이전 글에서 사용되었던 코드 보다
훨씬 더 빠르게 최적화 되었다는 것을 알 수 있을 것이다. 그리고 이 차이점은 아래와 같다.
1. 첫 번째 결과값을 얻기 위한 시간이 약간 길다. 왜냐하면 추가된 closure와 Dictionary는 초기화되어야 하기 때문이다.
2. 추가된 우회 방법과 Dictionary는 알고리즘을 약간 느리게 한다. 하지만 이것은 millisecond 정도의 수준에서도 기록되지 않을 정도로 미비하다.
이렇게 대단히 최적화된 결과에 연연 하지 않고, 우리는 다른 상황에서도 사용할 수 있는 재사용 가능한 “Memoization Function”을 구현해야 한다. 이것은 아직 재사용 가능하지 않다.
이유는 이 코드는 단지 우리가 예제로 사용하고 있는 “FibonacciCalculator” 타입에만 국한되어
있기 때문이다. 나는 지금까지 제네릭을 사용하는 것을 자제해왔다.
왜냐하면 제네릭은 아직 많이 사용되지 않아, 이와 대조되어 보일 수 있기 때문이다.
그러나 우리는 우리만의 Generic delegate 타입을 구현하여 이것을 재사용 가능하게 만들 수 있다.
“FibonacciCalculator” 대신에, 아래 코드를 사용할 수 있다.
|
delegate TResult Func<TArg, TResult>(TArg arg); |
(주의 : 위 코드에서 사용된 Generic은 .Net Framework 3.5에 포함될 예정이고, C# 3.0 컴파일러에
의해서 사용된다.)
우리가 위에서 구현한 Memoize Function은 자기 스스로가 Generic 형식으로 처리되고,
아래와 같이 새로운 delegate를 사용한다.
|
static Func<TArg, TResult> Memoize<TArg, TResult>(Func<TArg, TResult> function) |
그리고 이렇게 변경된 코드로 우리는 아래와 같은 Fibonacci 메소드를 구현할 수 있게 되었다.
|
int Fibonacci(int n) |
지금 우리는 하나의 인자를 받고 하나의 결과를 리턴하는 형식의 어떤 메소드와도 사용 가능한 “Memoization Function”을 구현했다. 그리고 이 방법은 저장된 값을 유지하고 명시적인 선언에 사용되는 추가 코드 없이 빠른 응답 성능을 얻을 수 있고 피보나치 알고리즘이 갖고 있는 고유의 장점을 그대로 사용 할 수 있다.
만약 여러분이 이 기술을 사용한 다른 application에 흥미가 생겼다면
“Wes Dyer”의 memoization에 대한 훌륭한 블로그 글을 여기와 여기에서 참조하기 바란다.
Wes Dyer는 “Singleton”과 “Multiton” 디자인 패턴을 구현하기 위해 이 기술을 사용하는 몇 가지 훌륭한 방법을 알고 있다.
출처: http://blogs.msdn.com/b/wesdyer/
One of my favorite pastimes is playing games. No not XBox 360, PS3, or Wii games nor other computer games, but board games, card games, and other such games. It's probably because I'm from a large family - I have 8 siblings - and we would often spend time together playing games. It is a good way to accommodate a wide variety of interests, skills, and aptitudes. Some of my favorite games are Settlers of Catan, Carcassonne, Spades, Rook, Mafia, Take Two, Stratego, Ticket to Ride, and of course Axis and Allies.
For my birthday this past year, I received an interesting board game titled RoboRally.
The premise of the game is there are a number of robots in a factory and they are bored, so they begin to indulge themselves by competing in races around the factory floor.
Each player takes command of a robot and seeks to win these competitions by controlling the robot.
The players are dealt a number of instruction cards whereupon each player elects five cards to load into his program registers.
After all the players have programmed their robots, their programs are executed somewhat simultaneously.
The robots can interact with each other by shooting, pushing, or otherwise hampering each other's progress.
But the real catch is that the board also interacts with the robots by way of conveyer belts, lasers, pushers, gears, pits, etc. The uncertainty caused by the sheer number of interactions coupled with the deterministic behavior of programmed robots creates pandemonium.
One day I was just itching to write some code so I thought why not implement a computer version of RoboRally. I thought that it would be particularly fun because of the number of interacting objects and the amount of state that is involved.
So I began to code away on a board editor.
This took a little bit of time mostly because I'm not very skilled at graphic art.
Here is a screenshot from an early version of the board editor.
The code for the editor consists of three assemblies: the windows application, a game engine, and a functional programming library.
This was one of the first non-trivial apps that I wrote using C# 3.0 and it was very fun to use the new language features.
In fact, it was incredible because I found that many design patterns that I commonly used changed drastically or were no longer needed.
Furthermore, I found that entirely new designs were possible. Today, I will touch on just one of these design patterns and the underlying principle used in it.
The game engine has an class called Board and these boards are composed of many Tiles which are each associated with a Location.
Tiles can be simple or rather complex.
For instance, there are blank tiles and there are move left express conveyer belt tiles.
But there are also gear tiles with a normal wall on the top side and a laser wall on the left side which also have a flag on the tile.
I made a design decision early on to have basic tiles and decorator tiles.
So complex tiles are formed from the composition of a basic tile and any number of decorator tiles. I wrote a factory which creates either some basic tile or some decorator tile.
For a first cut, I didn't worry that I created an overabundance of blank tiles even if they are all identical. Nor did I worry about the fact that all move right conveyer tiles are the same. However, later as I was refining the design I came back to the factory and wanted to improve it by reducing the number of tiles that were created to the bare minimum.
A typical solution to this problem for the blank tiles would look like this:
IBlankTile blankTile;
public IBlankTile CreateBlankTile()
{
if (blankTile == null)
blankTile = new BlankTile();
return blankTile;
}
But how do we do this for conveyer tiles?
Dictionary<Direction, IConveyerTile> conveyerTiles = new Dictionary<Direction, IConveyerTile>();
public IConveyerTile CreateConveyerTile(Direction direction)
{
IConveyerTile result;
if (!conveyerTiles.TryGetValue(direction, out result))
{
result = new ConveyerTile(direction);
conveyerTiles.Add(direction, result);
}
return result;
}
Ick! It only gets even more complicated for tiles that are parameterized on more items. Furthermore, it seems that there is a lot of repetition going on. Specifically, all of the machinery to track instance existence and creation is being duplicated for each tile type. To some extent the Singleton and Multiton patterns also suffer from the same problem. There must be a better way.
In fact, there is a better way. What we really want here is a function that returns the same value each time it is applied to the same parameter values. Functional programmers will instantly recognize this as function memoization.
Memoization can be implemented as a function which takes a function as a parameter and returns a new function which when invoked the first time on some set of parameters will compute the result and when invoked with the same values will not recompute the result but will instead return the previously computed result.
Now let's see how our code would have looked if we had a static method called Memoize is a functional library called Fun (why not? functional programming is fun isn't it?).
public readonly Func<IBlankTile> CreateBlankTile = Fun.Memoize(() => new BlankTile());
public readonly Func<Direction,IConveyerTile> CreateConveyerTile = Fun.Memoize(dir => new ConveyerTile(dir));
The new code is beautiful and doesn't have all of the redundancy and complexity of the old code. This is a very practical example of the modularity of functional style code that I referred to previously.
"But wait", you say, "how exactly does the magic happen?" Well, let's take a look. First, let's examine a memoize function which takes a function of no arguments and returns a memoized version of that function.
public static Func<R> Memoize<R>(this Func<R> f)
{
R value = default(R);
bool hasValue = false;
return () =>
{
if (!hasValue)
{
hasValue = true;
value = f();
}
return value;
};
}
Memoize takes a function which has no arguments and a return type of R and returns a function with the same signature. When Memoize is called it creates two local variables value and hasValue. Memoize then returns a new function that returns value if hasValue is true otherwise it computes value by evaluating the parameter f, sets hasValue to true, and then returns value.
Notice that the function that is returned from Memoize accesses hasValue, value, and f. These three variables are local to Memoize. The three variables together with a reference to the function that is created by Memoize form a closure.
So what happens when we invoke the function returned from Memoize for the first time? The variable hasValue will be set to false, so we will set hasValue to true and then apply f saving the result to value. Finally, we will return the value which is the result of f.
So the memoized function will return the same thing that f would have returned on its first invocation.
But what about on subsequent invocations? When we call memoized function again, hasValue will be true so we will simply return value without recomputing it. So the memoized function will always return the same value as it did on the first invocation without recomputing the result through f.
This has subtle implications such as if f has side effects then those side effects will only occur when we apply the memoized function the first time. So we need to be careful about using it. But consider how CreateBlankTile used Memoize. When CreateBlankTile is run the first time, it will create a blank tile and then return the result, but on subsequent invocations it will continue to return the same blank tile. This is exactly the behavior that we want.
Can we do the same thing for functions that have arguments? Absolutely, let's take a look at how to Memoize functions of one argument.
public static Func<A, R> Memoize<A, R>(this Func<A, R> f)
{
var map = new Dictionary<A, R>();
return a =>
{
R value;
if (map.TryGetValue(a, out value))
return value;
value = f(a);
map.Add(a, value);
return value;
};
}
This time instead of storing the computed values in a local variable directly, we store them in a dictionary and instead of marking that we have computed the value we just check for existence in the dictionary. This can be generalized to functions of n arguments by creating composite keys of n fields that are used in the dictionary.
Consider how this Memoize function works with CreateConveyerTile.
When we invoke it with some direction for the first time then it will not find that direction in the dictionary and so it will create a new conveyer tile parameterized on that direction and then store it in the dictionary. Subsequent calls with the same direction will not create new tiles but instead grab out the existing one from the dictionary.
Again this is the behavior that we want. Furthermore, all of the mechanics of storing and fetching tiles are located in Memoize instead of CreateBlankTile or CreateConveyerTile.
Memoize is also useful for the improving performance of recursive functions.
Eric Lippert has a great post about how not to teach recursion where he specifically mentions not to use fibonacci numbers. However, I'm going to use fibonacci numbers not to teach recursion but to show how to improve the performance of recursive functions. Recall, that the definition of the nth fibonacci number where n >= 0 is:
fib(0) = 0
fib(1) = 1
fib(n) = fib(n - 1) + fib(n - 2) if n > 1
We can easily write a little function to do this:
Func<int, int> fib = null;
fib = n => n > 1 ? fib(n - 1) + fib(n - 2) : n;
The problem is this function is very inefficient. Consider calculating the 5th fibonacci number.
fib(5)
= fib(4) + fib(3)
= fib(3) + fib(2) + fib(2) + fib(1)
= fib(2) + fib(1) + fib(1) + fib(0) + fib(1) + fib(0) + 1
= fib(1) + fib(0) + 1 + 1 + 0 + 1 + 0 + 1
= 1 + 0 + 1 + 1 + 0 + 1 + 0 + 1
= 5
Notice how the computation branches out forming a tree of expansions.
In fact, the number of leaves in a tree for the computation of the nth fibonacci number is fib(n + 1) where the number of ones is fib(n) and the number of zeros is fib(n - 1).
So calculating fib(5) will cause fib to evaluated twelve times (the sum of the fibonacci numbers from 0 to 5) but only six distinct calls will be made (fib(0), fib(1), ..., fib(5)).
The problem only gets worse because the fibonacci numbers grow very quickly.
Here are the first 20 fibonacci numbers:
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181
So our straightforward recursive function for computing fibonacci numbers will be exponential in n. Ouch! But wait, we can Memoize fib so that if it calls fib again with the same argument then it will not recalculate but instead use the previous result. This will move our exponential function to a linear one at the cost of linear space to store the previous results (we could possibly use a weak reference hash map instead to solve problems with space if they existed). In fact, subsequent calls to fib with previously computed values will be evaluated in constant time.
Func<int, int> fib = null;
fib = n => n > 1 ? fib(n - 1) + fib(n - 2) : n;
fib = fib.Memoize();
If you want, you can add a Console.WriteLine to show when the evaluations happen to both versions and compare. It is very enlightening.
Memoize is turning into quite the useful function. We have used it to solve parameterized identity creation problems and performance issues. Later, we will see other ways we can use Memoize to solve design problems.
Keith Farmer brought it to my attention that there is at least a little confusion about how closures work. Hopefully, I can help shed a little light on the subject. The question is why doesn't the following code actually memoize fib in the call to Test?
Func<int, int> fib = null;
fib = n => n > 1 ? fib(n - 1) + fib(n - 2) : n;
Test(fib.Memoize());
Before I explain why this code doesn't work, I want to return to the example that I used in my last post.
Func<int, int> fib = null;
fib = n => n > 1 ? fib(n - 1) + fib(n - 2) : n;
Func<int, int> fibCopy = fib;
Console.WriteLine(fib(6)); // displays 8
Console.WriteLine(fibCopy(6)); // displays 8
fib = n => n * 2;
Console.WriteLine(fib(6)); // displays 12
Console.WriteLine(fibCopy(6)); // displays 18
Probably the easiest way to see why this code behaves so strangely is to show what code the C# compiler generates. This can easily be done with ildasm.exe or reflector. There are two lambdas defined in the code. The first one captures the local variable named fib and the second does not capture any locals. Because fib is capture by a lambda, it must be hoisted on to the heap. So a class is declared that contains the captured local.
class DisplayClass
{
public Func<int, int> fib;
}
Now the compiler must emit a method that corresponds to the first lambda. This method will need access to the members of DisplayClass and must also be convertible to a Func<int,int> delegate.
Today the compiler achieves this by emitting the method on the display class as an instance method (we could also have used currying but that is a story for another day).
class DisplayClass
{
public Func<int, int> fib;
public int M1(int n)
{
return n > 1 ? fib(n - 1) + fib(n - 2) : n; // <-- 1st lambda body
}
}
The second lambda does not capture any local variables.
So this method can be emitted as a static method.
static int M2(int n)
{
return n * 2;
}
Finally, we are ready to show the emitted code for the original code fragment.
DisplayClass locals = new DisplayClass();
locals.fib = null;
locals.fib = locals.M1;
Func<int, int> fibCopy = locals.fib;
Console.WriteLine(locals.fib(6)); // displays 8
Console.WriteLine(fibCopy(6)); // displays 8
locals.fib = M2;
Console.WriteLine(locals.fib(6)); // displays 12
Console.WriteLine(fibCopy(6)); // displays 18
Notice how the first call to fib is really just a call to M1 and when M1 "recurses" on fib it just ends up calling M1 again because that is what is assigned to fib.
The call to fibCopy is a little trickier because the original call is really a call to M1 as well but when it "recurses" it invokes fib instead of fibCopy which also happens to be M1 at the time. So the first two calls behave as expected.
Now it starts to get a little strange. First we assign M2 to fib. Then when we invoke fib on the next line it doesn't invoke our original "fib" function M1 anymore but it not invokes M2. This of course displays the result of multiplying 6 by 2.
Now for the strangest part, we invoke fibCopy. But fibCopy actually still references M1 and not M2 and since 6 > 1 then it "recurses" by invoking fib twice with 5 and 4 respectively and then summing the results. But the calls to fib actually invoke M2 now.
So the results of the calls to fib are 10 and 8 which then are summed to produce 18.
Now let's return to our original problem.
Func<int, int> fib = null;
fib = n => n > 1 ? fib(n - 1) + fib(n - 2) : n;
Test(fib.Memoize());
Notice that the function passed to Test is memoized but the body of the function still calls the unmemoized fib. The function itself is memoized by all of the "recursive" calls are not. So it probably will not behave as intended. This can be corrected by doing the following.
Func<int, int> fib = null;
fib = Memoize(n => n > 1 ? fib(n - 1) + fib(n - 2) : n);
Test(fib);
Now the calls to fib when n > 1 are made to the memoized fib delegate.
If you read my last post on anonymous recursion in C# which introduces the Y combinator then you may have tried the following.
Func<int, int> fib = Y<int, int>(f => n => n > 1 ? f(n - 1) + f(n - 2) : n).Memoize();
This behaves very similarly to the incorrectly written fib above.
Calls to the function itself are memoized but all of the recursive calls are not.
This is because fib is memoized but f is not. Erik Meijer pointed me to a fantastic paper that discusses how to memoize functions that are the fixed point of functionals.
In this paper, Cook and Launchbury present a function written in Haskell that enables memoized anonymous recursive functions.
memoFix f = let g = f h
h = memo g
in h
Using the MemoizeFix function in C# looks very similar to using the Y combinator, but instead of just returning a recursive function, it would also memoize the function and all the recursive calls.
Func<int, int> memoFib = MemoizeFix<int, int>(f => n => n > 1 ? f(n - 1) + f(n - 2) : n);
But there are two problems with implementing the function in C#. First, Haskell lets programmers write mutually recursive definitions (g is defined in terms of h and h is defined in terms g). Second, Haskell is a lazy language.
A straightforward implementation in C# will either produce a null reference exception or a stack-overflow because of the eager evaluation and mutually recursive definitions. Fortunately, lambdas can be used to solve both problems.
static Func<A, R> MemoizeFix<A, R>(this Func<Func<A, R>, Func<A, R>> f)
{
Func<A, R> g = null;
Func<A, R> h = null;
g = a => f(h)(a);
h = g.Memoize();
return h;
}
Here we define both g and h before they are assigned their final values.
Then instead of assigning f(h) to g which would immediately invoke f causing a Null Reference exception, we assign a lambda to g which will be evaluated sometime in the future when h has a non-null value. The rest of the function is very similar to the Haskell version.
Notice what happens when memoFib is invoked.
This will actually invoke h which was defined in MemoizeFix, but h is really just a memoized version of g.
Since this is the first invocation of h and there will be no precomputed value and so g will be invoked. But when g is invoked then it actually invokes f passing h (memoized g) as the function to use for recursion.
This is exactly what we want. Beautiful isn't it?
Today I want to revisit our recursive Fibonacci number function from my previous article and see if there might be some ways to improve it by drawing on another functional programming technique. For reference, here's the Fibonacci function:
int Fibonacci(int n)
{
int[] results = new int[n + 1];
FibonacciCalculator calculator = null;
calculator = delegate(int x)
{
if (x < 2)
return x;
else
{
if (results[x] == 0)
results[x] = calculator(x - 1) + calculator(x - 2);
return results[x];
}
};
return calculator(n);
}
If you stuck with me through the article on closures, you know that a closure is created by this function because the local "results" variable is used within an anonymous method even though it is declared outside of it. So, the C# compiler will turn the "results" variable into a field on a compiler-generated helper class. What's not as obvious is that "calculator" is also a local variable declared outside of the anonymous method but used inside. If you missed it, look again. "calculator" isn't a method call. In reality, it's a variable of the FibonacciCalculator delegate type which happens to reference the method that we're calling from (and hence, resulting in recursion). This might seem like a minor detail but it's extremely important. The compiler actually generates code that looks something like this:
sealed class FibonacciClosure
{
public int[] results;
public FibonacciCalcualtor calculator;
public int CalculatorMethod(int x)
{
if (x < 2)
return x;
else
{
if (results[x] == 0)
results[x] = calculator(x - 1) + calculator(x - 2);
return results[x];
}
}
}
int Fibonacci(int n)
{
FibonacciClosure closure = new FibonacciClosure();
closure.results = new int[n + 1];
closure.calculator = new FibonacciCalculator(closure.CalculatorMethod);
return closure.calculator(n);
}
Looking at the compiler-generated code actually helps clarify this. If you look at "CalculatorMethod", you'll notice that it is not calling itself recursively. Instead it is calling the "calculator" delegate and the effect is that it calls itself recursively. This has importance that is actually a bit mind-bending but we'll get to that in a moment.
First, in the original article, I referred to the technique of storing the results from our function for retrieval later as caching. I used that term generally but there is a more specific term: Memoization. Now, a good object-oriented programmer would recognize that this "memoization" is an idea that should be reused. Perhaps some sort of abstract class could be created to solve this problem? The class could maintain the lookup table and handle when the function is called and when results from the lookup table are returned. That would work, right? Well, it might work but it sounds like a lot of extra effort to me and it would be awkward to reuse. In reality, there is a much more elegant (and reusable) solution to this problem. The answer is to use another closure. As usual, we'll stick with C# 2.0 for now.
{
Dictionary<int, int> results = new Dictionary<int, int>();
return delegate(int key)
{
int value;
if (results.TryGetValue(key, out value))
return value;
value = function(key);
results.Add(key, value);
return value;
};
}
Look carefully at what this method does. It takes a delegate of type "FibonacciCalculator" and returns a new delegate of the same type. The new delegate is declared as an anonymous method which uses a Dictionary to store and retrieve the results of the passed function. This new delegate is a closure because it references the local variables "results" and "function". That means that the scope of those referenced variables will be promoted and will exist outside the Memoize function (see my previous article if your need a refresher). With that in mind, here's how our Fibonacci function changes:
{
FibonacciCalculator calculator = null;
calculator = delegate(int x)
{
if (x < 2)
return x;
else
return calculator(x - 1) + calculator(x - 2);
};
calculator = Memoize(calculator);
return calculator(n);
}
This is a bit mind-bending if you're seeing a technique like this for the first time so let's tear it apart a bit. For those less-familiar with functional programming, it can be easier to see when expressed in the classes that are generated by the compiler:
sealed class MemoizeClosure
{
public FibonacciCalculator function;
public Dictionary<int, int> results;
public int MemoizedFunction(int key)
{
int value;
if (!results.TryGetValue(key, out value))
{
value = function(key);
results.Add(key, value);
}
return value;
}
}
FibonacciCalculator Memoize(FibonacciCalculator function)
{
MemoizeClosure closure = new MemoizeClosure();
closure.function = function;
closure.results = new Dictionary<int, int>();
return new FibonacciCalculator(closure.MemoizedFunction);
}
sealed class FibonacciClosure
{
public FibonacciCalculator calculator;
public int FibonacciFunction(int x)
{
if (x < 2)
return x;
else
return calcualtor(x - 1) + calculator(x - 2);
}
}
int Fibonacci(int n)
{
FibonacciClosure closure = new FibonacciClosure()
closure.calculator = new FibonacciCalculator(closure.FibonacciFunction);
closure.calculator = Memoize(closure.calculator);
}
Again, read the code carefully to see what's actually happening. The idea is that we've created a function which wraps our Fibonacci function with the memoization feature. This works because our Fibonacci function uses a delegate ("calculator") for recursion instead of calling itself directly. The delegate gets assigned to the new "memoized" function so the Fibonacci function actually calls that instead.
If you run this code, you will find that it is almost as fast as the optimized Fibonacci function from the previous article. The only differences are:
- A slightly longer time to get the first result because the extra closure and Dictionary have to be instantiated.
- The added indirection and Dictionary slow the algorithm down slightly but the difference doesn't register at the millisecond level.
Regardless of these extremely minor consequences, we now have a reusable Memoize function that can be used in other situations. Err... ok, it's not that reusable yet because it is tied to our FibonacciCalculator type. I held off on using generics until now because they can look bizarre to the uninitiated but we can make this reusable by creating our own generic delegate type. Instead of FibonacciCalculator, we could use this:
(Note that several generic delegates just like will be included with the .NET Framework 3.5 and used by the C# 3.0 compiler.)
Our Memoize function can become generic itself and use the new delegate like this:
{
Dictionary<TArg, TResult> results = new Dictionary<TArg, TResult>();
return delegate(TArg key)
{
TResult value;
if (results.TryGetValue(key, out value))
return value;
value = function(key);
results.Add(key, value);
return value;
};
}
And a small change is made to our Fibonacci function:
{
Func<int, int> calculator = null;
calculator = delegate(int x)
{
if (x < 2)
return x;
else
return calculator(x - 1) + calculator(x - 2);
};
calculator = Memoize(calculator);
return calculator(n);
}
Now we have a reusable memoization function that could be used with any function that takes one argument and returns a result. And, the solution allows us to capture the elegance of the original Fibonacci algorithm and achieve reasonable performance without the added baggage of explicitly declaring and maintaining storage.
If you are interested in other applications of this technique, Wes Dyer has some excellent blog posts on memoization here and here. Wes has some very cool ways to use this technique to implement the Singleton and Multiton design patterns.
Good luck and happy coding!
'IT_Programming > C#' 카테고리의 다른 글
| C# StreamReader 에서의 한글 Encoding 문제 (0) | 2010.12.30 |
|---|---|
| 비동기 방식의 콜백함수 (AsyncCallBack, BeginInvoke(), EndInvoke()) (0) | 2009.07.08 |
| [펌] using / foreach와 try / catch 확장 (0) | 2008.12.18 |
| [C++/CLI, C#] Predicate으로 사용할 객체형 대리자 및 무명 메서드. (0) | 2008.01.10 |
| 스레드(thread) 예제 (0) | 2007.12.23 |