효과(effect)를 표면 문법에서 표기하고 합성하는 전체 효과 시스템의 개념을 소개하고, Koka를 통해 예외, 비종료, 효과 행, 참조 수명 및 효과 다형성을 살펴본다.
Continuing on in our series on exotic programming ideas, we’re going to explore the topic of effects. Weak forms of effect tagging are found in many mainstream programming languages, however the use of programming with whole effect systems that define syntax for defining and marking regions of effects in the surface syntax is still an open area in language design.
먼저, 효과(effect)라는 말로 무엇을 의미하는지 정의해야 한다. 여기서는 함수형 프로그래밍 분야에서 흔히 쓰는 정의를 채택하겠다. 일상적 용법은 종종 정확하지 않지만, 이 정의는 정밀하기 때문이다. 순수 함수(pure function)란 반환값이 전적으로 입력에 의해 결정되고, 값을 반환하는 것 외에는 관측 가능한 효과가 전혀 없는 코드 단위다. 순수 함수는 프로그래밍에서 수학의 함수처럼 동작하는 함수다. 예를 들어 Python 코드에서 “함수” f를 다음처럼 표기하자:
def f(x):
return x**2
전통적으로 수학이라 부르는 의사코드에서는 함수 f를 다음처럼 표기한다:
f(x)=x2
이 정의에는 언급할 만한 미묘한 점이 몇 가지 있다. 첫 번째는 효과를 분석할 때의 관점 문제다. 이 Python 함수는 바이트코드 시퀀스로 컴파일되어 스택 변수를 조작하고, 힙에 메가바이트 단위의 데이터를 malloc하고, 가비지 컬렉터를 호출하며, CPU 레지스터에 수십만 개의 값을 넣었다 빼는 작업을 한다. 이 모든 것은 PyObject 구조체 안에서 임의 크기 정수의 거듭제곱을 계산하는 것과 대응된다. 구현 관점에서는 매우 효과적(effectful)이지만, 정상적인 언어 수준에서는 이런 내부 동작을 관측할 수 없다.
순수 함수형 프로그래밍의 큰 아이디어는 프로그래밍이 필연적으로 순수 로직과 효과를 갖는(때로는 불순하다고도 하는) 로직을 모두 포함한다는 점이다. 더 나아가, 표면 언어가 효과를 갖는 로직 단위를 구분할 수 있고, 프로그램 합성을 더 잘 추론하기 위해 효과의 종류를 분류할 수 있다면 유용하다고 본다.
대안은 대부분의 언어에서 볼 수 있는 모델이다. 거기서는 모든 로직이 거대한 효과의 수프에 뒤섞여 있고, 어떤 코드가 효과(메모리 할당, 사이드 채널 등)를 수행할 수 있는지, 어떤 로직은 수행할 수 없는지를 구분하는 일을 프로그래머의 직관과 머릿속 모델에 의존한다. 효과 시스템 연구는 본질적으로 프로그램 효과 합성에 대한 올바른 직관을 정형 모델로 정식화(canonising)하여, 컴파일러가 우리 대신 추론할 수 있게 하고 개발자 도구와도 인체공학적으로 상호작용하게 만드는 일이다.
Idris, Haskell, F* 같은 함수형 언어와 몇몇 연구용 언어들은 지난 10년의 대부분 동안 이 설계 공간을 탐구해 왔다. 모나드 같은 개념은 순수/불순 로직의 경계를 표시하기 위한 초기 탐색이었지만, 유용성 측면에서 한계에 부딪히면서 최근에는 관심이 줄었다. 현재 가장 활발히 탐구되는 분야는 대수적 효과 핸들러(algebraic effect handlers)로, 런타임 오버헤드를 도입하지 않으면서도 효과 로직을 검사하기 위한 다루기 쉬운 추론 알고리즘을 허용한다.
이 모델을 쓰는 주류 언어는 없지만, Microsoft Research의 학술 언어 Koka가 이런 아이디어를 가장 성숙하게 구현한 사례를 보여준다. 내가 보기엔 이 언어를 실제로 무언가에 쓰는 사람은 없는 듯하지만, 다운로드할 수 있고 아이디어를 탐구하기에는 꽤 쓸 만하다. 이 글의 모든 예제 코드는 Koka로 작성한다.
Koka에서 어떤 효과도 없음을 나타내는 표기는 효과 total이다. 함수 f를 계산한 결과는 단지 입력의 제곱을 반환하는 것뿐이다.
fun f( x : int ) : total int
{
return pow(x,2)
}
하지만 화면에서 입력을 읽는 것 같은 효과 함수를 작성할 수도 있는데, 이 경우 console 효과로 태그한다. 그러면 이 함수의 본문은 println 같은 함수를 호출할 수 있고, 이런 함수 호출의 결과 효과는 그것을 호출하는 함수의 시그니처에 반영된다. 반환 타입 ()는 C 계열 언어에서 void라고 부르는 유닛(unit) 타입을 뜻한다.
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!");
}
입출력 외에, 대부분의 프로그래밍에서 가장 흔한 효과는 실패할 수 있다는 능력이다. 보통 언어 런타임은 예외(exception)로 이 기능을 구현하는데, 예외는 이를 처리하는 로직으로 비지역 점프를 하거나 호출 스택을 풀면서 중단한다. 이는 분명 모델링할 수 있는 효과이며, 다른 언어의 검사 예외(checked exceptions)와 비슷한 인터페이스를 만들 수 있다.
throw 함수는 오류 합 타입(sum type)을 받아 exn으로 표시되는 효과를 발생시킨다. 반면 try 함수는 exn 타입의 결과를 내는 함수를 소비하고 오류를 반환한다. 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)이라는 부작용을 가진다. 주어진 함수가 total인지(항상 종료하며 값을 반환하는지) 판별하는 것은 일반적으로 쉽지 않지만, 서로 독립적으로 모두 total인 로직 단위들의 합성으로 이뤄진 함수는 그 자체도 total이어야 한다.
호출 지점(call-site) 분석만으로도 비-total임을 즉시 알 수 있는 단순한 경우가 많다. 예를 들어 다음 함수는 자기 자신을 재귀 호출하므로 자동으로 div 효과가 붙는다.
fun forever(f) {
f();
forever(f);
}
forever 조합자의 추론된 타입은 다음과 같다:
forever: forall<a,b,e> (() -> <div|e> a) -> <div|e> b
효과 검사기는 상호 재귀 정의에서도 total성을 추론할 수 있다. 따라서 서로를 호출하는 함수들은 합성 시 전체가 완전히 total이거나, 또는 발산 가능성이 있어야 한다.
fun f1() : div int
{
return 1 + f2();
}
fun f2() : div int
{
return 2 + f1();
}
개별 효과를 독립적으로 태그하는 것만으로도 유용하지만, 큰 규모의 프로그래밍에서는 로직을 합성해야 하므로 효과의 조합을 합성(synthesize)하는 방법이 필요하다. Koka에서는 이를 효과 행(row of effects)으로 표현한다. 이는 다음의 꺾쇠 괄호 문법으로 표기한다:
<e1, e2, ...>
수학의 언어로 말하면, 효과 행은 파이프(|)로 표시되는 확장 연산과 효과 부재를 나타내는 항등원(total 또는 <>)을 가진 가환 모노이드(commutative monoid)다. 확장 연산의 가환성과 결합성은 시그니처에서 효과의 정준적 순서를 가능하게 한다.
<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는 표현력이 증가하는 방향으로 다음과 같은 3단계 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>
상태(state)는 프로그래밍의 본질적인 부분이며, 본질적으로 효과적이다. 중요한 점은, 주어진 스코프 안에서 메모리나 로직의 어떤 영역에 쓸 수 있는지를 말할 수 있기를 원한다는 것이다. 이를 위해 특정 메모리 영역에 대한 효과를 효과의 매개변수로 참조할 수 있어야 한다. 이 언어는 괄호 표기를 사용해 힙 매개변수(heap parameter)로 효과를 매개변수화할 수 있게 해준다. 표준 라이브러리가 제공하는 핵심 상태 효과는 세 가지다:
alloc<h> - 힙 매개변수 h에 대해 참조를 할당하는 alloc 효과.read<h> - 힙 매개변수 h의 참조로부터 읽는 read 효과.write<h> - 힙 매개변수 h의 참조에 쓰는 write 효과.참조를 생성하고 조작하기 위한 핵심 함수는 세 가지다:
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로 표시될 수 있다. 따라서 지역 상태(local state)는 순수 함수 안에 내장될 수 있다. 예컨대 다음 함수는 내부적으로 가변 참조를 사용하지만 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>>
이런 종류의 효과 시스템으로 참조를 추적하면, 읽기 장벽(read barrier)과 쓰기 장벽(write barrier)이 있는 로직 영역을 표시하고, 변경(mutation)을 순수 로직과 분리하는 강력한 추상화를 얻을 수 있으며, 이는 기계적으로 검사 가능하다. 이런 정보를 컴파일 타임에 갖는 미래의 언어는, 순수 로직의 경계에 대한 보장을 유지하면서도 지역 변경 영역을 더 효율적인 코드로 컴파일하는 데 이를 활용할 수 있을 것이다.
마지막으로, 효과가 있거나 순수한 인자를 모두 받을 수 있고, 그 효과를 출력 타입의 일부로 포함할 수 있는 고차 함수를 작성하고 싶다. 흔한 map 함수는 리스트를 받아, 주어진 함수 인자를 리스트의 각 원소에 적용하는 고차 함수다. 효과 시스템이 있는 언어에서 이를 작성하려면, 함수 인자의 효과를 타입 변수(이 예에서는 e)로 참조하고 map의 출력 타입에 이를 사용해야 한다.
fun map( xs : list<a>, f : (a) -> e b ) : e list<b>
리스트에 total 산술 함수를 적용하는 경우에는 int 리스트를 되돌려 받는다. 반면 IO의 경우 println 같은 함수를 적용하면 각 정수를 콘솔에 출력하고, 결과 타입은 유닛들의 리스트가 된다. 두 사용 사례는 추상 효과 타입 변수에 대한 이 매개변수적 다형성(parametric polymorphism) 덕분에 같은 함수 하나로 포괄된다.
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년 동안 더 많은 결실을 맺기를 바란다.