What is the Functional?

1. Introduction
2. Algebraic Data Type
3. Maybe or Not
4. Monadic Molecule Parser

얼마 전에 지인과 맥주 한잔을 하다가 iOS 개발을 Swift로 하고 있다 보니 함수형으로 못 쓰는 것도 아닌데 같이 일하는 사람들이 배울 생각이 없어서 도입하기 어렵다는 말을 들었다. 요즘 여기저기에서 폴리글랏이니 병렬처리니 하는 말과 함께 함수형 패러다임이 무엇인지 어디에 좋다는지 하는 설명은 많이 들려오고 있어 관심이 있는 사람은 많지만, 그래서 그걸 구체적으로 어디에 어떻게 쓰이는지에 대해 잘 몰라 동기부여가 되지 않는 사람들이 많다. 나도 입문 단계를 아직 벗어나지 못했다고 생각해서 앞으로 쓸 글에 잘못된 점이 있을 수도 있지만Codewars의 문제 몇 개를 풀어보면서 이게 어떤 모습인지, 어떻게 쓰이는지 한번 써볼까 한다(그러니 이상하거나 틀린 점을 발견한다면 이슈에 남겨주길 바란다) . 사실 개발자가 뭔가를 배우는 데는 생업에 관련된 게 큰 이유겠지만 가장 좋은 동기부여는 역시 재미가 아닐까 싶다. 이걸 보고 뭔가 재미있게 쓰인다고 느끼고 서점가서 책이라도 한번 펼쳐보는 사람이 생긴다면 이 글의 목표는 성공한 것이다.

시작하기에 앞서서 앞으로 관심을 가질 사람들에게 가장 도움이 될만한 것은 내가 어떤 책을 읽고 어떻게 공부해왔는지부터 말하는 것이 아닐까. 예전의 PiS 리뷰에서 썼듯이 처음에 재미를 느끼고 뭔가 해보기 시작한 것은 자바 개발자를 위한 함수형 프로그래밍과 함수형 자바스크립트 에서다. 함수형 언어라고 불리는 것들을 배우면 함수형 사고에 큰 도움이 되지만 처음부터 너무 큰 벽을 넘으려고 하면 지치기 쉽다. 그런 의미에서 지금 가장 익숙한 언어가 적당히 함수형을 쓸 수 있도록 지원한다면 그걸로 먼저 조금씩 사고를 익히는 것이 좋다. JavaScript도 좋고 Java 8도 충분하고 Swift라면 훌륭하다.

이미 많은 사람이 알고 있지만 그래도 가장 먼저 익숙해지면 좋은 개념은 함수를 자료형으로 생각하는 것이다. First-class function이니 Higher-order function이라는 개념들이 있지만 결국 함수도 하나의 자료형이라는 개념에 조건을 붙인 것이다. 함수(혹은 메소드)에서 정적인 자료를 넘기는 것에 익숙한 사람들이 가장 이질적으로 느끼는 것이 이런 것으로 생각한다. 함수를 넘기고 함수를 만들어서 리턴하고, 함수끼리 연산해서 새로운 함수를 만들고. 함수형 자바스크립트라는 책에서 독자에게 훈련시키는 이런 것이 아닐까 싶다. 그럼 익숙한 것부터 시작해보자.

1
2
3
4

var count = 0;
try{ (function a(){ count++; return a(); })(); }
catch(e) { console.log(e.message, count); }
// Maximum call stack size exceeded 17926

JavaScript로 코딩하다 보면 재귀함수에서 로직을 잘못 짜거나 생각했던 범위를 훨씬 넘는 값을 받았을 때 저런 문제가 발생한다. 대부분은 이미 아는 내용이겠지만 잠시 다른 이야기를 해보자면, 기계는 코드를 한 줄씩 읽어서 해석하다가 어딘가로 넘어가게 될 때(CALL), 현재 가지고 있는 값들을 어딘가에 저장해두고 다시 돌아올 위치를 기록한 다음에 넘어가게 된다. 그래서 어딘가로 계속 넘어가다 보면 기계의 물리적 혹은 논리적인 한계 때문에 실행환경에서 익셉션을 발생시키거나 프로세스가 강제로 종료된다. 많은 언어에서는 꼬리 재귀 최적화(Tail Recursion Optimization) 혹은 꼬리 호출 제거(Tail-call Elimination)라고 불리는 기능을 지원하는데, 어딘가(A)로 한번 넘어갔을 때 거기에서 다시 어딘가(B)로 넘어갈 때 A에서의 상태를 굳이 저장하지 않아도 된다면 돌아올 곳은 똑같으니 현재 값들을 저장하고 돌아올 곳을 기록하는 작업을 생략한 채 그냥 B로 넘어가는 식(JMP)으로 최적화가 가능하다.

그렇다면 JavaScript에서는 언어적인 한계 때문에 충분한 시간이 있어도 충분히 많은 재귀를 할 수 없을까? JavaScript에서도 어떤 패턴을 통해 콜스택을 일정하게 유지할 수 있다(하지만 아마 다소 메모리의 증가는 생길 것이다). 간단한 예를 들어서 다음과 같은 피보나치 수열이 있다고 해보자.

1
2
3
4

const fibo = (n) =>
  n < 3
    ? 1
    : fibo(n-1) + fibo(n-2);

위에서 말했듯이 저장할 상태가 없어야하는데 양쪽으로 재귀를 돌다 보니 하나를 돌때 다른 하나를 저장하고 있어야 한다. 그러니 구조를 약간 바꾸어보자.

1
2
3
4
5
6
7

const f = (a, b, n) =>
  n < 2
    ? a
    : f(b, a+b, n-1);


const fibo2 = (n) => f(1, 1, n);

인자가 많이 늘어났지만 저장해야하는 상태없이 다음 재귀로 넘어갈 수 있게 되었다. 이제 콜 스택의 깊이를 유지하려면 함수를 재귀적으로 실행시키지 않고 실행하고 끝난 뒤에 다시 실행하도록 순서를 변경하면 된다.

1
2
3
4
5
6
7
8
9
10

const f2 = (a, b, n) =>
  n < 2
    ? a
    : () => f2(b, a+b, n-1)

const fibo3 = (n) => {
  let t = () => f2(1, 1, n);
  while(typeof (t = t()) === 'function');
  return t;
}

다음 실행될 재귀를 함수로 감싸서 리턴하면 한번에 하나씩 실행이 되며, 함수가 아닌 값을 받았을 때 재귀를 대신한 루프가 종료된다. 이해하기 편하도록 원형fibo2을 최대한 유지해서 fibo3를 작성했고, 이걸 일반화시킨 패턴을 트램펄린(trampoline) 이라고 부른다. 사실 트램펄린 자체는 함수형 패턴의 예시라기보다 CPS(Continuation passing style)의 예라고 설명하는 쪽이 더 적절하다. 다만 이 패턴이 재미있는 것은 JavaScript에서 지원하지 않는 꼬리 재귀 최적화와 지연평가의 개념, 그리고 우회 구현이 동시에 들어있기 때문에 언어의 한계를 기술적으로 우회한다는 점에서, 그리고 그 기반에 대한 개념이 함수형과 맞닿아있다는 점에서 예시로 가져왔다. 함수형 자바스크립트 책을 처음 읽었을 때 이해하기 어려워서 미뤄뒀는데 계속 함수형처럼 코딩하려고 노력하다 나중에 다시 읽으니 그 전에 왜 이해하지 못했나 싶었다. 아마 위에서 언급했던 것처럼 자료형처럼 넘기고 받는다는 생각에 이질감이 들어서였을까.

Reference

• Continuation-passing and tail call elimination in Javascript
• 예제로 설명하는 자바스크립트에서의 Continuation-passing style
• 함수형 자바스크립트, 한빛미디어 2014