어쩌다 보니 온라인 게임서버 개발에 종사하게 되어서 종종 이름을 듣곤 하는 넷텐션은 고성능 네트워크 서버 엔진인 프라우드넷을 개발한 회사로 유명하다. 얼마 전 이 회사의 입사면접시험 문제가 인터넷 커뮤니티에 공개되었다. 바로 1부터 백만까지의 소수를 출력하는 프로그램을 만들라는 것. 사실 2번 문제가 핵심이고 출제자의 의도는 에라토스테네스의 체 보다도 단순한 방법(루트n까지 나눠보기)으로 소수를 판별하면서도 이것을 병렬화하는 테크닉을 보고자 한 것 같지만, Functional Programming in Scala 수업을 듣던 중 1번 문제를 풀 수 있는 아주 간결한 방법을 보고 충격을 받고 몇 달째 누르길 귀찮아 하고 있던 글쓰기 버튼을 눌렀다.
전통적인 방법이라면, 에라토스테네스의 체는 아래와 같이 순차적으로 계산할 것이다. (in C++)
#include <iostream>
using namespace std;
const int N = 1000;
int main() {
bool nonprime[N + 1] = { true, true, false, };
for (int n = 2; n <= N; n++) {
if (!nonprime[n]) {
for (int m = 2; n * m <= N; m++) {
nonprime[n * m] = true;
}
}
}
for (int n = 2; n <= N; n++) {
if (!nonprime[n]) {
cout << n << endl;
}
}
}
2부터 시작해서 소수의 배수들을 하나씩 제외하는 정의에 충실한 코드이다. 그런데 Functional Programming in Scala 수업에서는 다음과 같이 위 C++ 프로그램과 같은 출력을 만드는 방법을 소개한다.
object Eratosthenes {
def from(n: Int): Stream[Int] = n #:: from(n+1)
def seive(s: Stream[Int]): Stream[Int] = {
s.head #:: seive(s.tail filter (_ % s.head != 0))
}
val primes = seive(from(2))
def main(args: Array[String]) {
primes takeWhile(_ <= 1000) print
}
}
순차적인 구현과 코드 분량은 크게 다르지 않지만, 접근 방법이 완전히 다르다. Stream[Int]는 수열을 의미하는데, lazy evaluation이 되기 때문에 무한히 긴 수열이 될 수도 있다. 실제로 from 은 n 이상의 모든 정수의 stream을 반환하고, seive는 주어진 stream의 첫 번째 숫자의 배수를 걸러내어 다시 seive를 적용한 stream을 반환한다. 종료 조건이 없는 재귀함수로 보이지만 이것 역시 lazy evaluation 덕분에 가능하다. 즉 2 이상의 모든 정수에 대해 seive를 하면, 모든 소수를 담고 있는 수열 primes를 얻게 된다. main 함수는 primes 에서 1000 이하의 소수를 뽑은 다음 출력한다. primes가 선언된 곳은 main 함수의 밖이었지만, lazy evaluation 덕분에 실제 에라토스테네스의 체 계산이 이루어지는 부분은 이곳이다.
저 풀이를 처음 보고선 무한히 긴 수열과 같은 추상적인 개념까지 간결하게 표현할 수 있는 함수형 프로그래밍의 매력에 awe moment를 느낄 수 밖에 없었다. 이어서 든 생각은, 정말 이건 Scala에서만 가능한걸까? 라는 것이었다. C++이나 Java와 같은 전통적인 언어는 태생적인 한계 덕분에 lazy evaluation같은 처리를 하려면 얼마나 손해를 보게 될까 라는 의문이 들어서 한번 해 보기로 했다. 두 언어 모두 lambda expression을 사용할 수 있게 되어서 수월하지 않을까 하는 낙관이 앞섰다...
먼저 Java 구현이다.
import java.util.function.Predicate;
import java.util.function.Supplier;
class Lazy<T> {
final Supplier<T> supplier;
T value;
public Lazy(Supplier<T> supplier) {
this.supplier = supplier;
}
public T get() {
if (value == null) {
value = supplier.get();
}
return value;
}
}
class Stream<T> {
T head;
Lazy<Stream<T>> tail;
public Stream(T value) {
this.head = value;
}
public Stream(T head, Supplier<Stream<T>> tail) {
this.head = head;
this.tail = new Lazy<>(tail);
}
public Stream<T> filter(Predicate<T> predicate) {
return tail.get() == null ? null :
predicate.test(head) ?
new Stream<>(head, () -> tail.get().filter(predicate)) :
tail.get().filter(predicate);
}
public Stream<T> takeUntil(Predicate<T> predicate) {
return predicate.test(head) && tail.get() != null ?
new Stream<>(head, () -> tail.get().takeUntil(predicate)) : null;
}
public void print() {
System.out.println(head);
if (tail.get() != null) {
tail.get().print();
}
}
}
public class Sieve {
static Stream<Integer> from(int n) {
return new Stream<>(n, () -> from(n+1));
}
static Stream<Integer> sieve(Stream<Integer> stream) {
return new Stream<>(stream.head, () -> sieve(stream.tail.get().filter(n -> n % stream.head != 0)));
}
static Stream<Integer> primes = sieve(from(2));
public static void main(String ... args) {
primes.takeUntil(n -> n < 1000).print();
}
}
일일히 유틸리티 클래스를 만들어야 하는 것과 lazy value에 대한 문법적 지원이 없어서 매번 () -> 를 써 주어야 하는 것이 좀 고단하지만, 어쨌든 주요 구현부분 자체는 충분히 간결하게 가능하다는 것을 볼 수 있다! 다만 Java 8에서 추가된 lambda expression이 없으면 몇 배나 지저분해졌을 지 상상하기가 두렵다. 한편 Java 8에서는 Scala의 Stream과 매우 유사한 Stream 클래스를 제공한다. 이를 사용하면 꽤 깔끔하게 구현을 할 수 있을 것 같은데, Java 8의 Stream은 lazy value를 제대로 구현하지 않는 대신 재사용이 불가능하게 만들어 놓은 데다가 head와 tail을 떼어낼 적절한 방법이 없는 것 같아서 방법을 찾다가 포기해야 했고-_-; C++로도 해보다가 new 쓰기 싫어서 스택에서 최대한 해보다가 쥐쥐=_=.. 다음에 천천히 도전해야 할 것 같다.
Functional Programming in Scala 수업의 마지막 과제를 아직 하지 않았지만 그래도 60% 이상의 과제를 완료하여 수료증을 받는 것은 확실해졌다. 프로그래밍 숙제를 가이드를 따라 해결하고 제출하면 자동으로 채점해 주고 동작 결과는 물론 코딩 스타일과 같은 사소하지만 유익한 부분까지도 피드백을 제공하는 Coursera의 시스템 덕분에 더 적극적으로 수업에 참여하게 되었다. 그래서 그런지 이 수업은 Coursera 전체 강의 중 수료생 비율이 제일 높다고 한다. 이제 이어지는 Coursera 수업인 Principles of Reactive Programming을 수강신청하고 즐겁게 들으려고 한다. 클라우드 시대의 문턱에 서 있는 서버 프로그래머로서 배우고 따라해 볼 점이 아주 많을 것 같다.
