프로그래밍 언어 컴파일러는 보통 기계어나 바이트코드, 혹은 자바스크립트 같은 다른 고수준 언어를 출력한다. 그런데 한 개발자가 휴가 기간에 만든 'catlang'이라는 실험적 언어는 전혀 다른 곳을 겨냥한다. 소스 코드를 컴파일하면 거대한 SQL SELECT 문 하나가 튀어나오고, 그 쿼리를 PostgreSQL에서 실행하면 프로그램의 실행 결과가 나온다. 저자는 이것이 새로운 질의 언어가 아니라 '컴파일 결과물이 우연히 SQL인' 범용 프로그래밍 언어라는 점을 분명히 한다. 예시로 든 프로그램은 입력과 무관하게 항상 100을 반환하지만, 내부적으로는 while 루프에 해당하는 반복을 거쳐 실제로 100까지 세어 올라간다.
왜 SQL을 노렸나
핵심은 SQL이라는 목표물 자체가 아니다. 저자의 관심사는 소스 언어와 최종 타깃 사이에 놓인 중간 표현(IL)이다. 이 IL은 변수 이름이 하나도 없이 범주론의 추상적인 연산 기호들로만 이루어져 있다. 각 기호는 매우 단순하고 명확한 대수적 의미를 갖는데, 예컨대 'A ⨟ B'는 'A를 수행한 뒤 그 결과를 B에 흘려보낸다'는 합성(composition)을 뜻한다. 이렇게 의미가 좁고 분명한 연산들로만 프로그램을 재구성해 두면, 이 IL에서 다른 도메인으로 가는 변환만 정의하면 어떤 괴상한 타깃이든 컴파일이 쉬워진다. SQL은 그 변환을 시험해 보기 위한 '웃긴 실험 대상'이었던 셈이다.
함수가 아니라 화살표
IL이 기대는 범주론의 뼈대는 의외로 단출하다. 타입이 있고, 타입 사이를 잇는 화살표(arrow)가 있다. 아무것도 하지 않는 항등 화살표 id가 있고, 한쪽 끝을 다른 쪽 끝에 맞춰 화살표를 합성할 수 있다. 결정적 차이는 하스켈을 비롯한 보통의 언어와 달리 '함수 적용(application)'이라는 개념이 없다는 점이다. 화살표는 적용하는 것이 아니라 오직 합성할 수 있을 뿐이며, 그래서 '함수'가 아니라 '화살표'라 부른다. 여기에 곱(product)을 다루는 연산들이 더해진다. 쌍에서 요소를 꺼내는 두 사영 함수(fst, snd에 해당)와, 둘을 하나의 쌍으로 묶는 'fork' 연산이다. 저자는 fork가 단순한 튜플 생성자처럼 보이지만 양쪽 사이에 데이터 의존성이 없기 때문에 각 변을 병렬화할 수 있다는 점을 강조한다.
곱 기계장치의 화살표 방향을 모두 뒤집으면 쌍대(dual) 개념인 여곱(coproduct), 즉 'a 또는 b 중 정확히 하나'를 다루는 장치가 나온다. 사영에 대응하는 주입(injection)과 분기에 해당하는 'join' 연산이 그것으로, 하스켈의 either 함수와 같은 역할을 한다. 저자는 이 여덟 개의 연산만으로도 데이터 의존성(⨟), 분기(▽), 병렬화 기회의 자동 인코딩(△), 자료구조의 구성과 해체(사영)까지 상당한 표현력이 확보된다고 설명한다.
이름을 지우면 재타깃이 쉬워진다
IL에 변수 이름이 없다는 사실은 단순한 가독성 저하 이상의 의미가 있다. 소스 언어를 디슈가링할 때 스택을 쌓아 올리고, 이후의 변수 참조는 그 스택을 향한 사영들의 연쇄로 대체된다. 덕분에 어떤 백엔드도 이름을 다룰 필요가 없고, 그저 스택 표현 위에서 작업하면서 사영의 연쇄를 자유롭게 특수 최적화할 수 있다. 저자는 전자 회로를 예로 든다. 32가닥 리본 두 개를 64가닥 리본으로 묶으면 그대로 (Int32, Int32) 쌍이 되듯, 이름이라는 개념이 없는 도메인에도 '묶음'이라는 개념은 흔히 존재하기 때문이다. 이름을 IL 이전 단계에서 제거해 두는 설계가 재타깃 비용을 낮춘다는 통찰이다.
루프는 cochoice라는 원시 연산으로 처리된다. Either 위에서 동작하는 화살표를 받아 Either가 사라진 화살표로 바꿔 주는데, 함수가 Left를 반환하면 그 값을 출력하고 Right를 반환하면 다시 집어넣어 반복한다. 흥미로운 점은 첫 번째 통과와 이후 통과를 정적으로 구분할 수 있다는 것이다. 처음에는 Left, 그 뒤로는 계속 Right이므로, 루프 첫 회에만 무언가를 초기화해야 하는 흔한 패턴을 자연스럽게 표현할 수 있다.
SQL로 내려보낼 때의 현실
실제 컴파일은 각 IL 연산에 SQL 구현을 하나씩 대응시키는 작업이다. id는 입력을 그대로 받는 SELECT * FROM {}가 되고, 합성은 중첩 쿼리, fork는 양쪽 서브쿼리의 컬럼을 이어 붙이는 CROSS JOIN, join은 WHERE 절로 올바른 생성자를 걸러내는 UNION이 된다. 곱은 컬럼으로 펼치면 되지만 여곱의 표현은 고민거리였고, 저자는 결국 여곱을 평탄화해 특정 시점에 오직 하나의 필드만 IS NOT NULL이 되도록 제약을 거는 방식을 택했다. 가장 까다로운 cochoice는 재귀 CTE로 구현되는데, 다중집합인 SQL 테이블에서 '마지막' 값을 안전하게 꺼내는 일이 특히 어려웠다. 반복 횟수 컬럼을 넣어 정렬하는 정공법이 PostgreSQL의 제약 탓에 막히자, 저자는 clock_timestamp()로 프로세서 시계를 읽어 정렬하는 편법을 썼다고 솔직히 밝힌다. 한 행만 생성하는 현재 원시 연산에서는 동작하지만 여러 행을 내놓는 연산을 추가하면 깨질 수 있는 명백한 꼼수다.
이 프로젝트는 실용 도구라기보다 범주론적 의미론이 어떻게 컴파일의 뼈대가 될 수 있는지를 보여 주는 사고 실험에 가깝다. 생성된 SQL에는 뻔한 최적화 여지가 많지만 저자는 거기에 관심이 없다고 못 박는다. 이상적으로는 이 모든 것이 하스켈의 arrow 표기법이 처리하는 작은 라이브러리로 끝났어야 하지만, arrow 추상화가 하스켈 함수를 범주 안에 끼워 넣는 arr 연산을 요구하는 탓에 현실에서는 arrow 표기법이 사실상 무력해진다는 지적도 덧붙인다. 람다 계산이 데카르트 닫힌 범주에 대응한다는 것은 잘 알려진 사실이지만, catlang은 eval 없이 cochoice만으로도 튜링 완전성을 달성할 수 있는지를 끝까지 밀어붙인 결과물이다. 실무자 입장에서 당장 쓸 물건은 아니되, 중간 표현에서 이름을 제거하고 의미가 좁은 연산들로 분해해 두면 전혀 다른 타깃으로도 손쉽게 코드를 내려보낼 수 있다는 설계 교훈만큼은 컴파일러나 DSL을 다루는 사람에게 음미할 가치가 있다.