lisp-in-rs-macros는 Rust의 선언적 매크로만으로 동작하는 단순한 렉시컬 스코프 Lisp 인터프리터이며, lisp! 매크로가 코드를 컴파일 타임에 평가해 문자열화된 Lisp 값을 생성함lisp!(CAR (CONS (QUOTE A) (QUOTE (B))))는 rustc의 매크로 확장 과정에서 계산되어 문자열 "A"로 확장되며, 전체 구현은 250줄 미만임- 예제는
CAR, LIST, QUOTE, PROGN, DEFINE, LAMBDA, DISPLAY를 사용하며, quine 예제는 Lisp 코드가 자기 자신으로 평가되는 형태를 보여줌
- 명시적 재귀는 현재 지원하지 않지만, self application으로 리스트 append 같은 재귀 동작을 작성할 수 있음; 다만
DEFINE 자체는 재귀 정의를 처리하지 않음
- 메타서큘러 인터프리터 예제는 동작하는 것으로 보이지만,
((lambda (X) X) (quote a)) 평가가 30초 이상 걸리고 백만 개 이상의 토큰을 생성해 cargo가 sigkill될 정도로 비효율적임
Rust 매크로 안에서 실행되는 Lisp
lisp-in-rs-macros는 Rust의 선언적 매크로만으로 작성된 렉시컬 스코프 Lisp 인터프리터임lisp! 매크로는 전달된 Lisp 코드를 평가한 뒤, 계산된 Lisp 값을 문자열화함- 예를 들어
lisp!(CAR (CONS (QUOTE A) (QUOTE (B))))는 문자열 "A"로 확장됨
- 이 계산은 런타임이 아니라 rustc가 매크로를 확장하는 컴파일 타임에 일어남
- 구현은 250줄 미만임
기본 사용 예시
CAR, LIST, QUOTE를 조합해 리스트의 첫 원소를 가져올 수 있음
let output = lisp!(CAR (LIST (QUOTE A) (QUOTE B) (QUOTE C)));
assert_eq!(output, "A");
- 여러 식을 평가하려면
PROGN을 사용함
PROGN은 모든 식을 평가하고 마지막 식의 값을 반환함
DISPLAY는 인자를 먼저 평가한 뒤 println!("{}", stringify!(evaled_argument)) 형태로 확장해 토큰을 문자열화해 출력함
lisp!(PROGN
(DEFINE message (LAMBDA () (QUOTE "hello there")))
(DISPLAY (message))
(DEFINE NOT (LAMBDA (X) (COND (X NIL) (TRUE TRUE))) )
(DISPLAY (NOT NIL))
);
- 위 예제는
"hello there"와 "TRUE"를 출력함
자기 자신으로 평가되는 quine
- quine 예제는 Lisp 코드가 자기 자신으로 평가되는 형태를 보여줌
lisp!
((LAMBDA (s) (LIST s (LIST (QUOTE QUOTE) s)))
(QUOTE (LAMBDA (s) (LIST s (LIST (QUOTE QUOTE) s)))));
- 이 코드는 다음과 같은
stringify! 호출로 확장됨
stringify!(((LAMBDA (s) (LIST s (LIST (QUOTE QUOTE) s)))
(QUOTE (LAMBDA (s) (LIST s (LIST (QUOTE QUOTE) s))))));
재귀와 self application
- 이 Lisp는 현재 명시적 재귀를 지원하지 않음
- 명시적 재귀 없이도 lambda만으로 재귀적 동작을 만들 수 있음
- 예제의
append 함수는 본문에서 append 이름을 직접 언급하지 않고, self 인자를 통해 자기 적용으로 재귀 호출을 수행함
lisp!(PROGN
(DEFINE append
(LAMBDA (self X Y)
(COND
((EQ X NIL) Y)
(TRUE (CONS (CAR X) (self self (CDR X) Y)))
)))
(append append (QUOTE (A B)) (QUOTE (C D)))
)
- 이 코드는
"(A B C D)"를 결과로 만듦
사용상 제약
lisp! 매크로는 단일 식만 평가함
- 여러 식은
(PROGN expr1 expr2 expr3)로 묶어야 함
- 빈 리스트는 self-evaluating이 아님
- 빈 리스트 값은
NIL 또는 (QUOTE ())로 얻을 수 있음
- 빈 리스트는 유일한 falsy 객체임
- dotted list는 지원하지 않음
DEFINE은 어디서나 사용할 수 있고 빈 리스트로 평가되지만, 재귀는 지원하지 않음TRUE는 함수가 아닌 atom 중 유일하게 self-evaluating임
지원하는 form
DEFINE
QUOTE
LAMBDA
LET
PROGN
CAR
CDR
CONS
LIST
EQ
ATOM
APPLY
DEFINE은 진짜 Lisp식 재귀 정의라기보다 Scheme의 내부 정의에 가까운 형태임
Lisp로 작성한 Lisp 인터프리터
- 저장소에는 이 Lisp 위에서 작성한 메타서큘러 인터프리터 예제가 포함되어 있음
- 예제는 두 인자용
Y2 조합자, CADR, CAAR, ASSOC, eval 등을 정의함
- 인터프리터는 동작하는 것으로 보이지만,
((lambda (X) X) (quote a))를 평가하려고 하면 30초 이상 걸림
- 해당 평가는 백만 개가 넘는 토큰을 생성하고, 결국 cargo가 sigkill될 정도로 커짐
- 명시적 Y 조합자를 사용한 재귀는 여기서 특히 비효율적임
- 이를 고치기 위해 명시적 재귀 primitive를 추가해야 한다고 적고 있음
- 메타서큘러 평가기 작성 walkthrough로 Paul Graham의
"Roots of Lisp"를 추천함
구현 방식과 참고 자료
- 기술 설명은
EXPLANATION.md에 있음
- 매크로는 본질적으로 SECD machine을 시뮬레이션함
- SECD machine은 lambda calculus term을 평가하는 단순한 스택 기반 추상 기계임
참고 자료
Functional Programming: Application and Implementation by Peter Henderson- Ager, Mads Sig, et al.
"A functional correspondence between evaluators and abstract machines."
The Implementation of Functional Programming Languages by Simon Peyton Jones- Matt Might의 Lisp 관련 블로그 글: https://matt.might.net
TODO