Clef 프로그래밍 언어에서의 고정점 스캐폴딩 (Fixed-Point Scaffolding)

Gabriel의 "Worse is Better"를 좋아하는 팬들에게는, 구조적 정당성 (correctness properties)을 갖춘 ML 계열 언어를 컴파일하기 위한 스캐폴딩 (scaffold) 역할을 C++가 MLIR을 통해 수행한다는 점이 아이러니하게 느껴질 수 있습니다. 우리의 Composer 컴파일러의 핵심 교차점은 Program Semantic Graph (PSG)로부터 차원 (dimensional), 등급 (grade), 탈출 (escape), 그리고 수치 표현 (numeric-representation) 구조를 보존하는 고정점 결합자 (fixed-point combinator)를 통해 로워링 (lowering)을 시작합니다. 그리고 PSG로부터 관찰된 MLIR은 수동적인 호스트가 아닙니다. 정적 단일 할당 (static single assignment, SSA), 속성 시스템 (attribute system), 그리고 다이얼렉트 (dialects)의 사용은 해당 구조를 실질적으로 전달합니다. 우리는 우리 컴파일러의 미들엔드 (middle end)가 해당 계층에 대한 동반 검증 (companion verification)과 함께 코드를 로워링하기 위해 범주론적 구성 (categorical construction)을 사용함을 보여줍니다: 즉, 합성 방정식 (compositionality equation)을 따르는 컴파일 포셋 (compilation poset)에서 타겟 범주 (target category)로의 함자 (functor)입니다. 우리 접근 방식의 근거는 각각 고유한 대수적 객체 (algebraic object)를 가진 세 가지 소스에서 옵니다: Ohori의 기계어 증명 이론 (machine-code proof theory)은 컴파일 축을 뒷받침하고, 매개변수성 (parametricity)은 기초에서의 콘텐츠를 뒷받침하며, 수반 모드 논리 (adjoint mode logic)는 우리의 검증 계층 간의 순회 (traversal)를 뒷받침합니다. 논지를 확장하기 위해 우리는 컴팩트-폐쇄 음수 및 분수 타입 (compact-closed negative and fractional types)을 도입하며, 타입 메커니즘이 보존된 구조와 함께 전달될 수 있고 MLIR이 제공하는 도구를 통해 실현될 수 있음을 보여줍니다. 더 넓게는, 컴파일을 통해 타입을 보존하는 동일한 고정점 프리미티브 (fixed-point primitive)가 파이프라인을 통해 로워링이 진행됨에 따라 그 무결성을 검증하기 위해 MLIR에서 계속 실행될 수 있는 증명 항 (proof terms)을 제공합니다. 우리는 이 토대가 차원 타입 (dimensional types), Tarau의 그루포이드 (groupoid), 그리고 셀룰러 셰이프 (cellular sheaves)를 포함하는 우리 프레임워크에서 예상되는 독특한 추가 지점이라고 주장합니다. 전 과정에 걸쳐, 형식주의 (formalism)는 내부 스캐폴드 (internal scaffold)로서 도구화됩니다: 즉, 추상화는 컴파일러의 메커니즘을 지원하며, 개발자는 컴파일러가 제공하는 보증을 신뢰하기 위해 범주론 (category theory)을 찾아볼 필요가 전혀 없습니다.