메타 순환 평가기: Mere가 Mere를 돌리다

프론트엔드는 이제 Mere를 읽고 다시 쓸 수 있다, 두 방식으로 검증되어. 명백한 다음 바람, 그리고 브라우저 데모가 구체로 만든 것 —— 파싱이 도니, 돌려 달라 —— 은, 평가기다. 평가기를 Mere로 쓰면, 이름과 작은 현기증이 붙은 무언가가 생긴다: 메타 순환 인터프리터, 그 같은 언어로 쓰인, 어떤 언어를 위한 인터프리터, 그러므로 자기 자신을 돌릴 수 있는.

타입 검사 전에 평가하기

이 셀프 호스트 노력의 더 큰 비전은 두 부품, 평가기와 타입 검사기였다. 평가기가 먼저 갔다, 이제 익숙한 패턴의 이유로: 둘 중, 더 단순하고, 더 즉각 설득적인 쪽이기 때문이다. 평가는 동적이다 —— 프로그램을, 그 트리를 걸으며 계산함으로써 돌리고, 타입을 먼저 알 필요가 없다 —— 그래서 타입 검사기가 아직 존재하는 것에 의존하지 않는다. 그리고 눈에 띄게 보답한다: 평가기는, 브라우저 데모를 “코드를 붙여 정형되는 것을 본다”에서 “코드를 붙여 도는 것을 본다”로 바꾼다. 타입 검사기는 더 어려운 기계로, unification과 일반화를 세워야 하므로, 어려운 부분 전에 땅을 다지고자, 평가기가 먼저 간다.

인터프리터의 대부분은 인터프리터가 아니다

OCaml 평가기는 이천 줄 가깝고, 그것은 Mere로 재현하기 벅차게 들린다 —— 줄이 어디로 가는지를 보기 전까지는. 그 약 오분의 사가 내장 함수다: print, 문자열 조작, list와 vector와 map의 조작, 파일의 입출력, 그 외 수십. 그것들은 인터프리터가 아니다. 그것들은 표준 라이브러리이고, 전혀 셀프 호스트를 요하지 않는다 —— 그것들은 런타임이 이미 제공하는 primitive이고, 어느 Mere 프로그램이나 그러듯 같은 방식으로, 셀프 호스트 평가기에서 닿는다.

그것들을 벗겨내면, 실제로 Mere로 써야 할 것은 작다: 도는 프로그램의 값이 어떻게 보이는지를 기술하는 값의 타입, 이름을 값에 대응시키는 환경, 패턴 매처, 그리고 트리 워커의 심장에 있는 디스패치 —— 식과 환경을 받아 값을 낳는, 재귀 함수다. OCaml의 이천 줄에 대해 아마 이백 줄. 다시 쓰지 않아도 되는 것을 아는 것이, 셀프 호스트를 다루기 쉽게 만드는 것의 절반이다: 인터프리터의 코어는 정말로 작고, 그리고 그것이 작은 것은, 그것이 해석하는 언어가 작기 때문이다 —— 연재 초입의 최소 ML 코어가, 이제 작은 평가기로 보답받는다.

코어, 그리고 이제 익숙한 클로저

형태는 교과서적인 트리 워커가, Mere 자신의 타입으로 표현된 것이다. 값은 variant —— 정수, 진릿값, 문자열, 클로저, 등. 환경은 이름과 값의 쌍의 리스트로, 걸어서 조회된다. 그리고 평가기는, 식의 종류로 매칭하는 단일한 재귀 함수다: 변수는 환경에서 자신을 조회하고; 이항 연산은 양변을 평가해 결합하고; if는 조건을 평가해 가지를 취하고; 함수 적용은 함수와 인자를 평가해 한쪽을 다른 쪽에 적용한다.

멈춰 설 가치가 있는 한 조각은 클로저다. 그것은, 이 연재가 이제 네 다른 층에서 만난 같은 아이디어이기 때문이다. 평가기가 함수 식을 만나면, 함수의 본체 와 그 시점에 유효한 환경을 나르는 클로저 값을 만든다 —— 포획된 결속이, 클로저 값의 필드로서 직접 저장된다. 그것은 또다시 클로저 변환이지만, 여기서는 교묘함을 전혀 요하지 않는다: 포획된 환경은 그저 값, 클로저 안에 쥐어진 결속의 리스트다. 레퍼런스 인터프리터는 클로저를 OCaml에서 공짜로 얻었다; C backend는 그것을 heap의 env struct로 세웠다; Wasm backend는 그것을 메모리 offset과 테이블 인덱스로 갈랐다; 그리고 셀프 호스트 평가기는 포획된 환경을 평범한 variant 필드로 쥔다. 하나의 개념 —— 코드와 그것이 닫아 넣은 환경 —— 의 네 표현, 그 저마다가 자기 층에 맞춰지고, 이 마지막 것이 가장 직접적이다: 환경이 데이터 안에 거기 있다.

“메타 순환”이 실제로 사는 것

셀프 호스트 평가기는, 다른 어느 것과도 같은 Mere 프로그램이다. 같은 네 backend로 컴파일되고, 같은 바이트 단위의 parity에 유지되고, 프로그램의 코퍼스 위에서 OCaml 평가기에 대해 cross-validate된다 —— 지난 회의 하네스가, 이제 Mere로 평가한 결과가 OCaml로 평가한 것과 일치하는지를 체크한다. 그것은, 그것이 Wasm으로 컴파일되어 브라우저에서 돌 수 있음을 뜻하고, 데모는 dogfood signal이 요구한 것이 된다: Mere 프로그램을 붙이면, Mere의 인터프리터 —— 그 자신 Mere에서 컴파일된 —— 가 그것을 돌리고 결과를 보인다. Mere를 위한 REPL, 브라우저에서, Mere에 의해 돈다.

“메타 순환”이라는 말은 그저 장식이 아니다. 자기 언어를 해석할 수 있는 인터프리터는, 원리적으로 자기 자신을 해석할 수 있다 —— 평가기에 그 자신의 소스를 건넬 수 있다. 호기심의 대상 이상으로, 그것은 언어의 코어에 대한 증명이다: Part I과 II에서 골라진 feature —— variant, 재귀, 패턴 매칭, 클로저 —— 는, 바로 평가 그 자체, 언어가 가진 가장 근본적인 조작을 표현하는 데 드는 feature였다. 언어는, 자기 자신의 실행을 기술하기에 충분히 표현력이 있다고 판명되었다. 그것은, 작은 코어가 옳은 코어였다고 확인하는 조용한 방식이다.

평가기는, 프로그램의 타입을 개의치 않고 돌린다. 타입을 개의하는 부품 —— 타입이 붙지 않는 것을, 돌기 전에 거부하는 것 —— 은 더 어렵고, 그것이 다음이다. 그것은 Hindley–Milner 추론을 Mere로 다시 세우는 것을 뜻한다: unification, 일반화, 그 조용한 알고리즘 통째. 다음 회: 타입 검사기.