인터프리터를 넣으면 컴파일러가 나온다: 부분 평가의 마법

The Magic of Partial Evaluation

부분 평가는 빌드 시점에 알 수 있는 부분을 미리 계산해 프로그램을 특수화하는 기법이다. Jimmy Miller는 JavaScript용 부분 평가기인 prepack의 부활에 자극받아 직접 만든 라이브러리를 공개하며, brainfuck 인터프리터를 부분 평가하면 컴파일된 프로그램이 나온다는 퍼투무라 투영을 설명한다. 인터프리터만 작성해도 컴파일러를 공짜로 얻을 수 있다는 통찰을 보여준다.

이것이 첫 번째 놀라운 사실이다. 인터프리터를 가져다가 프로그램과 함께 부분 평가하면, 컴파일된 프로그램이 결과로 나온다!
  1. TuringTest

    내게 가장 아름다운 소프트웨어는 프로그래밍 언어의 본질에 대해 뭔가를 드러내는 것들이다.

    함수형 프로그래머가 프로그래밍 언어가 실제로 어떻게 작동하는지, 즉 인간 사고의 상징적 표현으로서의 언어에 대한 이해를 진화시키는 순간이 세 가지 있다. 학교에서 배운, 컴퓨터 프로그램이 입력 데이터를 갈아서 결과를 내는 분쇄기라는 비유를 넘어서는 것이다.

    첫 번째는 재귀를 진정으로 이해하고, 함수가 자기 자신을 통해 어떻게 정의될 수 있는지(호출마다 매개변수가 달라지면서) 깨닫는 순간이다.

    두 번째는 Prolog의 변수 통일이나 Haskell의 지연 평가를 발견하고, 프로그램이 무한 루프에 빠지지 않고도 무한 데이터 구조를 표현할 수 있다는 것을 알게 되는 순간이다.

    세 번째는 어떤 명령형 언어의 동작(마이크로프로세서 데이터 경로의 작동까지도)이 순수 함수형 재작성 언어(파괴적 할당이나 셀 상태 변경 없이)로 완전히 표현될 수 있다는 것을 배우는 순간이다.

    이런 통찰은 모든 프로그래밍 패러다임이 기호 처리라는 본질을 공유한다는 것, 그리고 프로그램의 런타임 실행에 대한 '진정한 설명'은 없다는 것을 깨닫게 한다. 실행 중인 프로그램에 대한 명령형, 함수형, 논리적 관점은 모두 동등한 표현이다.

  2. artrax

    우리는 이것을 C++ 라이브러리로 구현해서 스트림 처리 엔진의 쿼리 컴파일을 수행한다.

    https://github.com/nebulastream/nautilus

    이를 통해 연산자나 함수를 LLVM IR DSL(또는 유사한 것)로 작성할 필요 없이 구현할 수 있다. 대신 래퍼 타입(그리고 반환도 래퍼 타입)에 대해 함수를 작성하면, C++에서 오버로드할 수 있는 모든 것에 대해 오버로드가 제공된다.

    어떤 C++ 값으로부터 래퍼를 인스턴스화할 수 있는데, 이 경우 래퍼는 모든 것을 그 값으로 전달한다. 이는 에이전트 이전 시대에 디버깅에 유용했다.

    하지만 이런 래퍼를 추적기(tracer)로 인스턴스화할 수도 있고, 그러면 함수 평가의 결과가 추적(trace)이 된다.

    제어 흐름의 경우, 래퍼 타입이 bool로 평가될 때마다 기록하고, 먼저 true를 반환하며, 한 분기의 끝에 도달하면 예외를 던져 시작 지점으로 돌아가 다시 처음부터 시작하되 false로 평가한다.

    결과 추적을 LLVM IR로 변환해 컴파일하거나, 예를 들어 wasm에서 실행할 수 있다.

  3. apignotti

    우리는 몇 년 전 C++ -> JavaScript/WebAssembly 컴파일러(Cheerp)에서 비슷한 개념을 구현했다. 꽤 도전적인 과제였다.

    https://labs.leaningtech.com/blog/reducing-webassembly-size-...

이 날의 다른 글

2026-11-18