뭘 할까 하다가, 팀이 주 언어로 사용하고 있던 Go에 대해 함수형 프로그래밍 관점에서 아쉬운 점을 이야기해보기로 했다. 어느 언어나 마찬가지겠지만 Go 역시 장점이 많지만 아쉬운 점도 더러 있다.

컴파일이 필요한 정적 언어임에도 sum type을 지원하지 않는다는 점이 떠올라서 간단히 정리해 보았다. Sum type이 뭔지 언제 필요한지 등등..

여기서는 sum type이 있었으면 하는 순간에 사용할 수 있는 대안을 간단히 살펴본다. 구글 검색 “go sum type”으로 젤 앞에 나오는 다음 글에 몇가지 대안이 제시된다.

Alternatives to sum types in Go

짧게 정리해보면 다음과 같다.

• 대안0: interface{} — 젤 먼저 떠오르는 방법이고 실제로 가장 많이 사용되는 것 같다.
• 대안1: sum type interface — sum type으로 묶고 싶은 타입들을 태깅 인터페이스로 묶어주는 방법이다. 이 방법도 종종 사용되는 것 같다.
• 대안2: visitor — 태깅 인터페이스에 visit(visitor)메쏘드를 사용한 것이다. 이유는 대안0,1에 필요한 type-switch를 사용하지 않기 위한 것.
• 대안3: decoupled visitor — visitor도 인터페이스로 만들었다. 대안2와 별로 다르지 않다.

visitor라니, 참 아재스럽다.

암튼, 대안들에 소개되지 않은 방법 중에 많이 쓰이는 것이 또 있다. 굳이 이름을 붙이자면 tagged superset 타입을 만드는 것이다. 이 방법도 은근히 많이 사용되는 것 같다. 왜? 편하니까?

type PublishEvent   struct { ... }
type SubscribeEvent struct { ... }

type Event struct {
  Type      EventType      
  Publish   PublishEvent
  Subscribe SubscribeEvent 
}

내가 세미나에서 소개한 방법은 Mogensen–Scott encoding이다. 실용적이라기 보다는 함수형 프로그래밍 관점에서 봤을때 이렇게도 가능하다는 정도로.

다음 글을 통해 알게 된 방법이다.

Kwang's Haskell Blog - Scott encoding of Algebraic Data Types

람다만 있으면 뭐든 할 수 있어! 라는 접근이다. sum type은 지원하지 않지만 람다를 지원하는 Go에서도 사용할 수 있는 방법이다.

type Event func(func (PublishEvent), func (SubscribeEvent))

Go Playground: https://play.golang.org/p/zjPhGFhMnFx (첫번째 블로그 글의 예제 코드를 조금 수정한 것이다.)

Go라고 하기엔 참 기괴한 모양이 되어 버렸다.

그런데 함정이 있다.

이 방법이나 visitor 방법이나 사실은 같은 방법이라는 거. 내가 소개한 방법도 아재 방법과 별로 다를게 없다.

visitor가 소개되는 맥락은 언제나 객체지향이다. OO에서 어떻게 타입 안전하게 여러 서브타입을 접근할 것인가? 여기서 서브타입을 sum type으로 두고 보면 visitor의 visit 함수들은 위의 scott encoding에서 함수 타입과 같다.

언제나 그렇지만 사실 다 그게 그거인 경우가 많다. 겉치장만 조금씩 다를뿐.

function map(f, xs) {
  return xs.reduce((a,b) => a.concat(f(b)), []);
}
function filter(p, xs) {
  return xs.reduce((a,b) => a.concat(p(b)?b:[]), []);
}

하지만 reduce는 좀 복잡하다. 대개의 경우는 reduce를 직접 사용하기 보다는 위의 map/filter처럼 한번더 래핑하는 것이 가독성에 유리하다. reduce는 반복/재귀 구조의 추상화이기 때문에 추상 수준이 매우 낮아서 어떤 의도를 드러내기 어렵다.

reduce는 fold 함수다. reduce 보다는 foldr/foldl 혹은 foldRight/foldRight 같은 이름이 더 많이 쓰인다. reduce는 fold 중에서도 fold from the left 함수다. 배열 구조를 결합 함수로 접어가는 방향이 왼쪽부터 오른쪽으로 진행되기 때문이다. Haskell 같은 지연 평가 언어는 fold from the right(foldr) 함수가 기본이지만 JavaScript 같은 대부분의 언어는 foldl이 기본이다.

Haskell에서는 fold 가능한 자료 구조를 “Foldable”이라고 추상화했다. JavaScript의 reduce 덕분에 배열은 Foldable 자료라고 할 수 있다. 그런데 Haskell에서는 어떤 자료 구조를 Foldable로 만들기 위해서는 foldr을 구현해도 되지만 foldMap을 구현해도 된다.

foldMap이란 함수를 이해하려면 Monoid를 알아야 한다. Monoid는 더할 수 있는 값이다. 어떤 자료형이 zero 값과 plus 연산을 정의할 수 있으면 Monoid라고 볼 수 있다. JavaScript에서도 Monoid를 많이 찾을 수 있다. (0, (a,b) => a+b), (1, (a,b) => a*b), (“”, (a,b) => a+b), ([], (a,b) => a.concat(b)), …

직관적으로 배열의 모든 요소들에 대해 더하기 연산을 적용할 수 있으면 그것을 모두 더해 하나의 값으로 reduce하는 것이 가능하다. JavaScript의 배열도 Foldable이기 때문에 당연히 foldMap을 정의할 수 있다.

function foldMap(f, xs, monoid) {
  let m = monoid.zero;
  for (const x of xs) {
    m = monoid.plus(m, f(x));
  }
  return m;
}

이미 reduce가 있으니 굳이 이렇게 정의할 필요는 없다. 둘 중 하나만 정의되면 다른 하나는 쉽게 구현된다.

function foldMap(f, xs, monoid) {
  return xs.reduce((a,b) => monoid.plus(a, f(b)), monoid.zero);
}

그렇다면 foldMap으로 reduce를 구현할 수도 있을까?

function reduce(f, init, xs) {
   // use foldMap
}

foldMap은 Monoid를 필요로 한다. 여기에 필요한 Monoid는 조금 특이한 Endo라는 Monoid다. Endo라는 Monoid는 입/출력 타입이 같은 함수를 말한다. 예를 들면 (a) => a + 1 같은 함수는 number를 입력으로 받아서 number 를 반환한다. Endo의 plus연산은 함수 합성이다. plus(f,g) = (x) => g(f(x)) 함수 합성에 있어서 zero값은 (즉 더하나 마나 한 값) identity 함수다.

const endo = {
  zero: x => x,
  plus: (f,g) => x => g(f(x))
};
function reduce(f, init, xs) {
  return foldMap(x => a => f(a, x), xs, endo)(init);
}

reduce에

** 여기까지 쓰다만 드래프트 발견하여 .. 일단 공개합니다. 다음에 무슨 이야기를 쓰려고 했을까요? 저도 잘 모르겠네요 ㅋ

그래서 간단한 프로그램이라도 돌아가는 프로그램을 살펴보는게 좋겠다 싶어서 http://www.haskellforall.com/2015/10/basic-haskell-examples.html 페이지에 소개된 Todo 프로그램 같이 살펴봤다.

마침 이날 모여서 다룬 내용이 타입클래스였고, Todo 예제에 나오는 show/read 함수는 각각 Show/Read 타입클래스를 사용하는 것이라서 아주 생뚱맞은 예제는 아니었다.

짧은 프로그램이지만 초급 학습자에겐 약간의 설명이 필요할 것 같아서 여기다 정리해본다.

이 프로그램은 todo.hs 파일 하나로 만든 다음 runghc todo.hs 명령으로 실행할 수 있다.

$ runghc todo.hs
Commands:
+ <String> - Add a TODO entry
- <Int>    - Delete the numbered entry
q          - Quit

Current TODO list:
_

도움말을 보여주고, 이어서 현재 할일목록을 보여준다. 마지막으로 명령 입력을 기다리는 프롬프트를 보여준다.

도움말을 보여주는 건 putStrLn “Hello, World” 명령만 이해하면 어려울 게 없다. 다만 하스켈에서 이런 출력은 IO 액션이라고 부르고 IO () 타입이라는 점, 그리고 여러 명령을 순차적으로 실행할 때 do 블록을 사용한다는 점만 알면 된다.

main :: IO ()
main = do
    putStrLn "Commands:"
    putStrLn "+ <String> - Add a TODO entry"
    putStrLn "- <Int>    - Delete the numbered entry"
    putStrLn "q          - Quit"
    prompt []

이렇게 처음 도움말을 출력한 다음에 prompt [] 를 호출하였다. prompt 함수는 현재 할일 목록을 인자로 받아서, 그것을 출력한 다음 사용자 입력을 처리하는 함수다. 할일목록은 단순하게 문자열 리스트 [String] 타입이다.

prompt :: [String] -> IO ()
prompt todos = do
    putStrLn ""
    putStrLn "Current TODO list:"
    mapM_ putTodo (zip [0..] todos)
    command <- getLine
    interpret command todos

여기서 조금 어려운 문장이 나오는데, mapM_ putTodo (zip [0..] todos) 부분이다. 먼저 zip [0..]todos 를 알아야 한다. zip 함수는 리스트 두 개를 인자로 받아서 순서대로 짝지어주는 함수다.

zip [0,1,2] “abc” == [(0,’a’), (1,’b’), (2,’c’)]

할일목록에 넘버링 하는 것이 zip [0..] todos 가 하는 일이다.

그 다음 mapM_ action list는 list의 항목들에 대해 action을 순차적으로 적용하는 함수다. 여기서는 todos를 넘버링(zip [0..])한 다음 그것들을 putTodo 액션 함수를 이용하여 출력한다.

putTodo :: (Int, String) -> IO ()
putTodo (n, todo) = putStrLn (show n ++ ": " ++ todo)

putTodo 함수는 넘버링된 할일 하나를 화면에 출력한다. 이때 사용된 show 함수는 Show a => a -> String 타입의 함수로, 무엇이든 문자열로 바꿔준다고 보면 된다.

다시 prompt 함수로 돌아가서 command <- getLine 명령을 보자. getLine은 콘솔에서 한 줄 읽어들이는 액션이고, 그 결과를 command에 저장한다. putStrLn 의 반대라고 할수 있다.

putStrLn :: String -> IO ()
getLine :: IO String

putStrLn 은 입력 문자열을 출력하는 액션이고, getLine은 그 자체로 사용자 입력을 읽어들이는 액션이다.

사용자 입력을 읽어들인 다음 command 를 해석하는 interpret 액션 함수를 호출했다. interpret 함수가 이 작은 프로그램에서 가장 복잡한 함수다.

interpret :: String -> [String] -> IO ()
interpret ('+':' ':todo) todos = prompt (todo:todos)
interpret ('-':' ':num ) todos =
    case delete (read num) todos of
        Nothing -> do
            putStrLn "No TODO entry matches the given number"
            prompt todos
        Just todos' -> prompt todos'
interpret  "q"           todos = return ()
interpret  command       todos = do
    putStrLn ("Invalid command: `" ++ command ++ "`")
    prompt todos

아직 하스켈을 보기 시작한지 얼마되지 않았다면 이렇게 함수 인자 위치에 다양하게 사용된 패턴이 눈에 잘 들어오지 않을 것 같다. 정의 몸체 부분을 빼고 보면 조금 이해하기 쉽다.

interpret :: String -> [String] -> IO ()
interpret ('+':' ':todo) todos = ...
interpret ('-':' ':num ) todos = ...
interpret  "q"           todos = ...
interpret  command       todos = ...

사용자 입력 문자열(명령)을 case 별로 나눠놓았다. 도움말과 거의 똑같이. 첫번째는 문자열이 “+(공백)”으로 시작하는 경우, 두번째는 “-(공백)”으로 시작하는 경우, 그리고 세번째는 입력 문자열이 “q”인 경우, 네번째는 나머지 모든 경우다.

첫번재 경우는 “+(공백)” 뒷부분을 todo란 이름으로 바인딩해주니까, 이를 이용해서 현재 할일목록(todos)에 붙여주면 된다. 맨 앞에 붙이고 싶다면 todo:todos 로 하면 될 것이고, 맨 뒤에 붙이고 싶다면 todos ++ [todo] 라고 할수 있을 것이다. 그런 다음, 다시 prompt 를 호출하여 프로그램이 반복 실행되게 만든다.

interpret ('+':' ':todo) todos = prompt (todo:todos)

호출을 보면, main -> prompt -> interpret -> prompt -> interpret -> … 처럼 재귀 호출인데, 하스켈은 이렇게 함수 끝에서 재귀호출을 사용해도 스택오버플로가 발생하지 않으니 걱정할 필요는 없다.

두번째 경우는 “-(공백)” 뒷부분을 num이란 이름으로 사용할 수 있는데, 여기서 num은 삭제할 할일의 번호를 나타낸다. 그런데 아직 num은 String 타입이므로 인덱스로 사용하려면 Int로 바꿔줘야 한다. putTodo 함수에서 사용한 show 와는 반대의 일을 하는 함수가 필요한데, 그것이 바로 read 함수다.

show :: Show a => a -> String
read :: Read a => String -> a

read 함수를 사용하면 해당 문맥에 필요한 타입으로 바꿔준다. 물론 그러기 위해서는 문자열이 올바른 형식을 한다. 여기서는 read num 이라고 하여 사용하면 하스켈 컴파일러는 올바르게 Int 타입으로 변환해준다.(혹은 파싱)

여기서는 지정된 위치의 할일 하나를 지워야 하는데, 우선 간단한 도움 함수로 delete라는 것을 가정해보자. delete 함수는 Int -> [String] -> [String] 의 타입으로 리스트에서 특정 위치의 항목을 삭제하여 반환하게 만들수도 있지만, Int가 올바른 인덱스가 아닌 경우도 고려해야 하므로 Int -> [String] -> Maybe [String] 타입으로 만드는 것이 낫다.

interpret ('-':' ':num ) todos =
    case delete (read num) todos of
        Nothing -> do
            putStrLn "No TODO entry matches the given number"
            prompt todos
        Just todos' -> prompt todos'

Maybe a 타입은 Just a 나 Nothing 두 가지 값 중 하나가 되므로 case ~~~ of를 이용하여 결과를 검사하였다. 지우기를 실패한 경우에는 delete가 Nothing을 반환하므로 실제로 지워지는 것 없이 그대로 적당한 메시지를 출력한 다음 prompt 루프로 진행한다. 제대로 지워졌다면 Just todos’ 패턴으로 매치하여 새로운 할일목록 todos’ 를 다음 prompt 루프에 전달한다.

세번째 경우는 prompt를 호출하지 않는 것 만으로 쉽게 프로그램을 종료시킬 수 있다.

interpret  "q"           todos = return ()

여기서 return () 부분은 아무것도 하지 않는 IO 액션을 만들어준다.

마지막 경우는 이해할 수 없는 명령이 입력된 것이므로, 적절한 메시지를 출력한 다음 prompt 루프를 반복한다.

이제 마지막으로 도움 함수 delete 를 구현하기만 하면 되는데, 이건 연습문제로 좋아보여서 설명없이 끝내기로 한다.

delete :: Int -> [a] -> Maybe [a]

enum 타입의 상수가 너무 많아서 컴파일이 안되는 문제를 해결해야 했다. 몇개인지 세어보진 않았는데 누군가 이슈를 올려서 들여다 보게 됐다.

2700개 정도 수준에서 문제를 일으킨 모양이었다. 좀 어정쩡한 숫자라 궁금하기도 했다. 스택오버플로에도 당연히 문제가 제기된 적이 있다.

Maximum number of enum elements in Java

처음엔 클래스파일의 상수 영역(constant pool) 크기 때문인줄 알았지만 enum 상수를 초기화하는 코드가 길어져서 단일 메쏘드 크기 제한에 걸린 것이었다.

enum의 기본 용도는 상수 집합이다(values()). 더러 상수 이름의 문자열을 이용하기도 한다(toString(), valueOf()). 이렇게 세 개의 메쏘드가 자동으로 생성된다. switch/case에 사용할 수도 있고, == 비교를 사용할 수도 있다.

첫번째로 시도해본 것은 위 세가지 자동생성 메쏘드를 가진, enum 처럼 동작하는 클래스 파일을 직접 만드는 것이었다. asm 라이브러리를 이용하여 클래스 파일을 직접 만들 수 있었다. 아이디어는 별다를게 없다. 크기 문제를 일으킨 정적 초기화 메쏘드를 여러개로 분리하는 것. 이렇게하니 10,000개 정도의 상수를 가지는 enum 타입의 클래스 파일을 만들 수 있었다.

이 방법의 문제점이라면 빌드 스크립트를 수정하여 커스텀 컴파일을 해야 한다는 점이었다. 이쯤에서 개인적인 호기심은 어느정도 해소되어 좀더 일반적인 대안을 찾아봤다.

enum 상수 대신 일반적인 static final 상수를 이용하는 방법을 취하기로 했다. Java에 enum이 등장하기 전에 사용하던 type-safe enum 방식은 새로운 상수를 하나 추가하기도 귀찮고 무엇보다 switch/case에 사용할 수 없다는 점이 아쉬웠다.

문자열 상수를 가지는 클래스로 바꾸기로 하고 보니 어떻게 안전하게 바꿀까 하는 문제가 되었다.

enum MyEnum { 
  A, B, C
}

class UseEnum {
  MyEnum e;

void method(MyEnum e) {
  Set<MyEnum> set = ...;
  switch(e) {
    case A: ...
    case B: ...
    default: 
  }

  if (e == C) {
  }
}

void foo(String s) {
  MyEnum e = MyEnum.valueOf(s);
  print(e.toString());
}

..
}

• 타입 참조는 MyEnum 타입을 String으로 바꾸어야 한다.
• switch/case에서 enum 상수처럼 바로 참조할 수 없으니 MyEnum.A 처럼 스코프를 지정해주거나 import static 을 추가해야 한다.
• == 비교는 예외적인 케이스이긴 하지만 null이 있는 경우에도 안전하게 동작하므로 단순히 String.equals()로 바꾸기 보다는 따로 비교함수를 호출하도록, 예를 들어 MyEnum.eq(a,b) 처럼 호출하게 바꿔줘야 한다.
• valueOf()는 String -> MyEnum 변환이 기본 역할이다. 그런데 MyEnum을 String으로 바꾸기로 했으니 필요없다 할 수 있다. 하지만 타입 변환 역할 외에 입력 문자열이 상수 집합에 포함되는지 검사하는 역할도 있으므로 살려줄 필요가 있다.
• toString()은 필요없어졌다.

이 정도의 코드 변환을 하자고 보니 단순히 정규 표현식 몇 개로 안전하게 바꾸기는 어려운 것 같아서 우선 타입 정보를 확인할 수 있는 JavaParser 라이브러리를 이용하여 AST 수준에서 코드 변환을 해보기로 했다.

이런 일로 파서 라이브러리를 사용해보면 늘 비슷한 상황을 겪는 것 같다.

1. 파서가 필요하다.
2. 파서를 찾아서 적용한다.
3. 몇가지 테스트에서 잘 되는 것 같다.
4. 실제로 돌려보면 파서의 오류가 드러난다.
5. 파서 오류 중 단순한 것 몇 개를 고치기 시작한다. GitHub 풀리퀘스 보낼 기회니까.
6. 그러다 파서의 결정적 한계에 다다른다.
7. 결국 간단하지만 당장의 필요에 맞는 약식 파서를 직접 만든다.

7번으로 바로 점프하면 사실 시간이 많이 단축되는데, 늘 완전한 파서부터 시작하다가 우회하게 된다.

JavaParser는 AST를 순회하며 타입 확인을 해 볼 수 있어서 정확하게 MyEnum 타입 참조만 String으로 바꾸거나 MyEnum 을 포함하는 ==, != 비교를 원하는 형태로 바꾸는 등의 작업이 수월했다.

JavaParser의 결정적 한계는 변형된 AST를 다시 저장할 때 기존 포맷을 유지하지 못한다는 점이었다. 커밋 diff가 너무 커지는 것은 피하고 싶었다.

마지막 단계로 직접 코드 변환기를 만들었다. JavaParser로 변환 지점을 모두 확인했으니 해당 지점들만 변환할 수 있도록 패턴을 다듬고 이로도 처리 안되는 몇 부분은 간단한 토크나이저(identifier, string literal, comment 등을 구분)를 만들어서 처리했다.

좀더 범용적인 enum 변환기를 만들어보려고 했지만 이 정도 수준에서 당장의 문제만 해결하고 접는걸로…

Promise.all([p1,p2,p3]).then(([v1,v2,v3]) => ...)

배열(혹은 Iterable)에 담긴 Promise들이 모두 resolve되면 resolve되는 Promise를 만들어준다. 여러 Promise들의 결과를 join처럼 모아주기 때문에 편리하게 사용할 수 있다.

그런데 Haskell을 공부하다 보면 Promise.all() 에 해당하는 좀더 일반화된 함수를 만날 수 있다. 바로 sequence 함수다.

sequence :: (Traversable t, Applicative f) => t (f a) -> f (t a)

Haskell 타입을 읽기 어렵다면 우선 Traversable을 JavaScript Array로 보고, Applicative를 JavaScript Promise로 바꿔서 위 함수의 타입을 다시 옮겨보자.

function sequence<A>(tfa: Array<Promise<A>>): Promise<Array<A>>

즉, 배열에 담긴 Promise들을 입력으로 받아서 배열 값에 대한 Promise로 변환한다. Promise.all()과 같다.

Promise.all()에서 발견되는 Applicative/Traversable과의 연결고리를 확장하면 새로운 도움 함수들을 발견할 수 있다.

먼저, Traversable에는 대표 함수가 두 개 정의되는데, 그 중 하나는 이미 살펴본 sequence다. 또 다른 하나는 traverse다.

traverse:: (Traversable t, Applicative f) => (a -> f b) -> t a -> f (t b) 

이번에도 Promise, Array를 대입해보자.

function traverse<A,B>(f: (a: A) => Promise<B>, ta: Array<A>): Promise<Array<B>>

배열에 담긴 요소들에 Promise 생성 함수를 적용하는 함수다. 이는 이미 Promise.all()의 일반적인 사용패턴에도 자주 등장한다.

const ids = [...]
Promise.all(ids.map(getName)).then(...)

실제로도 Haskell에서 traverse 구현은 이와 마찬가지다.

traverse f as = sequence (fmap f as)

자주 나오는 sequence/map 조합을 traverse로 만든 것이다. mapping 함수가 Promise를 반환하는 경우에 사용하면 편리하다.

function sequence(ps) {
  return Promise.all(ps);
}
function traverse(as, f) {
  return sequence(as.map(f));
}

그런데 사실 여기까지는 Promise.all도 있고 Array.prototype.map도 이미 있기 때문에 그다지 이득이 없어보인다.

그런데 Traversable을 그냥 Array가 아니라 JavaScript 객체로 확장하면 어떨까? 아래처럼 생긴 일반적인 JavaScript 객체를 Traversable 로 볼 수 있으려면 앞서 얘기한 것처럼 sequence() 함수와 map() 함수가 정의되어야 한다.

{
  todos: [ { ... }, { ... } ],
  visibilityFilter: { ... }
}

Promise는 고정하고 JavaScript 객체에 대해 sequence()와 map() 함수를 정의해보자.

function map(obj, f) {
  if (isArray(obj)) {
    return obj.map(a => map(a, f));
  } else if (isObject(obj)) {
    return Object.keys(obj).reduce(
      (a, b) => Object.assign(a, { [b]: map(obj[b], f) }),
      {}
    );
  } else {
    return f(obj);
  }
}

map() 함수는 배열과 객체에 대해 재귀적으로 map(f)를 적용하고, 다른 값들은 f()를 적용하여, 본래의 구조를 유지하면서 트리 구조의 리프 노드들에만 함수를 적용하여 값을 변환할 수 있다. (deep-map이란 라이브러리도 비슷한 일을 한다.)

다음은 JavaScript 객체로 확장된 sequence() 함수다.

function sequence(obj) {
  if (isArray(obj)) {
    return Promise.all(obj.map(sequence));
  } else if (isObject(obj)) {
    const keys = Object.keys(obj);
    return Promise.all(keys.map(k => sequence(obj[k])))
       .then(values => zipObject(keys, values));
  } else {
    return Promise.resolve(obj);
  }
}

이렇게 하여 JavaScript 객체를 Traversable로 만들었다. traverse 구현은 Array.prototype.map 대신 새로 정의한 map을 사용하면 된다.

function traverse(obj, f) {
  return sequence(map(obj, f));
}

이렇게 traverse와 sequence를 일반 JavaScript 객체로 확장하여 정의하면 Promise.all만 사용할 때보다 훨씬 다양한 경우에 사용할 수 있다.

function case1() {
   return Promise.all([getTodos(), getVisibility()])
     .then(([todos, visibility]) => ({ todos, visibility });
}

function case2() {
   return sequence({
     todos: getTodos(),
     visibility: getVisibility()
   });
}

case1()은 데이터를 가져와서 모양을 만드는 방식이고, case2()는 먼저 모양을 만들어서 요청하는 방식이다. 경우에 따라서는 case1의 방식이 또 어떤 경우는 case2의 방식이 더 맞을 것이다.

Promise.all()이 Applicative/Traversable의 sequence와 유사하다는 점으로부터 JavaScript 객체를 대상으로 all() 처럼 동작하는 sequence()와 traverse()를 구현해볼 수 있었다.

interpret(function *generator() { ... })

JavaScript에서 동시성 처리에 이 패턴을 적용해볼 수 있다. 이미 이런 스타일의 라이브러리들이 있고, async/await 가 나온 마당에 필요할까 싶기도 하지만 여기서는 한발짝 더 나아가보려고 한다. (이 글의 내용은 There is no Fork라는 페이퍼를 기본 뼈대로 한다.)

이런 API가 이미 있다고 보자.

function friendsOf(id): Promise<string[]>;
function memberOfGroup(gId, uId): Promise<bool>;
function getName(id): Promise<string>

이제 “FP” 그룹에 참여하는 친구들의 이름을 얻어오려고 한다. async 코루틴으로 작성하면 다음과 같다.

async function fpFriends(id) {
  const friends = await friendsOf(id);
  const names = [];
  for (const f of friends) {
    if (await memberOfGroup("FP", f)) {
      names.push(await getName(f));
    }
  }
  return names;
}       

memberOfGroup 을 여러번 순차적으로 호출하는 문제가 바로 보이긴 하지만 이 문제는 뒤에서 다시 언급하기로 하고 우선은 이 코드를 generator/interpreter 패턴으로 바꿔보자.

function fpFriends(id) {
  return co(function *() {
    const friends = yield friendsOf(id);
    const names = [];
    for (const f of friends) {
      if (yield memberOfGroup("FP", f)) {
        names.push(yield getName(f));
      }
    }
    return names;
  });
}

여기서 interpreter에 해당하는 co() 함수는 generator가 yield하는 Promise를 처리한다. Promise가 resolve되면 generator를 resume한다.

function co(g) {
  const i = g();
  function next(value) {
    const r = i.next(value);
    if (r.done) return Promise.resolve(r.value);
    return r.value.then(next);
  }
  return next();
}

혹은 co()를 async 함수로 만들 수도 있다.

async function co(g) {
  const i = g();
  let value;
  while (true) {
    const r = i.next(value);
    if (r.done) return r.value;
    value = await r.value;
  }
}

그런데 co()를 async로 구현할 수 있다면 처음부터 fpFriends를 async로 만들면 되는데 굳이 generator/interpreter로 나누는 것이 무슨 의미가 있을까?

여기서 중요한 것은 co()를 async로 구현했냐 .then()으로 구현했냐 보다, fpFriends()로부터 동시성 처리 부분이 분리되었다는 점이다.

그럼 처음 API부터 다시 살펴보자. friendsOf()의 반환값이 Promise였다. 바로 이 지점부터 동시성을 배제시킬 수도 있다. 그럼 API를 다음처럼 바꿀 수 있다.

function friendsOf(id) {
  return {type: "friendsOf", id};
}
function memberOfGroup(gId, uId) {
  return {type: "memberOfGroup", gId, uId};
}
function getName(id) {
  return {type: "getName", id};
}

동시성 요소(Promise)를 배제한 새로운 API로도 generator를 만들 수 있다.

function * fpFriends(id) {
  const friends = yield friendsOf(id);
  const names = [];
  for (const f of friends) {
    if (yield memberOfGroup("FP", f)) {
      names.push(yield getName(f));
    }
  }
  return names;
}

실제로 친구 목록을 얻어오는 대신 친구 목록을 필요로 한다는 요청만 yield하고, 실제로 이 요청을 처리하는 것은 interpreter에게 맡겼다.

async function run(g, process) {
  const i = g();
  let value;
  while (true) {
    const r = i.next(value);
    if (r.done) return r.value;
    value = await process(r.value);
  }
}

async function process(request) {
  if (request.type === "friendsOf") ...
  if (request.type === "memberOfGroup") ...
  if (request.type === "getName") ...
}

interpreter에서 실제 요청을 비동기로 처리하든지 동기로 처리하든지 하는 것과 (FP 그룹에 참여하는 친구 목록을 얻어오는) 비즈니스 로직이 분리된 셈이다. 덤으로 testRun() 같은 함수를 만든다면 너무나 쉽게 로직을 테스트할 수 있게 되었다. 테스트용 run()은 Promise를 사용하지 않아도 된다.

다시 처음 async 코루틴으로 구현된 fpFriends() 함수를 보자.

async function fpFriends(id) {
  const friends = await friendsOf(id);
  const names = [];
  for (const f of friends) {
    if (await memberOfGroup("FP", f)) {
      names.push(await getName(f));
    }
  }
  return names;
}

이 코드는 동시성 처리 관점에서 개선할 포인트가 보인다. memberOfGroup()이나 getName() 이 반복문에서 순차적으로 실행되지만 병렬 실행 가능하다는 점이다. Promise.all() 을 이용하도록 수정하여 이를 개선할 수 있다.

async function fpFriends(id) {
  const friends = await friendsOf(id);
  const fp = await Promise.all(friends.map(f => memberOfGroup("FP", f)));
  return Promise.all(friends.filter((f, i) => fp[i]).map(getName));
}

동시성 관점에서 개선되긴 했지만 코드가 갑자기 난해해졌다.

generator 버전에서 이 같은 동시성 효과를 적용하려면 어떻게 해야 할까? 기본적으로 generator에서 request 객체를 던지고 이를 interpreter가 해석하므로 무엇을 yield할 지 우리가 정하면 될 일이다. all()효과에 대응하는 새로운 요청 객체를 정의할 수도 있겠지만, 여기서는 좀더 단순하게, 요청들을 배열에 담아서 yield하면 이들을 동시에 처리하도록 구현해 볼 수 있다.

function* fpFriends(id) {
  const friends = yield friendsOf(id);
  const fp = yield friends.map(f => memberOfGroup("FP", f));
  return yield friends.filter((f, i) => fp[i]).map(getName);
}

이에 맞춰 interpreter에서 요청 대신 배열이 들어오는 경우에 대해 병렬 처리를 신경써줘야 한다.

async function run(g, process) {
  const i = g();
  let value;
  while (true) {
    const r = i.next(value);
    if (r.done) return r.value;
    if (Array.isArray(r.value)) {
      value = await Promise.all(r.value.map(process));
    } else {
      value = await process(r.value);
    }
  }
}

동시성 측면에서 여전히 개선할 여지가 있다. 여러 개의 요청을 병렬로 진행하는 것은 분명히 개선된 것이지만 memberOfGroup이나 getName 같은 요청을 여러 개 던질 필요 없이 배치로 처리할 수 있다면 어떨까? redis의 mget요청처럼 말이다. 그러면 N개의 요청을 던질 필요없이 하나의 요청으로 처리할 수 있다. 물론 이를 위해서는 요청에 대응할 서비스가 배치 처리를 지원해주어야 한다.

일단 getName 하나에 대해서만 배치를 지원하는 새로운 API를 추가한 다음 Promise 버전에 이를 적용해보자.

function getNameN(idList): Promise<NameList>

async function fpFriends(id) {
  const friends = await friendsOf(id);
  const fp = await Promise.all(friends.map(f => memberOfGroup("FP", f)));
  return getNameN(friends.filter((_, i) => fp[i]));
}

다시 generator/interpreter 버전으로 돌아와서 getNameN을 적용한다면 어떻게 될까? 어떤 요청이 배치를 처리하는지 여부에 따라 Promise.all로 병렬 실행할지 배치 API로 처리할지 알 수 있는 위치는 process가 적당해 보이므로 애초에 process가 요청리스트를 처리하도록 수정해보자.

async function run(g, process) {
  const i = g();
  let value;
  while (true) {
    const r = i.next(value);
    if (r.done) return r.value;
    if (Array.isArray(r.value)) value = await process(r.value);
    else [value] = await process([r.value]);
  }
}

async function process(requests) {
  const results = Array(requests.length);
  // 여기서 getName은 배치 요청
  // 나머진 단순 요청 + Promise.all
  return results;
}

process가 조금 복잡해지긴 했지만, fpFriends로직을 작성하는 입장에서 각 API가 배치로 처리 가능한지 여부를 신경쓰지 않아도 된다. 그러나 배치 처리 여부나 병렬 실행을 직접 신경 써야 한다는 점만 빼면 여전히 async 코루틴 방법이 더 간결(?)해 보인다. 그럼 다음 단계로 나아가 보자.

여기선 모듈화를 따져보려고 한다. fpFriends 함수를 만들었으니 이젠 두 사람의 친구들 중에서 공통적으로 FP 그룹에 참여하는 이들이 누구인지 알고 싶어서 commonFpFriends 함수를 만들고자 한다.

async function commonFpFriends(id1, id2) {
  const [names1, names2] = await Promise.all([fpFriends(id1), fpFriends(id2)]);
  return intersect(names1, names2);
}

Promise.all을 이용하여 병렬로 실행했지만 fpFriends라는 함수 호출 바운더리로 가로 막혀서 더이상의 병렬/배치 처리를 기대하기 어려워졌다. 예를 들어, friendsOf() API 역시 N개의 배치 처리를 지원하게 되었다고 했을 때(예, friendsOfN(idList)) 위 코드에서는 friendsOf(id1)과 friendsOf(id2) 를 병렬 실행만 할 수 있을 뿐 friendsOfN([id1, id2]) 와 같이 배치로 처리할 수 없다.

배치 처리를 굳이 하려면 fpFriends() 라고 만들어둔 함수를 사용하는 대신 한 덩어리 커다란 commonFpFriends를 만들면 가능하다.

async function commonFpFriends(id1, id2) {
  const [friends1, friends2] = await friendsOfN([id1, id2]);
  ...
}

동시성 이슈가 로직을 구현하는데 효율성 뿐 아니라 모듈화에도 영향을 미친 것을 알 수 있다.

generator/interpreter 패턴에서는 이 문제를 어떻게 해결할 수 있을까?

일단 JavaScript의 generator는 yield* 를 이용하여 다른 generator를 호출할 수 있다. (Stackless 코루틴 참고) 예를 들면..

function* commonFpFriends(id1, id2) {
  const friends1 = yield* fpFriends(id1);
  const friends2 = yield* fpFriends(id2);
  return intersect(friends1, friends2);
}

하지만 이 경우는 fpFriends() generator를 잠깐동안 yield* 에게 맡기는 셈이 되어 우리가 기대하는 동시성 처리를 interpreter가 직접 할 수 없게 된다.

yield* 대신 yield 로 다른 generator 를 전달하는 방법을 사용하면 가능하다. (JS 제너레이터로 스택오버플로 피하기 참고) 대신 이제는 yield* 가 해줬던 작업까지 interpreter가 떠 맡아야 한다.

아래 예는 foo()에서 bar()를 호출하여 그 결과를 받아오는 과정을 interpreter가 어떻게 처리하는지 보여준다.

function* foo() {
  const b = yield bar();
  return b + 1;
}

function* bar() {
  return 41;
}

run(foo);  // 42

function run(g) {
  const stack = [g()];
  let value;
  while(stack.length > 0) {
    const top = stack.pop();
    const r = top.next(value);
    if (r.done) value = r.value;
    else if (typeof r.value.next === 'function') {
      stack.push(top);
      stack.push(r.value);
    }
  }
  return value;
}

yield 한 값이 다른 generator라면 stack에 push하여 실행을 이어가고, 그 generator가 실행을 마치면 그 때 반환값을 push되었던 caller generator에 전달하며 resume하면 된다.

이 방법을 이용한다면 generator/interpreter 패턴으로 동시성을 처리할 때 함수 바운더리를 넘어서까지 병렬/배치 처리를 할 수 있다.

function* commonFpFriends(id1, id2) {
  const [fs1, fs2] = yield [fpFriends(id1), fpFriends(id2)];
  return intersect(fs1, fs2);
}

이미 배열을 yield하는 방법으로 병렬 처리를 가능하게 했었다. 여기에 요청 객체 뿐만 아니라 다른 generator를 yield할 수 있게하였다. 즉, 배열에 fpFriends(id1)과 fpFriends(id2)를 담아서 yield함으로써 이 두 함수들이 발생시키는 요청들을 병렬로 처리할 것을 알렸다. 이제 interpreter는 더 복잡해지겠지만 덕분에 generator 부분이 훨씬 간결해졌다.

run() interpreter를 구현해보자.

interpreter는 root에 해당하는 generator를 입력으로 받아 yield되는 값들을 처리한다. generator가 yield하는 값은 다음과 같다.

• 요청: 외부 데이터를 읽어와서 다음 단계를 시작한다.
• 배열: 배열의 각 요소들을 병렬 실행하여 그 결과를 모아 다음 단계를 시작한다.
• generator: 스택에 추가하고 계속 진행한다. generator가 끝나면 스택은 줄어든다.

배열 요소들을 병렬 실행하여 그 결과를 모으는 부분을 주목하자. 각 generator를 병렬 실행한다는 것은 무엇을 의미할까?

[g1, g2, g3]처럼 generator를 포함한 배열을 처리하는 경우를 따져보자. 우선 g1을 실행하다가 g1이 어떤 요청을 처리해야 할 상태가 되면 우선 멈춘다. 그리고 g2를 실행하다가 또 다른 요청을 처리해야 하는 상태에서 멈춘다. 이런식으로 g1, g2, g3 모두 처리하면, 각 generator는 요청을 처리해야 하는 상태거나 혹은 모든 실행을 마치고 결과가 준비된 상태에 머므르게 된다.

이를테면 어느 순간에는 g1은 r1 요청이 처리를 기다리며 멈춰있고, g2는 v2값을 계산하여 실행을 마쳤으며 , g3는 r2 요청 처리를 대기하며 멈춘 상태일 수 있다. 이런 상태에서 interpreter는 r1따로 r2 따로 요청을 처리하는 대신 [r1, r2] 로 요청을 끌어모을 수 있어야 우리가 원하는 병렬/배치 처리를 할 수 있다.

한번에 끝까지 계산하는 interpreter 대신 요청 처리를 대기하는 상태까지만 진행시키는 도움 함수가 필요하다는 얘기다. step() 이라고 이름지은 이 함수가 있다고 했을 때 interpreter는 매우 간단하다. step()을 실행하여 done이 계산되면 그대로 끝, blocked가 반환되면 해당 요청을 process한 다음 continuation을 실행하는 과정을 반복하면 된다.

function step(stack, value) {
  // ...
}

async function run(g, process) {
  let next = () => step([g()]);
  while (true) {
    const r = next();
    if ("done" in r) return r.done;
    await process(r.blocked); // 다음 실행에 앞서 처리되어야 할 요청들
    next = r.next;
  }
}

사실 run과 step의 관계는 다시 generator/interpreter 패턴으로 설명할 수 있지만 배열 처리에서 step을 재귀적으로 사용하게 되면 요청에 대한 결과 연결 처리가 까다로와져서 이 부분은 CPS로 처리한다. (CPS로 스택오버플로 회피하기 참고)

마지막step함수는 이미 살펴본 interpreter와 동일한데 다만 요청이나 배열을 따로 추가 처리하며, 모든 계산이 끝나면 {done: value}를 반환한다.

function step(stack, value) {
  while (stack.length > 0) {
    const top = stack.pop();
    if (top instanceof Request) {
      ... 
    } else if (Array.isArray(top)) {
      ...
    } else if (typeof top.next === "function") {
      const r = top.next(value);
      if (r.done) {
        value = r.value;
      } else {
        stack.push(top); // top not finished
        stack.push(r.value);
      }
    }
  }
  return { done: value };
}

요청은 step에서 직접 처리하지 않으며 병렬/배치 처리될 수 있도록 배열에 담아서 반환한다.

if (top instanceof Request) {
  const r = { request: top.request, value: undefined };
  return {
    blocked: [r],   // 배열로 만든다.
    next: () => step(stack, r.value)  // 요청이 해결되면 실행된다.
  };
else if (Array.isArray(top)) {
 ...

step()이 요청 r 을 만나면 {blocked: [{request: r}], next: () => …} 를 반환한다. 배열을 통한 병렬/배치 처리에서 이 객체의 대기 요청들을 모두 머지한다.

} else if (Array.isArray(top)) {
  const values = top.map(g => step([g]));  // recursive step()
  if (values.every(v => "done" in v)) {
    value = values.map(v => v.done);
  } else {
    return {
      blocked: values.reduce((a, b) => a.concat(b.blocked || []), []),
      next: function next() {
        for (const i in values) {
          if ("blocked" in values[i]) {
            values[i] = values[i].next();
          }
        }
        if (values.every(v => "done" in v)) {
          return step(stack, values.map(v => v.done));
        } else {
          return {
            blocked: values.reduce((a, b) => a.concat(b.blocked || []), []),
            next
          };
        }
      }
    };
  }
} else ...

처음 배열의 모든 요소를 step()으로 진행하여 모두 {done} 상태로 계산이 완료되면 value 만 업데이트하고 while 문을 계속한다.(trampoline과 비슷하다) 하지만 그렇지 않다면 {blocked} 로 모든 대기 요청들을 결합하여 반환한다. 배열의 모든 요청들이 처리된 다음에서야 원래 실행 중인 stack을 기준으로 실행을 이어간다.(step()의 재귀 호출에 전달하는 스택과 continuation에서 resume할 때 step()에 전달하는 스택이 다른 점에 유의하자)

여기까지 interpreter 를 확장하고 나면 다음의 commonFpFriends 함수는 모듈화를 해치지 않으면서 병렬/배치 처리도 가능하게 되었다.

function* commonFpFriends(id1, id2) {
  const [fs1, fs2] = yield [fpFriends(id1), fpFriends(id2)];
  return intersect(fs1, fs2);
}

한 걸음 더 나가면 interpreter 쪽에서 요청에 대한 응답을 cache로 처리함으로써 중복 요청을 제거하는 것도 가능하다. 예를 들면 이런식이다.

function step(cache, stack, value) {
  ... // returns {done: value}
      // return  {blocked: requests, next: continuation}
}
async function run(g, process) {
  let next = () => step(new HashMap(), [g()]);
  while (true) {
    const r = next();
    if ("done" in r) return r.done;
    await process(r.blocked);
    next = r.next;
  }
}

이제 다시 처음으로 돌아가서 async 코루틴으로 이러한 효과를 다 얻을 수 있을지 생각해보자. 그러기 위해서는 commonFpFriends() 라는 함수 하나를 위해서 API 수준에서부터 배치 여부를 고민하고 적당한 모듈화마저 포기해야 할 것이다.

하지만 generator/interpreter 패턴에서는 꽤나 복잡한 상황까지 커버하도록 기능을 확장하면서도 generator 파트의 간결성이나 모듈화도 해치지 않을 수 있었다. 테스트용 interpreter를 만든다면 generator 파트만 따로 테스트하는 것도 가능하다.

• 코드 참고

JavaScript 제너레이터는 함수형 프로그래밍의 모나드와 매우 닮아 있다. 아마도 이것 때문에 그렇게 제너레이터 이야기를 많이 하게 된 것 같다.

함수형 프로그래밍, 특히 하스켈과 같은 순수 함수형 프로그래밍에서 모나드는 매우 중요한 역할을 한다. a -> b 라는 단순한 값 계산이 아니라 a -> X b 처럼 어떤 효과 X를 동반하는 계산을 나타내는 방법이기 때문이다. X 라는 효과를 “모나드”로 만드는 순간 함수형 프로그래밍이 그렇게 추구하는 “합성에 의한 프로그래밍”이 다시 가능해지는 것이다.

예를 들어, a -> b 함수 f와 b -> c 함수 g 는 딱 봐도 너무나 쉽게 합성할 수 있다. a 가 f를 지나 b가 되고, 거기에 g 를 붙이면 b가 다시 c가 된다.

그런데 a -> X b 함수 f와 b -> X c 함수 g는 합성하기가 곤란하다. b가 계산 결과에 나타나기는 하지만 부수효과(side effect)를 감추지 못하는 순수 함수형 언어는 X 라는 타입생성자로 그 효과를 드러내야만 한다. 그러다 보니 X b 결과에 g 를 바로 가져다 붙일 수고 없다. 바로 여기 모나드가 등장하는 것이다.

X에 모나드 패턴을 적용시키면, 즉 X에 대해 >>= , bind, flatMap, .. 뭐가 되었건, 이 연산자를 정의하기만 하면 a -> X b 함수와 b -> X c 함수를 합성하여 a -> X c 가 만들어지게끔 한 것이다.

하스켈은 IO를 처리할 방법을 찾다가 이 모나드 패턴을 발견했고, IO를 모나드로 만들면서 정말 “깔끔하게” IO를 처리할 수 있게 되었다. 나아가 거의 모든 부수효과들을 모나드로 만들어버렸다.

모나드는 부수 효과를 수반하는 계산을 효과적으로 합성하기 위한 도구라고 했다. 그런데 긴 모나드 여정 뒤에, 모나드에서 “부수 효과”마저 배제하고, 오로지 “합성”에만 포커스를 둔 새로운 모나드가 발견(발명?)되었다. 바로 Free Monad다.

Free 모나드는 “효과”마저 인자로 추출하였고, 결과적으로 남은 구조는 오로지 모나드 합성만을 위한 형태가 되었다. Free 모나드로 만들어지는 어떤 값(계산식, 혹은 프로그램)은 사실 아무런 효과를 수반하지 않으며, 주입된 “효과”라는 것은 나중에 해석하기 위한 힌트 정보만 담당한다. 이제 이 Free 모나드로 만들어진 값이 실제로 어떤 효과를 발휘하려면 “해석기”가 필요해진다.

Free 모나드를 설명하는 글에는 이런 내용들이 나온다.

• Free 모나드는 AST 를 만들어내고, 나중에 해석기가 이 AST를 처리한다.
• Free 모나드로 만들어진 프로그램은 코루틴처럼 동작한다. 다른 한쪽이 해석기가 된다.

다시 말하지만, Free 모나드는 “효과”마저 배제한 순수한 계산 식을 만들 수 있게 했고, 나중에 해석기에서 “효과”를 처리한다. 그리고 Free 모나드 프로그램은 해석기와 코루틴 처럼 동작한다.

한참 돌고 돌아 다시 JavaScript 제너레이터를 이야기 할 수 있게 되었다. Free 모나드의 마지막 설명을 보면 이것이 딱 제너레이터를 설명하는 것 같다.

이미 순수와는 담쌓은 JavaScript지만 “효과”를 프로그램에서 분리 시키는 것은 개발자에게 굉장히 강력한 도구가 된다. 여러가지 효과가 코드에 섞여버린다든지 혹은 런타임이 처리하는 효과가 어떤 형식을 강요한다든지 하는 경우에 이런 효과들을 프로그램에서 분리시키고 해석기에서 처리할 수 있기 때문이다.

JavaScript 제너레이터는 순수 함수형 프로그래밍에서 Free 모나드로 작성한 프로그램 역할을 할 수 있다. 해석기에게 부탁할 내용이 있다면 yield 로 요청을 전달하면 되고, 해석기는 그 요청을 처리한 다음 다시 제너레이터에 넘겨준다. (이 구조를 가장 잘 활용하고 있는 라이브러리가 아마도 Redux-saga가 아닐까 한다.)

interpret(function *() {
  var response = yield request;
  ...
})

foo() 함수가 bar() 함수를 부르는 다음 경우를 보자.

function foo() {
  return 1 + bar();
}

function bar() {
  return 42;
}

console.log(foo());

foo>bar 로 이어지는 호출관계가 있다. 제너레이터를 이용하면 스택리스하게 이 호출관계를 나타낼 수 있다.

function* foo() {
  return 1 + (yield bar());
}

function* bar() {
  return 42;
}

console.log(loop(foo()));

내용은 동일하지만 실행 시 콜스택 사용이 다르다. 제너레이터 버전에서는 yield 할때 foo() 에서 빠져나와 loop()에서 bar() 로 진입한다. bar() 에서 42가 반환되면 loop() 에서 이 값을 foo() 로 전달하며 진입한다. 다시 foo()가 43을 반환하면 loop() 는 이 값을 반환한다.

call      |  generator
------------------------
foo()     |  loop()
  bar()   |    foo()
foo()     |  loop()
          |    bar()
          |  loop()
          |    foo()
          |  loop()

loop() 구현은 다음과 같다.

function loop(g) {
  const stack = [g];
  let returnValue;
  while (stack.length > 0) {
    let { value, done } = stack[stack.length - 1].next(returnValue);
    returnValue = undefined;
    if (done) {
      stack.pop();
      returnValue = value;
    } else {
      stack.push(value);
    }
  }
  return returnValue;
}

그런데 이 경우 bar() 에서 예외를 던지면 어떻게 될까? 스택을 사용하지 않다보니 이 예외는 foo() 로 전달되는 대신 콜스택 상 바로 위의 loop() 로 전달된다.

function* foo() {
  try { return 1 + (yield bar()); } // 의미없다
  catch (e) { return 41; }
}

function* bar() {
  throw new Error();
}

Error
    at bar (ex.js:6:9)
    at bar.next (<anonymous>)
    at loop (ex.js:14:51)
    at Object.<anonymous> (ex.js:25:13)

JavaScript 의 “Generator” 객체는 Iterator와 같이 next() 메쏘드를 가지면서 추가로 throw() 와 return() 메쏘드를 가진다. 여기서 throw() 를 이용하면 원래의 호출 관계에서 bar() 의 예외를 foo() 에서 받는 것과 같은 효과를 얻을 수 있다.

function loop(g) {
  const stack = [g];
  let returnValue, err;
  while (stack.length > 0) {
    try {
      let next;
      if (err) {
        next = stack[stack.length - 1].throw(err);
        err = undefined;
      } else {
        next = stack[stack.length - 1].next(returnValue);
        returnValue = undefined;
      }
      if (next.done) {
        stack.pop();
        returnValue = next.value;
      } else {
        stack.push(next.value);
      }
    } catch (e) {
      stack.pop();
      err = e;
    }
  }
  if (err) throw err;
  return returnValue;
}

이제 foo() 에서는 bar() 가 throw 한 예외를 catch 할 수 있다. 아쉬운 점은 new Error() 로 생성되는 예외의 stack 속성이 큰 도움을 주지 못하는 것.

트램폴리닝은 사실 non-local jump에 해당하며 그 점프를 함수 호출로 하는 대신 트램폴린 함수가 대신 해주는 것이다. 그런데 꼬리 재귀가 아닌 경우 jump 후 본래의 실행 흐름으로 return 할 방법이 없으니 적용할 수 없었던 것.

// parens <- paren*
function parens() {
  let result = [];
  while (true) {
    const r = paren();   // paren 호출 후 할 일이 많다.
    if (r === FAIL) break;
    result.push(r);
  }
  return result;
}

그러니 jump할 대상지점과 return할 지점을 함께 반환한다면 트램폴린 함수에서 이를 처리해줄 수 있고, 이 방법으로 꼬리재귀 트램폴리닝 처럼 스택오버플로를 회피할 수 있다.

이건 이미 JavaScript에서 너무나 익숙한 콜백 전달, 혹은 Continuation Passing Style 일 뿐이다. 아래처럼 CPS로 바꾸면 된다.

function parens() {
  let result = [];
  return call(paren, [], function loop(r) {
    if (r === FAIL) return result;
    result.push(r);
    return call(paren, [], loop);
  });
}

사실 제너레이터를 사용한 것과 흐름은 동일하다. 다만 제너레이터 코루틴을 사용하느냐, CPS를 사용하느냐, 스타일의 차이일 뿐이다. (코드)

그런데 이름에도 드러나듯 이 방법은 재귀 호출을 사용하고, 파싱하고자 하는 입력이 깊게 중첩된 경우 스택오버플로 에러를 유발할 수도 있다. 회피 방법은 RD 스타일의 파서 대신 직접 스택 처리를 해주면 되는데, 이렇게 되면 RD 파서 만큼의 직관적인 코드 대신 조금 더 복잡해진다.

여기도 JS 제너레이터를 등장시킬 수 있다. 직접 스택을 관리하는 건 맞는데 RD 파서 형태를 유지할 수 있어서 두 마리 토끼를 잡는 셈이다.

먼저 재귀호출로 인한 스택오버플로를 재현하기 위해 간단한 RD 파서를 하나 만들어보자. 파서가 처리할 입력은 간단한 재귀 문법으로 [], (), {}, [()], {()()[]} 처럼 쌍이 맞는 괄호 문자열이다. (이번에는 모나딕 파서 대신 일반적인 명령형 스타일로 작성할 것이다.)

아래는 중첩괄호 문장의 문법이다. (문법은 Parsing Expression Grammer 표기를 빌렸다.)

parens <- paren*               -- zero or more
paren  <- p1 / p2 / p3         -- choice
p1     <- '('  parens  ')'     -- sequence
p2     <- '['  parens  ']'
p3     <- '{'  parens  '}'

문법 룰을 좀더 간결하게 한 줄로 나타낼 수도 있겠지만 재귀 호출 스택에 압박을 가하기 위해 여러 단계로 나눠봤다.

각 룰은 파싱 함수 하나로 쉽게 변환 가능하다. parens <- paren*룰에 해당하는 parens()함수는 paren() 함수를 반복 호출하여 그 결과를 모으면 된다.

function parens() {
  let result = [];
  while (true) {
    const r = paren();
    if (r === FAIL) break;
    result.push(r);
  }
  return result;
}

paren <- p1 / p2 / p3 라는 규칙은 괄호의 세 종류 중 하나를 나타내는데, 왼쪽 우선순위가 있다. 이 경우 paren() 함수는 각 파서를 순서대로 호출하되 처음으로 성공한 것을 선택하면 된다.

function paren() {
  let r;
  r = p1();
  if (r !== FAIL) return r;
  r = p2();
  if (r !== FAIL) return r;
  return p3();
}

p1 <- ‘(‘ parens ‘)’ 라는 규칙이 재귀적으로 괄호 안에 또다른 괄호들이 들어올 수 있음을 나타낸다. 여는 괄호 문자가 일치한 다음 재귀적으로 parens() 를 호출하고, 그 다음에 닫는 괄호가 나와야 전체가 성공한다. 여기서는 마지막 단계에서 실패했을 때 전체가 실패하므로 파싱 중인 상태를 처음으로 되돌리는 것만 조심하면 된다.

function p1() {
  const p = _pos;    // parsing position 을 저장한다.
  let r;
  let result = [];
  r = char('(');
  if (r !== FAIL) {
    result.push(r);
    r = parens();     // 바로 여기 재귀 호출!
    if (r !== FAIL) {
      result.push(r);
      r = char(')');
      if (r !== FAIL) {
        result.push(r);
        return result;
      }
    }
  }
  _pos = p;
  return FAIL;
}

글자 하나가 일치하는지 확인하는 char(c) 함수는 현재 파싱 위치에 해당 문자가 있는지 확인하면 된다.

function char(c) {
  if (_pos < _input.length && _input[_pos] === c) {
    _pos++;
    return c;
  }
  return FAIL;
}

p2(), p3() 도 위처럼 구현하고 나면 끝이다. 모두 문법으로부터 기계적으로 옮긴 수준이다. 물론 p1(), p2(), p3() 에 나타난 중복은 seq(() => char('('), parens, () => char(')') 와 같이 순차적 연결을 처리하는 seq 도움 함수를 만들어서 단순하게 만들 수 있다.

문법의 root 규칙인 parens에 해당하는 함수를 호출하는 드라이버 함수를 만들어서 동작을 확인해보자.

const FAIL = {};
let _pos;
let _input;

function parse(input) {
  _input = input;
  _pos = 0;

  const r = parens();
  if (r === FAIL || _pos !== _input.length)
    throw new Error("parse error");
  return r;
}

작은 입력에 대해서 잘 동작한다. 하지만 괄호가 한번 중첩할 때마다 다음처럼 호출 스택이 자라난다.

parse()                // 입력: (((((((((((((((...
 parens()
  paren()
   p1()                // 첫괄호
    parens()
     paren()
      p1()             // 두번째 괄호
       parens()
        paren()
         p1()          // 세번째 괄호
          ...

대개 수천 정도의 호출 깊이를 지원하므로 입력 길이만 키우면 쉽게 스택오버플로를 만들 수 있다. (코드#1)

function long(nest) {
  let s = "";
  for (let i=0; i<nest; i++) s = '(' + s + ')';
  return s;
}
console.log(parse(long(10000)));

RangeError: Maximum call stack size exceeded
    at paren (rd.js:21:15)
    at parens (rd.js:15:15)
    at p1 (rd.js:36:9)
    at paren (rd.js:23:7)
    at parens (rd.js:15:15)
    at p1 (rd.js:36:9)
    at paren (rd.js:23:7)

힘들게 파서까지 만들어서 문제를 재현했다. 이제 해결 방안을 찾아보자.

이렇게 호출 스택이 쌓이는 것을 회피하는 방법 중 하나가 트램폴리닝이다. 트램폴리닝은 결과 대신 반환된 함수를 드라이버 함수가 실행시켜주는 방식이다. 예를 들어 쉽게 루프로 변환할 수 없는 상호 재귀 함수 even/odd 를 보자. 물론 이렇게 짝수/홀수를 판별할 일은 없지만, even(100000)으로 쉽게 스택오버플로를 만들 수 있다. (코드 #2)

function even(n) {
  if (n === 0) return true;
  else return odd(n-1);
}
function odd(n) {
  if (n === 0) return false;
  else return even(n-1);
}

위 함수는 트램폴리닝을 적용하면 다음처럼 바뀐다.

function even(n) {
  if (n === 0) return true;
  else return () => odd(n-1);
}
function odd(n) {
  if (n === 0) return false;
  else return () => even(n-1);
}

이 경우는 트램폴린을 튕겨줄 드라이버 함수가 필요하다. (코드 #3)

function trampoline(f) {
  while (typeof f === 'function') {
   f = f();
  }
  return f;
}

그런데 트램폴리닝은 꼬리 호출을 변환하기는 쉬워도 다른 경우는 변형하기 어렵다. 우리가 구현한 파서의 parens() 함수는 paren()을 꼬리호출하는 대신 중간에 반복 호출하여 배열에 값을 쌓아간다. 즉 실제로 “스택” 역할을 할 무언가가 필요하다. 그런데 트램폴리닝의 드라이버 함수는 스택은 나몰라라 하므로 적용할 수 없다.

(업데이트: 트램폴린 비슷하게 CPS로 바꿔서 해결할 수도 있다. 하지만 모양이 많이 바뀐다.)

제너레이터를 이용해보자. 제너레이터는 자신의 로컬 상태를 저장하면서 멈출 수 있다. 그리고 필요에 따라 멈출 지점에서 실행을 이어갈 수 있다.

parens() 파싱 함수가 직접 paren()을 호출하는 것은 호출 스택에 로컬 상태를 저장하며 스택이 한 층 자라나게 되지만, parens() 파싱 함수를 제너레이터로 만들면 paren() 을 호출해야 하는 지점에서 yield로 멈추고 부모 함수로 돌아갈 수 있다. 호출 스택이 자라나지 않게 된다. yield를 처리할 드라이버는 parens() 가 결과를 반환하는 대신 다른 파싱 함수인 paren()을 yield 한 것을 확인하여 직접 paren()으로 진입한다. 이 때 paren()이 결과를 반환하면 드라이버는 자신이 직접 관리하는 스택에서 parens() 를 꺼내어 paren()의 결과로 실행을 재개한다. 제너레이터로 구현한 parens() 파싱함수를 보자.

function* parens() {
  let result = [];
  while (true) {
    const r = yield paren();
    if (r === FAIL) break;
    result.push(r);
  }
  return result;
}

원래의 parens() 와 바뀐 부분을 찾아보자. 함수 대신 제너레이터 함수가 되었고, paren() 호출 앞에 yield가 하나 붙었을 뿐이다.

다른 파싱 함수들(p1(), p2(), … 등)도 이렇게 제너레이터 함수로 바꾸고 다른 파싱 함수를 호출할 일이 있으면 그 앞에 yield 만 붙이면 된다. 원래 RD 파서의 장점이 그대로 유지된다.

(주의! “모나딕 파서”에서도 파서 함수를 제너레이터 함수로 만들었다. 그런데, 거기서 제너레이터의 역할은 지연 리스트 효과를 위한 것. 즉 Non-deterministic 파서를 만들기 위한 것이었다. 여기서 파서 함수들을 제너레이터로 만든 것은 콜스택 대신 코루틴처럼 사용하기 위한 것이다. 모나딕 파서에서는 드라이버가 따로 필요없었다.)

그러면 이렇게 바뀐 파싱 함수를 호출하는 드라이버를 살펴보자. (코드 #4)

function parse(input) {
  _input = input;
  _pos = 0;

  let stack = [parens()]; // 초기 스택
  let result;
  while (stack.length) {
    let parser = stack[stack.length - 1];
    const { value, done } = parser.next(result);
    if (done) {
      stack.pop();
      result = value;
    } else {
      stack.push(value); // 콜스택 대신 직접 스택에 푸시
      result = undefined;
    }
  }

  if (result === FAIL || _pos < _input.length) {
    throw new Error('parse error');
  }
  return result;
}

기본적으로는 트램폴리닝 방법과 동일하지만 스택을 직접 관리하고 있다. Callee의 결과를 Caller에게 전달하는 것도 담당한다. 이제 실제 함수 호출스택은 자라나지 않는다. 스택 대신 힙을 사용할 뿐이다.

(업데이트: 콜 관계의 함수들을 제너레이터로 바꾸다보니 하위 함수에서 예외를 던져도 상위 함수에서 이를 잡을 수 없다. 예외를 사용하고 싶다면 디스패치 루프에서 이것까지 추가로 고려해줘야 한다. 참고)

예를 들어 char()파서에서 콜스택을 확인해보자.

function* char(c) {
  throw new Error();

    at char (rd-parser.js:94:9)
    at char.next (<anonymous>)
    at parse (rd-parser.js:14:36)
    at Object.<anonymous> (rd-parser.js:110:13)
    at Module._compile (module.js:612:30)
    at Object.Module._extensions..js (module.js:623:10)
    at Module.load (module.js:531:32)
    at tryModuleLoad (module.js:494:12)
    at Function.Module._load (module.js:486:3)
    at Function.Module.runMain (module.js:653:10)

원래의 호출 관계는 parser() → parens() → paren() → p1() → char() 순서인데, 호출 스택을 보면 parse()에서 바로 char.next()로 진입하는 것을 확인할 수 있다.

이제 Recursive Descent Parser를 사용한다고 해서 스택오버플로를 걱정할 필요는 없다.