Functional Programming Principles in Scala - Higher Order Functions

2.1 - Higher-Order Functions

Functional Language에서는 Functions을 first_class values로 다룬다. 따라서 function을 parameter나 결과값으로 돌려받을 수 있다(return). 이것은 프로그램을 구성할 때 유연한 방법을 제공하는데, function을 위와 같이 다루기위해 사용하는 경우를 higher order functions라고 한다.

아래의 경우를 보자.

// sum of the integers between a and b
def sumInts(a: Int, b: Int): Int =  
    if(a > b) 0 else a + sumIns(a + 1, b)

// sum of the cubes of all the integers between a and b
def cube(x: Int): Int = x * x * x

def sumCubes(a: Int, b: Int): Int =  
    if(a > b) 0 else cube(a) + sumCubes(a + 1, b)

// sum of the factorials of all the integers between a and b
def sumFactorials(a: Int, b: Int): Int =  
    if(a > b) 0 else fact(a) + sumFactorials(a + 1, b)

위 함수들에서 동일한 형태(pattern)이 적용된 함수들을 볼 수 있다. 따라서 아래와 같이 적용하여 재사용이 가능하다.

def sum(f: Int => Int, a: Int, b: Int): Int =  
    if(a > b) 0
    else f(a) + sum(f, a + 1, b)

// sum of all the integers that has been returned from f() between a and b
def sumInts(a: Int, b: Int)            = sum(id, a, b)  
def sumCubes(a: Int, b: Int)        = sum(cube, a, b)  
def sumFactorials(a: Int, b: Int)    = sum(fact, a, b)

// f()s
def id(x: Int): Int = x  
def cube(x: Int): Int = x * x * x  
def fact(x: Int): int = if(x == 0) 1 else fact(x - 1)

Function Types

위에서 보듯 function type을 A => B로 표현이 가능하다. A를 받아 B를 돌려준다는 의미로, Int => Int의 경우 integer를 받아 integer를 돌려준다는 의미이다.

Anonymous Functions

function을 parameter로 사용할 때 일일이 만드는 일은 여간 귀찮은게 아니다. 따라서 이경우 Anonymous Function을 이용하여 해결할 수 있다. 아래 경우를 보면,

def str = "abc"; println(str)

println("abc")

str을 마들어 넣는 것이 아니라 직접 입력하여주었다. 이런 방법으로 function을 parameter 부분에서 직접 정의하는 방식을 Anonymous Function이라고 한다. (이름이 없기때문에...)

따라서, 위의 예를 아래와 같이 작성이 가능하다.

def sumInts(a: Int, b: Int)  = sum(x => x, a, b)  
def sumCubes(a: Int, b: Int) = sum(x => x * x * x, a, b)  
...

여기서 잠깐, 위에서 보았던 sum함수는 linear recursion방식으로 구현이 되어있는데, 이전 포스팅에서 보았던 tail recursion 방식으로 아래와 같이 구현이 가능하다.

def sum(f: Int => Int)(a: Int, b: Int): Int = {  
    @tailRec
    def loop(a: Int, acc: Int): Int = {
        if(a > b) acc
        else loop(a + 1, acc + f(a))
    }
    loop(a, 0)
}

2.2 Currying

Motivation

위에서 봤던 예를 다시 보자.

def sumInts(a: Int, b: Int)            = sum(id, a, b)  
def sumCubes(a: Int, b: Int)        = sum(cube, a, b)  
def sumFactorials(a: Int, b: Int)    = sum(fact, a, b)

만약 여기서 a, b가 변경되지 않은 상태에서 sumInts와 sumCubes를 구한다고하면 어떻게 해야할까? a, b를 parameter에서 제외하는 방법이 없을까? 아래와 같이 작성해보자.

def sum(f: Int => Int): (Int, Int) => Int = {  
    def sumF(a: Int, b: Int): Int =
        if(a > b) 0
        else f(a) + sumF(a + 1, b)
    sumF
}

위와 같이 수정하여 sum 은 이제 sumF라는 다른 함수를 리턴하게 된다. 따라서, 아래와 같이 작성할 수 있다.

def sumInts(a: Int, b: Int)            = sum(x => x)  
def sumCubes(a: Int, b: Int)        = sum(x => x * x * x)  
def sumFactorials(a: Int, b: Int)    = sum(fact) 

sumCubes(1, 10) + sumFactorials(10, 20)

물론 sumInts, sumCubes와 같이 중간 함수(middlemen)을 작성하지 않을 수도 있다.

sum(cube)(1, 10)

Multiple Parameter Lists

함수를 리턴하는 scala의 특성은 functional programming을 하는데 매우 유용하다. 예를 들어, 위의 sum안에 sumF 함수를 생략하여 아래와 같이 작성하는 것도 가능하다.

def sum(f: Int => Int)(a: Int, b: Int): Int =  
    if(a > b) 0 else f(a) + sum(f)(a + 1, b)

이렇게 작성하면, 이전 sumCubes를 sum(cube)와 같이 작성하다. (return type = function) 이런 function definition 스타일을 currying 이라고 말한다.

More Function Types

그럼 아래와 같은 경우 sum의 type은 무엇일까?

def sum(f: Int => Int)(a: Int, b: Int): Int = ...

답은 아래와 같다.

(Int => Int) => (Int, Int) => Int

위와 같이 모든 functional type은 오른쪽 방향으로 연관되어(associate) 진다. 따라서 아래의 경우 동일하다고 말할 수 있다.

Int => Int => Int  
Int => (Int => Int)

Exercise

마지막으로 정리해보자. 일단 sum과 비슷한 product와 이를 이용한 factorial, 그리고 마지막으로 sum과 product 모두 적용할 수 있는 일반화된 함수(mapReduce)를 구현해보자.

def product(f: Int => Int)(a: Int, b: Int): Int =  
    if(a > b) 1
    else f(a) * product(f)(a + 1, b)

def fact(n: Int) = product(x => x)(1, n)  

def mapReduce(f: Int => Int, combine: (Int, Int) => Int, zero: Int)(a: Int, b: Int): Int =  
    if(a > b) zero
    else combine(f(a), mapReduce(f, combine, zero)(a + 1, b))

def product = mapReduce(f, (x, y) => x * y, 1)(a, b)

2.3 Example: Finding Fixed Points

예를 보자. fixed point 란 아래와 같은 function에 대해 x 값을 의미한다.

f(x) = x

이럴 경우 f를 지속적으로 적용하여 fixed point를 구할 수 있다.

x, f(x), f(f(x)), f(f(f(x))), ...

Programmatic Solution

fixed point를 구할 수 있는 solution을 보자.

val tolerance = 0.0001  
def isCloseEnough(x: Double, y: Double) =  
    abs((x - y) / x) / x < tolerance
def fixedPoint(f: Double => Double)(firstGuess: Double) = {  
    def iterate(guess: Double): Double) = {
        val next = f(guess)
        if(isCloseEnough(guess, next)) next
        else iterate(next)
    }
    iterate(firstGuess)
}

위를 이용하여 sqrt를 구할 수 도 있다.

  • sqrt(x) = the number y such that y * y = x
  • sqrt(x) = the number y such that y = x / y
  • Consequently, sqrt(x) is a fixed point of the function (y => x / y)

따라서, 아래와 같이 구현이 된다.

def sqrt(x: Double) = fixedPoint(y => x / y)(1.0)

하지만 실제 위의 코드는 실행 시 1.0 과 2.0 을 번갈아가며 호출 할 뿐 결과를 돌려주지 못한다.

따라서, 이런 경우를 막기위해 다음(successive) 수의 평균을 넣어 해결할 수 있다.

def sqrt(x: Double) = fixedPoint(y => (y + x / y) / 2)(1.0)

이런 기법을 stabilizing by averaging 이라고 이야기하는데 아래와 함수로 표현해놓을 수 있다.

def averageDamp(f: Double => Double)(x: Double) = (x + f(x)) / 2

이를 이용해서 위 sqrt를 재구현하면,

def sqrt(x: Double = fixedPoint(averageDamp(y + x / y))(1.0)

2.4 Scala Syntax Summary

EBNF(Extended Backus-Naur form) 에 따르면 context-free syntax는 다음과 같이 말할 수 있다.

In computer science, Extended Backus?Naur Form (EBNF) is a family of metasyntax notations, any of which can be used to express a context-free grammar. EBNF is used to make a formal description of a formal language which can be a computer programming language. They are extensions of the basic Backus?Naur Form (BNF) metasyntax notation.

  • | denotes an alternative
  • [...] an option (0 or 1)
  • {...} a repetition (0 or more)

Types

Type         = SimpleType | FunctionType  
FunctionType = SimpleType '=>' Type  
             | '(' [Types] ')' '=>' Type
SimpleType     = Ident  
Types         = Type { ',' Type }

Type은 다음과 같다.

  • A numeric type: Int, Double (and Byte, Short, Char, Long, Float)
  • The Boolean type with the values true and false
  • The String type
  • A function type, like Int => Int, (Int, Int) => Int

Expressions

Expr            = InfixExpr | functionExpr  
                | if ('(' Expr ')' Expr else Expr
InfixExpr        = PrefixExpr | InfixExpr Operator InfixExpr  
Operator        = ident  
PrefixExpr        = ['+' | '-' | '!' | '~'] SimpleExpr  
SimpleExpr        = ident | literal | SimpleExpr '.' ident  
                | Block
FunctionExpr    = Bindings '=>' Expr  
Bindings        = ident [':' SimpleType]  
                | '(' [Binding {',' Binding}] ')'
Binding            = ident [':' Type]  
Block            = '{' {Def ':'} Expr '}'

expression은 다음과 같다.

  • An identifier such as x, isGoodEnough
  • A literal, like 0, 1.0, "abc",
  • A function application, like sqrt(x)
  • An operator application, like -x, y + x
  • A selection, like math.abs
  • A conditional expression, like if (x < 0) -x else x
  • A block, like { val x = math.abs(y); x * 2 }
  • An anonymous function, like x => x + 1

Definitions

Def            = FunDef | ValDef  
FunDef        = def ident {'(' [Parameters] ')'}  
              [':' Type] '=' Expr
ValDef        = val ident [':' Type] '=' Expr  
Parameter    = ident ':' [ '=>' ] Type  
Parameters    = Parameter {',' Parameter}

Definition은 다음과 같다.

  • A function definition, like def square(x: Int) = x * x
  • A value definition, like val y = square(2)

Parameter는 다음과 같다.

  • A Call-by-value Parameter, like (x: Int),
  • A Call-by-name Parameter, like (y: => Double)

(둘 차이는 이전 포스팅에서 확인할 수 있다.)

2.5 Functions and Data

function이 어떻게 data structure를 만들고 캡슐화하는지 보자.

Example Rational Numbers We want to design a package for doing rational arithmetic. A rational number x/y is represented by two integers: * its numerator x, * its denominator y

유리수(Rational Numbers)를 계산하는 프로그램을 작성해보자.

def addRationalNumerator(n1: Int, d1: Int, n2: Int, d2: Int): Int  
def addRationalDenominator(n1: Int, d1: Int, n2: Int, d2: Int): Int

하지만 위 함수로는 모든 분자(numerators)와 분모(denominators)를 다루기는 쉽지않다. 따라서, 유리수의 부나조아 분모로 구성된 data structure를 구현하는 것이 더 유리하다.

Classes

Scala에서 class를 통해 해결할 수 있다.

class Rational(x: Int, y: Int) {  
    def numer = x
    def denom = y
}

Class 정의를 통해 두가지 entities를 가질 수 있다.

  • A new type, named Rational
  • A constructor Rational to create elements of this type

다른 언어와 같이 Rational을 여러개 만들어도 다른 namespace에 따로 보관하기 때문에 conflict가 발생하지 않는다.

Objects

class type의 원소들을 object 라고 말한다. 이런 object에 대해 constructor를 이용하여 생성할때 new라는 키워드를 사용한다.

new Rational(1, 2)

JAVA와 동일하게 class의 member에 접근할 때 .을 이용하여 접근한다.

val x = new Rational(1, 2)  
x.numer // 1  
x.denom // 2

Implementing Rational Arithmetic

위 Class를 이용하여 유리수 수학식(Arithmetic)을 만들어보자.

def addRational(r: Rational, s: Rational): Rational =  
    new Rational(
        r.rumer * s.denom + s.numer * r.denom,
        r.denom * s.denom)

def makeString(r: Rational) =  
    r.numer + "/" + r.denom

makeString(addRational(new Rational(1,2), new Rational(2,3))) > 7/6

Methods

위와 같이 function을 따로 만들 수도 있지만, data abstraction 자체에서 동작하게 끔 만들 수도 있다. 이런 function을 method라고 한다.

우리는 위의 예와 같이 add, sum, mul, div, equal, toString 등 기능을 추가 할 수 있다.

따라서, 아래와 같이 class를 변경할 수 있다.

class Rational(x: Int, y: Int) {  
    def numer = x
    def denom = y

    def add(that: Rational) =
        new Rational(
            numer * that.denom + that.numer + denom,
            denom * that.denom)

    def neg: Rational = new Rational(-numer, denom)

    def sub(that: Ration) = add(that.neg)

    override def toString = numer + "/" + denom
}

override는 toString의 경우 기존에 공통으로 정의된 method임으로 재정의를 한다는 것을 의미한다. (Object Class)

2.6 More Fun with Rationals

Data Abstraction

지금까지 보았던 rational numbers는 가장 단순한 형태가 아니었다. 예를들어, 70/49 는 10/7로 표현이 가능하다.

따라서, rational numbers는 아래와 같은 방법으로 simplified할 수 있다.

  • reduce them to their smallest numerator and denominator by dividing both with a divisor.

우리는 위와 같은 과정을 모든 rational operation(method)에 적용할 수 있지만, 쉽게 잊어버릴 수 있다.(?) 따라서, object를 만들 때(construct) 단순화 하는 것이 좋다.

위에서 말하는 divisor는 아래와 같이 최대공약수(gcd: Greatest Common Divisor)를 의미하여 아래와 같이 구할 수 있다. 또한, 이걸 numer 및 denom에 적용하면 된다.

class Rational(x: Int, y: Int) {  
    private def gcd(a: Int, b: Int): Int = if(b == 0) a else gcd(b, a % b)
    private val g = gcd(x, y)
    def numer = x / g
    def denom = y / g

    ...

private은 JAVA나 다른 객체지향언어와 같이 Rational class에서만 접근 가능하다. 또한 gcd를 number과 denom에 적용하여 모든 operation에서 gcd를 호출할 필요가 없다. 물론 g는 생략이 가능하다. 뿐만 아니라, numer과 denom이 자주 호출된다면, def를 val로 수정하면 한번만 계산하게 된다.

class Rational(x: Int, y: Int) {  
    private gcd(a: Int, b: Int) if(b == 0) a else gcd(b, a % b)
    val numer = x / gcd(x, y)
    val denom = y / gcd(x, y)

Clients는 모든 케이스에서 정확히 동일한 행위를 하게되고 clients에 영향 없이 데이터의 적용만 선택할 수 있는 것을 Data Abstration이라고 한다. 이것은 software engineering의 cornerstone이라고 할 수 있다.

다음으로 몇가지 Method를 추가 구현해보자.

def less(that: Rational) = numer * that.denom < that.numer * denom

def max(that: Rational) = if(this.less(that)) that else this

여기서는 이전에는 사용하지 않았던 this를 사용하는데, this는 지금 Method를 호출한 class 자신을 의미한다. (다른 언어와 동일하다.) 물론 less 및 다른 Method에서도 호출하는 class 자신을 의미하기 위해 this를 사용할 수 있으나, 생략한 경우이다. 따라서 아래와 같이 명시해도 상관없다.

def less(that: Rational) =  
    this.numer * that.denom < that.numer * this.denom

Preconditions

아래의 경우를 보자.

val strange = new Rational(1, 0)  
strange.add(strange) // Arithmetic Exception (div by zero)

위의 경우 0으로 분자를 나누려는 경우에 의해 exception을 발생하게 된다. 따라서 아래와 같이 조건을 추가할 수 있다.

class Rational(x: Int, y: Int) {  
    require(y != 0, "denominator must be nonzero")

    ...

Assertions

require이외에 assert라는 것도 있다. Assert 또한 조건과 옵션으로 메세지를 parameter로 받는다. 예를 들어,

val x = sqrt(y)  
assert(x >= 0)

require과 같이 assert도 false에 대해 exception을 throw하지만, require의 경우 IllegalArgumentException이지만, assert의 경우 AssertionError를 throw한다.

이것은 다른 의도를 반영한다. * require is used to enforce a precondition on the caller of a function * assert is used as to check the code of the function itself

Constructors

Scala에서 class는 내부적으로(implicitly) constructor를 가지는데, primary constructor 라고 이야기한다. primary constructor는 아래와 같은 성질을 가진다.
* takes the parameters of the class * and executes all statements in the class body (such as the require)

Rational class에서 만약 1개의 값만 받는다면, 아래와 같이 구현할 수 있다.

class Rational(x: Int, y: Int) {  
    require(y != 0, "denominator must be nonzero")

    def this(x: Int) = this(x, 1)

    ...

2.7 Evaluation and Operators

이전까지 substitution 에 근간한 computation을 function에 대해서만 적용하였다. 그럼 이번엔 class와 object에 적용해보자.

Operators

Rational에 의해 정의된 유리수(rational numbers)는 integer 만큼 natural(?)하다. 하지만 이런 abstraction에 대해 사용자는 눈에 띄는 차이점을 가진다.

  • We write x + y, if x and y are integer, but
  • We write r.add(s) if r and s are rational numbers.

Scala에서는 이런 차이를 없앨 수 있다.

Step 1: Infix Notation

infix operator처럼 method를 호출 할 수 있다. 따라서,

r add s // r.add(s)  
r less s // r.less(s)  
r max s // r.max(s)

Step 2: Relaxed Identifiers

Operator는 identifier에 의해 사용되는데, 아래와 같이 구분할 수 있다.

  • Alphanumeric: starting with a letter, followed by a sequence of letters or numbers
  • Symbolic: starting with an operator symbol, followed by other operator symbols
  • The underscore character '_' counts as a letter
  • Alphanumeric identifiers can also end in an underscore, followed by some operator symbols

예로는 아래와 같다.

x1        *       +?%&        vector_++       counter_-

이를 Rational class에 적용해보자.

...
def < (that: Rational) = numer * that.denom < that.numer * denom // def less

def max(that: Rational) = if (this < that) that else this

def + (that: Rational) =  
    new Rational(
        numer * that.denom + that.numer * denom
        denom * that.denom)

def unary_- : Rational = new Rational(-numer, denom)

def - (that: Rational) = this + -that

...

unary_-의 경우 scala convention에 의해 -that과 같이 -를 직접 붙이는 operator이다. 또한, operator를 정의시 : 이전 space가 필요한 것을 주의하기 바란다.

Reference

comments powered by Disqus