이색적인 프로그래밍 아이디어, 3부 (이펙트 시스템)
이색적인 프로그래밍 아이디어 시리즈를 이어 가며, 이번에는 이펙트라는 주제를 살펴보겠습니다. 약한 형태의 이펙트 태깅은 여러 주류 프로그래밍 언어에서 찾아볼 수 있지만, 표면 구문에서 이펙트의 영역을 정의하고 표시하는 구문을 갖춘 완전한 이펙트 시스템으로 프로그래밍하는 것은 여전히 언어 설계에서 열려 있는 분야입니다.
먼저 이펙트가 무엇을 뜻하는지 정의해야 합니다. 일상적인 용법에는 정확한 정의가 없는 경우가 많지만 함수형 프로그래밍 분야에는 정확한 정의가 있으므로, 여기서는 함수형 프로그래밍에서 흔히 쓰는 정의를 따르겠습니다. 우선 순수 함수란 반환값이 전적으로 입력에 의해 결정되고, 단순히 값을 반환하는 것 외에는 관찰 가능한 이펙트가 전혀 없는 코드 단위입니다. 순수 함수는 프로그래밍에서 수학의 함수처럼 동작하는 함수입니다. 예를 들어 Python 코드에서는 f라는 “함수“를 다음과 같이 나타냅니다:
def f(x):
return x**2
전통적으로 수학이라고 불리는 의사 코드에서는 함수 f를 다음과 같이 나타냅니다:
f(x)=x2
이 정의에는 언급해 둘 미묘한 점이 몇 가지 있습니다. 첫 번째는 이펙트를 분석할 때의 관점 문제입니다. 이 Python 함수는 일련의 바이트코드로 컴파일되는데, 이 바이트코드는 스택 변수를 조작하고, 힙에 메가바이트 단위의 데이터를 malloc하고, 가비지 컬렉터를 호출하고, CPU 레지스터에 수십만 개의 값을 넣었다 뺐다 합니다. 이 모든 것은 PyObject 구조체 안에서 임의 크기 정수의 거듭제곱을 계산하는 일에 해당합니다. 이 모든 것은 하부 구현의 관점에서 보면 매우 이펙트가 많은 일이지만, 일반적인 언어 안에서는 이러한 내부 동작을 관찰할 수 없습니다.
순수 함수형 프로그래밍의 핵심 아이디어는 프로그래밍이 필연적으로 순수한 로직과 이펙트가 있는(때로는 비순수하다고 불리는) 로직 둘 다로 이루어진다는 것입니다. 또한 이펙트가 있는 로직 단위를 구별할 수 있고, 프로그램 합성에 대해 더 잘 추론하기 위해 이러한 이펙트의 종류를 분류할 수 있는 것이 표면 언어의 유용한 속성이라고 가정합니다.
이에 대한 대안은 대부분의 언어에서 볼 수 있는 모델로, 모든 로직이 거대한 이펙트 수프 속에 뒤섞여 있으며, 어떤 코드가 이펙트(메모리 할당, 사이드 채널 등)를 수행할 수 있고 어떤 로직이 그럴 수 없는지를 구별하는 일은 프로그래머의 직관과 내부 멘탈 모델에 의존합니다. 이펙트 시스템 연구는 근본적으로 올바른 프로그램 이펙트 합성에 대한 우리의 직관을, 컴파일러가 우리 대신 추론할 수 있고 개발자 도구와 편리하게 상호작용할 수 있는 형식 모델로 정립하는 것에 관한 것입니다.
Idris, Haskell, F* 같은 함수형 언어와 몇몇 다른 연구용 언어는 지난 10년의 대부분 동안 이 설계 공간을 탐구해 왔습니다. 모나드 같은 개념은 순수한 로직과 비순수한 로직을 구분하기 위해 초기에 탐구되었지만, 그 모델이 유용성 측면에서 한계에 부딪히면서 최근 몇 년 사이 관심이 줄었습니다. 가장 활발하게 탐구되는 분야는 대수적 이펙트 핸들러라고 알려진 것으로, 런타임 오버헤드를 전혀 도입하지 않으면서도 이펙트가 있는 로직을 검사하는 다루기 쉬운 추론 알고리즘을 허용합니다.
이 모델을 사용하는 주류 언어는 없지만, Microsoft Research 연구소에서 나온 Koka라는 학술용 언어가 이러한 아이디어를 가장 발전된 형태로 구현하고 있습니다. 제가 아는 한 이 언어를 실제로 무언가에 사용하는 사람은 없지만, 내려받을 수 있고 이러한 아이디어를 탐구하는 데 꽤 쓸 만합니다. 모든 예제 코드는 Koka로 작성하겠습니다.
Koka에서는 이펙트가 전혀 없음을 total 이펙트로 나타냅니다. 함수 f를 계산한 결과는 오직 입력의 제곱을 반환하는 것뿐입니다.
fun f( x : int ) : total int
{
return pow(x,2)
}
그러나 화면에서 읽어 들이는 함수처럼 이펙트가 있는 함수는 console 이펙트를 태그로 붙여 작성할 수 있습니다. 그러면 이 함수의 본문에서 println 같은 함수를 호출할 수 있으며, 이러한 함수 호출의 결과는 그 함수를 호출하는 함수의 시그니처에 반영됩니다. 반환 타입 ()는 유닛 타입을 나타내며, C 계열 언어에서는 void라고 부릅니다.
fun main() : console ()
{
println("I can write to the screen!");
}
표준 라이브러리가 제공하는 println 함수의 타입 시그니처에도 효과가 들어 있다는 점은 짚고 넘어갈 만합니다. 그 시그니처는 다음과 같습니다.
fun println( s : string ) : console () 따라서 컴파일러는 이 함수에 딸린 효과를 알고 있습니다. 그래서 다음 함수는 애너테이션 없이 작성할 수 있으며, 사용자가 시그니처를 지정하지 않아도 효과 추론이 알맞은 시그니처를 도출합니다. 반환 타입도 일반적인 타입 추론 기법으로 추론할 수 있습니다.
fun main()
{
println("I can write to the screen!");
}
예외
입력/출력 외에, 대부분의 프로그래밍에서 볼 수 있는 가장 흔한 유형의 효과는 실패할 수 있는 능력입니다. 보통 언어 런타임은 이 기능을 예외로 구현합니다. 예외는 예외를 처리하는 로직으로 비지역 점프를 하거나, 호출 스택을 되감고 실행을 중단합니다. 이것은 분명히 모델링할 수 있는 효과이며, 다른 언어의 검사 예외(checked exception)와 비슷한 인터페이스를 만들 수 있습니다.
throw 함수는 error 합 타입을 받아서 exn으로 표시되는 효과를 낳습니다. 한편 try 함수는 exn 타입을 낳는 함수를 받아서 error를 반환합니다. error 타입은 Error이거나, 실행에 성공한 경우 Ok입니다.
type error<a> {
Error( exception : exception )
Ok( result : a )
}
오류 처리 함수는 exn 효과가 붙은 함수를 받아서 처리하는 고차 함수로 작성할 수 있습니다.
fun throw( err : error<a> ) : exn a
fun try( action : () -> <exn|e> a ) : e error<a>
fun maybe( t : error<a> ) : maybe<a>
예를 들어 0으로 나누기를 처리하는 고전적인 사례를 다룰 수 있습니다. 이때 산술 오류를 maybe 합 타입으로 감싸고, 0인 경우는 nothing으로 처리합니다.
fun divide(a : int, b : int) : exn int {
match(b) {
0 -> throw("Division by zero");
_ -> return (a / b);
}
}
fun safeDiv(a : int, b : int) : maybe<int>
{
maybe( try { divide(a,b) } );
}
컴파일러 내부에서 패턴 매칭을 정교화(elaboration)하는 과정에서 불완전한 패턴을 찾아낼 수 있으며, 런타임에 실패할 수 있는 패턴 매칭의 타입에 예외를 추가해야 한다고 추론할 수 있습니다.
fun unjust( m : maybe<a> ) : exn a {
match(m) {
Just(x) -> x
}
}
반면 완전한 패턴 매칭은 전함수(total)로 도출됩니다.
fun unmaybe( m : maybe<a>, default : a ) : total a {
match(m) {
Just(x) -> x
Nothing -> default
}
}
비종료는 효과입니다
위에서 내린 효과의 정의에 따르면, 함수를 호출했을 때 관찰할 수 있는 결과는 결괏값을 반환하는 것뿐입니다. 따라서 값을 계산하지 않고 무한히 실행되는 함수는 함수가 아니며, 발산(divergence)이라는 부수 효과를 가집니다. 주어진 함수가 전함수인지 판별하는 일은 일반적으로 쉽지 않습니다. 하지만 각각 독립적으로 전함수인 로직 단위들을 합성한 함수는 그 자체로도 전함수일 수밖에 없습니다.
호출 지점을 분석하는 것만으로 전함수가 아님을 곧바로 알아낼 수 있는 단순한 경우도 많습니다. 예를 들어 다음 함수는 자기 자신을 재귀 호출하므로 자동으로 div 효과가 붙습니다.
fun forever(f) {
f();
forever(f);
}
forever 컴비네이터의 추론된 타입은 다음과 같습니다.
forever: forall<a,b,e> (() -> <div|e> a) -> <div|e> b
효과 검사기는 상호 재귀 정의에 걸쳐서도 전함수 여부를 도출할 수 있습니다. 따라서 서로를 호출하는 함수들은 모두 전함수이거나, 합성했을 때 발산할 가능성이 있는 것으로 취급됩니다.
fun f1() : div int
{
return 1 + f2();
}
fun f2() : div int
{
return 2 + f1();
}
효과의 행
개별 효과에 각각 따로 태그를 붙이는 것도 그 자체로 유용합니다. 하지만 대규모 프로그래밍에서는 로직을 서로 합성해야 하므로 효과의 조합을 합성하는 방법이 필요합니다. Koka에서는 이를 효과의 행(row)으로 나타냅니다. 이는 꺾쇠괄호 문법으로 표기합니다.
<e1, e2, ...>
수학의 언어로 말하면 효과 행은 가환 모노이드입니다. 연산으로는 파이프로 표기하는 확장이 있고, 효과가 없음을 나타내는 항등원(total 또는 <>)이 있습니다. 확장 연산이 교환 법칙과 결합 법칙을 만족하므로 시그니처 안에서 효과를 표준적인 순서로 정렬할 수 있습니다.
<e1> | e2 = <e1,e2>
<e1,e2> | e3 = <e1,e2,e3>
<e1> | <> = <e1>
<e1> | e1 = <e1>
<e2, e1> = <e1,e2>
예를 들어 비결정성 효과 ndet를 가진 난수 생성기를 호출하면서, exn 효과로 예외도 발생시키는 함수를 작성할 수 있습니다. 이제 두 효과를 합성하면 행 <ndet, exn>이 됩니다.
fun multiEffect() : <ndet, exn> ()
{
val n = srandom-int()
throw("I raise an exception");
}
효과 시스템은 발산하거나 예외를 던질 수 있는 함수를 다음 별칭을 사용해 pure로 표기합니다.
alias pure = <exn,div>
효과에 대한 Haskell의 접근 방식에는 단 하나의 불투명한 IO 모나드가 있으며, 콘솔 입력, 출력 또는 시스템 연산을 수행할 수 있는 모든 동작이 이 모나드에 속합니다. 그러나 더 풍부한 효과 시스템을 갖춘 언어는 IO 계층을 훨씬 더 세분화하여 모델링할 수 있습니다. 예를 들어 Koka는 표현력이 증가하는 순서로 다음과 같은 세 단계의 IO 효과를 정의합니다.
// Functions that perform arbitrary IO operations
// but are terminating without raising exceptions
alias io-total = <ndet,console,net,file,ui,st<global>>
// Functions that perform arbitrary IO operations
// but raise no exceptions
alias io-noexn = <div,io-total>
// Functions that perform arbitrary IO operations.
alias io = <exn,io-noexn>
참조의 수명과 경계
상태는 프로그래밍의 필수적인 부분이며, 본질적으로 효과를 수반합니다. 중요한 점은 주어진 스코프 안에서 메모리나 로직의 어느 영역에 쓸 수 있는지를 다룰 수 있어야 한다는 것입니다. 이를 위해서는 주어진 메모리 영역에 대한 효과를 그 효과의 매개변수로 지칭할 수 있어야 합니다. 이 언어에서는 괄호 표기법을 사용하여 효과를 힙 매개변수로 매개변수화할 수 있습니다. 표준 라이브러리는 Core 상태 효과 세 가지를 제공합니다:
alloc<h>- 힙 매개변수 h에 대해 참조를 할당하는 alloc 효과입니다.read<h>- 힙 매개변수 h의 참조에서 읽는 read 효과입니다.write<h>- 힙 매개변수 h의 참조에 쓰는 write 효과입니다.
참조를 생성하고 조작하기 위한 Core 함수는 세 가지입니다:
fun ref( value : a ) : (alloc<h>) ref<h,a>
fun set( ref : ref<h,a>, assigned : a ) : (write<h>) ()
fun (!)( ref : ref<h,a> ) : <read<h>|e> a
내부 참조가 관찰 가능한 형태로 새어 나가지 않는 함수는, 참조의 타입이 인자 타입이나 반환 타입 어디에도 나타나지 않는다면 total로 표시할 수 있습니다. 따라서 지역 상태를 순수 함수 안에 포함시킬 수 있습니다. 예를 들어 다음 함수는 내부적으로 가변 참조를 사용하지만 total입니다:
fun localState() : total int
{
val z = ref(0);
set(z, 10);
set(z, 20);
return (!z);
}
컴파일러 자체도 참조를 다루기 위한 어느 정도의 문법적 설탕을 제공합니다. val은 불변의 이름 있는 변수를 도입하지만, var 구문을 사용하면 가변 참조를 간결하게 정의할 수 있습니다.
val z = ref(0)
var z : int = 0 // Identical to above
변수는 := 연산자를 사용하여 갱신할 수 있습니다.
set(z, 10)
z := 10 // Identical to above
따라서 다음의 카운터 함수와 같은 유사 명령형 로직을 작성할 수 있습니다:
fun bottlesOfBeer() {
var i := 0;
while { i >= 99 } {
println(i)
i := i + 1
}
}
참조는 함수의 인자로 전달할 수 있고 힙 매개변수는 타입 변수로 정량화할 수 있으므로, 어떤 타입의 참조에도 동작하는 제네릭 함수를 작성할 수 있습니다.
fun add-refs( a : ref<h,int>, b : ref<h,int> ) : st<h> int {
a := 10
b := 20
(!a + !b)
}
읽기, 쓰기, 할당 능력의 조합은 표준 라이브러리에서 상태를 가진 계산을 나타내기 위해 st라는 이름이 붙어 있습니다.
alias st<h> = <read<h>,write<h>,alloc<h>>
이러한 종류의 효과 시스템을 사용하여 참조를 추적하면, 읽기 장벽과 쓰기 장벽을 가진 로직 영역을 표시하고 기계적으로 검사 가능한 방식으로 변경을 순수 로직과 분리하는 강력한 추상화를 얻을 수 있습니다. 컴파일 시점에 이러한 정보를 가진 미래의 언어라면, 이를 활용하여 순수 로직의 경계에 대한 보장을 유지하면서도 지역적 변경 영역을 더 효율적인 코드로 컴파일할 수 있을 것입니다.
효과 다형성
마지막으로, 효과를 수반하거나 순수한 인자를 받을 수 있고 그 효과를 출력 타입의 일부로 포함하는 고차 함수도 작성할 수 있기를 원합니다. 흔히 쓰이는 map 함수는 리스트를 받아 주어진 함수 인자를 리스트의 각 원소에 적용하는 고차 함수입니다. 효과 시스템이 있는 언어에서 이를 작성하려면 함수 인자의 효과를 타입 변수(이 예에서는 e)로 지칭하고 이를 map의 출력 타입에 사용할 수 있어야 합니다.
fun map( xs : list<a>, f : (a) -> e b ) : e list<b>
리스트에 total인 산술 함수를 적용하는 경우에는 단순히 int의 리스트를 돌려받습니다. 반면 IO의 경우에는 각 정수를 콘솔에 개별적으로 출력하는 println 같은 함수를 적용할 수 있으며, 그 결과 타입은 unit의 리스트입니다. 두 사용 사례 모두 추상적인 효과 타입 변수에 대한 이러한 매개변수 다형성을 사용하는 동일한 함수로 포괄됩니다.
val e1 = map([1,2,3,4], println); // console list<()>
val e2 = map([1,2,3,4], dbl); // list<int>
fun dbl(x : int) : total int
{
return (x+x)
}
효과 시스템 연구는 아직 초기 단계입니다. 앞으로의 연구를 위해 제가 강조하고 싶은 핵심은, 효과 모델링의 사용성과 성능을 개선하려는 언어가 시스템 전체를 라이브러리에 떠넘기는 것만으로는 그 목표를 이룰 수 없다는 점입니다. 언어 차원에서 통합된 효과 타입을 지원해야 하고, 표면 언어에서도 하위 표현식에 레이블을 붙이고 타입 추론에 힌트를 줄 수 있는 어노테이션을 지원해야 합니다. Haskell, Scala 등에서 이를 구현하려는 많은 접근 방식은 바로 이 단순한 사실 때문에 사용성이 떨어질 수밖에 없습니다.
타입을 추론하는 데 그치지 않고, 컴파일러가 그냥 버리는 정적 정보를 코드 위에 한층 더 풍부하게 제공하면 완전히 새로운 수준의 정적 분석 도구를 만들 수 있습니다. 이는 매우 흥미로운 기법이며, 앞으로 10년 동안 더 많은 결실을 맺기를 바랍니다.