Un interprete Lisp scritto in Python da qualcuno che evidentemente non aveva niente di meglio da fare
Ecco a voi Lisp Interpreter KE, preparati a ridere e imparare allo stesso tempo, questo codice è la porta d'ingresso a una tecnica che ho chiamato Schrödinger's recursion e che vi farà restare senza parole. Il codice è completamente autoesplicativo grazie agli assert e al gustoso naimng. 🍳👨🍳
# Lisp Interpreter KE"
# Depth limit: 42 (answer to everything, including stack overflow)
class Recipe:
"""Atom: the basic ingredient"""
def __init__(self, name):
self.name = name
def __repr__(self):
return self.name
def __eq__(self, other):
return isinstance(other, Recipe) and self.name == other.name
def __hash__(self):
return hash(self.name)
class Platter:
"""List a collection of dishes"""
def __init__(self, dishes):
self.dishes = tuple(dishes)
def __repr__(self):
return f"({' '.join(repr(d) for d in self.dishes)})"
def __eq__(self, other):
return isinstance(other, Platter) and self.dishes == other.dishes
def __hash__(self):
return hash(self.dishes)
class Kitchen:
"""Environment, where cooking happens"""
def __init__(self, parent=None):
self.pantry = {}
self.parent = parent
def shelf(self, name):
if name in self.pantry:
return self.pantry[name]
if self.parent:
return self.parent.shelf(name)
raise NameError(f"Ingredient '{name}' not found in kitchen")
def store(self, name, ingredient):
self.pantry[name] = ingredient
def clone(self):
return Kitchen(parent=self)
class LispFunction:
"""A callable that is a value, not a thunk: bounce must not call it"""
def __init__(self, fn):
self.fn = fn
def __call__(self, *args):
return self.fn(*args)
def __repr__(self):
return f"<function>"
# The restaurant kitchen
main_kitchen = Kitchen()
# Tail-call optimization:
# We use a trampoline with a sentinel value that IS a function
# that returns itself. <<<Schrödinger's recursion>>>
class Springform:
"""The trampoline to bounces until it doesn't"""
def __init__(self):
self.current = None
self.depth = 0
def bounce(self, recipe):
self.depth += 1
assert self.depth <= 42, f"Kitchen in fire! Depth exceeded 42 (current: {self.depth})"
if callable(recipe) and not isinstance(recipe, LispFunction):
self.current = recipe()
self.depth -= 1
return self.bounce(self.current)
else:
self.depth -= 1
return recipe
# The global trampoline: every function returns either a value or a callable
springform = Springform()
def is_special_form(name):
"""recognizes forms that don't follow normal evaluation rules"""
return name in {'quote', 'lambda', 'if', 'define', 'defun', 'set!', 'begin'}
def prepare(raw_input, kitchen=None):
"""Parse s-expression into Recipe or Platter"""
kitchen = kitchen or main_kitchen
raw_input = raw_input.strip()
if raw_input.startswith('('):
assert raw_input.endswith(')'), "Unmatched parentheses in kitchen"
content = raw_input[1:-1].strip()
if not content:
return Platter([])
dishes = []
depth = 0
current_dish = ""
for char in content:
if char == '(':
depth += 1
current_dish += char
elif char == ')':
depth -= 1
current_dish += char
elif char in (' ', '\n', '\t') and depth == 0:
if current_dish:
dishes.append(prepare(current_dish, kitchen))
current_dish = ""
else:
current_dish += char
if current_dish:
dishes.append(prepare(current_dish, kitchen))
return Platter(dishes)
else:
try:
return int(raw_input)
except ValueError:
try:
return float(raw_input)
except ValueError:
return Recipe(raw_input)
def taste(platter, kitchen=None):
"""It is the main cooking function"""
kitchen = kitchen or main_kitchen
def cook():
nonlocal platter, kitchen
assert springform.depth <= 42, "Kitchen temperature critical!"
# Base case
if isinstance(platter, (int, float)):
return platter
if isinstance(platter, Recipe):
return kitchen.shelf(platter.name)
if isinstance(platter, Platter):
if not platter.dishes:
return platter
head = platter.dishes[0]
if isinstance(head, Recipe):
if head.name == 'quote':
assert len(platter.dishes) == 2, "quote needs exactly one ingredient"
return platter.dishes[1]
if head.name == 'if':
assert len(platter.dishes) == 4, "if needs condition, then, else"
condition = taste(platter.dishes[1], kitchen)
is_true = not (isinstance(condition, Recipe) and condition.name == 'false')
return lambda: (
springform.bounce(
lambda: taste(platter.dishes[2], kitchen)
) if is_true else springform.bounce(
lambda: taste(platter.dishes[3], kitchen)
)
)
if head.name == 'define':
assert len(platter.dishes) >= 3, "define needs name and value"
var_name = platter.dishes[1]
assert isinstance(var_name, Recipe), "define: variable must be a symbol"
value = taste(platter.dishes[2], kitchen)
kitchen.store(var_name.name, value)
return Recipe('defined')
if head.name == 'lambda':
assert len(platter.dishes) >= 3, "lambda needs params and body"
params = platter.dishes[1]
assert isinstance(params, Platter), "lambda params must br a list... preferably a well‑chopped one"
body = platter.dishes[2]
def baked_function(*args):
local_kitchen = kitchen.clone()
param_names = params.dishes
assert len(param_names) == len(args), \
f"Function expects {len(param_names)} args, got {len(args)}"
for param, arg in zip(param_names, args):
assert isinstance(param, Recipe), "Parameters must be symbols"
local_kitchen.store(param.name, arg)
return lambda: springform.bounce(taste(body, local_kitchen))
return LispFunction(baked_function)
if head.name == 'begin':
assert len(platter.dishes) > 1, "begin needs at least one expression"
for expr in platter.dishes[1:-1]:
taste(expr, kitchen)
return lambda: springform.bounce(taste(platter.dishes[-1], kitchen))
evaluated_args = [
springform.bounce(taste(arg, kitchen))
for arg in platter.dishes[1:]
]
func = springform.bounce(taste(head, kitchen))
return lambda: springform.bounce(func(*evaluated_args))
return platter
return springform.bounce(cook())
def serve(code, kitchen=None):
"""The main entry point"""
kitchen = kitchen or main_kitchen
springform.depth = 0 # Reset depth counter
parsed = prepare(code, kitchen)
result = taste(parsed, kitchen)
return result
# ============ BUILT-IN RECIPES ============
def math_addition(*args):
assert len(args) >= 0, "Addition takes any number of arguments ;)"
return sum(args) if args else 0
def math_subtraction(*args):
assert len(args) >= 1, "Subtraction needs at least one argument"
result = args[0]
for arg in args[1:]:
result -= arg
return result
def math_multiplication(*args):
assert len(args) >= 0, "Multiplication takes any number of arguments"
result = 1
for arg in args:
result *= arg
return result
def math_division(*args):
assert len(args) == 2, "Division takes two arguments"
dividend, divisor = args
assert divisor != 0, "Division by zero makes the kitchen blow up"
return dividend / divisor
def comparison_equal(*args):
assert len(args) == 2, "= compares two things"
return Recipe('true') if args[0] == args[1] else Recipe('false')
def comparison_less(*args):
assert len(args) == 2, "< compares two numbers"
return Recipe('true') if args[0] < args[1] else Recipe('false')
def comparison_greater(*args):
assert len(args) == 2, "> compares two numbers"
return Recipe('true') if args[0] > args[1] else Recipe('false')
def list_constructor(*args):
assert True, "list can take any number of arguments"
return Platter(args)
def list_head(lst):
assert isinstance(lst, Platter) and len(lst.dishes) > 0, "car needs a non-empty list"
return lst.dishes[0]
def list_tail(lst):
assert isinstance(lst, Platter) and len(lst.dishes) > 0, "cdr needs a non-empty list"
return Platter(lst.dishes[1:])
def list_cons(head, tail):
assert isinstance(tail, Platter), "cons: second argument must be a list"
return Platter([head] + list(tail.dishes))
def is_nil(val):
return Recipe('true') if isinstance(val, Platter) and len(val.dishes) == 0 else Recipe('false')
def is_number(val):
return Recipe('true') if isinstance(val, (int, float)) else Recipe('false')
def is_symbol(val):
return Recipe('true') if isinstance(val, Recipe) else Recipe('false')
def display(*args):
assert len(args) >= 1, "display needs at least one argument"
print(' '.join(str(arg) for arg in args))
return Recipe('nil')
# Register all built-ins (wrapped in LispFunction so bounce doesn't call them as thunks)
main_kitchen.store('+', LispFunction(math_addition))
main_kitchen.store('-', LispFunction(math_subtraction))
main_kitchen.store('*', LispFunction(math_multiplication))
main_kitchen.store('/', LispFunction(math_division))
main_kitchen.store('=', LispFunction(comparison_equal))
main_kitchen.store('<', LispFunction(comparison_less))
main_kitchen.store('>', LispFunction(comparison_greater))
main_kitchen.store('list', LispFunction(list_constructor))
main_kitchen.store('car', LispFunction(list_head))
main_kitchen.store('cdr', LispFunction(list_tail))
main_kitchen.store('cons', LispFunction(list_cons))
main_kitchen.store('nil?', LispFunction(is_nil))
main_kitchen.store('number?', LispFunction(is_number))
main_kitchen.store('symbol?', LispFunction(is_symbol))
main_kitchen.store('display', LispFunction(display))
main_kitchen.store('true', Recipe('true'))
main_kitchen.store('false', Recipe('false'))
# ============ EXAMPLES ============
if __name__ == '__main__':
print("\n=== Lisp KE INTERPRETER ===\n")
print("Test 1: (+ 2 3 4)")
result = serve("(+ 2 3 4)")
assert result == 9, f"Expected 9, got {result}"
print(f"Result: {result}\n")
print("Test 2: (* (+ 2 3) 4)")
result = serve("(* (+ 2 3) 4)")
assert result == 20, f"Expected 20, got {result}"
print(f"Result: {result}\n")
print("Test 3: (define x 42) then (+ x 8)")
serve("(define x 42)")
result = serve("(+ x 8)")
assert result == 50, f"Expected 50, got {result}"
print(f"Result: {result}\n")
print("Test 4: (lambda (x) (* x x)) applied to 5")
serve("(define square (lambda (x) (* x x)))")
result = serve("(square 5)")
assert result == 25, f"Expected 25, got {result}"
print(f"Result: {result}\n")
print("Test 5: (if (< 3 5) 'yes 'no)")
result = serve("(if (< 3 5) (quote yes) (quote no))")
assert result == Recipe('yes'), f"Expected yes, got {result}"
print(f"Result: {result}\n")
print("Test 6: (car (list 1 2 3))")
result = serve("(car (list 1 2 3))")
assert result == 1, f"Expected 1, got {result}"
print(f"Result: {result}\n")
print("Test 7: Factorial with recursion")
serve("""
(define fact
(lambda (n acc)
(if (= n 0)
acc
(fact (- n 1) (* acc n)))))
""")
result = serve("(fact 5 1)")
assert result == 120, f"Expected 120, got {result}"
print(f"Result: {result}\n")
print("Test 8: THE EDGE CASE - What does (+) do?")
result = serve("(+)")
print(f"Result: {result}")
print("This shouldn't work but it does! Empty sum is 0 (monoid identity).\n")
print("Test 9: (begin (define y 10) (+ y 5))")
result = serve("(begin (define y 10) (+ y 5))")
assert result == 15, f"Expected 15, got {result}"
print(f"Result: {result}\n")
print("Test 10: Checking depth limit at 42")
try:
serve("(define deepfact (lambda (n acc) (if (= n 0) acc (deepfact (- n 1) (* acc n)))))")
result = serve("(deepfact 50 1)")
print(f"Result: {result}")
except AssertionError as e:
print(f"Caught assertion (as expected): {e}\n")
print("Test 11: Subtraction with single arg")
result = serve("(- 100)")
assert result == 100, f"Expected 100, got {result}"
print(f"Result: {result}")
print("Unary minus returns the number itself (non-standard but consistent)\n")
print("Test 12: (* 5 0)")
result = serve("(* 5 0)")
assert result == 0, f"Expected 0, got {result}"
print(f"Result: {result}\n")
print("Test 13: Function returning function")
serve("""
(define make-adder
(lambda (x)
(lambda (y)
(+ x y))))
""")
serve("(define add-5 (make-adder 5))")
result = serve("(add-5 3)")
assert result == 8, f"Expected 8, got {result}"
print(f"Result: {result}\n")
print("Test 14: (quote (1 2 3))")
result = serve("(quote (1 2 3))")
assert result == Platter([1, 2, 3]), f"Expected list, got {result}"
print(f"Result: {result}\n")
print("Test 15: Type predicates")
result1 = serve("(number? 42)")
result2 = serve("(symbol? (quote x))")
result3 = serve("(nil? (list))")
assert result1 == Recipe('true')
assert result2 == Recipe('true')
assert result3 == Recipe('true')
print(f"(number? 42) = {result1}")
print(f"(symbol? 'x) = {result2}")
print(f"(nil? (list)) = {result3}\n")
print("Test 16: ANOTHER EDGE CASE - Nested empty operations")
result = serve("(+ (*) (- 0))")
print(f"Result: {result}")
print("(*) returns 1, (- 0) returns 0, sum is 1.\n")
print("Test 17: Begin with display (side effect)")
print("Output: ", end="")
result = serve("(begin (display (quote Hello)) (display (quote World)) 42)")
assert result == 42
print(f"\nFinal result: {result}\n")
print("Test 18: If with explicit false")
result = serve("(if (quote false) 1 2)")
assert result == 2, f"Expected 2 (false branch), got {result}"
print(f"Result: {result}\n")
print("Test 19: (cons 1 (list 2 3))")
result = serve("(cons 1 (list 2 3))")
assert result == Platter([1, 2, 3])
print(f"Result: {result}\n")
print("Test 20: (car (cdr (list 1 2 3)))")
result = serve("(car (cdr (list 1 2 3)))")
assert result == 2
print(f"Result: {result}\n")
print("Test 21: Fibonacci")
serve("""
(define fib
(lambda (n)
(if (< n 2)
n
(+ (fib (- n 1)) (fib (- n 2))))))
""")
result = serve("(fib 6)")
assert result == 8
print(f"Result: {result}\n")
print("Test 22: Multiple comparisons")
result1 = serve("(= 5 5)")
result2 = serve("(< 3 7)")
result3 = serve("(> 10 5)")
print(f"(= 5 5) = {result1}")
print(f"(< 3 7) = {result2}")
print(f"(> 10 5) = {result3}\n")
print("Test 23: Empty multiplication (*)")
result = serve("(*)")
assert result == 1
print(f"Result: {result}")
print("ANOTHER EDGE CASE! Monoid identity for multiplication.\n")
print("Test 24: Testing near-limit recursion")
serve("""
(define countdown
(lambda (n)
(if (= n 0)
(quote done)
(countdown (- n 1)))))
""")
try:
result = serve("(countdown 40)")
assert result == Recipe('done')
print(f"Result: {result}")
print("✓ Survived depth 40\n")
except AssertionError as e:
if "depth" in str(e).lower() or "kitchen" in str(e).lower():
print(f"✗ Failed at depth 40: {e}\n")
else:
raise
print("Test 25: Multi-param lambda")
serve("""
(define add3
(lambda (x y z)
(+ x y z)))
""")
result = serve("(add3 1 2 3)")
assert result == 6
print(f"Result: {result}\n")
print("\n🐈 ALL TESTS COMPLETED SUCCESSFULLY\n")Entriamo nei gustosi dettagli della struttura del progetto, la parte più divertente del progetto sono le piccole scelte tecniche che trasformano un codice semplice in un piatto sperimentale. Ad esempio alcune chiamate non restituiscono il piatto pronto ma un ordine da eseguire più tardi. Questo permette di modellare la lazy evaluation senza cambiare la sintassi del linguaggio. Gli ordini possono essere annidati e rimbalzati fino a quando non arriva il piatto finale, e ogni lambda riceve la sua mini-cucina clonata dal contesto esterno. Questo garantisce che i parametri locali non contaminino la dispensa globale e permette di sperimentare scope lessicali senza sorprese, ma sarà tutto più chiaro più avanti.
Un atomo Lisp è un simbolo con un'identità unica e qui si chiama Recipe.
class Recipe:
def __init__(self, name):
self.name = name__eq__ confronta per nome, __hash__ permette agli atomi di stare nei dizionari. Gli atomi rappresentano simboli (x, fact), booleani (true, false), e valori di ritorno speciali come defined e nil. Niente di esotico.
Le S-expression sono liste, noi per coerenza e perché ci piacciono le chiamiano Platter.
class Platter:
def __init__(self, dishes):
self.dishes = tuple(dishes)Immutabili per costruzione (tupla, non lista). __repr__ stampa in notazione Lisp: (elem1 elem2 ...). Anche Platter è hashable, il che non serve quasi mai ma è coerente.
Ogni Kitchen ha un pantry (dizionario locale) e un parent (la cucina esterna).
class Kitchen:
def __init__(self, parent=None):
self.pantry = {}
self.parent = parent
def shelf(self, name):
if name in self.pantry:
return self.pantry[name]
if self.parent:
return self.parent.shelf(name)
raise NameError(f"Ingredient '{name}' not found in kitchen")
def clone(self):
return Kitchen(parent=self)shelf() sale la catena dei parent fino a trovare il simbolo o esplodere con NameError. Mentre clone() crea un ambiente figlio, viene usato ogni volta che si chiama una lambda, per isolare i parametri locali dal contesto esterno.
È un wrapper che dice a bounce "questo callable è un valore, non un thunk da eseguire".
class LispFunction:
def __init__(self, fn):
self.fn = fn
def __call__(self, *args):
return self.fn(*args)È callable, ma non è una lambda... Ne capirete il perché nella sezione sul trampoline.
Python non supporta TCO, quindi ogni chiamata ricorsiva accumula un frame sullo stack e per un interprete Lisp che vuole supportare ricorsione profonda signiica andare a fuoco ma c'è un ingrediente che risolve, il trampoline, cosa significa? Le funzioni ritornano lambda invece di chiamarsi direttamente, e bounce le esegue in sequenza.
class Springform:
def __init__(self):
self.current = None
self.depth = 0
def bounce(self, recipe):
self.depth += 1
assert self.depth <= 42, f"Kitchen fire! Depth exceeded 42 (current: {self.depth})"
if callable(recipe) and not isinstance(recipe, LispFunction):
self.current = recipe()
self.depth -= 1
return self.bounce(self.current)
else:
self.depth -= 1
return recipeNotiamo che bounce si chiama ricorsivamente, in un trampoline classico userebbe un loop while callable. Questo significa che lo stack Python cresce comunque, solo più lentamente. Non è TCO vero!
Ma più interessante, il discriminante è callable(recipe) and not isinstance(recipe, LispFunction), quindi rimbalza tutto quello che è callable, tranne le funzioni Lisp. Il che significa che bounce non sa cosa ha davanti finché non lo guarda, e questa è l'idea di Schrödinger applicata al codice.
La nostra cook() (la funzione interna di taste) cucina due tipi di cose:
- Un valore concreto: un numero, un
Recipe, unPlatter, unaLispFunction - Una lambda nuda: una computazione differita da rimbalzare
bounce riceve il risultato e deve decidere cosa farne. Il discriminante è callable().
- Una lambda nuda è callable, va eseguita e rimbalzata
- Una
LispFunctionè callable, è un valore, non va toccata - Un numero non è callable, è un valore
- Un
Recipenon è callable, è un valore
Quindi prima che bounce guardi, il risultato di cook() si trova in uno stato di sovrapposizione per così dire, quindi sta cosa potrebbe essere qualcosa da rimbalzare ancora, o potrebbe essere il valore finale. Non lo sai finché bounce non fa l'osservazione come nel famoso esperimento mentale del gatto.
cook() → {valore concreto ∪ lambda da rimbalzare}
↓
bounce() ← l'osservatore che collassa lo stato
Lo so è assurdo e non lo farebbe nessuno me è volutamente così e l'ambiguità viene gestita esplicitamente tramite LispFunction come sentinel.
1. taste(['+', 1, 2])
↓
2. cook() valuta:
'+' → LispFunction(math_addition)
1 → 1
2 → 2
ritorna lambda: springform.bounce(math_addition(1, 2))
↓ una LAMBDA NUDA
3. bounce(lambda)
callable? SÌ, e non è LispFunction → esegue la lambda
math_addition(1, 2) = 3
→ bounce(3)
4. bounce(3)
callable? NO → ritorna 3
Al passo 2, il valore 3 esiste già dentro la lambda, ma al passo 3, bounce non sa ancora che esiste. Il valore è simultaneamente calcolato (dentro la lambda) e non-osservato (la lambda non è stata ancora eseguita). Solo al passo 4, quando bounce vede un non-callable, il valore collassa definitivamente.
Il parsing, l'amore di una vita... comunque prepare() converte una stringa in Recipe o Platter, tutto fatto in casa come una volta.
def prepare(raw_input, kitchen=None):
raw_input = raw_input.strip()
if raw_input.startswith('('):
content = raw_input[1:-1].strip()
dishes, depth, current_dish = [], 0, ""
for char in content:
if char == '(':
depth += 1
current_dish += char
elif char == ')':
depth -= 1
current_dish += char
elif char in (' ', '\n', '\t') and depth == 0:
if current_dish:
dishes.append(prepare(current_dish, kitchen))
current_dish = ""
else:
current_dish += char
if current_dish:
dishes.append(prepare(current_dish, kitchen))
return Platter(dishes)
else:
try: return int(raw_input)
except ValueError:
try: return float(raw_input)
except ValueError: return Recipe(raw_input)I separatori sono spazio, \n e \t, il che permette di passare espressioni multi-riga a serve().
Le forme speciali non seguono la regola standard di "valuta tutti gli argomenti, poi applica la funzione" ma come per ogni cuoco che si rispetti questo piatto ha una sua identità quindi ognuna ha le sue regole.
quote: previene la valutazione. (quote x) ritorna l'atomo x invece di cercarlo nell'ambiente. Essenziale per manipolare il codice come dato.
if: valuta solo il ramo scelto, mai entrambi. Solo l'atomo false è falso; tutto il resto è vero, incluso 0, inclusa la lista vuota. È una scelta deliberata che diverge da Scheme (dove #f è l'unico falso) ma è internamente coerente. Non è "IF" la poesia di Kipling, ma leggetela lo stesso che è bellissima.
condition = taste(platter.dishes[1], kitchen)
is_true = not (isinstance(condition, Recipe) and condition.name == 'false')
return lambda: (
springform.bounce(lambda: taste(platter.dishes[2], kitchen))
if is_true else
springform.bounce(lambda: taste(platter.dishes[3], kitchen))
)define: modifica l'ambiente come side-effect e ritorna Recipe('defined'). Non ritorna il valore definito, ritorna defined.
lambda: Crea una LispFunction che cattura l'ambiente corrente (closure). Quando chiamata, clona la Kitchen, lega i parametri, e ritorna una lambda nuda, non una LispFunction.
def baked_function(*args):
local_kitchen = kitchen.clone()
for param, arg in zip(param_names, args):
local_kitchen.store(param.name, arg)
return lambda: springform.bounce(taste(body, local_kitchen))
return LispFunction(baked_function)Quindi baked_function è avvolto in LispFunction (quindi bounce non lo chiama quando lo incontra come valore), ma dentro ritorna una lambda nuda (quindi bounce la rimbalza quando viene chiamata). È la distinzione tra "questa funzione è un valore che qualcuno vorrà chiamare dopo" e "questa computazione deve essere eseguita adesso dal trampoline".
begin: valuta una sequenza di espressioni e ritorna solo l'ultima. Utile per side-effect come display. Valuta tutto tranne l'ultima espressione per i loro effetti, poi ritorna una lambda sull'ultima in modo che anche quella passi per il trampoline.
Valuta tutti gli argomenti da sinistra a destra, valuta la funzione, ritorna una lambda nuda per il trampolining. Standard insomma.
evaluated_args = [springform.bounce(taste(arg, kitchen)) for arg in platter.dishes[1:]]
func = springform.bounce(taste(head, kitchen))
return lambda: springform.bounce(func(*evaluated_args))Tutti i built-in sono chiusi in LispFunction prima di essere registrati nella cucina globale, senza LispFunction, bounce li chiamerebbe come thunk ogni volta che li incontra come valori, il che porta immediatamente a TypeError: 'int' object is not callable e a una mezz'ora di debugging.
Alcune peculiarità degne di nota:
(+) ritorna 0. E' l'identità monoide dell'addizione
(*) ritorna 1. Stesso ragionamento, identità monoide della moltiplicazione. Se non capisci perché (*) dovrebbe fare 1, pensa a quante volte moltiplichi niente, una volta, appunto.
(- 100) ritorna 100. La sottrazione unaria non nega il numero e QUESTO NON è un bug, è una scelta: (- a b c) fa a - b - c, e (- a) fa a. Se vuoi -42, fai (- 0 42). (- ) con zero argomenti solleva AssertionError perché la sottrazione richiede almeno un argomento su cui operare.
assert True in list_constructor. È lì. Non fa niente. È un placeholder che non è mai diventato qualcosa di più, o forse è un commento mascherato da codice. In ogni caso, è intenzionale nel senso che è rimasto lì intenzionalmente.
defun e set! sono riconosciuti da is_special_form ma non implementati. Lasciati come esercizio per il lettore, o per una versione futura, o per nessuno in particolare.
Quello che abbiamo visto ha un nome, anche se nessuno lo userebbe mai in produzione, Schrödinger Recursion. È un pattern dove una funzione ritorna uno di due tipi incompatibili senza specificare quale, e un osservatore esterno gestisce entrambi i casi.
Proprietà 1: Indecidibilità iniziale. Chi riceve il risultato di cook() non sa cosa ha in mano finché non lo ispeziona. Non esiste un campo is_thunk o un tipo Maybe che chiarisca la situazione prima dell'osservazione.
x = cook(platter)
# x è Recipe, Platter, int, float, LispFunction, o lambda nuda
# Non c'è modo di saperlo senza guardareProprietà 2: Rimbalzo ricorsivo. L'osservatore non esegue la computazione una volta sola ma la esegue finché il risultato non è stabile. Se cook() ritorna una lambda che ritorna una lambda che ritorna 42, bounce farà tre passaggi prima di fermarsi.
def bounce(self, recipe):
if callable(recipe) and not isinstance(recipe, LispFunction):
return self.bounce(recipe()) # ricorsivo, non iterativo
return recipeNota: questo bounce è ricorsivo su se stesso, non iterativo come sarebbe un trampoline classico con while callable. Lo stack Python cresce di un frame per ogni rimbalzo, il che significa che il limite a 42 non è solo un easter egg, è anche il motivo per cui l'interprete non crolla su se stesso mentre cerca di non crollare su se stesso.
Proprietà 3: Uniformità della firma. cook() può ritornare qualsiasi cosa, e bounce gestisce tutto. Non ci sono percorsi separati per "caso base" e "caso ricorsivo" a livello di chiamante.
Quando un errore avviene dentro una lambda che bounce sta eseguendo, lo stack trace mostra una catena di bounce → bounce → bounce → errore, senza nessuna traccia di dove nel codice Lisp l'errore è originato. L'utente vede un crash che sembra venire dal nulla, perché il punto di origine è sepolto in una closure che è già stata eseguita e dimenticata.
def cook(platter):
return lambda: operazione_che_crasha()
# L'errore è qui, ma il traceback non lo mostrerà
# L'utente vedrà:
# File "lispke.py", line 62, in bounce
# self.current = recipe()
# ... e poi il crash
# cook() non appare da nessuna partePoi c'è il problema della leggibilità, che però è opinabile, chi ha letto fin qui probabilmente non è intimidito da un callable che non sa se è un valore.
Il modo corretto di risolvere il problema sarebbe rendere esplicito lo stato fin dall'inizio, con tipi separati per valori e thunk:
class Computed:
def __init__(self, value):
self.value = value
class Deferred:
def __init__(self, func):
self.func = func
def cook(platter):
if base_case:
return Computed(x)
else:
return Deferred(lambda: cook(transform(x)))
def bounce(result):
if isinstance(result, Deferred):
return bounce(result.func())
return result.valueAdesso Computed e Deferred sono tipi distinti, il discriminante è isinstance non callable, e i traceback mostrano Deferred invece di lambda anonime. Ma non è quello che è stato fatto, perché questo interprete usa callable() come discriminante, mantiene la sovrapposizione come caratteristica e la chiama Schrödinger Recursion invece di ammettere che è un bug risolto a metà.
Il più vicino in letteratura è il visitor pattern con trampolining in Scheme:
(define (eval expr env)
(cond
((number? expr) expr)
((symbol? expr) (env expr))
(else (lambda () (eval (car expr) env)))))
(define (trampoline f)
(if (procedure? f)
(trampoline (f))
f))Ma anche qui i tipi sono espliciti, (lambda ...) produce un tipo distinto, e (procedure? ...) è un predicato di tipo, non callable() applicato a tutto indiscriminatamente. Il punto è che la maggior parte dei linguaggi non permette di ritornare "int o funzione" senza un wrapper esplicito ma Python sì e questo interprete ne approfitta nel modo più scomodo possibile.
Nella sezione precedente abbiamo risolto il paradosso culinario di Schrödinger ma i callable che sono valori vengono marcati esplicitamente così da non essere eseguiti per errore. Ma c'è un'altra direzione in cui si può andare, ed è molto più radicale. Invece di insegnare a bounce a distinguere thunk da valori, si può eliminare bounce del tutto, cioè se ogni ramo di compute ritorna una lambda, e ogni lambda viene applicata immediatamente, allora il trampolining non è una funzione esterna... è la struttura stessa del codice.
def compute(x):
return (lambda f: f())(
(lambda: x) if is_base(x) else lambda: compute(transform(x))
)La lambda interna (lambda f: f()) prende il risultato della condizione e lo chiama subito. Sia che il ramo produca (lambda: x), un valore wrappato, sia che produca lambda: compute(transform(x)), una computazione differita, entrambi vengono applicati immediatamente.
La traccia per un caso base è:
compute(42)
→ (lambda f: f())(lambda: 42)
→ (lambda: 42)()
→ 42
La traccia per un caso ricorsivo è:
compute(x)
→ (lambda f: f())(lambda: compute(transform(x)))
→ (lambda: compute(transform(x)))()
→ compute(transform(x))
→ (lambda f: f())(lambda: compute(transform(transform(x))))
→ ...
Il confronto con il trampoline classico chiarisce cosa è cambiato:
# Schrödinger classico: due passaggi per livello
compute(x) → lambda₁
bounce(lambda₁) → esegui
compute(next) → lambda₂
bounce(lambda₂) → esegui
# Autoapplicazione forzata
compute(x) → esecuzione immediata
compute(next) → esecuzione immediata
...bounce è sparito... Ogni chiamata a compute si risolve da sola... Ma i casi base passano per una lambda inutile, infatti (lambda: x)(), crea una closure solo per applicarla subito e buttarla via. Si può ottimizzare:
def compute(x):
if is_base(x):
return x # nessuna lambda, nessun overhead
return (lambda: compute(transform(x)))() # solo i ricorsivi sono wrappatiAdesso i casi base non passano per lambda, e i casi ricorsivi si autoapplicano. È il compromesso intelligente tra "folle" e "inutile". Vediamo anche che la forma con lambda esplicita:
compute = lambda x: (lambda f: f())(
x if is_base(x) else lambda: compute(transform(x))
)e la forma equivalente con if callable:
def compute(x):
result = x if is_base(x) else lambda: compute(transform(x))
return result() if callable(result) else resultproducono lo stesso bytecode a runtime. Non è zucchero sintattico nel senso tecnico, Python non riconosce nessuna delle due come un costrutto speciale, ma sono semanticamente identiche.
Fin qui abbiamo fatto tutto in Python, e il risultato è funzionante, appetitoso e divertente ma è anche molto scomodo. Abbiamo lambda annidate che il compilatore non capisce, stack trace confusi, overhead nei casi base, e nessun modo per dichiarare l'intenzione in modo che il tooling ne sappia qualcosa.
Il punto di svolta è passare a un linguaggio in cui l'autoapplicazione forzata non è un hack ma una struttura di controllo legittima. In Scheme:
(define compute
(lambda (x)
((lambda (resolve)
(resolve
(if (base? x)
x
(lambda () (compute (transform x))))))
(lambda (f)
(if (procedure? f) (f) f)))))La struttura è identica a quella Python, ma qui ogni resolve è una tail call, e Scheme fa TCO. E lo stack rimane costante indipendentemente dalla profondità della ricorsione. Ma la cosa più importante è che questa struttura può essere estratta in una macro:
(define-syntax autoapply
(syntax-rules ()
((autoapply condition base-case recursive-case)
((lambda (resolve)
(resolve (if condition base-case (lambda () recursive-case))))
(lambda (f) (if (procedure? f) (f) f))))))
(define compute
(lambda (x)
(autoapply (base? x) x (compute (transform x)))))Adesso il codice dichiara l'intenzione: "questo è trampolinato".
Non lo implica attraverso lambda annidate che si devono decifrare... lo dice esplicitamente, e la macro si occupa di costruire la struttura sottostante. Il compilatore sa cosa sta guardando e può ottimizzarlo di conseguenza.
Si può andare ancora più lontano:
(define-syntax define-trampolined
(syntax-rules ()
((define-trampolined (name args ...)
body ...)
(define (name args ...)
((lambda (resolve)
(resolve body ...))
(lambda (f)
(if (procedure? f) (f) f)))))))
(define-trampolined (compute x)
(if (base? x)
x
(lambda () (compute (transform x)))))Scrivi codice ricorsivo normale, dichiari che è trampolinato e il resto è automatico. E da lì la combinazione con le continuazioni reali diventa ovvia:
(define compute
(lambda (x)
(call/cc
(lambda (escape)
((lambda (resolve)
(resolve (if (base? x) x (lambda () (compute (transform x))))))
(lambda (f) (if (procedure? f) (f) f)))))))Ora il trampolining è una continuazione vera e si può catturare il punto di uscita e saltarci da qualsiasi punto della computazione (il tutto con lazy streams):
(define lazy-sequence
(lambda (n)
(autoapply
(> n limit)
(cons n (lambda () (lazy-sequence (+ n 1)))))))Un compilatore Lisp che vede autoapply o define-trampolined può portarlo in bytecode senza indirezioni:
JUMP_IF condition RESOLVE
PUSH_THUNK recursive
JMP APPLY
RESOLVE:
PUSH base
APPLY:
CALL resolve
E funziona!
Se avete letto fino a qui forse vi siete divertiti, abbiamo usato un difetto del sistema dei tipi di Python come meccanismo architetturale, di solito la gente incontra quel TypeError aggiunge un isinstance e va avanti ma non sempre un errore, o meglio un errore a volte è ispirazione! E a me ha ispirato che la sovrapposizione che sembra un bug è in realtà la stessa sovrapposizione che rende potente la lazy evaluation perché un valore che non è ancora collassato è indistinguibile da una computazione che non è ancora terminata. Ovviamente è qualcosa di già visto, il trampoline come pattern è vecchissimo, la lazy evaluation strutturale con thunk espliciti è Haskell, e la continuation-passing style con autoapplicazione è studiata nella teoria dei linguaggi. In ogni caso io mi sono divertito a ideare la Schrödinger's recursion, spero anche voi a leggerla. Avete capito cosa significa KE?
Il testo non è finito, c'è parecchio ancora da scrivere, appena avrò un po' di tempo in pausa pranzo lo finirò... Arriveremo a vedere come forse python, se supportasse l'homoiconicity diventerebbe uno schifo ma anche potentissimo, infatti vorrei proporre due versioni di Python, una standard e una KE ma ci devo lavorare. Però l'idea a cui si può arrivare è che si potrebe avere un decorator che riceve codice imperativo e genera la versione funzionale equivalente, o viceversa (Davvero? Ci sto pensando per questo il testo non è finito):
@generate_variants
def fibonacci_iterative(n):
a, b = 0, 1
for _ in range(n):
a, b = b, a + b
return bOra se Python KE esistesse il decorator riconoscerebbe il pattern iterativo con due accumulatori e genererebbe automaticamente:
- Una versione ricorsiva con memoization
- Una con matrix exponentiation per n molto grandi
- Una numpy per calcolare array di valori fibonacci
- Una parallela per calcoli batch
- ...
Tutte partendo dalla stessa definizione iterativa, con il decorator che sceglie automaticamente la versione ottimale in base agli argomenti, ma per farlo Python dovrebbe gestire il codice in modo che possa essere struttura dati prima ancora di essere compilato, come in Lisp... avrebbe bisogno di un sistema di macro con accesso garantito all'AST al momento della definizione, non recuperato con getsource() e di un quote/unquote syntax per generare codice in modo sicuro e componibile. In Lisp, il quoting consente di costruire strutture di codice come dati ordinari, con interpolazione di valori in punti specifici. E poi il codice non dovrebbe essere compilato finché la macro non ha deciso cosa farci.
Il limite a 42 è la risposta alla vita, all'universo e a tutto quanto ma è anche, più concretamente, la risposta alla domanda: Quanto possiamo simulare la comprensione del compilatore prima che la simulazione diventi troppo costosa da mantenere? La risposta è quarantadue rimbalzi. Poi conviene usare Racket. Lunga vita e rigatoni alla matriciana 🖖