[Monad/Free Monad] 내멋대로 Free 모나드 이해하기

Free Monad + 인터프리터 패턴은 재대로 써본적이 없어서 맨날 까먹는다... 까먹지 않기 위해 포스팅

 

FP 에서는 순수를 지향하기 때문에...

부수효과가 섞이는것을 꺼린다,  특히 부수효과는 쉽게 전파되기 때문에 부수효과를 최대한 배재하고자 한다.

그런데 부수효과 없는 프로그램이란 없는법, 콘솔 출력도 해야되고 파일 저장도 해야되고 DB엑세스도 해야긋지..

근데 그럼 어떻게 하느냐!

바로 [효과] 자체를 분리하고, [효과] 가 필요한 순간에만 [효과]를 적용시키는것!

엥 그거 완전 의존성 주입 아니냐?

인터페이스를 이용한 OOP 식 DI, ISP 가 깨질확률이 높고, Compose를 할수없고, Funciton 자체를 DI 받는경우는, 효과가 분리되야할 Function 이 너무 많으면 모든 Function 에 DI 를 적용하는것은 관리가 어렵고 코드 자체도 장황해진다.
어쩌고 저쩌고 라고한다.

 

암튼 FP 의 자랑 모오오오나드를 이용하면 효과적으로 효과를 분리할수있다 (오 라임~)

그리고 FP Lang 에서 지원해주는 Tool들, 예를 들어 하스켈의 Do, 스칼라의 For, F#의 계산식 등을 이용하면

코드도 깔삼하게 나온다.

 

암튼 그래서 어떻게 해야하느냐...

예시를 통해서 알아보자

예제는내가 애용하는 fsharpforfunandprofit.com/posts/13-ways-of-looking-at-a-turtle/ 의

Thirteen ways of looking at a turtle | F# for fun and profit

요기의 거북이를 조금 간략화 해서 설명하도록 하겠다.

 

거북이를 만들건데, 거북이는 크게 3가지 정도 기능을 할수있다 치자.

움직일수있고 (Move), 회전할수있으며 (Turn), 잠잘수 있다 (Sleep)

 

이 거북이를 컨트롤 하고싶은데, 어떻게 움직였으면 좋겠나하면

대충 이렇게, 앞으로 200미터 이동 한 다음에, 90도 돈 다음에, 100 이동 한 다음에, 90 도 돈 다음에, 100 이동 한 다음에, 한숨 잔 다음에, 100 이동

이렇게 움직이도록 하고싶다.

일반적으로 코드로 구현하면 다음과 같다.

Move(200);
Turn(90);
Move(100);
Turn(90);
Move(100);
Sleep(5);
Move(100);

하지만 이건 함수를 호출한것이므로, 함수 자체의 실행이 요구된다.

따라서 우리는 "함수"를 호출하는것을 아예 뺴고

아까 말한 그대로

200미터 이동 한 다음에;
90도 돈 다음에;
100 이동 한 다음에;
90 도 돈 다음에;
100 이동 한 다음에;
한숨 잔 다음에;
100 이동;

이렇게 순수 데이터만 가지고있고, 이걸 나중에 효과가 필요할때 이걸 실행해주는 인터프리터에 넘겨주는 것이다.

그럼 이 문장을 내가 사용하는 프로그래밍 언어로 모델링 하느냐.. 하면

딱봐도 패턴이 있다

"200 미터 이동 한다음에" 라는 표현은 -> 200 미터 (value) 이동(command) 한 다음에(then) 이다

Command 에 대한 Value 을 나타내는 방법은 쉽다.

type TurtleCommand =
    | Move of int 
    | Turn of int 
    | Sleep of int

난 F# 을 사용했는데, Case Class를 이용하던 뭘하던 해당 값을 가질수있는 Type 을 만들고, 타입에 따라 행동을 매칭해주면 해당 Command(Type) 에 따른  Value 를 나타낼수있다.

이제 여기서 우리는 ~한 다음에 (then) 을 추가 해주어야하는데 그럼 어떻게 추가하느냐?

가장 쉬운 방법은 Tuple로 Then을 써주는것이다.

type TurtleProgram<'a> =
    | Move of int * (unit -> TurtleProgram<'a>)
    | Turn of int * (unit -> TurtleProgram<'a>)
    | Sleep of int * (unit -> TurtleProgram<'a>)

일반적으로 이렇게 인터프리터에 들어갈 type 에는뒤에 Program을 붙이는게 F# 관례인듯하다

N미터(int) 이동(Move) 한 다음에 (unit -> TurtleProgram) 꼴이다.

(unit -> TurtleProgram) 은 unit을 받고 TurtleProgram 을 리턴하는 함수꼴인데 이렇게된 이유는,

200미터 이동 한 다음에 -> (방금 이동한 결과는 아무의미 없고 그다음) 90도 돈 다음에 ->

이렇게 해석되기 때문이다.

만약 거북이가 발이 다쳐서 움직일수 없는 경우가 있다면?

type TurtleProgram<'a> =
    | Move of int * (bool -> TurtleProgram<'a>)
    | Turn of int * (unit -> TurtleProgram<'a>)
    | Sleep of int * (unit -> TurtleProgram<'a>)

이렇게 표현된다.

200미터 이동 한 다음에 -> (근데 방금 이동시켰는데, 진짜 이동했나? 암튼 이동시킨 다음에는) 90도 돈 다음에 ->

이렇게 해석될수있다.

 

근데 현재 상태에서는 Turtle 이 모든 행동뒤에, 한 다음에 (then) 이 붙어있기 때문에

거북이는 평생 ~~ 한 다음에 ~~한 다음에 ~~한 다음에... 를 엮어나가야한다..

거북이도 일이 끝마치면 좀 쉬어야 하기 떄문에.. 이제 그만 쉬라는 Stop 까지 넣어주자.

type TurtleProgram<'a> =
    | Stop of 'a
    | Move of int * (bool -> TurtleProgram<'a>)
    | Turn of int * (unit -> TurtleProgram<'a>)
    | Sleep of int * (unit -> TurtleProgram<'a>)

이상태에서.

200미터 이동 한 다음에;
90도 돈 다음에;
100 이동 한 다음에;
90 도 돈 다음에;
100 이동 한 다음에;
한숨 잔 다음에;
100 이동;

아까 만들어둔 명령이 이건데, 현재 우리가 만든 Turtle Program은 "이동" 한 이후는 무조건 ~~ 다음에를 명령받아야 되므로, 조금 수정해보자

200미터 이동 한 다음에;
90도 돈 다음에;
100 이동 한 다음에;
90 도 돈 다음에;
100 이동 한 다음에;
한숨 잔 다음에;
100 이동 한 다음에;
쉬어라~ ;

위와 같은 명령을 만들수있다.

let command =  Move (200, (fun _ ->
               Turn (90, (fun _ ->
               Move (100, (fun _ ->
               Turn (90, (fun _ ->
               Move (100, (fun _ ->
               Sleep( 5, (fun _ ->
               Move (100, (fun _ ->
               Stop)
               )))))))))))))

문장의 순서만 다르지 거의 완벽하게 호환된 명령셋을 만들었다.

여기서 중첩된 괄호가 꼴보기 싫으므로 TurtleProgram 을 모오오나드로 만들어서 계산식으로 깔끔하게 만들수 있다.

 

type TurtleProgram<'a> =
    | Stop of 'a
    | Move of int * (bool -> TurtleProgram<'a>)
    | Turn of int * (unit -> TurtleProgram<'a>)
    | Sleep of int * (unit -> TurtleProgram<'a>)


let command =  Move (200, (fun _ ->
               Turn (90, (fun _ ->
               Move (100, (fun _ ->
               Turn (90, (fun _ ->
               Move (100, (fun _ ->
               Sleep( 5, (fun _ ->
               Move (100, (fun _ ->
               Stop ())
               )))))))))))))

let returnT x = 
    Stop x  

let rec bindT f inst  = 
    match inst with
    | Stop x -> 
        f x
    | Move(dist,next) -> 
         Move(dist,next >> bindT f) 
    | Turn(angle,next) -> 
        Turn(angle,next >> bindT f)  
    | Sleep (time,next) ->
        Sleep(time, next >> bindT f)

type TurtleProgramBuilder() =
    member this.Return(x) = returnT x
    member this.Bind(x,f) = bindT f x
    member this.Zero(x) = returnT ()

let turtleProgram = TurtleProgramBuilder()

우선 모나드에서는 return (zero, pure 기타등등) 을 위한 값이 하나 무조건 필요하므로, Stop 도 제네릭한 값을 가질수 있도록 변경해주었다. 사용하는 언어에 맞게 모오오나드로 변경해주면 된다.

F#이기 때문에, f#에 맞게 터틀프로그램에 대한 return 과 bind 함수를 작성, 보일러 플레이트 코드

Bind 는 내부의 값에 F를 적용시킨다 A->M[B] 함수를 M[A] 에 적용시켜 M[B] 를 만드는게 Bind 다, 나의 TurtleProgram 에서는 'a 가 A 인데, 'a 는 Stop 만 가지고 있고, 나머지는 함수이므로, >> 통해서 함수를 함성시켜 놓는것!

let commandSame = 
    turtleProgram {
      do! Move (200, (fun _ -> Stop ()))
      do! Turn (90, (fun _ ->  Stop ()))
      do! Move (100, (fun _ -> Stop ()))
      do! Turn (90, (fun _ ->  Stop ()))
      do! Move (100, (fun _ -> Stop ()))
      do! Sleep( 5, (fun _ ->  Stop ()))
      do! Move (100, (fun _ -> Stop ()))
    }

위 와 같이 bind 되도록하여 똑같은 내용을 보다 깔끔하게 작성할수있다.

여기에 Helper 함수를 추가하여 더 깔끔하게 작성할수도 있고,

모나드의 기능을 십분활용하여 마치 절차지향 프로그래밍 하듯이 코딩이 가능하다.

 

이렇게 만들어진 데이터는 말그대로 아무기능하지 않는 데이터이다.

그냥 우리가 거북이를 어떻게 움직이고 싶다~ 라고 기술한 "데이터" 이기 때문에 어떠한 부수효과도 가지지 않는다.

나중에 이렇게 움직이는 거북의 콘솔 출력이 필요하면 콘솔에 출력하는 인터프리터를 짜면되고, 거북이의 움직인 거리를 구하고 싶은거면 거북이의 움직인 거리를 구하는 인터프리터를 짜면된다.

//거리 계산 인터프리터
let rec interpretAsDistance distanceSoFar program =
    let recurse = interpretAsDistance 
    match program with
    | Stop x -> 
        distanceSoFar
    | Move (dist,next) ->
        let newDistanceSoFar = distanceSoFar + dist
        let nextProgram = next true 
        recurse newDistanceSoFar nextProgram 
    | Turn (angle,next) ->
        let nextProgram = next()
        recurse distanceSoFar nextProgram 
    | Sleep (time,next) ->
        let nextProgram = next()
        recurse distanceSoFar nextProgram

//콘솔 출력 인터프리터
let rec interpretSay  program =
    let recurse = interpretSay 
    let log = printfn "%s"
    match program with
    | Stop x -> printfn "STOP"
    | Move (dist,next) ->
        printfn "Move %A" dist
        let nextProgram = next true 
        recurse  nextProgram 
    | Turn (angle,next) ->
        printfn "Turn %A" angle
        // no change in distanceSoFar
        let nextProgram = next()
        recurse  nextProgram 
    | Sleep (time,next) ->
        printfn "Sleep %A" time
        let nextProgram = next()
        recurse  nextProgram

 

 

그럼 Free 모나드는 무엇이냐? 하면

Free 모나드는 펑터에 대한 모나드이다. (먼 개소리야 이게? )

 

우리가 만든 인터프리터의 명령은 "거북이 이동", "거북이 회전", "거북이 꿀잠" + 종료 이다

만약 신용카드 관리 프로그림을 인터프리터 패턴으로 짠다면 "출금", "입금", "카드중지" ... + 종료 이런식으로 명령을 내릴텐데, 결국 "내가원하는 명령들" + 종료 의 패턴을 가지게 된다.

그래서 보다 제네릭하게 "내가 원하는 명령" + 종료 의 타입을 가지는 모나드를 만든것이 Free 모나드이다.

type FreeMonadExampleProgram<'a> =
	| Free of DoInstruction<FreeMonadExampleProgram<'a>>
	| Pure of 'a

 

스칼라로 치면

sealed trait Free[F[_],A]

 

Pure 의 경우 종료, Free 의 경우 계속 다음 Free (또는 Pure) 를 재귀적으로 감싼다, 감싸면서 필요한 명령 (DoInstruction) 을 가지게 된다.

 

기존에는 연속적 호출을 위하여  TurtleProgram 타입이 모나드였는데 (bind 함수를 구현했는데)

이제는 FreeMonadExampleProgram가 연속적 호출을 담당하므로 이 타입에 대한 Bind 함수를 구현하면 된다.

대신 내가 원하는 명령 ( "거북이 이동", "거북이 회전", "거북이 꿀잠") 을 DoInstruction 타입에 넣고,

Bind 대신, 해당 명령을 사용할수있도록, Map 함수를 구현하여 펑터로 만든다.

그렇게 되면? 짜잔~ Functor 인 우리 DoInstruction ("거북이 이동", "거북이 회전", "거북이 꿀잠") 에 대한 재귀적 처리가 가능한 모나드인 FreeMonadExampleProgram 가 완성된다.

 

//My Functor
    type TurtleInstruction<'next> = 
        | Move  of int * (bool -> 'next)
        | Turn  of int * 'next
        | Sleep of int * 'next
  
/// map the instructions
    let mapInstr f inst  = 
        match inst with
        | Move(dist,next) -> 
            Move(dist,next >> f) 
        | Turn(angle,next) -> 
            Turn(angle,f next)  
        | Sleep(time,next) -> 
            Sleep(time,f next) 


//Free Monad
    type TurtleProgram<'a> = 
        | Pure of 'a
        | Free of TurtleInstruction<TurtleProgram<'a>>
        
    let returnT x = 
        Stop x 

    let rec bindT f program = 
        match program with
        | Free instruction -> 
            Free (mapInstr (bindT f) instruction)
        | Stop x -> 
            f x

 

Free Monad의 의의는 Fuctor 를 AST 꼴의 형태로 만들어 나만의 DSL 를 구축하고, 그 DSL 을 해석하는 해석기를 만들어서 Side Effect 를 분리 시킬수있다. (어찌보면 AST 를 Monadic 하게 추상화한게 Free Monad 라고 보인다)

 

 

ps. Scala 코드를 뜬금없이 Free Monad 에 집어넣은 이유는, Scala, Haskell은 타입클래스와 HKT 에 대한 지원(?), 구현(?) 이 빠방해서 진짜 Free Moand (모든 Functor 에 대한 재귀적 자료구조 ) 를 구현할수있는데 반하여 F# 은 그렇지 않기 때문에 (...) Instruction (Fucntor) 에 대한 Program (Free Monad) 를 같은 내용일지라도 각각 구현해야한다. 위 예제에서도

TurtleProgram 의 Free를 보면 TurtleInstruction 이 박혀있다.  (따라서 Free monad가 아닌 Free Monad 패턴 이라고 한단다)

Scala의 경우 Free[F[_],A] 보면 F[_], A 로 둘다 제네릭 하다.

ps2. 어찌보면 약간 Lisp 계열의 S-Expression 식의 Parser 를 모나딕하게 구현하는거 아닐까..?

ps3. 솔직히 제대로 써본적이 없어서 맞는지 모르겟다.