4.1 Functions as Objects

Functions as Objects

지금까지 Scala의 numeric type과 boolean type이 보통 class와 동일하게 적용되는 것을 볼 수 있었다. 그럼 function에 대해서는 어떨까? 사실 Scala에서 function은 object로 다뤄진다. 따라서 function type A => B는 단지 아래와 같은 형태의 축약이라고 볼 수 있다.

trait Function1[A, B] {  
    def apply(x: A): B
}

따라서 function은 apply method를 지닌 object로 볼 수 있다. 또한 Function2, Function3 등 22개 까지 parameter를 받을 수 있는 trait가 있다.

Expansion of Function Values

아래와 같이 anonymous function이 있다면,

(x: Int) => x * x

다음과 같이 해석될 수 있다.

{ class AnonFun expends Function1[Int, Int] {
     def apply(x: Int) = x * x
 }
 new AnonFun
}

또는, anonymous class를 이용하여 더 짧게도 가능하다.

new Function1[Int, Int] {  
    def apply(x: Int) = x * x
}

이번엔 function call에 대해 이야기하면, 예를 들어 f(a, b)를 이용하여 호출 할때, 아래와 같이 확장이된다.

f.apply(a, b)  

따라서, 다음과 같이 된다고 볼 수 있다.

val f = (x: Int) => x * x  
f(7)

val f = new Function1[Int, Int] {  
    def apply(x: Int) = x * x
}
f.apply(7)  

Functions and Methods

method는 아래와 같은데,

def f(x: Int): Boolean = ...  

이 자체는 function value가 아닌지만, Function type이 예상되는 위치에서 사용될 때, 아래와 같이 function value로 자동 변환된다.

(x: Int) => f(x)

또는 아래와 같이 변환된다.

new Function1[Int, Boolean] {  
    def apply(x: Int) = f(x)
}

4.2 Objects Everywhere

Pure Object Orientation

pure object-oriented language는 모든 값이 object인 것을 의미한다. 만약 language가 class에 근간하면, 이것은 모든 값이 class라는 걸 의미한다. Scala는 pure object-oriented language인가? 짐작하기에 몇가지 예외사항이 보인다. primitive types, functions같은 경우에 말이다.

Standard Classes

먼저 primitive type을 보자. 개념적으로, Int 또는 Boolean의 경우 Scala에서 특별히 조치되어지지 않는다. scala package에 다른 class들과 동일하다. 효율성을 위해 Scala compiler는 scala.Int는 32-bit integer로, scala.Boolean은 Java의 boolean으로 해석한다.

Pure Booleans

Boolean type은 JVM의 primitive type boolean과 맵핑되어 지는데, 아래와 같이 class로 정의할 수 있다.

abstract class Boolean {  
    def ifThenElse[T](t: => T, e: => T): T

    def && (x: => Boolean): Boolean = ifThenElse(x, false)
    def || (x: => Boolean): Boolean = ifThenElse(true, x)
    def unary_! :                   = ifThenElse(false, true)

    def == (x: Boolean): Boolean    = ifThenElse(x, x.unary_!)
    def != (x: Boolean): Boolean    = ifThenElse(x.unary_!, x)
    ...
}

ifThenElse를 설명하자면,

if(cond) te else ee  

를 아래와 같이 구현한 것이다.

cond.ifThenElse(te, ee)  

이를 이용하여 위 Method를 다시 보면 이해가 쉽다.

Boolean Constants

그럼 Boolean 에서 사용되는 constant인 true와 false를 보자.

object true extends Boolean {  
    def ifThenElse[T](t: => T, e: => T) = t
}

object false extends Boolean {  
    def ifThenElse[T](t: => T, e: => T) = e
}

그럼 만약 < operator에 대해서도 정의를 하면 어떻게 될까?

class Boolean {  
    ...
    def < (x: Boolean) = ifThenElse(false, x)
}

위와 같이 정의할 수 있다. (true < any 의 경우 false이며, false < any에 대해 any에 따라 달라지기 때문이다.)

The class Int

이번엔 scala.Int에 대해 보도록 하자.

class Int {  
    def + (that: Double): Double
    def + (that: Float): Float
    def + (that: Long): Long
    def + (that: Int): Int           // same for -, *, /, %

    def << (cnt: Int): Int           // same for >>, >>> */

    def & (that: Long): Long
    def & (that: Int): Int           // same for |, ^ */

    def == (that: Double): Boolean
    def == (that: Float): Boolean
    def == (that: Long): Boolean      // same for !=, <, >, <=, >=
    ...
}

그럼 primitive type르 쓰지 않고 모든 것을 class로 구현할 수 있는가?

Exercise

non-negative integer를 의미하는 abstract class Nat를 구현해보자.

abstract class Nat {  
    def isZero: Boolean
    def predecessor: Nat
    def successor: Nat
    def + (that: Nat): Nat
    def - (that: Nat): Nat

여기서 standard numerical class를 사용하지 말고, sub-object와 sub-class를 구현해보자.

object Zero extends Nat  
class Succ(n: Nat) extends Nat  

한가지는 숫자 0을 의미하고 나머지는 양수를 의미한다. 그럼 이제 구현을 해보자

object Zero extends Nat  
    def isZero = true
    def predecessor = throw new Error("0.predecessor")
    def successor = new Succ(this)
    def + (that: Nat)
    def - (that: Nat)

class Succ(n: Nat) extends Nat {  
    def isZero = false
    def predecessor = n
    def successor = new Succ(this)
    ...
}

이쯤 되면 successor가 Zero와 Succ에 대해 동일한 것을 볼 수 있다. 따라서 super-class에 정의하는 것이 유리하다.

abstract class Nat {  
    ...
    def successor = new Succ(this)
    ...
}

나머지도 구현해보자.

object Zero extends Nat {  
    def isZero = true
    def predecessor = throw new Exception("0.predecessor")
    def + (that: Nat) = that
    def - (that: Nat) = if (that.isEmpty) this else throw new Error("negative number")
}

class Succ(n: Nat) extends Nat {  
    def isZero = false
    def predecessor = n
    def + (that: Nat) = new Succ(n + that)
    def - (that: Nat) = if (that.isZero) this else n - that.predecessor
}

이런 것을 전문 용어로 peano number라고 말한다.

4.3 Subtyping and Generics

Polymorphism

이전 포스팅에서 polymorphism에 대해 다뤘었다. 아래와 같이 두가지 원리가 있는데,

• subtyping
• generics

이번에는 이 두가지를 교차해보자 하는데, 두가지 주요 영역이 있다.

• bounds
• variance

Type Bounds

먼저 assertAllPos method를 고려하고자 하는데, assertAllPos는

• takes an IntSet
• returns the IntSet itself if all its element are positive
• throws an exception otherwise

그럼 여기서 assertAllPos를 위한 가장 좋은 type은 무엇일까? 아마도,

def assertAllPos(s: IntSet): IntSet  

대부분의 상황에서 문제가 없을 것이다. 하지만, 아래 상황을 고려하여 좀 더 정확하게(precise) 표현할 수 없을까?

// Empty case
assertAllPos(Empty) = Empty  
assertAllPos(NonEmpty(...)) = NonEmpty(...)  
                              or throw Exception

다시 말해 누군가 assertAllPos는 Empty 빈 set을 위해 Empty를 받고, 비어있지 않은 set을 위해 NonEmpty를 받는 다는 것을 표현하고 싶을 경우 아래와 같이 작성할 수 있다.

def assertAllPos[S <: IntSet](r: S): S = ...  

여기서 <: IntSet은 type parameter S: 의 upper bound를 의미한다. 즉, 여기서 S는 오직 IntSet을 따르는(conform) type에 대해서만 instance화 할 수 있다는 것이다.

일반적으로, 아래와 같이 정리할 수 있다.

• S <: T means: S is a subtype of T
• S >: T means: S is a supertype of T, or T is a subtype of S

Lower Bounds

그럼 lower bound 에 대해서도 다뤄보면,

[ S >: NonEmpty]

여기서 S는 NonEmpty의 supertypes 이상이라는 범위를 내포한다. 따라서 S는 NonEmtpy, IntSet, AnyRef 또는 Any 중 하나를 의미한다.

나중에 lower bound가 유용한 경우를 다눠보록 하겠다.

Mixed Bounds

아래와 같이 섞어서 사용할 수도 있다.

[S >: NonEmpty <: IntSet]

이 경우 S는 NonEmtpy와 IntSet사이가 된다.

Covariance

만약,

NonEmpty <: IntSet  

이라고 할 경우,

List[NonEmpty] <: List[IntSet]  

에 대해서는 어떻게 생각 할 수 있을까? 직관적으로 이해할 수 있듯이 위의 경우가 맞다. 이렇듯 type parameter에 의해 다양한 subtype 관계를 가지기 때문에 covariant라고 이야기하는데, 그럼 모든 type에 대해 그럴까? 아니면 List에 대해서만 그럴까?

Arrays

Array에 대해 간단히 보자면 아래와 같다.

• An array of T elements is written T[] in Java
• In Scala we use parameterized type syntax Array[T] to refer to the same type

Java에서 Array는 covariant이다. 따라서 아래와 같이 말 할 수 있다.

NonEmpty[] <: IntSet[]  

Array Typing Probem

하지만, covariant array type은 문제를 일으킨다. 아래 같이 Java 코드를 보면,

NonEmpty[] a = new NonEmpty[]{new NonEmpty(1, Empty, Empty)}  
IntSet[] b = a  
b[0] = Empty  
NonEmpty s = a[0]  

설명을 하면 위와 같은 경우 IntSet[] b = a를 통해 b가 a와 동일한 memory공간을 바라보는 가운데 b[0] = Empty를 호출하여 0번째 자리가 Empty가 된다. 이 가운데 NonEmpty s = a[0]를 실하게 되어 NonEmpty인 s에 Empty를 할당하게 되는 것이다.

따라서, 이럴 경우를 방지하기 위해 Array에 type tag 같은 것이 필요하다. a라는 array에 NonEmpty라는 type tag가 있어 b[0] = Empty를 할당하려 할 경우 Exception을 발생하면 된다.

위와 동일한 상황을 Scala로 코딩해보자.

val a: Array[NonEmpty] = Array(new NonEmpty(1, Empty, Empty))  
val b: Array[IntSet] = a  
b(0) = Empty  
val s: NonEmpty = a(0)  

위와 같은 코딩에서 Error가 어디서 발생할까? 2번째 라인에서 Error를 발생한다. 왜냐하면 a의 경우 Array[NonEmpty]이고, b는 Array[Intset]이지만, Scala에서 Array는 Non-covariant 이기 때문이다. 따라서, b = a는 Error를 발생한다.

4.4 Variance (Optional)

이전보다 내용이 어려울 수 있어, 구독자에 따라 이 내용을 무시해도 좋다.

Variance

List와 같이 일부 type은 covariant이고 나머지는 그렇지 않다. (Array의 경우) 설명하자면, mutation이 허락되는 type의 경우 covaraint가 아니다. 하지만, 몇가지 조건만 통과한다면 immutation의 type의 경우 covariant이다.

Definition of Variance

만약 C[T]에 대해 A <: B인 A, B가 parameter type일 경우, 일반적으로 아래 3가지 관계를 가진다.

• C[A] <: C[B] 인 경우 C는 covariant이다.
• C[A] >: C[B] 인 경우 C는 contravariant이다.
• C[A]와 C[B] 둘다 다른 object의 subtype이 아닐 경우 C는 nonvariant이다.

Scala는 위와 같은 variance type을 type parameter를 통해 표현한다.

• class C[+A] { ... } 에서 C는 covariant를 의미한다.
• class C[-A] { ... } 에서 C는 contravariant를 의미한다.
• class C[A] { ... } 에서 C는 nonvariant를 의미한다.

Typing Rules for Functions

일반적으로 function type 간 subtype은 아래와 같은 룰을 따른다.

If A2 <: A1 and B1 <: B2, then A1 => B1 <: A2 => B2

따라서 function은 argument type에 대해서는 contravariant하고 result type에 대해서는 covariant하다.

이 결과 Function1 trait의 경우 아래와 같이 변경된 정의를 이끈다.

package scala  
trait Funciton1[-T, +U] {  
    def apply(x: T): U
}

Variance Checks

앞서 Array example을 다시 보자. 이전에서는 covariance 조합에 대해 이야기를 안했는데, 아래와 같이 Array를 class로, 그리고 update를 method로 표현하면,

class Array[+T] {  
    def update(x: T) ...
}

위와 같다 할 수 있는데, 이 경우 문제가 되는 조합은 아래와 같다.

• the covariant type parameter T
• which appears in parameter position of the method update

Scala compiler는 class가 variance annotations과 함께 있을 경우 문제가 되는 조합이 없는지 있는지 아래와 같이 체크한다.

• convariant type parameters can only appear in method results.
• contravariant type parameter can oly appear in method parameters.
• nonvariant type parameter can appear anywhere.

Function Trait Declaration

따라서 이전에 봤던 Function1 trait는 옮바른 경우라고 볼 수 있다.

package scala  
trait Funciton1[-T, +U] {  
    def apply(x: T): U
}

apply의 argument type인 T는 contravariant이며, result type인 U는 covariant이기 때문이다.

Variance and Lists

그럼 이전에 list를 구현했던 예제를 보자. 만약 Nil을 object로 표현하고 싶을 경우(오직 하나로 empty list를 표현하고자 할 경우), 어떻게 변경해야할까?

object Nil extends List[Nothing] {  
    def isEmpty: Bolean = true
    def head: Nothing = ...
}

object test {  
    val x: List[String] = Nil   // error
}

위와 같이 할 경우 String과 Nothing이 연관성이 없기 때문에 error를 발생한다. 따라서 아래와 같이 List trait를 변경해야 한다.

trait List[+T] {  
    def isEmpty: Boolean
    ...
}

때때로 class를 covariant로 만들어야하는 일들이 생길 수 있다. 예를 들어 List에 pretend라는 method를 추가해보자. 생각해보면 아래와 같이 구현할 수 있다.

trait List[+T] {  
    def pretend(elem: T): List[T] = new Cons(elem, this)
}

하지만 위의 코드를 돌아가지 않는다. 아래와 같은 에러를 발생하게 된다.

covariant type T occurs in contravariant position in type T of value elem

이러한 에러를 발생하는 이유는 pretend가 LSP(Liskov Substitution Principle)을 어기기 때문인데, 아래와 같은 예를 보자.

만약 누군가 List[IntSet] xs를 만들었다면, 아래와 같은 코드는 에러를 발생하지 않는다.

xs.pretend(Empty)  

하지만, 같은 동작에 대해 List[NonEmpty]는 에러를 발생한다.

ys.pretend(Empty) // type mismatch  
                  // required: NonEmpty
                  // found: Empty

따라서 List[NonEmpty]는 List[IntSet]의 subtype이 될 수 없다.

Lower Bounds

하지만, 생각해보면 pretend는 중립적인(natural) method로 immutable lists가 가질 수 있는 것이다. 이럴 경우 어떻게 해결해야하는가?

이럴경우 lower bound를 이용하면된다.

def pretend[U >: T](elem: U): List[U] = new Cons(elem, this)  

이럴 경우 variance check를 넘어간다. 이유는

• covariant type parameter가 method type parameter의 lower bound로 나타거나
• contravariant type parameter가 method의 upper bound로 나타날 수 있기 때문이다.

더 자세한 예를 들어 설명하면, 아래와 같은 함수가 있을 경우,

def f(xs: List[NonEmpty], x: Empty) = xs pretend x ?  

돌려주는 return type이 List[IntSet]이 된다. 즉, NonEmpty와 Empty 모두의 supertype인 IntSet을 U로 받기 때문이다.

4.5 Decomposition

만약 수학적(arithmetic) expression을 위한 작은 interpreter를 만들려고 한다고 가정해보자. 간단함을 유지하기 위해 number와 addition만 이용한다고 생각해보자. expression은 class hierarchy를 가지는데, base trait로 Expr과 두개의 subclass인 Number와 Sum을 가진다. expression을 다루기 위해서는 expression의 형태와 그 구성요서를 알아야한다. 아래의 정의를 보자.

trait Expr {  
    def isNumber: Boolean  // classification
    def isSum: Boolean     // classification
    def numValue: Int      // Accessor
    def leftOp: Expr       // Accessor
    def rightOp: Expr      // Accessor
}

class Number(n: Int) extends Expr {  
    def isNumber: Boolean = true
    def isSum: Bollean = false
    def numValue: Int = n
    def leftOp: Expr = throw new Error("Number.leftOp")
    def rightOp: Expr = throw new Error("Number.rightOp")
}

class Sum(e1: Expr, e2: Expr) extends Expr {  
    def isNumber: Boolean = false
    def isSum: Boolean = true
    def numValue: Int = throw new Error("Sum.numValue")
    def leftOp: Expr = e1
    def rightOp: Expr = e2
}

다음은 이런 expression을 evaluation하는 함수 구현을 보자.

def eval(e: Expr): Int = {  
    if (e.isNumber) e.numValue
    else if (e.isSum) eval(e.leftOp) + eval(e.rightOp)
    else throw new Error("Unknown expression " + e)
}

이런 과정을 보면 classification과 accessor부분 구현이 번거롭다는 것을 볼 수 있다. (Number와 Sum에 대해 불필요한 method를 각각 정의해야한다.) 따라서 만약 아래와 같이 새로운 expression 추가가 필요하다면 또다시 모든 class에 대해classification과 accessor에 대한 추가 및 정의가 필요하다.

class Prod(e1: Expr, e2: Expr) extends Expr  // e1 * e2  
class Var(x: String) extends Expr            // Variable 'x'  

Non-Solution: Type Tests and Type Casts

"Hacky" solution으로 type test와 type cast를 사용하면 된다. Scala에서 아래와 같은 method를 사용할 수 있다.

def isInstanceOf[T]: Boolean // checks whether this object's type conforms to 'T'  
def asIntanceOf[T]: T        // treats this obejct as an instance of type 'T'  
                             // throws 'ClassCastException' if it isn't

java의 x instance of T와 (T) x 와 동일한 형태이다. 하지만 Scala에서는 실제 사용을 권장하지 않는다.

이를 적용하여 eval method를 수정해보자.

def eval(e: Expr): Int =  
    if (e.isIntanceOf[Number])
        e.asInstanceOf[Number].numValue
    else if (e.isInstanceOf[Sum])
        eval(e.asInstanceOf[Sum].leftOp) +
        eval(e.asInstanceOf[Sum].rightOp)
    else throw new Error("Unknown expression " + e)

이렇게 할 경우 아래와 같은 장점과 단점을 가진다.

• 장점: classificiation 과 accessor method가 필요없다.
• 단점: 잠재적으로 문제를 가질 수 있다. (Cast 실패 등)

Solution 1: Object-Oriented Decomposition

만약 우리가 원하는 것이 expression을 evaluation하고자 한다면 아래와 같이 정의하여 해결할 수 있다.

trait Expr {  
    def eval: Int
}

class Number(n: Int) extends Expr {  
    def eval: Int = n
}

class Sum(e1: Expr, e2: Expr) extends Expr {  
    def eval: Int = e1.eval + e2.eval
}

하지만 만약 def show: String과 같이 expression을 보여주는 method를 추가할 경우 모든 subclass(ex. Number, Sum)에 대해 정의해줘야한다.

또한, OO Decomposition을 이용할 경우 아래와 같은 rule에 대해 문제가 발생한다.

a * b + a * c -> a * (b + c)  

위는 non-local simplification으로 단일 object의 method로 캡슐화 할 수 없다. 따라서 다른 모든 subclass에 대해 method를 test하고 접근해야한다.

4.6 Pattern Matching

지금까지 한 사항을 정리해보면,

• Classification and access methods: quadratic explosion
• Type tests and casts: unsafe, low-level
• Object-oriented decomposition: does not always work, need to touch all classes to add a new method.

Solution 2: Functional Decomposition with Pattern Matching

새로운 방법의 관점은 test와 accessor functions의 유일한 목적이 construnction process를 반대로(reverse) 하는 것이라고 보는 것이다.

• 어떤 subclass가 사용되었는가?
• constructor의 arguments가 뭔가?

Case Classes

case class 는 class와 달리 앞에 modifier case를 붙이는 것만 다르다.

trait Expr  
case class Number(n: Int) extends Expr  
case class Sum(e1: Expr, e2: Expr) extends Expr  

위를 보면 이전과 흡사해보인다.

이것은 또한 내부적으로 apply method를 포함한 companion object를 정의한다.

object Number {  
    def apply(n: Int) = new Number(n)
}

object Sum {  
    def apply(e1: Expr, e2: Expr) = new Sum(e1, e2)
}

따라서 new Number(1)대신 Number(1)이라고 쓸 수 있다. 간편해졌지만, class가 비어있어 member를 어떻게 접근할까?

Pattern Matching

Pattern Matching은 C/JAVA에서 사용되는 switch를 class hierarchy에 일반화한 것이다. Scala 에서는 match라는 keyword를 사용하여 표현한다. 예를 들어,

def eval(e: Expr): Int = e match {  
    case Number(n) => n
    case sum(e1, e2) => eval(e1) + eval(e2)
}

위와 같이 사용할 수 있는데, 아래와 같은 rule이 있다.

• match is followed by a sequence of cases, pat => expr.
• Each case associates an expression expr with a pattern pat.
• A MatchError exception is thrown if no pattern matches the value of the selector.

동작은 switch / case와 동일하게 동작하는데 아래 동작 예를 보자.

eval(Sum(Number(1), Number(2)))  

위는 아래와 같이 해석된다.

Sum(Number(1), Number(2)) match {  
    case Number(n) => n
    case Sum(e1, e2) => eval(e1) + eval(e2)
}

-> eval(Number(1)) + eval(Number(2))

->
Number(1) match {  
    case Number(n) => n
    case Sum(e1, e2) => eval(e1) + eval(e2)
} + eval(Number(2))

-> 1 + eval(Number(2))

...

Pattern Matching and Methods

물론 evaluation 함수를 base trait에 method로 추가하는 것도 가능하다.

trait Expr {  
    def eval: Int = this match {
        case Number(n) => n
        case Sum(e1, e2) => e1.eval + e2.eval
    }
}

이럴 경우 OO Decomposition에 비해 구현해야하는 method가 줄어든다는 것을 볼 수 있다. (OO Decomposition의 경우 모든 concrete method를 각 subclass에서 구현해야함.)

4.7 Lists

이전에 이미 보았지만 여기서 다시 한번 List를 보자.

val fruit = List("applies", "oranges", "pears")  
val nums  = List(1, 2, 3, 4)  
val diag3 = List(List(1, 0, 0), List(0, 1, 0), List(0, 0, 1))  
val empty = List()  

기본적인 데이터 구조로 위와 같이 생성할 수 있다. List와 Array의 가장 중요한 차이는 아래와 같다.

• Lists are immutable - the elements of a list cannot be changed.
• Lists are recursive, while arrays are flat.

The List Type

Array와 마찬가지로 List는 homogeneous이다. 즉, 모득 element가 동일한 type을 가져야한다.

val fruit: List[String]  
val nums : List[Int]  
val diag3: List[List[Int]]  
val empty: List[Nothing]  
...

Constructors of Lists

모든 list는 아래와 같은 과정으로 생성할 수 있다.

• the empty list Nil
• the contruction operation :: (pronounced cons): x :: xs gives a new list with the first element x, followed by the elements of xs.

예를 들어 아래와 같이 만들 수 있다.

fruit = "applies" :: ("oranges" :: ("pears" :: Nil))  
empty = Nil  

Contruction operation은 Right Associativity로 아래와 같이 해석과정을 가진다.

A :: B :: C is interpered as A :: (B :: C).

Operations on Lists

list에 적용되는 몇가지 operation을 보면,

• head - the first element of the list
• tail - the list composed of all the elements except the first.
• isEmpty - true if the list is empty, false otherwise.

위와 같은 operation은 list의 methods로 정의로 되어있어, 아래와 같이 사용이 가능하다.

fruit.head        == "apple"  
fruit.tail.head    == "orange"  
diag3.head        == List(1, 0, 0)  
empty.head        == throw new NoSuchElementException("head of empty list")  

Sorting Lists

List를 오름차순으로 정렬해보자. 아래와 같이 Insertion Sort를 구현할 수 있다.

def isort(xs: List[Int]): List[Int] = xs match {  
    case List() => List()
    case y :: ys => insert(y, isort(ys))
}

def insert(x: Int, xs: List[Int]): List[Int] = xs match {  
    case List() => List(x)
    case y :: ys => if (x <= y) x :: xs else y :: insert(x, ys)
}

Reference

• Functional Programming Principles in Scala, Coursera