Python으로 Lisp 인터프리터 작성하기
Python으로 Lisp 인터프리터 작성하기
Lisp 인터프리터를 구현하는 것은 컴퓨터와 컴파일러가 어떻게 동작하는지를 이해하는 기본적인 방법입니다. Peter Norvig의 "Lispy" 프로젝트는 Scheme 방언의 기능적 부분집합을 약 117줄의 Python 3 코드로 구현할 수 있음을 보여주며, "세상에서 가장 강력한 언어"가 아주 적은 양의 소스 코드로 정의될 수 있음을 증명합니다.
언어 인터프리터의 구조
언어 인터프리터는 두 가지 주요 구성 요소로 이루어집니다: 파싱과 실행. 과정은 선형 파이프라인을 따릅니다: Program → Parse → Abstract Syntax Tree (AST) → Eval → Result.
파싱
파싱은 문자 시퀀스를 내부 표현, 보통 추상 구문 트리(AST)로 변환합니다. Lispy에서는 이를 두 단계로 나눕니다:
- 어휘 분석 (Tokenization): 입력 문자열을 토큰(괄호, 기호, 숫자)으로 분리합니다. Lispy는 괄호 주변에 공백을 추가하고 Python의
str.split을 사용해 이를 구현합니다. - 구문 분석: 토큰을 중첩 리스트 구조로 조립합니다.
read_from_tokens함수는 여는 괄호를 만나면 재귀적으로 리스트를 만들고, 괄호가 아닌 토큰은 원자(정수, 실수, 기호)로 처리합니다.
실행 (평가)
실행은 AST를 언어의 의미 규칙에 따라 처리합니다. Lispy의 eval 함수는 표현식의 유형에 따라 값을 결정합니다:
- 기호: 현재 환경에서 찾아 반환합니다.
- 숫자: 자체로 평가됩니다.
- 특수 형태:
if,define같은 키워드는 특정 로직(예: 조건 분기 또는 변수 할당)을 트리거합니다. - 프로시저 호출: 연산자와 인자를 평가한 뒤, 결과 프로시저를 인자 값에 적용합니다.
Lispy 계산기 구현
첫 번째 인터프리터 버전인 "Lispy Calculator"는 다섯 가지 기본 구문 형태를 지원합니다:
| Expression | Syntax | Semantics |
|---|---|---|
| 변수 참조 | symbol |
변수의 값을 반환합니다. |
| 상수 리터럴 | number |
숫자 자체를 반환합니다. |
| 조건문 | (if test conseq alt) |
test가 참이면 conseq를, 그렇지 않으면 alt를 반환합니다. |
| 정의 | (define symbol exp) |
exp의 값을 symbol에 바인딩합니다. |
| 프로시저 호출 | (proc arg...) |
proc와 args를 평가한 뒤, 프로시저를 적용합니다. |
전체 Lispy로 확장: 프로시저와 렉시컬 스코핑
계산기에서 거의 완전한 Scheme 부분집합으로 확장하기 위해 Lispy는 quote, set!, lambda를 도입합니다. lambda의 추가는 환경을 통한 변수 관리가 필요합니다.
Env 클래스와 렉시컬 스코핑
지역 변수와 중첩 함수를 지원하기 위해 환경을 dict를 상속받는 클래스로 재정의합니다. 각 Env 인스턴스는 자체 로컬 매핑과 outer 환경에 대한 참조를 가집니다.
변수가 참조될 때 인터프리터는 find 메서드를 사용해 가장 안쪽 환경부터 검색하고, 찾지 못하면 외부 환경을 재귀적으로 탐색합니다. 이 메커니즘은 렉시컬 스코핑을 구현하여, 프로시저가 호출된 위치가 아니라 정의된 환경의 변수를 참조하도록 합니다.
프로시저 구현
Procedure 객체는 매개변수 이름, 함수 본문, 그리고 생성 시점의 환경을 저장합니다. 호출될 때 제공된 인자를 매개변수에 바인딩하고, 원래 환경을 외부 스코프로 설정한 새로운 Env를 생성합니다.
성능 및 완전성
Lispy는 교육적 명료성을 목표로 하며, 실제 프로덕션 사용을 위한 것이 아닙니다. 주요 특징은 다음과 같습니다:
- 크기: 매우 컴팩트하며, 약 117줄(빈 줄 제외)과 4KB 정도의 소스 코드로 구성됩니다.
- 속도:
(fact 100)을 약 0.003초에 계산할 수 있습니다. - 제한점: 꼬리 호출 최적화,
call/cc, 문자열, 문자, 불리언, 포괄적인 오류 복구 등 여러 표준 Scheme 기능이 누락되어 있습니다.
커뮤니티 인사이트
개발자와 교육자는 Lisp 인터프리터 구현을 컴퓨터 과학의 기본 연습으로 평가합니다. 토론에서 언급된 바와 같이:
"프로그래밍 언어를 어떻게 작성하는지 궁금했다면, 이것이 시작하기에 가장 좋은 자료일 것입니다."
다른 기여자들은 Lisp의 트리 구조와 언어학자가 문장 구조를 주석 달 때 사용하는 구문 구조 문법 사이의 동형성을 강조했습니다. 또한 AI가 이제는 이러한 코드를 생성할 수 있지만, 인터프리터를 직접 구현하는 행위는 프로그래머에게 여전히 "깨우는 경험"이라고 지적했습니다.
SUMMARY: Peter Norvig는 Python 3을 사용해 간결한 Scheme 방언 Lisp 인터프리터인 Lispy를 구현함으로써 언어 파싱과 실행의 기본 메커니즘을 보여줍니다.
TITLE: Python으로 Lisp 인터프리터 작성하기