Dialecto LISP en Python: TCO y FEXPR

Creando un dialecto LISP mínimo en Python con optimización de llamadas cola y FEXPR

Este dialecto de LISP está implementado en Python para desarrolladores intermedios y senior. Soporta optimización de llamadas en cola (TCO) solo para llamadas recursivas en cola, funciones FEXPR con argumentos no evaluados y ámbito dinámico. Conjunto limitado de formas especiales: if, quote, macro, setq, expand, foreach, loop, lambda.

La TCO usa un trampolín: llamadas recursivas como (fact (- n 1) ( n acc)) no desbordan la pila, a diferencia de ( n (fact (- n 1))). Las FEXPR permiten que las macros reciban argumentos crudos para generar código.

Ejemplo de macro defun:

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

Se expande a (setq square (lambda (x) (begin (princ x) (* x x)))).

Analizador léxico y sintáctico

El analizador léxico convierte una cadena en tokens:

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

Prueba:

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

El analizador sintáctico usa una pila para listas anidadas:

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

Lógica: ( empuja una nueva lista a la pila, ) la saca y la adjunta al padre, los átomos se parsean como int/float/cadena.

Entorno (Env)

La clase Env almacena variables y macros:

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'¿qué? (no lo conozco: "{name}")')

    def delete(self, name):
        if not name in self.env:
            raise Exception(f'¿qué? (no lo conozco: "{name}")')
        elif name in self.macros:
            self.macros.remove(name)
        del self.env[name]

Métodos: add para asignación, get para búsqueda, delete con limpieza de macros.

Trampolín para TCO

Thunk envuelve cálculos demorados:

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

El bucle trampoline ejecuta Thunk.bounce() hasta obtener un valor final, evitando el crecimiento de la pila.

Evaluador principal

La función central eval procesa el 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)
    # ... (otras formas: 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)

Puntos clave:

• Las formas especiales devuelven Thunk para evaluación diferida.
• Las macros reciben args no evaluados, otros argumentos se evalúan.
• Lógica FEXPR: if op in env.macros — llamada con argumentos crudos.

Limitación TCO: [trampoline(arg, env) for arg in args] evalúa todos los argumentos de antemano, bloqueando optimización no en cola.

Primitivas integradas

Entorno base con utilidades:

• list, nth para operaciones con listas.
• Operadores binarios +, - vía apply_binop.
• Relacionales 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

Lecciones clave

• TCO solo para llamadas en cola vía trampolín y Thunk.
• Macros FEXPR reciben argumentos no evaluados para generar código.
• Ámbito dinámico simplifica la implementación pero arriesga fugas de ámbito.
• Analizador sintáctico basado en pila de descenso recursivo, léxico usa preprocesamiento de cadenas.
• Sin quasiquote, TCO completa ni GC — margen para mejoras.

— Editorial Team