개발자가 레이튼 교수 문제 푸는 법이라는 영상이 있다. 퍼즐 게임을 하다가 문제가 나오면 게임기를 내려놓고 코드를 짜서 답을 구하는 영상이다. 머리로 풀라고 만든 문제를 굳이 반복문으로 밀어버리는 모습이 우스우면서도 묘하게 통쾌한데, 보고 나면 개발자라는 직업의 본질 하나가 남는다. 우리는 문제를 직접 푸는 대신, 문제를 풀어주는 기계를 만드는 사람들이다.
그렇다면 한 단계 더 올라가볼 수도 있다. 문제를 풀어주는 기계, 그러니까 프로그램을 만드는 도구인 프로그래밍 언어 자체를 만들어보는 것이다. 언어를 만든다고 하면 컴파일러 책 한 권과 학기 하나가 필요할 것 같지만, 만들 언어를 잘 고르면 저녁 시간 안에 끝난다. 그 언어가 Lisp이다. Peter Norvig은 (How to Write a (Lisp) Interpreter (in Python))에서 동작하는 Lisp 인터프리터를 Python 117줄로 만들어 보였고, 심지어 Python 16줄로 짜는 방법을 다룬 글도 있다.1
이번 글에서는 Python으로 작은 Lisp을 바닥부터 만들어본다. 이름은 함수썬이라고 하겠다. Lisp은 함수형 언어의 원조이고 구현은 파이썬이니, 함수와 파이썬을 붙여 함수썬이다. 지난번 계산기 엔진 만들기에서 토큰화 → 파싱 → 평가라는 3단계 파이프라인으로 수식 문자열을 계산했는데, 이번에는 정확히 같은 뼈대 위에 변수, 조건문, 함수, 재귀, 클로저까지 갖춘 진짜 프로그래밍 언어를 세운다. 완성본은 주석과 빈 줄을 빼고 135줄이다. 글에 나오는 코드와 실행 결과는 전부 실제로 실행해 확인한 것이다.
왜 하필 Lisp인가
Lisp은 1958년에 John McCarthy가 만든 언어다. Fortran 다음으로 오래된, 지금까지 살아 있는 두 번째로 늙은 프로그래밍 언어다.2 반세기 넘게 살아남은 비결은 여러 가지가 있지만, 우리 목적에 중요한 것은 하나다. 문법이 사실상 하나뿐이다.
Lisp 코드는 전부 이렇게 생겼다.
(연산 인자1 인자2 ...)괄호를 열고, 무엇을 할지 먼저 쓰고, 재료를 나열하고, 괄호를 닫는다. 이 덩어리를 **S-표현식(S-expression)**이라고 부른다. 1 + 2는 (+ 1 2)가 되고, 1 + 2 * 3은 (+ 1 (* 2 3))이 된다. 함수를 정의하는 것도, 조건문도, 전부 같은 모양이다.
(+ 1 2) ; 3
(* (+ 1 2) (- 7 3)) ; (1+2) * (7-3) = 12
(define x 10) ; 변수 정의
(if (> x 5) 1 2) ; 조건문
(define square (lambda (x) (* x x))) ; 함수 정의처음 보면 괄호 폭탄에 눈이 어지럽다. 그런데 언어를 만드는 입장으로 자리를 옮기면 이 괄호들이 갑자기 고맙게 느껴진다. 계산기 엔진을 만들 때 파서에서 가장 애먹었던 부분을 떠올려보자. 1 + 2 * 3에서 곱하기를 먼저 묶는 연산자 우선순위, 2 ^ 3 ^ 2를 오른쪽부터 묶는 결합 방향, 빼기 부호와 음수 부호의 구분. 사람에게 자연스러운 문법을 기계에게 이해시키느라 생긴 비용이었다. Lisp에는 이 문제가 통째로 없다. (+ 1 (* 2 3))은 무엇을 먼저 계산할지 괄호가 이미 다 말해준다. 우선순위 규칙이 필요 없는 것이 아니라, 프로그래머가 우선순위를 손으로 다 적는 언어인 것이다.
한 발 더 나아가면 이런 관찰에 도달한다. 계산기 엔진에서 파서의 일은 토큰을 트리(AST)로 엮는 것이었다. 그런데 (+ 1 (* 2 3))이라는 코드를 보자. 괄호가 곧 중첩이고, 중첩이 곧 트리다. Lisp 프로그래머는 처음부터 트리를 직접 적고 있는 셈이다.3 파서가 할 일이 거의 없으니 인터프리터 전체가 가벼워진다. 언어 구현에 입문할 때 다들 Lisp부터 만드는 이유다.
만들 것을 정확히 정해두자. 함수썬은 다음을 지원한다.
- 정수, 실수, 불리언(
#t,#f) - 변수 정의와 대입:
define,set! - 조건문:
if - 함수:
lambda(클로저와 재귀 포함) - 코드를 데이터로:
quote - 여러 식을 순서대로:
begin - 리스트 다루기:
list,car,cdr,cons,map,filter등 - 대화형 셸(REPL)
문자열 타입과 매크로는 없다. 그래도 이 목록이면 재귀 함수를 짜고 퍼즐을 풀 수 있는, 튜링 완전한 언어가 된다. 전체 구조는 계산기 엔진과 같은 3단계다. 문자열을 토큰으로 쪼개고(토큰화), 토큰을 트리로 엮고(파싱), 트리를 순회하며 실행한다(평가). 하나씩 만들어보자.
토큰화: 세 줄이면 충분하다
계산기 엔진의 토크나이저는 50줄쯤 됐다. 문자를 한 글자씩 읽으며 숫자인지 이름인지 연산자인지 분기하는 반복문이었다. 함수썬의 토크나이저는 이렇다.
def tokenize(source):
return source.replace('(', ' ( ').replace(')', ' ) ').split()끝이다. 괄호 양옆에 공백을 끼워 넣은 다음 공백으로 자른다. Lisp의 토큰은 여는 괄호, 닫는 괄호, 그리고 나머지 덩어리(숫자든 이름이든) 세 종류뿐이라 이걸로 충분하다.
>>> tokenize('(+ 1 (* 2 3))')
['(', '+', '1', '(', '*', '2', '3', ')', ')'](+ 1처럼 괄호와 글자가 붙어 있어도 replace가 공백을 벌려놨기 때문에 깔끔하게 떨어진다. 문법을 단순하게 설계하면 구현이 얼마나 가벼워지는지 첫 단계부터 체감된다.4
파싱: 괄호를 리스트로
이제 토큰의 나열을 트리로 엮는다. 계산기 엔진에서는 ASTNode라는 전용 자료구조를 정의했지만, 함수썬은 그럴 필요가 없다. Python 리스트가 곧 트리다. (+ 1 (* 2 3))을 파싱한 결과가 ['+', 1, ['*', 2, 3]]이라면, 중첩 리스트의 모양이 원본 코드의 괄호 구조와 정확히 같다. 따로 트리 클래스를 만들어봐야 같은 정보를 두 번 적는 일이 된다.
파서는 토큰을 앞에서부터 하나씩 꺼내면서 만든다. 규칙은 두 개뿐이다. (를 만나면 )가 나올 때까지 안쪽을 재귀적으로 파싱해 리스트로 모으고, 그 외의 토큰은 값 하나로 바꾼다.
def parse(tokens):
if len(tokens) == 0:
raise SyntaxError('입력이 끝나버렸다. 괄호가 닫혔는지 확인하자')
token = tokens.pop(0)
if token == '(':
expr = []
while tokens and tokens[0] != ')':
expr.append(parse(tokens))
if not tokens:
raise SyntaxError('닫는 괄호가 없다')
tokens.pop(0) # ')' 버리기
return expr
elif token == ')':
raise SyntaxError('여는 괄호 없이 )가 나왔다')
else:
return atom(token)안쪽에서 parse가 자기 자신을 부르는 것에 주목하자. (+ 1 (* 2 3))을 읽다가 두 번째 (를 만나면, 그 안쪽 (* 2 3)을 처리하는 일은 재귀 호출에게 맡긴다. 괄호가 얼마나 깊게 중첩되든 같은 코드가 처리한다. 계산기 엔진에서 배운 재귀 하강 파싱과 같은 원리인데, 문법이 단순하니 함수 하나로 끝난 것이다.
괄호가 아닌 토큰은 atom이 값으로 바꾼다. 원자(atom)라는 이름 그대로, 더 쪼갤 수 없는 최소 단위라는 뜻이다.
Symbol = str # 함수썬의 심볼은 파이썬 문자열
Number = (int, float) # 함수썬의 숫자는 파이썬 숫자
def atom(token):
if token == '#t':
return True
if token == '#f':
return False
try:
return int(token)
except ValueError:
try:
return float(token)
except ValueError:
return Symbol(token)정수로 읽어보고, 안 되면 실수로 읽어보고, 그것도 안 되면 **심볼(symbol)**로 취급한다. 심볼은 x, square, +처럼 무언가의 이름이 되는 토큰이다. 함수썬에서 심볼의 정체는 그냥 Python 문자열인데, "이 문자열은 데이터가 아니라 이름이다"라는 의도를 코드에 남기기 위해 Symbol이라는 별칭을 붙였다.5
토큰화와 파싱을 묶은 read까지 만들면 앞단이 완성된다.
def read(source):
return parse(tokenize(source))>>> read('(+ 1 (* 2 3))')
['+', 1, ['*', 2, 3]]
>>> read('(define square (lambda (x) (* x x)))')
['define', 'square', ['lambda', ['x'], ['*', 'x', 'x']]]문자열이 중첩 리스트가 됐다. 아래에서 직접 쳐보자. 괄호를 지우거나 덜 닫으면 파서가 어떤 에러를 내는지도 볼 수 있다.
평가: 트리를 값으로
이제 심장부다. 평가기(evaluator)는 파싱된 트리를 받아 값을 돌려주는 함수다. 먼저 산술만 되는 최소 버전을 만들어보자. 규칙은 세 개면 된다.
- 심볼이면 → 그 이름에 묶인 값을 찾아온다
- 숫자면 → 그 자체가 값이다
- 리스트면 → 첫 요소는 함수, 나머지는 인자다. 인자를 전부 평가한 뒤 함수를 부른다
이름과 값의 대응표가 필요하니, 우선 Python 사전으로 만든다. 이 대응표를 **환경(environment)**이라고 부른다.
import math
import operator as op
global_env = {
'+': op.add, '-': op.sub, '*': op.mul, '/': op.truediv,
'>': op.gt, '<': op.lt, '>=': op.ge, '<=': op.le, '=': op.eq,
'abs': abs, 'max': max, 'min': min,
'pi': math.pi,
}operator 모듈은 Python 연산자를 함수로 쓸 수 있게 해준다. op.add(1, 2)는 1 + 2다. 즉 함수썬의 +는 Python의 덧셈을 이름만 바꿔 빌린 것이다. 언어를 만든다고 해서 덧셈까지 발명할 필요는 없다. 숙주 언어의 기능을 얼마나 영리하게 빌리느냐가 인터프리터 구현의 절반이다.
평가기는 위의 세 규칙을 그대로 옮기면 된다.
def evaluate(x, env=global_env):
if isinstance(x, Symbol): # 규칙 1: 이름 → 환경에서 찾는다
return env[x]
if isinstance(x, Number): # 규칙 2: 숫자 → 그 자체가 값
return x
proc = evaluate(x[0], env) # 규칙 3: 함수 호출
args = [evaluate(arg, env) for arg in x[1:]]
return proc(*args)>>> evaluate(read('(+ 1 2)'))
3
>>> evaluate(read('(* (+ 1 2) (- 7 3))'))
12
>>> evaluate(read('(max 1 8 3)'))
8#t와 #f는 어디서 처리되나 싶을 텐데, Python의 bool이 int의 서브클래스라서 규칙 2의 Number 검사에 얹혀 그 자체로 평가된다. 이 구현이 슬쩍 기대고 있는 Python의 성질이니 기억해두자.
동작 과정을 손으로 따라가 보자. (* (+ 1 2) (- 7 3))이 들어오면 첫 요소 *를 환경에서 찾아 곱셈 함수를 얻고, 인자 (+ 1 2)와 (- 7 3)을 각각 평가한다. 그 각각이 다시 규칙 3에 걸려 재귀가 일어나고, 3과 4가 되어 돌아온다. 마지막으로 op.mul(3, 4)가 불려 12가 나온다. 트리의 잎에서 뿌리 방향으로 값이 차오르는 구조다. 아래 데모에서 이 재귀를 한 단계씩 눈으로 확인할 수 있다.
파서까지 포함해 지금까지 50줄쯤인데 벌써 전위 표기 계산기가 됐다. 계산기 엔진 한 편 분량을 따라잡은 셈이다. 지금부터가 언어의 영역이다.
특수형: 평가를 미루는 문법
변수 정의를 추가해보자. (define x 10)을 지금의 evaluate에 넣으면 어떻게 될까. 리스트니까 규칙 3에 걸리고, 첫 요소 define을 환경에서 찾으려다 KeyError가 난다. 설령 define이라는 함수를 환경에 넣어둔다 해도 문제가 남는다. 규칙 3은 인자를 전부 평가한 뒤 함수를 부른다. 그러면 아직 정의되지도 않은 x를 평가하려다 죽는다.
if는 문제가 더 심각하다. (if (> x 0) (/ 100 x) 0)에서 인자를 전부 먼저 평가하면, x가 0일 때 실행되지 말아야 할 (/ 100 x)까지 실행해서 0으로 나누기 에러가 난다. 조건문의 존재 이유가 "한쪽 갈래는 실행하지 않는 것"인데 둘 다 실행해버리면 조건문이 아니다.
그래서 모든 언어에는 함수처럼 생겼지만 함수가 아닌 것들이 있다. 인자를 미리 평가하면 안 되고, 각자의 규칙대로 특별하게 처리해야 하는 문법. Lisp에서는 이를 **특수형(special form)**이라고 부른다. 함수썬에는 quote, if, define, set!, lambda, begin 여섯 개가 있고, 전부 evaluate 안에서 함수 호출보다 먼저 가로채서 처리한다.
def evaluate(x, env=global_env):
if isinstance(x, Symbol):
return env[x]
if isinstance(x, Number):
return x
head = x[0]
if head == 'quote': # (quote 식)
return x[1]
if head == 'if': # (if 조건 참일때 거짓일때)
(_, test, conseq, alt) = x
branch = conseq if evaluate(test, env) else alt
return evaluate(branch, env)
if head == 'define': # (define 이름 식)
(_, name, expr) = x
env[name] = evaluate(expr, env)
return None
proc = evaluate(head, env) # 아니면 보통의 함수 호출
args = [evaluate(arg, env) for arg in x[1:]]
return proc(*args)if를 보자. 조건만 먼저 평가하고, 그 결과에 따라 두 갈래 중 한쪽만 평가한다. 다른 갈래는 트리인 채로 버려진다. define은 이름 자리를 평가하지 않고 문자열 그대로 환경의 키로 쓴다. 평가를 미루거나 건너뛰는 것, 이것이 특수형의 본질이다.
>>> evaluate(read('(define radius 10)'))
>>> evaluate(read('(* pi (* radius radius))'))
314.1592653589793
>>> evaluate(read('(if (> radius 5) 1 2)'))
1quote는 셋 중 가장 이상해 보이지만 가장 Lisp다운 특수형이다. 인자를 평가하지 않고 트리 그대로 돌려준다.
>>> evaluate(read('(+ 1 2)'))
3
>>> evaluate(read('(quote (+ 1 2))'))
['+', 1, 2]같은 (+ 1 2)인데 quote를 씌우면 계산 결과가 아니라 코드 조각 자체, 그러니까 리스트가 나온다. 코드와 데이터가 같은 모양이니 가능한 일이다. 함수썬에서 quote는 리스트 리터럴을 만드는 용도로 쓴다. (quote (1 2 3))은 그냥 리스트 [1, 2, 3]이다. 참고로 quote 없이 (1 2 3)을 평가하면 규칙 3이 1을 함수로 호출하려다 TypeError: 'int' object is not callable을 낸다. 괄호는 기본적으로 "호출하라"는 뜻이기 때문이다.
환경: 이름이 사는 곳
lambda로 넘어가기 전에 환경을 손봐야 한다. 지금 환경은 사전 하나라서 모든 이름이 전역이다. 하지만 함수가 생기는 순간 지역 변수가 필요해진다. (define square (lambda (x) (* x x)))에서 x는 square가 실행되는 동안만 존재해야 하고, 전역의 다른 x를 덮어써서도 안 된다.
해법은 사전을 사슬로 엮는 것이다. 함수가 호출될 때마다 새 사전을 만들어 인자를 담고, "여기서 못 찾으면 바깥에서 찾아라"라는 연결 고리를 달아둔다.
class Env(dict):
def __init__(self, params=(), args=(), outer=None):
self.update(zip(params, args))
self.outer = outer
def find(self, name):
if name in self:
return self
if self.outer is None:
raise NameError(f'정의되지 않은 이름: {name}')
return self.outer.find(name)Env는 Python 사전을 상속받아 outer라는 링크 하나를 더 가진 물건이다. find는 이름이 어느 환경에 정의돼 있는지를 사슬을 거슬러 올라가며 찾는다. 함수 안에서 지역 변수 x를 찾으면 그 자리에서 끝나고, pi처럼 지역에 없는 이름은 전역까지 올라가서 찾아진다. 끝까지 없으면 그제야 NameError를 낸다. Python이나 JavaScript에서 매일 겪는 **스코프(scope)**가 정확히 이 구조다. 안쪽에서 바깥 변수는 보이지만 그 역은 안 되는 이유가, 링크가 안에서 바깥으로만 걸려 있기 때문이라는 걸 이 열 줄이 보여준다.
전역 환경도 Env로 바꿔주고, evaluate의 이름 찾기와 set!이 find를 쓰게 고친다.
global_env = Env()
global_env.update({
'+': op.add, '-': op.sub, '*': op.mul, '/': op.truediv,
'>': op.gt, '<': op.lt, '>=': op.ge, '<=': op.le, '=': op.eq,
'quotient': op.floordiv, 'mod': op.mod,
'abs': abs, 'max': max, 'min': min, 'not': op.not_,
'and': lambda *xs: all(xs), 'or': lambda *xs: any(xs),
'list': lambda *xs: list(xs),
'car': lambda xs: xs[0],
'cdr': lambda xs: xs[1:],
'cons': lambda x, xs: [x] + xs,
'null?': lambda xs: xs == [],
'length': len,
'range': lambda a, b: list(range(a, b)),
'map': lambda f, xs: list(map(f, xs)),
'filter': lambda f, xs: list(filter(f, xs)),
'print': print,
'pi': math.pi,
})내친김에 표준 라이브러리도 채웠다. car는 리스트의 첫 요소, cdr은 첫 요소를 뺀 나머지, cons는 앞에 하나 붙이기다.6 전부 Python 한 줄짜리 람다로 때웠다. 아까 말한 "숙주 언어 빌려 쓰기"의 연속이다.
lambda: 언어가 살아나는 순간
드디어 함수다. evaluate에 세 특수형을 마저 넣는다. 이름 찾기가 env.find(x)[x]로 바뀐 것도 눈여겨보자.
class Procedure:
def __init__(self, params, body, env):
self.params, self.body, self.env = params, body, env
def __call__(self, *args):
return evaluate(self.body, Env(self.params, args, self.env))
def evaluate(x, env=global_env):
if isinstance(x, Symbol):
return env.find(x)[x] # 사슬을 타고 이름을 찾는다
if isinstance(x, Number):
return x
if x == []: # 빈 리스트는 그 자체가 값
return x
head = x[0]
if head == 'quote':
return x[1]
if head == 'if':
(_, test, conseq, alt) = x
branch = conseq if evaluate(test, env) else alt
return evaluate(branch, env)
if head == 'define':
(_, name, expr) = x
env[name] = evaluate(expr, env)
return None
if head == 'set!': # (set! 이름 식) — 이미 있는 변수를 고친다
(_, name, expr) = x
env.find(name)[name] = evaluate(expr, env)
return None
if head == 'lambda': # (lambda (인자들) 본문)
(_, params, body) = x
return Procedure(params, body, env)
if head == 'begin': # (begin 식1 식2 ...) — 순서대로 평가
result = None
for expr in x[1:]:
result = evaluate(expr, env)
return result
proc = evaluate(head, env)
args = [evaluate(arg, env) for arg in x[1:]]
return proc(*args)lambda가 하는 일은 허무할 정도로 적다. 인자 목록과 본문 트리, 그리고 지금의 환경을 Procedure 객체에 담아둘 뿐, 본문은 평가하지 않는다. 실제 평가는 호출될 때 일어난다. Procedure.__call__을 보면, 호출 시점에 새 Env를 만들어 인자 이름과 실제 값을 짝지어 담고, outer를 함수가 만들어질 때의 환경으로 연결한 뒤 본문을 평가한다.
>>> evaluate(read('(define square (lambda (x) (* x x)))'))
>>> evaluate(read('(square 12)'))
144(square 12)가 불리면 {'x': 12}라는 작은 환경이 태어나고, 본문 (* x x)가 그 안에서 평가되고, 144가 나오고, 환경은 버려진다. 함수 호출이라는 익숙한 마법의 전체 구현이 이 두 줄짜리 __call__이다.
여기서 outer를 호출한 쪽의 환경이 아니라 정의된 곳의 환경으로 연결한 것이 이 글에서 가장 중요한 한 수다. 이 선택 덕분에 클로저(closure)가 공짜로 생긴다. 함수를 돌려주는 함수를 보자.
(define make-adder (lambda (n) (lambda (x) (+ x n))))
(define add3 (make-adder 3))read는 식 하나만 파싱하므로, 이렇게 식이 여러 개인 코드는 한 식씩 evaluate(read('...'))에 넣는다고 생각하면 된다. 토큰이 남아 있는 동안 parse와 evaluate를 반복하는 대여섯 줄짜리 헬퍼를 만들어두면 편하다.
(make-adder 3)이 실행되는 동안 {'n': 3}이라는 환경이 존재하고, 그 안에서 안쪽 lambda가 Procedure로 만들어지며 이 환경을 env로 붙든다. make-adder가 리턴하고 나서도 add3이 그 Procedure를 물고 있는 한 {'n': 3}은 사라지지 않는다.
>>> evaluate(read('(add3 10)'))
13
>>> evaluate(read('(add3 100)'))
103"함수가 자기가 태어난 곳의 변수를 기억한다"는 클로저 설명을 다들 한 번쯤 들어봤을 텐데, 구현 쪽에서 보면 신비할 게 없다. 환경 사전이 Procedure에 매달려 있어서 가비지 컬렉션이 못 치우는 것뿐이다. JavaScript 면접 단골 문제인 클로저 카운터도 그대로 돌아간다.
(define make-counter
(lambda ()
(begin
(define count 0)
(lambda () (begin (set! count (+ count 1)) count)))))
(define tick (make-counter))>>> evaluate(read('(tick)'))
1
>>> evaluate(read('(tick)'))
2
>>> evaluate(read('(tick)'))
3호출할 때마다 값이 올라간다. count는 전역에 없고, tick이 물고 있는 환경 안에만 산다.
재귀는 어떨까. 놀랍게도 추가 구현이 필요 없다. (define fact ...)가 전역에 이름을 등록하고, 본문 속 fact는 호출 시점에 환경 사슬을 타고 전역까지 올라가 자기 자신을 찾는다.
(define fact (lambda (n) (if (<= n 1) 1 (* n (fact (- n 1))))))
(define fib (lambda (n) (if (< n 2) n (+ (fib (- n 1)) (fib (- n 2))))))>>> evaluate(read('(fact 20)'))
2432902008176640000
>>> evaluate(read('(fib 10)'))
55
>>> evaluate(read('(map fib (range 0 10))'))
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34]이제 함수썬으로 함수썬의 표준 라이브러리를 짤 수도 있다. 아까 Python 람다로 때운 map을 함수썬 자신의 언어로 다시 정의해보자.
(define my-map
(lambda (f xs)
(if (null? xs)
(quote ())
(cons (f (car xs)) (my-map f (cdr xs))))))>>> evaluate(read('(my-map square (list 1 2 3 4))'))
[1, 4, 9, 16]빈 리스트면 빈 리스트를, 아니면 첫 요소에 f를 적용한 것을 나머지의 my-map 결과 앞에 붙인다. 135줄짜리 인터프리터 위에서 언어가 자기 자신을 확장하기 시작했다. 여기까지 오면 만든 사람 입장에서도 좀 뭉클해진다.
REPL: 언어와 대화하기
매번 evaluate(read('...'))를 치는 건 언어를 쓴다는 기분이 안 난다. 마지막 부품으로 REPL(Read-Eval-Print Loop)을 붙이자. 읽고, 평가하고, 출력하는 무한 루프다. 그 전에 출력을 다듬는 함수 하나가 필요하다. 지금은 결과가 Python 값이라 리스트가 [1, 2, 3]으로 보이는데, 함수썬 사용자에게는 (1 2 3)으로 보여야 한다.
def to_string(value):
if value is True:
return '#t'
if value is False:
return '#f'
if isinstance(value, list):
return '(' + ' '.join(map(to_string, value)) + ')'
return str(value)
def repl():
print('함수썬 v0.1 — 나가려면 Ctrl-C')
while True:
try:
value = evaluate(read(input('함수썬> ')))
if value is not None:
print(to_string(value))
except (KeyboardInterrupt, EOFError):
print()
break
except Exception as e:
print(f'에러: {e}')에러를 잡아서 출력만 하고 루프를 계속 도는 것이 REPL의 핵심 매너다. 오타 한 번에 셸이 죽어버리면 아무도 안 쓴다. 단 종료 신호까지 삼키면 안 되니 KeyboardInterrupt(Ctrl-C)와 EOFError(Ctrl-D)는 따로 받아 루프를 빠져나간다. 처음에는 except Exception 하나로 뭉뚱그렸다가, Ctrl-D를 눌렀더니 에러 메시지가 무한히 쏟아지는 REPL이 되는 걸 보고 고쳤다. 실행하면 이런 대화가 가능해진다.
함수썬 v0.1 — 나가려면 Ctrl-C
함수썬> (+ 1 2)
3
함수썬> (define square (lambda (x) (* x x)))
함수썬> (square 12)
144
함수썬> (quote (i can lisp))
(i can lisp)
함수썬> (+ 1
에러: 닫는 괄호가 없다이로써 함수썬 v0.1이 완성됐다. 아래 데모는 본문의 Python 구현을 TypeScript로 그대로 옮겨 브라우저에서 돌린 것이다. 예제 버튼을 눌러도 되고, 직접 아무 식이나 쳐봐도 된다.
장난감이 아니게 되는 순간
여기까지는 즐거운 공작 시간이었다. 그런데 이 135줄짜리 장난감의 구조가 실무에서 꽤 진지하게 쓰인다는 얘기를 해야겠다.
커머스 어드민을 만든다고 하자. 운영팀이 요청한다. "5만 원 이상 구매한 VIP에게 10% 할인, 아니면 10만 원 이상 구매 고객에게 5% 할인을 적용해주세요. 아, 그리고 이 조건은 프로모션마다 계속 바뀔 거예요." 마지막 문장이 무섭다. 조건이 바뀔 때마다 코드를 고쳐 배포할 수는 없으니, 할인 규칙을 데이터로 저장하고 실행 시점에 해석해야 한다.
흔한 첫 시도는 규칙을 JSON으로 설계하는 것이다. {"if": {">=": ["total", 50000]}, ...} 같은 모양이 되는데, 조금만 복잡해지면 JSON으로 조건식 트리를 손으로 적는 것이 얼마나 고통스러운지 알게 된다. 두 번째 유혹은 Python의 eval로 규칙 문자열을 그냥 실행하는 것이다. 이건 계산기 엔진 글에서 말한 것과 같은 이유로 사고로 가는 지름길이다. 어드민에 규칙을 입력하는 사람이 __import__('os').system(...)을 넣는 순간 서버가 남의 것이 된다.
함수썬 같은 미니 인터프리터가 정확히 이 틈새의 물건이다. 규칙을 사람이 읽고 쓸 만한 문자열로 저장하면서, 실행할 수 있는 것은 우리가 환경에 넣어준 함수뿐이다. import도 파일 접근도 네트워크도 언어에 존재하지 않으니 원천적으로 못 한다.
(define discount
(lambda (total vip)
(if (and (>= total 50000) vip)
(* total 0.1)
(if (>= total 100000) (* total 0.05) 0))))이 문자열을 DB에 저장해두고, 주문이 들어오면 읽어와 평가한다.
>>> evaluate(read(rule_from_db)) # discount가 정의된다
>>> evaluate(read('(discount 80000 #t)'))
8000.0
>>> evaluate(read('(discount 80000 #f)'))
0
>>> evaluate(read('(discount 120000 #f)'))
6000.0운영팀이 "8만 원 이상으로 바꿔주세요"라고 하면 DB의 문자열에서 숫자 하나를 고치면 끝이다. 배포가 없다.7 이렇게 특정 문제 하나를 위해 만든 작은 언어를 DSL(Domain-Specific Language, 도메인 특화 언어)이라고 부른다. 스프레드시트 수식, 검색창의 고급 검색 문법, CI 설정 파일의 조건식이 전부 DSL이고, 그 뒤에는 전부 오늘 만든 것 같은 토큰화-파싱-평가 파이프라인이 산다. Emacs는 에디터 전체가 Lisp 인터프리터 위에 올라가 있고, 40년째 사용자들이 그 언어로 기능을 붙이고 있다.8
레이튼 교수 문제 풀기
처음의 영상으로 돌아가자. 개발자는 퍼즐을 코드로 푼다. 그러면 언어를 만든 개발자는 자기가 만든 언어로 퍼즐을 풀어야 마땅하다. 레이튼 교수 스타일의 수수께끼 하나를 준비했다.
두 자리 수 중에서, 십의 자리 숫자와 일의 자리 숫자를 더한 값에 4를 곱하면 다시 자기 자신이 되는 수를 모두 찾아라.
머리로 풀려면 "각 자리 합의 4배가 자기 자신"이라는 조건을 만족하는 수를 이리저리 대입해봐야 한다. 함수썬으로 풀면 조건을 그대로 받아 적은 뒤 두 자리 수 전체를 체로 거르면 된다.
(filter
(lambda (n) (= n (* 4 (+ (quotient n 10) (mod n 10)))))
(range 10 100))함수썬> (filter (lambda (n) (= n (* 4 (+ (quotient n 10) (mod n 10))))) (range 10 100))
(12 24 36 48)12는 (1+2)×4, 24는 (2+4)×4, 36은 (3+6)×4, 48은 (4+8)×4. 답이 네 개나 있었다. 두 자리 수 90개를 일일이 확인하는 노동을 filter에게 시켰고, 문제의 조건은 lambda 안에 거의 문장 그대로 옮겨 적었다. 우리가 직접 만든 토크나이저가 이 문자열을 쪼갰고, 우리가 만든 파서가 트리를 세웠고, 우리가 만든 평가기가 클로저를 만들어 90번 호출했다. 위의 REPL 데모에 이 식이 예제 버튼으로 들어 있으니 직접 확인해보자.
남은 숙제
함수썬 v0.1은 여기서 멈추지만, 진짜 언어가 되려면 갈 길이 남아 있다. 무엇이 빠졌는지 아는 것도 공부라서 정리해둔다.
먼저 실용적인 구멍들이다. 문자열 타입이 없고(토크나이저를 갈아야 한다), 에러 메시지에 위치 정보가 없다(계산기 엔진에서 했던 pos 흘려보내기가 필요하다). and와 or를 보통 함수로 구현해서 단락 평가(short-circuit)가 안 되는 것도 흠이다. (and #f (/ 1 0))은 진짜 Lisp에서는 #f지만 함수썬에서는 0으로 나누기 에러가 난다. 인자를 미리 평가하지 않는 특수형으로 옮겨야 맞다.
구조적인 한계도 있다. 함수썬의 재귀 깊이는 Python의 재귀 깊이에 묶여 있어서 (count-down 100000) 같은 코드는 RecursionError로 죽는다. Scheme 계열 언어는 꼬리 호출 최적화(tail call optimization)로 이런 재귀를 반복문처럼 상수 메모리에서 돌리는데, 이를 넣으려면 evaluate의 재귀를 while 루프로 펴는 수술이 필요하다. 그리고 매크로가 없다. quote가 코드를 데이터로 바꿔줬으니, 데이터를 조작해서 다시 코드로 실행하는 문이 하나만 더 있으면 언어의 문법을 사용자가 확장하는 세계가 열린다. 이 두 가지가 궁금하다면 Norvig의 개정판 lispy가 정확히 그 내용이고, 더 갈 사람에게는 여러 언어로 Lisp을 만드는 Make a Lisp 프로젝트와, Racket 과목을 듣던 학생이 Norvig의 구현을 발전시킨 lispy 같은 참고 자료가 있다. 그 끝판왕에 SICP라는 고전이 기다린다.
돌아보면 한 일은 단순하다. 문자열을 리스트로 바꿨고(토큰화·파싱 30여 줄), 리스트를 값으로 바꿨다(평가 40줄). 나머지는 환경과 출력 손질이다. 그런데 그 안에서 스코프가 왜 그렇게 동작하는지, 클로저가 무엇을 붙들고 있는지, if가 함수일 수 없는 이유가 뭔지를 구현자의 눈으로 확인했다. 프로그래밍 언어는 쓰기만 할 때는 자연법칙 같지만, 한 번 만들어보면 누군가의 설계 결정 뭉치라는 것이 보인다. 다음에 이상한 언어 동작을 만나면 "이 언어의 evaluate는 여기서 뭘 하고 있을까"를 상상하게 될 것이다. 그 상상이 되는 개발자와 안 되는 개발자는 디버깅의 깊이가 다르다.
레이튼 교수라면 이렇게 말했을 것이다. 훌륭한 수수께끼에는 우아한 답이 있는 법이라고. 135줄짜리 답안치고는 꽤 우아하지 않은가.
Footnotes
-
16줄 버전은 파서를 만드는 대신 Lisp 코드를 Python 튜플 문법으로 적게 해서 Python의
eval이 파싱을 대신하게 하는 트릭을 쓴다. 재치 있는 지름길이지만 이 글에서는 파서까지 직접 만든다. ↩ -
정확히는 Lisp이라는 단일 언어보다 언어 가족에 가깝다. Common Lisp, Scheme, Clojure, Racket이 모두 Lisp 방언이고, 이 글의 함수썬은 그중 가장 단순한 Scheme을 닮았다. ↩
-
코드의 표기법과 자료구조가 같은 모양인 이 성질을 동형성(homoiconicity)이라고 부른다. Lisp의 매크로라는 강력한 기능이 여기서 나오는데, 글 끝에서 다시 언급한다. ↩
-
이 방식의 대가는 문자열 리터럴을 지원할 수 없다는 것이다.
"hello world"가 공백에서 잘려버리기 때문이다. 문자열이 필요하면 계산기 엔진처럼 한 글자씩 읽는 토크나이저로 돌아가야 한다. Norvig의 개정판이 정규식 기반 토크나이저로 이 문제를 푼다. ↩ -
진짜 Lisp은 리스트를 배열이 아니라 cons 셀이라는 연결 리스트로 표현하고, 심볼도 문자열과 구분되는 별도 타입이다. Python의 리스트와 문자열을 빌려 쓰는 건 구현을 줄이기 위한 의도적인 타협이다. ↩
-
1950년대 IBM 704의 레지스터 이름(Contents of Address Register, Contents of Decrement Register)에서 온 화석 같은 이름이다. 첫 요소/나머지라는 뜻으로 그냥 외우면 된다. ↩
-
물론 실무라면 여기에 평가 시간 제한, 재귀 깊이 제한, 룰 버전 관리와 테스트를 붙여야 한다. "안전한 언어"라도
(define loop (lambda () (loop)))같은 무한 재귀는 짤 수 있기 때문이다. ↩ -
"충분히 복잡한 C/Fortran 프로그램에는 버그투성이에 느리고 절반만 구현된 Common Lisp이 들어 있다"는 Greenspun의 열 번째 법칙이라는 농담이 있다. 규칙 엔진을 JSON으로 짜다 보면 이 농담이 예언이었음을 알게 된다. ↩