Git the Princess! - Toggl

이 농담의 백미는 오직 Lisp만이 실제로 공주를 구했다는 것임.
The best part of this is that Lisp is the only that actually rescues the princess. - Slap*Happy

왜 지금 함수형 프로그래밍인가?

Java에 Stream이 추가된지 7년이 되어갑니다. 저는 지금까지 함수형 프로그래밍을 의도적으로 공부했다기 보단 자바의 Stream과 Optional, 그리고 Spring WebFlux와 프론트엔드의 React 라이브러리를 사용하면서 간접적으로 함수형 프로그래밍을 익혀왔습니다. 점점 실무에서 함수형 프로그래밍과 관련된 부분이 늘어나고 있기 때문에 필요한 부분만 그때 그때 익히는 것이 아니라 함수형 프로그래밍 자체에 대해서 제대로 공부해야 할 때가 왔다고 느낍니다(오히려 늦은 감도...).

사용자와의 interaction을 처리해야 하는 프론트엔드/모바일 앱 개발 진영에서는 이미 비동기로 프로그래밍하는 방식이 익숙하고, Rx계열의 라이브러리를 통해 사용자의 input을 비동기 데이터 스트림으로 추상화해서 구독(Observe, Subscribe)하는 반응형 프로그래밍하는 방식도 보편적입니다. Spring에서는 5.0(2017년)부터 WebFlux라는 이름으로 반응형 프로그래밍 방식을 지원하기 시작했고, Spring Boot 2.3(2020년 5월 15일)에는 R2DBC가 정식으로 지원되어 백엔드 애플리케이션과 DBMS간의 통신을 비동기로 처리하기가 쉬워졌습니다.

아래는 반응형(reactive), 비동기(asynchronous), 함수형(functional) 프로그래밍간의 관계를 명확히 하기 위해 참고한 글들입니다. 아래 글들을 요약하자면: 반응형 프로그래밍은 비동기 데이터 스트림을 다루는 프로그래밍 기법입니다. 비동기란 메인 프로그램의 흐름을 막지 않으면서 동시에 여러가지 일을 처리하는 것이고, 이를 위해 함수를 어떤 함수의 매개변수로 넘기는 방식의 프로그래밍을 해야 합니다. 따라서 비동기 프로그래밍은 태초부터 존재하던 함수형 프로그래밍 방식과 잘 맞습니다.

즉 함수형 프로그래밍은 반응형 프로그래밍의 기초가 됩니다.

함수형 프로그래밍과 Side Effect

※ 여기서 함수형 프로그래밍이랑 순수 함수형 프로그래밍(Purely functional programming)을 말합니다.

함수란 무엇인가

수학의 함수

두 개의 변수 x, y 사이에서, x가 일정한 범위 내에서 값이 변하는 데 따라서 y의 값이 종속적으로 정해질 때, x에 대하여 y를 이르는 말. y가 x의 함수라는 것은 y=f(x)로 표시한다.

- 네이버 국어사전: 함수

  1. 두 개의 변수
    • 즉 함수의 매개변수는 1개다 (!?).
  2. 일정한 범위
    • 정의역(Domain), 공역(Codomain), 치역(Range)
  3. 동일한 input에 대해서 동일한 output이 나옴 (Referential transparency)

컴퓨터의 함수

우리 모두가 알고있는 그것... 수학의 함수와 약간 다릅니다. 가장 큰 차이점은 "Side effect가 발생할 수 있다"는 것.

Side effect의 여부에 따라 함수를 2가지로 나눌 수 있습니다.

  1. Side effect가 없을 때: function (pure function이라고도 불림)
  2. Side effect가 있을 때: procedure
#include <stdio.h>

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

int counter = 0;

// procedure
int getNextPositiveInt() {
  return ++counter;
}

// printf때문에 side effect가 발생하므로 int main(void)는 procedure
int main(void) {
  int a = 1;
  int b = 2;
  printf("add(%d, %d) == %d\n", a, b, add(a, b));

  for (int i = 0; i < 3; i++)
    printf("nextPositiveInt: %d\n", getNextPositiveInt());

  return 0;
}

위 코드에서 int add(int, int)는 함수고 int getNextPositiveInt()int main(void)는 프로시저입니다. 엄밀하게 따지면 Side effect가 있는 프로시저를 함수라고 부르면 안 됩니다.

함수형 프로그래밍에서는 Side effect 없이 코딩을 한다고?

하지만 컴퓨터는 finite state machine인걸? 상태를 변경하는 Side effect로 돌아가는 기계를 Side effect를 없이 사용한다고? 이게 무슨소리야?

물론 Side effect를 완전히 없앨 수 없지만.. Side effect가 발생하는 부분과 발생하지 않는 부분을 확실하게 구분하면 에러를 줄일 수 있습니다. 아래와 같은 효과도 있는데요,

  • (심리적인 효과) Side effect가 없다 → 함수가 외부 세계에 영향을 주지 않는다 → 함수의 return값만 신경쓰면 된다 → 마음이 편하다.
  • (기능적인 효과) Side effect가 없다 → 동일한 매개변수에 대해서 항상 동일한 값이 나온다 (referential transparency) → 캐싱이 가능하다.

첫인상

저는 C, C++, Java만 알던 학부생 시절 2016년에 프로그래밍 언어론 수업에서 함수형 프로그래밍을 처음 접했습니다.

?????
  • 머?? 함수 안에 함수를 선언한다고? 그게 돼??? 굳이 왜?????
  • 머?? 함수에 이름이 없다고????
  • 머??? 재귀를 적극적으로 사용한다고??? 함수콜 오버헤드는???? 스택 오버플로는??????
  • 머????? 객체 상태를 바꾸지 않고 매번 새로운 객체를 생성한다고????? 메모리가 남아돌아??????
  • 하스켈????? 커리???????? 이게뭐야ㅠ
  • 실무에서 잘 안쓴다고 하던데 일단 객체지향부터 제대로 알자...

하지만 시나브로 함수형 프로그래밍을 제대로 공부해야할 때가 왔습니다.

함수형 프로그래밍... 너는 계획이 다 있구나

Java 사용자들에겐 몇 년 전부터 함수형 프로그래밍이 주목받고 실무에 영향을 주기 시작했지만, 함수형 프로그래밍은 람다 계산법(Lambda calculus)이라는 이름으로 태초부터 있었습니다. 람다 계산법에 영향을 받은 프로그래밍 언어의 예시로 근본의 LISP과 공포의 Haskell을 들 수 있습니다.

근본의 LISP: 1958년생. 아직도 팔팔하게 살아있는 언어입니다. LISP 매니아가 많습니다. 교환학생 신분으로 미국에 유학 갔을 때 컴파일러 교수님이 LISP 괴물이었습니다... 덕분에 C언어로 Pascal → LISP 으로 변환하는 컴파일러를 작성했었습니다.

공포의 Haskell: 1990년생. 하위호환성을 보장하지 않는 것으로 악명이 높습니다. 항상 최신의 것(State-of-the-art)을 지향합니다. 프로그래밍 언어론 수업의 과제로 Haskell로 ragged sudoku 문제를 푸는 프로그램을 만들었었는데 생소한 문법과 사용법 때문에 너무 어려웠습니다. 몇 년 전에 페이스북이 Spam filter를 Haskell로 만들어서 개발자들에게 충격을 주기도 했습니다. 이게 실무에서 되네?

명령형 프로그래밍은 CPU에서부터, 함수형 프로그래밍은 수식에서부터

지금까지 다양한 프로그래밍 언어들이 고안되었고, 언어마다 유도하는 생각의 방식이 있다. 컴퓨터로 계산한다는 것을 무엇으로 보냐에 따라 다른 방식의 언어가 만들어졌다.

이게 무슨 말인가? 튜링(Alan Turing)이 정의한 소프트웨어는 튜링기계다. '기계적으로 계산 가능한 것'이 뭐냐를 정의한 것이 튜링의 경우 튜링기계였다. 원시적이지만, 구체적이고 명백한 기계다. 테이프가 있고 정해진 규칙표에 따라서 테이프에 문자를 읽고 쓰며 동작하는 기계.

튜링과 같은 시기에 처치(Alonzo Church)는 '기계적으로 계산 가능한 것'을 다른 스타일로 정의한다. 람다 계산법Lambda calculus이라는 것이다. 튜링 기계만큼 원시적이지만 '기계'의 모습은 없다. 심벌을 단순히 다루는 함수만으로 계산을 정의한다.

튜링기계와 람다 계산법은 표현력이 똑같다. 튜링 기계로 돌릴 수 있으면 람다 계산법으로도 계산할 수 있고 그 반대도 그렇다.

...

이 두 언어는 각각 다른 관점에서 소프트웨어를 보도록 유도한다. 튜링기계는 소프트웨어를 기계에게 전달하는 명령으로 보게 한다. 람다 계산법은 소프트웨어를 상위의 세계에서 논리적으로 따져가는 계산식으로 보게 한다.

두 개의 판이한 기원이 있다는 건 행운이다. 하나만으로는 프로그래밍 기술은 멀리 날 수 없었다. 튜링기계와 람다 계산법의 두 중력이 맞물릴 때 프로그래밍 기술은 비로소 좀 더 높이 올라설 수 있었다. 이 두 중력은 프로그래밍 언어의 연구도 전혀 다르게 이끌었고, 그래서 다채롭고 유용한 성과를 프로그래밍 세계에 선사해 주었다.

- 이광근, 『컴퓨터과학이 여는 세계』, 인사이트, 2017, p155 and p160

컴퓨터의 태동기부터 명령형 프로그래밍과 함수형 프로그래밍이 있었고 이 둘 모두 컴퓨터과학이라는 학문에 큰 성과를 가져다 주었습니다. 그러나 두 패러다임 중에서 입문자들에게 영향력이 컸던 것은 명령형 프로그래밍이었습니다. 컴퓨터의 동작 원리를 이해하기 위해서는 명령형 프로그래밍을 필수로 익혀야 하기 때문입니다.

제가 다녔던 학부의 커리큘럼도 명령형 프로그래밍 → 객체지향 프로그래밍 → 함수형 프로그래밍의 순서로 수강하도록 되어 있었습니다. 함수형 프로그래밍을 배우는 '프로그래밍 언어론' 과목은 필수가 아니어서 마음만 먹으면 함수형 프로그래밍을 피해갈 수도 있었습니다.

하.. 함수형 프로그래밍??

그리고 성능만 놓고 보면 아무래도 함수형 프로그래밍이 명령형 프로그래밍에 뒤질 수 밖에 없습니다. 함수를 부른(call)다는 일 자체의 오버헤드가 적지 않거든요. 때문에 제 학부시절만 하더라도 함수형 프로그래밍을 배워도 실무에서 쓸데가 없다는... 그런 분위기가 있었습니다.

그러나 CPU와 메모리의 극적인 발전, 함수형 프로그래밍 언어 컴파일러들의 놀라운 발전 덕분에 함수형 프로그래밍이 필연적으로 가지는 오버헤드는 무시할 만한 수준이 되었습니다. 게다가 반응형·비동기 방식의 프로그램을 작성할 때 함수형 프로그래밍으로 작성한 코드의 복잡도가 명령형 프로그래밍의 것보다 낮기 때문에 이제 자바 사용자들에게도 함수형 프로그래밍은 피해갈 수 없는 무언가가 되었습니다.

개인적인 견해에 따르면 프로그래밍 패러다임은 과거의 패러다임을 폐기시키는 혁명적인 과정을 거치지 않는 것으로 보인다. 오히려 과거에 있던 패러다임의 단점을 보완하는 발전적인 과정을 거치는 것으로 보인다. 간단히 말해 프로그래밍 패러다임은 혁명적(revolutionary)이 아니라 발전적(evolutionary)이다.

이런 사실은 비록 객체지향 패러다임을 주로 사용한다고 하더라도 다른 패러다임을 배우는 것이 도움이 될 것이라는 사실을 암시한다. '은총알은 없다'는 프레디 브룩스의 말을 기억하라. 객체지향 패러다임은 은총알이 아니다. 객체지향이 적합하지 않은 상황에서는 언제라도 다른 패러다임을 적용할 수 있는 시야를 기르고 지식을 갈고 닦아야 한다.

- 조영호, 『오브젝트』, 위키북스, 2019, p6

함수로 추상화(Abstract)하기

  • 추상
    • 抽象. 뽑을 추, 모양 상.
    • abstract: https://www.etymonline.com/word/abstract
      • late 14c., originally in grammar (in reference to certain nouns that do not name concrete things), from Latin abstractus "drawn away," past participle of abstrahere "to drag away, detach, pull away, divert;" also figuratively, from assimilated form of ab "off, away from" (see ab-) + trahere "to draw," from PIE root *tragh- "to draw, drag, move" (see tract (n.1)).
    • 중요한 것만 뽑아내고 중요하지 않은 부분을 생략하는 것(=요약)

함수형 프로그래밍은 추상화 수준을 극단으로 끌어올릴 수 있다고 책 The Joy of Kotlin에서 말합니다. 저는 이 책으로 함수형 프로그래밍을 공부하고 있습니다.

기쁘다 코틀린 오셨네

아래는 책에서 인상깊게 본 예시입니다. while을 사용하는 명령형 프로그래밍 코드의 단점을 이야기하면서 재귀를 사용하는 함수형 프로그래밍 코드로 개선합니다. tailrec 키워드 덕분에 재귀를 사용하면서도 while을 사용했을 때와 동일한 성능을 갖게 됩니다.

fun sum(n: Int): Int {
  var sum = 0
  var idx = 0
  while(idx <= n) {
    sum += idx
    idx += 1
  }
  return sum
}

Not a big deal, but this code contains many places where it could go wrong, especially since I had to translate the flowchart into a while loop implementation. It's easy to mess with the conditions. Should it be <= or <? Should idx be incremented before or after sum ? Obviously, this style of programming is for smart programmers who don't make these kinds of mistakes. But for the rest of us, who'd need to write many tests to check for potential errors, is it possible to write a corecursive implementation doing the same thing? Sure

- Pierre-Yves Saumont, 『The Joy of Kotiln』, Manning Publications, 2019, p90

fun sum(n: Int): Int {
  tailrec fun sum(s: Int, i: Int): Int = if (i > n) s else sum(s + i, i + 1)

  return sum(0,0)
}

정말로 tailrec를 사용하면 while을 사용했을 때와 동일한 성능을 발휘하는지 알아보기 위해 tailrec이 없는 재귀, tailrec이 있는 재귀, 그리고 while을 사용하는 반복문의 경우 3가지를 컴파일해서 바이트코드를 뽑아봤습니다..

1. tailrec 없는 재귀

// Recursive.kt
fun sum(n: Int): Int {
  fun sum(s: Int, i: Int): Int = if (i > n) s else sum(s + i, i + 1)

  return sum(0,0)
}

바이트코드중 위 함수의 로컬함수인 fun sum(s: Int, i: Int): Int 부분

  public final int invoke(int, int);
    Code:
       0: iload_2
       1: aload_0
       2: getfield      #28                 // Field $n:I
       5: if_icmple     12
       8: iload_1
       9: goto          25
      12: aload_0
      13: checkcast     #2                  // class RecursiveKt$sum$1
      16: iload_1
      17: iload_2
      18: iadd
      19: iload_2
      20: iconst_1
      21: iadd
      22: invokevirtual #18                 // Method invoke:(II)I
      25: ireturn

22: 레이블에서 함수콜(invokevirtual, 정확히 말하자면 메서드 콜)을 합니다.

2. tailrec이 있는 재귀

// Corecursive.kt
fun sum(n: Int): Int {
  tailrec fun sum(s: Int, i: Int): Int = if (i > n) s else sum(s + i, i + 1)

  return sum(0,0)
}

바이트코드중 위 함수의 로컬함수인 fun sum(s: Int, i: Int): Int 부분

  public final int invoke(int, int);
    Code:
       0: iload_2
       1: aload_0
       2: getfield      #28                 // Field $n:I
       5: if_icmple     12
       8: iload_1
       9: goto          28
      12: aload_0
      13: checkcast     #2                  // class CorecursiveKt$sum$1
      16: pop
      17: iload_1
      18: iload_2
      19: iadd
      20: iload_2
      21: iconst_1
      22: iadd
      23: istore_2
      24: istore_1
      25: goto          0
      28: ireturn

invokevirtual 대신 goto가 있는 것을 볼 수 있습니다. 함수콜이 사라졌군요!

3. while

// while.kt
fun sum(n: Int): Int {
  var sum = 0
  var idx = 0
  while(idx <= n) {
    sum += idx
    idx += 1
  }
  return sum
}

아래는 바이트코드입니다.

  public static final int sum(int);
    Code:
       0: iconst_0
       1: istore_1
       2: iconst_0
       3: istore_2
       4: iload_2
       5: iload_0
       6: if_icmpgt     20
       9: iload_1
      10: iload_2
      11: iadd
      12: istore_1
      13: iload_2
      14: iconst_1
      15: iadd
      16: istore_2
      17: goto          4
      20: iload_1
      21: ireturn

tailrec의 경우와 마찬가지로 goto를 볼 수 있습니다.

따라서 tailrec을 사용하면 함수콜대신 while의 경우처럼 goto를 사용하게 되므로 재귀함수의 문제점인 스택 오버플로와 함수콜 오버헤드가 사라집니다. 지쟈쓰...

저자는 절차적 프로그래밍의 trivial한 부분들이 함수형 프로그래밍에서는 함수로 추상화하므로 실수를 덜 할 수 있다고 합니다. 재귀를 사용하더라도 tailrec 덕분에 성능에 대한 걱정을 덜 수 있으니 함수형 프로그래밍으로 코드를 작성하지 않을 이유가 없습니다.

while뿐만 아니라 if else, for같은 control structure를 코틀린에서 제공하는 expression으로, 혹은 함수로 추상화를 하는 법을 배우게 됩니다.

물론 혼자만 함수형 프로그래밍에 익숙하다고 실무에서 코드들을 함수형 프로그래밍으로 작성하면 안되겠지요... 그래서 동료분들과 함수형 프로그래밍을 같이 공부하기 위해 그룹 스터디를 준비하고 있습니다.

부록: 타입 레벨 프로그래밍이란?

함수형 프로그래밍 방식으로 코드를 작성하다보면 함수의 타입이 복잡해지기 때문에 함수의 타입을 작성하는데 많은 노력이 들게 됩니다. 그래서 자연스럽게 타입만을 중점적으로 다루는 타입 레벨 프로그래밍에도 관심이 가게 되는데요,

타입(Type)과 값(Value)의 상호작용은 4가지로 구분할 수 있습니다.

  1. 값 → 값: Function
  2. 값 → 타입: Literal Types
  3. 타입 → 값: Reflection
    • Java의 Class<T>
  4. 타입 → 타입: 당연한 것... 뭐라고 불러야 할 지 모르겠습니다. Type Composition?

타입 레벨 프로그래밍은 '값 → 타입'과 '타입 → 타입'의 2가지 경우를 활용해서 컴파일 타임에 할 수 있는 일을 극대화합니다. 값으로 타입을 지정할 수 있는 Literal Types가 가능해지면 변수에 어떤 값이 들어가는지 컴파일 타임에 알 수 있기 때문에 컴파일러가 매우 세밀한 validation을 수행할 수 있게 됩니다.

// TypeScript
type LiteralType = "a" | "b"

let a: LiteralType = "a"
a = "b" // ok
a = "c" // error: Type '"c"' is not assignable to type 'LiteralType'.

TypeScript 4.1부터 Template Literal Types를 지원하게 되는데요, 이 기능으로 Type-level html parser를 작성한 코드도 있습니다😫. static하게 값이 결정되는 문자열이라면 값이 html문법을 만족하는지 컴파일 타임에 검증할 수 있습니다. 가슴이 뛰지 않나요?