소프트웨어에는 실용성과 무관하게 그 자체로 아름다운 아이디어들이 있다. 프로그래밍 언어 설계에 매료된 개발자라면 특히, 계산의 본질을 다시 보게 만드는 개념에 끌리기 마련이다. 이번에 다룰 '부분 평가(partial evaluation)'가 바로 그런 주제다. 이 글은 개발자 지미 밀러가 자신의 글에서 소개한 내용을 바탕으로, 인터프리터와 컴파일러가 실은 하나의 뿌리에서 나온 형제라는 사실을 설명한다. 밀러는 메타가 만든 자바스크립트용 부분 평가기 prepack을 제임스 롱이 되살렸다는 소식을 계기로, 자신 역시 Rust로 자바스크립트용 부분 평가기를 직접 구현해 공개했다고 밝힌다. 다만 그는 prepack이 '아름다움'보다 '실용성'을 겨냥해 설계됐다고 평가하며, 자신의 라이브러리는 널리 쓰이기 위해서가 아니라 이 개념을 직접 만져보게 하려고 만들었다고 덧붙인다.
부분 평가란 무엇인가
부분 평가의 직관은 단순하다. 프로그램에서 빌드 시점에 미리 계산할 수 있는 부분은 계산해 버리고, 런타임에만 알 수 있는 나머지만 남기는 것이다. 모든 값이 정적으로 알려져 있다면 컴파일 시점에 통째로 실행해 답만 내놓을 수 있다. 반대로 일부 값이 런타임에 들어온다면, 그 미지의 값과 무관한 재귀 호출이나 분기는 모두 펼쳐 없애고 프로그램을 '동적인 뼈대'만 남은 형태로 축약한다. 밀러는 산술 연산만 지원하는 간단한 인터프리터를 예로 든다. 입력값을 모르더라도 그 값이 '숫자'라는 부분적 정보는 알 수 있고, 그 정보만으로도 식을 더 깊이 줄여나갈 수 있다는 것이다.
인터프리터가 컴파일러가 되는 순간
진짜 놀라움은 더 복잡한 예시에서 드러난다. 그는 brainfuck 인터프리터를 가져온다. 입력이 필요 없는 프로그램을 부분 평가하면 그냥 실행 결과가 나오지만, 입력을 받는 프로그램을 부분 평가하면 '컴파일된 brainfuck 프로그램'이 튀어나온다. 즉 인터프리터를 특정 프로그램에 대해 부분 평가하면, 인터프리터라는 범용 해석 장치는 사라지고 그 프로그램만을 위한 코드가 남는다. 이것이 세 가지 후타무라 투영(Futamura projection) 중 첫 번째다. 의사코드로 쓰면 '부분평가기(인터프리터, 프로그램) = 컴파일된 프로그램'이 된다.
이 사실이 중요한 이유는 인터프리터를 짜는 일과 컴파일러를 짜는 일이 실무에서 난이도가 꽤 다르기 때문이다. 인터프리터에 계측을 넣거나 새 기능을 추가하는 일은 비교적 쉽지만 컴파일러에서는 훨씬 까다롭다. 게다가 세상에는 '인터프리터처럼 동작하지만 아무도 컴파일러를 따로 짜지 않는' 코드가 많다. 밀러가 든 예가 스키마 처리 코드다. 범용 스키마 검증·변환 로직을 부분 평가해 특정 스키마 전용 함수로 특수화하면, 객체가 복잡해질수록 약 5배의 성능 향상을 얻을 수 있다고 한다. 손으로 전용 함수를 짜거나 컴파일러를 따로 만들 수도 있지만, 런타임에만 존재하는 스키마라면 결국 컴파일러와 인터프리터를 둘 다 유지해야 한다. 부분 평가는 그 부담을 덜어준다.
특수화의 특수화, 그리고 컴파일러 생성기
밀러는 부분 평가를 '프로그램 특수화(specialization)'라는 틀로 다시 설명한다. 범용 패턴 매처나 간단한 정규식 엔진처럼 여러 입력을 처리하도록 만든 코드를, 하나의 고정된 패턴만 처리하는 전용 코드로 바꾸는 것이 특수화다. 부분 평가기는 무엇이 정적이고 무엇이 동적인지를 보고 특수화 지점을 스스로 찾아내는, 말하자면 '범용 특수화기'다.
여기서 질문이 이어진다. 특수화기가 어떤 프로그램이든 특수화할 수 있다면, 자기 자신도 특수화할 수 있지 않을까. 특수화기를 '특정 인터프리터'에 대해 특수화하면, 이제 임의의 프로그램을 받아 그 프로그램 전용 컴파일 결과를 내놓는 함수, 즉 컴파일러가 만들어진다. 이것이 두 번째 투영이며, 인터프리터만 주면 컴파일러가 자동으로 유도된다. 세 번째 투영은 여기서 한 걸음 더 나아가 특수화기를 자기 자신에 적용한다. 그 결과물은 어떤 인터프리터를 넣어도 그에 맞는 컴파일러를 뱉어내는 '컴파일러 생성기'다.
물론 밀러 본인도 자신의 구현이 합리적이되 여전히 상당히 제한적이라고 분명히 밝힌다. 다양한 인터프리터에서 잘 동작하도록 다듬었고 두 번째·세 번째 투영도 제한된 형태로 구현했지만, 통하지 않는 경우가 많다는 것이다. 실무에서 당장 부분 평가기를 도입하라는 이야기가 아니라, 인터프리터와 컴파일러의 관계라는 깊은 구조를 눈으로 확인하고 직접 만져볼 수 있다는 점에 그 가치가 있다. 실용성의 잣대만으로 이런 탐구를 가로막을 필요는 없다는 것이 그의 결론이다.