F#에서 재귀함수와 불변성 (Immutability)에 관한 쉬운 문제

학교 기초 컴파일러 수업에서 F#언어를 다루고 과제가 나왔다.

module P2

// (Note) Do NOT change the definition of the following type and exception.

type Exp =

    Num of int

  | Add of Exp * Exp

  | Sub of Exp * Exp

  | Mul of Exp * Exp

  | Div of Exp * Exp

exception DivByZero

/// Return the integer value represented by the expression 'e'. If there is any

/// division-by-zero case, raise the 'DivByZero' exception.

let rec eval (e: Exp) : int =

 

이런 문제가 있어서, eval함수를 채우는게 과제 중 하나이다.

  | Div (exp1, exp2) -> if eval exp2 = 0 then raise DivByZero else eval exp1 / eval exp2

 

이런식으로 코드를 짰었는데 PS하는 사람들 입장에서는 당연한 의문점이 드는 코드인데,

eval 안에서 eval exp2을 2번 부르기 때문에 이론상 2^n의 시간복잡도를 가진 코드이다.

 

그래서 let tmp = eval exp2 로 정의하고 tmp에 대해서 비교를 하면, 괜찮을 것으로 추측된다.

근데 나는 저런식으로 tmp를 선언해서 계산하는게 크게 달라지지 않을 것이라고 생각했는데, 그 이유가 어차피 tmp의 statement는 재귀적으로 정의되어 있기 때문에 tmp의 실제 값을 호출하려면 statement들을 타고타고 들어가야 해서 선언 과정에서도 함수가 한번 불리고, 사용과정에서 한번 더 불릴 것으로 생각했다.

 

그래서 확인해보기 위해 아래와 같은 F# 코드를 짰다.

let rec func (n: int) : int =

    if n = 1 then

        printfn "HELLO WORLD"

        1

    else

        let tmp = func(n-1)

        //func (n-1) + func (n-1)

        //2 * tmp

printfn "%d" (func 4)

 

func(n-1) + func(n-1)을 할 때와, 2*tmp할 때 "HELLO WOLRD"가 몇번 출력되는 지를 살펴봤다.

전자는 2^n번 출력되는 것이 맞고, 후자는 1번 출력됐다.

 

let rec func (n: int) : int =

    if n = 1 then

        printfn "HELLO WORLD"

        1

    else

        let tmp = func(n-1)

        tmp + tmp

printfn "%d" (func 4)

이렇게 해도 1번 실행된다.

 

그래서 왜 그런지 생각을 좀 해봤는데, F#은 기본적으로 불변성을 가지고 있다. 즉 가변적으로 정의해주지 않는 한 한번 정의된 변수(이자 함수이자 statement)는 값이 바뀌지 않는다는 점이다. 그래서 한번 부르고 그 이후로 사실상 부를 필요가 없다. (저장되어 있는 값을 가져오기 때문에) 

 

강의자료 내용을 첨부한다.... 
강의자료는 Tree로 되어 있는데 사실 재귀 statement 자체가 tree라 동일할 것이다.

 

결론적으로 F#은 불변적 성질을 가짐으로써 코드 자체를 엄밀하고 빠르게 사용할 수 있다는 것이다. 
불변적 성질이 없다면 시간이 터지고 말 것...