[모던 자바 인 액션] chap19. 함수형 프로그래밍 기법

내용
일급 시민, 고차원 함수, 커링, 부분 적용
영속 자료구조
자바 스트림을 일반화하는 게으른 평가와 게으른 리스트
패턴 매칭, 자바에서 패턴 매칭을 흉내 내는 방법
참조 투명성과 캐싱

 

1. 함수는 모든 곳에 존재한다

함수형 언어 프로그래밍이란 함수를 마치 일반값처럼 사용해서 인수로 전달하거나, 결과로 반환받거나, 자료 구조에 저장할 수 있음을 의미한다. 일반값처럼 취급할 수 있는 함수를 일급 함수라고 한다. 자바 8에서는 :: 연산자로 메서드 참조를 만들거나 (int x) -> x + 1 같은 람다 표현식으로 직접 함숫값을 표현해서 메서드를 함숫값으로 사용할 수 있다.

Function<String, Integer> shortToInt = Integer::parseInt;
// 자바 8에서는 이렇게 메서드 참조로 Integer.parseInt를 저장할 수 있다.

 

1. 고차원 함수

Comparator<Apple> c = comparing(Apple::getWeight);
// 함수를 인수로 받아 다른 함수를 반환한다.

Function<String, String> transformationPipeline = addHeader
	.andThen(Letter:checkSpelling)
    	.andThen(Letter:addFotter);
// 3장에서 함수를 조립해서 연산 파이프라인을 만들 때 위 코드와 비슷한 기능을 활용했다.

함수형 프로그래밍 커뮤니티에 따르면 Comparator.comparing처럼 다음 중 하나 이상의 동작을 수행하는 함수를 고차원 함수라 부른다.

• 하나 이상의 함수를 인수로 받음
• 함수를 결과로 반환

자바 8에서는 함수를 인수로 전달할 수 있을 뿐 아니라 결과로 반환하고, 지역 변수로 할당하거나, 구조체로 삽입할 수 있으므로 자바 8의 함수도 고차원 함수라고 할 수 있다. 

 

2. 커링 - x와 y라는 두 인수를 받는 함수 f를 한 개의 인수를 받는 g라는 함수로 대체하는 기법이다.

이때 g라는 함수 역시 하나의 인수를 받는 함수를 반환한다. 함수 g와 원래 함수 f가 최종적으로 반환하는 값은 같다. 즉, f(x,y) = (g(x))(y)가 성립한다. 예를 들어 섭씨를 화씨로 변환하는 공식은 CtoF(x) = x * 9 / 5 + 32이다. 이러한 패턴을 코드로 적용해보면 아래와 같다.

public double converter(double x, double f, double b) {
    return x * f + b;
}
double convertCtoF = converter(1000, 9.0/5, 32);
double convertUSDtoGBP = converter(1000, 0.6, 0);
double convertKmToMi = converter(1000, 0.6124, 0);

이러한 방법은 인수의 기준치를 사용할때마다 넣는 일은 귀찮은 일이며 오타도 발생하기 쉽다. 각각 변환하는 메서드를 따로 만드는 방법도 있지만 로직을 재활용하지 못한다. 이러한 상황에서 커링이라는 개념을 활용해 특정 상황에 적용할 수 있다. 한 개의 인수를 갖는 변환 함수를 생산하는 팩토리(factory)를 정의하는 것이다.

public DoubleUnaryOperator curriedConverter(double f, double b) {
    return (double x) -> x * f + b;
}
DoubleUnaryOperator convertCtoF = curriedConverter(9.0/5, 32);
DoubleUnaryOperator convertUSDtoGBP = curriedConverter(0.6, 0);
DoubleUnaryOperator convertKmToMi = curriedConverter(0.6124, 0);
convertCtoF.applyAsDouble(1000);
convertUSDtoGBP.applyAsDouble(1000);
convertKmToMi.applyAsDouble(1000);

위 메서드에 f와 b만 넘겨주면 우리가 원하는 작업을 수행할 함수가 반환된다. 이러한 방식으로 변환 로직을 재활용할 수 있으며 다양한 변환 요소로 다양한 함수를 만들 수 있다.

 

2. 영속 자료구조

함수형 프로그램에서는 함수형 자료구조, 불변 자료구조 등의 용어도 사용하지만 보통은 영속 자료구조라 부른다(여기서 말하는 영속은 데이터베이스에서 프로그램 종료 후에도 남아있음을 의미하는 영속과는 다른 의미).

함수형 메서드에서는 전역 자료구조나 인수로 전달된 구조를 갱신할 수 없다? 자료구조를 바꾼다면 같은 메서드를 두 번 호출했을 때 결과가 달라지면서 참조 투명성이 위배되고 인수를 결과로 단순하게 매핑할 수 있는 능력이 상실되기 때문이다.

 

1. 파괴적인 갱신과 함수형

Class TrainJourney {
	public int price;
    public TrainJourney onward;
    public TrainJourney(int p, TrainJourney t) {
    	price = p;
        onward = t;
    }
}

static TrainJourney link(TrainJourney a, TrainJourney b) {
	if(a==null) return b;
    TrainJourney t = a;
    while(t.onward != null) {
    	t = t.onward;
    }
    t.onward = b;
    return a;
}

TrainJourney firstJourney = new TrainJourney(1000, new TrainJourney(2000, null));
TrainJourney secondJourney = new TrainJourney(3000, new TrainJourney(4000, null));
TrainJourney newJourney = link(firstJourney, secondJourney);
// TrainJourney{price=1000, onward=TrainJourney{price=2000, onward=TrainJourney{price=3000, onward=TrainJourney{price=4000, onward=null}
// firstJourney도 newJourney처럼 바뀐것을 확인할 수 있다.
// link는 자료구조를 바꿔버리는 파괴적인 갱신을 하게된다.

static TrainJourney append(TrainJourney a, TrainJourney b) {
	return a==null ? b : new TrainJourney(a.price, append(a.onward, b));
}
TrainJourney newJourney = append(firstJourney, secondJourney);
// TrainJourney{price=1000, onward=TrainJourney{price=2000, onward=TrainJourney{price=3000, onward=TrainJourney{price=4000, onward=null}
// append는 자료구조를 갱신하지않아, 바꾸지 않는다.

 

2. 트리를 사용한 다른 예제

class Tree {
    private String key;
    private int val;
    private Tree left, right;
    public Tree(String key, int val, Tree left, Tree right) {
        this.key = key;
        this.val = val;
        this.left = left;
        this.right = right;
    }
}
class TreeProcessor {
    public static int lookup(String k, int defaultVal, Tree t) {
        if (t == null) return defaultVal;
        if (k.equals(t.key)) return t.val;
        return lookup(k, defaultVal, k.compareTo(t.key) < 0 ? t.left : t.right);
    }
    // 트리의 다른 작업을 처리하는 기타 메서드
}

새로운 노드를 추가할 때는 주의해야 한다. 가장 쉬운 방법은 update 메서드가 탐색한 트리를 그대로 반환하는 것이다. (새로운 노드를 추가하지 않으면 기존 트리가 그대로 반환된다.)

하지만 이 방법은 그리 깔끔하지 못하다. 사용자는 update가 즉석에서 트리를 갱신할 수 있으며, 전달한 트리가 그대로 반환된다는 사실, 원래 트리가 비어있으면 새로운 노드가 반환될 수 있다는 사실을 모두 기억해야 하기 때문이다.

 

public void update(String k, int newVal, Tree t) {
    if (t == null) { /* 새로운 노드를 추가해야 함 */ }
    else if (k.equals(t.key)) t.val = newVal;
    else update(k, newVal, k.compareTo(t.key) < 0 ? t.left : t.right);
} 

public Tree update(String k, int newVal, Tree t) {
    if (t == null)
        t = new Tree(k, newVal, null, null);
    else if (k.equals(t.key)) 
        t.val = newVal;
    else if (k.compareTo(t.key) < 0) 
        t.left = update(k, newVal, t.left);
    else 
        t.right = update(k, newVal, t.right);
    return t;
}

두 가지 update 버전 모두 기존 트리를 변경한다. 즉, 트리에서 저장된 맵의 모든 사용자가 변경에 영향을 받는다.

 

3. 함수형 접근법 사용

 

위 트리의 문제를 함수형으로 어떻게 처리할 수 있을까? 우선 새로운 키/값 쌍을 저장할 새로운 노드를 만들어야 한다. 또한 트리의 루트에서 새로 생성된 노드의 경로에 있는 노드들도 새로 만들어야 한다.

public Tree fupdate(String k, int newVal, Tree t) {
    return (t == null) ?
        new Tree(k, newVal, null, null) :
        k.equals(t.key) ?
            new Tree(k, newVal, t.left, t.right) :
            k.compareTo(t.key) < 0 ? 
                new Tree(t.key, t.val, fupdate(k, newVal, t.left), t.right) :
                new Tree(t.key, t.val, t.left, fupdate(k, newVal, t.right));
}

위 코드에서는 if-then-else 대신 하나의 조건문을 사용했는데 이렇게 해서 위 코드가 부작용이 없는 하나의 표현식임을 강조했다. 하지만 취향에 따라 if-then-else 문으로 코드를 구현할 수 있다. 이전 update 메서드는 모든 사용자가 같은 자료구조를 공유하며 프로그램에서 누군가 자료구조를 갱신했을 때 영향을 받는 반면에 fupdate는 순수한 함수형이다. fupdate에서는 새로운 Tree를 만든다. 하지만 인수를 이용해서 가능한 한 많은 정보를 공유한다.

이와 같은 함수형 자료구조를 영속이라고 하며 따라서 프로그래머는 fupdate가 인수로 전달된 자료구조를 변화시키지 않을 것이라는 사실을 확신할 수 있다. '결과 자료구조를 바꾸지 말라'는 것이 자료구조를 사용하는 모든 사용자에게 요구하는 단 한 가지 조건이다.

 

3. 스트림과 게으른 평가

1. 자기 정의 스트림

다음 코드처럼 소수 스트림을 계산할 수 있었다.

public boolean isPrime(int candidate) {
    int candidateRoot = (int) Math.sqrt((double) candidate);
    return IntStream.rangeClosed(2, candidateRoot)
        .noneMatch(i -> candidate % i == 0);
}

public Stream<Integer> primes(int n) {
    return Stream.iterate(2, i -> i + 1)
        .filter(this::isPrime)
        .limit(n);
}

이 코드는 후보 수로 정확히 나누어떨어지는지 매번 모든 수를 반복 확인해야한다. 이론적으로 소수로 나눌 수 있는 모든 수를 제외할 수는 있다.

 

1 단계 : 스트림 숫자 얻기

IntStream.iterate 메서드를 이용하면 2에서 시작하는 무한 숫자 스트림을 생성할 수 있다.

public IntStream numbers() {
    return IntStream.iterate(2, n -> n + 1);
}

2 단계 : 머리 획득

IntStream은 첫 번째 요소를 반환하는 findFirst라는 메서드를 제공한다.

public int head(IntStream numbers) {
    return numbers.findFirst().getAsInt();
}

3 단계 : 꼬리 필터링

스트림의 꼬리를 얻는 메서드를 정의한다.

public IntStream tail(IntStream numbers) {
    return numbers.skip(1);
}

다음처럼 획득한 머리로 숫자를 필터링할 수 있다.

IntStream numbers = numbers();
int head = head(numbers);
IntStream filtered = tail(numbers).filter(n -> (n & head) != 0);

4 단계 : 재귀적으로 소수 스트림 생성

 

반복적으로 머리를 얻어서 스트림을 필터링한다.

public IntStream primes(IntStream numbers) {
    int head = head(numbers);
    return IntStream.concat(
        IntStream.of(head),
        primes(tail(numbers).filter(n -> n % head != 0))
    );
}

 

 

게으른 평가

만약 4단계 코드를 실행하면 IllegalStateException이 발생할 것이다. 위 코드에서는 호출하면 스트림이 완전 소비되는 두 개의 최종 연산 findFirst와 skip을 사용했기 때문이다. 그리고 IntStream.concat은 두 개의 스트림 인스턴스를 인수로 받는데, 두 번째 인수가 primes를 직접 재귀적으로 호출하면서 무한 재귀에 빠진다. "재귀적 정의 허용하지 않음"같은 Java8의 스트림 규칙은 우리에게 아무 해도 끼치지 않으며 오히려 이 규칙 덕분에 데이터베이스 같은 질의를 표현하고 병렬화 할 수 있는 능력을 얻을 수 있다. 그래서 Java8 설계자는 이 같은 제한을 두기로 결정했다. 결론적으로 concat의 두 번째 인수에서 primes를 게으르게 평가하는 방식으로 문제를 해결할 수 있다. 좀 더 기술적인 프로그래밍 언어의 용어로는 게으른 평가를 비 엄격한 평가 또는 이름에 의한 호출(콜 바이 밸류)이라 한다.

 

2. 게으른 리스트 만들기 - 스트림은 최종 연산을 적용해서 실제 계산을 해야 하는 상황에서만 실제 연산이 이루어진다.

특히 스트림에 여러 연산(filter, map, reduce 등)을 적용할 때 이와 같은 특성을 활용할 수 있다. 게으른 특성 때문에 각 연산별로 스트림을 탐색할 필요 없이 한 번에 여러 연산을 처리할 수 있다.

 

기본적인 연결 리스트

Supplier<T>를 이용해서 게으른 리스트를 만들면 꼬리가 모두 메모리에 존재하지 않게 할 수 있다. Supplier<T>로 리스트의 다음 노드를 생성할 것이다. 

interface MyList<T> {
    T head();
    MyList<T> tail();
    default boolean isEmpty() {
        return true;
    }
}

class LazyList<T> implements MyList<T> {
    final T head;
    final Supplier<MyList<T>> tail;

    public LazyList(T head, Supplier<MyList<T>> tail) {
        this.head = head;
        this.tail = tail;
    }

    @Override
    public T head() {
        return head;
    }

    @Override
    public MyList<T> tail() {
        return tail.get();
    }
    
    public boolean isEmpty() {
        return false;
    }
}

이제 연속적인 숫자의 다음 요소를 만드는 LazyList의 생성자에 tail 인수로 Supplier를 전달하는 방식으로 n으로 시작하는 무한히 게으른 리스트를 만들 수 있다.

public LazyList<Integer> from(int n) {
    return new LazyList<>(n, () -> from(n + 1));
}

LazyList<Integer> numbers = from(2);
        
int two = numbers.head();
System.out.println("two : " + two);

int three = numbers.tail().head();
System.out.println("three : " + three);

int four = numbers.tail().tail().head();
System.out.println("four : " + four);

실행 결과

만약 요청했을 때 코드가 실행되는 것이 아니라 2부터 시작해서 모든 수를 미리 계산하려 한다면 프로그램은 영원히 종료되지 않을 것이다. 그럼 위에 구현한 LazyList를 활용해서 게으른 소수 리스트를 생성해보자. 우선 LazyList에 요소들을 필터링할 filter 메서드를 구현(게으른 필터 구현)하고 적용해보자.

class LazyList<T> implements MyList<T> {
	
    ...
    
    public MyList<T> filter(Predicate<T> p) {
        return isEmpty() ? this : p.test(head()) ?
            new LazyList<>(head(), () -> tail().filter(p)) :
            tail().filter(p);
    }
    
    ...
}

public MyList<Integer> primes(MyList<Integer> numbers) {
    return new LazyList<>(numbers.head(),
        () -> primes(numbers.tail().filter(n -> n % numbers.head() != 0)));
}

tail과 head 호출을 연결해서 처음 세 개의 소수를 계산할 수 있다.

LazyList<Integer> numbers = from(2);

int two = primes(numbers).head();
System.out.println("two : " + two);

int three = primes(numbers).tail().head();
System.out.println("three : " + three);

int five = primes(numbers).tail().tail().head();
System.out.println("five : " + five);

실행 결과

이로써 함수를 자료구조 내부로 추가할 수 있고, 이런 함수는 자료구조를 만드는 시점이 아니라 요청 시점에 실행된다는 사실도 확인했다. 또한 게으른 리스트는 Java8의 스트림과의 연결고리를 제공한다. 하지만 자료구조의 10퍼센트 미만의 데이터만 활용하는 상황에서는 게으른 실행으로 인한 오버헤드가 더 커질 수 있다. 게으른 리스트가 게으르진 않을 수 있다는 말이다. 위 예제로 예를 들면 LazyList값을 탐색할 때 10번째 항목까지는 모든 노드를 두 번 생성하므로 10개가 아니라 20개의 노드가 생성되는데 이 작업은 게으르게 처리할 수 없고, LazyList 탐색을 요청할 때마다 tail의 Supplier가 반복적으로 호출된다는 점이 문제다. 처음 탐색 요청을 호출할 때만 tail의 Supplier가 호출되도록 하여(그리고 결과값을 캐시 해서) 이 문제를 해결할 수 있다. LazyList에 private Optional<LazyList<T>> alreadyComputed 필드를 추가하고 tail 메서드가 적절하게 리스트를 업데이트하도록 정리할 수 있다.

게으른 자료구조는 강력한 프로그래밍 도구이다. 애플리케이션을 구현하는 데 도움을 준다면 게으른 자료구조를 사용하되, 게으른 자료구조 때문에 효율성이 떨어진다면 전통적인 방식으로 코드를 구현해야 할 것이다.

 

4. 패턴 매칭

private static void simplify() {
    TriFunction<String, Expr, Expr, Expr> binopcase = // BinOp 표현식 처리
    (opname, left, right) -> {
      if ("+".equals(opname)) {	// 더하기 처리
        if (left instanceof Number && ((Number) left).val == 0) {
          return right;
        }
        if (right instanceof Number && ((Number) right).val == 0) {
          return left;
        }
      }
      if ("*".equals(opname)) {	// 곱셈 처리
        if (left instanceof Number && ((Number) left).val == 1) {
          return right;
        }
        if (right instanceof Number && ((Number) right).val == 1) {
          return left;
        }
      }
      return new BinOp(opname, left, right);
    };
    Function<Integer, Expr> numcase = val -> new Number(val);	// 숫자 처리
    Supplier<Expr> defaultcase = () -> new Number(0);	// 수식을 인식할 수 없을때 기본 처리
    
    return patternMatchExpr(e, binopcase, numcase, defaultcase);	// 패턴 매칭 적용
}

다음처럼 simplify 메서드를 호출할 수 있다.

Expr e = new BinOp("+", new Number(5), new Number(0));
Expr match = simplify(e);
System.out.println(match);
// 5 출력

 

마치며

• 일급 함수란 인수로 전달하거나, 결과로 반환하거나, 자료구조에 저장할 수 있는 함수다.
• 고차원 함수란 한 개 이상의 함수를 인수로 받아서 다른 함수를 반환하는 함수다. 자바에서는 comparing, andThen, compose 등의 고차원 함수를 제공한다.
• 커링은 함수를 모듈화하고 코드를 재사용할 수 있도록 지원하는 기법이다.
• 영속 자료구조는 갱신될 때 기존 버전의 자신을 보존한다. 결과적으로 자신을 복사하는 과정이 따로 필요하지 않다.
• 자바의 스트림은 스스로 정의할 수 없다.
• 게으른 리스트는 자바 스트림보다 비싼 버전으로 간주할 수 있다. 게으른 리스트는 데이터를 요청했을 때 Supplier를 이용해서 요소를 생성한다. Supplier는 자료구조의 요소를 생성하는 역할을 수행한다.
• 패턴 매칭은 자료형을 언랩하는 함수형 기능이다. 자바의 switch문을 일반화할 수 있다.
• 참조 투명성을 유지하는 상황에서는 계산 결과를 캐시할 수 있다.
• 콤비네이터는 둘 이상의 함수나 자료구조를 조합하는 함수형 개념이다.