백트래킹을 모나드로 구현해 보았다. 내용을 정리해 보자.
[팁] 모나드에 대한 구체적인 내용은 위키피디아*에 아주 잘 쓰여 있다. 하지만 개인적인 생각으론 모나드를 알기 위해 모든 모나드 구현체를 알 필요는 없다. 모나드로 구현된 어떤 하나라도 이해하게 되면 나머지도 이해가 될 것이다.
*en.wikipedia.org/wiki/Monad_(functional_programming)
내 마음속의 모나드는 부가적인 정보를 처리하는 디자인패턴이다. 예를 들어, 피보나치 수열을 계산한다고 하자. 이때 계산된 피보나치 수열의 최종 값은 '주된 정보'다. '부가적인 정보'가 아니다. 생각할 수 있는 부가적인 정보에는 최종 값을 구하기까지 덧셈을 몇 번 했는지, 함수를 몇 번 호출했는지, 디버깅을 위해 중간 값들을 화면에 어떻게 출력할 것인지 같은 것들이 있을 수 있겠다. 만약 중간에 계산된 값들을 기억하는 동적 계획법(dynamic programming)을 이용한다면 그 기억도 부가적인 정보라 볼 수 있다.
모나드는 다음 세 녀석들로 구성된다. 아마 구체적인 예를 보기 전까진 이것들이 무엇에 쓰는 물건인지 감이 오지 않을테니 타입만 대강 보고 넘어 가자.
타입 생성자 (type constructor)
m : Type -> Type단항 연산자 (unary operator)
ret : 'a -> 'a m2항 연산자(binary operator)
bind : 'a m -> ('a -> 'b m) -> 'b m이것들이 어떤 조건*을 만족해야 모나드라 불릴 수 있다. 사실 모나드의 조건에 대해서도 다루려 했는데 생각보다 백트래킹 모나드 정의가 복잡하여 하지 않기로 한다. 혼신의 힘을 다하면 증명은 될 것 같으나 하지 않았다.
*en.wikipedia.org/wiki/Monad_(functional_programming)#Monad_laws
백트래킹을 구현해 보자. 사용 언어는 OCaml이다.
먼저 타입 생성자 m를 다음과 같이 정의한다. 타입 ('a m)은 백트래킹 함수의 결과 타입을 나타낸다.
type 'a m =
| Succ of 'a * (unit -> 'a m)
| Fail두 가지 핵심을 이해하면 되는데,
백트래킹 함수의 실행은 성공하거나 실패할 수 있다. 그래서 실행 결과가 Succ과 Fail로 나뉜다. option 타입처럼 실행이 성공한 경우 결과값(Succ의 첫 번째 인자)을 출력한다.
백트래킹에서 중요한 건 어떤 값을 계산하여 사용하다가 나중에 실행이 실패했을 때 그 어떤 값을 대신할 값을 다시 계산하는 것이다. 따라서 여기서 '부가적인 정보'는 대신할 값을 계산하는 함수(Succ의 두 번째 인자)가 된다. 이 함수는 unit값을 받아 원래와 같은 타입('a m)의 값을 출력한다.
ret은 보통 타입의 값으로부터 모나드 타입의 값을 만든다. 인자로 값을 하나만 받기 때문에 나중에 실행이 실패했을 때 그것을 대신할 값이 없다.
let ret v = Succ (v, fun () -> Fail)bind는 한마디로 표현해서 OCaml의 let같은 존재이다. 변수에 값을 묶는(bind). 본질적으로는 함수 적용(function application)이다.
(bind e f)의 의미는 "e를 계산하여 함수 f를 적용하는 것"이다. 하지만 위의 타입 정의에서 보듯이 e는 모나드 타입이고 f의 인자는 보통 타입이다. bind는 이 사이의 갭을 메꾼다. 아래의 예를 통해 이해해 보자.
let rec bind e f =
match e with
| Succ (v1, c1) ->
( match f v1 with
| Succ (v2, c2) ->
Succ (v2, compose c2 (fun () -> bind (c1 ()) f))
| Fail -> bind (c1 ()) f )
| Fail -> Fail(8줄) e의 실행이 실패한 경우: 전체 실행도 실패한다. 함수의 인자값 계산에 실패했으니 함수 적용도 실패할 수 밖에 없다.
(3-7줄) e의 실행이 성공한 경우: e를 계산한 값은 v1이다. 그리고 나중에 실행이 실패했을 때 v1을 대신할 값을 계산하는 함수가 c1이다. 이제 f를 v1에 적용할 수 있다. 타입이 맞는다.
(7줄) (f v1)이 실패한 경우: v1으로 계산이 안 되니 그걸 대신할 값인 (c1 ())으로 다시 함수 적용을 시도한다.
(5-6줄) (f v1)이 성공한 경우: 결과값은 v2이고 v2를 대신할 값을 계산하는 함수는 c2이다. 하지만 여기서 (Succ (v2, c2))를 그대로 출력하는 것이 아니라 compose라는 이상한 함수가 등장한다. 왤까?
v2를 가지고 실행하다 나중에 실패하면,
먼저 (c2 ())를 시도해 볼 수 있다. 그리고 그 마저도 실패하면 우리는 (f v1)의 실행이 완전히 실패했음을 확정지을 수 있다.
하지만 이것이 끝이 아니다. 우리에겐 v1을 대신할 c1이 있고 (bind (c1 ()) f)를 통해 추가적인 시도를 해 볼 수 있다.
이 두 시도를 하나로 묶는 함수가 compose이다.
compose : (unit -> 'a m) -> (unit -> 'a m) -> unit -> 'a mlet rec compose c2 c1 () =
match c2 () with
| Succ (v2, c3) -> Succ (v2, compose c3 c1)
| Fail -> c1 ()내용은 간단하다. 먼저 c2를 시도한다. 실패하면 c1을 시도한다. 반대로 성공하면 그 값을 출력한다. 대신 새로 알게 된 시도 c3을 아직 시도하지 않은 c1과 합성하여 보관한다. 해 볼 수 있는 모든 시도를 잃지 않고 모으는 것이 중요하다.
문제: 1부터 5사이의 두 수를 곱해서 n이 되게 하는 숫자쌍을 찾는 프로그램을 백트래킹으로 구현해 보자.
먼저 1부터 5까지의 값을 하나씩 꺼내어 시도해 보는 (int m) 타입의 값이 필요하다. choose는 그를 위한 함수인데 리스트를 받아서 하나씩 꺼내 준다. 이제 어느 정도 익숙해졌을테니 내용은 따로 설명하지 않는다.
let rec choose = function
| [] -> Fail
| hd :: tl -> Succ (hd, fun () -> choose tl)>>=let (>>=) = bindbind를 그냥 쓰면 프로그램이 꽤나 지저분해지기 때문에 중간 연산자를 정의해서 사용한다. 즉, 아래의 두 식은 같은 식이다.
bind e1 (fun x -> e2)
e1 >>= fun x -> e2[팁]
OCaml에서는 두 번째 식처럼 괄호가 없어도 파싱에 문제가 없다.8년 만에 더 직관적으로 모나드를 쓰는 방법이 생겼다. Yaron Minsky 형님이 쓰라면 쓰는 거다. 대강 이렇게 생김.let%bind x = e1 in e2
하스켈에서는 같은 의미로 do 문법을 사용하기도 한다. 앞으로는 do를 보아도 무서워하지 말자.
do x <- e1
e2자, 이제 필요한 모든 준비가 끝났다. 다음 네 줄이면 된다.
let find n =
choose [1; 2; 3; 4; 5] >>= fun x ->
choose [1; 2; 3; 4; 5] >>= fun y ->
if x * y = n then ret (x, y) else Failx, y가 될 수 있는 후보는 1부터 5까지의 수이다.n과 같으면 결과를 출력하고 그렇지 않으면 실패를 한다.추가로 중간에 만족해야 하는 조건을 검사하는 함수 guard를 정의하면 다음과 같이 쓸 수도 있다.
let guard e = if e then ret () else Fail
let find' n =
choose [1; 2; 3; 4; 5] >>= fun x ->
choose [1; 2; 3; 4; 5] >>= fun y ->
guard (x * y = n) >>= fun () ->
ret (x, y)[팁] 두 종류 이상의 모나드를 섞어 쓰는 순간부터 헬게이트가 열린다는 소문이 있다. 조심하자.
블로그가 "사실 그냥 일기"라서 기술적인 내용은 피하려 했는데 독자들의 관심에 대한 욕심에 이래 되었다. 초심을 잃지 말아야지.
2016-08-30 씀.