Free Monad in “FP in Scala”
Functional Programming in Scala의 13장 제목은 External effects and I/O. 이 장은 외부 효과를 어떤 식으로 다루느냐를 설명하는 듯 하지만 사실은 Free monad의 유도 과정을 보여주는 것이 더 큰 목적인 것 같다.
IO를 순수 함수로 처리하는 과정에서 IO 타입을 유도하고, 효과적인 합성을 위해 IO 타입을 모나드로 발전시킨다. 이때 발생하는 스택오버플로 문제를 회피하기 위해 IO 모나드를 변형한다.(tailrec 가능하도록) 이렇게 도출된 IO 모나드의 인터프리터 함수가 trampolining 방식으로 동작하므로, 이를 일반화하여 TailRec 모나드를 만든다. 인터프리터 함수 run입장에서 TailRec을 실행하는 건 그냥 멈췄던 함수를 실행시켜주는 것 뿐이므로, 동시성을 부여하려면 (앞 장에서 구현했던) Par를 결과로 하는 Async 모나드를 만들 수 있다. 이쯤 되고 보니 TailRec이 멈춘 함수를 실행하는 것, Async가 Par를 통해 콜백을 실행하는 것만 다를 뿐 두 모나드는 거의 똑같다. 여기서 “효과”에 해당하는 함수 실행(Function0)과 동시성 결합(Par)을 파라미터로 추출할 수 있고, 이렇게 얻은 결과물이 바로 Free[F,A]다.
sealed trait Free[F[_],A]
case class Return[F[_],A](a: A) extends Free[F,A]
case class Suspend[F[_],A](s: F[A]) extends Free[F,A]
case class FlatMap[F[_],A,B](s: Free[F,A],
f: A => Free[F,B]) extends Free[F,B]type TailRec[A] = Free[Function0,A]
type Async[A] = Free[Par,A]
그럼 Free[F, A]가 무얼 의미하는가?
Free[F, A]는 A타입의 값을 F로 겹겹이 감싼 재귀 자료 구조!
여기에 각주로 두가지 설명을 덧붙인다.
Put another way, it’s a tree with data of type A at the leaves, where the branching is described by F . Put yet another way, it’s an abstract syntax tree for a program in a language whose instructions are given by F , with free variables in A .
Free[F, A]는 A 타입의 값을 리프 노드로 가지는 트리 자료 구조이며 F는 트리의 가지 구조를 결정한다. 혹은 Free[F, A]는 F를 명령어로, A를 자유 변수로 가지는 프로그램의 Abstract syntax tree이다.
이후로 Free monad를 응용하는 몇가지 사례를 들면서 “효과”를 어떻게 다루는지 보여준다. 최종적으로 IO[A] = Free[Par, A]로 두고 “순수”한 main 을 아래처럼 구현한다.
abstract class App {
import java.util.concurrent._ def unsafePerformIO[A](a: IO[A])(pool: ExecutorService): A =
Par.run(pool)(run(a)(parMonad)) def main(args: Array[String]): Unit = {
val pool = Executors.fixedThreadPool(8)
unsafePerformIO(pureMain(args))(pool)
} def pureMain(args: IndexedSeq[String]): IO[Unit]
}
pureMain 이 만들어내는 IO[Unit]은 사실 Free[Par,A], 그러니까 순수한 데이터 덩어리 일 뿐이다. 이것을 unsafePerformIO 에서, 먼저 Free.run을 통해 IO[A]가 Par[A]로 변환되고, 이것이 다시 Par.run을 거쳐 실제 실행된다.
참고자료
이 과정을 Free monad와는 별개로 Java를 이용해 구현한 것도 있다.
CouchDB의 스칼라 인터페이스 DSL “Stoop”은 FP in Scala의 저자 Rúnar Bjarnason가 자주 써먹는 예이기도 하다. (Contributors에는 Jessica Kerr도 있음)
type Couch[A] = Free[CouchF, A]// DSLdef createDB(name: String): Couch[DB] =
liftF(CreateDB(name, DB(name)))
def dropDB(name: String): Couch[Boolean] =
liftF(DropDB(name, identity))
def getAllDBs: Couch[List[DB]] =
liftF(GetAllDBs(identity))// USAGEdescribe ("creating a database then dropping it") {
val dbName = "testdb_" + UUID.randomUUID().toString
it ("should return true since the database exists") {
val test = couch {
createDB(dbName) >> dropDB(dbName)
}
test.run should be (true)
}
}// Algebrasealed trait CouchF[+A] {
def map[B](f: A => B): CouchF[B]
}
case class CreateDB[+A](name: String, a: A)
extends CouchF[A]
case class DropDB[+A](name: String, k: Boolean => A)
extends CouchF[A]
case class GetAllDBs[+A](k: List[DB] => A)
extends CouchF[A]
case class NewDoc[+A](db: DB, ...)
extends CouchF[A]
case class UpdateDoc[+A](db: DB, ...)
extends CouchF[A]// Interpretertrait CouchInterpreter {
def apply[A](action: Couch[A]): Task[A]
}case class CouchHttp(dbhost: String, ...)
extends CouchInterpreter { ... }
Free 모나드의 유도 과정을 다른 각도에서 코믹하게 보여주는 영상도 있다. “The Interpreter Pattern Revisited”라는 발표 영상이다.
FP in Scala의 13장을 압축하여 설명하는 페이퍼로 “Stackless Scala With Free Monads”라는 것도 있으니 참고.
