Skip to content

2016 09 20 cbk

Jump to bottom
baekkyu cho edited this page Oct 4, 2016 · 9 revisions

6장 순수 함수적 상태

<주요내용>
* 상태(state)를 다루는 순수 함수적 프로그램을 작성하는 방법을 알아본다.
* 임의의 상태있는(stateful) API를 순수 함수적으로 만드는 데 쓰이는 기본 패턴들을 익힌다.

6.1 부수 효과를 이용한 난수 발생

  • 스칼라에서 난수를 발생시킬 때에는 표준라이브러리(scala.util.Random)를 이용하면 된다.
//현재시스템 시간을 종잣값(seed)으로 해서 새 난수 발생기를 만든다.
scala> val rng = new scala.util.Random
scala> rng.nextDouble
res1: Double = 0.09876676677678
scala> rng.nextDouble
res2: Double = 0.07871283787821
  • scala.util.Random 안에서 일어나는 일을 알지 못하더라도, 해당객체 안에는 메서드를 호출할 때마다 갱신되는 어떤 내부 상태가 존재한다고 가정할 수 있다. 그렇지 않다면 nextDouble을 호출할 때마다 같은 값을 얻게 될 것이기 때문이다.
  • 상태갱신은 부수효과로 수행되므로 이 메서드는 참조에 투명하지 않다.
// 육면체 주사위의 굴림을 흉내내는 것 1~6사이의 값이 나와야 한다.
def rollDie: Int = {
  val rng = new scala.util.Random
  rng.nextInt(6)
}
  • 위 메서드는 0~5사이의 값을 되돌려준다, 테스트케이스를 만들었을경우 상황에 따라 검사에 성공할 수도, 실패할 수도 있다.

6.2 순수 함수적 난수 발생

  • 참조 투명성을 되찾는 관건은 상태 갱신을 명시적으로 드러내는 것이다.
// 새 상태를 발생한 난수와 함께 돌려주는 인터페이스 (기존 상태는 수정하지 않는다)
trait RNG {
  def nextInt: (Int, RNG)
}

// 순수 함수적 난수 발생기
case class SimpleRNG(seed: Long) extends RNG {
  def nextInt: (Int, RNG) = {
    val newSeed = (seed * 0x5DEECE66DL + 0xBL) & 0xFFFFFFFFFFFFL
    val nextRNG = SimpleRNG(newSeed)
    val n = (newSeed >>> 16).toInt  // >>>는 빈자리를 0으로 채우는 오른쪽시프트
    (n, nextRNG)
  }
}

//REPL 에서의 사용예제
scala> val rng = SimpleRNG(42) //임의의 seed
rng: SimpleRNG = SimpleRNG(42)

scala> val (n1, rng2) = rng.nextInt
n1: Int = 12314124
rng2: RNG = SimpleRNG(10101012314)
  • 위 예제를 여러번 되풀이해서 실행해도 항상 같은 값들이 나온다. (참조 투명성)

6.3 상태 있는 API를 순수하게 만들기

  • 겉보기에 상태 있는 API를 순수하게 만드는 문제와 그 해법(API가 실제로 뭔가를 변이하는 대신 다음 상태를 계산하게 하는 것)은 난수발생에만 국한된 것은 아니고, 자주 등장하며 항상 동일한 방식으로 해결할 수 있다.
// 상태값을 가진 클래스
// bar, baz는 s의 상태값을 변이한다고 가정.
class Foo {
  private var s: FooState = ...
  def bar: Bar  
  def baz: Int  
}

// 위와 같은 클래스가 존재할 경우, 한 상태에서 다음 상태로의 전이를 명시적으로 드러내는 과정을 진행하여
// 이 API를 순수 함수적 API로 변환할 수 있다.
trait Foo {
  def bar: (Bar, Foo)
  def baz: (Int, Foo)
}
//위와 같은 패턴은, 계산된 다음 상태를 프로그램의 나머지 부분에 전달하는 책임을 호출자에게 지운다.

6.1 연습문제

  • RNG.nextInt를 이용해서 0 이상, Int.maxValue 이하의 난수 정수를 생성하는 함수를 작성하라, nextInt가 Int.minValue를 돌려주는 구석진 경우(음이 아닌 대응수가 없다)도 확실하게 처리해야 한다.
def nonNegativeInt(rng: RNg): (Int, RNG)
  • 정답
def nonNegativeInt(rng: RNG): (Int, RNG) = {
  val (i, r) = rng.nextInt
  (if (i < 0) -(i + 1) else i, r)
}

6.4 상태 동작을 위한 더 나은 API

  • 앞의 구현들을 살펴보면 모든 함수가 어떤 형식 A에 대해 RNG => (A, RNG) 형식을 사용한다는 공통의 패턴을 발견할 수 있다.
  • 한 RNG 상태를 다른 RNG 상태로 변환한다는 점에서, 이런 종류의 함수를 상태동작(state action) / 상태전이(state transition)이라고 부른다.
  • 이 상태 동작들을 고차 함수인 조합기(combinator)를 이용해서 조합할 수 있다.
// RNG 상태동작 자료형식에 대한 별칭(alias)를 선언함.
type Rand[+A] = RNG => (A, RNG)
  • 이것은 하나의 상태 동작이다. 즉 어떤 RNG에 의존하고, 그것을 이용해서 A를 생성하며, RNG를다른 동작이 이후에 사용할 수 있는 새로운 상태로 전이하는 하나의 프로그램이다.
// Rand 동작들을 조합하되 RNG상태들을 명시적으로 전달하지 않아도 되는 조합기를 작성
val int: Rand[Int] = _.nextInt
  • 이런 식으로 나아가다 보면 그러한 모든 전달을 자동으로 처리하는 일종의 영역 국한 언어(domain-specific langage, DSL)에 도달하게 된다.
//주어진 RNG를 사용하지 않고 그대로 전달하는, 가장 간단한 형태의 RNG상태전이 동작이다.
def unit[A](a: A): Rand[A] = 
  rng => (a, rng)

//한 상태동작의 출력을 변환하되 상태자체는 수정하지 않는 map도 생각할 수 있다.
def map[A, B](s: Rand[A])(f: A => B): Rand[B] = 
  rng => {
    val (a, rng2) = s(rng)
    (f(a), rng2)
  }

// map에대한 예제 (연습문제 6.1을 재활용)
def nonNegativeInt(rng: RNG): (Int, RNG) // 0 ~ Int.MaxValue 사이의 난수정수를 생성하는 함수

//0보다 크거나 같고, 2로 나누어지는 Int를 발생하는 함수
def nonNegativeEven: Rand[Int] = 
  map(nonNegativeInt)(i => i - i % 2)

6.4.1 상태 동작들의 조합

  • RNG동작을 단항함수가 아니라, 이항함수로 조합하는 새로운 조합기 map2에 대한 문제
  • 연습문제 6.6 - 다음과 같은 서명에 따라 map2를 구현하라, 이 함수는 두 상태동작 ra 및 rb와 이들의 결과를 조합하는 함수 f를 받고, 두 동작을 조합한 새 동작을 돌려준다.
def map2[A, B, C](ra: Rand[A], rb: Rand[B])(f: (A, B) => C): Rand[C]
  • 정답
def map2[A, B, C](ra: Rand[A], rb: Rand[B])(f: (A, B) => C): Rand[C]
  rng => {
    val (a, r1) = ra(rng)
    val (b, r2) = rb(r1)
    (f(a, b), r2)
  }
  • map2를 한번만 작성해 두면 이를 이용해서 임의의 RNG상태 동작들을 조합할 수 있다. 예를들어 A형식의 값을 발생하는 동작과 B형식의 값을 발생하는 동작이 있다면 그 둘을 조합해서 A와 B의 쌍을 발생하는 동작을 얻을 수 있다.
def both[A, B](ra: Rand[A], rb: Rand[B]): Rand[(A, B)] = 
  map2(ra, rb)((_, _))

6.4.2 내포된 상태 동작

  • 지금까지의 예에서 하나의 패턴이 보일 것이다. 이를 잘 추출한다면 RNG값을 명시적으로 언급하거나 전달하지 않는 구현이 가능하다.
  • 그러나 map과 map2로는 잘 잘성할 수 없는 함수들 도 있다.
// 0 이상, n미만의 정수 난수를 발생하는 함수
// 음이 아닌 정수 난수를 n으로 나눈 나머지를 돌려준다.
def nonNegativeLessThan(n: Int): Rand[Int] = 
  map(nonNegativeInt) { _ % n }
  • 요구된 범위의 난수가 발생하긴 하지만, Int.MaxValue가 n으로 나누어떨어지지 않을 수도 있으므로 전체적으로 난수들이 치우치게 된다.
  • nonNegativeInt가 32비트 정수를 벗어나지 않는 n의 최대배수보다 큰 수를 발생 했다면 더 작은 수가 나오길 바라면서 난수발생기를 다시 시도해야 한다.
def nonNegativeLessThan(n: Int): Rand[Int] = 
  map(nonNegativeInt) { i =>
    val mod = i % n
    if (i + (n - 1) - mod >= 0) mod else nonNegativeLessThan(n)(???) //형식이 맞지 않는다.
  }
  • 위 코드에서 형식이 맞지 않는 문제가 있다. 이 함수는 Rand[Int]를 돌려주어야 하며, 그것은 RNG하나를 인수로 받는 함수여야 한다.
  • 상태를 전파처리하는 flatMap 조합기
def flatMap[A, B](f: Rand[A])(g: A => Rand[B]): Rand[B] = 
  rng => {
    val (a, rng2) = f(rng)
    g(a)(rng2) // We pass the new state along
  }
  • flatMap을 이용하여 재구현
def nonNegativeLessThan(n: Int): Rand[Int] = {
  flatMap(nonNegativeInt) { i =>
    val mod = i % n
    if (i + (n-1) - mod >= 0) unit(mod) else nonNegativeLessThan(n)
  }
}

6.5 일반적 상태 동작 자료 형식

  • 지금까지 작성한 함수들 (unit, map, map2 flatMap)은 난수발생에만 국한된 것이 아니다. 이들은 상태동작에 대해 작용하는 범용 함수들로, 상태의 구체적인 종류는 신경쓰지 않는다.
//좀 더 일반적인 형태의 서명 (RNG를 단지 S로만 바꿨을 뿐이다)
def map[S, A, B](a: S => (A, S))(f: A => B): S => (B, S)
  • 임의의 상태를 처리할 수 있는 일반적인 형식을 생각해보자.
type State[S, +A] = S => (A, S)
  • State는 어떤 상태를 유지하는 계산, 즉 상태동작 또는 상태전이를 대표한다.
  • 심지어 명령문(statement)을 대표한다고 할 수도 있다.
// 독립적인 클래스의 형태로도 작성할 수 있다.
case class State[S, +A](run: S => (A, S)) {
  def map[B](f: A => B): State[S, B] =
    flatMap(a => unit(f(a)))
  def map2[B,C](sb: State[S, B])(f: (A, B) => C): State[S, C] =
    flatMap(a => sb.map(b => f(a, b)))
  def flatMap[B](f: A => State[S, B]): State[S, B] = State(s => {
    val (a, s1) = run(s)
    f(a).run(s1)
  })
}

6.6 순수 함수적 명령식 프로그래밍

  • 이전 절들에서 작성한 예제들은 상태동작을 실행하고, 그 결과를 val에 배정하고, 그 val을 사용하는 또 다른 상태 동작을 실행하고, 그 결과를 또 다른 val에 배정하는 등의 형태로 이어졌다.
  • 이와 같은 방식은 명령식 프로그래밍과 아주 비슷하다. (명령형 프로그래밍 패러다임에서 하나의 프로그램은 일련의 명령문(statement)들로 이루어지며, 각 명령문은 프로그램의 상태를 수정할 수 있다)
  • 함수형 프로그래밍은 단지 부수효과가 없는 프로그래밍일 뿐임을 기억하길 바란다.
//함수형 스타일
val ns: Rand[List[Int]] = 
  int.flatMap(x =>  //int는 하나의 정수난수를 발생하는 Rand[Int]형식의 값.
    int.flatMap(y =>  
      ints(x).map(xs =>  //ints(x)는 길이가 x인 목록을 생성한다.
        xs.map(_ % y))))  //목록의 모든 요소를 y로 나눈 나머지로 치환한다.

//명령형 스타일의 프로그래밍
val ns: Rand[List[Int]] = for {
  x <- int
  y <- int
  xs <- ints(x)
} yield xs.map(_ % y)
  • 위 코드에서 명령형 스타일의 코드가 읽기(쓰기)가 훨씬 쉽다.
  • for-함축(flatMap)을 활용하는 이런 종류의 명령식 프로그래밍을 지원하는 데 필요한 것은 기본적인 State조합기 두 개 뿐이다.
  • 현재 상태를 얻는 조합기가 get이고, 새 상태를 설정하는 조합기가 set이라고 할 때, 상태를 임의의 방식으로 수정하는 조합기를 다음과 같이 구현할 수 있다.
def modify[S](f: S => S): State[S, Unit] = for {
  s <- get
  _ <- set(f(s))
} yield ()

// 입력상태를 전달하고, 그것을 반환값으로 돌려준다.
def get[S]: State[S, S] = State(s => (s, s))

// 새 상태를 받고, 결과로 나오는 동작은 입력상태를 무시하고, 그것을 새 상태로 치환하며, 의미있는 값 대신 ()를 돌려준다.
def set[S](s: S): State[S, Unit] = State(_ => ((), s))

연습문제 6.11 (어려움)

  • 사탕판매기 작성
  • 입력
  • 사용자가 넣는 동전
  • 돌리면 사탕이 나오는 손잡이
  • 상태
  • 사탕이 몇개나 남았는지, 동전이 몇개나 들어있는지 추적한다.
sealed trait Input
case object Coin extends Input
case object Turn extends Input

case class Machine(locked: Boolean, candies: Int, coins: Int)

  • 규칙

  • 잠겨진 판매기에 동전을 넣으면, 사탕이 남아 있는 경우 잠김이 풀린다.

  • 풀린 판매기의 손잡이를 돌리면 사탕이 나오고 판매기가 잠긴다.

  • 잠긴 판매기의 손잡이를 돌리거나 풀린 판매기에 동전을 넣으면 아무 일도 생기지 않는다.

  • 사탕이 없는 판매기는 모든 입력을 무시한다.

  • 정답

sealed trait Input
case object Coin extends Input
case object Turn extends Input

case class Machine(locked: Boolean, candies: Int, coins: Int)

object Candy {
  def update = (i: Input) => (s: Machine) =>
    (i, s) match {
      case (_, Machine(_, 0, _)) => s
      case (Coin, Machine(false, _, _)) => s
      case (Turn, Machine(true, _, _)) => s
      case (Coin, Machine(true, candy, coin)) =>
        Machine(false, candy, coin + 1)
      case (Turn, Machine(false, candy, coin)) =>
        Machine(true, candy - 1, coin)
    }

  def simulateMachine(inputs: List[Input]): State[Machine, (Int, Int)] = for {
    _ <- sequence(inputs map (modify[Machine] _ compose update))
    s <- get
  } yield (s.coins, s.candies)
}

Refer

스터디 진행상황

뻔뻔한 발표

Clone this wiki locally