[FP In Scala] 지역 효과와 변이 가능 상태

참조 투명성 개념을 다룬다. 효과가 한 표현식 안에서 지역적으로 발생할 수 있다는, 그리고 그런 효과가 발생했음을 더 큰 프로그램의 다른 부분이 전혀 관측하지 못함을 보장할 수 있다는 착안을 살펴본다.

1. 순수 함수적 변이 가능 상태

순수 함수형 프로그래밍에서 mutable 상태를 사용할 수 없을 것 같지만 그렇지 않다.

참조 투명성과 순수성의 정의를 자세히 보면 지역(local) 상태의 변이를 금지하는 사항은 전혀 없음을 알 수 있다.

참조 투명성과 순수성의 정의를 다시 살펴보면..

 

참조 투명성과 순수성의 정의

• 만일 모든 프로그램 p에 대해 표현식 e의 모든 출현을 e의 평가 결과로 치환해도 p의 의미에 아무런 영향을 미치지 않는다면, 그 표현식 e는 참조에 투명하다.

표현식을 해당 표현식의 평가(evaluation) 결과로 대체해도 프로그램에 아무런 지장을 미치지 않는다면, 해당 표현식을 참조에 투명하다라고 한다.

 int globalValue = 0;

 int rq(int x)
 {
   globalValue++;
   return x + globalValue;
 }

 int rt(int x)
 {
   return x + 1;
 }

• 만일 표현식 f(x)가 참조에 투명한 모든 x에 대해 참조에 투명하면, 함수 f는 순수하다.

참조 상 투명한 함수를 평가하게 되면 동일한 인자에 대해 동일한 값을 반환해야 한다. 그러한 함수를 순수 함수라고 부른다.

 

다음 함수는 for 루프와 갱신 가능한 var, 변이 가능한 배열을 사용하지만 순수 함수이다.

def quicksort(xs: List[Int]): List[Int] = if (xs.isEmpty) xs else {
  val arr = xs.toArray
  def swap(x: Int, y: Int) = {	
    val tmp = arr(x)
    arr(x) = arr(y)
    arr(y) = tmp
  }
  def partition(n: Int, r: Int, pivot: Int) = {	
    val pivotVal = arr(pivot)
    swap(pivot, r)
    var j = n
    for (i <- n until r) if (arr(i) < pivotVal) {
      swap(i, j)
      j += 1
    }
    swap(j, r)
    j
  }
  def qs(n: Int, r: Int): Unit = if (n < r) {	
    val pi = partition(n, r, n + (n - r) / 2)
    qs(n, pi - 1)
    qs(pi + 1, r)
  }
  qs(0, arr.length - 1)
  arr.toList
}

이 함수를 호출하는 쪽에서는 quicksort의 본문 내부에 있는 개별 부분표현식이 참조에 투명하지 않다는,

다시 말해 지역 메서드 swap과 partition, qs가 순수 함수가 아니라는 점을 알지 못한다.

quicksort 함수 외부에서는 변이 가능 배열에 대한 참조가 전혀 없기 때문이다.

 

모든 변이는 지역 범위 안에서 일어나므로 전체적인 함수는 순수하다.

 

즉, List[Int] 형식의 어떤 표현식 xs가 참조에 투명하면 표현식 quicksort(xs)도 항상 참초에 투명하다.

함수 안에서 변이가 발생해도, 변이된 객체를 함수 외부에서 전혀 참조하지 않는다면 그 변이는 부수 효과가 아니다.

quicksort 같은 알고리즘은 제대로 작동하기 위해서는 자료를 제자리에서 변이해야 한다.

스칼라에서는 지역 범위에서 생성된 자료를 항상 안전하게 변이할 수 있다.

 

어떤 함수가 내부적으로 부수 효과가 있는 구성요소를 사용하더라도 호출자에게 순수한 외부 인터페이스를 제공한다면, 그런 함수를 사용하는 것은 함수형 프로그램의 원리를 위반하는 것이 아니다.

 

원칙적으로, 구현에서 지역 부수 효과를 사용하는 순수 함수를 만드는 것에는 아무런 문제가 없다.

 

2. 부수 효과를 지역 범위로 한정하는 자료 형식

스칼라의 형식 시스템을 이용해서 변이를 지역 점위로 한정하는 자료 형식을 개발해 본다.

 

2.1 범위 있는 변이를 위한 작은 언어

변이 가능 상태를 서술하는 작은 언어를 만든다. 

 

상태를 쓰고 읽는 것은 기존의 State[S, A] 모나드로도 가능하다. 이 모나드는 입력 상태를 받고 결과 하나와 출력 상태를 산출하는 S => (A, S) 형식의 함수일 뿐이다. 

 

지금 말하는 것은 상태를 제자리에서 변이하는 것이지 한 동작에서 다음 동작으로 넘겨주는 것이 아니다.

 

넘겨줄 것은 S 형식으로 표시된 일종의 토큰이다. 토큰과 함께 호출된 함수는 같은 형식 S로 표시된 자료를 변이할 '권한'을 가진다.

 

새 자료 형식은 스칼라의 형식 시스템을 이용해서 다음 두 가지 사항을 정적으로 보장하기 위한 것이다. 즉, 다음 두 불변식이 성립하지 않으면 코드가 컴파일되면 안된다.

 

• 함수 안에 변이 가능 객체에 대한 참조가 있다고 할 때, 함수 외부에서는 그 참조에 대한 변이를 전혀 관측할 수 없다.
• 변이 가능 객체는 그것이 생성된 범위 밖에서는 전혀 관측할 수 없다.

quicksort 구현은 첫 불변식을 만족한다. 함수는 배열을 변이하지만, 그 배열에 대한 참조가 함수 안에만 있으므로 함수 밖에서는 그러한 변이를 전혀 관측하지 못한다. 

 

둘째 불변식이 지켜진다면, 변이 가능 상태가 범위 안에 머무르는한 그 어떤 변이 가능 상태에 대한 참조도 새어나가지 않는다. 

 

지역 효과 모나드(Local Effect Monad)를 ST(state thread, state transition, state tag 등의 약자)라 정하고 새 ST 자료 형식을 작성한다.

run 메서드가 보호된 메서드라는 점을 제외하면 이 모나드의 구조는 State 모나드의 것과 동일하다.

 

sealed trait ST[S,A] { self =>
  protected def run(s: S): (A,S)
  def map[B](f: A => B): ST[S,B] = new ST[S,B] {
    def run(s: S) = {
      val (a, s1) = self.run(s)
      (f(a), s1)
    }
  }
  def flatMap[B](f: A => ST[S,B]): ST[S,B] = new ST[S,B] {
    def run(s: S) = {
      val (a, s1) = self.run(s)
      f(a).run(s1)
    }
  }
}
object ST {
  def apply[S,A](a: => A) = {
    lazy val memo = a	
    new ST[S,A] {
      def run(s: S) = (memo, s)
    }
  }
}

run 메서드를 보호 메서드로 한 것은, s가 상태의 변이 능력을 나타내는데 그 변이가 범위를 탈출해서는 안 되기 때문이다. 

 

ST 동작을 실행할 때 초기 상태를 어떻게 제공해야 할까?

핵심은 형식 시스템을 이용해서 변이 가능 상태의 범위를 한정할 수 있다는 점이다.

 

2.2 범위 있는 변이를 위한 작은 언어

ST 모나드의 첫 응용 예제는 변이 가능 참조를 서술하는 작은 언어이다.

이 언어는 몇 가지 기본수단들로 이루어진 조합기 라이브러리의 형태다.

 

변이 가능 메모리 칸(cell)들을 언급하는 언어는 반드시 다음과 같은 기본 명령들을 갖추어야 한다.

• 새 변이 가능 칸을 할당하는 명령
• 변이 가능 칸에 값을 쓰는 명령
• 변이 가능 칸을 읽는 명령

변이 가능 참조에 사용할 자료구조는 그냥 보호된 var 변수 하나를 감싸는 wrapper이다.

sealed trait STRef[S,A] {
  protected var cell: A
  def read: ST[S,A] = ST(cell)
  def write(a: A): ST[S,Unit] = new ST[S,Unit] {
    def run(s: S) = {
      cell = a
      ((), s)
    }
  }
}

object STRef {
  def apply[S,A](a: A): ST[S, STRef[S,A]] = ST(new STRef[S,A] {
    var cell = a
  })
}

메모리 칸을 읽고 쓰는 STRef 메서드들은 ST 동작만 돌려주므로 순수 함수다.

형식 S가 변이되는 칸(cell)의 형식이 아니며, S 형식의 값을 실제로 사용하는 일은 전혀 없다. 

 

apply를 호출해서 ST 동작 중 하나를 실제로 실행하려면 S 형식의 값이 필요하다. 따라서 그 값은 칸을 바꾸거나 읽을 수 있는 권한을 나타내는 일종의 토큰 역할을 한다.

 

STRef 특질은 밀봉되어 있으며(sealed), 이 특질의 인스턴스를 생성하는 방법은 동반 객체 STRef의 apply 메서드를 호출하는 것뿐이다.

동반 객체(동반 객체는 class나 trait과 동일한 이름을 가지는 object가 Class나 trait과 같은 파일에 있을 때 동반 객체라고 한다. object는 class의 private한 변수나 함수에 접근할 수 있다.)

 

apply는 메모리 칸(cell)의 초기 값(형식은 A)을 받아서 STRef를 생성한다.

 

이 메서드가 실제로 STRef 인스턴스를 돌려주진 않는다.

S 형식의 토큰과 함께 실행되었을 때 STRef를 생성하는 ST[S, STRef[S, A]] 동작을 돌려준다.

ST 동작과 그것이 생성하는 STRef에 같은 S 형식이 부여된다는 점이 중요하다.

 

간단한 ST 프로그램을 작성해서 시험해 보자.

지금은 S 형식을 임의로 선택해야 하기 때문에 코드가 어색하다. 다음은 Nothing을 임의로 선택한 예이다.

 

for {
  r1 <- STRef[Nothing,Int](1)
  r2 <- STRef[Nothing,Int](1)
  x <- r1.read
  y <- r2.read
  _ <- r1.write(y+1)
  _ <- r2.write(x+1)
  a <- r1.read
  b <- r2.read
} yield (a,b)

 아직 run이 보호된 메서드라 실행하지 못한다.

2.3 변이 가능 상태 동작의 실행

실행했을 때 어떤 지역 변이 가능 상태를 할당하고, 그것을 변이해서 어떤 과제를 수행하고, 그런 다음 그 변이 가능 상태를 페기하는 계산을 ST를 이용해서 구축하는 것이다.

 

전체 계산은 참조에 투명하다. -> 변이 가능 상태가 지역 점위 안에서 비공개로 존재하기 때문.

 

원하는 것은 지역 범위 한정을 보장받는 것이다.

예를 들어 변이 가능 var를 담은 STRef가 있다고 할 때, 그 STRef를 ST 바깥으로 추출하는 것이 불가능함을 스칼라의 형식 시스템이 보장해 주어야 한다.

STRef가 외부로 유출되면 변이 가능 참조가 ST 동작의 지역 범위라는 불변식이 깨져서 전체 공정의 참조 투명성이 무너진다.

 

ST 동작을 안전하게 실행하는 방법은 무엇일까?

 

첫째로 안전하게 실행할 수 있는 동작과 그렇지 않은 동작을 구분해야 한다.

 

• ST[S, STRef[S, Int]] (안전하게 실행할 수 없음)
• ST[S, Int] (완전히 안전하게 실행할 수 있음

전자는 변이 가능 참조를 돌려주는 ST 동작이다. 후자는 그렇지 않다. 

 

이 두 형식에는 활용 가능한 차이점이 존재하는데 STRef에는 형식 S가 관여하지만 Int에는 관여하지 않는다는 점이다.

 

ST[S, STRef[S, Int]] 형식의 동작은 실행을 금지해야 한다. 이 동작을 실행하면 STRef가 노출될 수 있기 때문이다.

T가 형식 S에 관련된 형식이면 ST[S, T]는 실행하기에 안전하지 않다.

반대로, 변이 가능 객체를 노출하지 않는 ST 동작의 실행은 항상 안전하다.

ST[S, Int]같은 형식의 순수 동작이 있다면, 그것을 S에 전달해서 Int를 뽑아내도 안전하다. 나아가 이런 경우에 S가 실제로 무엇인지는 중요하지 않다. 어차피 폐기하기 때문이다. 이는 그러한 동작이 S에 대해 다형적이라는(임의의 S에 대해서도 작동한다는) 뜻이기도 하다.

 

이 점을 나타내기 위해, 실행하기에 안전한 ST 동작들, 다시 말해 S에 대해 다형적인 동작들을 대표하는 새 특질을 도입한다.

trait RunnableST[A] {
  def apply[S]: ST[S,A]
}

RunnableST[A] 형식의 값은 형식 S를 받아서 ST[S, A] 형식의 값을 산출하는 참수이다.

 

이전에 S 형식을 임의로 Nothing으로 선택했다. 대신 이번에는 그것을 RunnableST로 감싸서 S에 대해 다형적으로 만든다. 그러면 형식 S를 선택할 필요가 없다.

S는 apply를 호출하는 코드에 의해 자동으로 결정된다.

val p = new RunnableST[(Int, Int)] {
  def apply[S] = for {
    r1 <- STRef(1)
    r2 <- STRef(2)
    x <- r1.read
    y <- r2.read
    _ <- r1.write(y+1)
    _ <- r2.write(x+1)
    a <- r1.read
    b <- r2.read
  } yield (a,b)
}

이제 S에 해당하는 형식을 임의로 선택함으로써 임의의 다형적 RunnableST에 대해 apply를 호출하는 runST 함수를 작성할 수 있다. RunnableST 동작은 S에 대해 다형적이므로, 전달된 값이 전혀 쓰이지 않는다는 점이 보장된다. 따라서 Unit 형식의 값인 ()를 전달하는 것도 사실상 완벽하게 안전한다.

 

runST 함수는 반드시 ST 동반 객체에 넣어야 한다. run은 ST 특질의 보호된 메서드이므로, 동반 객체에서는 접근할 수 있지만 그 외의 곳에서는 접근할 수 없다.

object ST {
  def apply[S,A](a: => A) = {
    lazy val memo = a
    new ST[S,A] {
      def run(s: S) = (memo, s)
    }
  }
  def runST[A](st: RunnableST[A]): A =
    st.apply[Unit].run(())._1
}

앞에서 보았던 간단한 프로그램 p를 실행할 수 있다.

scala> val p = new RunnableST[(Int, Int)] {
     |   def apply[S] = for {
     |     r1 <- STRef(1)
     |     r2 <- STRef(2)
     |     x <- r1.read
     |     y <- r2.read
     |     _ <- r1.write(y+1)
     |     _ <- r2.write(x+1)
     |     a <- r1.read
     |     b <- r2.read
     |   } yield (a,b)
     | }
p: RunnableST[(Int, Int)] = $anon$1@e3a7d65

scala> val r = ST.runST(p)
r: (Int, Int) = (3,2)

표현식 runST(p)는 내부적으로 변이 가능 상태를 사용하지만, 부수 효과를 내지는 않는다. 다른 표현식들이 볼 때 이 표현식은 그냥 보통의 정수 쌍일 뿐이다. 이 표현식은 항상 같은 정수 쌍을 돌려준다.

 

여기서 좀 더 중요한 점은, 변이 가능 참조를 돌려주려 하는 프로그램은 실행할 수 없다는 점이다. 노출된 STRef를 돌려주는 RunnableST를 생성하는 것을 불가능하다.

 

 scala> new RunnableST[STRef[Nothing,Int]] {
     |   def apply[S] = STRef(1)
     | }
<console>:17: error: type mismatch;
 found   : ST[S,STRef[S,Int]]
 required: ST[S,STRef[Nothing,Int]]
               def apply[S] = STRef(1)

형식 S가 apply 메서드에 묶이므로 new RunnableST 블록안에서는 그 형식에 접근할 수 없다.

 

STRef에는 항상 자신이 속한 ST 동작의 형식 S가 꼬리표로 붙으므로, STRef는 결코 ST 동작을 벗어나지 못한다. 이 점은 스칼라의 형식 시스템이 보장한다. 

ST 동작에서 STRef를 얻을 수 없다는 사실은 다음과 같은 명제를 보장한다.

만일 STRef를 얻었다면 그 지점은 그 STRef를 생성한 ST 동작의 내부이며, 따라서 참조를 변이해도 항상 안전하다.