callback, cps, call/cc 그리고 monad

jsonkim·2020년 5월 13일
3

call/cc 너무 어렵다. 😩

Javascript와 비동기

JavaScript에서 비동기를 다루는 방법중 하나는 callback을 사용한 방식이다. 어떤 함수가

function f<A>(arg: any, cb: (a: A) => void)

와 같은 시그니쳐를 가지고 있을때, 비동기 함수 f는 자신의 작업이 완료되면 인자로 전달받은 cb함수를 호출하게 된다. cb함수를 보통 callback이라고 부르기도 하지만 continuation이라고도 부른다. 이에 대한 자세한 의미는 '더 읽어보기'를 참고하자.

continuation을 전달하는 형태의 프로그래밍을 continuation-passing style(cps)이라고 부르며, 이것은 비동기에서 뿐만 아니라 분기, 예외, 성공과 실패등 프로그램의 흐름을 제어하는 전반적인 부분에 사용할 수 있다.

cps의 일반적인 의미

위에서 설명한 f함수의 cb인자를 "나중에 호출되는 함수(callback)"라고 설명 할 수도 있지만 "반환값을 전달 받는 함수"라고 설명하면 이해하기가 더 쉽다고 생각한다. 이와 대비해서 값을 직접 반환하는 함수를 "direct-style"이라고도 부른다. 입력값을 그대로 리턴하는 id함수를 예로 들어보자. 이 코드는 여기를 참고했다.

const id = <A>(a: A): A => {
  return a
}

const id_cps = <A>(a: A, ret: (a: A) => void): void = {
  // return 키워드를 함수로 만들었다.
  ret(a)
}

ret의 더 나은 타입은 <R>((a: A) => R) => R 이 되어야겠지만, 여기서는 직관적인 이해를 위해 단순화하였다.

함수 합성과 callback-hell

cps스타일의 함수를 작성하다보면 악명높은 callback-hell을 만나게 된다. 이런 현상이 나타나는 이유는 cps함수의 합성이 필요해지기 때문이다.

const x1 = fn1(x0)
const x2 = fn2(x1)
const x3 = fn3(x2)
// x3를 사용하는 어떤 코드

// 위의 코드와 아래 코드는 동일하다.
const x3 = fn3(fn2(f1(x0)))
// x3를 사용하는 어떤 코드
next_fn(x3)

와 같은 코드를 cps스타일로 작성한다면 아래처럼 합성을 해야한다.

fn1(x0, (x1) => {
  return fn2(x1, (x2) => {
    return fn3(x2, (x3) => {
      // x3를 사용하는 어떤 코드
      return id_cps(x3)
    }
  }
})(next_fn)

함수의 값을 돌려받을 수 없기 때문에 무조건 중첩된 형태로만 코드가 작성되어야 한다.

call/cc

continuation과 call/cc에 대한 자세한 설명은 이 곳을 참고하자. 여기서는 javascript에서 call/cc를 구현하고 사용하는 방법에 대해서만 간단히 언급하겠다. (이걸 정리하려고 이 글을 쓰고 있는 중이다.)

// type Cont<A> = <R>((a: A) => R) => R
const callCC = <A, B>(f: (k: (a: A) => Cont<B>) => Cont<A>): Cont<A>
const callCC = f => (cc => f(x => _k => cc(x))(cc))

callCC(escape => k => fn1(x0, (x1) => {
  return fn2(x1, (x2) => {
    
    if (... 임의의 조건 검사 등등 ...) {
      return escape(some value)
    }
    
    return fn3(x2, (x3) => {
      // x3를 사용하는 어떤 코드
    }
  }
})(k))(next_fn)

시그니처가 복잡한데, 천천히 뜯어보자.

callCC에 전달되는 함수는 f: (k: (a: A) => Cont<B>) => Cont<A>이고, 이에 따라 escape의 타입은 k: (a: A) => Cont<B>가 된다.
callCC내의 두번째 인자 k는 f의 리턴타입이 ((a: A) => R) => R(Cont<A>를 풀어서 썼다)이 되기 때문에 이것의 첫번째 인자인 A => R이 되는것이다. (point-free style로 생략할 수 있으나 설명을 위해 일부러 표시했다.)
이어지는 함수 본문은 내가 사용하고 싶은 cps를 지정한다. 이 함수 본문이 callback-hell 형태로 중첩되어 있다고 하더라도 원하는 위치에서 escape을 사용해서 return 한다면, 중첩된 모든 함수의 호출은 이루어지지 않고 그 위치에서 즉시 리턴 된다.

이것이 가능한 이유는 call/cc는 자기한테 전달된 cps에 개입해서 해당 cps의 원래 continuation대신 자신의 continuation(여기서는 cc)으로 바꿔치기 하기 때문이다. callCC의 구현을 보면 _k가 사용되지 않는 걸 볼 수 있다.

더 생각해보기

함수에 값을 적용하는 함수 apply = f => a => f(a)의 cps버전을 만든다면 이는 곧 continuation monad에 대한 flippedBind(=<<)가 된다. 하스켈과 같은 언어에서는 do-notation을 사용하면 direct-style과 거의 동일한 형태로코드 작성이 가능하다. javascript에서는 async-await구문을 사용하면 cps스타일의 코드를 direct-style로 번역할 수도 있다(promise의 도움이 필요하다). apply 함수 자체를 flip하면 unit(return)이 되는데 이게 우연의 일치인지 어떤 의미가 있는건지는 모르겠다.

더 읽어보기

https://www.hacklewayne.com/callcc-in-haskell-and-my-ultimate-monad
http://blog.tpleyer.de/posts/2019-02-02-callCC-in-Haskell.html
http://guruma.github.io/posts/2018-11-18-Continuation-Concept/
http://dogfeet.github.io/articles/2012/by-example-continuation-passing-style-in-javascript.html
https://medium.com/@jooyunghan/cps%EB%A1%9C-%EC%8A%A4%ED%83%9D%EC%98%A4%EB%B2%84%ED%94%8C%EB%A1%9C-%ED%9A%8C%ED%94%BC%ED%95%98%EA%B8%B0-11db11eb8d75

cps와 monad는 강력한 관계가 있다.https://stackoverflow.com/questions/4525919/continuation-passing-style-vs-monads

여기도 참고
http://blog.sigfpe.com/2008/12/mother-of-all-monads.html

0개의 댓글