What is the Functional?

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

Codewars에 분자식(문자열)에서 원자들이 몇 개인지 세는 문제가 있었다. 이미 제출한 답은 다음과 같은 구조였다.

1
2
3
4
5
6
7
8
9
10

const token = (str) => str.match(regToken);
const lexer = (arr) => arr.reduce((r,t) => ..., [])
const parse = (form) => {
  const syms = lexer(token(formula));
  let offset = 0;
  let buffer = traverse();
  return evaluate(buffer);

  function evaluate(array) {...}
}

옛날에 컴파일러 수업을 들었던 게 대충 생각나서 그래도 tokenizer로 식을 token 단위로 끊고, lexer로 symbol로 만들고(원래는 scan할 때 한 번에 하는 작업이었던 것으로 기억하지만), parse에서 Parse Tree를 만들어서 evaluator에서 실행(계산)하도록 만들려고 짜다가 구현을 할수록 구조는 복잡해지는데 비해 난이도는 올라가서 그냥 뒷부분은 한군데 섞어버렸다. 배운 걸 써먹기 위해서 이걸 다시 Haskell로 도전해보았다. 일단 문제를 단순화시켜서 괄호 없는 분자식을 구현해보자. 규칙은 다음과 같다.

1. 원소기호는 대분자와 소문자, 혹은 대문자로 이루어진다.
2. 개수는 원소기호 뒤에 오는 0자리 이상의 숫자로 없다면 1이 된다.
3. 원소기호와 개수를 합쳐서 동원소분자(homoatomic; 물론 제대로 된 명칭인지는 모름)라고 부른다.
4. 분자식은 동원소분자가 1개 이상 이어진다.

BNF라는 명칭만 기억나고 정확한 내용은 기억나지 않지만 비슷하게 옮겨보자면

• molecules = homoatomic | molecules
• homoatomic = atom amount | atom

이제 이걸 적용할 수 있는 파서를 만들어보자. 일단 파서의 적절한 타입을 만들어야 하는데, 함수형에서는 어떤 흐름을 기록하는데 자주 쓰이는 State라는 패턴이 있다. 모양은 대충 type State s a = s -> (a, s)가 된다. 즉, 현재의 어떤 상태s에서 그 상태에서 원하는 결과 a와 다음 상태s를 동시에 가져오게 된다. 상태는 변이(tramsform)되지만 원하는 값을 얻으면서 변수의 불변성(immutability)도 만족해서, 메모리만 충분하다면 구조에 따라 상태 변이를 기록할 수 있어서 추적하기 쉽다는 장점이 있다. 다시 돌아와서, State처럼 파싱할 문자열을 받아서 어떤 연산을 규칙에 맞는 결과물 T를 가져온 뒤 남은 문자열과 함께 돌려주는 일종의 State같은 타입을 Parser라고 정의해서 사용할 것이다.

1

// type Parser[T] = String -> (T, String)

먼저 앞에서 구현했던 것처럼 token을 가져오는 Parser를 만들어보자. Haskell의 경우에는 강한 타입에다 패턴 매칭을 지원하는 언어라서 원하는 타입이나 원하는 형태가 아니면 실패했다고 돌려줄 수 있지만, JavaScript는 둘 다 지원되지 않아서 내가 원하는 것이 맞는지 글자를 소모하지 않고 확인할 수 있는 기능과 글자를 소모해서 원하는 것인지 확인하는 기능 두 가지를 통해 tokenizer를 구현할 수 있다.

1
2
3
4

///// Parser => Parser
const ahead   = p => (str) => p(str) ? ['', str] : [];
///// Parser => Parser
const satisfy = p => (str) => p(str) ? [str[0], str.substr(1)] : [];

실패[]의 경우는 같고, 성공할 경우에 ahead는 아무것도 매칭하지 않은 채 원래의 문자열str을 돌려주고, satisfy의 경우 매칭된 글자와 나머지 문자열을 돌려준다. 원래는 튜플(Tuple)로 구현하는 게 좋지만, JavaScript에 그런 게 있을 리가.

이제 다음 글자가 대문자라는 파서를 만들려면 다음과 같이 만들면 된다.

1
2
3

const upper = satisfy(ch => 'A' <= ch[0] && ch[0] <= 'Z');

console.log( upper("H") ); // [ 'H', '' ]

하지만 타입 확인도 패턴 매칭도 존재하지 않아서 적절한 입력인지 확인할 수 있는 규칙과 그것을 합성할 수 있는 기능이 필요하다. 물론 합성 기능은 다음 글자가 소문자라는 파서를 만들었을 때 그 파서와 합성하는 데 사용할 수도 있다.

1
2
3
4
5
6
7
8

// (Parser, Parser) -> Parser
const and = (pa, pb) => (str) => {
  const ra = pa(str);
  if(ra.length === 0) return [];
  const rb = pb(ra[1]);
  if(rb.length === 0) return [];
  return [ra[0] + rb[0], rb[1]];
};

이제 첫 번째 파서가 성공할 경우 [match1, rest1]를 받아서 rest1을 다음 파서에 넘겨서 [match2, rest2]를 가져온 뒤에 [match1 + match2, rest2]라는 결과를 만들어주는 파서를 생성할 수 있게 되었다. 물론 둘 중 하나라도 실패하면 실패[]가 리턴된다. 이걸 사용해서 소문자 확인과 결합해보자.

1
2
3

const lower = satisfy(ch => 'a' <= ch[0] && ch[0] <= 'z');

console.log(and(upper, lower)("Mg")); // [ 'Mg', '' ]

그리고 앞서 만들어놓은 ahead와 더불어 원하는 조건인지 확인을 합성할 수도 있다.

1
2
3
4
5

const chr   = ahead(str => str.length > 0);

const upper = and(chr, satisfy(ch => 'A' <= ch[0] && ch[0] <= 'Z'));
const lower = and(chr, satisfy(ch => 'a' <= ch[0] && ch[0] <= 'z'));
const digit = and(chr, satisfy(ch => '0' <= ch[0] && ch[0] <= '9'));

다음 글자가 존재하는지, 존재할 때 원하는 범위의 글자가 맞는지를 한 번에 확인할 수 있는 파서들이 만들어졌다. 이제 원소기호를 파싱할 때 대문자와 소문자가 연속으로 올 때도 있지만, 대문자만 존재할 수 있으니 or를 만들어보자.

1
2
3
4
5
6

///// (Parser, Parser) -> Parser
const or = (pa, pb) => (str) => {
  const r = pa(str);
  if(r.length > 0) return r;
  else             return pb(str);
};

and처럼 파서 두 개를 받아서 새로운 파서를 만들어주는데, 차이는 첫 번째 파서가 실패하면 바로 실패했다는 결과를 넘겨주고 뒤의 규칙은 확인하지 않으며, 두 번째 파서가 실패할 경우에는 그 자체가 실패의 결괏값이므로 그냥 넘겨주면 된다. 이걸로 원소기호를 가져와 보자.

1
2
3
4

const atom   = or(and(upper, lower), upper);

console.log(atom("Mg")); // [ 'Mg', '' ]
console.log(atom("H"));  // [ 'H', '' ]

이제 둘 다 만족하게 되었다. 그럼 다음은 숫자를 0개 이상 받을 때인데, 재귀적인 규칙이라 앞에서 구현한 것들보다 약간 복잡해진다.

1

const amount = or(and(digit, amount), digit);

ES6에서 생긴 상수/변수인 const와 let은 호이스팅(hoisting)되지 않아서 이렇게 만들면 작동하지 않는다. 그래서 함수가 실행된 뒤에 amount를 읽을 수 있도록 소스가 약간 길어지지만 감수하면서 만들자면 다음과 같다.

1

const amount = (str) => or(and(digit, amount), digit)(str);

하지만 0개 이상을 읽는 경우가 이번뿐이 아니므로 이걸 좀 다듬어보자.

1
2

const many = (p) => (str) => or(and(p, many(p)), p)(str);
const amount = many(digit);

이제 many를 사용하면 나머지를 완성할 수 있다.

1
2

const homo   = or(and(atom, amount), atom);
const mole   = many(homo);

원소기호와 개수가 나오는 경우 혹은 원소기호만 있는 경우가 0번 이상 반복되는 것을 분자식이라고 한다. 아예 받지 않거나 실패하는 경우에는 아무것도 출력하지 않도록 결과를 다듬어보자.

1
2

const parse  = (p) => (str) => or(p, (str) => ['', str])(str)[0];
console.log(parse(mole)("H2O")); // H2O

이제 satisfy(ch=>ch=='(') 같은 식으로 열고 닫는 괄호를 3종류로 나누어서 규칙을 만들고 and와 or로 잘 조합하면 원래 문제의 답을 얻을 수 있을 것이다. 맨 위에 적어놓은 것보다 훨씬 깔끔한 구조로 함수들을 연결해서 답을 만들어냈다. 다만 현재 JavaScript 엔진들은 스코프를 생성하는 비용이 비싸서 함수 호출이 많아질수록 꽤 느려질 수 있다. 다만 불변성 구조가 유행하고 있고 엔진들도 최적화가 많이 진행되고 있으므로 trade-off를 통해 성능은 비슷하지만 구조는 깔끔하게 만들 수 있지 않을까 기대한다.

예전에 Rx, LINQ 등을 만든 에릭 마이어(Erik Meijer)가 edX에서 함수형 프로그래밍 입문을 강의한다길래 반가운 마음에 들어봤는데, 이상한 아저씨가 이상한 배경에 하이톤으로 함수형에 대해 역사부터 열심히 설명하길래 거기까지만 듣고 포기했던 적이 있다. 이번에 읽은 책이 Haskell 자체보다는 함수형 개념에 관해 설명한 책이라 Haskell로 문제를 풀어보면서 모르는 게 있어서 리뷰하려고 다시 들어봤더니 여전히 그 배경은 적응이 안 되지만 그래도 친절하고 좋은 강의였다(참고로 아래의 Contents 링크에 들어가면 화질별 강의와 슬라이드, 자막이 있다). 10월 15일에 다음 강의가 열리는데, 함수형이나 Haskell 입문에 관심 있는 분들께는 시각적인 어려움을 참작하고라도 매우 도움이 되는 강의니 추천한다.

ps, 구직중

Reference

• Monadic Parser Combinators - Graham Hutton, Erik Meijer

• Codewars

  • Molecule to atoms

• Hackage: Official Haskell Package archive

  • Text.ParserCombinators.ReadP

• Haskell/Wikibooks

  • Haskell/ParseExps

• FP101x

  • edX course 10/15~
  • Contents

What is the Functional?

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

Maybe

바로 앞에서 언급했듯이 최근에 생겼거나 메이저 업데이트를 한 언어들이라면 대부분 지원하는 Maybe(Optional, Option)라는 타입이 있다. 값을 가지고 있는 Just라는 타입과 값이 없는 Nothing이라는 타입 중 하나가 되는 섬 타입이다. 일단 함수형이니 하는 이야기는 잠시 미뤄두고 간단하게 Maybe를 만들어보자. Maybe의 정의를 간단하게 표현해보자면 다음과 같다.

1

data Maybe a = Just a | Nothing

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Maybe {
  toString() { throw new Error("Must be implemented."); }
}

class Just extends Maybe {
  constructor(v) {
    super();
    this.value = v;
    Object.freeze(this);
  }
  toString() { return `Just ${this.value.toString()}`; }
}

class Nothing extends Maybe {
  constructor(v) {
    super();
    Object.freeze(this);
  }
  toString() { return "Nothing"; }
}

const nothing = new Nothing();

정의는 단순하지만 같은 내용을 JavaScript로 구현하면 다소 길어진다. 소스를 보면 알겠지만, Just는 생성될 때만 값을 받을 수 있고 생성된 후에는 값을 변경할 수 없다. 이제 이 Maybe를 어떻게 다룰지에 대해서 생각을 해보자. Maybe 타입을 통해 어떤 연산을 하고 싶을 때 메소드를 추가해서 Maybe를 계속 생산하도록 만들면 편하겠지만, 값이 있다 없다의 속성을 가질 수 있다면 Maybe의 연산 결과를 Maybe라고 유지하고, 값이 없을 때는 계속 값이 없도록 유지하려면 그 결괏값을 보장해줘야한다. 이걸 만족하는 연산들을 생각해보자.

1. 값을 Maybe로 감싸서 새로운 Maybe를 만들어준다.
2. Maybe의 값에 그 값을 처리하는 함수를 적용하고 싶다.
3. 그런데 그 함수가 Maybe의 값일 수도 있다.
4. 함수의 결괏값 자체가 Maybe라면 어떨까?

1번의 구현은 간단하다.

1
2

///// unit : a -> Maybe a
const unit = (x) => new Just(x)

값만 존재할 때는 두 배로 만들려면 단순히 x * 2를 하면 되지만, Maybe로 감싸져 있으니 바로 적용하기 어렵다. 그러니 2번처럼 값을 처리하는 함수를 적용할 수 있는 기능을 구현해보자.

1
2
3
4
5
6
7
8
9
10
11
12

const isNothing = (m) =>
  m.constructor.name === "Nothing"

///// fmap : Maybe a, (a -> b) -> Maybe b
const fmap = (m, fn) =>
  isNothing(m)
    ? new Nothing
    : new Just(fn(m.value))

const doub = (d) => d * 2
console.log( fmap(unit(1), doub).toString() ); // Just 2
console.log( fmap(nothing, doub).toString() ); // Nothing

Maybe의 값이 함수일 경우에 그 함수를 다른 Maybe의 값에 적용해보자.

1
2
3
4
5
6
7
8
9

///// appl : Maybe (a -> b), Maybe a -> Maybe b
const appl = (mfn, ma) =>
  isNothing(mfn) || isNothing(ma)
    ? new Nothing()
    : unit(mfn.value(ma.value))

const mdoub = unit(doub);
console.log( appl(mdoub, nothing).toString() ); // Nothing
console.log( appl(mdoub, unit(1)).toString() ); // Just 2

그런데 모양을 보면 fmap과 비슷해서 fmap을 재사용해서 구현할 수도 있다.

1
2
3
4
5
6
7

const appl2 = (mfn, ma) =>
  isNothing(mfn)
    ? new Nothing()
    : fmap(ma, mfn.value)

console.log( appl2(mdoub, nothing).toString() ); // Nothing
console.log( appl2(mdoub, unit(1)).toString() ); // Just 2

이제 마지막으로 함수의 결과 자체가 Maybe일 경우를 생각해보자.

1
2
3
4
5
6
7
8
9

///// bind :  Maybe a, (a -> Maybe b) -> Maybe b
const bind = (ma, fn) =>
  isNothing(ma)
    ? new Nothing()
    : fn(ma.value)

const udoub = (d) => unit(doub(d));             // a -> Maybe b
console.log( bind(nothing, udoub).toString() ); // Nothing
console.log( bind(unit(1), udoub).toString() ); // Just 2

지금까지의 구현에서 JavaScript 자체의 복잡한 기능을 사용한 곳은 없다. 구현 자체가 어렵지도 않고 짧아서 여기까지는 다들 이해할 수 있을 것으로 생각한다. 그런데 안에 값을 넣을 수 있는 타입 중에서 개발자들이 항상 사용하고 있으며, 다들 사용법에 대해 아주 잘 알고 있는 타입이 하나 있다. 이제 Maybe를 Array와 비교해보자.

F, A, M with Array

1. Functor

앞에서 구현했던 fmap에서 설명을 돕기 위해 구현 위에 주석으로 타입을 적어놓은 것이 있다. 처음에는 Haskell 식으로 타입을 적었다가 이해하기 편하도록 수정했더니 무슨 언어인지 모를 내용이 되긴 했지만.

1

///// fmap : Maybe a, (a -> b) -> Maybe b

값을 가지고 있는 타입과 값을 변환하는 함수를 받아서 다른 값을 가지고 있는 타입으로 변환해준다. 이걸 이해하기 좋게 조금 수정해보자면,

1
2
3

///// amap : Array a, (a -> b) -> Array b
const amap = (arr, fn) => arr.map(fn);
console.log( amap([1,2,3], (n => String(n))) );  // [ '1', '2', '3' ]

a라는 타입의 값을 가지고 있는 어떤 타입을 ⓐ라고 하고, b의 경우를 ⓑ라고 하면, (a -> b) 함수를 통해 결과적으로 (ⓐ -> ⓑ)를 만족하도록 연산할 수 있는 타입을 Functor라고 부른다. Array에서는 그런 연산을 해주는 map 메소드를 가지고 있다.

2. Applicative Functor

순서대로 fmap 다음에 구현했던 appl을 이야기할 차례다.

1

///// appl : Maybe (a -> b), Maybe a -> Maybe b

applicative라는 표현 그대로 어딘가에 적용할 수 있는 Functor이다. 즉, 함수를 가지고 있는 Functor.

1
2
3
4
5
6
7
8
9

const doub = d => d * 2;
const incr = d => d + 1;

///// Array (a -> b), Array a -> Array b
const appl = (fns, as) => fns.map(fn => as.map(fn))
                             .reduce((r,b) => r.concat(b), [])
console.log(
  appl( [doub, incr], [1, 2, 3] )
); // [ 2, 4, 6, 2, 3, 4 ]

이렇게 (a -> b)를 가지고 있는 Array와 Array a를 통해 Array b를 만들었다. 위에서 말했듯 함수를 가지고 있는 Functor(Array (a -> b))와 다른 Functor(Array a)를 통해 다른 Functor(Array b)를 만들어내는 Applicative Functor를 map을 사용해서 간단히 구현해보았다. 하지만 Applicative Functor 자체를 본 적이 별로 없어서 내가 맞게 이해하고 있는 것인지 잘 모르겠다.

3. Monad

1

///// bind :  Maybe a, (a -> Maybe b) -> Maybe b

JavaScript에서는 lodash같은 라이브러리를 사용하지 않은 사람에게 익숙하지 않은 개념일 수 있지만, 다른 함수형 언어들을 써본 사람이라면 Sequence 종류에서 기본적으로 지원해주는 익숙한 개념이 있다.

1
2
3
4
5
6
7

const flatMap = function(fn) {
  return this.map(fn).reduce((r,a) => r.concat(a), [])
};

console.log(
  [1,2,3]::flatMap(d => Array(d).fill(d))
); // [ 1, 2, 2, 3, 3, 3 ]

바로 flatMap(간혹 concatMap)이라는 개념인데, (a -> ⓑ) 함수를 통해 (ⓐ -> ⓑ)를 만족하는 함수를 말한다. [1, [2], [[3]]]처럼 깊이가 다른 배열을 1차원으로 합치는 함수를 flatten이라고 표현하는데, flatten + map이 아닐까 싶다. Haskell에서는 Monad라면 Applicative Functor를 만족하고, Applicative Functor라면 Functor를 만족한다. 즉 Monad > Applicative > Functor로 상속하는 구조다. 잠깐 접해본 짧은 생각으로는 독립적인 개념으로 봐도 될 것 같은데(굳이 따지자면 Functor와 Applicative 정도는 has-a로 봐도 될 것 같지만), 내가 놓치고 있는 뭔가가 있는 것 같다.

이렇게 대수형 타입끼리 어떻게 연산하는지의 패턴들에 대해 알아봤는데, 왜 이렇게 복잡한 설명과 패턴을 통해 타입을 유지해야 하는가 싶은 생각이 들 수 있다. 가장 기본이 되는 개념은 간단한 개념이니 이것만 알면 된다! 라는 식의 글을 참 많이 봤는데, 내가 원점에 있을 때 (10, 0)쯤에 있던 글보다 쉽다는 글은 (0, 10)쯤에 있었고 그보다 쉽다고 주장하는 글은 (-10, 0)쯤에 있었다. 방향만 달라질 뿐, 거리는 좁혀지지 않는 느낌이었다. 그래도 그나마 알아들을만 했던 예제는 Railway oriented Programming이었다.

Just에 어떤 연산bind을 할 때 결과는 다시 Maybe가 되어야 하니 Just(그림에서의 Success) 혹은 Nothing(그림에서의 Failure) 둘 중 하나가 된다.

그런 연산이 여러 개 존재할 수 있다.

그때, 앞에서 어떤 처리들이 있었고 어디에서 Nothing으로 갔는지 관계없이 현재 들어온 값을 보고 Just인지 Nothing인지 구분(switch)해주는 하나의 블럭을 만들기만 하면 된다.

한번 Nothing이 되면 그 뒤에 어떤 연산이 오든 관계없이 Nothing으로 계속 유지된다. 앞의 어디에서 Nothing이 되었다는 것에 신경 쓰지 않고 현재의 값만 보고 Just인지 Nothing인지 연결하면 된다. 즉, bind(혹은 flatMap)에서는 현재 값과 앞뒤 타입만 맞추면 입력에서 출력까지 연산이 안전하다고 보장된다.

패턴이라는 것은 약속이고, 약속이라는 것은 그것이 보장된다는 말이다. 즉 일종의 추상화로 블랙박스 모델처럼 그림에서의 스위치만 구현해서 레일을 연결하면 안전하게 연산이 잘 흘러간다. OOP처럼 객체 단위의 추상화가 없으니 타입클래스에서 이런 패턴들이 그 역할을 대신하고, 덕분에 재사용하기 좋고 확장 가능해진다. 그런 것들의 기초가 되기 때문에 사람들이 중요하다고 많이 이야기하는 것이라고 생각한다.

여전히 이게 뭐다라고 정의내려서 설명하기는 어렵지만 이제 A가 B다라는 말에서 그게 맞거나 틀리다는걸 구분할 수는 있는 것 같다. 사실 이 글을 쓰게 된 목적 중 하나는 이거다. 그동안 함수형 언어를 기껏해야 퀴즈 몇개 풀어보는 정도 이외에는 제대로 써본 적이 없다보니 알듯말듯 한 상태가 몇년째 계속되고 있는데, 최근에 Haskell 책 한권을 읽으면서 그 감이 약간 더 구체화된 김에 정리를 해서 더 잡기 위해서다. 물론 조금 어긋난 내용이 있을 수도 있고 아예 잘못된 내용이 있을 수 있어서 언젠가 이 글을 읽고 이불킥할지도 모르겠지만, 이번 기회에 정리하지 않으면 몇년 더 이해할 기회가 오지 않을 것같다는 느낌이 들었다. 그러니 틀린게 있으면 틀린거고, 아니면 좋고. 이제 Monad라는게 뭔지 대충 정리를 해밨으니 이걸로 뭘 할 수 있는지 한번 써먹어보자.

ps, 타입을 유지하기 위한 연산의 패턴들에 대해서 알아봤는데 이런 것들이 타입론 (Type Theory)이나 범주론(Category Theory)에 속한 것이라면, "정수의 덧셈은 정수에 '닫혀있다'"라고 말하는 것처럼 연산 자체의 성질에 대해서 논하는 군론(Group Theory)라는 것이 있고 그 중 모노이드(Monoid)라는 개념을 모나드와 함께 사용하면 더 편하게 사용할 수 있는데 그 부분에 대해서는 지금보다 아는 것이 좀 더 생기면 다뤄보고 싶다.

ps2, 다시 말하지만 ps도 맞는지 확신이 없다.

Reference

• Hackage: Official Haskell Package archive

  • Control.Monad
  • Control.Applicative
  • GHC.Base | Source

• Codewars Kata

  • Monads: The Maybe Monad : Maybe = Just | Nothing

• Functors, Applicatives, And Monads In Pictures (번역)

• All Image Credit under CC BY 3.0 by ScottWlaschin

  • from Railway oriented programming

What is the Functional?

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

컴퓨터 프로그래밍에서, 특히 함수형 프로그래밍과 타입 이론에서 대수 자료형은 합성 타입의 한 종류이며 즉, 다른 타입들을 모아서 형성된 타입이다. 제일 보편적인 두 경우로는 프로덕트 타입(product type. 예를 들어 튜플과 레코드)과 섬 타입(sum type. 혹은 Tagged Union이라 불린다)이 있다. (중략) 대수 자료형의 값들을 패턴 매칭을 통해 분석해서 생성자나 필드 이름을 통해 값을 알아내거나 내부의 값을 추출해낸다. 대수 자료형은 70년대 에든버러 대학에서 개발한 작은 함수형 언어인 Hope에서 소개됐다.

Algebraic data type - Wikipedia

프로덕트 타입은 여러 타입을 한 번에 쓸 수 있는 구조(튜플의 경우 (A, B), 레코드의 경우 {A: B}같은 형식)이며 섬 타입은 열거형(Union) 비슷한 이름을 갖는 것에서도 추정할 수 있듯 여러 타입 중 하나를 쓸 수 있는 구조다. 여러 언어에서 예전부터 혹은 최근에 도입된 자료형 중에서 Maybe, Option, Optional 등의 이름으로 값을 갖거나(Just) 혹은 값이 없거나(Nothing, None, Null)로 구분되는 자료형이 가장 익숙하지 않을까 싶다. 설명을 하다 보니 OOP에서 추상 클래스와 상속받은 클래스들간 메소드 오버로딩을 통한 다형성과 비슷한 느낌이 든다.

위키피디아의 내용처럼 패턴 매칭에서 주로 사용되는데 패턴 매칭을 지원하지 않는 JavaScript에서는 적용할 수 없는 개념이고 제대로 사용할 수 없으므로 이해하기 어려운 개념이기도 하다. 그런데 굳이 처음부터 잘 이해하고 갈 필요가 있나? 그냥 어떤 것인지 알아보고 JavaScript로 한번 구현해보면 제대로는 아니어도 어떤 것인지 정도는 감을 잡을 수 있을 것이다.

대수적 자료형의 재미있는 점은 재귀적 구조와 지연 평가(Lazy Evaluation)을 통해 무한의 자료형이 가능하다는 점인데, Codewars에서 Nat(0 이상의 정수)과 Cons를 JavaScript로 구현하는 문제가 있다.

Nat

1

data Nat = Zero | Succ Nat

Haskell에서 대수 자료형 Nat을 정의해보았다. 코드를 정확히 이해할 필요는 없고, Zero라는 0에 해당하는 값과 Nat을 인자로 받아 그다음 값을 갖는 Succ의 두가지 경우가 될 수 있는 Nat이라는 섬 타입이다. 문제에서는 Zero와 Succ에 대해서 정확히 같지는 않지만, 다음과 비슷하게 주어진다.

1
2

const zero = () => {};
const succ = (nat) => ( ()=>nat );

zero는 일종의 상수고, succ는 nat을 리턴하는 함수를 리턴한다. 즉, 패턴 매칭을 통해 Succ에서 받은 이전 값을 다시 추출하는 과정을 함수 호출로 대신했다. 패턴 매칭을 통해 Nat을 정숫값으로 변환하는 과정도 JavaScript로 대신해보자.

1
2
3

toInt :: Nat -> Int
toInt Zero = 0
toInt (Succ nat) = 1 + toInt nat

인자로 Zero를 받을 경우에는 당연히 0이 되고, Succ를 받았을 경우에 Succ를 생성할 때 받았던 이전 값 nat을 패턴 매칭을 통해 추출해서 다시 toInt로 넘겨서 Nat은 하나씩 이전값을 보고 Zero가 나올 때까지 결괏값을 하나씩 증가시킨다.

1

toInt (Succ (Succ (Succ Zero)))

이렇게 0의 세 번째 다음 값을 정수로 변환한다면 그 과정을 간단히 표현해서 1 + (1 + (1 + 0)이 되고 3을 리턴하게 된다. 그렇다면 이걸 JavaScript로 구현하면

1
2
3
4
5
6

const toInt = (nat) =>
  nat === zero
    ? 0
    : 1 + toInt(nat())

console.log(toInt(succ(succ(succ(zero))))); // 3

이런 식으로 재귀를 통해 구현할 수 있다. 혹은 앞에서 언급했던 트램펄린과 비슷하게

1
2
3
4
5
6
7

const toInt = (nat) => {
  let count = 0;
  for(; nat !== zero ; nat = nat(), count++);
  return count;
}

console.log(toInt(succ(succ(succ(zero))))); // 3

구현할 수도 있다. succ와 zero의 의미, 그리고 어떻게 다루어야하는지 방법을 알았으니 나머지 인터페이스는 쉽게 구현할 수 있다.

Cons

Codewars에 대수 자료형을 다룬 문제가 하나 더 있다. Nat처럼 재귀적인 구조로 아주 비슷한 Cons라는 구조다. 많은 언어에서 List 혹은 Sequence라는 이름으로 구현체를 제공하는 유명한 자료형이다.

1
2

data List a = Cons { head :: a , tail :: List a}
            | Nil

List는 Cons 혹은 Nil이 될 수 있는 섬 타입이다. 그리고 Cons는 다시 a 타입의 head와 List a 타입의 tail로 이루어진다. 위에서 말했듯이 Nat와 유사한 모양의 재귀적인 구조다. 참고로 head와 tail은 Cons 구조에서 일반적으로 쓰이는 이름이지만 언어에 따라서 car과 cdr로 표현하기도 한다. 또한, List와 Array를 모두 제공하는 언어나 라이브러리에서는 보통 C언어에서처럼 고정된 길이의 index를 가지는 배열을 Array(혹은 Vector)라고 부르고 앞서 말했듯 이런 Cons 구조를 List(Sequence)라고 부르는 경우가 많다.

1
2
3
4
5
6
7

function Cons(head, tail) {
  this.head = head;
  this.tail = tail;
}
const Nil = new Cons(null, ()=> {
  throw new Error('Empty!');
});

문제를 다른 사람이 낸 것인지 앞에서는 함수 호출을 통해 지연 평가를 비슷하게 구현했는데 이번에는 간단하게 속성(property)으로만 구현해서 제공된다. 앞에서의 Nat과 비슷한 정수의 스트림을 구현해보면

1
2
3

int :: Int -> List Int
int n = Cons n tail
  where tail = int (n + 1)

이런 식이 된다. tail을 바로 평가하지 않기 때문에 int 0으로 List를 만들어도 바로 Cons 0 tail을 만들 뿐 무한루프를 돌지 않는다. JavaScript에서 비슷하게 만들어보자면

1
2
3
4

const int = (n) => new Cons(n, ()=>int(n+1))

int(0)        // { head: 0, tail: [Function] }
int(0).tail() // { head: 1, tail: [Function] }

이렇게 계속 tail을 실행할 때마다 다음 Cons를 생성해서 지연 평가를 구현했다. 사실 링크의 문제에서는 지연 평가에 대한 내용이 없어서 굳이 이렇게까지 할 필요는 없지만, 문제풀이가 목적이 아니니. 그럼 언어가 제공하는 List에서 앞서 정의한 List(Cons|Nil)로 변환을 통해 Cons를 생성할 수 있도록 해보자.

1
2
3

fromArray :: [a] -> List a
fromArray [] = Nil
fromArray (x:xs) = Cons x (fromArray xs)

x:xs는 Cons의 x가 head고 xs가 tail이며 두 개를 연결해서 하나의 Cons를 만든다는 연산자 :이다. 참고로 ++의 경우 두 개의 Cons를 연결(concat)한다. 이걸 또 JavaScript로 구현해보면 다음과 같다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

const fromArray = (arr = []) => {
  if(arr.length === 0) return Nil;
  else return new Cons(arr.shift(), ()=>fromArray(arr.slice()));
}

let cons = fromArray([1, 2]);
console.log(cons); // { head: 1, tail: [Function] }
cons = cons.tail();
console.log(cons); // { head: 2, tail: [Function] }
cons = cons.tail();
console.log(cons, cons === Nil); // { head: null, tail: [Function] } true
cons = cons.tail();
//   throw new Error('Empty!');
//         ^
// Error: Empty!

이제 Sequence 타입에 항상 적용해보는 filter와 map을 구현해보자

1
2
3
4
5
6
7
8
9
10

filter' :: (a -> Bool) -> List a -> List a
filter' f Nil = Nil
filter' f (Cons x xs)
  | f x       = Cons x (filter' f xs)
  | otherwise = (filter' f xs)


map' :: (a -> b) -> List a -> List b
map' f Nil = Nil
map' f (Cons x xs) = Cons (f x) (map' f xs)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

const filter = (f, cons) => {
  if(cons === Nil) return Nil;
  else if(!f(cons.head)) return filter(f, cons.tail());
  else return new Cons(cons.head, ()=>filter(f, cons.tail()));
}

const map = (f, cons) => {
  if(cons === Nil) return Nil;
  else return new Cons(f(cons.head), ()=>map(f, cons.tail()));
}

const prt = (cons) => {
  while(cons !== Nil) {
    console.log(cons.head);
    cons = cons.tail();
  }
}

출력이 귀찮아서 prt 함수를 따로 만들었다. 이제 확인을 해보면

1
2
3
4
5
6
7
8
9
10
11
12
13

const even = (d) => d % 2 === 0;
const doub = (d) => d * 2;
const toFive = fromArray([1,2,3,4,5]);

prt(filter(even, toFive));
// 2
// 4
prt(map(doub, toFive));
// 2
// 4
// 6
// 8
// 10

이제 재귀적인 구조를 다룰 때 어떻게 실행되는지에 대해 안에서 어떻게 돌아갈지를 간단하게 구현해봤는데 적당히 감이 왔을 것이다. 여기에서 약간의 스킬을 더해서 window.setImmediate나 process.nextTick으로 스레드 점유를 살짝 연기시키면 충분히 큰 자료도 시간만 있으면 다룰 수 있을 것이다. JavaScript에서 map과 filter를 어떻게 쓰는지 모르는 사람은 거의 없을 것이고 Cons에서 구현한 것들도 배열에서 쓰이는 것과 큰 차이가 없었다. 다음에는 이걸 대수적으로 해석할 때의 의미와 그걸 지원하는 구조에 대한 명칭을 이야기할 것이다.

Reference

• Codewars Kata
  • Algebraic Data Types : Nat = Zero | Succ Nat
  • Algebraic List : List a = Cons {a, List a} | Nil
• 함수프로그래밍 실천기술(가칭), 제이펍 2015

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