[프언] #04. Functional Programming

Pure Function

본론으로 들어가기 전에 Pure Function이 뭔지부터 짚고 넘어가도록 합시다. 

int foo(int* a, int* b) {
	*a = *b + 10;
    return *a + 2;
}

int bar(int a, int b) {
	return a + b + 2;
}

위와 같은 C++ 코드에서, foo 함수는 리턴값을 계산하는 것 외에도 a에 저장된 값에 b에 저장된 값과 10을 더하는 역할을 수행합니다. 즉, 함수를 실행하게 되면 a의 값이 바뀌게 됩니다. 반면 bar 함수는 리턴값을 계산하는 것 외에 a와 b에 저장된 값을 바꾸지는 않습니다. 이렇게 현재 상태를 변경시키지 않고 리턴값만 계산하는 함수를 우리는 Pure Function이라고 부릅니다.

 

Functional Programming이란?

Functional Programming은 프로그래밍을 함에 있어 프로그램이 어떤식으로 전개될지에 대한 하나의 패러다임입니다. (Scala가 Functional Programming을 위해 만들어진 프로그래밍 언어입니다.) 이에 대비되는 개념이 바로 Imperative Programming인데요, (Imperative Programming을 위해 만들어진 언어는 C, Python등이 있습니다.) 예시를 통해 더 자세히 알아보겠습니다.

a = 10
b = 15
if (a > b):
	a = a + b
else:
	a = a - b

위 코드는 Imperative Programming의 예시입니다. a와 b를 비교해서 a가 b보다 클 경우 a에 b를 더하고, 그게 아닐 경우 a에 b를 빼는 Python 코드이죠. Imperative Programming에서 프로그램은 a, b와 같은 변수의 상태를 계속 변화시키며 알고리즘을 실행해 나갑니다.

val a = 10
val b = 15
if (a > b) a + b else a - b

위 코드는 Functional Programming의 예시입니다. Scala 코드인데요, 위의 프로그램와 정확히 같은 작업을 수행하죠. 그러나 변수의 값은 변하지 않았죠. 이렇게 Functional Programming에서 프로그램은 변수를 입력받아 어떤 결과를 출력하는 함수의 연속입니다.

Scala에서 여러 변수들을 정의할 때 대부분의 값들이 변경 불가능했던 거, 기억하시나요? 이렇게 Pure Function만을 이용해서 프로그램을 전개하게 되면 변수들의 값을 변경할 필요가 없기 때문입니다.

이렇게 프로그래밍을 하게 되면 여러가지 장점이 있습니다.

val x = 17
// ...
foo (x)

위와 같이 코드를 작성했다고 생각합시다. Scala에서 var로 정의된 값은 Immutable이기 때문에, 중간에 어떠한 코드를 작성했더라도 나중에 x라는 값을 사용할 때 이 값이 17이라는 확신을 가질 수 있겠죠? 만약 이게 아니라면 나중에 x라는 값을 다시 사용할 때 중간에 어떤 코드가 있는지 하나하나 읽어봐야 할 것입니다. 이런 장점은 다른 사람의 코드를 이용하거나 할 때 정말 크게 작용합니다.

 

이런 Functional Progarmming의 또 다른 특징으로는, 반복문의 사용이 의미가 없다는 것인데요.

while (a < 10) {
	// ...
}

어짜피 a의 값이 변하지 않는데 이렇게 반복문을 쓰는게 의미가 없죠. 그래서 Functional하게 프로그래밍을 할 때는 반복문 대신에 Recursion을 사용합니다.

저번 글 마지막에서 Recursion을 사용해 IntList를 정의했었는데요, 그 부분을 보면서 이야기를 계속해보도록 하겠습니다.

sealed trait IntList
case Class Nil() extends IntList
case Class Cons(h: Int, t: IntList) extends IntList

이렇게 Inductive하게 정의된 IntList에 대해서, 이 IntList의 길이를 출력하는 함수를 한번 작성해 보겠습니다.

def length(li: IntList): Int = 
	li match {
		case Nil => 0
		case Cons(h, t) => 1 + length(t)
	}

입력받은 IntList가 빈 List일 경우 0을 출력하고, 그게 아닐 경우 마지막 원소(h)를 제외한 리스트(t)의 길이인 length(t)에 1을 더한 값을 출력하는 함수가 되겠죠. 

그럼 이제 두 IntList를 합치는 함수도 Inductive하게 한번 정의해볼까요?

def concat(fst: IntList, snd: Intlist): IntList = 
	fst match {
		case Nil() => Snd
		case Cons(h, t) => Cons(h, concat(t, snd))
	}

첫 List가 빈 List일 경우 두번째 List를 그대로 출력하고, 그게 아닐 경우 Cons를 이용해 첫 List의 첫 원소만 두번째 List에 합치고 첫번째 List의 첫번째 원소만 제거한 List와 두번째 List를 concat를 이용해 합쳐주는 함수입니다.

 

이번에는 IntList를 정렬하는 함수를 만든다고 한번 가정해 보겠습니다. 먼저, 이미 정렬된 List에 하나의 원소를 끼워넣는 함수인 ins 함수를 정의해보겠습니다. (3, 5, 7과 4를 입력하면 3, 4, 5, 7로 합쳐주는 함수)

def ins(li: IntList, n: Int): IntList = 
	li match {
		case Nil() => Cons(n, Nil())
		case Cons(h, t) => if (n < h) Cons(n, li) else Cons(h, ins(t, n))
	}

이 코드를 좀 풀어서 설명해 보겠습니다. IntList로 3 :: 5:: 7 :: nil 이 주어졌고 Int로 4가 주어졌다고 생각해보겠습니다. 그럼 2번째 case로 들어가게 되는데요. li = Cons(h, t)에서 h = 3, t = 5 :: 7 :: nil이 됩니다. 이제 IntList에 넣고 싶은 Int인 4와 h를 비교하여, h가 더 작으로 if문은 else의 값을 가지게 되고 이 함수의 값은 Cons(3, ins(5 :: 7 :: nil, 4))가 됩니다.

즉, 5 :: 7 :: nil에 4를 넣고 그것을 3과 합친 List가 되는거죠. ins(5 :: 7 :: nil, 4)를 보게되면, 여기에서는 h가 5이고 넣고 싶은 값은 4가 되므로 h가 더 커 if문의 값은 Cons(n, li) 즉 5 :: 7 :: nil과 4를 합친 4 :: 5 :: 7 :: nil이 ins(5 :: 7 :: nil, 4)의 값이 됩니다. 따라서, 이를 3과 합친 3 :: 4 :: 5 :: 7 :: nil이 최종 결과값이 됩니다.

이제 이 ins 함수를 이용하여 IntList를 오름차순으로 정렬하는 함수 sort를 만들 수 있습니다. 

def sort(li: IntList): IntList = 
	li match {
		case Nil() => Nil()
		case Cons(h, t) => ins(sort(t), h)
	}

간단히 설명하자면 리스트의 첫 원소를 h, 첫 원소를 뺀 나머지 부분을 t라고 했을 때, 아까 만들었던 ins 함수를 이용해 sort(t)에 h를 집어넣은 것이라고 보시면 됩니다.

 

Recursion의 문제점

하지만, 이렇게 Recursion을 사용해서 함수를 정의하는 것에도 문제점이 있습니다. 어떤 IntList를 뒤집는 함수는 아래와 같이 만들 수 있는데요,

def reverse(li: IntList): IntList = 
li match {
	case Nil() => li
	case Cons(h, t) => concat(reverse(t), Cons(h, Nil()))
}

리스트의 첫 원소를 h, 첫 원소를 뺀 나머지 부분을 t라고 했을 때, reverse(t) 뒷부분에 h를 집어넣는 역할을 하는 함수입니다.

그런데 이렇게 함수를 만들게 되면 문제가 하나 생깁니다. 바로 비효율성이죠. 프로그램이 돌아갈 때, 하나의 함수가 호출되면 그 함수에 대해서 Stack이 하나씩 생깁니다. (Call Stack이라고 부르죠.) 이 방식으로 reverse 함수를 만들면 길이가 n인 List를 뒤집기 위해서는 이 함수를 n번 호출해야 하고, 총 n개의 Call Stack이 필요합니다.

이런 문제를 해결하기 위해 사용하는 방식이 바로 Tail-Recursion입니다.

def reverse_rec(reversed: IntList, tail: IntList): IntList =
	tail match {
		case Nil() => reversed
		case Cons(h, t) => reverse_rec(Cons(h, reversed), t)
	}

위 함수와의 차이점을 한번 보겠습니다. reverse_rec는 하나의 변수가 더 존재합니다. 만약 2 :: 5 :: 7 :: nil 이라는 List를 뒤집고 싶다고 가정하면, 이 함수의 reversed에는 일단 빈 List인 Nil을 넣고 tail에 2 :: 5 :: 7 :: nil을 집어넣습니다.

그럼 tail이 Nil이 아니기 때문에 2번째 case로 이동하게 되고, h = 2, t = 5 :: 7 :: nil이 되므로 우리가 원하는 값은 reverse_rec(Cons(2, Nil), 5 :: 7 :: nil)이 됩니다. Cons(2, Nil)은 2 :: nil을 의미하므로 reverse_rec(2 :: nil, 5 :: 7 :: nil) 이라고도 할 수 있겠네요.

이제 reverse_rec(2 :: nil, 5 :: 7 :: nil)를 볼까요? 역시 2번째 case가 되므로 우리가 원하는 값은 reverse_rec(Cons(5, 2 :: nil), 7 :: nil)이 됩니다. Cons(5, 2 :: nil)을 다시 적으면 5 :: 2 :: nil이니까 reverse_rec(5 :: 2 :: nil, 7 :: nil)이 됩니다.

뭔가 감이 오시나요? reverse_rec의 첫번째 인수 reversed는 Induction이 진행되면서의 현재 상태를 의미하는 값입니다. 그래서 Tail-Recursion을 사용하지 않았다면 현재 상태를 계산하기 위해 또 다른 Call Stack이 사용될텐데, 그 과정을 줄여주는겁니다. 현재 상태를 저장해서 다음 단계로 넘어간다고 이해하시면 될 듯 합니다.

저는 이 과정을 이해하면서 예전에 배웠던 Dynamic Programming과 유사하다고 느꼈습니다. 관심 있으신 분들은 한번 검색해보는 것도 이해에 도움이 될 듯 하네요.

 

First-Class Function & High-Order Function

Function은 크게 First-Class Function과 High-Order Function으로 분류됩니다. 함수의 입력값이나 리턴값에 또 다른 함수가 포함되어 있을 경우 이 함수를 High-Order Function이라고 부르고, 이 외의 함수들을 First-Class Function이라고 합니다. (사실 대부분의 함수는 First-Class입니다.)

val cube = (x: Int) => x * x * X
val square = (x: Int) => x * x

val sumOf3 = (x: Int, y: Int, z: Int, ftn: Int => Int) =>
	ftn(x) + ftn(y) + ftn(z)

하나의 Int를 입력받아 그 세제곱과 제곱을 출력하는 함수인 cube, square가 정의되어 있습니다. 이 두 함수는 First-Class Function입니다. 그리고 그 밑에 있는 함수는 3개의 Int와 Int에서 Int로의 함수 1개를 입력받는 함수입니다.

즉, sumOf3(1, 2, 3, cube)와 같이 입력하게 되면 $1^3+2^3+3^3$을 계산하여 36을 출력합니다. 이런 함수를 High-Order Function이라고 합니다.

 

가장 대표적인 High-Order Function 중 하나는 바로 Map인데요, 저희가 보통 리스트의 모든 값에 대해 함수를 적용하기 위해서 반복문을 사용하잖아요? 하지만 Functional Programming Language에서는 반복문을 사용하지 않기 때문에 그 대신 Map을 사용하는 것입니다. 아래는 그 예시입니다.

val l = Cons(5, Cons(3, Cons(7, Nil())))	// 5 :: 3 :: 7 :: Nil
def map(ftn: Int => Int, li: IntList): IntList = 
	li match {
		case Nil() => Nil()
		case Cons(h, t) => Cons(ftn(h), map(ftn, t))
	}
println(map(cube, l))	// prints 125 :: 27 :: 343

 

또 다른 예시로는 Fold가 있습니다. 리스트의 모든 값에 대해서 차례대로 함수를 적용하고 싶을 때가 있습니다. 예를 들어 리스트에 모든 값을 곱하고 싶다고 가정하면, 아래와 같이 코드를 작성할 수 있습니다.

val l = Cons(5, Cons(3, Cons(7, Nil())))	// 5 :: 3 :: 7 :: Nil
def mult(a: Int, b: Int) = a * b

def fold(base: Int, ftn: (Int, Int) => Int, li: Intlist): Int =
	li match {
		case Nil() => base
		case Cons(h, t) => fold(ftn(base, h), ftn, t)
	}
println(fold(1, mult, 1))	// prints 105

 

Closure

아까 First-Class Function은 값으로 취급할 수 있다고 했죠? 그 말은, 함수를 작성하는 함수를 만들 수 있다는 뜻이 됩니다. 예시를 한번 볼까요?

def makeAdder(x: Int): Int => Int = {
	def adder(y: Int): Int = x + y
	adder
}

val add1 = makeAdder(1)
println(add1(3))	// prints 4

val add5 = makeAdder(5)
println(add5(3))	// prints 8

makeAdder 함수는 Int 하나를 입력받아서, 그 Int만큼을 더해주는 함수 adder를 출력하는 함수입니다. 즉, makeAdder(1)은 1을 더해주는 함수를 출력하는 함수라고 생각할 수 있습니다.

 

Option Type

어떤 list의 n번째 값을 출력하는 함수를 만든다고 생각해봅시다.

def nth(li: IntList, n: Int): Int =
	li match {
		case Nil() => ???
		case Cons(h, t) => if(n == 0) h else nth(t, n-1)
	}

문제가 하나 생겼습니다. 만약 주어진 List의 길이보다 n이 크게 되면, 언젠가 li = Nil인 경우가 생길텐데, 이 경우는 어떻게 처리해야 할까요? 이 문제를 해결하기 위해서 값을 포함할 수도, 포함하지 않을 수도 있는 type을 하나 정의할 것입니다.

trait OptionalInt
case object None extends OptionalInt
case class Some(n: Int) extends OptionalInt

def nth(li: IntList, n: Int): OptionalInt = 
	li match {
		case Nil() => None
		case Cons(h, t) => if(n == 0) Some(h) else nth(t, n-1)
	}

이렇게 Int일 수도 있고, None일 수도 있는 trait OptionalInt를 만들어서 문제를 해결할 수 있습니다. 그런데 사실, Scala에서는 이렇게 우리가 직접 OptionalInt를 만들어줄 필요가 없습니다.

def nth(li: IntList, n: Int): Option[int] = 
	li match {
		case Nil() => None
		case Cons(h, t) => if(n == 0) Some(h) else nth(t, n-1)
	}

이렇게 Option[Int] 와 같이 적게 되면 바로 위에 적었던 코드의 OptionalInt와 정확히 같은 기능을 하는 값을 사용할 수 있습니다.

감사합니다.

---

이 글은 컴퓨터공학과 학부생이 개인 공부 목적으로 작성한 글이므로, 부정확하거나 틀린 내용이 있을 수 있으니 참고용으로만 봐주시면 좋겠습니다. 레퍼런스 및 글에 대한 기본적인 정보는 이 글을 참고해 주세요.