Dialecte LISP sur Python : TCO et FEXPR

Créer un dialecte LISP minimal en Python avec optimisation des appels terminaux et FEXPR

Ce dialecte LISP est implémenté en Python pour les développeurs intermédiaires et seniors. Il supporte l'optimisation des appels terminaux (TCO) uniquement pour les appels récursifs terminaux, les fonctions FEXPR avec arguments non évalués, et le scoping dynamique. Ensemble limité de formes spéciales : if, quote, macro, setq, expand, foreach, loop, lambda.

La TCO utilise un trampoline : les appels récursifs comme (fact (- n 1) ( n acc)) ne font pas déborder la pile, contrairement à ( n (fact (- n 1))). Les FEXPR permettent aux macros de recevoir des arguments bruts pour générer du code.

Exemple de macro defun :

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

Se développe en (setq square (lambda (x) (begin (princ x) (* x x)))).

Analyse lexicale et syntaxique

L'analyseur lexical convertit une chaîne en jetons :

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

Test :

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

L'analyseur syntaxique utilise une pile pour les listes imbriquées :

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

Logique : ( pousse une nouvelle liste sur la pile, ) dépile et attache au parent, les atomes sont parsés en int/float/chaîne.

Environnement (Env)

La classe Env stocke les variables et 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'quoi ? (je ne connais pas : "{name}")')

    def delete(self, name):
        if not name in self.env:
            raise Exception(f'quoi ? (je ne connais pas : "{name}")')
        elif name in self.macros:
            self.macros.remove(name)
        del self.env[name]

Méthodes : add pour l'assignation, get pour la recherche, delete avec nettoyage des macros.

Trampoline pour la TCO

Thunk encapsule les calculs différés :

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

La boucle trampoline exécute Thunk.bounce() jusqu'à obtenir une valeur finale, évitant la croissance de la pile.

Évaluateur principal

La fonction eval centrale traite l'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)
    # ... (autres formes : 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)

Points clés :

• Les formes spéciales retournent un Thunk pour un report d'évaluation.
• Les macros reçoivent des args non évalués, les autres arguments sont évalués.
• Logique FEXPR : if op in env.macros — appel avec arguments bruts.

Limite TCO : [trampoline(arg, env) for arg in args] évalue tous les arguments d'avance, bloquant l'optimisation des appels non terminaux.

Primitives intégrées

Environnement de base avec utilitaires :

• list, nth pour les opérations sur listes.
• Opérateurs binaires +, - via apply_binop.
• Opérateurs relationnels 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

Points clés à retenir

• TCO uniquement pour les appels terminaux via trampoline et Thunk.
• Macros FEXPR reçoivent des arguments non évalués pour générer du code.
• Scoping dynamique simplifie l'implémentation mais risque des fuites de portée.
• Analyseur syntaxique récursif à base de pile, analyseur lexical par prétraitement de chaîne.
• Pas de quasiquote, TCO complète ou GC — marge d'amélioration.

— Editorial Team