LISP Dialect on Python: TCO and FEXPR

Building a Minimal LISP Dialect in Python with Tail-Call Optimization and FEXPRs

This LISP dialect is implemented in Python for intermediate and senior developers. It supports tail-call optimization (TCO) for tail-recursive calls only, FEXPR functions with unevaluated arguments, and dynamic scoping. Limited set of special forms: if, quote, macro, setq, expand, foreach, loop, lambda.

TCO uses a trampoline: recursive calls like (fact (- n 1) ( n acc)) won't overflow the stack, unlike ( n (fact (- n 1))). FEXPRs let macros receive raw arguments for code generation.

Example defun macro:

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

Expands to (setq square (lambda (x) (begin (princ x) (* x x)))).

Lexer and Parser

The lexer turns a string into tokens:

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

Test:

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

The parser uses a stack for nested lists:

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

Logic: ( pushes a new list onto the stack, ) pops and attaches to the parent, atoms are parsed as int/float/string.

Environment (Env)

The Env class stores variables and 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'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]

Methods: add for assignment, get for lookup, delete with macro cleanup.

Trampoline for TCO

Thunk wraps delayed computations:

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

The trampoline loop runs Thunk.bounce() until a final value is reached, avoiding stack growth.

Main Evaluator

The core eval function processes the 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)
    # ... (other forms: 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)

Key points:

• Special forms return Thunk for deferred evaluation.
• Macros get unevaluated args, other arguments are evaluated.
• FEXPR logic: if op in env.macros — call with raw arguments.

TCO limitation: [trampoline(arg, env) for arg in args] evaluates all arguments upfront, blocking non-tail call optimization.

Built-in Primitives

Base environment with utilities:

• list, nth for list operations.
• Binary operators +, - via apply_binop.
• Relational 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

Key Takeaways

• TCO only for tail calls via trampoline and Thunk.
• FEXPR macros receive unevaluated arguments for code generation.
• Dynamic scoping simplifies implementation but risks scope leakage.
• Parser is stack-based recursive descent, lexer uses string preprocessing.
• No quasiquote, full TCO, or GC — room for improvements.

— Editorial Team