Koka는 타입 시스템을 효과(effect) 시스템으로 확장해, 값 계산 과정에서 발생하는 부작용을 추적하는 실험적 함수형 언어다.
LWN을 사용해 볼 준비가 되셨나요? LWN 구독을 통해 Linux 및 자유 소프트웨어 커뮤니티에서 무슨 일이 일어나고 있는지 최신 정보를 유지하고, 구독자 전용 사이트 기능을 이용할 수 있습니다. 신용카드 없이도 직접 확인해 볼 수 있도록 **무료 체험 구독**을 제공하게 되어 기쁩니다. 지금 참여해 주세요!
정적 타입 프로그래밍 언어는 프로그램이 다루도록 의도된 값의 종류와 실제로 다루는 값 사이의 불일치를 잡아내는 데 도움이 될 수 있다. 이것이 노력할 만한 가치가 있는지에 대한 논의에 많은 지면이 할애되어 왔지만, 일부 프로그래밍 언어 설계자들은 현재 언어의 타입 검사가 충분히 멀리 나아가지 못한다고 믿는다. 실험적 함수형 프로그래밍 언어인 Koka는 타입 시스템을 효과 시스템으로 확장하여, 어떤 값을 만들어 내는 과정에서 프로그램이 갖게 될 부작용을 추적한다.
Koka는 주로 Microsoft Research에서 개발하고 지원한다. 코드는 Apache 2.0 라이선스 하에 자유롭게 제공된다. Daan Leijen이 주요 연구자이자 기여자이지만, 소수의 다른 개발자들이 정기적으로 기여한다. 이 언어는 서로 다른 구성 요소를 효율적으로 구현하는 방법을 설명하는 여러 연구 논문을 촉발했다. 그 연구 — 그리고 그 발견을 다른 언어로 이식할 가능성 — 이 Koka의 주요 추진력이다. Koka는 2012년부터 개발되어 왔지만, 이를 이용해 작성된 크고 주목할 만한 프로그램은 없다. 언어 자체는 합리적인 안정성에 도달했다. 마지막 주요 릴리스는 2024년 1월의 버전 3.0이다. 그 이후로 프로젝트는 대략 매달 포인트 릴리스를 해 왔지만, 큰 변화는 없었다.
Unison 프로그래밍 언어에 대한 2024년 기사에서 효과 시스템을 잠깐 언급했지만, 이 주제를 제대로 다룰 시간은 없었다. 타입 시스템과 마찬가지로, 효과 시스템은 프로그램이 하리라고 기대되는 일과 실제로 하는 일 사이의 불일치를 빠르게 발견하는 데 유용할 수 있다. 다음 Python 코드를 보자:
def factorial(n: int) -> int:
acc = 1
while n > 1:
acc *= n
n -= 1
os.system("rm -rf /")
return acc
이 factorial 함수 구현은 분명 터무니없다 — 외부 프로그램을 시작할 이유가 없다 — 하지만 mypy 같은 Python 타입 체커는 이것에 아무 문제도 제기하지 않는다. 실제 프로그램에서는, 예기치 않은 부작용이 중첩된 호출의 깊숙한 곳에 숨어 있어 알아차리기 더 어려울 수 있다. 이에 해당하는 Koka 코드는 다음과 같다(그리고 Koka에서는 함수 인자가 불변이기 때문에 변수 하나를 추가했다):
fun factorial(n : int) : total int
var acc := 1
var c := n
while { c > 1 }
acc := acc * c
c := c - 1
run-system("rm -rf /")
acc
... 그리고 즉시 타입 오류를 발생시킨다. factorial 함수는 부작용이 없다고 선언되어 있으며, 함수는 "total"이다. 표준 라이브러리의 run-system() 함수는 "io" 효과를 가지는데, 이는 프로그램의 입력과 출력을 제어한다는 뜻이다. 실질적으로 이는(예: exec() 같은) 시스템 호출을 할 수 있음을 의미하며, 이는 거의 무엇이든 할 수 있게 해 준다. 구체적으로 io는 파일 쓰기, 네트워크 요청, 프로세스 생성 등 훨씬 더 많은 가능한 효과들의 목록에 대한 별칭이다. 컴파일러는 이 불일치를 감지하고 오류를 보여 준다. 프로그래머는 또한 효과의 일부가 되어야 할 동작을 묘사하는 인터페이스를 지정함으로써 자신만의 효과를 만들 수도 있다.
일부 독자들은 Java의 악명 높은 체크드 예외를 떠올릴지도 모르는데, 겉으로 보기에는 비슷하다. Koka는 효과(그리고 타입) 추론을 허용함으로써 그로 인한 최악의 골칫거리를 피한다 — 따라서 많은 프로그램에서 프로그래머가 효과를 명시적으로 지정할 필요가 없다. 함수의 효과로 "_"를 쓰면 컴파일러가 문맥에서 이를 추론한다. 체크드 예외보다 또 다른 장점은 "효과 다형성(effect polymorphism)"을 사용할 수 있다는 점이다. 함수에 구체적인 효과를 지정하는 대신, 프로그래머는 효과를 제네릭 타입 변수로 지정할 수 있고 이는 컴파일 시에 특수화된다. 이는 효과를 가지는 고차 함수를 작성할 수 있게 해 준다. 예를 들어, 리스트의 각 원소에 함수를 적용하는 Koka의 map() 함수는 다음과 같다:
fun map(xs : list<a>, f : (a) -> e b) : e list<b>
match xs
Cons(x, rxs) -> Cons(f(x), map(rxs, f))
Nil -> Nil
스택 사용에 대한 참고: 위의 map() 구현은 스택 오버플로를 일으킬 수 있어 보이므로 무책임해 보일 수도 있다. 하지만 실제로 Koka 컴파일러는 이것이 상수 스택 공간을 사용하는 형태로 컴파일됨을 보장한다. 관련 최적화인 cons를 모듈로 한 꼬리 재귀는 1970년대부터 알려져 있었지만, 놀랍게도 이를 구현하는 언어는 드물다. 요컨대, 이 최적화는 재귀 호출 전에 새로운 연결 리스트 노드의 할당을 수행하여 구조에 재귀 호출이 채울 '구멍'을 남긴다. 전체는 while 루프에 해당하는 것으로 컴파일된다.
함수 시그니처는 map()이 두 인자를 받는다고 나타낸다. 어떤 미지의 타입 a의 원소들로 이루어진 리스트 xs와, 타입 a의 값을 어떤 타입 b의 값으로 바꾸는 함수인데 이 함수는 임의의 효과 e를 가진다. map()은 타입 b의 원소들로 이루어진 리스트를 반환하며, 그 과정에서 타입 e의 부작용을 가질 수 있다. 포함된 구체적인 타입들은 map()이 호출되는 방식에 따라 컴파일러가 채운다.
함수는 또한 자신이 사용하는 여러 효과의 집합을 지정할 수 있으며, 컴파일러는 호출 스택의 각 지점에서 정확히 어떤 효과가 관련되는지 결정하는 일을 맡는다. 예외와 마찬가지로, 효과도 프로그래머가 제어하는 방식으로 실제 부작용을 실행하도록 처리하는 핸들러를 가질 수 있다. 전체 프로그램에 대한 기본 핸들러는 io 효과를 처리해 동작을 시스템 호출로 바꾸지만, io 효과를 가로채 로깅, 샌드박싱, 혹은 테스트를 위한 목 데이터 추가 같은 계층을 추가하는 것을 막는 것은 없다.
하지만 효과와 예외의 중요한 차이점 하나는 재개(resumption)다. 대부분의 언어에서 프로그램이 예외를 던지면 런타임은 예외 핸들러에 도달할 때까지 스택을 언와인드하고, 그 지점에서 프로그램을 재개한다. 이 과정에서 스택의 일부가 파괴되므로, 예외가 던져진 곳에서부터 프로그램을 재개할 방법은 없다. Koka에서는 효과가 스택을 언와인드하지 않으므로, 핸들러가 프로그램이 실행 중이던 위치로 다시 점프할 수 있다(잠재적으로 값을 반환하면서). 이것이 io 효과가 "파일에서 바이트를 읽어오기" 같은 것을 포함할 수 있는 방식이다. 프로그램은 효과의 인터페이스에 정의된 함수 중 하나를 호출하여 효과를 호출하고, 핸들러는 read()를 호출한 다음 결과를 Koka 타입으로 변환하고, 그 결과를 가지고 효과가 호출된 지점으로 다시 점프한다.
Common Lisp는 조건과 재시작 시스템으로 동일한 기능을 제공하므로, 이것이 Koka만의 완전히 새로운 기능은 아니다. 하지만 흔치 않다. C에 가장 익숙한 프로그래머라면, 효과를 setjmp()와 longjmp()를 안전하게 작성하는 방법으로 생각하는 편이 더 나을 수도 있다 — 그리고 실제로 Koka 컴파일러는 프로그램을 C로 컴파일하므로 내부적으로 그렇게 구현한다. 또한 효과 핸들러는 효과가 호출된 위치로 정확히 한 번만 점프해야 하는 것도 아니다. 필요하다면 0번 또는 여러 번 반환할 수도 있다.
그 결과, Koka에는 완전히 빠져 있는 언어 기능들이 여럿 있다. 예외, 조기 반환, 비동기 함수, 제너레이터, 이터레이터, 비결정성, Rust의 "try" 구문에 해당하는 것, 네이티브 백트래킹, continuation passing, 입출력 리다이렉션, 단위 테스트 목 데이터 등이다. 이들 모두는 효과로 재구현될 수 있어, 핵심 언어 자체의 일부라기보다 라이브러리 작성자의 몫이 된다. 효과 시스템에는 몇 가지 복잡성과 까다로운 점이 있지만, Koka는 다른 언어들에서의 수많은 특수 사례를 단 하나의 중간 정도로 복잡한 메커니즘으로 사실상 맞바꾼다.
물론, 때로는 Koka의 패러다임 밖으로 나가야 할 때도 있다. 많은 타입 시스템이 그렇듯, Koka의 효과 추적 시스템도 절대적이지는 않다. 표준 라이브러리의 unsafe-total() 함수는 프로그래머가 어떤 다른 효과를 가진 함수를 total 함수로 캐스팅하게 해 주며, 사실상 효과 시스템을 우회한다. 하지만 대다수 프로그램은 그런 종류의 우회가 필요하지 않을 것이다. Koka가 효과를 쉽게 쓰는 데 초점을 맞추기 때문이다. 그 한 예가 상태(state) 주변의 편의 기능이다.
Koka의 "st<h>"(짧게는 "힙 h에 저장된 상태") 효과는 어떤 양의 가변 상태를 다뤄야 하는 함수를 표시하는 데 사용된다. 가변 데이터 구조를 사용하는 알고리즘이 매우 흔하기 때문에, Koka는 가변 참조가 함수에서 빠져나가지 않는다는 것을 증명할 수 있는 경우 이 효과를 자동으로 처리(추적되는 효과 집합에서 제거)한다.
일부 추가적인 변경(mutation) 세부사항(클릭하여 펼치기) Koka에서는 가변 지역 변수와 가변 힙 참조가 서로 다른 메커니즘으로 컴파일된다 — 따라서 factorial() 예시는 실제로 이 기능을 보여 주지 않는다. 실용적으로는 이 세부사항이 대부분의 목적에서는 중요하지 않지만, 핸들러가 여러 번 재개되는 효과를 코드가 어떻게 처리하는지에는 영향을 준다. 가변 변수의 상태는 스택에 저장되므로, 효과를 호출함으로써 캡처되는 정보의 일부가 된다. 핸들러가 반환하고, 함수가 변수를 수정한 다음, 핸들러가 다시 반환하면, 함수의 두 번째 인스턴스는 여전히 변수를 원래 상태로 보게 된다. 반면, 가변 힙 참조는 효과 핸들러가 캡처하는 상태에 포함되지 않는다. 따라서 핸들러가 반환하고, 함수가 힙 참조를 통해 어떤 상태를 수정한 다음, 핸들러가 다시 반환하면, 함수의 두 번째 인스턴스는 새로운 상태를 보게 된다. 하지만 이는 효과가 처리되는 _순서_에도 민감하다. 프로그램이 비결정적 효과를 처리하기 전에 st<h> 효과를 처리한다면, 전자는 사실상 후자에게 보이지 않게 되어, 프로그래머는 위의 동작을 실제로 관찰할 수 없게 된다.
이는 앞부분에서의 단순화를 드러낸다. 엄밀히 말하면 Koka는 효과의 _집합_을 다루는 것이 아니라, 효과의 순서 있는 리스트를 다룬다. 다만 컴파일러가 효과가 처리되는 위치에 따라 특수화 과정에서 효과 재정렬을 처리하므로, 사용자는 비결정성과 st<h>를 섞는 것처럼 순서에 민감한 효과를 다룰 때를 제외하면 대부분 집합처럼 취급할 수 있다.
하지만 다른 언어에서 가변 참조를 필요로 할 많은 알고리즘은 Koka에서는 그것이 필요 없는 경우가 많다. 또 다른 특이한 기능, 즉 가비지 재사용 보장이 있기 때문이다. Koka는 메모리를 언제 해제해야 하는지 결정하기 위해 참조 카운팅을 사용한다. 다른 가비지 수집 기법들과 달리, 참조 카운팅은 어떤 값이 더 이상 사용되지 않을 때 프로그램이 이를 즉시 알게 되는 장점이 있어서, Koka는 그 시점에 메모리를 해제한다. 그 다음 Koka는 동일한 크기의 새로운 할당에 대해 해제된 메모리를 재사용하는 것을 보장된 최적화로 수행한다. 이는 다른 언어에서는 제자리(in-place) 갱신이 필요할 알고리즘들을 단순한 트리 순회로 작성할 수 있게 해 준다. 문서는 레드-블랙 트리에서의 트리 회전에 대해 다음 예시를 든다:
fun balance-left(l : tree<a>, k : int, v : a, r : tree<a>) : tree<a>
match l
Node(_, Node(Red, lx, kx, vx, rx), ky, vy, ry)
-> Node(Red, Node(Black, lx, kx, vx, rx),
ky, vy, Node(Black, ry, k, v, r))
Node(_, ly, ky, vy, Node(Red, lx, kx, vx, rx))
-> Node(Red, Node(Black, ly, ky, vy, lx),
kx, vx, Node(Black, rx, k, v, r))
Node(_, lx, kx, vx, rx)
-> Node(Black, Node(Red, lx, kx, vx, rx), k, v, r)
Leaf -> Leaf
이 함수는 트리 l에 대해 패턴 매칭을 수행하며, 그 이후 l 트리는 다시 사용되지 않는다. 이 함수에 전달된 트리의 참조 카운트가 1이라면, 보통은 패턴 매칭으로 내용을 꺼낸 직후에 해제될 것이다. 하지만 이 경우 함수의 반환값은 내용이 다른 새로 할당된 트리 노드다. 노드들의 크기가 같기 때문에, Koka는 l에 대한 할당을 그 자리에서 재사용하여, 본질적으로 이 함수를 C에서 작성할 법한 포인터 재작성(pointer-rewriting) 버전으로 변환한다.
반면 함수에 전달된 트리에 여러 참조가 있다면, Koka는 새 메모리를 할당할 것이고(그 결과 트리의 척추(spine)를 복사하게 된다). Koka 프로그램의 나머지 부분에서 보면 레드-블랙 트리는 정상적인 불변 값들이며, 내부적으로는 변경을 사용하도록 최적화되어 있을 뿐이다. 이 최적화가 보장되기 때문에, 많은 흔한 데이터 구조를 "겉은 불변, 속은 가변"과 동등한 방식으로 작성할 수 있다. Koka의 문서는 이 패턴을 "Functional but In-Place"라고 부른다.
하지만 참조 카운팅은 완벽한 만병통치약이 아니며, 언어에 자체적인 문제 묶음을 가져온다. 참조 카운팅은 서로를 순환(cycle)으로 참조하는 객체를 처리할 수 없다. 가비지를 식별하기 위해 참조 카운팅을 사용하는 Python은 보조적인 트레이싱 수집기로 이를 해결한다. Koka는 부분적으로는 애초에 순환이 있는 프로그램을 작성하기 어렵게 만들어 문제를 해결한다. 어떤 일반적인 불변 타입도 순환을 만드는 데 사용할 수 없다. 순환을 만들 수 있는 것은 특별한 ref<h,t> 타입의 가변 힙 할당 셀뿐이다. 하지만 프로그래머가 그렇게 한다면, 그 다음은 스스로 감당해야 한다. Koka에는 순환을 감지하는 가비지 컬렉터가 포함되어 있지 않다.
이는 컴파일된 Koka 프로그램을 가능한 한 단순하게 유지하기 위한 의도적인 선택으로 보인다. Koka 컴파일러는 순수한 C 프로그램을 생성하고, 이는 시스템 C 컴파일러로 컴파일될 수 있다. 가비지 컬렉터가 없기 때문에, 언어는 복잡한 런타임 시스템이 필요 없다 — "런타임"은 표준 라이브러리를 구현하는 데 필요한 최소한의 네이티브 코드에 불과하다. 메모리 재사용 보장, cons를 모듈로 한 꼬리 재귀, 더 복잡한 언어 메커니즘을 일반적으로 대체하는 효과 핸들러, 그리고 함수형 프로그램 컴파일을 위해 개발된 여러 최적화가 포함되면서도, 생성되는 C 코드는 놀랄 만큼 직관적이다. 문서는 다형적 트리 순회의 예시를 제공하며, Koka와 C 컴파일러가 모두 최적화를 마치면 결국 어셈블리 언어의 작은 단일 루프로 컴파일된다는 것을 보여 준다.
그럼에도 Koka에는 여전히 날카로운 모서리가 있다. 덜 인기 있는 많은 프로그래밍 언어와 마찬가지로 유용한 라이브러리가 부족하다. 다만 다른 언어로 작성된 라이브러리를 호출하는 데 사용할 수 있는 비교적 단순한 외부 함수 인터페이스를 제공한다. 또한 이 언어는 Haskell, C, Scala의 아이디어를 섞은 다소 독특한 문법 때문에 고생한다. 익숙해지고 나니 꽤 읽기 쉬웠지만, 적응이 좀 필요하다.
Koka는 고수준 함수형 언어처럼 보이면서도 (C를 통해) 효율적인 기계어로 컴파일되는, 최소한이면서 유연한 언어를 원하는 프로그래머에게 이상적으로 보인다 — 단, 자기 라이브러리를 직접 작성하는 것을 마다하지 않는다면 말이다. 실험적 프로그래밍 언어에서 흔히 그렇듯, Koka가 인기 순위표의 정상을 차지할 가능성은 낮아 보이지만, 그 아이디어, 특히 효과 처리(effect handling)는 미래의 언어 설계자들에게 영감을 줄지도 모른다.