MetaOCaml은 OCaml에 타입이 있는 코드 값과 괄호/이스케이프 표기를 더해 “프로그램을 생성하는 프로그램”을 작성할 수 있게 하는 보수적 확장이다. 생성된 코드는 출력, 파일 저장, 또는 컴파일하여 실행 중인 프로그램에 링크할 수 있고, 오프쇼어링을 통해 C 등으로 변환할 수도 있다. 스코프 유출 검사를 통해 생성 코드의 정적 보장을 강화하고, let/let rec 삽입, 1급 패턴, 명시적 리프팅, CSP 등을 제공한다.
(BER) MetaOCaml은 “프로그램을 생성하는 프로그램”을 작성하기 위한 OCaml의 보수적 확장이다. MetaOCaml은 OCaml에 코드 값(“프로그램 코드” 혹은 미래 단계의 계산)을 나타내는 타입과, 그것을 구성하는 두 가지 기본 구문(괄호와 이스케이프)을 추가한다. 생성된 코드는 출력하거나 파일로 저장할 수 있으며, 컴파일 후 실행 중인 프로그램에 다시 링크하여 런타임 코드 최적화를 구현할 수 있다. 생성 코드의 명령형 부분은 오프쇼어링을 통해 C로 변환할 수도 있다. 잘 타입검사된 MetaOCaml 프로그램은 스코프가 올바르고 타입이 올바른 프로그램만 생성한다. 즉 생성된 코드는 타입 오류 없이 컴파일된다. 현재의 MetaOCaml은 Walid Taha, Cristiano Calcagno 및 협력자들이 만든 원조 MetaOCaml을 전면 재구현한 것이다.
Installation and availability https://okmij.org/ftp/ML/MetaOCaml.html#install
Introduction to staging and MetaOCaml https://okmij.org/ftp/ML/MetaOCaml.html#using
Data constructor restriction https://okmij.org/ftp/ML/MetaOCaml.html#ctors
Moving free variables around but not letting them escape https://okmij.org/ftp/ML/MetaOCaml.html#got-away
Many ways to run the code https://okmij.org/ftp/ML/MetaOCaml.html#run
Native (natively-compiled) MetaOCaml https://okmij.org/ftp/ML/MetaOCaml.html#native
More brackets https://okmij.org/ftp/ML/MetaOCaml.html#more-brackets
First-class pattern-matching https://okmij.org/ftp/ML/MetaOCaml.html#make-match
Let-insertion as a primitive https://okmij.org/ftp/ML/MetaOCaml.html#genlet
Generating mutually recursive definitions https://okmij.org/ftp/ML/MetaOCaml.html#letrec
Offshoring https://okmij.org/ftp/meta-programming/tutorial/genc.html
Cross-stage persistence https://okmij.org/ftp/ML/MetaOCaml.html#CSP
Further plans https://okmij.org/ftp/ML/MetaOCaml.html#plans
The Design and Implementation of (BER) MetaOCaml https://okmij.org/ftp/ML/MetaOCaml.html#ber-design
MetaOCaml: Ten Years Later https://okmij.org/ftp/ML/MetaOCaml.html#design-10
Implementing staging https://okmij.org/ftp/ML/MetaOCaml.html#implementing-staging
A brief history of (BER) MetaOCaml https://okmij.org/ftp/ML/MetaOCaml.html#history
Staging, Program Generation, and Meta-Programming https://okmij.org/ftp/meta-programming/
Reconciling Abstraction with High Performance: A MetaOCaml approach https://okmij.org/ftp/meta-programming/tutorial/
MetaScheme, or untyped MetaOCaml https://okmij.org/ftp/meta-programming/implementations.html#meta-scheme
MetaOCaml은 타입이 있는 코드 값을 구성하기 위한 단계(스테이징) 주석을 제공하는 OCaml의 보수적 확장이다. 아래에서 이 기능들에 대한 간단한 소개를 볼 수 있다. 생성된 코드는 출력하거나 파일에 저장할 수 있으며, 혹은 컴파일하여 실행 중인 프로그램에 다시 링크하여 런타임 코드 최적화를 구현할 수 있다. 스테이징 주석이 없는 MetaOCaml 코드(또는 주석을 지운 코드)는 일반 OCaml과 동일하다.
MetaOCaml은 최적의 스트림 퓨전, 빠른 파서와 정규표현식 매처 생성, 수치/동적 프로그래밍 알고리즘의 특화, FFT 커널 구축, 이미지 처리 및 데이터베이스 쿼리 DSL 컴파일러, OCaml 서버 페이지, 특화된 기본 선형대수 및 가우스 소거 루틴의 계열 생성, 고성능 스텐실 계산 등에 성공적으로 사용되었다.
MetaOCaml은 Camlp4 등의 매크로 처리기와 다음 점에서 구별된다: 위생(hygiene, 렉시컬 스코프 유지); 잘 타입된 코드를 보장하여 생성; 고차 함수, 모듈, ML의 기타 추상화 기능과의 통합. 이는 코드 생성기의 모듈성 및 재사용을 촉진한다. 잘 타입검사된 MetaOCaml 프로그램은 잘 타입검사된 프로그램만 생성한다. 즉 생성된 코드는 타입 오류 없이 컴파일된다. 크고 난독화되어 변수명이 불친절한 생성 코드의 컴파일 오류를 해석해야 하는 문제는 더 이상 없다. 오류는 생성기 기준으로 보고된다.
MetaOCaml은 순수 생성적(purely generative)이다: 생성된 코드는 블랙박스로 취급되어 내부를 들여다볼 수 없다. 코드를 합칠 수는 있지만 분해할 수는 없다. 순수 생성성은 타입 시스템을 단순화하며 정적 보장을 강화한다. 순수 생성성이 코드 최적화를 막을 것처럼 보일 수 있지만, 실제로는 그렇지 않다. MetaOCaml로 최적 코드를 생성하는 많은 문헌 사례가 있다.
현재의 (BER) MetaOCaml은 원조 MetaOCaml의 정신을 따르되 서로 다른 알고리즘과 기법으로 완전히 다시 작성되었다. 예전 MetaOCaml 코드는 적거나 전혀 수정 없이 여전히 실행된다. 전반적으로, MetaOCaml은 OCaml과 스테이징을 조화롭게 통합하여 차이를 최소화하는 것을 목표로 한다. 이를 통해 MetaOCaml을 최신 상태로 유지하고 장기적으로 생존 가능하게 만들기 쉽다.
BER MetaOCaml은 OCaml 타입 검사기의 변경을 최소화하고 ‘커널’과 ‘사용자 수준’을 분리하도록 재구성되었다. 커널은 코드 값의 생성 및 타입검사를 담당하는 OCaml에 대한 패치와 추가의 집합이다. 생성된 코드의 처리(소위 ‘실행’)는 사용자 수준이다. 현재 사용자 수준 라이브러리 ‘metalib’는 코드 값의 출력, 타입검사, 바이트/네이티브 컴파일 및 링크를 지원한다. 추가로, 생성 코드는 ‘오프쇼어링’되어 중간의 명령형 언어로 변환된 뒤 C, OpenCL, LLVM 등으로 전사될 수 있다.
BER MetaOCaml은 원조 MetaOCaml과 거의 완벽히 하위 호환된다. 사용자 관점에서 BER MetaOCaml의 주요 차이는 다음과 같다(자세한 설명은 아래 참고):
눈에 띄는 소소한 차이로는, 함수 리터럴이나 값에 해당하는 코드에 대한 특수 ‘부분 타입’, 더 도움이 되는 오류 메시지, CSP 값의 더 나은 출력, 라벨드 인자에 대한 완전한 지원 등이 있다. 다형적 필드를 가진 레코드의 오랜 문제가 자연스레 해결되었다. BER MetaOCaml 코드는 주석이 풍부하고 회귀 테스트 모음도 갖추었다. MetaOCaml은 지역/1급 모듈과 객체를 생성 코드로 직접 생성하는 것은 지원하지 않는다. 다만 모듈과 객체를 코드 생성기에서 사용하는 것은 가능하다.
OCaml 4.02의 기능인 애트리뷰트에 의존함으로써, BER N102는 OCaml과 더욱 밀접히 통합되었고(그리고 BER N153은 더더욱 그러하다). MetaOCaml이 OCaml 배포본에 가하는 변경량을 비교해보는 것이 유익하다. 이전 버전(BER N101)은 OCaml 파일 32개를 수정했다. BER N153은 5개만 수정한다(이 수는 더 줄여 1개로도 가능하며, 실질적인 수정은 typing/typecore.ml 하나뿐). 앞으로의 OCaml 버전이 작은 훅을 제공하면, MetaOCaml이 포크가 아니라 일반 라이브러리나 플러그인이 될 가능성이 현실적이다.
배포본의 NOTES.txt 파일은 MetaOCaml의 기능을 더 자세히 설명하고, 향후 개발 방향을 개괄한다. 연구개발 계획은 방대하며, 스테이징 이론에서부터 생성 코드를 LLVM, Wasm 등의 대상으로 변환하는 변환기의 개발까지 포함한다. 누구에게나 재미와 과제가 있다. MetaOCaml의 공개가, 타입드 메타프로그래밍의 사용과 연구를 촉진하길 바란다.
현재 버전은 N153, 2025년 5월
Stream Fusion, to Completeness
최신이자 주목할 만한 응용 사례
Reconciling Abstraction with High Performance: A MetaOCaml approach
MetaOCaml 서적
ml2013-talk.pdf[200K]
MetaOCaml은 계속된다: 함수형 언어의 단계적 방언을 구현하며 얻은 교훈
2013년 9월 22일, ACM SIGPLAN Workshop on ML, Boston, MA, USA 발표의 주석 달린 슬라이드
(BER) MetaOCaml N153은 OCaml 5.3.0에 대응한다. OPAM을 통해 MetaOCaml을 설치하려면 다음을 수행한다.
$ opam update
$ opam switch create 5.3.0+BER
$ eval `opam config env`
Tuareg를 사용한다면, 다음 옵션이 유용하다고 보고되어 있다:
Tuareg group
(setq tuareg-support-metaocaml t)
Tuareg Faces group
Tuareg Font Lock Multistage Face
MetaOCaml을 수동으로 설치할 수도 있다. 커널과 사용자 수준의 분리에 걸맞게, MetaOCaml은 OCaml에 적용하는 패치 모음과 별도 라이브러리 ‘metalib’로 배포된다. 설치는 OCaml 배포본을 패치하고, 평소처럼 OCaml 시스템을 빌드한 뒤, metalib와 MetaOCaml 톱레벨을 컴파일하는 절차다. 패치된 OCaml 컴파일러는 OCaml과 완전한 소스/바이너리 호환이며, 스테이징 구문이 있든 없든 OCaml 코드를 처리한다. 또한 MetaOCaml은 기존 OCaml로 컴파일된 모듈과 라이브러리를 그대로 사용할 수 있다. MetaOCaml은 다음 형태로 제공된다:
OCaml 5.3.0 배포본에 대한 패치 세트
이 아카이브의 INSTALL 문서를 참고하라. OCaml 5.3.0의 소스 배포본이 필요하다.
메타프로그래밍의 표준 예제(부분 평가를 탄생시킨 A. P. Ershov의 1977년 논문의 주 예제)는 거듭제곱 함수 x^n 계산이다. (보다 현실적이고 설명적인 예시는 mult.ml 참고) OCaml로는 다음과 같다:
let square x = x * x
let rec power n x =
if n = 0 then 1
else if n mod 2 = 0 then square (power (n/2) x)
else x * (power (n-1) x)
(* val power : int -> int -> int = <fun> *)
(코드 아래 주석은 MetaOCaml 톱레벨의 응답을 보여준다.)
프로그램이 x^7을 여러 번 계산해야 한다고 하자. 부분 적용을 이름 붙여 공유하기 위해 다음과 같이 정의할 수 있다:
let power7 x = power 7 x
(* val power7 : int -> int = <fun> *)
MetaOCaml에서는 거듭제곱 함수를 특정 값 n에 특화하여, 나중에 x를 받아 x^n을 계산할 코드를 얻을 수 있다. power n x를 ‘지금’(n을 아는 시점)과 ‘나중’(x가 주어지는 시점)으로 주석 달아 다시 쓴다.
let rec spower n x =
if n = 0 then .<1>.
else if n mod 2 = 0 then .<square .~(spower (n/2) x)>.
else .<.~x * .~(spower (n-1) x)>.
(* val spower : int -> int code -> int code = <fun> *)
두 가지 주석(스테이징 구문)은 브래킷 .< e >. 와 이스케이프 .~e 이다. 브래킷 .< e >.는 표현식 e를 ‘나중에’ 계산될 것으로 준인용(quasi-quote)한다. 이스케이프 .~e는 브래킷 내부에서만 사용되며, e는 ‘지금’ 계산되지만 그 결과(코드)가 ‘나중’을 위한 것임을 알린다. 그 결과 코드는 바깥 브래킷에 스플라이스된다. spower의 추론된 타입은 다르다. 결과가 더 이상 int가 아니라 int code(정수를 계산하는 표현식의 코드)다. spower의 타입은 어떤 인자가 지금, 어떤 인자가 나중에 주어지는지 명시한다: 미래 단계 인자는 코드 타입을 갖는다. 브래킷과 이스케이프의 대체 문법(확장 노드)도 있다. 예컨대 위 spower는 다음처럼도 쓸 수 있다:
let rec spower n x =
if n = 0 then [%metaocaml.bracket 1]
else if n mod 2 = 0 then [%metaocaml.bracket square [%metaocaml.escape spower (n/2) x]]
else [%metaocaml.bracket [%metaocaml.escape x] * [%metaocaml.escape spower (n-1) x]]
(* val spower : int -> int code -> int code = <fun> *)
편집기와 설정에 따라 이 형태가 실제로 입력/표시에 더 쉬울 수 있다.
spower를 7에 특화하려면 다음과 같이 정의한다:
let spower7_code = .<fun x -> .~(spower 7 .<x>.)>.;;
(*
val spower7_code : (int -> int) code = .<
fun x_1 -> x_1 * (csp_square_3 (x_1 * (csp_square_2 (x_1 * 1))))>.
*)
이로써 x를 받아 x^7을 반환할 함수의 코드를 얻는다. 함수의 코드라도 출력할 수 있는데, MetaOCaml 톱레벨은 방금 그렇게 했다. 출력에는 이른바 단계 교차 지속 값(CSP)이 포함되어, 현재 단계의 값(예: square)을 ‘인용’하여 나중에 사용한다. CSP는 ‘외부 라이브러리’에 대한 참조로 생각할 수 있다. 단지 우리 경우엔, 프로그램이 자신이 생성하는 코드의 라이브러리 역할을 한다. square가 별도 파일 sq.ml에 정의되어 있었다면, spower7_code에서 그 발생은 단순히 Sq.square로 출력되었을 것이다.
이렇게 특화된 x^7을 지금 코드에서 사용하려면, spower7_code를 ‘실행(run)’해야 한다. 즉 'a code -> 'a 타입의 함수 Runcode.run을 적용한다. 이 함수는 코드를 컴파일하여 우리 프로그램에 다시 링크한다.
open Runcode;;
let spower7 = run spower7_code
(* val spower7 : int -> int = <fun> *)
특화된 spower7의 타입은 위의 부분 적용 power7과 동일하다. 동작도 같다. 하지만 power7 x는 n에 대한 재귀를 수행하며 n의 홀짝을 확인한다. 반면 특화된 spower7은 재귀가 없다(spower7_code에서 볼 수 있듯). n에 대한 모든 연산은 spower7_code를 생성할 때 완료되었고, 결과 spower7은 x를 곧장 곱하는 직선적 코드다.
생성된 spower7_code는 꽤 단순하며(생성 코드는 대체로 그렇다), 따라서 오프쇼어링을 통해 C로 쉽게 변환할 수 있다. 다만 우리가 정의한 square 함수에 대해 알려줄 필요가 있다. C에 static int sqr(int const x) { return x * x; } 같은 함수 sqr이 있고, 우리의 square를 그것으로 매핑하고 싶다고 하자.
let _ =
let module M = struct (* 오프쇼어링 라이브러리에 매핑 지시 *)
open Offshoring (* 우리의 Sq.square를 C의 sqr로 *)
include DefaultConv
let id_conv path name = match (path,name) with
| ("Sq","square") -> "sqr"
| _ -> id_conv path name
end
in
Offshoring.offshore_to_c ~cnv:(module M) ~name:"power7" spower7_code
결과(파일로 저장할 수 있음)는 다음과 같다:
int power7(int const x_1){
return (x_1 * sqr(x_1 * sqr(x_1 * 1)));
}
MetaOCaml은 임의 개수의 미래 단계를 지원하여, 코드 생성기뿐 아니라 코드 생성기의 생성기 등도 작성할 수 있다.
Reconciling Abstraction with High Performance: A MetaOCaml approach
Walid Taha: A Gentle Introduction to Multi-stage Programming
A.P. Ershov: On the partial computation principle
Information Processing Letters, 1977, v6, N2, pp. 38-41.
부분 평가 연구 분야를 연 논문의 영어판. 논문 그림 1의 거듭제곱 예시는 다음 원고 스캔에서 볼 수 있다.
<http://ershov.iis.nsk.su/files/archive/fold0241/241_75.gif>
Information Processing Letters 논문은 A. P. Ershov: A Theoretical Principle of System Programming의 영어판이다.
Doklady AN SSSR (Soviet Mathematics Doklady), 1977, v18,N2, pp.312--315.
지면 사정으로 Doklady AN SSSR 논문에는 거듭제곱 예시가 빠졌지만, 1976년 11월 초고의 노트에서 확인할 수 있다.
<http://ershov.iis.nsk.su/files/archive/fold0241/241_17.gif>
아마도 거듭제곱 함수 특화의 최초 사례로 보인다.
이 논문의 기타 초고는 “The Ershov Archive for the history of computing”에서 볼 수 있다.
<http://ershov.iis.nsk.su/archive/eaindex.asp?gid=1480>
MetaOCaml에는 테스트 모음이 함께 제공되며, 배포본의 metalib/test/ 디렉터리에 작은 예제부터 큰 예제까지 다수 포함되어 있다.
mult.ml[11K]
상수 곱셈 예제: 거듭제곱의 보다 현실적인 버전으로, 코드 템플릿(브래킷/이스케이프), let 삽입, 오프쇼어링, JIT 느낌의 실시간 특화, 심지어 다단계를 보여준다.
MetaOCaml은 프로그램 코드를 위한 데이터 타입과 그러한 타입드 코드 값을 구성하고 실행하는 연산을 추가하여 OCaml을 확장한 상위호환 언어다. 도메인 특화 언어(DSL)의 컴파일과 고성능 계산 커널의 지루하고 오류가 나기 쉬운 특화를 자동화하는 데 사용되었다. 생성된 코드가 컴파일됨을 정적으로 보장하고, 빠르게 실행해볼 수 있게 함으로써 MetaOCaml은 생성기 작성의 부담을 줄이고 생산성을 높인다.
현재의 BER MetaOCaml은 Taha, Calcagno 및 협력자들이 만든 원조 MetaOCaml의 완전 재구현이다. 새로운 구성, 알고리즘, 코드뿐 아니라, 환경 분류자를 대체하는 스코프 유출 검사를 추가했다. 바인딩되지 않았거나 잘못 바인딩된 변수(변경이나 기타 효과로 인해 발생 가능)를 가진 코드 값을 만들려 할 경우 이제 조기에 포착되어, 좋은 진단과 함께 예외를 발생시킨다. 생성 코드가 항상 컴파일됨에 대한 보장은, 코드를 생성할 때 어떤 효과가 사용되었든 무조건적이 되었다.
우리는 새로운 코드를 모듈화하고 유지보수 가능하게 만든 설계 결정을 강조하며 BER MetaOCaml을 설명한다. 또한 스코프 유출 검사의 구현을 설명한다.
ber-design.pdf[297K]
FLOPS 2014에 발표된 논문의 전체판. 짧은 버전은 Springer LNCS 8475, pp. 86-102 수록.
doi:10.1007/978-3-319-07151-0_6
talk-FLOPS.pdf[196K]
2014년 6월 4일 일본 가나자와에서 열린 FLOPS 2014에서 발표된 주석 달린 슬라이드.
Let-insertion without pain or fear or guilt
루프 불변 코드 이동을 편리한 let 삽입으로 구현(FLOPS 2014 발표의 주요 예제)
MetaOCaml은 정적 보장을 갖춘 편리한 코드 생성을 위한 OCaml 상위호환 언어로, 생성된 코드는 작성과 동시에 문법/타입/스코프가 올바르다. 완성된 생성 코드가 항상 컴파일될 뿐 아니라, 변수의 스코프 탈출도 코드 생성 중에 이미 감지된다. MetaOCaml은 도메인 특화 언어 컴파일, 제네릭 프로그래밍, HPC에서의 지루한 특화 자동화, 효율적 계산 커널과 임베디드 프로그래밍 생성에 사용되었다. 교육용으로도 쓰이며 여러 메타프로그래밍 시스템에 영감을 주었다.
MetaOCaml에서 가장 잘 알려진 것은 생성 코드 값을 위한 타입과, 그런 값을 만드는 템플릿 기반 메커니즘(브래킷과 이스케이프)이다. MetaOCaml은 또한 CSP, 일반/상호 재귀 정의 생성, 1급 패턴 매칭, 이종 메타프로그래밍을 지원한다.
FLOPS 2014에서 처음 소개된 현존 구현은 지속적으로 진화해왔다. 우리는 현재 설계와 구현을, 특히 주목할 만한 추가 사항에 초점을 맞춰 설명한다. 그 중에는 타입드 코드 템플릿을 코드 조합자(code combinator)로 번역하는 새롭고 효율적이며 이식하기 쉬운 방법이 있다. 스코프 유출 탐지는 뜻밖에도 let 삽입과 20년 묵은 CSP 문제의 결정적 해결을 가져왔다.
design-10.pdf[386K]
Functional and Logic Programming. FLOPS 2024. Lecture Notes in Computer Science, vol. 14659, pp. 219-236, 2024. Springer 게재 논문.
doi:10.1007/978-981-97-2300-3_12
mult.ml[11K]
논문의 러닝 예제로, 브래킷/이스케이프만이 아니라 다양한 MetaOCaml 기능을 보여주도록 설계되었다.
스테이지드 언어를 구현하는 매력적인 접근은 기존 언어에 스테이징을 추가하여, 기존 코드 생성기, 파서, 라이브러리, 사용자 기반을 활용하는 것이다. 이 절은 타입드 함수형 언어에 스테이징을 추가하는 세 가지 방법을 설명하며, 마지막 방법이 MetaOCaml에 실제로 구현되어 있다.
가장 직관적인 방법은 추상 구문 트리(AST)에 스테이징 형태를 추가하고 파서를 조정하며, 타입드 AST에도 스테이징 형태를 추가하여 타입 검사기를 수정하고, 중간 언어에도 스테이징 형태를 추가하여 코드 생성기에서 반영하는 것이다. 모든 것을 수정해야 하니 차라리 언어를 처음부터 다시 구현하는 편이 나을 수 있다. 하지만 훨씬 간단한 방법이 있다.
가장 간단한 접근은 브래킷을 코드 조합자로 만든 표현식으로 전처리해 없애는 것이다. 예를 들어, MetaOCaml 표현식
fun x -> .<fun y -> .~x * y + 1>.
은 다음의 평범한 OCaml 코드로 번역된다.
fun x -> lam "y" (fun y -> (add (mul x y) (int 1)))
이는 평가되면 코드를 생성한다.
코드 조합자(code combinator), 즉 원시 코드 생성자는 타입이 있으며 대략 다음 시그니처를 가진다:
type 'a cod
val int: int -> int cod
val add: int cod -> int cod -> int cod
val mul: int cod -> int cod -> int cod
val lam: string -> ('a cod -> 'b cod) -> ('a->'b) cod
val app: ('a->'b) cod -> ('a cod -> 'b cod)
이 번역은 camlp4나 독립 전처리기로 할 수 있다. 기반 시스템(OCaml)은 수정 없이 그대로 사용할 수 있다. 가장 좋은 점은, 이 번역이 타입과 합치된다는 것이다: 전처리 결과(순수 OCaml)가 일반 OCaml 규칙에 따라 타입검사에 성공한다면, 원본 MetaOCaml 코드도 MetaOCaml 규칙에 따라 잘 타입된 것이다. 이 단순한 접근은 놀랍도록 잘 작동한다: Scala의 LMS가 유사한 아이디어를 기반으로 한다. Scheme의 quasi-quote 구현도 상당히 비슷하지만, 람다나 let 형태를 특별 취급하지는 않는다.
조건문과 루프 같은 특수 형태를 다루는 등의 복잡성이 있다. 썽크를 도입해야 한다. 패턴 매칭과 타입 주석은 골칫거리인데, 해킹으로(deconstructors와 Haskell의 asTypeOf 같은 특수 타입 주석 함수로 번역) 우회할 수 있다. Scala-Virtualized 논문이 그런 번역을 자세히 논한다. 그러나 .<let f = fun x -> x in ...>. 같은 다형적 let은(였었다!) 막는 요소였다. 브래킷 내부의 let 바인딩은 번역 후 람다 바인딩이 되는데, 이는 다형적일 수 없다. OCaml이 1급 다형성을 지원하긴 하지만 타입 주석을 요구하므로, 번역은 타입검사 이전의 매크로 확장/전처리로는 불가하다. 일반적으로 다형성은 이 단순 접근에서 문제가 된다: 코드 값은 표현식으로 번역되므로, 다형적 코드 값(예: let f = .<fun x -> x>.)은 값 제한 때문에 단형 표현식으로 번역된다.
남은 접근은 타입검사 이후 스테이징을 제거하는 것이다. 예를 들어 fun x -> .<fun y -> .~x * y + 1>. 은 먼저 브래킷과 이스케이프를 반영한 수정된 OCaml 규칙에 따라 타입검사된다. 그런 다음 다음과 같이 번역된다:
fun x -> build_fun_simple "y" (fun y ->
mkApp (mkIdent "+")
[mkApp (mkIdent "*") [x; y];
mkConst 1])
미래 단계의 코드는 적절히 타입검사되며, 다형적 구성도 포함된다. 브래킷과 이스케이프는 타입검사 도중에 제거된다. 타입 t의 미래 단계 바운드 변수는 현재 단계의 바운드 변수 y가 되지만, 타입은 t code가 된다.
이것이 MetaOCaml의 접근이다. 스테이징 주석이 타입검사 후 제거되므로, OCaml 백엔드(최적화기/코드 생성기)는 수정 없이 그대로 사용된다. 다만 타입검사기가 현재 브래킷 레벨을 추적하고 브래킷 내부를 타입검사하도록 수정해야 한다. 전자를 위해 현재 레벨을 위한 전역 ref를 두고, 브래킷/이스케이프를 만날 때 증가/감소시킨다. 미래 단계 코드의 타입검사는 현재 단계와 거의 동일하나 한 가지 예외가 있다. 미래 단계 바인딩 형태에 의해 바인딩된 식별자는 그 단계로 주석되어야 한다. BER N102는 value_description에 애트리뷰트를 붙여 해당 값의 스테이징 레벨을 표시한다.
코드 생성 표현식의 결과는 'a cod 타입의 값이다. 코드 값이 저수준 코드 비트일 수도 있지만, 그런 것을 합성하기는 매우 어렵다. 예를 들어 .<1>.은 문맥에 따라 명령어의 일부가 될 수도, 데이터 세그먼트의 일부가 될 수도 있어 표현이 다르다. 생성된 코드가 잘 타입됨이 보장되므로 다시 타입검사할 필요가 없다. 따라서 코드 조합자는 타입검사 이후의 중간 언어 조각을 만들 수 있다. 이 언어(타입 주석이 달린 AST — OCaml에선 Typedtree) 역시 합성하기 어렵다: 타입 주석과 그 타입 환경을 유지하는 일이 번거롭다. MetaOCaml 코드는 임의 개수의 let 표현식을 생성할 수 있다. 코드 조합자가 타입 주석 AST를 만든다면, 새로 바운드된 식별자와 그 타입으로 타입 환경을 확장해야 한다. 생성된 let 표현식이 다형적일 경우, 코드 생성기는 타입 변수 갱신을 해야 한다. 코드 값을 untyped AST로 실현하는 것이 가장 단순하다. AST는 표면 문법으로 pretty-print한 뒤, 일반 소스 코드처럼 컴파일할 수 있다.
A surprisingly simple implementation of staging
여기서 개략한 단순 접근은 실제로 작동하며, 실용적인 2단계 언어 구현에 사용할 수 있다. 다형적 let 생성 문제도 — 아주 최근에야 — 해결되었다.
BER N114부터 구현됨.
대수 데이터 타입은 OCaml의 두드러진 특징 중 하나지만, 스테이징 계산에서는 고려되지 않았다. 이론은 따라서 다음과 같은 사용자 정의 대수 타입의 생성자를 포함하는 코드의 스테이징에 지침을 주지 못한다:
type foo = Foo | Bar of int
.<let x = Foo in match x with Bar z -> z>.
생성된 코드는 파일에 저장될 수 있고, 그 내용은 let x = Foo in match x with Bar z -> z 이다. 하지만 Foo와 Bar가 선언되지 않았으므로 이 파일을 컴파일하면 실패한다. 문제는, 생성된 코드가 문법적으로 ‘표현식’이므로 선언을 포함할 수 없는데, 데이터 타입 선언을 생성된 코드에 어떻게 넣느냐이다.
예전 MetaOCaml은 생성 코드를 나타내는 AST를 수정하여 선언(실제로는 전체 타입 환경)을 위한 필드를 추가함으로써 문제를 다뤘다. 이런 변경은 타입 검사기 전반에 연쇄적인 수정을 유발해, MetaOCaml이 OCaml과 괴리되는 주요 이유 중 하나가 되었고, 결국 MetaOCaml의 일시적 소멸에 기여했다.
BER MetaOCaml은 N100부터 이런 AST 수정을 피하고 대신 ‘생성자 제약’을 도입한다: 브래킷 안에서 사용하는 모든 데이터 생성자와 레코드 라벨은 별도 컴파일된 모듈에서 선언된 타입에서 와야 한다. 이 제약은, OCaml이 표준 데이터 타입의 생성자를 사용하는 Some 1 같은 코드를 컴파일하는 데 아무 문제 없다는 관찰에서 나온다. 다음 표현식들은 모두 제약을 만족한다:
.<true>.
.<raise Not_found>.
.<Some [1]>.
.<{Complex.re = 1.0; im = 2.0}>.
let open Complex in .<{re = 1.0; im = 2.0}>.
.<let open Complex in {re = 1.0; im = 2.0}>.
왜냐하면 bool, option, list, Complex.t 등의 데이터 타입은 Stdlib에 있거나 표준 라이브러리에 (별도 컴파일된) 정의되어 있기 때문이다. Complex.t 같은 외부 타입 선언은 complex.cmi에 있으며, 생성 코드를 컴파일할 때 참조할 수 있다. 반면 다음 예시는 제약을 위반하므로 BER MetaOCaml이 거부한다:
type foo = Bar
.<Bar>.
module Foo = struct exception E end
.<raise Foo.E>.
foo의 타입 선언이나 Foo의 모듈 선언은 인터페이스 파일로 옮겨 별도 컴파일해야 한다. 컴파일된 인터페이스는 런타임에도 필요하다: 실행 파일과 같은 디렉토리에 두거나, OCaml 라이브러리 검색 경로 어딘가에 두어야 한다(표준 라이브러리 타입처럼).
그럼에도 Parsetree.expression 트리 안에 타입 선언을 포함시키는 방법이 있다. 예를 들어,
type foo = Foo | Bar of int
.<let x = Foo in match x with Bar z -> z>.
은 다음과 같은 생성 코드를 만들 수 있다:
let module M =
struct
type foo = Foo | Bar of int
end
in let open M in
let x = Foo in match x with Bar z -> z
이는 문제 없이 컴파일된다. OCaml의 지역 모듈은 사실상 선언을 표현식 안에 등장시킬 수 있게 한다. 생성된 코드는 데이터 타입 환경에 대해 클로저가 된다. 따라서, 생성자 제약은 향후 어떤 릴리스에서든 해제될 수 있다. 한편 초기 경험으로는 이 제약이 크게 제한적이거나 만족하기 어려워 보이지 않는다.
MetaOCaml은 열린 코드(open code)를 다룰 수 있게 한다. 이 절은 그런 코드의 모든 자유 변수가 최종적으로 의도한 바인더에 의해 바인딩되도록 보장하는 데 따르는 복잡성과 트레이드오프를 설명한다. BER MetaOCaml은 N101부터 선배격 시스템과 선택을 뒤집어, 타입 수준 검사를 포기하는 대신 더 강하고 정보적인 동적 스코프 유출 검사를 채택했다.
MetaOCaml에서 프로그램 코드는 1급이다: 함수 인자로 전달되거나 결과로 반환되거나, 변경 가능한 셀에 저장되거나, 예외로 던져질 수 있다. 그 코드는 자유 변수를 포함할 수 있는데, 그런 변수는 MetaOCaml 프로그램이 타입검사되기 위해 타입 환경에 등장해야만 한다. 자유 변수는 결국 바인딩되어 생성된 코드가 닫혀 있을 것이라 생각할 수 있다. 따라서 실행은 미바인딩 변수로 인해 실패하지 않아야 한다. 유감스럽게도, 잘 타입검사된 BER MetaOCaml 프로그램도 실행 시, 열린 코드를 실행하거나 스코프가 잘못된 코드를 구성하려 ‘시도’할 수 있다 — 즉, 자유 변수가 자신의 바인더를 ‘벗어나’ 영영 바인딩되지 않거나, 더 나쁘게는 우연히 다른 바인딩에 묶이는 경우다. BER MetaOCaml에서는 이런 시도가 조기에 탐지되어, 정보적인 오류 메시지와 함께 생성기 실행이 중단된다. 이전 MetaOCaml 버전들은 타입 시스템(환경 분류자)으로, 드물게 발생하는 열린 코드 실행 시도의 일부를 막았다. 그러나 다른 시도는 탐지되지 않아 스코프가 잘못된 코드가 생성되었다. 이제는 더 이상 그렇지 않다.
열린 코드를 다루는 데에는 두 가지 위험이 있다. 첫째, 언어에 run 연산이 존재한다는 사실만으로 아직 완성되지 않은 코드에 이를 적용할 위험이 생긴다. 다음은 전형적 예시다:
.<fun x y -> .~(let z = run .<x+1>. in .<z>.)>.
BER N101 이전의 MetaOCaml은 이 코드를 타입검사 시점에, 환경 분류자의 도움으로 거부했다(Taha and Nielsen, POPL 2003). 당시 int 코드 값의 타입은 ('c,int) code였는데, 'c는 분류자다. 코드 값이 닫혀 있으면 분류자는 일반화 가능하다. 위 예시는 다음 타입 오류로 거부되었다:
.<fun x y -> .~(let z = .! .<x+1>. in .<z>.)>.;;
^^^^^^^
.! error: 'a not generalizable in ('a, int) code
(BER N101 이전에는 코드 실행 연산이 .!로 표기되었다.)
BER에서는 위 예시가 타입검사를 통과한다. 그러나 생성기의 실행은 런타임 예외로 중단된다:
.<fun x y -> .~(let z = run .<x+1>. in .<z>.)>.;;
Exception:
Failure
"The code built at Characters 29-32:
.<fun x y -> .~(let z = run .<x+1>. in .<z>.)>.;;
^^^
is not closed: identifier x_1 bound at Characters 6-7:
.<fun x y -> .~(let z = run .<x+1>. in .<z>.)>.;;
^
is free".
오류 메시지는 자유 변수의 이름과, 생성기 소스에서 그 변수를 바인딩했어야 할 바인더를 가리키며 정보가 풍부하다.
열린 코드를 이리저리 옮기다 보면, 변경 가능한 셀에 저장하거나, 예외로 던지거나, 제한 연속(delimited continuations)에 캡처하는 경우 등, 또 다른 방식으로 스코프가 잘못된 코드를 낳을 수 있다. 유감스럽게도 환경 분류자는 이런 오류를 탐지하지 못했고, 실제로 나쁜 일이 일어났다. 다음은 2006년 옛 MetaOCaml(버전 3.09.1 alpha 030)을 사용하는 예이다(문제를 더 간단히 보일 수도 있지만, 이 예가 더 현실적이고 교묘하다).
let c =
let r = ref .<fun z->z>. in
let f = .<fun x -> .~(r := .<fun y -> x>.; .<0>.)>. in
.<fun x -> .~f (.~(!r) 1)>. ;;
(*
val c : ('a, '_b -> int) code =
.<fun x_4 -> ((fun x_2 -> 0) ((fun y_3 -> x_2) 1))>.
*)
결과 코드(주석에 인터프리터 출력으로 표시됨)에서 x_2가 사실 미바인딩이라는 점을 알아차리려면 한참 들여다봐야 한다. 소위 스코프 유출이 일어났다. 이 코드를 실행해보아야만 어디선가 잘못되었음을 알 수 있다.
.! c;;
(*
Characters 77-78:
Unbound value x_2
Exception: Trx.TypeCheckingError.
*)
어차피 오류가 나니(그마저 진단은 부실하지만) 문제가 그리 심각하지 않다고 치부할 수 있다. 유감스럽게도, 때로는 스코프 유출이 오류를 유발하지 않고 — 단지 잘못된 결과를 낼 뿐이다. 간단한 변형은 문제를 덮어버린다:
let c1 =
let r = ref .<fun z->z>. in
let _ = .<fun x -> .~(r := .<fun y -> x>.; .<0>.)>. in
!r;;
(*
val c1 : ('a, '_b -> '_b) code = .<fun y_3 -> x_2>.
*)
이제 c1을 사용해 코드 c2를 구성한다:
let c2 = .<fun y -> fun x -> .~c1>.;;
(*
val c2 : ('a, 'b -> 'c -> '_d -> '_d) code =
.<fun y_1 -> fun x_2 -> fun y_3 -> x_2>.
*)
여기에는 미바인딩 변수가 없으므로 문제없이 실행된다.
(.! c2) 1 2 3;;
(* - : int = 2 *)
사용자는 아마도 c2의 fun x -> 가 c1의 x를 바인딩하길 의도하지 않았을 것이다. 이는 렉시컬 스코프의 노골적인 위반이다. 그런데도 오류나 이상 징후 없이 넘어간다.
BER MetaOCaml에는 이런 일이 없다. 타입 시스템은 여전히 유출 변수가 있는 코드 값을 허용하지만, 그런 코드를 스플라이스/출력/실행하려는 즉시 예외가 발생한다. 예를 들어 위 c 표현식을 BER MetaOCaml 톱레벨에 입력하면 다음과 같다:
Exception:
Failure
"Scope extrusion detected at Characters 127-137:
.<fun x -> .~f (.~(!r) 1)>. ;;
^^^^^^^^^^
for code built at Characters 80-90:
let f = .<fun x -> .~(r := .<fun y -> x>.; .<0>.)>. in
^^^^^^^^^^
for the identifier x_2 bound at Characters 65-66:
let f = .<fun x -> .~(r := .<fun y -> x>.; .<0>.)>. in
^".
표현식 c는 타입검사를 통과했지만, 평가 도중 예외로 중단되어 코드가 생성되지 않았다. BER N100 이전에는 c가 미바인딩 변수를 가진 코드로 ‘성공’적으로 평가되었다. 이제 스코프 유출이 탐지될 뿐 아니라, 어느 변수가 도망쳤는지, 생성기의 어느 부분이 그것을 바인딩했어야 하는지, 어디서 달아났는지를 알려주는 정보가 풍부한 메시지로 보고된다. 두 번째 예에서 c1은 성공적으로 평가되지만(결과를 출력하면 스코프 유출이 보고됨), c1을 스플라이스하는 순간 추가 코드 생성이 즉시 중단된다. 예외는 도망친 변수 x의 이름과, 그 변수가 바인딩되었어야 할 생성기 소스의 위치를 다시 알려준다. 결과적으로 스코프가 잘못된 코드는 생성되지 않는다.
트레이드오프를 정리해보자. N101 이전 MetaOCaml은 환경 분류자에 의존해, 타입검사 시점에 단 하나의 오류 부류 — 아직 완성되지 않은 코드의 실행 시도 — 만을 방지했다. 환경 분류자는 스코프 유출을 막지 못해 스코프가 잘못된 코드가 생성되곤 했다. 경험적으로, 환경 분류자가 막는 오류는 드물었다(부분적으로는 run의 복잡한 타입 때문에 톱레벨에서만 쓰기 쉬웠고, 그 지점에서는 코드가 항상 완성되어 있었기 때문). code 타입의 추가 타입 매개변수는 성가셨다: 코드를 담을 수 있는 모든 자료구조는 환경 분류자를 담는 타입이어야 했다. 생성기 추상화는 정의/사용이 번거로웠다. 값 제한 때문에 분류자의 일반화가 막히는 경우가 잦아, 환경 분류자는 종종 false positive를 냈다.
BER N101의 스코프 유출 검사는 동적이다 — 생성기가 컴파일될 때가 아니라 실행될 때 작동한다. 타입 오류를 동적 오류로 바꾸는 것은 아쉬울 수 있다. 반면, 생성기는 나쁜 코드를 만들기 전에 중단되고, 비교적 자세하고 유익한 오류 메시지(달아난 변수를 가리킴)와 함께 예외를 던진다. 오류가 예외이므로, 예외 스택 백트레이스를 얻어 어떤 생성기 부분이 변수를 누출했는지 정확히 파악할 수 있다. BER N100 이전에는, 최선의 경우 생성된 코드를 컴파일하다 오류가 나서 당황하고, 생성기의 어느 부분이 문제였는지 추적하는 데 어려움을 겪었다. 스코프 유출 검사는 타입 시스템 확장을 요구하지 않으므로 구현/유지가 더 쉽다.
따라서 BER MetaOCaml N101은 환경 분류자를 제거했다. 이는 드문 오류에 대해서만 좋은 보호(타입 오류)를 제공하면서, 항상 번거로웠기 때문이다. 스코프 유출 검사는 비록 동적이지만 포괄적이고 정보가 풍부하여, 효과가 있더라도 올바른 형식 보장을 유지한다. 다시 말해, N100부터 BER MetaOCaml은 코드가 성공적으로 생성되어 화면에 표시되거나 파일로 저장될 수 있다면 — 그 코드는 잘 타입/스코프화되었음을 무조건 보장한다. 타입 오류 없이 컴파일된다.
BER MetaOCaml은 ‘커널’과 ‘사용자 수준’으로 구성된다. 전자는 스테이징 주석을 타입검사하고 컴파일한다. 생성된 코드를 다루는 일은 사용자 수준 라이브러리의 몫이다. 예를 들어, BER MetaOCaml 배포본의 metalib는 코드 값을 출력하고, 바이트/네이티브로 컴파일한다. 사용자 수준 MetaOCaml 코드는 MetaOCaml 자체를 다시 빌드하지 않고도 변경/확장할 수 있다. 나아가 OCaml의 변경이 사용자 수준 코드에 미치는 영향도 줄어든다.
BER MetaOCaml은 다음과 같은 커널 인터페이스를 제공한다.
type 'a code (* 추상: 열린 코드일 수 있음 *)
type 'a closed_code = private Parsetree.expression
val close_code : 'a code -> 'a closed_code
val open_code : 'a closed_code -> 'a code
뒤쪽(open_code)은 전체 함수이고, 앞쪽(close_code)은 스코프 유출 검사를 수행한다. 닫힌 코드는 본질적으로 OCaml AST이므로, 생성 코드를 닫은 후 사용자 측에서 이를 다양한 방식으로 살펴보고 ‘실행’할 수 있다. 실행의 한 방식은 출력이다. 사용자 수준 Codelib 라이브러리는 다음 인터페이스를 제공한다:
val print_code : Format.formatter -> 'a code -> unit
val print_closed_code : Format.formatter -> 'a closed_code -> unit
val format_code : Format.formatter -> 'a closed_code -> unit
val print_code_as_ast : 'a closed_code -> unit
앞의 두 함수는 코드를 pretty-print한다. print_code는 close_code와 print_closed_code의 합성이다. 이 두 함수는 MetaOCaml 톱레벨에서 코드 값의 프린터로 등록되어 있다. format_code는 print_closed_code와 유사하지만 바깥 브래킷을 생략한다. 생성 코드를 파일에 저장해 나중에 컴파일할 때 유용하다. 마지막 함수는 닫힌 코드 값을 파스 트리로 출력하여 디버깅에 도움을 준다.
코드를 실행하기 위해, 현재 사용자 수준 MetaOCaml은 바이트코드 컴파일로 실행하는 val run_bytecode : 'a closed_code -> 'a 또는 네이티브 컴파일로 실행하는 val run_native : 'a closed_code -> 'a 를 제공한다. 함수 Runcode.run : 'a code -> 'a 는 close_code와 run_bytecode 또는 run_native의 합성이다.
이 밖의 run-유사 함수는 추가하기 쉽다: 평범한 함수이며 다른 라이브러리 함수처럼 링크하거나 톱레벨에 로드하면 된다. 더 이상 MetaOCaml을 재컴파일할 필요가 없다. 옛 MetaOCaml에는 생성 코드를 C와 Fortran으로 변환하는 이른바 ‘오프쇼어링’이 있었다. 예를 들어 FFT 커널 생성에 사용되었고, 생성된 C 코드는 FFTW 벤치마킹/테스트 프레임워크에 그대로 꽂아 사용할 만큼 충분히 좋았다. 전면 개편 동안 오프쇼어링은 정리와 재작성을 위해 잠시 제외되었고, 이제 별도 라이브러리로 개발 중이다. 오프쇼어링과 유사한 많은 변환은 타입 주도이므로, 이를 위해 MetaOCaml은 typecheck_code : 'a closed_code -> Typedtree.expression 을 제공하여 생성 코드를 타입검사할 수 있게 한다. N107부터 오프쇼어링이 더 일반적인 방식으로 돌아왔으며, (생성된) OCaml 코드의 부분집합을 단순한 명령형 중간 언어로 번역한 다음 C, OpenCL, LLVM 등으로 전사할 수 있게 했다.
N104부터, 생성기가 네이티브로 컴파일(metaocamlopt)되었다면 생성된 코드를 네이티브로 컴파일하여 제공한다. 네이티브로 컴파일된 생성 코드는 실행 중인 프로그램에 다시 링크되며, 그 결과 런타임 코드 특화를 지원한다.
런타임 코드 특화는 MetaOCaml을 사용하는 한 가지 방식일 뿐임을 강조해야 한다. 다른 방식은 사실 더 두드러지며, 세 개 이상의 제법 큰 프로젝트에서 사용되었다: 손코드 수준의 성능을 가진 스트림 라이브러리, FFT 커널과 가우스 소거의 최적 코드 생성. 가우스 소거(GE)는 많은 알고리즘 계열로, 도메인(int, float, 다항식), 피벗 선택, 행렬식/랭크/치환 행렬 계산 여부, 행렬 레이아웃 등 수많은 요소로 매개변수화된다. GE는 자주 내부 루프에 사용되므로 성능이 매우 중요하다. 따라서 이 모든 매개변수화는 정적으로 이루어져야 한다. Jacques Carette와 함께 우리는 다양한 매개변수 조합에 대해 많은 GE 프로시저를 생성했다. 생성 코드는 파일에 저장되어 ocamlopt로 라이브러리로 컴파일되었다. 생성기는 바이트코드 OCaml이었지만, 생성 코드는 최적화된 네이티브 OCaml로 컴파일될 수 있었다. 우리는 바이트코드 실행을 테스트에만 사용했다. FFT 프로젝트도 유사했다: 생성기는 바이트코드였고, 테스트에는 바이트코드 실행을 사용했으며, 생성 코드는 C였고 Intel C 컴파일러로 컴파일했다.
강조하자면, 바이트코드 생성기는 적합한 어떤 컴파일러로든 컴파일될 코드를 만든다. 생성기와 생성 코드의 모드(바이트코드/네이티브)는 서로 무관하다.
Stream Fusion, to Completeness
Generating optimal FFT code and relating FFTW and Split-Radix
Multi-stage programming with functors and monads: eliminating abstraction overhead from generic code
MetaOCaml의 브래킷 .<e>. 과 이스케이프 .~e 는 내부적으로 확장 노드 metaocaml.bracket과 metaocaml.escape로 표현된다. 즉 .<e>. 는 [%metaocaml.bracket e]의 문법 설탕이다.
브래킷 관련 애트리뷰트 두 개도 있다. 이는 브래킷 표현식에 부착되도록 되어 있다. 애트리뷰트는, 그것이 붙은 브래킷 표현식과 함께, 일종의 ‘특수 브래킷’으로 간주할 수 있다. 현재 이러한 ‘특수’ 브래킷에 대한 문법 설탕은 제공하지 않는다(기존 OCaml 문법을 덜 교란하기 위해). 아래의 브래킷-수정 애트리뷰트 중 하나만 브래킷에 붙일 수 있다.
첫 번째 브래킷 수정 애트리뷰트는 metaocaml.functionliteral 이다. 이는 브래킷된 표현식이 실제로 함수 리터럴(예: .<function p1 -> e1 ... pn -> en>. 또는 .<fun p -> e>.)임을 주장(assert)한다. 이런 함수 리터럴은 1급 패턴처럼 동작한다. 타입 검사기는 브래킷된 표현식이 실제 함수 리터럴인지 확인하고, 그렇다면 더 정제된 타입 pat_code를 부여한다. 예:
let t1 = .<fun x -> x>. [@metaocaml.functionliteral]
(* val t1 : ('a -> 'a) Trx.pat_code = <abstr> *)
let t2 = .<function [] -> true | (_::_) -> false>. [@metaocaml.functionliteral]
(* val t : ('a list -> bool) Trx.pat_code = <abstr> *)
let t3 = .<let x = function () -> () in x>. [@metaocaml.functionliteral]
let t3 = .<let x = function () -> () in x>. [@metaocaml.functionliteral];;
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
Error: The expression does not appear to be a functional literal as requested
주석은 추론된 타입을 보여준다. 함수 리터럴로 보이지 않는 코드에 이 애트리뷰트를 붙이면, 마지막 예 t3처럼 타입 오류가 난다. 자세한 내용은 1급 패턴 매칭 절을 보라.
다른 브래킷 수정 애트리뷰트는 metaocaml.value 이다. 이것도 주장으로, 브래킷된 표현식이 실제로 값(상수, 변수 참조, 상수 튜플 등)을 나타냄을 뜻한다. 정말 그렇다면, 타입 검사기는 브래킷된 표현식에 더 정제된 타입 val_code를 부여한다. 그렇지 않으면 오류가 보고된다. 자세한 내용과 예시는 아래 let 삽입 절을 보라.
MetaOCaml N104 이후 버전은 정적으로 절의 개수가 미지인 match ... with ... 표현식을 생성할 수 있다. 이는 런타임에 임의의 패턴을 구성하는 길로 가는 첫 단계다. 이런 1급 패턴 매칭은 이전의 어떤 MetaOCaml/MetaML에서도 없던 것이다. 저수준 Template Haskell(편리한 quasi-quotation 바깥)과 Scheme도 패턴 매칭 표현식을 동적으로 만들 수 있지만, 결과가 의미가 있는지에 대한 보장을 전혀 제공하지 않는다. MetaOCaml은 보장한다. 아래 make_match가 만드는 match는 문법/타입이 올바름이 보장된다. Rhiger의 패턴 조합자도 타입 안전을 제공하지만, 타입이 극도로 복잡하다. 조합자 사용 실수 시 오류 메시지는 거의 이해 불가하다. 대조적으로, MetaOCaml의 1급 패턴 매칭은 놀랍도록 단순하다.
MetaOCaml의 1급 패턴 매칭이 극도로 단순한 이유는 OCaml이 이미 패턴 매칭 절을 위한 편리한 문법을 갖고 있기 때문이다. 실제로 .<function [1] -> 0>. 같은 친숙한 함수 리터럴은 패턴 매칭 절이다. 우리는 코드 값이 함수 타입일 때 실제 리터럴임을 보장( metaocaml.functionliteral 애트리뷰트로)하고, 그런 리터럴을 모아 match 문을 만들기만 하면 된다. 예:
(* defined in codelib.mli *)
val make_match : 'a code -> ('a -> 'w) pat_code list -> 'w code
let p = [.<function [1] -> 0>. [@metaocaml.functionliteral]; .<fun [x] -> x+1>. [@metaocaml.functionliteral] ]
let c = make_match .<[2]>. @@ [.<fun [] -> 0>. [@metaocaml.functionliteral] ] @ p @ [.<fun (x::y) -> x+1>. [@metaocaml.functionliteral] ]
이는 다음과 같은 match 표현식을 생성한다:
val c : int code = .<
match [2] with
| [] -> 0
| 1::[] -> 0
| x_14::[] -> x_14 + 1
| x_12::y_13 -> x_12 + 1>.
더 많은 예시는 metalib 라이브러리의 test 디렉터리의 pattern.ml을 보라. 남은 것은 정적으로 미지인 패턴(예: 정적으로 미지인 상수에 대한 매칭)의 생성이다. 사실, when 가드를 통해 어느 정도 가능하다(앞서 언급한 샘플 코드 참고).
Morten Rhiger: Type-Safe Pattern Combinators
J. Functional Programming, v19, March 2009, pp. 145-156
let 삽입의 중요성은 아무리 강조해도 지나치지 않다. 원래는 let 삽입을 구현하려고 제한 연속 라이브러리 delimcc가 개발되었다. let 삽입은 제한 연속 같은 효과와 스테이징을 결합하려는 주된 동기였다. 자세한 논의는 해당 논문들을 참고하라.
let 삽입의 중요성과 보편성을 감안하여, 이를 MetaOCaml의 네이티브 프리미티브로 제공하는 것이 합당해 보였다. 이제 더 이상 제한 연속이나 이펙트 라이브러리 같은 외부 의존이 필요 없다. MetaOCaml은 이미 스코프 유출 탐지를 위해 표현식의 자유 변수를 추적한다. let 삽입을 추가하는 일은(중첩 때문에 그리 단순하진 않지만) 그다지 복잡하지 않다.
N104부터, BER MetaOCaml은 외부 라이브러리나 제한 연속 없이 네이티브로 let 삽입을 지원한다. 먼저, 'a code의 부분타입으로 'a val_code를 도입한다. 이는 문법적으로 값(식별자 참조, 상수, 람다식 등)인 프로그램 파편을 나타낸다. 이런 파편은 효과 중복이나 평가 순서를 염려하지 않고 여러 번 자유롭게 스플라이스할 수 있다. 'a val_code 인자를 받는 코드 생성 함수는 스테이징 주석을 지우면 콜바이밸류 함수처럼 동작한다. val_code는 언제든 code로 변환(강제)할 수 있다.
'a val_code 값을 만드는 한 가지 방법은 metaocaml.value 애트리뷰트가 붙은 브래킷을 사용하는 것이다:
fun x -> .<(1,function y -> y + .~x)>. [@metaocaml.value]
(* inferred type: int code -> (int * (int -> int)) val_code *)
이 애트리뷰트가 붙은 브래킷 표현식이 문법적으로 실제 값이 아니면 타입 오류가 난다.
'a val_code를 만드는 또 다른 방법은 다음과 같다:
genletv : 'a code -> 'a val_code
이 함수는 먼저 인자가 이미 값이고, 생성이 큰 할당을 요구하지 않음(즉 중복이 저렴함)을 확인한다. 그렇다면 그대로(단지 'a val_code 타입으로) 반환한다. 그렇지 않으면, genlet은 인자를 새 미래 단계 변수에 바인딩하는 let 문을 생성하고, 그 변수를 참조하는 코드를 반환한다. 변수 참조는 값임이 분명하다. 즉 genlet exp는 생성 코드 어딘가에 let freshname = exp in ... 를 삽입하고 .<freshname>. 을 반환한다. let은 exp가 포함하는 ‘가장 최근’ 자유 변수의 바인더 바로 아래에 삽입된다. 예:
.<fun x y -> x + y + .~(genlet .<x+1>.)>.
생성 결과:
- : (int -> int -> int) code = .<
fun x_1 -> let t_3 = x_1 + 1 in fun y_2 -> (x_1 + y_2) + t_3>.
(여기서 genlet은 genletv의 결과 'a val_code를 'a code로 강제한 뒤 스플라이스할 수 있게 한 합성이다.)
let으로 바인딩되는 변수의 이름은 genlet의 재량이지만, 선택 인자 ~name으로 힌트를 줄 수 있다:
.<fun x y -> x + y + .~(genlet ~name:"v" .<x+1>.)>.
이는 fun x_1 -> let v_3 = x_1 + 1 in fun y_2 -> (x_1 + y_2) + v_3>. 를 생성한다.
N111은 let 문을 어디에 삽입할지 사용자가 제어할 수 있게 한다. 이는 let으로 바인딩하여 이동하려는 표현식이 효과적일 때 종종 필요하다. 예를 들어 다음을 보자:
let sum_up =
let body arr =
let arr = genlet arr in
let sum = genlet ~name:"sum" .<ref 0>. in
.<for i=0 to Array.length .~arr - 1 do
.~sum := ! .~sum + (.~arr).(i)
done;
! .~sum>.
in .<fun x -> .~(body .<Array.map succ x>.)>.
결과는 다음과 같다:
val sum_up : (int array -> int) code = .<
let sum_6 = Stdlib.ref 0 in
fun x_4 ->
let t_5 = Stdlib.Array.map Stdlib.succ x_4 in
for i_7 = 0 to (Stdlib.Array.length t_5) - 1 do
sum_6 := ! sum_6 + Stdlib.Array.get t_5 i_7
done;
! sum_6>.
여기서 누산기 sum_6은 함수 바깥에 바인딩되어, sum_up 호출 간에도 누산된다. 이는 아마 프로그램 의도와 다를 것이다. 간단한 수정으로 해결할 수 있다:
let sum_up =
let body arr =
with_locus @@ fun locus ->
let arr = genlet arr in
let sum = genlet ~name:"sum" ~locus .<ref 0>. in
.<for i=0 to Array.length .~arr - 1 do
.~sum := ! .~sum + (.~arr).(i)
done;
! .~sum>.
in .<fun x -> .~(body .<Array.map succ x>.)>.
이제 누산기는 함수 내부에 머문다:
val sum_up : (int array -> int) code = .<
fun x_8 ->
let t_10 = Stdlib.Array.map Stdlib.succ x_8 in
let sum_11 = Stdlib.ref 0 in
for i_12 = 0 to (Stdlib.Array.length t_10) - 1 do
sum_11 := ! sum_11 + Stdlib.Array.get t_10 i_12
done;
! sum_11>.
with_locus는 genlet ~locus 바인딩의 스코프 상한을 지정한다. 바인딩은 스코프 유출을 피하기 위해 더 이르게 삽입될 수도 있다.
마지막으로, BER N111은 ‘즉시’ let 삽입도 제공한다:
let t = letl ~name:"v" .<1+2>. (fun v -> .<4 + .~v>.)
이는 .<let v_3 = 1 + 2 in 4 + v_3>. 를 생성한다. 본질적으로 with_locus 직후에 이어지는 genlet이다. 일반 genlet과 마찬가지로, 바인딩할 표현식이 단순(큰 메모리 할당을 수반하지 않는 값)하면 let은 생성되지 않는다.
더 많은 예시는 metalib/test의 genlet.ml을 보라. fib.ml은 메모이제이션과 let 삽입을 결합한 더 큰 예시를 제공한다.
Shifting the Stage: Staging with Delimited Control
BER N111은 let rec 삽입, 즉 정적으로 크기를 알 수 없는 상호 재귀 바인딩 그룹을 생성하는 기능을 도입한다. 이런 그룹은 브래킷과 이스케이프만으로는 생성할 수 없다: 표현식만 브래킷/스플라이스할 수 있고, 개별 바인딩 var = exp는 표현식이 아니기 때문이다. 따라서 BER N111은 두 가지 프리미티브를 도입한다.
type locus_rec
val with_locus_rec : (locus_rec -> 'w code) -> 'w code
val mkgenlet : ?name:string -> (* 바인딩 이름 힌트 *)
locus_rec -> (* with_locus_rec가 만든 로커스 *)
('key->'key->bool) -> (* 메모 키 비교 *)
(* 결과: genletrec — 키를 받아 바인딩할 표현식을 생산하는 함수를 받아,
해당 키에 대한 바인딩/참조 코드를 생성 *)
(('key -> ('a->'b) code) -> 'key -> ('a->'b) code)
여기서 with_locus_rec은 앞서 설명한 with_locus와 유사하게, 결국 생성될 let rec의 스코프를 표시한다. mkgenlet은 ‘메모이징 genletrec’을 만들어 준다. 동작은 예시로 설명하는 편이 낫다.
예시는 Neil Jones의 부분 평가기 벤치마크인 Ackermann 함수 특화다.
let rec ack m n =
if m = 0 then n+1 else
if n = 0 then ack (m-1) 1 else
ack (m-1) (ack m (n-1))
도전과제는 m의 특정 값에 특화된 코드를 만드는 것이다. 앞서 power 예시처럼 스테이징 주석을 추가하면 대략 다음과 같다:
let sack m =
let rec loop m =
if m = 0 then .<fun n -> n + 1>. else
.<fun n -> if n = 0 then .~(loop (m-1)) 1
else .~(loop (m-1)) (.~(loop m) (n-1))>.
in loop m
아쉽게도 이 생성기를 양의 m에 적용하면 무한 루프에 빠진다. m ≠ 0일 때 loop m의 결과가 loop m에 의존함이 분명하다. 재귀 정의, 사실 사용자 입력 값까지 포함해 0에서 그 값까지 모든 m에 대한 여러 정의를 만들어야 한다. 이는 사실 꽤 쉽다: mkgenlet으로 ‘바인딩 생성기’ g를 얻고, 모든 loop 호출 앞에 맹목적으로 삽입한다:
let sack m =
with_locus_rec @@ fun l ->
let g = mkgenlet l (=) in
let rec loop m =
if m = 0 then .<fun n -> n + 1>. else
.<fun n -> if n = 0 then .~(g loop (m-1)) 1
else .~(g loop (m-1)) (.~(g loop m) (n-1))>.
in g loop m
그러면 sack 2는 원하는 결과를 낸다:
val sac2 : (int -> int) code = .<
let rec h_6 n_7 = n_7 + 1
and h_4 n_5 = if n_5 = 0 then h_6 1 else h_6 (h_4 (n_5 - 1))
and h_2 n_3 = if n_3 = 0 then h_4 1 else h_4 (h_2 (n_3 - 1)) in h_2>.
PEPM 2019 and 2022 papers 자세한 논의가 있으며, 결국 MetaOCaml에 구현된 인터페이스에 이른다.
BER MetaOCaml 배포본의 test/genletrec.ml은 더 많은 예시를 보여주며, 스키마적 설명에서 유한 오토마타를 생성하는 사례도 포함한다.
브래킷된 표현식(즉, 생성할 코드의 템플릿)은 열린 표현식일 수 있다: 자유 변수를 포함하는데, 이를 단계 교차 지속(Cross-Stage Persistent, CSP) 변수라 부른다. Tim Sheard의 “Accomplishments and Research Challenges in Meta-programming”(SAIG 2001)에서 예시를 빌리고 변형하자:
let f x = x + 1
let z = .<f 4 + 5>.
let f x = not x in Runcode.run z
z에 바인딩된 코드 값에는 자유 변수 f가 포함되어 있다. 이는 z가 정의될 때 스코프에 있던 int->int 함수 f를 가리키지, z가 실행될 때 스코프에 있는 f:bool->bool를 가리키지 않는다. 즉 CSP 변수도 다른 변수처럼 렉시컬 스코프를 따른다. CSP는 광범위하다: 예컨대 위 코드 값 z에는 또 다른 자유 변수(=CSP)인 +가 있다. 이는 Stdlib에 바인딩된다. 모든 표준 라이브러리 연산은 따라서 CSP다.
CSP는 달리 볼 수도 있다: 동일한 표현식/값/식별자를 여러 단계(지금과 나중)에서 쓰는 능력이다. 예를 들어 Stdlib.succ는 지금 정수를 증가시킨다: succ 1. 미래 단계 표현식 .<succ 1>. — 나중에 이 코드가 컴파일/실행될 때 1을 증가 — 도 같은 succ를 참조한다. 이런 참조가 CSP다. 이 절에서는 원조/BER MetaOCaml의 CSP, 그 문제점, 그리고 현재 구현을 설명한다. 계산들에 존재하는 CSP 표현식은 항상 CSP 식별자로 환원하여 흉내낼 수 있다(예: .<.~(let x = e in .<x>.)>.). 따라서 아래에서는 CSP 식별자만을 다룬다.
lambda^a(Taha and Nielsen, 2003), lambda_i(Calcagno, Moggi, Taha, 2004) 같은 스테이징 계산은 CSP에 제약을 두지 않는다. MetaOCaml도 마찬가지여서 다음을 쓸 수 있다:
let polylift x = .<x>.;;
val polylift : 'a -> 'a code = <fun>
이런 다형적 CSP는, 현실 세계 스테이징 언어의 작고 순수한 부분집합을 형식화하는 계산에서는 잘 정의된다. 그러나 그 부분집합을 벗어나면 문제가 생긴다. 예컨대 변경 가능한 셀이나 입력 채널의 CSP의 의미는 무엇인가?
let r = ref 0 in
let x = run .<let () = r := 1 in !r>. in
(x, !r)
let c = open_in "/etc/motd" in .<c>.
in_channel code = .<(* cross-stage persistent value (id: c) *)>.
위에서 r은 단계 간에 공유되는가, 복사되는가? .<c>.가 나중에 실행될 때, 지금 열린 파일은 무엇을 가리킬 수 있는가? 생성 코드는 파일로 저장되어 라이브러리로 컴파일되고, 생성기와 다른 컴퓨터에서 실행될 수 있는 프로그램에 링크될 수도 있다. 특화된 계산 커널 라이브러리 생성은 MetaOCaml의 중요한 응용이다. 한편, 변경 가능한 셀/열린 채널의 CSP는 런타임 코드 특화에서는 의미가 있을 수 있다.
글로벌 식별자의 CSP와 로컬 식별자의 CSP를 구분하는 것이 중요해 보인다. 우연히 Template Haskell에도 그런 구분이 있다. succ 같은 글로벌 식별자를 참조하는 .<succ>. 는 .<1>. 과 다를 바 없어 보인다. 결국 1과 succ는 타입이 다른 ‘상수’다. 계산/논리를 정의할 때 흔히 “적절한 타입/아리티를 가진 상수들의 집합 Sigma(숫자, succ 등)를 가정”으로 시작한다. 코드
let x = 1 in
let y = .<1>. in ...
의 첫 줄 1은 현재 단계 계산의 Sigma(“표준 라이브러리 상수”)의 상수를, 둘째 줄 1은 다음 단계의 Sigma의 원소를 가리킨다. 다음 코드도 동일하게 해석되어야 한다:
let x = succ in
let y = .<succ>. in ...
양 단계의 Sigma가 동일해야 함이 핵심이다. 즉 생성기를 실행하는 컴퓨터와 생성 코드를 실행하는 컴퓨터는 동일한 표준 라이브러리(광의로 사용자 라이브러리, .cmi, .cmo 포함)를 가져야 한다. 따라서 글로벌 식별자의 CSP는 표준 라이브러리에 대한 참조로 이해되어야 한다. 이런 CSP는 ‘공통 지식’으로, 모든 단계에 존재한다.
로컬 식별자의 CSP는 lift(직렬화)로 해석되어야 하며, 특정 타입에서만 유효하다. 그러므로 let x = 1 in .<x+2>. 는 let x = 1 in .<.~(lift_int x) +2>. 로 해석되어야 한다. 여기서 lift_int는 정수 값을 직렬화하는 내부 함수다. 직렬화는 항상 값을 복사한다. 값이 직렬화 불가/매우 곤란하다면? 사용자 정의 데이터 타입에 대한 lift 같은 함수를 어떻게 추가하나? 이는 어렵고, 이제야 답을 얻었다.
우선, 코드 값의 ‘글로벌’ 변수(현재 컴파일 단위 밖에서 바인딩)는 해당 ‘라이브러리’ 식별자에 대한 참조로 해석된다. 타입에 제약이 없다. 다음은 ‘로컬’ CSP(현재 컴파일 단위에서 바인딩된 식별자)에 관한 것이다:
요약하면, 쉽게 직렬화 가능한 값은 값에 의해(복사) 해석되고, 그 외는 참조에 의해 해석된다.
N107부터 MetaOCaml은 다음 시그니처의 리프팅 모듈 모음도 제공한다:
module type lift = sig
type t
val lift: t -> t code
end
이를 통해 option, list, array 타입의 값을 들어 올릴 수 있다. 특정 CSP를 직렬화해야 한다면 이런 리프터를 사용하는 것을 권장한다.
Reconciling Abstraction with High Performance: A MetaOCaml approach
서적의 3.2.1절 “A Digression on CSP”가 명시적 리프팅을 설명하며, N107 이후(리스트/옵션, 특히 배열 리프팅 포함) 구현되어 있다.
MetaOCaml에는 광범위한 연구개발 계획이 있다. 연구 측면에서는 객체, 모듈, GADT를 반영하는 스테이징 계산을 개발하는 일이 있다. 모듈과 객체는 바인딩 형태이므로 스테이징이 복잡하다. 적절한 이름 변경과, 생성된 식별자가 결과 코드에서 미바인딩으로 남지 않음을 확인해야 한다. 또한 스테이징과 (최근 1급이 된) 모듈의 통합도 흥미롭다. 둘 다 코드에 대한 추상화이므로, 스테이징을 모듈 시스템으로 사용할 수 있을까? 또 다른 주제는 CSP 제약이 일반화의 비정합 문제를 피함을 증명하는 것이다.
사용자 영역 개발은 더 광범위하다: 코드 값을 C, Fortran, LLVM, Verilog로 변환해 ‘실행’하는 더 많은 방식을 원한다. 그러면 MetaOCaml은 특화된 C 등 코드 라이브러리 생성을 위해 사용할 수 있다. 사용자 영역 MetaOCaml 개발은 진입 비용이 가장 낮다(OCaml 내부를 알 필요 없음) 그리고 개발자들에게 활짝 열려 있다. 누구나 기여할 수 있고, 모두 환영한다.
BER MetaOCaml은 원조 MetaOCaml에서 나왔고, 그 구현에서 얻은 교훈에 크게 빚지고 있다. BER MetaOCaml은 효과가 검증된 것 위에 세워졌다. 동기가 MetaOCaml의 역사에서 분명해진다.
원조 MetaOCaml CVS 저장소의 흥미로운 파일 하나에는 2000년 9월 29일 파리에서 Xavier Leroy와 Walid Taha가 가진 회의의 짧은 메모들이 있다. 그중 하나가 눈에 띈다: “우리는(Xavier!) ‘run bracket 1’을 컴파일하고 실행할 수 있었다!!” 이 순간을 MetaOCaml의 탄생으로 볼 수 있겠다.
MetaOCaml은 MetaML의 방향을 따라 OCaml의 포크로 시작했다. Walid Taha가 설계/아키텍처를 맡고 Cristiano Calcagno가 개발을 맡아, 2003년쯤 현재 형태에 도달했다. 환경 분류자는 그해 말에 도입되었다. 네이티브 코드 컴파일과 오프쇼어링(생성 코드를 C/Fortran으로 변환)은 2004년에 추가되었다.
MetaOCaml이 개발되는 동안, 메인라인 OCaml도 수많은 수정/개선과 함께 새 버전을 발표했다. MetaOCaml 팀은 새로운 OCaml 릴리스를 추적하여 변경을 통합했다(MetaOCaml 버전 번호는 기본적으로 OCaml 릴리스 버전을 따른다). 통합은 고통스러웠다. 예컨대 OCaml 컴파일러에서 Parsetree(AST)나 Typedtree를 다루는 새로운 함수가 나오면, MetaOCaml이 이 자료구조에 추가한 확장을 처리하도록 반드시 수정해야 했다. 언어가 갈라질수록 통합 과정은 더욱 고통스러웠다. 예를 들어 MetaOCaml 3.07에서 처음 등장한 네이티브 컴파일은 동적 링크를 지원하기 위한 malc@pulsesoft.com의 OCaml 대규모 패치 SCaml에 의존했다. OCaml 3.08은 SCaml과 호환되지 않는 많은 변경을 가져왔다. 따라서 MetaOCaml 3.08에서 네이티브 컴파일 모드는 망가졌다. 이 모드는 2005년 여름에 SCaml 패치를 재공학하고, 동적 링크에 필요한 부분을 OCaml 수정 없이 구현하여 되살렸다. 부활한 네이티브 컴파일은 끝까지 살아남았다.
2006년 MetaOCaml은 Concoqtion의 기반이 되었다. OCaml과 MetaOCaml의 증가하는 괴리는 변경 통합을 점점 더 어렵게 만들었다. 프로젝트 자금이 바닥나고, OCaml 3.10과 3.11의 많은 변경을 통합해야 하는 암담한 전망 속에서 MetaOCaml 개발은 중단되었다. 마지막 공개 버전은 3.09.1 alpha 030이었다.
원 개발팀이 더 이상 MetaOCaml을 지원할 수 없게 되었지만, 사용자들(특히 Jacques Carette)은 프로젝트가 사장되는 것을 못 견뎠다. 그의 촉구로 2010년 2월 OCaml 3.11 변경 통합이 착수되었다. 자금 부족과 제한된 자원은 메인라인 OCaml과 최대한 가까이 머물며 괴리를 피해야 했다. 스테이징과 직접 관련 없는 모든 것(태그 제거, Concoqtion 등)은 제거했다. MetaOCaml이 영향을 주는 OCaml 배포본 파일 수는 23개 줄었다. Walid Taha는 새로운 최소선 MetaOCaml에 BER MetaOCaml이라는 이름을 제안했다. 첫 버전 N002는 2010년 3월 1일 공개되었다.
BER MetaOCaml은 커널과 사용자 수준의 분리를 확립했다. OS 커널과 마찬가지로, MetaOCaml 커널 변경은 ‘리부팅’(MetaOCaml 재컴파일)을 요구하고 시스템을 쓸 수 없게 할 수도 있다. 사용자 수준 변경은 개별 프로그램에만 영향하며 개발이 쉽다. MetaOCaml 커널은 코드 값을 생성/타입검사하는 책임을 지고, 사용자 수준은 코드 값을 처리(예쁘게 출력, 실행, 바이트/네이티브 컴파일, C 등으로 변환)한다. 프로그래머는 코드 값을 처리하는 새로운 방식을 — 예컨대 LLVM/JavaScript로 컴파일 — OCaml이나 BER MetaOCaml을 수정하지 않고도 작성할 수 있다. BER N002 배포본에서 커널은 OCaml에 대한 59KB 패치와 54KB 길이의 typing/trx.ml로 구성되었고, 사용자 수준은 pretty-printer(59KB 소스)와 생성 코드의 바이트코드 실행/커스텀 톱레벨 지원(합계 3KB)로 구성되었다. 테스트 코드는 20KB 있었다.
OCaml에 대한 59KB 패치는 커 보인다. 일부는 불가피하다. BER MetaOCaml이 AST 자료형 Parsetree를 스테이징 구문(Pexp_bracket, Pexp_escape, Pexp_run, Pexp_cspval)으로 확장했기에, AST를 처리하는 OCaml의 모든 부분을 수정해야 했다. 컴파일러의 많은 부분이 AST를 다룬다. 다단계 언어에서는 각 표현식이 현재 단계 또는 점점 미래인 단계의 레벨과 연관된다. 원조 MetaOCaml은 각 식별자에 대한 타입 및 기타 정보를 유지하는 value_description 레코드의 추가 필드 val_level에 레벨을 저장했다. 식별자에서 value_description으로 가는 맵이 타입 환경이므로, 타입 검사기 전반에서 사용된다. 따라서 새 필드를 추가하면 대대적인 변경이 필요했다. 새로운 OCaml 버전은 타입 검사기를 크게 바꾸곤 했다. 이런 변경을 MetaOCaml에 통합하면서 새 필드 val_level을 반영하는 것은 어려운 작업이었다. 하지만 피할 수 있다: 식별자와 레벨을 다르게 연관시키자 — 환경에 새로운 맵을 추가하여, 각 ‘미래 단계’ 식별자의 레벨을 기록한다. 이 맵에 없는 식별자는 현재 단계로 간주한다. 그러면 value_description은 그대로다. BER MetaOCaml N100(아래 참조)은 이 경로를 택했다. 원조 MetaOCaml은 생성 코드에서 사용하는 데이터 생성자에 대한 정보를 저장하려고 AST를 더 수정했다(실제로는 생성 코드에 대응하는 AST가 현재 단계 타입 검사기의 전체 환경을 포함). 이로써 많은 OCaml 패치가 생겼다. BER N100은 이 페이지 다른 곳에서 설명한 생성자 제약을 도입하여, 여분의 AST 수정과 추가 패치의 필요를 제거했다. 즉, MetaOCaml을 OCaml에 더 가깝게 가져가려는 목표라면, OCaml에 대한 수정량을 최소화할 수 있다 — BER N100이 보여주었듯.
OCaml 3.12 릴리스는 1급 모듈 등 뜻밖에 많은 새 기능을 언어에 가져왔다. OCaml 4.0은 GADT와 동적 링크를 추가했다. 이렇게 많은 변경을 BER MetaOCaml N002에 통합하는 일은 우울했다. BER MetaOCaml N100은 2013년 1월 개발되어 1월 31일 공개된, 깨끗한 상태에서의 재구현이다. MetaOCaml 브랜치에 OCaml 4.0을 머지하는 대신, BER N100은 새로 시작했다. OCaml 배포본을 가져와, 스테이징 구문을 AST에 추가하고, 그 구문이 완전히 처리될 때까지 — OCaml 코드 전반의 패턴 매칭이 빠짐없이 exhaustive가 될 때까지 — 코드를 보탰다. 이 exhaustiveness 검사가 매우 도움이 되었다. OCaml 자료구조를 가능한 한 적게 수정하는 데 주의를 기울였다. BER N100 분해: 커널은 49KB 패치(28개 파일 수정, 이 중 6개는 사소)와, 주석이 매우 많은 77KB 길이의 완전히 다시 쓴 typing/trx.ml로 구성되었다. 사용자 수준에는 Jacques Carette가 크게 수정한 58KB pretty-printer, 톱레벨과 run 지원을 위한 소규모 파일(총 3KB)이 포함되었다. 테스트는 54KB였고, 처음으로 회귀 테스트 모음도 포함했다. BER N100은 OCaml에 덜 침습적이다: 스테이징 구문 타입검사의 대부분 변경이 담긴 OCaml 메인 타입 검사기 typing/typecore.ml에 대한 패치 크기를 비교하라. 이전 BER N004에서는 추가/삭제/컨텍스트 합쳐 564줄이었으나, 이제 328줄뿐이다.
BER MetaOCaml N101(2013년 11월 공개)은 MetaOCaml을 더 정리했다. 스코프 유출 검사에 대한 긍정적 경험을 바탕으로 환경 분류자를 제거하여 스테이징 구문 타입검사를 눈에 띄게 단순화했다. 코드 실행 연산은 더 이상 전용 타입검사 규칙이 필요 없게 되었다. N101에서 이는 일반 함수가 되어 MetaOCaml 커널 밖으로 이동했다. 내부적으로 N101은 스코프 유출 검사를 개선하고, 특히 바인딩 형태의 스테이징 구문 번역을 최적화했다. 코드의 pretty-print는 OCaml 자체의 일부가 되어 별도로 유지할 필요가 없어졌다.
2015년 1월 1일 공개된 N102는 사용자에게 거의 보이지 않는 변화지만 또 하나의 큰 재작성이다. N102 코드는 OCaml 4.02의 새 기능인 애트리뷰트를 광범위하게 사용한다. 스테이징 주석 — 브래킷, 이스케이프, CSP — 은 이제 진짜로 주석(Parsetree/Typedtree의 애트리뷰트)이다. Typedtree에는 비확장성(non-expansive) 노드를 표시하는 전용 애트리뷰트를 붙인다(비확장성 검사는 브래킷 번역 전 수행되지만, 사용은 번역 후). value_description에 붙는 애트리뷰트는 값의 스테이징 레벨을 나타낸다. 타입검사 후 브래킷/이스케이프를 번역하는 별도 Typedtree 순회가 더 이상 없다. 이는 스테이징 주석이 없는 코드에는 MetaOCaml 오버헤드가 사실상 없음을 의미한다. N102는 CSP 재정비를 시작했고, 상당수 CSP가 출력/직렬화 가능해졌다. 직렬화 불가 CSP는 네이티브 MetaOCaml의 유일한 걸림돌이었다. MetaOCaml이 수정하는 OCaml 배포본 파일 수는 32개에서 7개로 감소했다. 패치 크기는 34KB로 줄었다. 이제 MetaOCaml이 포크가 아니라 일반 라이브러리/플러그인이 될 가능성이 뚜렷해졌다.
N104(2017년 1월 1일)는 네이티브 MetaOCaml을 되살리고, MetaOCaml/MetaML에 없던 두 가지 새로운 기능 — 1급 패턴 매칭과 let 삽입 프리미티브 — 을 구현했다.
N107(2018년 10월 5일)은 다른 방식으로 오프쇼어링을 되살리고 명시적 리프팅을 추가했다. 코드 타입은 더 이상 특별/사전정의되지 않으며(이는 MetaOCaml이 수정하는 OCaml 파일이 렉서/파서/프리티프린터/typecore.ml 네 개뿐임을 의미),
N111(2020년 10월 5일)은 let rec 삽입(정적으로 크기를 알 수 없는 상호 재귀 정의 생성)을 추가했다. let 바인딩 표현식이 효과적일 때 종종 필요한 let 삽입 스코프 제어도 가능해졌다. 스코프 올바름 보장은 여전히 유지된다. 오프쇼어링도 더 다듬어졌다.
N114(2023년 5월 11일)은 오프쇼어링을 재구현하며, 정규화(@@와 |> 제거, 중첩 let 평탄화, 가능/쉬운 let 리프팅 등)를 추가했다. 변경 가능한 변수와 포인터 타입을 제약 없이 지원한다. 오프쇼어링은 이제 C99 코드 출력까지 완전히 지원한다. offshoringIR 중간 언어는 MetaOCaml 밖(예: C/WASM 생성)에서도 사용할 수 있다. CSP가 재구현되어, 직렬화 불가 CSP는 최상위 let 바인딩으로 변환된다. 이제 Parsetree 확장 노드 metaocaml.bracket, metaocaml.escape를 사용한다. 렉서는 적응형으로, 첫 .<(여는 브래킷)을 보기 전까지 .>를 OCaml 그대로 렉싱한다.
N153(2025년 5월 6일)은 MetaOCaml을 OCaml 5.3.0과 나란히 가져간다. OCaml 5.x는 특히 함수 관련하여 AST(Parsetree)와 Typedtree를 크게 변경했다. MetaOCaml을 이에 맞추는 데 작업이 필요했다. 스테이징 주석 관련 OCaml 문법 패치를 병합해준 OCaml 팀에 깊이 감사드린다. 덕분에 MetaOCaml 유지보수가 크게 쉬워졌다.
새 언어를 개발하고 특히 유지보수하는 일은 거대한 작업이다. 잘 유지되는 언어의 방언으로 공학하는 일은 어렵지만, 많은 보답을 준다.
The MetaOCaml files: Status report and research proposal
2010 ACM SIGPLAN Workshop on ML 비공식 프로시딩에 실린 확장 초록
ml2013-talk.pdf[200K]
MetaOCaml은 계속된다: 함수형 언어의 단계적 방언을 구현하며 얻은 교훈
2013년 9월 22일, ACM SIGPLAN Workshop on ML, Boston, MA, USA 발표의 주석 달린 슬라이드
The Design and Implementation of (BER) MetaOCaml
BER MetaOCaml은 원조 MetaOCaml의 완전한 재구현이다.
원조 MetaOCaml은 Walid Taha가 이끈 NSF 프로젝트 “ITR/SY(CISE): Putting Multi-Stage Annotations to Work”의 지원을 주로 받아 개발되었다. 원래의 스테이징 개발/구현 대부분은 Cristiano Calcagno가 수행했다. Edward Pizzi가 코드 프리티프린팅을 구현했고, 이후 Jacques Carette가 수정했다. Xavier Leroy(INRIA)는 컴파일러 관련 사항을 도왔다.
Jacques Carette, Walid Taha, Jeremy Yallop, Yukiyoshi Kameyama와 츠쿠바 대학 그의 연구실 구성원들, Chung-chieh Shan, Cedric Cellier, Jun Inoue에게 많은 유익한 토론과 격려에 깊이 감사드린다. Tran Minh Quang, Mustafa Elsheik, Nicolas Ojeda Bar의 리포트와 테스트에도 감사한다.