Salt Systems Language: Z3 Theorem Proving and MLIR Codegen

Salt Systems Language: Z3 Theorem Proving and MLIR Codegen

Salt integrates Z3 theorem proving directly into the compiler

Salt은 시스템 프로그래밍 언어로, 가비지 컬렉터의 런타임 오버헤드나 Borrow Checker의 복잡성 없이 메모리 안전성과 함수 계약에 대한 수학적 확실성을 제공하도록 설계되었습니다. Microsoft Research의 Z3 SMT 솔버를 컴파일 과정에 직접 삽입함으로써, Salt은 개발자가 requires() 전제조건과 ensures() 사후조건을 정의하고 이를 빌드 시점에 검증할 수 있게 합니다.

Z3 솔버가 조건이 성립함을 증명하면, 해당 런타임 검사는 완전히 생략되어 그 검사를 위한 명령어가 전혀 생성되지 않습니다. Z3가 위반을 발견하면, 컴파일러는 구체적인 반례를 보고합니다. 솔버가 제한 시간(의무당 100 ms) 내에 판단하지 못하면, 컴파일러는 안전한 런타임 검사를 삽입합니다.

High-performance architecture and MLIR codegen

Salt은 TensorFlow와 PyTorch를 구동하는 동일한 인프라인 MLIR(Multi-Level Intermediate Representation)을 활용하여 clang -O3와 동등한 성능을 달성합니다.

Automatic Loop Tiling

MLIR affine dialect를 통해 Salt은 손으로 튜닝한 타일 크기 없이 자동 루프 타일링을 구현합니다. 이를 통해 일반 행렬 곱셈과 같은 연산 집약적 작업이 C와 동등한 속도로 실행됩니다. 600줄짜리 Salt 구현인 Basalt Llama 2 추론 엔진에서는 affine optimizer가 행렬 곱셈을 타일링하여 높은 효율성을 유지합니다.

Arena Memory Model

Salt은 전통적인 가비지 컬렉션과 Borrow Checking을 아레나 기반 메모리 모델로 대체합니다. 모든 할당은 특정 영역 내에서 이루어지며, 전체 영역이 한 번에 해제됩니다. 컴파일러는 어떤 참조도 자신의 아레나보다 오래 살아남지 않음을 정적으로 검증하므로, 수동 free() 호출이나 복잡한 수명 주석이 필요 없습니다.

Real-world implementations and benchmarks

이 언어는 여러 고성능 시스템 구축에 사용되어 다양한 도메인에서의 다재다능함을 입증했습니다:

  • KeuOS: Salt으로 처음부터 작성된 마이크로커널로, x86 하드웨어에서 부팅됩니다. 16코어 SMP와 Chase‑Lev 워크 스틸링, 제로 트랩 소켓 API를 특징으로 합니다. 벤치마크에 따르면 널 시스템 콜이 102 사이클(리눅스보다 7.4배 빠름)이며 IPC 핑‑퐁이 297 사이클입니다.
  • Lettuce: 567줄의 Salt으로 구성된 Redis 호환 인‑메모리 데이터 스토어입니다. 제로‑카피 RESP 파서와 kqueue 이벤트 루프를 활용해 테스트된 동시성 수준(1–100 클라이언트)에서 Redis보다 뛰어난 성능을 보입니다.
  • Basalt: 모든 연산 커널이 배열 접근이 범위 내에 있음을 증명하는 Z3 증명을 포함하는 Llama 2 추론 엔진입니다.
  • FACET: 모든 픽셀 쓰기가 프레임버퍼 내에 있음을 Z3가 검증하는 2D 렌더링 엔진으로, 457 fps를 달성합니다.

Apple M4(macOS ARM64)에서 수집된 성능 데이터에 따르면 Salt은 21개의 알고리즘 벤치마크 중 19개에서 C(clang -O3)와 동등하거나 더 빠른 성능을 보입니다. HashMap 및 LRU 캐시와 같은 할당이 많은 워크로드는 아레나 할당 모델 덕분에 2‑10배의 성능 향상을 나타냅니다.

Language ergonomics and tooling

Salt은 보일러플레이트를 줄이고 가독성을 높이기 위해 여러 문법 기능을 도입했습니다:

  • Pipe Operator: |> 연산자는 데이터를 왼쪽에서 오른쪽으로 흐르게 하며, |?>는 오류를 전파합니다. 이는 C에서의 장황한 오류 처리 패턴이나 Rust의 트레이트 바인딩 절차를 대체합니다.
  • F-strings: 힙 할당이나 포맷 지정자 없이 표현식을 삽입할 수 있는 타입‑안전 문자열 포맷팅입니다.
  • Package Management: sp 도구는 프로젝트 생성, 빌드, 의존성 관리를 담당합니다. 내용 주소 기반 캐싱을 사용해 소스 코드가 변경되지 않으면 재빌드가 일어나지 않도록 합니다. 안전 계약은 패키지 경계 전체에 걸쳐 검증되며, 라이브러리가 특정 조건을 요구하면 컴파일러가 다운스트림 패키지의 모든 호출 지점에서 해당 조건을 확인합니다.

Technical limitations and community context

Salt이 뛰어난 성능과 검증 기능을 보여주지만, 현재는 연구 수준 프로젝트이며 프로덕션 준비가 된 언어는 아니라는 점을 저자는 강조합니다. 표준 라이브러리가 미완성이고, Z3의 문자열 및 양화자 지원이 부분적입니다. 또한 Z3 패스에서 발생하는 오류 메시지가 때때로 불투명할 수 있습니다.

커뮤니티 논의에서는 다른 형식 검증 언어와의 비교가 자주 언급됩니다. 예를 들어, Ada의 서브셋인 SPARK는 1980년대부터 안전‑중요 항공·방위 프로젝트에 Z3를 사용해 왔으며, Verus는 Rust에 Z3를 결합해 유사한 검증 목표를 추구합니다. 비평가들은 현재 문서와 언어 사양이 일관성이 부족하고, 주요 개발자를 제외한 베타 테스터 커뮤니티가 넓지 않다고 지적합니다.

요약: Salt은 Z3 SMT 솔버를 컴파일러에 직접 통합하여 수학적으로 검증된 안전 계약을 제공하고, 런타임 비용을 전혀 발생시키지 않으며 clang -O3와 동등한 성능을 달성하는 시스템 프로그래밍 언어입니다.

제목: Salt Systems Language: Z3 Theorem Proving and MLIR Codegen

Sources