Functional Programming Principles in Scala - Functions & Evaluation

1.1 Programming Paradigms

Paradigm: In science, a paradigm describes distinct concepts or thought patterns in some scientific discipline.

보통 프로그래밍에서 Paradigm이라고 말하는 것들은 다음과 같다.

  • Imperative Programming
  • Functional Programming
  • Logic Programming

많은 사람들이 또하나의 Paradigm으로 이야기는 하지만, 위에 3가지를 합쳐 한 가지 더 이야기 할 수 있다.

  • Object-orient Programming

Imperative Programming

Imperative Programming은 다음과 같은 성질을 가진다.

  • modifying mutable variables
  • using assignments
  • and control structures such as if-then-else, loops, break, continue, return

imperative programs을 이해하는 방법으로 폰 노이만 컴퓨터를 생각하면 되는데, 다음과 같은 유사점을 볼 수 있다.

Mutable variables = memory cells Variable dereferences = load instructions Variable assignments = store instructions Control structures = jumps

문제는 Scaling up이다. 말로만 개념화하고 있는 프로그램을 어떻게 피하냐이다. 폰 노이만 방식은 데이터 구조를 말(word)로만 개념화하고 있기 때문에 pure imperative programming이 불가능하다.

따라서 collections, polynomials, geometric shapes, strings, documents와 같은 high-level abstraction을 위한 Theory를 만들어야한다.

  • one or more data types
  • operations on these types
  • laws that describe the relationships between values and operations

Theory는 위와 같은 것들이 필요한데 mutation에 대해 설명하지 않는다. 따라서, 아래와 같은 polynomial(다항식) 법칙에 대해mutation이 적용될 경우 theory 가 무너질 수 있다.

(ax + b) + (cx + d) = (a + c)*x + (b + d)

위 상황에서 imperative program을 짠다면,

class Polynomial { double[] coefficient; }  
Polynomial p = ...;  
p.coefficient[0] = 42;

이러할 경우 polynomial 법칙을 유지한 체 모든 사칙연산에 대해 coefficient(계수) 변화를 주어도 theory가 유지되야 하지만, 그러지 않을 수 있다.

따라서, 다음과 같은 것들이 필요하다.

  • concentrate on defining theories for operators expressed as functions,
  • avoid mutations,
  • have powerful ways to abstract and compose functions.

Functional Programming

Functional programming은 다음과 같이 말할 수 있다.

  • In a restricted sense, functional programming (FP) means programming without mutable evariables, assignments, loops, and other imperative control structures.
  • In a wider sense, functional programming means focusing on the functions.
  • In particular, functions can be values that are produced, consumed, and compsed.
  • All this becomes easier in a functional language.

Functional Programming Languages 는 위와 같은 특성을 가진 언어인데, 추가적으로 다음과 같은 성질을 가진다.

  • In particular, functions in a FP language are first-class citizens. This means
    • they can be defined anywhere, including inside other functions
    • like any other value, they can be passed as parameters to funcitons and returned as results
    • as for other values, there exists a set of operators to compose functions

Functional Programming은 다음과 같은 장점을 가진다.

  • simpler reasoning principles
  • better modularity
  • good for exploiting parallelism for multicore and cloud computing

1.2 Elements of Programming

대부분의 Programming 언어는 다음과 같은 것을 제공한다.

  • primitive expressions representing the simplest elements
  • ways to combine expressions
  • ways to abstract expressions, which introduce a name for an expression by which it can then be referred to

Functional programming은 마치 계산기 같은데 REPL(Read-Eval_Print-Loop) 과 같은 shell을 통해 expression을 작성하고 값을 돌려받을 수 있다.

Scala에서는 REPL을 다음과 같이 사용한다.

> scala

sbt 를 설치하였다면, 다음과 같이 실행할 수도 있다.

> sbt console

Evaluation

Evaluation은 우리가 흔히 알고 있는 것처럼 왼쪽에서 오른쪽으로 진행되며, 필요시 괄호 등에 의해 순서가 정의된다.

예를 들어,

(2 * pi) * radius
(2 * 3.14159) * radius
6.28318 * radius  
6.28318 * 10  
62.8318

위와 같이 진행된다고 볼 수 있다.

아래와 같이 Definitions 은 parameter를 가질 수 있다.

scala> def square(x: Double) = x * x  
square: (Double)Double

return type을 정의 할 수도 있는데,

def power(x: Double, y: Int): Double = ...

위와 같이 정의하면 된다.

이렇게 parameter가 정의된 함수도 위에 operator에 대해 적용된 방법과 비슷하게 evaluation된다.

  • Evaluate all function arguments, from left to right
  • Replace the function application by the function's right-hand side, and, at the same time

  • Replace the formal parameters of the function by the actual arguments

    이러한 expression evaluation scheme을 substitution model 이라고 이야기한다. 이 model 근간에 아이디어는 reduce an expression to a value 이다. 이건 side effect가 없는 한 모든 expression에 적용될 수 있다. substitution model은 lambda-calculus로 형식화 할 수 있는데 이건 functional programming에 기본을 제공한다.

    그럼 모든 expression이 value로 reduce되는가? 그렇지 않다.

def loop: Int = loop

위의 경우 loop -> loop -> ... 식으로 계속해서 진행하게 될 것이다.

따라서, evaluation strategy를 변경해야하는데, interpreter는 function arguments를 function을 재작성하는 과정이전에 reduce하지 않도록 바꾸면 된다. 다음 예를 보자

sumOfSquares(3, 2+2)  
square(3) + square(2+2)  
3 * 3 + square(2+2)  
9 + square(2+2)  
9 + (2+2) * (2+2)  
9 + 4 * (2+2)  
9 + 4 * 4

위와 같이 2+2를 최종적으로 진행될때가지 reduce하지 않는다.

Call by Value & Call by Name

evaluation strategy에는 call-by-value와 call-by-name이 있다. 둘다 아래와 같은 경우 동일한 결과를 reduce한다.

  • the reduced expression consist of pure functions
  • both evaluations terminate

call-by-value는 모든 function argument가 한번만 evaluate되는 장점이 있는 가 반면, call-by-name은 function body evaluation에서 사용되지 않은 parameter의 경우 evaluate 되지 않는 장점이 있다.

예를 들어,

def test(x: Int, y: Int) = x * x

위와 같을 경우 CBV와 CBN에 대해 다음의 경우 Evaluation time 차이가 발생할 수 있다. 

test(3+4, 8) // CBV's faster than CBN  
test(7, 3*4) // CBN's faster then CBV

1.3 Evaluation Strategies and Termination

위 두가지 evaluation strategy에 대해 모두 terminate되는 것을 확인할 수 있다. 그럼 termination(종료)가 보장되지 않은 경우 어떻게 될까?

  • If CBV evaluation of an expression e terminates, then CBN evaluation of e terminates, too
  • The other direction is not true

따라서 아래의 경우를 보면,

def first(x: Int, y: Int) =x  
first(1, loop)

CBN의 경우 1로 바로 evaluation이 완료된다. 하지만 CBV의 경우 loop를 reduce하기 위해 계속해서 loop에 빠지게 된다.

Scala's evaluation strategy

Scala는 통상 CBV를 사용한다. 하지만 아래와 같이 =>를 사용하여 CBN으로 강제할 수 있다.

def constOne(x: Int, y: => Int) = 1  
constOne(1+2, loop)

1.4 Conditionals and Value Definitions

Conditional expression

JAVA와 동일하게 Scala에도 if-else conditional expression을 가진다. 하지만, JAVA와 달리 statements가 아닌 expressions를 위해 사용된다.

def abs(x: Int) = if(x >= 0) x else -x

Value Definitions

def의 경우 by-name에 의해 define(정의)되고, val의 경우 by-value에 의해 정의된다.

예를 들어, 

val x = 2  
val y = square(x)

이 경우 y는 square(x)가 아닌 4로 정의되어 진다.

하지만, def의 경우는 아래를 보면 이해할 수 있다.

만약 음과 같은 경우,

def loop: Boolean = loop  

def x = loop // OK  
val x = loop // Error

def의 경우 loop 를 by-name방식으로 정의하기 때문에 문제가 되지 않지만, val의 경우 loop를 reduce후 정의하려하기 때문에 프로그램이 멈추게 된다.

따라서, 만약 and(&&)를 구현할 때 다음과 같이 하여 loop를 해결할 수 도 있다.

def and(x: Boolean, y: => boolean) = if(x) y else false  
and(false, loop)

1.5 Example: square roots with Newton's method

Newton 방식을 이용하여 연차근사법(successive approximations)으로 sqrt를 구해보자.

def sqrt(x: Double): Double = ...

먼저 재귀를 이용해서 function을 구현하면,

def sqrtIter(guess: Double, x: Double): Double =  
    if(isGoodEnough(guess, x)) guess
    else sqrtIter(improve(guess, x), x)

def isGoodEnough(guess: Double, x: Double) =  
    abs(guess * guess - x) < 0.001

def improve(guess: double, x: Double) =  
    (guess + x / guess) / 2

def sqrt(x: Double) = sqrtIter(1.0, x)

위의 sqrtIter는 재귀방법으로 else부분이 자신을 계속해서 호출 한다. 따라서 재귀함수는 Scala에서 explicit return type이 필요하다. (위 경우 Double을 명시(explicit)한 것을 볼 수 있다.) non-recursive function에 대해서는 return type이 optional할 수 있다.

문제는 isGoodEnough 에 대해 매우 작은 숫자에 대해 부정확하며, 큰 수에 대해서는 non-termination할 수 있다.

따라서, 계산의 경우를 줄이기 위해

def isGoodEnough(guess: Double, x: Double) =  
    abs(guess * guess - x) / x < 0.001

로 변경하면 된다.

1.6 Blocks and Lexical Scope

Nested functions

되도록 task별로 작은 function들을 만드는 것은 중요하지만, 위의 예의 경우처럼 sqrt를 위해 isGoodEnough, sqrtIter 등 사용자가 직접 접근할 필요 없는 경우도 있다. sqrt안에 auxciliary function을 두어 해결하는 방안이 있다.

def sqrt(x: Double) = {  
    def sqrtIter(guess: Double, x: Double): Double =
        if(isGoodEnough(guess, x)) guess
        else sqrtIter(improve(guess, x), x)

    def isGoodEnough(guess: Double, x: Double) = 
        abs(guess * guess - x) < 0.001

    def improve(guess: double, x: Double) =
        (guess + x / guess) / 2

    sqrtIter(1.0, x) // return
}

Block Visibility

다른 프로그램 언어와 동일한 Block Scoping을 가진다.

예를 들어,

val x = 0  
def f(y: Int) = y +1  
val result = {  
    val x = f(3) // access to outer f()
    x * x // access to inner x
} + x // access to outer x

주석과 동일한 결과를 준다.

이런 block scoping 을 이용하여 중복(redundant) 사용되는 경우를 줄일 수 있는데, 앞선 sqrt의 경우에 적용이 가능하다.

def sqrt(x: Double) = {  
    def sqrtIter(guess: Double): Double =
        if(isGoodEnough(guess)) guess
        else sqrtIter(improve(guess))

    def isGoodEnough(guess: Double) =
        abs(guess * guess - x) / x < 0.001

    def improve(guess: Double) =
        (guess + x / guess) / 2

    sqrtIter(1.0)
}

Semicolons

Scala 에서는 ;(Semicolon)을 생략해도 되는데, 한줄에 여러 statement를 입력할 때는 아래와 같이 사용하여 구분 가능하다.

val y = x + 1; y * y

하지만, scala 에서 Semicolon을 삭제하여 문제가 생기는 경우가 있는데 다음과 같은 경우이다.

someLongExpression  
+ someLongExpression

위 경우 첫번째 someLongExpression 이 끝난 것으로 인식하여 다음 줄에 에러를 나타낼 수 있다. 이런 경우를 해결하기 위해 다음과 같은 방식을 이용해야한다.

(someLongExpression
+ someLongExpression)

someLongExpression + // complier thinks it is not finished yet  
    someLongExpression

1.7 Tail Recursion

재귀(Recursion)에 대해 다시 돌아보기 위해 아래와 같은 예를 보자. gcd는 최대공약수를 구하는 함수로 아래와 같이 재귀를 이용하여 구현할 수 있다.

def gcd(a: Int, b: Int): Int =  
    if (b == 0) a else gcd(b, a % b)

만약 gcd(14, 21)을 입력하면 최종적으로 gcd(7, 0)까지 함수를 재귀호출하게 된다. 반면 factorial 함수의 경우를 보면 아래와 같다.

def factorial(n: Int): Int =  
    if (n == 0) 1 else n * factorial(n - 1)

예를 들어 factorial(4)을 구하면 아래와 같이 돌아가게 된다.

factorial(4)  
->> 4 * factorial(3)
->> 4 * (3 * factorial(2))
->> 4 * (3 * (2 * factorial(1)))
->> 4 * (3 * (2 * 1 * 1)))

위에서 보듯 gcd와 달리 함수만 재귀호출하는 것이 아닌 추가적인 변수 공간이 필요하다. 하지만 gcd는 본래 함수의 stack frame이 재사용될 수 있다. 이런 경우를 tail recursion 이라고 하며, 이런 호출을 tail-calls라고 한다.

Scala에서는 directly recursive calls 에 대해서만 최적화되어있다. 또한, tail-recursive에 대해 @tailrec annotation을 통해 해결할 수 있다. 하지만 tail recursion이 아닌 경우에 대해 해당 annotation을 사용할 경우 error를 발생할 수 있다.

@tailrec
def gcd(a: Int, b: Int): Int = ...

그럼 factorial()에 대해 tail recursive function을 구현할 수 있을까? 아래와 같이 구현이 가능하다.

def factorial(n: Int): Int = {  
    def loop(acc: Int, n: Int) = {
        if (n == 0) acc
        else loop(acc * n, n - 1)
    }
    loop(1, n)
}

Reference

comments powered by Disqus