Dialekt LISP na Pythonie: TCO i FEXPR

Implementacja minimalnego dialektu LISP w Pythonie z TCO i FEXPR

Dialekt LISP jest implementowany w Pythonie dla programistów średniego/zaawansowanego poziomu. Obsługuje optymalizację wywołań ogonowych (TCO) tylko dla rekurencji ogonowych, funkcje FEXPR z argumentami nieewaluowanymi i dynamiczne zakresy zmiennych. Ograniczony zestaw form specjalnych: if, quote, macro, setq, expand, foreach, loop, lambda.

TCO działa przez trampolinę: wywołania rekurencyjne takie jak (fact (- n 1) ( n acc)) nie przepełniają stosu, w przeciwieństwie do ( n (fact (- n 1))). FEXPR umożliwiają makrom otrzymywanie surowych argumentów do generowania kodu.

Przykład makra defun:

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

Rozszerza się w (setq square (lambda (x) (begin (princ x) (* x x)))).

Lekser i parser

Lekser przekształca ciąg znaków na tokeny:

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

Test:

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

Parser używa stosu dla zagnieżdżonych list:

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

Logika: ( dodaje nową listę do stosu, ) kończy i dołącza do rodzica, atomy są parsowane na int/float/string.

Środowisko (Env)

Klasa Env przechowuje zmienne i makra:

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]

Metody: add do przypisywania, get do wyszukiwania, delete z czyszczeniem makr.

Trampolina dla TCO

Thunk owija opóźnione obliczenia:

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

Cykl trampoline wykonuje Thunk.bounce() do uzyskania końcowej wartości, zapobiegając wzrostowi stosu.

Główny ewaluator

Centralna funkcja eval przetwarza 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)
    # ... (pozostałe formy: 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)

Kluczowe punkty:

• Formy specjalne zwracają Thunk do opóźnionego wykonania.
• Makra otrzymują nieewaluowane args, pozostałe argumenty są ewaluowane.
• Logika FEXPR: if op in env.macros — wywołanie z surowymi argumentami.

Ograniczenie TCO: lista [trampoline(arg, env) for arg in args] ewaluuje wszystkie argumenty z góry, blokując optymalizację nieszczytowych wywołań.

Wbudowane prymitywy

Podstawowe środowisko z narzędziami:

• list, nth do pracy z listami.
• Operatory binarne +, - przez apply_binop.
• Relacyjne 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

Co jest ważne

• TCO tylko dla wywołań szczytowych przez trampolinę i Thunk.
• Makra FEXPR otrzymują nieewaluowane argumenty do generowania kodu.
• Dynamiczne zakresy zmiennych upraszczają implementację, ale ryzyko wycieku zakresów.
• Parser rekurencyjny zstępujący na stosie, lekser — przetwarzanie stringów.
• Brak quasiquote, pełnego TCO lub GC — do dopracowania.

— Editorial Team