LISP-Dialekt auf Python: TCO und FEXPR

Minimaler LISP-Dialekt in Python mit Tail-Call-Optimierung und FEXPRs

Dieser LISP-Dialekt ist in Python für fortgeschrittene und erfahrene Entwickler implementiert. Er unterstützt Tail-Call-Optimierung (TCO) nur für schwanzrückrufende Rekursion, FEXPR-Funktionen mit unevaluiereten Argumenten und dynamisches Scoping. Begrenzte Menge an Spezialformen: if, quote, macro, setq, expand, foreach, loop, lambda.

TCO nutzt einen Trampolin-Mechanismus: Rekursive Aufrufe wie (fact (- n 1) ( n acc)) lassen den Stack nicht überlaufen, im Gegensatz zu ( n (fact (- n 1))). FEXPRs ermöglichen Makros, rohe Argumente für Codegenerierung zu erhalten.

Beispiel für defun-Makro:

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

Erweitert sich zu (setq square (lambda (x) (begin (princ x) (* x x)))).

Lexer und Parser

Der Lexer wandelt einen String in Token um:

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

Test:

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

Der Parser verwendet einen Stack für verschachtelte Listen:

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

Logik: ( schiebt eine neue Liste auf den Stack, ) poppt und hängt sie an das Eltern-Element, Atome werden als int/float/string geparst.

Umgebung (Env)

Die Env-Klasse speichert Variablen und Makros:

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'was? (kenne ich nicht: "{name}")')

    def delete(self, name):
        if not name in self.env:
            raise Exception(f'was? (kenne ich nicht: "{name}")')
        elif name in self.macros:
            self.macros.remove(name)
        del self.env[name]

Methoden: add für Zuweisung, get für Lookup, delete mit Makro-Bereinigung.

Trampolin für TCO

Thunk umschließt verzögerte Berechnungen:

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

Die trampoline-Schleife führt Thunk.bounce() aus, bis ein finales Ergebnis erreicht ist, und vermeidet Stack-Wachstum.

Haupt-Evaluator

Die Kernfunktion eval verarbeitet den 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)
    # ... (weitere Formen: 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)

Wichtige Punkte:

• Spezialformen geben Thunk für verzögerte Evaluation zurück.
• Makros erhalten unevaluierte args, andere Argumente werden evaluiert.
• FEXPR-Logik: if op in env.macros — Aufruf mit rohen Argumenten.

TCO-Einschränkung: [trampoline(arg, env) for arg in args] evaluiert alle Argumente vorab und blockiert Optimierung bei Nicht-Schwanzaufrufen.

Eingebaute Primitiven

Basisumgebung mit Hilfsfunktionen:

• list, nth für Listenoperationen.
• Binäre Operatoren +, - via apply_binop.
• Relationale 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

Wichtige Erkenntnisse

• TCO nur für Schwanzaufrufe via Trampolin und Thunk.
• FEXPR-Makros erhalten unevaluierte Argumente für Codegenerierung.
• Dynamisches Scoping vereinfacht die Implementierung, birgt aber Risiken bei Scope-Lecks.
• Parser ist stackbasierter rekursiver Descent, Lexer nutzt String-Vorverarbeitung.
• Kein Quasiquote, vollständiges TCO oder GC — Verbesserungspotenzial.

— Editorial Team