GN⁺: Rust 매크로로 구현된 Lisp

(github.com/RyanWelly)

`lisp-in-rs-macros`

Rust의 선언적 매크로로 완전히 작동하는 간단한 렉시컬 스코프 Lisp 인터프리터. lisp! 매크로는 코드에 의해 계산된 Lisp 값을 확장하고 문자열로 변환함. 예를 들어, lisp!(CAR (CONS (QUOTE A) (QUOTE (B))))는 문자열 "A"로 확장되며, 모든 계산은 rustc가 매크로를 확장할 때 컴파일 시간에 발생함.

왜 중요한가

Rust의 매크로로 작성된 Lisp 인터프리터로, 매우 흥미로움. 또한 250줄 미만으로 작성되어 간결함.

예제

let output = lisp!(CAR (LIST (QUOTE A) (QUOTE B) (QUOTE C)));
assert_eq!(output, "A");

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이 있음:

lisp!((LAMBDA (s) (LIST s (LIST (QUOTE QUOTE) s))) (QUOTE (LAMBDA (s) (LIST s (LIST (QUOTE QUOTE) s)))));

이 코드는 자기 자신을 평가함.

재귀

이 Lisp는 현재 명시적인 형태의 재귀를 지원하지 않음. 다행히도, 명시적인 재귀는 필요하지 않으며, 람다만 있으면 됨. 두 리스트를 연결하는 간단한 함수를 작성할 수 있음:

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)"임. append 함수는 본문에서 append를 언급하지 않지만, 재귀적으로 호출할 수 있음.

사용 시 주의사항

lisp! 매크로는 단일 표현식만 평가함. 여러 표현식을 평가하려면 (PROGN expr1 expr2 expr3)을 사용해야 함.
DISPLAY 형식은 단일 표현식을 평가한 후 println!("{}", stringify!(...)) 문을 생성하여 토큰의 문자열 버전을 출력함.
빈 리스트는 자체 평가되지 않으며, 빈 리스트 값을 얻으려면 NIL 또는 (QUOTE ())를 사용해야 함.
점 리스트는 지원되지 않으며, cons는 마지막 인수가 리스트라고 가정함.
define 형식은 어디서나 사용할 수 있으며 빈 리스트로 평가되지만, 재귀를 지원하지 않음.
TRUE는 함수가 아닌 유일한 자체 평가 원자임.

지원되는 형식

DEFINE
QUOTE
LAMBDA
LET
PROGN
CAR
CDR
CONS
LIST
EQ
ATOM
APPLY

메타순환 인터프리터

다음은 Lisp로 작성된 Lisp 인터프리터임:

lisp!(PROGN
  (DEFINE Y2
    (LAMBDA (h)
      ((LAMBDA (x) (h (LAMBDA (a b) ((x x) a b))))
        (LAMBDA (x) (h (LAMBDA (a b) ((x x) a b)))))))
  (DEFINE CADR (LAMBDA (X) (CAR (CDR X))))
  (DEFINE CAAR (LAMBDA (X) (CAR (CAR X))))
  (DEFINE CADAR (LAMBDA (X) (CAR (CDR (CAR X)))))
  (DEFINE CADDR (LAMBDA (X) (CAR (CDR (CDR X)))))
  (DEFINE CADDAR (LAMBDA (X) (CAR (CDR (CDR (CAR X))))))
  (DEFINE CAADAR (LAMBDA (X) (CAR (CAR (CDR (CAR X))))))
  (DEFINE ASSOC (Y2 (LAMBDA (ASSOC) (LAMBDA (X ENV)
    (IF (EQ (CAAR ENV) X) (CADAR ENV) (ASSOC X (CDR ENV))))))
  )
  (DEFINE eval (Y2 (LAMBDA (EVAL) (LAMBDA (E A)
    (COND
      ((ATOM E) (ASSOC E A))
      ((ATOM (CAR E))
        (COND
          ((EQ (CAR E) (QUOTE quote)) (CADR E))
          ((EQ (CAR E) (QUOTE atom)) (ATOM (EVAL (CADR E) A)))
          ((EQ (CAR E) (QUOTE car)) (CAR (EVAL (CADR E) A)))
          ((EQ (CAR E) (QUOTE cdr)) (CDR (EVAL (CADR E) A)))
          ((EQ (CAR E) (QUOTE equal)) (EQ (EVAL (CADR E) A) (EVAL (CADDR E) A)))
          ((EQ (CAR E) (QUOTE cons)) (CONS (EVAL (CADR E) A) (EVAL (CADDR E) A)))
          (TRUE (EVAL (CONS (ASSOC (CAR E) A) (CDR E)) A))
        ))
      ((EQ (CAAR E) (QUOTE lambda)) (EVAL (CADDAR E) (CONS (LIST (CAADAR E) (EVAL (CADR E) A)) A)))
    ))))
  )
  (eval (QUOTE (quote (A))) NIL)
  (eval (QUOTE ((lambda (X) X) (quote a))) NIL)
);

이 코드는 작동하지만, 인터프리터에서 ((lambda (X) X) (quote a))를 평가하려고 하면 30초 이상 걸리며 백만 개 이상의 토큰을 생성함. 명시적인 y combinator를 사용한 재귀는 여기서 효율적이지 않음. 이를 해결하려면 명시적인 재귀 원시 기능을 추가해야 함. 메타순환 평가기를 작성하는 방법에 대한 훌륭한 설명은 Paul Graham의 "Roots of Lisp"를 참조.

기술적 설명

EXPLANATION.md를 참조. 매크로는 SECD 머신을 시뮬레이션하며, 이는 람다 계산식을 평가하기 위한 간단한 스택 기반 추상 머신임.

훌륭한 자료

Peter Henderson의 "Functional Programming: Application and Implementation"
Mads Sig Ager 등의 "A functional correspondence between evaluators and abstract machines." (2003)
Simon Peyton Jones의 "The Implementation of Functional Programming Languages"
Matt Might의 블로그 (https://matt.might.net)에서 Lisp에 관한 모든 글

TODO

letrec 추가
재귀적 정의 추가

GN⁺의 정리

Rust 매크로로 작성된 Lisp 인터프리터는 매우 흥미로우며, 간결한 코드로 강력한 기능을 제공함.
재귀를 명시적으로 지원하지 않지만, 람다를 통해 재귀를 구현할 수 있음.
메타순환 인터프리터는 효율적이지 않으므로, 명시적인 재귀 원시 기능을 추가하는 것이 필요함.
Paul Graham의 "Roots of Lisp"는 메타순환 평가기를 이해하는 데 훌륭한 자료임.
유사한 기능을 제공하는 다른 프로젝트로는 Scheme 인터프리터나 다른 Lisp 변형을 추천함.