언어 구현의 신비 해제: 7줄의 람다 계산법에서 함수형 인터프리터까지

프로그래밍 언어를 구현하는 것은 종종 컴파일러 엔지니어와 박사 학위 소지자들만이 할 수 있는 벅찬 과제로 여겨집니다. 하지만 그 핵심에서, 이 과정은 계산에 대한 이해를 연습하는 과정입니다. 언어를 그 절대적인 본질로까지 깎아내림으로써, 우리는 수학적 표기법과 작동하는 인터프리터 사이의 간극이 놀라울 정도로 작다는 것을 알 수 있습니다.

이 가이드는 Structure and Interpretation of Computer Programs와 같은 중대한 텍스트에서 발견되는 확장 가능한 eval/apply 디자인 패턴을 활용하여, 람다 계산법에 기반한 함수형, 튜링 완전(Turing-equivalent) 언어의 구현을 탐구합니다.

기초: 람다 계산법

20세기 초 Alonzo Church에 의해 개발된 람다 계산법은 계산을 표현하기 위한 미니멀리스트 시스템입니다. 이것은 현대적 의미의 "프로그래밍 언어"는 아닙니다—내장된 숫자, 불리언, 또는 I/O가 부족하지만—튜링 완전합니다. 이는 튜링 머신으로 계산 가능한 모든 함수를 람다 계산법으로 표현할 수 있음을 의미합니다.

이 시스템은 오직 세 가지 유형의 표현식에 의존합니다:

  1. 변수 참조(Variable References): 값을 참조하는 이름.
  2. 익명 함수(Abstractions): (λ v . e)로 작성되며, 여기서 v는 인자이고 e는 반환되는 표현식입니다.
  3. 함수 호출(Applications): (f e)로 작성되며, 여기서 함수 f가 인자 e에 적용됩니다.

튜링 완전성 달성하기

명시적인 루프나 재귀 없이 어떻게 이런 희박한 시스템이 복잡한 로직을 처리할 수 있을까요? 람다 계산법은 두 가지 주요 "해킹"을 사용합니다: Church encodings(정수와 불리언 같은 데이터를 함수로 표현하는 것)와 Y Combinator(익명 함수에서 재귀를 가능하게 하는 것)입니다.

이 시스템의 강력함을 보여주는 놀라운 예시는 "Omega" 프로그램입니다: ((λ f . (f f)) (λ f . (f f))). 이 프로그램은 결코 종료되지 않으며, 이는 람다 계산법이 모든 범용 언어에서 발견되는 것과 동일한 무한 루프를 표현할 수 있음을 보여줍니다.

7줄의 인터프리터

R5RS Scheme을 사용하면, 단 7줄의 코드로 람다 계산법을 위한 데노테이션 인터프리터를 구현할 수 있습니다. Scheme은 read 함수가 렉싱(lexing)과 s-expression으로의 파싱을 자동으로 처리하기 때문에 여기서 이상적인 선택입니다.

; eval takes an expression and an environment to a value
(define (eval e env) (cond
  ((symbol? e)       (cadr (assq e env)))
  ((eq? (car e) 'λ)  (cons e env))
  (else              (apply (eval (car e) env) (eval (cadr e) env)))))

; apply takes a function and an argument to a value
(define (apply f x) 
  (eval (cddr (car f)) (cons (list (cadr (car f)) x) (cdr f))))

; read and parse stdin, then evaluate:
(display (eval (read) '())) (newline)

작동 원리: Eval/Apply 패턴

이 아키텍처는 두 개의 상호 재귀 함수에 의존합니다:

  • eval: Expression과 Environment를 Value로 매핑합니다.
  • apply: Value (함수)와 다른 Value (인자)를 새로운 Value로 매핑합니다.

이 구현에서, Closure는 열린 항(open term)을 "닫기" 위해 사용됩니다. 이는 람다 표현식과 그 자유 변수를 정의하는 환경을 쌍으로 묶어, 함수가 호출되는 위치에 관계없이 문맥(context)을 유지하도록 보장합니다.

확장하기: 더 풍부한 언어 구축하기

7줄 버전은 개념 증명(proof of concept)일 뿐이지만, eval/apply 패턴은 효과적으로 확장 가능합니다. eval 함수를 더 많은 표현식 형태를를 처리하도록 확장함으로써, 우리는 더 유능한 언어를 구축할 수 있습니다. Racket에서 구현한 100줄짜리 구현체는 다음과 같은 것들을 도입할 수 있습니다:

  • 상수(Constants): 숫자 및 불리언 리터럴.

  • Primitive Operations: 덧셈, 뺄셈, 그리고 비교 연산.

  • Control Flow: if 조건문과 begin 시퀀싱.

  • Variable Bindings: 로컬 바인딩을 위한 let과 재귀적 바인딩을 위한 letrec.

  • State: 변수 변이를 위한 set!.

개발자는 구문론적 설계(코드가 어떻게 작성되는지)와 의미론적 설계(how the code is evaluated)를 분리함으로써, 단순히 인터프리터가 처리할 s-expression을 출력하는 파서를 구축함으로써 다양한 구문을 실험할 수 있습니다.

기술적 관점 및 비판

이러한 개념을 구현하는 것은 종종 함수형 미니멀리즘의 실용성에 대한 논쟁을 불러일으킵니다. 어떤 이들은 람다 계산법을 Lisp-like 언어에서 구현하는 것은 본질적으로 "Lisp를 Lisp로 구현하는 것"이라고 주장하며, 이는 간결결함이 대상 언어의 단순함보다는 호스트 언어의 내재적 특성 때문이라고 말합니다.

하지만 다른 이들은 이 과정이 단순히 코드에 관한 것이 아니라—계산의 "마법법"을 해제하는 것에 관한 것이라고 지적합니다. 한 기여자가 다음과 같이 언급했습니다:

"LED와 로직 게이트로 ALU를 만드는 것은 모든 커리큘럼의 일부여야 합니다... 사람들은 그것이 복잡하지만, 동시에 마법이 아니라는 것을 깨달아야 합니다."

나아가, 람다 계산법은 고수준 인터프리터 너머로 확장됩니다. **Binary Lambda Calculus (BLC)**에서는, 항(term)들은 비트로 표현되어, 때로는 여기에 제공된 7줄의 Scheme 코드보다 더 작은 매우 컴팩트한 자기 인터프리터(self-interpreters)를 가능하게 합니다.

결론

재미를 위해 장난감 언어를 만들고 있거나, 프로덕션급 컴파일러를 설계하고 있다면, 람다 계산법에서 시작하는 것은 값, 환경, 그리고 함수가 어떻게 상호작용하는지에 대한 근본적인 이해를를 제공합니다. eval/apply 패턴은 확장 가능한 청사진-이것이 가장 복잡한 프로그래밍밍 언어조차 몇 개의 단순하고 재귀적인 기초 위에 구축되어 있다는 것을 증명합니다.

Sources