Structural Typing과 Duck Typing

Posted 2011.04.15 16:23

Duck Typing

duck typing에 대한 정의는 duck test를 정의한 다음 문장에 잘 나타난다.
오리처럼 소리내고, 오리처럼 걷는다면 오리라고 불러도 무방하다.
좀 더 구체적으로 정의하면, 해당 객체의 타입을 이용해 객체의 적합성 여부를 검증하기 보다는, 특정 객체가 호출하려는 메세지를 이해할 수만 있다면 사용해도 좋은 객체로 간주하겠다는 의미이다. 위키피디아의 duck typing 설명에 의하면, 다음과 같이 "객체를 구성하는 메서드와 프로퍼티가 객체의 유효 여부를 결정한다"고 정의되어 있다.
an object's current set of methods and properties determines the valid semantics
개인적으로는 Objective-C와 같이 메시지 호출과 객체의 구성 요소(메서드 혹은 프로퍼티)가 동적으로 분리(dynamic dispatching)될 수 있는 언어를 고려하면, "객체가 메시지를 이해할 수 있다면 유효하다고 간주한다"는 말이 좀 더 정확하다고 생각한다. 메세지 디스패칭을  동적으로  정의할 수도 있기 때문이다.

사전 준비

다음과 같이 클래스 Fish, Duck, Person를 정의하자.
class Fish {
 def swim = println("fish: swim")
}

class Duck {
 def quack = println("duck: quaaaack")
 def feathers = println("duck: white feathers")
}

class Person {
 def think = println("person: therefore I am")
 def quack = println("person: speak qua~~ack!")
 def feathers = println("person: wear feather clothing")
}

Structural Typing

Scala에서는 Structural Typing으로 type safe한 방법의 Duck Typing을 지원한다. 다음과 같이 Structural Type을 이용해 DuckLike 타입을 선언하자. DuckLike 타입은 quack, feathers 메서드가 정의된 어떤 타입과도 호환된다.
type DuckLike = { def quack; def feathers } // Structural Typing

def inTheForest( duckLike: DuckLike ) {
  duckLike.quack
  duckLike.feathers
}

/*
scala> inTheForest( new Duck )  
duck: quaaaack
duck: white feathers

scala> inTheForest( new Person )
person: speak qua~~ack!
person: wear feather clothing

scala> inTheForest( new Fish )
<console>:9: error: type mismatch;
 found   : Fish
 required: DuckLike
       inTheForest( new Fish )
                    ^

*/
동적 타입 언어와는 달리 해당 메시지를 이해할 수 있는지 미리 검증한다는 점에서 검증 시점의 차이가 존재한다. Ruby나 Python, Objective-C와 같은 다른 언어에서의 duck typing은 소개한 위키피디아 링크에 나와 있으니 참고하자.
 2010년 가을 무렵에 맹수님이 스칼라 스터디에서 출제했던 순열(permutation) 구하기 문제를 공유[각주:1]합니다. 당시 이 퀴즈를 풀기위해 점심 시간 한 번은 고민하느라, 또 한 번은 문제 푸느라 휙~ 보냈던 기억이 있어 지금도 이 순열 퀴즈를 '밥도둑'이라 부릅니다. 당연한 이야기이지만, 풀이 방법은 다양하므로 본문 내용은 참고로 보시면 됩니다.

문제

주어진 순열 문제는 다음과 같다.
임의의 알파벳 시퀀스를 입력받아서, 해당 알파벳으로 만들 수 있는 순서의 조합을 모두 구한다. 
그리고 결과는 문자열의 오름차순으로 정렬하여 출력한다. 
(예를 들어, "AB", "BA" 가 있는 경우 "AB"가 "BA"보다 먼저 나와야 한다.)

 ex)  "ABC" -> "ABC", "ACB", "BAC", "BCA", "CAB", "CBA"
      "AAB" -> "AAB", "ABA", "BAA"
      "ABA" -> "AAB", "ABA", "BAA"
      "000" -> "000"

목표코드의 형태

우선은 순열로 나타낼 대상 문자열을 List[Char]로 나타내고, List에 permutate라는 메서드를 추가해[각주:2] 다음과 같이 동작할 계획이다.
scala> "AB".toList.permutate
res8: List[List[Char]] = List(List(A, B), List(B, A))

scala> "ABB".toList.permutate
res9: List[List[Char]] = List(List(A, B, B), List(B, A, B), List(B, B, A))
순열은 여러 종류의 문자열이므로 permutate의 결과는 List의 List, 즉 List[List[Char]]이다.

순열 분석

"ABB"를 순열로 표현한다면 첫째 자리에는 3개의 글자 중 중복을 제거한 A 또는 B 두 가지만이 가능하다. 이를 Tree로 나타내면 다음과 같다.

A 혹은 B가 나왔다면 그 다음은 어떤 문자들이 나와야 할까를 고민하며 트리를 작성하다보니, 자식 노드들은 결국 부모 노드의 문자를 제외한 나머지 문자들의 순열이라는 사실을 알 수 있었다. 


다시 말해 1의 영역은 A를 제외한 나머지 원소들의 순열이고, 2의 영역은 B를 제외한 나머지 원소들의 순열이다. 예를 들어 부모 노드에서 A가 나오면 나머지 문자인 B, B로 구성된 순열은 1가지 뿐이다.  전체 순열은 "A + 영역1"과 "B+영역2"로 나타낼 수 있으므로, 이를 통해 순열 문제는 재귀적인 과정으로 풀 수 있다는 예측이 가능하다.

permutate 메서드의 작성

이제 트리를 코드로 표현해야 한다. 트리의 특정 문자열(예시의 경우 List("A","B","B"))의 순열은 결국 자신의 원소들을 중복 제거한 head와 head를 제외한 나머지 원소들의 순열로 표현된다. 이는 대강 다음과 같은 형태로 표현이 가능하다. 
def permutate(list:List[Char]):List[List[Char]] = {

  val heads:List[Char] = list.distinct       // 원소의 중복을 제거하는 distinct 메서드는 제공됨
  
  // heads loop {

    val tail = list.removeFirst( _ == head)  // 일치하는 조건의 원소를 단 하나만 지움(작성 예정)
    permutate(tail).map( head :: _ )         // 자식의 순열에 head를 결합하면 전체 순열이 됨

  // } loop end
완전하지 않은 코드이지만 핵심은 모두 담고 있다.

먼저 조건식 p와 일치하는 원소를 하나만 제거하는 removeFirst()를 작성하자.
def removeFirst[T](p:(T)=> Boolean):List[T] = {
  val index = list.indexWhere(p)
  val (first, _ :: second) = list.splitAt(index)
  first ::: second
}
내용은 간단하다. 조건식 p와 일치[각주:3]하는 원소의 위치를 찾아(indexWhere), 해당 위치를 기준으로 두 리스트로 쪼개고(splitAt), 패턴 매칭[각주:4]을 활용해 조건에 맞는 위치의 원소 하나를 제외한 앞 뒤 List를 합쳤다. 그 결과 찾아낸 원소가 제외된 리스트가 완성된다. 

핵심 메서드인 permutate의 구현은 다음과 같다. 중복 없는 head에 소트를 추가하는 등의 내용이 추가됐고, flatMap 등의 메서드가 머리를 어지럽게 할 수도 있지만  미리 작성해본 permutate 구현과 핵심적인 내용은 같다. 오히려 코드를 참고하지 않고 직접 작성해 보면 이해가 빠를지도 모르겠다.
def permutate(list:List[Char]):List[List[Char]] ={
val heads:List[Char] = list.distinct.sortWith(_ < _)
heads.flatMap( head => {
  val tail = list.removeFirst( _ == head)
  tail match {
	case Nil => List(List(head))
	case _ => permutate(tail).map ( head :: _ )
  }
})
}
마지막으로 List에 permutate 메서드(removeFirst 도 추가하려 한다)를 추가하기 위해 Implicit Type Conversion을 적용해 보자.

Implcit Type Conversion 적용

PermuatbleList 클래스에 순열을 만들기 위해 필요한 기능을 넣고 Implicit Type Conversion을 적용해 List의 기능을 확장할 계획이다. Implicit Type Conversion을 적용하려면 해당하는 implicit 메서드가 현재 scope에서 사용가능해야 한다.
object PermutableList {
  implicit def listToPermutableList(list:List[Char]):PermutableList = {
    new PermutableList(list)
  }
}
implicit 메서드가 위와 같이 선언되어 있을 경우, Implicit Type Conversion이 일어나게 하려면 다음 구문이 필요하다.
import PermutableList._

마무리

Implicit Type Conversion을 적용하고 정리한 최종 코드는 다음과 같다
package lasco.homework.nephilim.permutation

class PermutableList(val list:List[Char]) {
  def permutate():List[List[Char]] ={
    PermutableList.permutate(list)
  }

  def removeFirst[T](p:(T)=> Boolean):List[T] = {
    PermutableList.removeFirst(list)(p)
  }

}

object PermutableList {
  implicit def listToPermutableList(list:List[Char]):PermutableList = {
    new PermutableList(list)
  }

  def removeFirst[T](list:List[T])(p:(T)=> Boolean):List[T] = {
    val index = list.indexWhere(p)
    val (first, _ :: second) = list.splitAt(index)
    first ::: second
  }

  def permutate(list:List[Char]):List[List[Char]] ={
    val heads:List[Char] = list.distinct.sortWith(_ < _)
    heads.flatMap( head => {
      val tail = list.removeFirst( _ == head)
      tail match {
        case Nil => List(List(head))
        case _ => permutate(tail).map ( head :: _ )
      }
    })
  }
}

/*
//@ scala console
import lasco.homework.nephilim.permutation._
import PermutableList._

"A".toList.permutate
res7: List[List[Char]] = List(List(A))

"AB".toList.permutate
res8: List[List[Char]] = List(List(A, B), List(B, A))

"ABB".toList.permutate
res9: List[List[Char]] = List(List(A, B, B), List(B, A, B), List(B, B, A))
*/
  1. 사실 이번에도 묵은지 포스팅임. 본문은 2010년 9월 초에 임시 저장했던 글임. [본문으로]
  2. Implicit Type Conversion을 활용한다는 의미. 이렇게 Implicit Type Conversion은 기존 클래스 혹은 모듈의 기능 확장에 주로 사용됨. [본문으로]
  3. p는 predicate을 나타냄 [본문으로]
  4. val (first, _ :: second) = ... 에는 tuple pattern과 list pattern이 사용됨 [본문으로]
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. 전체 소스는 이 곳에서 보실 수 있습니다. 퀴즈로 진행한 거라 그렇게 깔끔하지 만은 않습니다. 참고 정도로 활용해 주세요. [본문으로]

Scala '읽고 말하기 수열' 실습

Posted 2010.08.25 01:44
 스칼라 스터디 멤버가 읽고 말하기 수열(개미수열)을 실습 퀴즈로 출제했는데, 짧고 재밌는 예제인 듯 하여 공유합니다. 당연한 말이지만, 푸는 방법은 여러 가지가 존재하므로 참고만 하심 되겠습니다.
 
 개미 수열이라고도 알려진 '읽고 말하기(look-and-say) 수열'은, 나열된 숫자를 "숫자 x가 y개"와 같은 식으로 읽으면 수열이 완성됩니다. 예를 들어 [1,1,2] 를 주어진 형식에 맞게 읽으면  숫자 1이 2개, 숫자 2가 1개이지요. 이를 수열로 나타낸 [1,2,2,1]이 개미 수열입니다.

 저는 다음과 같이 작성하였습니다.
// co-ons operator (~:)
// ex) List(1,1,1,2,3) == 1 ~: List(2,3)
object ~: {
  def unapply(list:List[Int]):Option[(Int, List[Int])] = {
    list match {
      case Nil => None;
      case x::xs => Some((x, xs.dropWhile( _ == x )));
    }
  }
}
 
 
object AntSeq {
  def lookAndSay(list:List[Int]):List[Int] = {
    list match {
      case Nil => Nil;
      case x~:xs => x::(list.size-xs.size)::lookAndSay(xs)     //co-ons
    }
  }
}

 우선 정의한 ~: 를 살펴볼 필요가 있습니다. 개미 수열의 단위는 반복되는 특정수의 묶음 입니다. 예를 들어 List(1,1,1,2,2,3)을 놓고 보면, 개미수열을 만들기 위해서는 List(1,1,1), List(2,2), List(3)과 같이 나누어 각 수를 셈할 필요가 있습니다. (적어도 제 머리는 그렇게 수열을 해석하는 것 같습니다.)

 이렇게 "기준 묶음을 뽑아내어 개수를 읽고, 나머지는 같은 요령으로(재귀적으로)처리한다."는 것이 핵심입니다. 기준 묶음과 나머지로 분리하기 위해 리스트를 다뤄본 사람[각주:1]이라면 지겹게 봤을 :: (cons)와 유사한 기호의 ~:를 이름을 살짝 바꾸어(co-ons)라고 정의했습니다.

List(1,1,1,2,2,3) = 1~:List(2,2,3) = 1~:2~:3

 눈으로 보니 co-ons의 정의가 더 간단합니다. 이를 패턴 매칭에 활용하여 개미 수열을 읽으려고 했습니다. 실제로 해당 역할을 하는 단 한 줄(17번째 줄)이 문제 풀이의 핵심이네요.수행 결과는 다음과 같습니다.
scala> import AntSeq._
import AntSeq._
 
scala> lookAndSay(List(1,1,1,2,2,3))
res0: List[Int] = List(1, 3, 2, 2, 3, 1)

 패턴매칭을 잘 활용하면, 자신이 가진 생각을 간단한 기호나 패턴으로 만들고 추상화할 수 있습니다. 그리고 함수형 스타일로 프로그래밍하는데 익숙해지면 문제 해결이 좀 더 빨라집니다. 제 경우 함수형 프로그래밍에 그렇게 익숙한 편도 아닌데, co-ons연산자를 도출하는 과정까지 포함해서 문제 푸는데 걸린 시간은 그렇게 길지 않았습니다. "제 머리가 생각하는 방법과 실제 프로그래밍의 간극이 가까웠기 때문"이라 생각합니다. 만일 for나 중간의 각종 변수를 정의하는 등 imperative style로 풀었다면, (적어도 저의 경우엔) 훨씬 오래 걸렸을 듯합니다. 

 scala가 가진 표현력과 함수형 프로그래밍 스타일[각주:2]의 문제 해결 능력을 맛볼 수 있는 좋은 예제였습니다. 출제해 준 스터디 멤버에게 감사!
  1. lisp 방언이나 hakell 등을 배워본 경험이 있다면 cons가 익숙할 겁니다. 심지어 lisp은 문법 트리조차 cons를 기반으로 표현되는데, 이는 http://en.wikipedia.org/wiki/Homoiconicity를 참고합니다. [본문으로]
  2. 참고로 scala는 functional style과 impertative style을 모두 지원하는 hybrid 언어입니다. [본문으로]

Actor의 react와 receive

Posted 2010.08.08 00:07
Actor의 개념도 생소하지만, 특히 메시지 수신에 사용하는 reactor, receive 메서드는 헷갈리기 쉬운 듯합니다. stackoverflow에 일목요연하게 정리된 답변이 올라와 번역한 뒤 설명을 추가해 봤습니다. 스터디에서 해당 링크를 알려준 명수 맏형께도 감사합니다. 도움이 되었으면 좋겠군요. 본문에서는 존칭을 생략합니다.
 Actor의 기본적인 내용을 알고 있다고 가정하고, 메세지 수신에 사용되는 receive, react 두 개의 메서드를 비교해본다.

First, each actor waiting on receive is occupying a thread. If it never receives anything, that thread will never do anything. An actor on react does not occupy any thread until it receives something. Once it receives something, a thread gets allocated to it, and it is initialized in it.

Now, the initialization part is important. A receiving thread is expected to return something, a reacting thread is not. So the previous stack state at the end of the last react can be, and is, wholly discarded. Not needing to either save or restore the stack state makes the thread faster to start.

There are various performance reasons why you might want one or other. As you know, having too many threads in Java is not a good idea. On the other hand, because you have to attach an actor to a thread before it can react, it is faster to receive a message than react to it. So if you have actors that receive many messages but do very little with it, the additional delay of react might make it too slow for your purposes.
우선 receive로 동작하는 Actor 는 하나의 스레드를 차지한다. 만일 어떠한 메시지도 수신하지 않는다면, 해당 스레드는 아무 것도 하지 않을 것이다. 반면 react에 기반한 Actor는 메시지를 수신하기 전까지는 스레드를 차지하지 않는다. 메시지를 수신하면 비로소 스레드가 할당되고, 초기화를 수행한다.

초기화는 중요한 부분이다. receive를 사용하는 스레드는 무언가를 리턴한다고 가정하지만, react를 사용하는 스레드는 리턴을 아예 하지 않는다고 가정한다.

그렇다면 왜 두 가지 선택 사항이 존재하는가? 여기에는 성능과 관련된 여러 이유가 있다. 알고 있듯이, 자바에서 많은 스레드를 사용하는 것은 좋은 방법이 아니다. 하지만 react 기반의 actor는 react 수행 전 actor를 할당해야 하기 때문에, receive를 사용하는 쪽이 react를 사용하는 것보다 속도가 빠르다. 만일 많은 메세지를 수신하는데, 수신한 메시지를 기반으로 아주 작은 일만을 수행한다면, react에서 발생하는 추가적인 delay는 성능저하를 일으킬 수도 있다. 

 두 메서드는 일단 메서드의 반환 타입부터가 다르다. 특히 react는 다음과 같이 정의되어 있다.
def react(f : scala.PartialFunction[scala.Any, scala.Unit]) : scala.Nothing
 메서드가 Nothing 타입을 반환한다는 사실의 의미를 생각해보자. Nothing은 bottom type이기 때문에 Nothing을 상속한 서브 클래스는 존재할 수 없으며, Nothing 자체를 반환하려고 해도 abstract 클래스이기 때문에 불가능하다. 따라서 react 메서드는 값을 반환할 수 없고, react 내부에서는 예외를 발생시키거나 무한히 실행해야 한다. 애당초 react 메서드는 메서드를 종료하지 못해 해당 스레드를 유지할 수 밖에 없는 불쌍한(?) 운명인 것이다.

다음 코드를 실행해보자. react 종료 후 println("message processed!")는 수행되지 않는다. 물론 react대신 receive를 사용하면 이야기는 달라진다.
import scala.actors.Actor._

actor { 
  loop { 
    react { 
      case any => println(any) 
    } 
    println("message processed!"); 
}}
참고로 Actor.actor 메서드는 Actor를 생성하고 즉시 수행한다. 


R-S 플립플롭 제작 (만능기판)

Posted 2010.07.29 00:38

R-S 플립플롭("뇌를 자극하는 하드웨어 입문" 5장 참고)을 제작해 봤습니다. 혹시나 하드웨어 스터디를 하게 되면 필요한 기초 내용을 남겨 놓습니다.



인두 받침과 인두 팁 크리너는 있어야 하겠더군요. 인두 끝을 자주 닦아줘야 타지 않고 잘 진행됩니다.

만능 기판을 사용할 예정이므로 도선(0.25mm)을 벗겨 사용합니다.

사진처럼 0.25mm도선은 잘 끊어지므로, 힘을 주지 않고 피복을 잡고 뜯어 낸다는 느낌으로 해야 합니다.

하지만 이것도 금새 익숙해 지더군요. 처음에만 몇 번 끊어먹고, 하다보니 거의 실수하지 않고 작업 하는 듯

플립플롭의 결과를 나타낼 2개의 LED입니다.

9V전원과 레귤레이터를 사용하는 "뇌를 자극하는 하드웨어 입문"과는 달리 USB 5V를 사용합니다. 동작 전압으로 바로 전원이 공급되므로 레귤레이터도 필요없고, 또 상당히 안정적인 전원 공급이 가능합니다. USB선을 피복을 벗겨 나오는 선들 중 "검정 + 빨강선"을 이용해 연결부위를 만들어 줍니다.

전원 콘센트는 클램프 전선과 헤더를 연결하여 간단히 만들 수 있습니다.

핀 헤더를 딱 한 줄만 끊어 2pin 전원부를 만듭니다. 살짝 납땜하여 움직이지 않게 합니다.


74LS02 가 들어갈 자리를 만들어 놓습니다. 소켓을 사용하면 나중에 탈착이 용이하며, 열에 약한 칩들을 납땜 후 설치할 수 있다는 장점이 있습니다.

이렇게 소켓과 칩 사이에 앏은 물체를 넣으면 빼는데 도움이 됩니다.

사실 뒷판이 그렇게 깔끔하지 않습니다. 시간을 들이면 더 깔끔해 지겠지만, 머리를 상당히 써야 합니다. 이렇게 간단한 내용으로도 만능 기판 작업은 상당히 번거로워집니다. 에칭 용액을 사용해 기판을 만드는 이유죠.

R-S 플립플롭을 완성 모습입니다. 
스위치는 사진 방향에서 위로 올리면 H신호가, 아래로 내리면 L신호가 됩니다. 
위쪽 스위치가 Reset, 아래쪽 스위치가 Set이구요. 사진은 "Reset 동작"이군요.

다음에는 PCB 기판 제작을 남겨 보겠습니다.

case classes 정리

Posted 2010.07.26 14:29
패턴 매칭을 알기 전에 case class를 알면 편리합니다. case class는 객체를 생성할 때 자주하는 작업들을 미리 제공하는 문법 요소이며, 특히 패턴 매칭과 자주 사용됩니다. 내용이 매우 간단하여 특징을 간략히 알아보는 정도로도 바로 사용할 수 있습니다.

    • 패턴 매칭과 함께 자주 사용되지만, 일반적인 '간편 문법(syntactic sugar)'으로 여러 곳에 사용할 수 있다.

    • class 앞에 case 키워드를 붙이기만 하면 다음의 마법이 일어난다.

      1. companion object를 이용한 factory method 자동 생성됨
      2. 생성자의 인자는 별도의 표기없이 val로 알아서 구현(해당 변수에 대한 읽기 전용 접근자가 생성됨)
      3. toString이 알아서 구현됨
      4. "패턴 매칭"에 사용할 수 있음 - 이건 9장을 예습하면서 확인하길 바람



  • case class를 만들고 1,2,3의 특징을 확인하는 예는 다음을 참고한다.

아직 저항에 붙어 있는 색띠도 더듬더듬하는 제가 하드웨어의 세계에 발을 담그고, 해당 분야의 블로깅을 시작[각주:1]합니다. 뛰어난 분들의 하드웨어 관련 국내외 블로그가 많아 뭔 의미가 있겠냐하는 생각도 들지만, 일단 제 삽질의 역사를 남기고 싶었고, 시작하는 누군가에게 제 시작 과정을 보여준다면 그것도 도움이 될지 모르겠다는 생각에 가뜩이나 산만한 저의 블로깅 카테고리에 또 하나를 추가한거죠.

참고로 여정을 꾸리고 있는 저의 현재 상태입니다.

 1. 하드웨어는 걸음마 수준. 기초 부품도 잘 모릅니다.
 전자기 관련 내용은 중/고등학교 시절의 V=IR, P=IE, 오른손의 법칙 정도 이외에는 기억도 나지 않습니다.
 2. 최근 국내/외 하드웨어 입문서를 몇 권 읽었습니다.
 부족한 하드웨어 지식을 메꾸고자 아마존과 국내 서점을 꽤 오래 방황했습니다. 명저가 참 많더군요. 기회가 닿는대로 차근 차근 소개하겠습니다.
 3. AVR 지식이 아주 약간 있습니다.
 최근 뻔뻔강사님의 AVR 강좌도 들었습니다. 사실  몇 년 전에도 AVR을 공부하다 그만둔 적이 있습니다.
 4. 소프트웨어 개발에 대한 지식이 어느정도 있습니다.
 새로운 프로그래밍 언어에 대한 두려움은 없습니다. 하지만 정작 H/W 분야에서 많이 사용하는 C 개발은 2003년에 잠깐 해본 정도입니다.
 5. 창의력은 나쁘지 않습니다.
 새로운 것을 좋아합니다.
 6. 손재주가 좋지 않습니다.
 저는 이게 장점이라고 생각하는데, 손재주가 좋지 않아 좀 더 정확한 결과를 낼 수 있는 도구 등을 많이 생각해 보는 편입니다.

  저는 긴 호흡으로 이해하며 공부하는 걸 좋아합니다. 아마 블로깅도 그러한 저의 호흡에 맞추어 진행될 듯 합니다. 최근에야 의심하기 시작했는데, 어쩌면 전 yak shaving을 좋아하는 건지도 모르겠습니다. 예를 들면 flip-flop회로를 공부하면서 아무런 근거없이 PCB 기판을 만들어야 한다는 생각을 했고, 며칠동안 개인이 만들 수 있는 PCB 기판 관련 자료를 뒤졌습니다. 그리고 Eagle 캐드를 깔고, AVR에서 사용할 수 있는 8bit 혹은 16bit 메모리로 발전시켜볼까 하는 생각을 하고 있네요. 하지만 아직 모든게 머리 속에만 있으니, 아마 전 오타쿠는 아닐껍니다. 하하하!

  일단 지금 곱씹고 있는 책은 "뇌를 자극하는 하드웨어 입문"입니다. 따로 설명이 필요없을 정도로 아주 친절합니다. 저 같은 하드웨어 관한 기초 지식이 없는 초보자에게 강추하는 책이죠. 같은 내용을 더 어렵게 설명하면 지는 거라는  생각이 있는 저에게는 (1)이 책과 (2)Oreilly 출판의 Make: Electronics는 진정한 승자라 할 수 있겠습니다. 국내 하드웨어 입문서의 자존심 같은 느낌이랄까요. 사실은 책이 처음 나왔을 때 쓰윽 한 번 읽기는 했는데, 그냥 눈으로만 본 것이어서 다시 읽고 있습니다. 지금은 플립플롭(5장)에 관한 내용을 보고 있습니다.


 뭐 이제 시작이라 익숙치 않은게 많아 답답할지도 모르겠습니다. 이해해 주시고, 화이팅 외쳐 주시길...

  1. 사실은 예전부터 로봇이나 전자 부품에 대한 로망이 어느정도 있어 시도는 했습니다. 잘 모르겠기에 조금 쉬어갔고 덕분에 수준은 항상 "hello world"였죠. [본문으로]
 Intellij Scala 플러그인 설정과 HelloWorld 출력은 트랙백을 건 "Outsider님의 블로그"에서 확인하시면 됩니다. 참고로 Intellij 9.0.2를 대상으로 실행하였으며, scala 플러그인을 설치하면 기본적으로 2.8beta1이 설치됩니다.



  • http://www.scala-lang.org/downloads 에서 Scala2.8RC2를 다운로드 합니다. 저는 그냥 zip으로 다운로드 받아 특정 폴더에 풀었습니다.

  • Intellij를 기동하여 Scala Project를 생성하거나, 기존 Scala facet이 적용된 프로젝트를 엽니다.
    • 프로젝트를 우클릭하여 Module Settings를 봅니다.
    • Project Settings > Facet에서 스칼라 컴파일러와 라이브러리 경로를 다음과 같이 압축 해제한 곳의 Scala2.8RC2폴더/lib/XXX.jar로 바꿉니다.

  • 역시 Module Settings 에서 Platform Settings > Global Libraries를 봅니다.

    Scala Facet에서 사용한 scala-compiler.jar, scala-library.jar를 포함하는 Global Library를 새로 추가합니다. 제 경우, 이름은 scala2.8rc2로 정했습니다.


  • 현재 진행 중인 프로젝트의 External Libraries를 다음 그림과 같이 (2)에서 작성한 scala2.8rc global library로 대체 합니다. 



  • 이제 scala 2.8rc2를 이용할 수 있습니다.



ps: 이런, 이 글을 쓰는 사이 2.8rc3이 나왔군요... OTL.
     (이제 슬슬 이클립스로 테스트할 때가 오는 것 같습니다.)









« PREV : 1 : 2 : 3 : 4 : NEXT »

티스토리 툴바