Scala의 Stream 클래스는 리스트와 같은 컬렉션을 지연 평가를 이용해 효율적으로 다루도록 해줍니다. Scala By Example에도 소개되어 있지만, 스칼라 스터디[각주:1] 진행 당시 급하게 지나간 느낌이 있어 블로그를 통해 Stream의 기본적인 내용을 보다 차분하게 공유해보려 합니다. 본문에서는 존칭을 생략합니다.

Stream 객체의 생성

 백문이 불여일견이니 일단 예제를 보고 시작하자.
scala> Stream.cons(1, Stream.cons(2, Stream.empty))        // (1)
res0: Stream.Cons[Int] = Stream(1, ?)

scala> Stream.range(1,10)                                  // (2)
res1: scala.collection.immutable.Stream[Int] = Stream(1, ?)
 Stream의 생성은 기본적으로 Stream.cons( head:A, tail:Stream[A])의 형태로 이루어진다. List의 cons(::)에 익숙하다면 List와 유사하나 Nil 대신 Stream.empty를, :: 대신 Stream.cons를 사용했다고 보면 된다. 하지만 Stream은 List와는 달리 실제 호출하기 전까지는 tail을 평가하지 않는다는 특징을 가지고 있는데, 이를 이용하면 기존 List에서는 할 수 없던 일들이 가능해진다.

 실제로 (1),(2)의 출력 결과를 살펴보면 (1, ?)의 형태로 tail에 해당하는 부분은 ?이 출력되어 아직 평가되지 않았음을 알려준다. 그러면 (1)의 결과에 tail을 호출해 ?부분의 평가 결과를 확인해보자.
scala> res0.tail                 // res0 = Stream.cons(1, Stream.cons(2, Stream.empty))
res2: scala.collection.immutable.Stream[Int] = Stream(2, ?)
(1)에서 ?로 표시되었던 부분이 다시 (head, tail)로 평가되어 (2, ?)가 출력됐다.

(2)에서 Stream.range()가 제공된다는 사실을 확인했지만, 다음과 같이 직접 구현해도 된다.
def range(start: Int, end: Int): Stream[Int] =
  if (start >= end) Stream.empty   
  else Stream.cons(start, range(start + 1, end))
 range(1,3) 의 경우, range의 재귀호출을 따라가면 Stream.cons(1, range(2,3)) == Stream.cons(1, Stream.cons(2, range(3,3))... 가 되어 결국 결국 Stream.cons와 Stream.empty를 사용한 생성 구문이 된다.

call-by-name을 이용한 지연 평가

Stream은 지연 평가를 어떻게 구현했을까? Stream의 소스 코드를 살펴보면 간단하게 확인할 수 있다.
object Stream {
  object cons {
    def apply[A](head : A, tail : => Stream[A]) : Stream[A] {
       // ...
    }
  }
  // ...
}
 cons가 메서드[각주:2]가 아닌 inner object로 구현되어 있다는 사실도 흥미롭다. 내부의 cons object에 apply를 정의해 마치 cons를 메서드처럼 활용했다. 하지만 핵심은 무엇보다도 apply의 인자 tail이 by-name 타입으로 정의되어 있다는 점이다. 따라서 인자 tail은 호출 전까지는 평가되지 않는다.  

  tail의 타입인 => Stream[A]은 Stream 객체를 반환하는 인자 없는 함수 타입, 즉 ()=>Stream과 유사하다고 이해해도 되는데, 함수의 경우 호출하기 전까지는 코드 블럭을 수행하지 않으므로 태생부터 지연 평가에 적합하다는 특성을 갖고 있다. tail의 by-name 타입은 여러가지로 ()=> Stream[A]과 유사하지만, 함수가 아닌 Stream 평가식을 인자로 전달해야 한다는 차이가 있다. Stream 객체를 인자 tail로 전달하는 것은 문제가 없지만, tail에 함수 타입인 ()=>Stream형 인자를 전달하면 type mismatch 에러가 발생한다.  

Stream 활용 예

실제로 Stream을 이용해 작업을 수행해보자. 1~10000의 정수에서 짝수를 작은 순서 대로 5개를 고르는 작업을 Stream을 이용하면 다음과 같이 처리하면 된다.
scala> Stream.range(1,10000)  // 1~10000 범위를 갖는 Stream 생성
res1: scala.collection.immutable.Stream[Int] = Stream(1, ?)

scala> res1.filter( _ % 2 == 0 )   // predicate을 전달하여 짝수인 경우만 필터링
res2: scala.collection.immutable.Stream[Int] = Stream(2, ?)

scala> res2.take(5)    // 앞에서 5개를 취함
res3: scala.collection.immutable.Stream[Int] = Stream(2, ?)

scala> res3.print      // 해당 내용을 출력
2, 4, 6, 8, 10, empty

Stream의 메서드는 List가 제공하는 메서드와 상당히 유사하다. List와 Stream은 모두 LinearSeq를 구현한 immutable한 컬렉션이기 때문이다. 아래 그림은 Scala 컬렉션의 기본적인 구조[각주:3]이다. Immutable/mutable 컬렉션이 모두 공유하는 구조이므로 참고하자.


 List를 활용한 것과 다른 점은 무엇인지 확인하기 위해 Stream 대신 List를 사용해 각 단계를 재현해보자.
scala> List.range(1,10000)
res4: List[Int] = List(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16
, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35
, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54
, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73
, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92
, 93, 94, 95, 96, 97, 98, 99, 100, 101, 102, 103, 104, 105, 106, 107, ... 
시작부터가 Stream과 다르다. 1~10000 범위 전체를 담은 List가 우선 생성된다. 그 다음은 필터링 차례이다.
scala> res4.filter( _ % 2 == 0)
res5: List[Int] = List(2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30,
 32, 34, 36, 38, 40, 42, 44, 46, 48, 50, 52, 54, 56, 58, 60, 62, 64, 66, 68, 
70, 72, 74, 76, 78, 80, 82, 84, 86, 88, 90, 92, 94, 96, 98, 100, 102, 104, ...
이 경우도 1~10000의 범위에 존재하는 짝수로 이루어진 List가 생성된다. 앞에서 고작 5개를 얻기 위해 사전에 너무 많은 작업을 수행했다는 사실을 확인할 수 있다. Stream을 활용한 작업이 훨씬 효율적이다.

지연 평가를 활용하는 Stream은 우선 List가 감당하기 힘든 크기의 수열을 표현할 수 있다.
scala> Stream.range(1, Integer.MAX_VALUE - 1)    
res6: scala.collection.immutable.Stream[Int] = Stream(1, ?)
더 나아가 자연수 전체와 같은 무한 수열 또한 표현 가능하다.
scala> def rangeFrom(x:Int):Stream[Int] = {
     |   Stream.cons(x, rangeFrom(x+1)) }

scala> val naturalNumber = rangeFrom(1)
naturalNumber: Stream[Int] = Stream(1, ?)
다음과 같이 표현할 수도 있다.
scala> val naturalNumber: Stream[Int] = Stream.cons(1, naturalNumber.map(_ + 1))
naturalNumber: Stream[Int] = Stream(1, ?)
Stream을 활용해 푸는 수학 문제가 여럿 있는데, 피보나치 수열[각주:4]의 경우 다음과 같이 비교적 간단하게 표현할 수 있다. Stream의 zip, map 또한 그 결과가 Stream이라는 사실에 유의하며 살펴보면 이해가 빠르다.
scala> val fibonacci: Stream[Int] = Stream.cons(0, Stream.cons(1, 
     |   fibonacci.zip(fibonacci.tail).map(zipped => zipped._1 + zipped._2)))
fibonacci: Stream[Int] = Stream(0, ?)

scala> fibonacci.take(10).print
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, empty
  1. 스터디 멤버 중 아웃사이더 님은 http://blog.outsider.ne.kr에서 왕성한 블로그 활동 중 [본문으로]
  2. Stream.cons는 T #:: Stream[T]와 같이 #:: 로도 표현 가능함 [본문으로]
  3. http://www.scala-lang.org/docu/files/collections-api/collections.html 에서 인용 [본문으로]
  4. 0, 1로 시작하며 앞의 두 수의 합으로 이루어진 수열 [본문으로]
저작자 표시 비영리 변경 금지
신고

Scala로 '라이프 게임' 만들기

Posted 2010.08.29 14:19
스칼라 스터디에 객원 멤버(?)로 참여하고 계신 너구리님의 제안으로 라이프 게임을 실습하게 되었습니다. 이전 개미수열과 마찬가지로 패턴 매칭을 이용하여, 주변 세포의 패턴을 구현하니 보기에도 깔끔하고, 구현도 자연스럽게 진행됐습니다. 프로그래밍에서 반드시 등장하는 분기와 반복이라는 번거로운 과정을 다스릴 신무기가 생긴 기분이랄까요?
 라이프 게임: 글라이더 건

게임 규칙


 위키피디아 링크를 살펴보면 룰이 나와있습니다. 핵심적인 내용만 언급하면 격자 하나를 세포라고 생각하고, 한 세포를 둘러싸고 있는 8개의 주변 세포에 대해 다음과 같은 규칙이 적용됩니다.

  • 죽은 세포의 주변 세포 중 정확히 3개가 살아 있으면 그 세포는 살아난다. (‘태어난다’.) 
  • 살아 있는 세포의 주변 세포 중에 2개나 3개가 살아 있으면, 그 세포는 계속 살아 있는 상태를 유지하고, 이외에는 ‘외로워서’, 또는 ‘숨이 막혀서’ 죽어버린다.

 특정 세포와 그 주변 세포를 나타내는 3x3의 세포 격자를 편의상 "DieHardArea"라고 부르겠습니다. (별다른 의미는 없고, 그냥 제가 작성한 스칼라 객체의 이름이 그렇습니다.)

목표 코드의 형태


 프로그래밍을 할 때 최종 완성된 모습을 (=어떤 형태로 핵심 로직을 실행하고 결과를 얻을지) 미리 그려보는데, '라이프 게임'을 Scala로 구현하려고 보니, 주변 세포에 대한 각각의 패턴이 있어 패턴 매칭 구문으로 해당 패턴을 활용해 세포의 다음 상태를 결정하는 모습이 머리 속에 떠올랐습니다. 이를 scala 코드로 표현하면 다음과 같습니다. 참고로, getDieHardArea(x,y)는 세포 (x,y)를 중심으로 하는 DieHardArea를 반환하는 메서드입니다.
getDieHardArea(x,y) match {
  case 생성패턴 => // 세포가 탄생함
  case 소멸패턴 => // 세포가 죽음
  case 유지패턴 => // 상태를 유지함
}
 먼저 각 패턴의 이름을 만들어 봅니다.'생성패턴', '유지패턴', '소멸 패턴'은 DieHardArea의 패턴을 나타내는 object 입니다. 'XX패턴'은 '패턴'을 상속합니다. 각 object는 내용을 따로 작성할 필요는 없으며, 단순히 패턴 매칭의 결과로만 활용될 예정입니다.
abstract class 패턴
object 생성패턴 extends 패턴
object 소멸패턴 extends 패턴
object 유지패턴 extends 패턴
 이제 목표하는 형태로 패턴 매칭을 완성하기 위해 extractor, 즉 unapply 메서드를 구하면 되겠죠. 그래서 3x3 정수 행렬을 추상화한 DieHardArea 모듈을 다음과 같이 만들기 시작합니다.
object DieHardArea {
   ...
  def unapply(matrix:DieHardArea):Option[패턴] = {
    matrix.amIAlive match {
      case 죽은세포 if (/*이웃세포 3개*/) => Some(생성패턴)
      case 산세포 if(/*이웃세포 2~3개*/) => Some(유지패턴)
      case 산세포 => Some(소멸패턴)
      case _ => None
    }
  }
}

패턴 매칭 코드 작성


 DHA의 unapply메서드가 있으니, 이제 목표했던 패턴 매칭 구문을 바로 작성해 볼 수 있습니다. 특정 셀의 운명을 결정 짓는 메서드니 decideCellDestiny라 이름짓고, 다음과 같이 구현했습니다.
def decideCellDestiny(dha:DieHardArea):Int = {
  dha match {
    case DieHardArea(생성패턴) => Life
    case DieHardArea(유지패턴) => dha.array(1)(1)  //유지
    case DieHardArea(소멸패턴) => Death
    case _ => Death
  }
}

주변 세포의 수 세기


 아직 채워야 할 것이 적잖이 남았지만, 그래도 문제의 핵심적인 부분을 금방 해결한 듯 합니다. 이제 실제로 DHA가 특정한 3x3 정수 배열을 나타내도록 class도 정의해 봅니다.
class DieHardArea(val array:Array[Array[Int]]) {
  require( is3x3Matrix(array));

  // 살아있는 주변 세포 카운트
  def countAliveNeighbor():Int = {
    var count = 0;
    array.foreach(                // DieHardArea 내 살아 있는 세포 수
      count +=  _.filter( _ == Life ).length )

    if( amIAlive ) count -= 1     // 자신은 카운트에서 제외
    count
  }

  // 중앙 세포가 살아있는가?
  def amIAlive():Boolean = {
     ( array(1)(1) == Life )
  }
}
 DHA 클래스 생성시 3x3 정수 배열을 전달하여 멤버로 설정하도록 했습니다. 또. 패턴 매칭 구문에서 주석으로 처리한 주변 세포의 개수를 구하는 메서드도 추가했습니다. countAliveNeighbor 메서드는 DHA내의 모든 살아있는 세포수를 확인한 후, 자신을 제외시키는 방법으로 동작합니다.

 강조 표시된 코드(7,8 번째 줄)는 DHA(DieHardArea)에서 살아있는 세포 수를 세는 부분인데, 약간 생소해 보일 수도 있습니다. 여기서 array는 3x3 크기의 2차원 정수 배열이므로 타입은 Array[Array[Int]] 입니다. 같은 array에 대해 다음 구문을 실행하면 첫째 줄부터 마지막 줄의 크기를 쭈욱~ 출력합니다. 다시 말해, 다음 코드에서 _ 의 타입은 Array[Int] 죠. (array가 배열의 배열이니까요)
array.foreach( println( _.length) )
 제시된 코드는 다음과 같이 각 줄(Array[Int])에 filter를 적용합니다. (Life는 상수로 1을 의미합니다.)
array.foreach(           
  count +=  _.filter( _ == Life ).length
)
 (익숙하지 않으면)혼란을 주는 _를 line으로 치환해 보면 이해가 빠릅니다.
array.foreach(              
  line => {
    val alives = line.filter( _ == Life ).length 
    count +=  alives
  }
)
 위와 같이 함수를 fisrt class value로 이해하고 축약하는 것에 익숙해지면 코드가 매우 간편해 집니다. 참고로, 2차원 정수 배열을 (0이면 □, 그외에는 ■으로 바꾸어) 화면에 출력하는 convertToShapeArray는 다음과 같이 작성할 수 있습니다. _ 등이 익숙치 않으면 분석해 보세요.
def convertToShapeArray(intMatrix:Array[Array[Int]]):Array[Array[Char]] = {
  intMatrix.map{
    _.map {
      case 0 => '□'
      case _ => '■'
}}}
 이제 DHA의 unapply 메서드 내에서 주석으로 처리했던 if 문장을 구현할 수 있습니다.
def unapply(matrix:DieHardArea):Option[패턴] = {
  matrix.amIAlive match {
    case 죽은세포 if (matrix.countAliveNeighbor == 3) => Some(생성패턴)
    case 산세포 if (matrix.countAliveNeighbor ==3 || matrix.countAliveNeighbor == 2) => Some(유지패턴)
    case 산세포 => Some(소멸패턴)
    case _ => None
  }
}

Implcit Type Conversion 적용


 이렇게 해도 충분히 동작하지만, 어쩐지 matrix.countAliveNeighbor ==3 || matrix.countAliveNeighbor == 2과 같은 구문이 눈에 걸립니다. 보기에도 지저분해 보이고 countAliveNeighbor를 두 번 호출하는 것도 안 좋아 보입니다. Range.contains 등을 사용해도 간단히 줄일 수 있지만 고집스럽게 다음과 같이 개선해 봤습니다.  목표는 matrix.countAliveNeighbor.isBetween(1,3) 입니다. 하지만 matrix.countAliveNeighbor의 결과인 Int에는 isBetween과 같은 메서드가 존재하지 않습니다. 이쯤되면 무엇을 하려는지 아시는 분들도 있을 겁니다. 암묵적으로 Int를 사용자 정의 객체 VeryRichInt로 형변환 하려고 합니다(이를 implicit type conversion이라 합니다). 클래스 명에 스며있는 약간의 허풍은 애교로 봐주시길 바랍니다.
class VeryRichInt(val number:Int) {
  def isBetween(from:Int, to:Int):Boolean = {
    if ( from <= number && number <= to) true
    else false
  }
}
 허점은 좀 많지만(from보다 to가 작을 경우 등), isBetween를 담고 있는 VeryRichInt를 작성했습니다. 이제 오브젝트 DHA 내에 다음과 같이 Int를 VeryRichInt로 암묵적 형변환하는 메서드를 만듭니다. 이제 DHA 내에서 Int.isBetween을 하면 Int가 암묵적으로 VeryRichInt로 바뀌어 VeryRichInt.isBetween이 호출될 것입니다.
object DieHardArea {
  ... 
  implicit def int2VeryRichInt(number:Int):VeryRichInt = {
    new VeryRichInt(number)
  }
}

패턴 매칭 마무리


 여기까지 작업하면 기존의 패턴 매칭 구문은 다음과 같이 변경됩니다.
def unapply(matrix:DieHardArea):Option[패턴] = {
  matrix.amIAlive match {
    case 죽은세포 if (matrix.countAliveNeighbor.equals(3)) => Some(생성패턴)
    case 산세포 if( matrix.countAliveNeighbor.isBetween(2,3)) => Some(유지패턴)
    case 산세포 => Some(소멸패턴)
    case _ => None
  }
}
 여기까지 입니다. 코드의 일부만을 놓고 글을 썼지만, 사실 라이프 게임을 완성하기 위한 나머지 코드는 별 내용이 없습니다. 초기값을 2차원 정수 배열로 정의하고, 여기서 DHA를 추출한 뒤, DHA를 이용해 패턴을 분석하고, 결과를 다시 정수 배열에 담아 출력하는 식으로 진행하면 됩니다[각주:1].
  1. 전체 소스는 <a href="http://bit.ly/9rIlnB">이 곳</a>에서 보실 수 있습니다. 퀴즈로 진행한 거라 그렇게 깔끔하지 만은 않습니다. 참고 정도로 활용해 주세요. [본문으로]
저작자 표시 비영리 변경 금지
신고
« PREV : 1 : 2 : 3 : 4 : 5 : ··· : 44 : NEXT »

티스토리 툴바