함수형 언어

함수형 패러다임을 따라가는 함수형 언어는 프로그래밍 가능한 모든 자료와 처리를 수학적 함수의 계산으로 취급하고, 모든 프로그래밍은 함수와 불변수(Immutable Variable)로만 나타냅니다.

함수형 언어는 절차 지향, 객체 지향과는 다르게 선언형 프로그램이으로 순서보다는 값과 함수의 실행 여부에만 초점을 둔 패러다임이기 때문입니다. 함수형 언어는 온전한 수학 대수 체계를 받을 수 없어서  람다 대수를 사용하여 구성하였기 때문에, 람다 표현식의 영향을 많이받았습니다.


객체지향 언어의 약한 결합력과 강한 응집력의 단점인 강한 응집력으로 인한 객체 내부에서의 값들과 메소드들 사이에 영향이 높고 이는 곧 코드가 깔끔하지 못한 결과를 가져오는데 함수형은 값들이 불변하고 메소드는 상태를 고려하지 않고 인자 값만을 고려한 설계를 하기에 객체지향의 문제점을 해결할 수 있습니다.


함수형 패러다임에서는 부작용(Side-Effect)를 중요하게 생각하는데, 함수가 받는 인자와 자신의 정보로만 결과 값을 만드는 함수인 순수함수를 사용하지 않고, 사이드 이펙트 함수를 사용하면, 어떠한 상태가 결과값에 영향을 주거나 함수의 리턴값을 제외한 일부 외부 데이터를 변경할 가능성이 있게 되는데, 이러한 함수가 많아지면 추후 디버깅을 하는데 있어 불리함을 가져옵니다. 하지만 모든 고급언어는 어셈블리 - 기계어로 번역되는데 여기서 어셈블리는 순수 사이드 이펙트 함수로 구성됩니다. 그럼에도 불구하고 순수함수를 사용해야하는 이유로는 사이드 이펙트 함수는 예상치 못한 버그가 발생하기 쉬운 구조가 되기 때문입니다.


함수형 언어에서 모든 함수는 일급 객체로 취급됩니다. 여기서 일급 객체란, 다른 객체들에 일반적으로 적용가능한 연산을 모두 지원하는 객체를 의미하는데, 이는 곧 함수가 다른 함수의 인자로 받을 수 있음을 의미합니다. 함수또한 타입이 되는 것이기에 함수의 타입을 인자와 반환 값을 화살표를 통해 나타낼 수 있습니다. (add::int -> int -> int) = (int add(int a, int b))


함수의 타입에서 인자를 일부만 받은 경우, 해당 함수는 남은 인자와 반환 값의 형태로 새로운 함수 타입이 되는데 이를 Currying 이라고 합니다. (int add(1)) = (add::int -> int)


데이터 타입에는 크게 다음 2가지로 구분할 수 있습니다.

 

• 대수적 데이터 타입
• 구조적 타입 시스템

 

대수적 데이터 타입은 다른 타입과의 결합으로 만들어지는 합성 타입을 의미합니다. 대수적 데이터 타입은 다시 크게 2가지로 갈라지는데, 합타입과 곱타입이 있습니다. 합타입은 대표적으로 enum, 곱타입은 대표적으로 Tuple이 있습니다. 대수적 데이터 타입은 참조타입이나 원시 데이터 타입과 동일하게 타입 변수의 이름이 타입을 구별하는 구별자 역할을 합니다. (int a, char* b ... etc) 이러한 방식을 명목적 타입 시스템이라고 합니다.


구조적 타입 시스템은 명목적 타입 시스템과 다르게 타입의 내부 구성이 타입을 구별하는 구별자가 됩니다. 이러한 특성덕에 타입의 합과 타입의 곱으로 집합 연산을 정의할 수 있습니다. (여기서 말하는 집합 연산은 원소의 집합연산이 아닌, 타입 집합의 연산)


구조적 타입 시스템과 비슷한 시스템으로 덕타이핑이 있는데, 다른점은 동적 타입 시스템으로 실시간으로 타입을 체크하는 시스템입니다. (구조적 타입 시스템은 정적 타입 시스템) 대표적으로 JS는 덕타이핑을 사용하고, TS는 구조적 타이핑을 사용합니다.


함수형은 패턴 매칭을 지원하는데, 함수형에서 사용하는 패턴 매칭이란, 원소의 타입이나, 해당 원소의 구조를 지정한 패턴에 부합하는지 검사하여 부합하는 경우 패턴에 대입하여 값을 가져오는 방식으로 사용됩니다. 함수형에서는 원소의 타입을 매개하는 패턴인 타입 패턴 매칭과 원소의 구조를 매개하는 패턴인 디스트럭쳐링을 주로 사용합니다. 이러한 패턴 매칭을 통해 선언형 코드 스타일을 제공할 수 있습니다.


함수가 타입으로 취급되면서 생길 수 있는 여러 케이스 중 하나를 해결하는 방법으로 클로저가 있습니다. 예를 들어 함수 내에서 또다른 함수를 정의하는 경우, 내부함수는 외부함수의 내부 값을 사용할 수 있습니다. 이때, 외부함수의 리턴값이 내부함수에 의해서 나오는 것이라면 외부함수는 리턴값만 남기고 나머지를 폐기해버리는데 이 경우 리턴 값을 구하는 과정에서 폐기된 상위 변수를 사용한다면 오류가 발생합니다. 따라서, 폐기하기전에 내부함수의 종속된 범위는 모두 백업을 하고 재사용할 때, 내부함수와 백업한 범위를 같이 사용하여 값을 반환할 수 있게됩니다.

 

함수형 언어에서 리스트를 사용하면 가장 자주 쓰이는 고차함수로 map, filter, reduce가 있습니다.

먼저 map은 map(f(x), (y), Domain)의 형태로 작성됩니다. 즉, Domain의 모든 원소 x는 y로 치환되어 결과를 도출해냅니다. ([1,2,3].map(x) => (x+1) = [2,3,4])

filter는 filter(f(x), {y(:bool), Domain)의 형태로 작성되고, Domain의 모든 원소 x는 논리값 y를 토대로 y가 true인 값 x만 남겨서 Codomain을 채우는 함수입니다. ([1,2,3].filter(x) => (x % 2 == 1) = [1,3])

reduce는 reduce(f(x_acc, x), {y_acc}, acc_init, Domain)의 형태로 작성되고, Domain의 모든 원소 x는 사용자가 정의한 연산을 거쳐 y_acc에 누산되고, 최종 누산 결과 y_acc를 반환합니다. ([1,2,3].reduce(acc, x) => (acc + x), 1 = 7)

 

함수형 패러다임은 다른 패러다임과 다르게 선언적이며, 특정한 상태를 가지지않고 모든 변수가 불변이며 모든 함수는 순수함수로 작성합니다. 이는 프로그래밍 적으로 장점을 가져올 수 있지만, 사이드 이펙트 함수를 필연적으로 써야하는 상황이 생기는 경우 이를 해결하기가 어렵습니다. 예를들어 print 함수의 경우는 IO()의 결과에 따라 값이 변할 수 있으므로 순수함수라고 볼 수 없습니다. 이를 해결하기 위해 모나드 기법을 사용합니다.

 

모나드 기법은 사이드 이펙트 함수 및 특정 상태를 지닌 채로 프로그램이 지속되는 방법입니다. 리턴 값에 출력 결과와 출력 상태를 둘다 반환하고 이를 받으면서 연속적으로 함수 합성을 수행하여 문제를 해결합니다. (print의 경우 Monad(print)::{IO(), UNIT} 으로 상태는 IO(), 출력은 싱글톤 void인 UNIT으로 반환하여 순수성을 유지합니다.)

 

Monad(M)은 Functor의 일종으로, unit::T->M<T> 함수와 flat::M<M<T>>->M<T> 함수를 가지는 Functor를 의미합니다. 이를 설명하기 위해 먼저 Functor부터 서술하겠습니다.

 

Functor(lift)는 타입 생성자 F의 일종으로 함수 타입 lift<F>::(A->B) -> (F(A)->F(B))를 가지는 타입 생성자입니다. 이것이 성립하기 위해서는 2가지 조건이 필요한데, 먼저 함수의 항등성 보존입니다. 위 Functor에서 인자로 (A->A), 타입으로 F(A)가 주어 졌을 때, F(A)가 반환되어야합니다. 두번째로 함수의 합성관계 보존입니다. f::A->B & B->C이면, h= g ∘ f::A->C 일때, lift<F>(h) = lift<F>(g) ∘  lift<F>(f)::(A->C) -> (F(A)->F(C)) 이어야 합니다.

 

결국 Functor는 일변수 함수를 인자로 받아 결과 값을 만드는 타입 생성자인데, 만일 다변수함수인 f:A -> B -> C가 인자로 오게 된다면, lift의 타입은 lift_2D<F>(f)::F<A> -> F<B> -> F<F<C>>가 됩니다. 따라서, n차 변수 함수를 lift 할 때에는 n번 lift를 호출하게 되고 총 반환은 F가 n번 겹친 형태가 됩니다. (F<A> -> F<B> -> F<F<C>>에서 h(a) -> F<C>, g(b) -> C 로 리턴값을 구하고 이를 겹쳐서 lift<F>(h)(Fa) 생성. 이 형태는 편미분에서 각 변수를 미적분 하는 동안 다른 변수는 상수 취급과 유사) 

 

앞서 Monad는 unit과 flat 함수를 가진다고 서술했습니다. 그럼 unit과 flat의 정의에 대해서 서술하겠습니다.

 

unit 함수는 타입 T를 받으면, 모나드 타입 M으로 씌운 타입 M<T>를 리턴하는 함수입니다. 반대로 flat 함수는 M<M<T>> 타입의 정보를 일부 뭉개서 M<T> 타입으로 만들어 리턴하는 함수입니다.

 

단, unit 함수와 flat 함수는 다음 4가지 조건을 만족해야합니다. 먼저 조건에서 f::A -> B로 정의하고 모든 lift와 unit, flat 함수는 <M>을 다루는 함수라고 정의합니다.

 

1. lift(f)::M<A> -> M<B>, unit::A -> M<A> 일때,  unit을 한 후, lift(f)의 결과와 f를 한후, unit을 한 결과가 같아야합니다.
2. flat::M<M<A>> -> M<A>, lift(lift(f))::M<M<A>> -> M<M<B>> 일때, flat을 한후, lift(f)의 결과와 lift(lift(f))를 한후, flat의 결과가 같아야합니다.
3. lift(unit)::M<A> -> M<M<A>> 일때, M<A>를 lift(unit)한 결과와 M<A>를 unit한 결과가 달라도 괜찮지만 이 결과들을 flat했을때 결과는 서로 같아야하고, 이 결과값은 처음의 M<A>와 같아야합니다.
4. lift(flat)::M<M<M<A>>> -> M<M<A>> 일때, M<M<M<A>>>의 lift(flat)한 결과와 M<M<M<A>>>의 flat 결과가 달라도 괜찮지만 이 결과값을 flat 했을 때의 결과는 서로 같아야합니다. 

unit함수와 flat함수를 가볍게 정리하자면, unit 함수에서 M<A>는 A의 확장된 타입이기 때문에, ( A ⊂ M<A> ) 업캐스팅과 유사하다고 볼 수 있고, flat함수는 일반적으로는 값이 일부 뭉개져서 변환되겠지만, M<A>에서 A로 손실없이 변환 가능하다면 이는 다운캐스팅과 유사하다고 볼 수 있습니다.

 

모나드 기법으로 제네릭 함수 두개의 합성을 해결하였으나, 구체적으로 f::A->M<B> 와 g::B->M<C>를 합성하는 경우, f의 치역과 g의 정의역이 다르기 때문에 합성이 불가능하지만, flatlift를 사용하면 이를 합성할 수 있습니다. flatlift는 flat과 lift의 합성으로, lift(g)::M<B> -> M<M<C>>, flat::M<M<C>> -> M<C>로 정의됩니다. 따라서, flatlift(g) = M<B> -> M<C>가 됩니다. 이 타입은 f를 합성할 수 있으므로, flatlift::(A -> M<B>) -> M<A> -> M<B> 로 정의됩니다. flatlift는 앞서 언급한 lift와 마찬가지로 다변수인자를 받을 수 있으므로 flatlift2D로 정의할 수 있습니다.

 

Monad의 확장된 개념으로 Applicative Functor가 있는데, Applicative Functor는 pure::T -> M<T> 와 apply::M<A -> B> -> M<A> -> M<B> 함수를 가지는 펑터입니다. 여기서 apply 함수는 2가지 규칙이 존재하는데 다음과 같습니다.

 

1. apply(f, x)에서 f(x) = x 인 항등 함수 id인 경우, apply(id, x) = x가 성립해야합니다.
2. apply(f, apply(g,x)) = f(g(x)) = apply(apply(apply( ∘, f), g), x) 가 성립해야합니다.

Unit(Wrapper)의 반대역할로 Unwrap 함수도 존재하는데, M<T> -> T로 타입을 구체화하는 역할을 수행합니다.