Python에서의 LISP Dialect: TCO와 FEXPR

파이썬으로 최소 LISP 방언 구현: 꼬리 호출 최적화와 FEXPR 지원

이 LISP 방언은 중급 및 고급 개발자를 위해 파이썬으로 구현되었습니다. 꼬리 재귀 호출에 대한 꼬리 호출 최적화(TCO), 평가되지 않은 인자를 받는 FEXPR 함수, 동적 스코핑을 지원합니다. 특수 형식은 제한적: if, quote, macro, setq, expand, foreach, loop, lambda.

TCO는 트램폴린을 사용합니다: (fact (- n 1) ( n acc)) 같은 재귀 호출은 스택 오버플로가 발생하지 않지만, ( n (fact (- n 1)))는 발생합니다. FEXPR은 매크로가 코드 생성을 위해 원시 인자를 받을 수 있게 합니다.

defun 매크로 예시:

(macro defun (name args . body)
  (list (quote setq) name (list (quote lambda) args (cons (quote begin) body))))

(setq square (lambda (x) (begin (princ x) (* x x))))로 확장됩니다.

Lexer와 Parser

렉서는 문자열을 토큰으로 변환합니다:

def read(s):
    return s.replace('(',' ( ').replace(')',' ) ').replace('\n', ' ').split()

테스트:

>>> test = """(defun square (x)
 (* x x)"""
>>> read(test)
['(', 'defun', 'square', '(', 'x', ')', '(', '*', 'x', 'x', ')']

파서는 중첩 리스트를 위해 스택을 사용합니다:

def parse(tokens):
    stack = [[]]
    for token in tokens:
        if token == '(':
            stack.append([])
        elif token == ')':
            completed = stack.pop()
            if stack:
                stack[-1].append(completed)
            else:
                return completed
        else:
            stack[-1].append(atom(token))
    if len(stack) == 1 and len(stack[0]) == 1:
        return stack[0][0]
    return stack[0]

def atom(token):
    try:
        return int(token)
    except:
        try:
            return float(token)
        except:
            return token

로직: (는 새 리스트를 스택에 푸시, )는 팝해서 부모에 붙임, 원자는 int/float/문자열로 파싱.

환경(Env)

Env 클래스는 변수와 매크로를 저장합니다:

class Env:
    def __init__(self):
        self.env = {}
        self.macros = []

    def add(self, name, value):
        self.env[name] = value

    def get(self, name):
        if name in self.env:
            return self.env[name]
        raise Exception(f'what? (i dont know it: "{name}")')

    def delete(self, name):
        if not name in self.env:
            raise Exception(f'what? (i dont know it: "{name}")')
        elif name in self.macros:
            self.macros.remove(name)
        del self.env[name]

메서드: add로 할당, get으로 조회, delete로 매크로 정리 포함 삭제.

TCO를 위한 트램폴린

Thunk는 지연 계산을 래핑합니다:

class Thunk:
    def __init__(self, func, *args):
        self.func = func
        self.args = args
        
    def bounce(self):
        return self.func(*self.args)
    

def trampoline(ast, env):
    result = eval(ast, env)
    while type(result) is Thunk:
        result = result.bounce()
    return result

trampoline 루프는 최종 값에 도달할 때까지 Thunk.bounce()를 실행해 스택 증가를 방지합니다.

메인 평가기

핵심 eval 함수가 AST를 처리합니다:

def eval(ast, env):
    if type(ast) is str:
        return env.get(ast)
    elif type(ast) is not list:
        return ast
    
    if ast == []:
        return -1
    
    op, *args = ast
    
    if op == 'quote':
        return Thunk(lambda: args[0])
    elif op == 'setq':
        var, val_expr = args
        val = trampoline(val_expr, env) 
        env.add(var, val)
        return val
    elif op == 'if':
        test, a, b = args
        test = trampoline(test, env)
        return Thunk(eval, a if test else b, env)
    # ... (다른 형식: foreach, loop, begin, lambda, macro, expand)
    
    proc = trampoline(op, env)

    if op in env.macros:
        return trampoline(proc(*args), env)
        
    vals = [trampoline(arg, env) for arg in args]

    return proc(*vals)

주요 포인트:

• 특수 형식은 평가 지연을 위해 Thunk 반환.
• 매크로는 평가되지 않은 args 받음, 다른 인자는 평가.
• FEXPR 로직: if op in env.macros — 원시 인자로 호출.

TCO 제한: [trampoline(arg, env) for arg in args]가 모든 인자를 미리 평가해 비꼬리 호출 최적화 불가.

내장 기본 함수

유틸리티가 포함된 기본 환경:

• 리스트 작업용 list, nth.
• apply_binop을 통한 이항 연산자 +, -.
• 관계 연산 apply_relop.

def apply_binop(op, *args):
    if len(args) == 1:
        return args[0]
    result = args[0]
    for arg in args[1:]:
        result = op(result, arg)
    return result

def rem(lst, el):
    new_lst = []
    for i in lst:
        if i != el:
            new_lst.append(i)
    return new_lst

주요 요약

• 트램폴린과 Thunk로 꼬리 호출에만 TCO 적용.
• FEXPR 매크로는 코드 생성을 위해 평가되지 않은 인자 받음.
• 동적 스코핑은 구현 간단하지만 스코프 누출 위험.
• 파서는 스택 기반 재귀 하강, 렉서는 문자열 전처리.
• 준인용문, 완전 TCO, GC 없음 — 개선 여지 많음.

— Editorial Team