Python 上的 LISP 方言：TCO 和 FEXPR

用 Python 构建极简 LISP 方言：支持尾调用优化与 FEXPR

这个 LISP 方言用 Python 实现，面向中高级开发者。它仅支持尾递归调用的尾调用优化（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))))。

词法分析器与解析器

词法分析器将字符串转为令牌：

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'什么鬼？（我不认识："{name}"）')

    def delete(self, name):
        if not name in self.env:
            raise Exception(f'什么鬼？（我不认识："{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

核心要点

• TCO 仅限尾调用，通过蹦床和 Thunk 实现。
• FEXPR 宏接收未求值参数，用于代码生成。
• 动态作用域简化实现，但易导致作用域泄漏。
• 解析器基于栈的递归下降，词法分析用字符串预处理。
• 无准引号、完整 TCO 或 GC — 有改进空间。

— Editorial Team