rusty-lisp 0.45.0

// Copyright (c) 2026 Nicholas Vermeulen
// SPDX-License-Identifier: AGPL-3.0-or-later

use crate::parser::Expr;
use crate::env::{Env, EnvFrame, Value, list, cons};
use reqwest::Client;
use serde::{Deserialize, Serialize};

/// Every special-form / built-in-syntax name the evaluator recognizes as a
/// call head. Single source of truth — the LSP, the command registry, and
/// (help) all read this. Keep in sync with the `match head.as_str()` arms in
/// `eval` — sync is MANUAL and unverified: an arm missing from this list is
/// invisible to the registry, discovery, and the coverage ratchet alike (the
/// ratchet only enforces the reverse direction — every listed name must be
/// exercised or allowlisted).
pub const SPECIAL_FORMS: &[&str] = &[
    "define", "def", "lambda", "fn", "λ", "set!", "set", "let", "let*",
    "letrec", "letrec*", "do", "if", "cond", "when", "unless", "and", "or",
    "begin", "match", "try-catch", "load", "load-relative", "quote",
    "quasiquote", "unquote", "unquote-splicing", "eval", "eval-when",
    "defmacro", "define-macro", "defrust", "defrust*", "checkpoint",
    "command-registry", "deftool", "tool-call", "list-tools", "react-loop", "llm",
];

/// Plain two-row Levenshtein distance — only ever runs on the error path.
fn levenshtein(a: &str, b: &str) -> usize {
    let (a, b): (Vec<char>, Vec<char>) = (a.chars().collect(), b.chars().collect());
    let mut prev: Vec<usize> = (0..=b.len()).collect();
    let mut cur = vec![0usize; b.len() + 1];
    for i in 1..=a.len() {
        cur[0] = i;
        for j in 1..=b.len() {
            let sub = prev[j - 1] + if a[i - 1] == b[j - 1] { 0 } else { 1 };
            cur[j] = sub.min(prev[j] + 1).min(cur[j - 1] + 1);
        }
        std::mem::swap(&mut prev, &mut cur);
    }
    prev[b.len()]
}

/// Build the Undefined error message, with a did-you-mean suggestion when a
/// bound name (or special form) is within edit distance 2 (1 for names ≤3
/// chars), ties broken lexicographically; else an apropos hint for hyphenated
/// names. Error path only — never runs on successful lookups.
fn undefined_error(env: &Env, name: &str) -> String {
    let cutoff = if name.len() <= 3 { 1 } else { 2 };
    let mut best: Option<(usize, String)> = None;
    let mut consider = |cand: &str| {
        if cand == name { return; }
        let d = levenshtein(name, cand);
        if d <= cutoff {
            let better = match &best {
                None => true,
                Some((bd, bn)) => d < *bd || (d == *bd && cand < bn.as_str()),
            };
            if better { best = Some((d, cand.to_string())); }
        }
    };
    for sf in SPECIAL_FORMS { consider(sf); }
    let mut frame = Some(env.clone());
    while let Some(f) = frame {
        for k in f.borrow().vars.keys() { consider(k); }
        let parent = f.borrow().parent.clone();
        frame = parent;
    }
    if let Some((_, s)) = best {
        return format!("Undefined: '{}' — did you mean '{}'?", name, s);
    }
    match name.split_once('-') {
        Some((prefix, _)) if !prefix.is_empty() =>
            format!("Undefined: '{}' (try (apropos \"{}\"))", name, prefix),
        _ => format!("Undefined: '{}'", name),
    }
}

#[derive(Serialize, Deserialize)]
struct ChatMessage {
    role: String,
    content: String,
}

#[derive(Serialize)]
struct ChatRequest {
    model: String,
    messages: Vec<ChatMessage>,
    temperature: f32,
    max_tokens: Option<u32>,
}

#[derive(Deserialize)]
struct ResponseMessage {
    content: Option<String>,
    reasoning_content: Option<String>,
}

#[derive(Deserialize)]
struct ChatChoice {
    message: ResponseMessage,
    finish_reason: Option<String>,
}

#[derive(Deserialize)]
struct ChatResponse {
    choices: Vec<ChatChoice>,
}

pub struct Evaluator;

impl Evaluator {
    pub fn new() -> Self { Evaluator }

    // One tokio runtime for every LLM call — building a fresh runtime per
    // call (the old behavior) spins up and tears down a thread pool each
    // time. First use initializes it; it lives for the process.
    fn llm_runtime() -> &'static tokio::runtime::Runtime {
        static RT: std::sync::OnceLock<tokio::runtime::Runtime> = std::sync::OnceLock::new();
        RT.get_or_init(|| tokio::runtime::Runtime::new()
            .expect("failed to initialize tokio runtime for LLM calls"))
    }

    // ── LLM Builtin ───────────────────────────────────────────────────────
    async fn call_llm(prompt: &str, temperature: f32, max_tokens: Option<u32>) -> Result<String, String> {
        // Without a timeout a hung llama-server freezes the whole
        // interpreter (the runtime block_on's this future). Default 120s,
        // overridable via RUSTY_LLM_TIMEOUT_SECS.
        let timeout_secs = std::env::var("RUSTY_LLM_TIMEOUT_SECS").ok()
            .and_then(|s| s.parse::<u64>().ok())
            .unwrap_or(120);
        let client = Client::builder()
            .timeout(std::time::Duration::from_secs(timeout_secs))
            .build()
            .map_err(|e| format!("LLM client build failed: {}", e))?;

        // llama-server ignores the model name for a single loaded model, so
        // the fallback is a neutral placeholder — set RUSTY_MODEL to target
        // a specific model on multi-model servers.
        let model = std::env::var("RUSTY_MODEL")
            .unwrap_or_else(|_| "local-model".to_string());
        let url = std::env::var("RUSTY_LLM_URL")
            .unwrap_or_else(|_| "http://localhost:8080/v1/chat/completions".to_string());
        let system = std::env::var("RUSTY_SYSTEM")
            .unwrap_or_else(|_| "You are a helpful AI assistant. Be concise and direct.".to_string());

        let request = ChatRequest {
            model,
            messages: vec![
                ChatMessage { role: "system".to_string(), content: system },
                ChatMessage { role: "user".to_string(),   content: prompt.to_string() },
            ],
            temperature,
            max_tokens,
        };

        let response = client
            .post(&url)
            .json(&request)
            .send()
            .await
            .map_err(|e| format!(
                "LLM request failed (is llama-server running? timeout is {}s): {}", timeout_secs, e))?
            .json::<ChatResponse>()
            .await
            .map_err(|e| format!("LLM response parse error: {}", e))?;

        let choice = response.choices.first()
            .ok_or_else(|| "No response from LLM".to_string())?;
        let content = choice.message.content.as_deref().unwrap_or("").trim();
        if !content.is_empty() {
            return Ok(content.to_string());
        }
        // Empty content = a reasoning model spent the whole reply thinking.
        // If it stopped naturally the reasoning tail may hold the answer, but
        // if it hit max_tokens it's truncated chain-of-thought — refusing it
        // beats handing raw thinking to the caller as if it were the reply.
        if choice.finish_reason.as_deref() == Some("length") {
            return Err("LLM hit max_tokens while still reasoning (no final content) — raise the token budget".to_string());
        }
        Ok(choice.message.reasoning_content.clone()
            .unwrap_or_default()
            .trim()
            .to_string())
    }

    pub fn eval_all(&self, ast: &[Expr], env: &Env) -> Result<Value, String> {
        let mut result = Value::Nil;
        for expr in ast { result = self.eval(expr, env)?; }
        Ok(result)
    }

    pub fn eval(&self, expr: &Expr, env: &Env) -> Result<Value, String> {
        // Leaf fast path (v0.34.0 profiling): the trampoline below clones
        // `expr` on entry, and for Expr::Symbol that clone is a String
        // allocation — paid on every argument evaluation, ~15% of
        // call-heavy runtime. Leaves never loop, so answer them from the
        // borrow before cloning anything.
        match expr {
            Expr::Number(n) => return Ok(Value::Number(*n)),
            Expr::Bool(b)   => return Ok(Value::Bool(*b)),
            Expr::String(s) => return Ok(Value::String(s.clone())),
            Expr::Nil       => return Ok(Value::Nil),
            Expr::Symbol(s) => {
                return EnvFrame::get(env, s)
                    .ok_or_else(|| undefined_error(env, s));
            }
            _ => {}
        }
        let mut cur = expr.clone();
        let mut env = env.clone();

        loop {
            match &cur {
                Expr::Number(n) => return Ok(Value::Number(*n)),
                Expr::Bool(b)   => return Ok(Value::Bool(*b)),
                Expr::String(s) => return Ok(Value::String(s.clone())),
                Expr::Nil       => return Ok(Value::Nil),

                Expr::Symbol(s) => {
                    return EnvFrame::get(&env, s)
                        .ok_or_else(|| undefined_error(&env, s));
                }

                Expr::List(lst) => {
                    if lst.is_empty() { return Ok(Value::Nil); }

                    if let Expr::Symbol(head) = &lst[0] {
                        // Coverage: this is the one place a call's operator name
                        // is known — special forms and ordinary calls alike — so
                        // recording here attributes every invoked command by the
                        // name actually written. Off by default (one bool read).
                        if crate::trace::coverage_enabled() { crate::trace::cover(head); }
                        match head.as_str() {

                            // ── LLM Call ─────────────────────────────────
                            "llm" => {
                                if lst.len() < 2 {
                                    return Err("(llm prompt [temperature] [max-tokens])".into());
                                }
                                let prompt = match self.eval(&lst[1], &env)? {
                                    Value::String(s) => s,
                                    _ => return Err("llm: prompt must be a string".into()),
                                };
                                let temp = if lst.len() > 2 {
                                    match self.eval(&lst[2], &env)? {
                                        Value::Number(n) => n as f32,
                                        _ => 0.7,
                                    }
                                } else { 0.7 };
                                let max_t = if lst.len() > 3 {
                                    match self.eval(&lst[3], &env)? {
                                        Value::Number(n) => Some(n as u32),
                                        _ => None,
                                    }
                                } else { None };

                                let t0 = crate::trace::start();
                                let result = Self::llm_runtime()
                                    .block_on(Self::call_llm(&prompt, temp, max_t));
                                if let Ok(ref r) = result {
                                    crate::trace::record_since("llm", "llm", t0,
                                        Some(format!("prompt-chars={} response-chars={}", prompt.len(), r.len())));
                                }

                                return result.map(Value::String);
                            }

                            // ── deftool ───────────────────────────────────
                            "deftool" => {
                                if lst.len() < 4 {
                                    return Err("deftool: (deftool name (params) \"description\" body...)".into());
                                }
                                let name = sym_name(&lst[1], "deftool")?;
                                let params = match &lst[2] {
                                    Expr::List(ps) => ps.iter().map(|p| sym_name(p, "deftool param"))
                                        .collect::<Result<Vec<_>, _>>()?,
                                    _ => return Err("deftool: params must be a list".into()),
                                };
                                let description = match self.eval(&lst[3], &env)? {
                                    Value::String(s) => s,
                                    _ => return Err("deftool: description must be a string".into()),
                                };
                                let body = std::rc::Rc::new(lst[4..].to_vec());
                                EnvFrame::set(&env, name.clone(), Value::Tool {
                                    name, description, params: std::rc::Rc::new(params), body, env: env.clone(),
                                });
                                return Ok(Value::Nil);
                            }

                            // ── tool-call ─────────────────────────────────
                            "tool-call" => {
                                if lst.len() < 2 {
                                    return Err("tool-call: (tool-call \"name\" args...)".into());
                                }
                                let name = match self.eval(&lst[1], &env)? {
                                    Value::String(s) => s,
                                    Value::Symbol(s) => s,
                                    _ => return Err("tool-call: name must be a string".into()),
                                };
                                let args: Result<Vec<Value>, _> = lst[2..]
                                    .iter().map(|a| self.eval(a, &env)).collect();
                                let args = args?;
                                match EnvFrame::get(&env, &name) {
                                    Some(Value::Tool { params, body, env: tenv, .. }) => {
                                        let child = EnvFrame::new(Some(tenv.clone()));
                                        for (p, a) in params.iter().zip(args.iter()) {
                                            EnvFrame::set(&child, p.clone(), a.clone());
                                        }
                                        let t0 = crate::trace::start();
                                        let last = body.len() - 1;
                                        for e in &body[..last] { self.eval(e, &child)?; }
                                        let result = self.eval(&body[last], &child);
                                        crate::trace::record_since("tool-call", &name, t0, None);
                                        return result;
                                    }
                                    Some(Value::Builtin(_, f)) => return f(&args),
                                    Some(Value::Lambda { params, rest, body, env: lenv }) => {
                                        let child = EnvFrame::extend(&lenv, &params, &rest, args)?;
                                        let last = body.len() - 1;
                                        for e in &body[..last] { self.eval(e, &child)?; }
                                        return self.eval(&body[last], &child);
                                    }
                                    _ => return Err(format!("Unknown tool: {}", name)),
                                }
                            }

                            // ── list-tools ─────────────────────────────────
                            "list-tools" => {
                                let mut tools = Vec::new();
                                fn collect_tools(env: &Env, out: &mut Vec<Value>) {
                                    let frame = env.borrow();
                                    for (name, v) in &frame.vars {
                                        if let Value::Tool { description, params, .. } = v {
                                            out.push(crate::env::list(vec![
                                                Value::Symbol(name.clone()),
                                                Value::String(description.clone()),
                                                crate::env::list(params.iter().map(|p| Value::Symbol(p.clone())).collect()),
                                            ]));
                                        }
                                    }
                                    if let Some(ref parent) = frame.parent {
                                        collect_tools(parent, out);
                                    }
                                }
                                collect_tools(&env, &mut tools);
                                return Ok(list(tools));
                            }

                            // ── react-loop goal max-steps) ────────────────────
                            // ReAct: Reason → Act → Observe loop
                            // The LLM reasons about which tool to call,
                            // Rusty executes it, result feeds back to LLM.
                            "react-loop" => {
                                if lst.len() < 2 {
                                    return Err("react-loop: (react-loop goal [max-steps])".into());
                                }
                                let goal = match self.eval(&lst[1], &env)? {
                                    Value::String(s) => s,
                                    other => format!("{}", other),
                                };
                                let max_steps = if lst.len() > 2 {
                                    match self.eval(&lst[2], &env)? {
                                        Value::Number(n) => n as usize,
                                        _ => 10,
                                    }
                                } else { 10 };

                                // Build tool descriptions for system prompt
                                let mut tool_descs = String::new();
                                {
                                    let frame = env.borrow();
                                    for (_, v) in &frame.vars {
                                        if let Value::Tool { name, description, params, .. } = v {
                                            tool_descs.push_str(&format!(
                                                "- {}{}: {}\n",
                                                name,
                                                if params.is_empty() { String::new() }
                                                else { format!("({})", params.join(", ")) },
                                                description
                                            ));
                                        }
                                    }
                                }

                                let system = format!(
                                    "You are an AI agent. Complete the goal using available tools.\n\
                                     Available tools:\n{}\n\
                                     To use a tool, respond with:\n\
                                     ACTION: tool-name\nINPUT: argument\n\n\
                                     When done, respond with:\n\
                                     FINAL: your answer",
                                    tool_descs
                                );

                                let mut history = format!("Goal: {}\n", goal);
                                let mut last_result = Value::Nil;

                                for step in 0..max_steps {
                                    let prompt = format!("{}\nStep {}:", history, step + 1);
                                    let full_prompt = format!("{}\n\n{}", system, prompt);

                                    let t0 = crate::trace::start();
                                    let response = Self::llm_runtime()
                                        .block_on(Self::call_llm(&full_prompt, 0.3, Some(200)));

                                    let response = match response {
                                        Ok(r) => r,
                                        Err(e) => return Err(format!("react-loop: LLM error: {}", e)),
                                    };
                                    crate::trace::record_since("llm", "react-llm", t0,
                                        Some(format!("prompt-chars={} response-chars={}", full_prompt.len(), response.len())));

                                    // Parse ACTION / FINAL from response
                                    if response.contains("FINAL:") {
                                        if let Some(ans) = response.split("FINAL:").nth(1) {
                                            crate::trace::record("react-step", "final", None,
                                                Some(format!("step={}", step + 1)));
                                            last_result = Value::String(ans.trim().to_string());
                                            break;
                                        }
                                    } else if response.contains("ACTION:") {
                                        let action = response.split("ACTION:").nth(1)
                                            .unwrap_or("").lines().next().unwrap_or("").trim();
                                        let input = response.split("INPUT:").nth(1)
                                            .unwrap_or("").lines().next().unwrap_or("").trim();

                                        // Try to call the tool
                                        let t0 = crate::trace::start();
                                        let obs = match EnvFrame::get(&env, action) {
                                            Some(Value::Tool { params, body, env: tenv, .. }) => {
                                                let child = EnvFrame::new(Some(tenv.clone()));
                                                if !params.is_empty() {
                                                    EnvFrame::set(&child, params[0].clone(),
                                                        Value::String(input.to_string()));
                                                }
                                                let last = body.len() - 1;
                                                for e in &body[..last] { let _ = self.eval(e, &child); }
                                                match self.eval(&body[last], &child) {
                                                    Ok(v) => format!("{}", v),
                                                    Err(e) => format!("Error: {}", e),
                                                }
                                            }
                                            _ => format!("Unknown tool: {}", action),
                                        };
                                        crate::trace::record_since("react-step", action, t0,
                                            Some(format!("step={} input-chars={}", step + 1, input.len())));

                                        history.push_str(&format!(
                                            "\nStep {}: ACTION={} INPUT={}\nOBSERVATION: {}\n",
                                            step + 1, action, input, obs
                                        ));
                                        last_result = Value::String(obs);
                                    } else {
                                        // Pure reasoning step
                                        history.push_str(&format!("\nThought: {}\n", response.trim()));
                                    }
                                }

                                return Ok(last_result);
                            }

                            // ── (load "file.lisp") ──────────────────────
                            "load" | "load-relative" => {
                                if lst.len() != 2 {
                                    return Err(format!("{}: expects a filename", head));
                                }
                                let path_val = self.eval(&lst[1], &env)?;
                                let path_str = match &path_val {
                                    Value::String(s) => s.clone(),
                                    _ => return Err(format!("{}: filename must be a string", head)),
                                };
                                let code = std::fs::read_to_string(&path_str)
                                    .map_err(|e| format!("load: cannot read '{}': {}", path_str, e))?;
                                let tokens = crate::lexer::Lexer::new(&code).tokenize();
                                let ast    = crate::parser::Parser::new(tokens).parse();
                                // Loaded files evaluate at TOP LEVEL (the
                                // global env), like Scheme's load — so a
                                // load inside a function (e.g. pkg-load)
                                // defines durable bindings, not frame-local
                                // ones that vanish with the call.
                                let mut top = env.clone();
                                loop {
                                    let parent = top.borrow().parent.clone();
                                    match parent { Some(p) => top = p, None => break }
                                }
                                return self.eval_all(&ast, &top);
                            }

                            // ── (checkpoint "file.lisp") ────────────────
                            // Snapshot the global env as plain Lisp source;
                            // restore is just (load "file.lisp"). See
                            // checkpoint.rs for what gets serialized.
                            "checkpoint" => {
                                if lst.len() != 2 {
                                    return Err("checkpoint: (checkpoint \"file.lisp\")".into());
                                }
                                let path = match self.eval(&lst[1], &env)? {
                                    Value::String(s) => s,
                                    _ => return Err("checkpoint: filename must be a string".into()),
                                };
                                return crate::checkpoint::write_checkpoint(&path, &env);
                            }

                            // ── (command-registry) → rows of every command ──
                            "command-registry" => {
                                // Walk to the root (global) frame.
                                let mut root = env.clone();
                                loop {
                                    let next = root.borrow().parent.clone();
                                    match next { Some(p) => root = p, None => break }
                                }
                                let mut rows: Vec<Value> = Vec::new();
                                for (name, val) in root.borrow().vars.iter() {
                                    let (kind, sig) = match val {
                                        Value::Builtin(..) => ("builtin", String::new()),
                                        Value::Lambda { params, rest, .. } =>
                                            ("function", fmt_sig(name, params, rest)),
                                        Value::Macro { params, rest, .. } =>
                                            ("macro", fmt_sig(name, params, rest)),
                                        Value::Tool { params, .. } =>
                                            ("function", fmt_sig(name, params, &None)),
                                        Value::Native { .. } | Value::NativeGrad { .. } =>
                                            ("function", String::new()),
                                        _ => continue, // plain data bindings aren't commands
                                    };
                                    let cat = crate::interp::category_of(name)
                                        .unwrap_or_else(|| "other".to_string());
                                    rows.push(crate::env::list(vec![
                                        Value::String(name.clone()),
                                        Value::Symbol(kind.to_string()),
                                        Value::String(sig),
                                        Value::Symbol(cat),
                                    ]));
                                }
                                for sf in crate::eval::SPECIAL_FORMS {
                                    rows.push(crate::env::list(vec![
                                        Value::String((*sf).to_string()),
                                        Value::Symbol("special-form".to_string()),
                                        Value::String(String::new()),
                                        Value::Symbol("special-form".to_string()),
                                    ]));
                                }
                                return Ok(crate::env::list(rows));
                            }

                            // ── (try-catch body (err) handler) ──────────
                            "try-catch" => {
                                if lst.len() < 4 {
                                    return Err("try-catch: (try-catch body (err) handler)".into());
                                }
                                match self.eval(&lst[1], &env) {
                                    Ok(v) => return Ok(v),
                                    Err(e) => {
                                        let catch_env = EnvFrame::new(Some(env.clone()));
                                        if let Expr::List(vars) = &lst[2] {
                                            if let Some(Expr::Symbol(name)) = vars.first() {
                                                EnvFrame::set(&catch_env, name.clone(),
                                                    Value::String(e));
                                            }
                                        }
                                        cur = lst[3].clone();
                                        env = catch_env;
                                        continue;
                                    }
                                }
                            }

                            // ── (match expr (pat body)...) ───────────────
                            "match" => {
                                if lst.len() < 3 {
                                    return Err("match: (match expr (pattern body)...)".into());
                                }
                                let subject = self.eval(&lst[1], &env)?;
                                let mut matched = None;
                                'clauses: for clause in &lst[2..] {
                                    if let Expr::List(c) = clause {
                                        if c.len() < 2 { continue; }
                                        let pat = &c[0];
                                        let body_exprs = &c[1..];
                                        let mut bindings: Vec<(String, Value)> = Vec::new();
                                        if match_pattern(pat, &subject, &mut bindings) {
                                            let match_env = EnvFrame::new(Some(env.clone()));
                                            for (name, val) in bindings {
                                                EnvFrame::set(&match_env, name, val);
                                            }
                                            let last = body_exprs.len() - 1;
                                            for e in &body_exprs[..last] {
                                                self.eval(e, &match_env)?;
                                            }
                                            matched = Some((body_exprs[last].clone(), match_env));
                                            break 'clauses;
                                        }
                                    }
                                }
                                match matched {
                                    Some((body, match_env)) => {
                                        cur = body;
                                        env = match_env;
                                        continue;
                                    }
                                    None => return Err(format!("match: no clause matched {}", subject)),
                                }
                            }

                            // ── Quote / Quasiquote ────────────────────────
                            "quote" => {
                                if lst.len() != 2 { return Err("quote: expects 1 arg".into()); }
                                return Ok(expr_to_value(&lst[1]));
                            }

                            // ── eval: run a data value as code, in the
                            // CURRENT env (unlike eval-string's deliberate
                            // fresh env). Rebinding `cur` makes it a tail
                            // call. Code values (lambdas etc.) inside the
                            // datum don't convert — eval takes pure data.
                            "eval" => {
                                if lst.len() != 2 { return Err("eval: (eval datum)".into()); }
                                let datum = self.eval(&lst[1], &env)?;
                                cur = value_to_expr(&datum);
                                continue;
                            }

                            "quasiquote" => {
                                if lst.len() != 2 { return Err("quasiquote: expects 1 arg".into()); }
                                return self.expand_quasiquote(&lst[1], &env);
                            }

                            // ── Conditionals ──────────────────────────────
                            "if" => {
                                if lst.len() < 3 { return Err("if: (if test then [else])".into()); }
                                let test_val = self.eval(&lst[1], &env)?;
                                if is_truthy(&test_val) {
                                    cur = lst[2].clone();
                                } else if lst.len() > 3 {
                                    cur = lst[3].clone();
                                } else {
                                    return Ok(Value::Nil);
                                }
                                continue;
                            }

                            "when" => {
                                if lst.len() < 3 { return Err("when: (when test body...)".into()); }
                                let test_val = self.eval(&lst[1], &env)?;
                                if is_truthy(&test_val) {
                                    let last = lst.len() - 1;
                                    for e in &lst[2..last] { self.eval(e, &env)?; }
                                    cur = lst[last].clone(); continue;
                                }
                                return Ok(Value::Nil);
                            }

                            "unless" => {
                                if lst.len() < 3 { return Err("unless: (unless test body...)".into()); }
                                let test_val = self.eval(&lst[1], &env)?;
                                if !is_truthy(&test_val) {
                                    let last = lst.len() - 1;
                                    for e in &lst[2..last] { self.eval(e, &env)?; }
                                    cur = lst[last].clone(); continue;
                                }
                                return Ok(Value::Nil);
                            }

                            "cond" => {
                                let mut found: Option<Expr> = None;
                                'cond: for clause in &lst[1..] {
                                    if let Expr::List(c) = clause {
                                        if c.is_empty() { continue; }
                                        let is_else = matches!(&c[0], Expr::Symbol(s) if s == "else");
                                        let test_val = if is_else { Value::Bool(true) } else { self.eval(&c[0], &env)? };
                                        if is_truthy(&test_val) {
                                            if c.len() == 1 { return Ok(test_val); }
                                            let last = c.len() - 1;
                                            for e in &c[1..last] { self.eval(e, &env)?; }
                                            found = Some(c[last].clone());
                                            break 'cond;
                                        }
                                    }
                                }
                                match found {
                                    Some(e) => { cur = e; continue; }
                                    None    => return Ok(Value::Nil),
                                }
                            }

                            // ── Boolean short-circuit ─────────────────────
                            "and" => {
                                if lst.len() == 1 { return Ok(Value::Bool(true)); }
                                let last = lst.len() - 1;
                                for e in &lst[1..last] {
                                    let v = self.eval(e, &env)?;
                                    if !is_truthy(&v) { return Ok(v); }
                                }
                                cur = lst[last].clone(); continue;
                            }

                            "or" => {
                                if lst.len() == 1 { return Ok(Value::Bool(false)); }
                                let last = lst.len() - 1;
                                for e in &lst[1..last] {
                                    let v = self.eval(e, &env)?;
                                    if is_truthy(&v) { return Ok(v); }
                                }
                                cur = lst[last].clone(); continue;
                            }

                            // ── Sequencing ────────────────────────────────
                            "begin" => {
                                if lst.len() == 1 { return Ok(Value::Nil); }
                                let last = lst.len() - 1;
                                for e in &lst[1..last] { self.eval(e, &env)?; }
                                cur = lst[last].clone(); continue;
                            }

                            // (eval-when (phase...) body...) — runs body immediately,
                            // like `begin`. Rusty has no separate compile/load phase,
                            // so `phase` is accepted but not inspected here; the one
                            // place it changes anything is `defmacro`, which runs a
                            // top-level `eval-when` once at *definition* time instead
                            // of once per expansion (see the defmacro handler).
                            "eval-when" => {
                                if lst.len() < 2 { return Err("eval-when: (eval-when (phase...) body...)".into()); }
                                if !matches!(&lst[1], Expr::List(_)) {
                                    return Err("eval-when: phase spec must be a list".into());
                                }
                                if lst.len() == 2 { return Ok(Value::Nil); }
                                let last = lst.len() - 1;
                                for e in &lst[2..last] { self.eval(e, &env)?; }
                                cur = lst[last].clone(); continue;
                            }

                            // ── Definitions ───────────────────────────────
                            "define" => { return self.eval_define(lst, &env); }
                            "def"    => { return self.eval_def(lst, &env); }

                            "set!" => {
                                if lst.len() != 3 { return Err("set!: (set! name value)".into()); }
                                let name = sym_name(&lst[1], "set!")?;
                                let val  = self.eval(&lst[2], &env)?;
                                if !EnvFrame::set_existing(&env, &name, val) {
                                    return Err(format!("set!: undefined variable '{}'", name));
                                }
                                return Ok(Value::Nil);
                            }

                            // Legacy SimpleLisp alias — creates variable if not yet defined
                            "set" => {
                                if lst.len() != 3 { return Err("set: (set name value)".into()); }
                                let name = sym_name(&lst[1], "set")?;
                                let val  = self.eval(&lst[2], &env)?;
                                if !EnvFrame::set_existing(&env, &name, val.clone()) {
                                    EnvFrame::set(&env, name, val);
                                }
                                return Ok(Value::Nil);
                            }

                            // ── Lambdas ───────────────────────────────────
                            "lambda" | "fn" | "λ" => { return self.eval_lambda(lst, &env); }

                            // ── Macros ────────────────────────────────────
                            "defmacro" | "define-macro" => {
                                if lst.len() < 4 { return Err("defmacro: (defmacro name (params) body...)".into()); }
                                let name = sym_name(&lst[1], "defmacro")?;
                                let (params, rest) = match &lst[2] {
                                    Expr::List(ps) => parse_params(ps)?,
                                    _ => return Err("defmacro: params must be a list".into()),
                                };
                                // Compile-time evaluation: a top-level (eval-when (...) body...)
                                // in the macro's body runs once, right now, in def_env — not on
                                // every future expansion. `define`s inside it (e.g. a precomputed
                                // lookup table) land in def_env, which becomes the macro's closure
                                // env, so every expansion can see them via ordinary lookup.
                                let def_env = EnvFrame::new(Some(env.clone()));
                                let mut retained = Vec::new();
                                for stmt in &lst[3..] {
                                    if let Expr::List(items) = stmt {
                                        if let Some(Expr::Symbol(s)) = items.first() {
                                            if s == "eval-when" && items.len() >= 2 && matches!(&items[1], Expr::List(_)) {
                                                for e in &items[2..] { self.eval(e, &def_env)?; }
                                                continue;
                                            }
                                        }
                                    }
                                    retained.push(stmt.clone());
                                }
                                if retained.is_empty() {
                                    return Err("defmacro: body must have an expression after any eval-when blocks".into());
                                }
                                // Hygiene: rename identifiers the macro's own template
                                // introduces (let/lambda/do bindings inside quasiquote)
                                // to fresh gensyms, so they can't capture or be captured
                                // by identifiers from the use site.
                                let body = std::rc::Rc::new(retained.iter().map(hygienic_rename_top).collect::<Vec<_>>());
                                EnvFrame::set(&env, name, Value::Macro { params: std::rc::Rc::new(params), rest, body, env: def_env });
                                return Ok(Value::Nil);
                            }

                            // ── defrust: codegen + compile + load real Rust ──
                            "defrust" => {
                                if lst.len() != 4 { return Err("defrust: (defrust name (params...) body)".into()); }
                                let name = sym_name(&lst[1], "defrust")?;
                                let params = match &lst[2] {
                                    Expr::List(ps) => ps.iter().map(|p| sym_name(p, "defrust param"))
                                        .collect::<Result<Vec<_>, _>>()?,
                                    _ => return Err("defrust: params must be a list".into()),
                                };
                                let native = crate::rust_jit::compile_and_load(&name, &params, &lst[3])?;
                                EnvFrame::set(&env, name, native);
                                return Ok(Value::Nil);
                            }

                            // ── defrust*: a group compiled into ONE .so, so
                            // the functions can call each other (mutual
                            // recursion) — plain Rust calls, no cross-library
                            // linking. (defrust* (name (params...) body)...)
                            "defrust*" => {
                                let mut defs = Vec::with_capacity(lst.len() - 1);
                                for d in &lst[1..] {
                                    let Expr::List(parts) = d else {
                                        return Err("defrust*: each function must be (name (params...) body)".into());
                                    };
                                    if parts.len() != 3 {
                                        return Err("defrust*: each function must be (name (params...) body)".into());
                                    }
                                    let name = sym_name(&parts[0], "defrust*")?;
                                    let params = match &parts[1] {
                                        Expr::List(ps) => ps.iter().map(|p| sym_name(p, "defrust* param"))
                                            .collect::<Result<Vec<_>, _>>()?,
                                        _ => return Err("defrust*: params must be a list".into()),
                                    };
                                    defs.push(crate::rust_jit::FnDef { name, params, body: parts[2].clone() });
                                }
                                let natives = crate::rust_jit::compile_and_load_group(&defs)?;
                                for (d, native) in defs.iter().zip(natives) {
                                    EnvFrame::set(&env, d.name.clone(), native);
                                }
                                return Ok(Value::Nil);
                            }

                            // ── Let forms ─────────────────────────────────
                            "let" => {
                                // Named let: (let loop ((var val)...) body...)
                                if lst.len() > 2 {
                                    if let Expr::Symbol(lname) = &lst[1] {
                                        let lname = lname.clone();
                                        let (e, new_env) = self.eval_named_let(&lname, lst, &env)?;
                                        cur = e; env = new_env; continue;
                                    }
                                }
                                let (e, new_env) = self.eval_let(lst, &env)?;
                                cur = e; env = new_env; continue;
                            }

                            "let*" => {
                                let (e, new_env) = self.eval_let_star(lst, &env)?;
                                cur = e; env = new_env; continue;
                            }

                            "letrec" | "letrec*" => {
                                let (e, new_env) = self.eval_letrec(lst, &env)?;
                                cur = e; env = new_env; continue;
                            }

                            // ── Do loop ───────────────────────────────────
                            "do" => { return self.eval_do(lst, &env); }

                            _ => {} // fall through to macro / function call
                        }
                    }

                    // ── Macro expansion ──
                    if let Expr::Symbol(s) = &lst[0] {
                        if let Some(Value::Macro { params, rest, body, env: mac_env }) =
                            EnvFrame::get(&env, s)
                        {
                            let arg_vals: Vec<Value> = lst[1..].iter().map(expr_to_value).collect();
                            let mac_child = EnvFrame::extend(&mac_env, &params, &rest, arg_vals)?;
                            let last = body.len() - 1;
                            let profile_start = macro_profile::start(s);
                            for e in &body[..last] { self.eval(e, &mac_child)?; }
                            let expanded = self.eval(&body[last], &mac_child)?;
                            macro_profile::finish(s, profile_start);
                            cur = value_to_expr(&expanded);
                            continue;
                        }
                    }

                    // ── Function call ──
                    let func = self.eval(&lst[0], &env)?;
                    let args: Result<Vec<Value>, _> = lst[1..].iter()
                        .map(|a| self.eval(a, &env)).collect();
                    let args = args?;

                    match func {
                        Value::Builtin(_, f) => return f(&args),
                        Value::Lambda { params, rest, body, env: cenv } => {
                            let child = EnvFrame::extend(&cenv, &params, &rest, args)?;
                            let last = body.len() - 1;
                            for e in &body[..last] { self.eval(e, &child)?; }
                            cur = body[last].clone();
                            env = child;
                            continue;
                        }
                        // Tools are first-class callables, same shape as Lambda
                        // (fixed params, no rest) — needed so `apply` and the
                        // 2.3 contract layer (std.lisp safe-call) can invoke
                        // them without going through the tool-call form.
                        Value::Tool { name, params, body, env: tenv, .. } => {
                            if args.len() != params.len() {
                                return Err(format!("{}: expected {} arg(s), got {}", name, params.len(), args.len()));
                            }
                            // Entry-only trace event: this path is a TCO
                            // `continue`, so the call's end isn't observable
                            // here without breaking tail calls.
                            crate::trace::record("tool-enter", &name, None, None);
                            let child = EnvFrame::extend(&tenv, &params, &None, args)?;
                            let last = body.len() - 1;
                            for e in &body[..last] { self.eval(e, &child)?; }
                            cur = body[last].clone();
                            env = child;
                            continue;
                        }
                        Value::Native { name, arity, fn_ptr, .. } => {
                            if args.len() != arity {
                                return Err(format!("{}: expected {} arg(s), got {}", name, arity, args.len()));
                            }
                            let nums: Result<Vec<f64>, String> = args.iter().map(|a| match a {
                                Value::Number(n) => Ok(*n),
                                other => Err(format!("{}: expected a number, got {}", name, other)),
                            }).collect();
                            return Ok(Value::Number(crate::rust_jit::call(fn_ptr, &nums?)));
                        }
                        Value::NativeGrad { name, fn_ptr, in_shapes, out_shapes, .. } => {
                            return crate::rust_jit::call_native_grad(&name, fn_ptr, &in_shapes, &out_shapes, &args);
                        }
                        other => return Err(format!("Not callable: {}", other)),
                    }
                }
            }
        }
    }

    // ── quasiquote ────────────────────────────────────────────────────────
    fn expand_quasiquote(&self, expr: &Expr, env: &Env) -> Result<Value, String> {
        match expr {
            Expr::List(qlst) if !qlst.is_empty() => {
                // (unquote x) → evaluate x
                if let Expr::Symbol(s) = &qlst[0] {
                    if s == "unquote" && qlst.len() == 2 {
                        return self.eval(&qlst[1], env);
                    }
                }
                // Build list, splicing ,@ items
                let mut result = Vec::new();
                for item in qlst.iter() {
                    if let Expr::List(inner) = item {
                        if let Some(Expr::Symbol(s)) = inner.first() {
                            if s == "unquote-splicing" && inner.len() == 2 {
                                match self.eval(&inner[1], env)? {
                                    Value::List(vs) => { result.extend(vs.iter().cloned()); continue; }
                                    Value::Nil      => continue,
                                    v => return Err(format!(",@: expected list, got {}", v)),
                                }
                            }
                        }
                    }
                    result.push(self.expand_quasiquote(item, env)?);
                }
                Ok(crate::env::list(result))
            }
            other => Ok(expr_to_value(other)),
        }
    }

    // ── define / def ────────────────────────────────────────────────────────
    fn eval_define(&self, list: &[Expr], env: &Env) -> Result<Value, String> {
        if list.len() < 3 { return Err("define: needs name and value".into()); }
        match &list[1] {
            Expr::Symbol(name) => {
                let val = self.eval(&list[2], env)?;
                EnvFrame::set(env, name.clone(), val);
            }
            Expr::List(sig) => {
                let name = sym_name(sig.first().ok_or("define: empty signature")?, "define")?;
                let (params, rest) = parse_params(&sig[1..])?;
                let body = std::rc::Rc::new(list[2..].to_vec());
                EnvFrame::set(env, name, Value::Lambda { params: std::rc::Rc::new(params), rest, body, env: env.clone() });
            }
            _ => return Err("define: first arg must be symbol or list".into()),
        }
        Ok(Value::Nil)
    }

    fn eval_def(&self, list: &[Expr], env: &Env) -> Result<Value, String> {
        if list.len() < 3 { return Err("def: needs name and value".into()); }
        if list.len() == 3 { return self.eval_define(list, env); }
        let name = sym_name(&list[1], "def")?;
        let (params, rest) = match &list[2] {
            Expr::List(ps) => parse_params(ps)?,
            _ => return Err("def: params must be a list".into()),
        };
        let body = std::rc::Rc::new(list[3..].to_vec());
        EnvFrame::set(env, name, Value::Lambda { params: std::rc::Rc::new(params), rest, body, env: env.clone() });
        Ok(Value::Nil)
    }

    fn eval_lambda(&self, list: &[Expr], env: &Env) -> Result<Value, String> {
        if list.len() < 3 { return Err("lambda: (lambda (params) body...)".into()); }
        let (params, rest) = match &list[1] {
            Expr::List(ps)  => parse_params(ps)?,
            Expr::Symbol(s) => (vec![], Some(s.clone())),
            _ => return Err("lambda: params must be a list or symbol".into()),
        };
        Ok(Value::Lambda { params: std::rc::Rc::new(params), rest, body: std::rc::Rc::new(list[2..].to_vec()), env: env.clone() })
    }

    // ── let forms ─────────────────────────────────────────────────────────
    // let/let*/letrec evaluate bindings by REFERENCE (v0.35.0 profiling):
    // the old shape went through extract_let_parts, which allocated a
    // bindings Vec, cloned every name String and init Expr, and to_vec'd
    // the body — several allocations per let per evaluation, dominant in
    // let-heavy code like the shouzhong proofs. Only the map key clone and
    // the (usually Rc-bump) body clone remain.
    fn eval_let(&self, list: &[Expr], env: &Env) -> Result<(Expr, Env), String> {
        let bs = let_bindings(list)?;
        let child = EnvFrame::new(Some(env.clone()));
        for b in bs.iter() {
            let (n, init) = let_pair(b)?;
            let v = self.eval(init, env)?;
            EnvFrame::set(&child, n.clone(), v);
        }
        Ok((body_expr(&list[2..]), child))
    }

    fn eval_let_star(&self, list: &[Expr], env: &Env) -> Result<(Expr, Env), String> {
        let bs = let_bindings(list)?;
        let child = EnvFrame::new(Some(env.clone()));
        for b in bs.iter() {
            let (n, init) = let_pair(b)?;
            let v = self.eval(init, &child)?;
            EnvFrame::set(&child, n.clone(), v);
        }
        Ok((body_expr(&list[2..]), child))
    }

    fn eval_letrec(&self, list: &[Expr], env: &Env) -> Result<(Expr, Env), String> {
        let bs = let_bindings(list)?;
        let child = EnvFrame::new(Some(env.clone()));
        for b in bs.iter() {
            let (n, _) = let_pair(b)?;
            EnvFrame::set(&child, n.clone(), Value::Nil);
        }
        for b in bs.iter() {
            let (n, init) = let_pair(b)?;
            let v = self.eval(init, &child)?;
            EnvFrame::set(&child, n.clone(), v);
        }
        Ok((body_expr(&list[2..]), child))
    }

    // Named let: (let loop ((i 0) (acc 1)) body...)
    fn eval_named_let(&self, name: &str, list: &[Expr], env: &Env) -> Result<(Expr, Env), String> {
        let bindings_raw = match &list[2] {
            Expr::List(b) => b,
            _ => return Err("named let: bindings must be a list".into()),
        };
        let mut params = Vec::new();
        let mut inits  = Vec::new();
        for b in bindings_raw.iter() {
            if let Expr::List(pair) = b {
                if pair.len() == 2 {
                    if let Expr::Symbol(n) = &pair[0] {
                        params.push(n.clone());
                        inits.push(pair[1].clone());
                        continue;
                    }
                }
            }
            return Err("named let: each binding must be (var init)".into());
        }
        let body = list[3..].to_vec();
        // Evaluate inits in outer env
        let init_vals: Result<Vec<Value>, _> = inits.iter().map(|e| self.eval(e, env)).collect();
        let init_vals = init_vals?;
        // Create env with the loop function bound
        let loop_env = EnvFrame::new(Some(env.clone()));
        let lambda = Value::Lambda {
            params: std::rc::Rc::new(params.clone()), rest: None,
            body: std::rc::Rc::new(body.clone()), env: loop_env.clone(),
        };
        EnvFrame::set(&loop_env, name.to_string(), lambda);
        // Bind initial param values
        let call_env = EnvFrame::extend(&loop_env, &params, &None, init_vals)?;
        Ok((wrap_begin(body), call_env))
    }

    // ── do loop ─────────────────────────────────────────────────────────
    // (do ((var init step)...) (test result...) body...)
    fn eval_do(&self, list: &[Expr], env: &Env) -> Result<Value, String> {
        if list.len() < 3 { return Err("do: (do ((var init step)...) (test result...) body...)".into()); }
        let var_specs = match &list[1] { Expr::List(v) => v, _ => return Err("do: var specs must be a list".into()) };
        let test_clause = match &list[2] { Expr::List(t) if !t.is_empty() => t, _ => return Err("do: test clause must be a non-empty list".into()) };
        let body = &list[3..];

        let mut names: Vec<String>       = Vec::new();
        let mut inits: Vec<Expr>         = Vec::new();
        let mut steps: Vec<Option<Expr>> = Vec::new();

        for spec in var_specs.iter() {
            if let Expr::List(s) = spec {
                match s.len() {
                    2 => { names.push(sym_name(&s[0], "do")?); inits.push(s[1].clone()); steps.push(None); }
                    3 => { names.push(sym_name(&s[0], "do")?); inits.push(s[1].clone()); steps.push(Some(s[2].clone())); }
                    _ => return Err("do: var spec must be (var init) or (var init step)".into()),
                }
            } else { return Err("do: var spec must be a list".into()); }
        }

        let loop_env = EnvFrame::new(Some(env.clone()));
        for (n, i) in names.iter().zip(inits.iter()) {
            let v = self.eval(i, env)?;
            EnvFrame::set(&loop_env, n.clone(), v);
        }

        loop {
            if is_truthy(&self.eval(&test_clause[0], &loop_env)?) {
                if test_clause.len() == 1 { return Ok(Value::Nil); }
                let last = test_clause.len() - 1;
                for e in &test_clause[1..last] { self.eval(e, &loop_env)?; }
                return self.eval(&test_clause[last], &loop_env);
            }
            for e in body { self.eval(e, &loop_env)?; }
            // Evaluate all steps before updating (simultaneous)
            let new_vals: Result<Vec<Value>, _> = names.iter().zip(steps.iter())
                .map(|(n, step)| match step {
                    Some(s) => self.eval(s, &loop_env),
                    None    => Ok(EnvFrame::get(&loop_env, n).unwrap_or(Value::Nil)),
                }).collect();
            for (n, v) in names.iter().zip(new_vals?.into_iter()) {
                EnvFrame::set(&loop_env, n.clone(), v);
            }
        }
    }
}

// ── free helpers ─────────────────────────────────────────────────────────

pub fn is_truthy(v: &Value) -> bool {
    // #f is the ONLY false value (SPEC §3). Nil, `()`, 0, and "" are all
    // truthy — Nil stays a distinct value (JSON null / void), it is just not false.
    !matches!(v, Value::Bool(false))
}

pub fn expr_to_value(e: &Expr) -> Value {
    match e {
        Expr::Number(n) => Value::Number(*n),
        Expr::Bool(b)   => Value::Bool(*b),
        Expr::String(s) => Value::String(s.clone()),
        Expr::Symbol(s) => Value::Symbol(s.clone()),
        Expr::List(vs)  => list(vs.iter().map(expr_to_value).collect()),
        Expr::Nil       => Value::Nil,
    }
}

pub fn value_to_expr(v: &Value) -> Expr {
    match v {
        Value::Number(n) => Expr::Number(*n),
        Value::Bool(b)   => Expr::Bool(*b),
        Value::String(s) => Expr::String(s.clone()),
        Value::Symbol(s) => Expr::Symbol(s.clone()),
        Value::List(vs)  => crate::parser::elist(vs.iter().map(value_to_expr).collect()),
        _                => Expr::Nil,
    }
}

fn sym_name(e: &Expr, ctx: &str) -> Result<String, String> {
    match e {
        Expr::Symbol(s) => Ok(s.clone()),
        _ => Err(format!("{}: expected a symbol", ctx)),
    }
}

/// Format a callable's signature string, e.g. "(map fn lst)" or
/// "(foo a b . rest)". Used by the command registry.
fn fmt_sig(name: &str, params: &[String], rest: &Option<String>) -> String {
    let mut s = String::from("(");
    s.push_str(name);
    for p in params { s.push(' '); s.push_str(p); }
    if let Some(r) = rest { s.push_str(" . "); s.push_str(r); }
    s.push(')');
    s
}

fn parse_params(exprs: &[Expr]) -> Result<(Vec<String>, Option<String>), String> {
    let mut params = Vec::new();
    let mut rest   = None;
    let mut i = 0;
    while i < exprs.len() {
        match &exprs[i] {
            Expr::Symbol(s) if s == "." => {
                if i + 1 < exprs.len() {
                    if let Expr::Symbol(r) = &exprs[i+1] { rest = Some(r.clone()); break; }
                }
                return Err("malformed rest param after '.'".into());
            }
            Expr::Symbol(s) => params.push(s.clone()),
            _ => return Err("params must be symbols".into()),
        }
        i += 1;
    }
    Ok((params, rest))
}

fn let_bindings(list: &[Expr]) -> Result<&[Expr], String> {
    if list.len() < 3 { return Err("let: (let ((x v)...) body...)".into()); }
    match &list[1] { Expr::List(b) => Ok(b), _ => Err("let: bindings must be a list".into()) }
}

fn let_pair(b: &Expr) -> Result<(&String, &Expr), String> {
    if let Expr::List(pair) = b {
        if pair.len() == 2 {
            if let Expr::Symbol(n) = &pair[0] { return Ok((n, &pair[1])); }
        }
    }
    Err("let: each binding must be (name expr)".into())
}

/// Single-body lets return the body expression itself (a clone that is an
/// Rc bump when it's a list); only multi-expression bodies build a begin.
fn body_expr(body: &[Expr]) -> Expr {
    if body.len() == 1 { body[0].clone() }
    else {
        let mut v = Vec::with_capacity(body.len() + 1);
        v.push(Expr::Symbol("begin".into()));
        v.extend_from_slice(body);
        crate::parser::elist(v)
    }
}

pub fn wrap_begin(mut exprs: Vec<Expr>) -> Expr {
    if exprs.len() == 1 { exprs.remove(0) }
    else { let mut v = vec![Expr::Symbol("begin".into())]; v.extend(exprs); crate::parser::elist(v) }
}

// ── Symbolic differentiation ──────────────────────────────────────────────
//
// `(grad (lambda (x) expr))` (builtin, interp.rs) differentiates `expr`
// symbolically with respect to the lambda's first parameter and returns a
// new callable Lambda for the derivative — no numeric approximation, no
// execution tracing, just AST rewriting via the standard calculus rules.
// Free variables (anything that isn't `var`) are treated as constants.
pub fn symbolic_derivative(expr: &Expr, var: &str) -> Result<Expr, String> {
    match expr {
        Expr::Number(_) => Ok(Expr::Number(0.0)),
        Expr::Symbol(s) if s == var => Ok(Expr::Number(1.0)),
        Expr::Symbol(_) => Ok(Expr::Number(0.0)),
        Expr::List(items) if !items.is_empty() => {
            let head = match &items[0] {
                Expr::Symbol(s) => s.as_str(),
                _ => return Err("grad: unsupported expression (expected an operator)".into()),
            };
            let args = &items[1..];
            match head {
                "+" if !args.is_empty() => {
                    let ds = args.iter().map(|a| symbolic_derivative(a, var)).collect::<Result<Vec<_>, _>>()?;
                    Ok(sum_expr(ds))
                }
                "-" if !args.is_empty() => {
                    let ds = args.iter().map(|a| symbolic_derivative(a, var)).collect::<Result<Vec<_>, _>>()?;
                    Ok(crate::parser::elist(std::iter::once(Expr::Symbol("-".into())).chain(ds).collect()))
                }
                "*" if args.len() >= 2 => {
                    // Sum, over each term, of (product of all terms with that one replaced by its derivative).
                    let mut terms = Vec::new();
                    for i in 0..args.len() {
                        let mut factors = Vec::with_capacity(args.len());
                        for (j, a) in args.iter().enumerate() {
                            factors.push(if i == j { symbolic_derivative(a, var)? } else { a.clone() });
                        }
                        terms.push(crate::parser::elist(std::iter::once(Expr::Symbol("*".into())).chain(factors).collect()));
                    }
                    Ok(sum_expr(terms))
                }
                "/" if args.len() == 1 => {
                    // d/dx[1/a] = -a' / a^2
                    let da = symbolic_derivative(&args[0], var)?;
                    Ok(list2("/", crate::parser::elist(vec![Expr::Symbol("-".into()), da]),
                        list2("*", args[0].clone(), args[0].clone())))
                }
                "/" if args.len() == 2 => {
                    // Quotient rule: (a'b - ab') / b^2
                    let da = symbolic_derivative(&args[0], var)?;
                    let db = symbolic_derivative(&args[1], var)?;
                    let numer = crate::parser::elist(vec![Expr::Symbol("-".into()),
                        list2("*", da, args[1].clone()), list2("*", args[0].clone(), db)]);
                    Ok(list2("/", numer, list2("*", args[1].clone(), args[1].clone())))
                }
                "expt" if args.len() == 2 => {
                    let n = match &args[1] {
                        Expr::Number(n) => *n,
                        _ => return Err("grad: expt only supports a constant numeric exponent".into()),
                    };
                    let da = symbolic_derivative(&args[0], var)?;
                    // n * a^(n-1) * a'
                    let pow = list2("expt", args[0].clone(), Expr::Number(n - 1.0));
                    Ok(crate::parser::elist(vec![Expr::Symbol("*".into()), Expr::Number(n), list2("*", pow, da)]))
                }
                "sqrt" if args.len() == 1 => {
                    // a' / (2 * sqrt(a))
                    let da = symbolic_derivative(&args[0], var)?;
                    let denom = list2("*", Expr::Number(2.0), crate::parser::elist(vec![Expr::Symbol("sqrt".into()), args[0].clone()]));
                    Ok(list2("/", da, denom))
                }
                "sin" if args.len() == 1 => {
                    // cos(a) * a'
                    let da = symbolic_derivative(&args[0], var)?;
                    Ok(list2("*", crate::parser::elist(vec![Expr::Symbol("cos".into()), args[0].clone()]), da))
                }
                "cos" if args.len() == 1 => {
                    // -(sin(a) * a')
                    let da = symbolic_derivative(&args[0], var)?;
                    let inner = list2("*", crate::parser::elist(vec![Expr::Symbol("sin".into()), args[0].clone()]), da);
                    Ok(crate::parser::elist(vec![Expr::Symbol("-".into()), inner]))
                }
                "tan" if args.len() == 1 => {
                    // a' / cos(a)^2
                    let da = symbolic_derivative(&args[0], var)?;
                    let cos_a = crate::parser::elist(vec![Expr::Symbol("cos".into()), args[0].clone()]);
                    Ok(list2("/", da, list2("*", cos_a.clone(), cos_a)))
                }
                "atan" if args.len() == 1 => {
                    // a' / (1 + a^2)
                    let da = symbolic_derivative(&args[0], var)?;
                    let denom = list2("+", Expr::Number(1.0), list2("*", args[0].clone(), args[0].clone()));
                    Ok(list2("/", da, denom))
                }
                "exp" if args.len() == 1 => {
                    // exp(a) * a'
                    let da = symbolic_derivative(&args[0], var)?;
                    Ok(list2("*", crate::parser::elist(vec![Expr::Symbol("exp".into()), args[0].clone()]), da))
                }
                "log" if args.len() == 1 => {
                    // a' / a
                    let da = symbolic_derivative(&args[0], var)?;
                    Ok(list2("/", da, args[0].clone()))
                }
                "if" if args.len() == 3 => {
                    let dthen = symbolic_derivative(&args[1], var)?;
                    let delse = symbolic_derivative(&args[2], var)?;
                    Ok(crate::parser::elist(vec![Expr::Symbol("if".into()), args[0].clone(), dthen, delse]))
                }
                other => Err(format!("grad: unsupported operator '{}' in body", other)),
            }
        }
        _ => Err("grad: unsupported expression in body".into()),
    }
}

fn list2(op: &str, a: Expr, b: Expr) -> Expr { crate::parser::elist(vec![Expr::Symbol(op.into()), a, b]) }

fn sum_expr(mut terms: Vec<Expr>) -> Expr {
    terms.retain(|t| !matches!(t, Expr::Number(n) if *n == 0.0));
    match terms.len() {
        0 => Expr::Number(0.0),
        1 => terms.into_iter().next().unwrap(),
        _ => crate::parser::elist(std::iter::once(Expr::Symbol("+".into())).chain(terms).collect()),
    }
}

// ── Macro expansion profiler ──────────────────────────────────────────────
//
// Off by default (`start` is a single bool check, so zero overhead when
// unused). Turn on with `(macro-profile-on)`, inspect with
// `(macro-profile-report)`, which returns (name call-count
// total-microseconds) rows sorted by total time descending — debugging aid
// for finding which macros are used heavily or expand slowly.
pub mod macro_profile {
    use std::cell::{Cell, RefCell};
    use std::collections::HashMap;
    use std::time::Instant;

    thread_local! {
        static ENABLED: Cell<bool> = Cell::new(false);
        static STATS: RefCell<HashMap<String, (u64, u128)>> = RefCell::new(HashMap::new());
    }

    pub fn set_enabled(on: bool) { ENABLED.with(|c| c.set(on)); }
    pub fn reset() { STATS.with(|s| s.borrow_mut().clear()); }

    pub fn start(_name: &str) -> Option<Instant> {
        if ENABLED.with(|c| c.get()) { Some(Instant::now()) } else { None }
    }

    pub fn finish(name: &str, started: Option<Instant>) {
        if let Some(t0) = started {
            let micros = t0.elapsed().as_micros();
            STATS.with(|s| {
                let mut s = s.borrow_mut();
                let entry = s.entry(name.to_string()).or_insert((0, 0));
                entry.0 += 1;
                entry.1 += micros;
            });
        }
    }

    pub fn report() -> Vec<(String, u64, u128)> {
        STATS.with(|s| {
            let mut rows: Vec<(String, u64, u128)> =
                s.borrow().iter().map(|(k, &(c, t))| (k.clone(), c, t)).collect();
            rows.sort_by(|a, b| b.2.cmp(&a.2));
            rows
        })
    }
}

// ── Macro hygiene ─────────────────────────────────────────────────────────
//
// A defmacro body is ordinary code that runs at expansion time; the only
// part that becomes code at the *use site* is whatever sits inside its
// `quasiquote` templates. Any identifier the template itself binds via
// let/let*/letrec/lambda/do (as opposed to one supplied through `,x`/`,@x`
// from the macro's arguments) is renamed to a fresh gensym once, when the
// macro is defined. Because every expansion still creates its own env
// frame, a fixed rename is enough to guarantee the template's internal
// names can never capture, or be captured by, identifiers coming from the
// call site — while names supplied via unquote (the user's own bindings)
// are left completely untouched.
use std::collections::HashMap;

pub fn hygienic_rename_top(expr: &Expr) -> Expr {
    match expr {
        Expr::List(items) if !items.is_empty() => {
            if let Expr::Symbol(s) = &items[0] {
                if s == "quasiquote" && items.len() == 2 {
                    let map = HashMap::new();
                    return crate::parser::elist(vec![items[0].clone(), hygienic_rename(&items[1], &map)]);
                }
            }
            crate::parser::elist(items.iter().map(hygienic_rename_top).collect())
        }
        other => other.clone(),
    }
}

fn fresh(name: &str, map: &mut HashMap<String, String>) -> String {
    let g = crate::env::gensym_name(name);
    map.insert(name.to_string(), g.clone());
    g
}

fn rename_binding_list(
    bindings: &[Expr],
    outer_map: &HashMap<String, String>,
    child: &mut HashMap<String, String>,
    sequential: bool,
) -> Vec<Expr> {
    let mut out = Vec::new();
    for b in bindings {
        if let Expr::List(pair) = b {
            if pair.len() >= 2 {
                if let Expr::Symbol(n) = &pair[0] {
                    // let*/letrec/do steps may see earlier bindings; plain let
                    // evaluates inits in the outer scope.
                    let val_map: &HashMap<String, String> = if sequential { child } else { outer_map };
                    let renamed_init = hygienic_rename(&pair[1], val_map);
                    let new_name = fresh(n, child);
                    let mut new_pair = vec![Expr::Symbol(new_name), renamed_init];
                    if pair.len() == 3 {
                        new_pair.push(hygienic_rename(&pair[2], child));
                    }
                    out.push(crate::parser::elist(new_pair));
                    continue;
                }
            }
        }
        out.push(hygienic_rename(b, outer_map));
    }
    out
}

fn hygienic_rename(expr: &Expr, map: &HashMap<String, String>) -> Expr {
    match expr {
        Expr::List(items) if !items.is_empty() => {
            if let Expr::Symbol(head) = &items[0] {
                match head.as_str() {
                    "unquote" | "unquote-splicing" => return expr.clone(),

                    // Named let: (let name ((v init)...) body...)
                    "let" if items.len() >= 3 && matches!(&items[1], Expr::Symbol(_)) => {
                        if let (Expr::Symbol(loop_name), Expr::List(bindings)) = (&items[1], &items[2]) {
                            let mut child = map.clone();
                            let new_loop_name = fresh(loop_name, &mut child);
                            let new_bindings = rename_binding_list(bindings, map, &mut child, false);
                            let mut new_items = vec![
                                items[0].clone(),
                                Expr::Symbol(new_loop_name),
                                crate::parser::elist(new_bindings),
                            ];
                            for rest in &items[3..] { new_items.push(hygienic_rename(rest, &child)); }
                            return crate::parser::elist(new_items);
                        }
                    }

                    "let" | "let*" | "letrec" | "letrec*" if items.len() >= 2 => {
                        if let Expr::List(bindings) = &items[1] {
                            let sequential = head != "let";
                            let mut child = map.clone();
                            let new_bindings = rename_binding_list(bindings, map, &mut child, sequential);
                            let mut new_items = vec![items[0].clone(), crate::parser::elist(new_bindings)];
                            for rest in &items[2..] { new_items.push(hygienic_rename(rest, &child)); }
                            return crate::parser::elist(new_items);
                        }
                    }

                    "lambda" | "fn" | "λ" if items.len() >= 2 => {
                        let mut child = map.clone();
                        let new_params = match &items[1] {
                            Expr::List(ps) => {
                                let mut np = Vec::new();
                                for p in ps.iter() {
                                    match p {
                                        Expr::Symbol(s) if s == "." => np.push(p.clone()),
                                        Expr::Symbol(s) => np.push(Expr::Symbol(fresh(s, &mut child))),
                                        other => np.push(hygienic_rename(other, map)),
                                    }
                                }
                                crate::parser::elist(np)
                            }
                            Expr::Symbol(s) => Expr::Symbol(fresh(s, &mut child)),
                            other => other.clone(),
                        };
                        let mut new_items = vec![items[0].clone(), new_params];
                        for rest in &items[2..] { new_items.push(hygienic_rename(rest, &child)); }
                        return crate::parser::elist(new_items);
                    }

                    // (do ((var init step)...) (test result...) body...)
                    "do" if items.len() >= 3 => {
                        if let Expr::List(specs) = &items[1] {
                            let mut child = map.clone();
                            let new_specs = rename_binding_list(specs, map, &mut child, true);
                            let mut new_items = vec![items[0].clone(), crate::parser::elist(new_specs)];
                            for rest in &items[2..] { new_items.push(hygienic_rename(rest, &child)); }
                            return crate::parser::elist(new_items);
                        }
                    }

                    _ => {}
                }
            }
            crate::parser::elist(items.iter().map(|e| hygienic_rename(e, map)).collect())
        }
        Expr::Symbol(s) => match map.get(s) {
            Some(renamed) => Expr::Symbol(renamed.clone()),
            None => expr.clone(),
        },
        other => other.clone(),
    }
}

// ── Pattern matching helper ───────────────────────────────────────────────
//
// Patterns:
//   _                  — wildcard, matches anything
//   42 / "str" / #t   — literal match
//   x                  — symbol binding (binds value to x)
//   (list p1 p2 ...)   — list pattern
//   (cons h t)         — head/tail destructure
//   (quote sym)        — match literal symbol
//   (? pred)           — guard: match if (pred value) is truthy
//
pub fn match_pattern(pat: &Expr, val: &Value, bindings: &mut Vec<(String, Value)>) -> bool {
    match pat {
        // Wildcard
        Expr::Symbol(s) if s == "_" => true,

        // Symbol → bind
        Expr::Symbol(s) => {
            bindings.push((s.clone(), val.clone()));
            true
        }

        // Literal number
        Expr::Number(n) => matches!(val, Value::Number(v) if v == n),

        // Literal bool
        Expr::Bool(b) => matches!(val, Value::Bool(v) if v == b),

        // Literal string
        Expr::String(s) => matches!(val, Value::String(v) if v == s),

        // Nil / empty list
        Expr::Nil => matches!(val, Value::Nil) || matches!(val, Value::List(v) if v.is_empty()),

        // List pattern
        Expr::List(pats) if !pats.is_empty() => {
            // (quote sym) — match literal symbol
            if let Expr::Symbol(head) = &pats[0] {
                if head == "quote" && pats.len() == 2 {
                    if let Expr::Symbol(sym) = &pats[1] {
                        return matches!(val, Value::Symbol(s) if s == sym);
                    }
                }

                // (? pred-expr) — guard pattern (pred applied to value)
                if head == "?" && pats.len() == 2 {
                    // We can't easily eval here without an env reference,
                    // so guard is a symbol predicate check: (? number?) etc.
                    if let Expr::Symbol(pred) = &pats[1] {
                        return match pred.as_str() {
                            "number?"  => matches!(val, Value::Number(_)),
                            "string?"  => matches!(val, Value::String(_)),
                            "boolean?" => matches!(val, Value::Bool(_)),
                            "list?"    => matches!(val, Value::List(_) | Value::Nil),
                            "symbol?"  => matches!(val, Value::Symbol(_)),
                            "nil?"     => matches!(val, Value::Nil),
                            "pair?"    => matches!(val, Value::List(v) if !v.is_empty()),
                            "zero?"    => matches!(val, Value::Number(n) if *n == 0.0),
                            "positive?"=> matches!(val, Value::Number(n) if *n > 0.0),
                            "negative?"=> matches!(val, Value::Number(n) if *n < 0.0),
                            _          => false,
                        };
                    }
                }

                // (cons head tail) — destructure list
                if head == "cons" && pats.len() == 3 {
                    if let Value::List(xs) = val {
                        if xs.is_empty() { return false; }
                        let h = xs[0].clone();
                        let t = list(xs[1..].to_vec());
                        let save = bindings.len();
                        if match_pattern(&pats[1], &h, bindings)
                            && match_pattern(&pats[2], &t, bindings) {
                            return true;
                        }
                        bindings.truncate(save);
                        return false;
                    }
                    return false;
                }
            }

            // (p1 p2 ...) — fixed-length list pattern
            // OR (p1 p2 . rest) — dotted rest pattern (last pat is `. rest-var`)
            if let Value::List(vals) = val {
                // Check for dotted rest: if second-to-last pattern is the symbol "."
                // e.g. pattern (a b . rest) parsed as list [a, b, ., rest]
                let dot_pos = pats.iter().position(|p| matches!(p, Expr::Symbol(s) if s == "."));
                if let Some(dp) = dot_pos {
                    // Fixed part: pats[..dp], rest var: pats[dp+1]
                    if dp + 1 >= pats.len() { return false; }
                    if vals.len() < dp { return false; }
                    let save = bindings.len();
                    for (p, v) in pats[..dp].iter().zip(vals[..dp].iter()) {
                        if !match_pattern(p, v, bindings) {
                            bindings.truncate(save);
                            return false;
                        }
                    }
                    // Bind rest variable to remaining items
                    let rest_val = list(vals[dp..].to_vec());
                    if !match_pattern(&pats[dp+1], &rest_val, bindings) {
                        bindings.truncate(save);
                        return false;
                    }
                    return true;
                }

                // Fixed-length: must match exactly
                if vals.len() != pats.len() { return false; }
                let save = bindings.len();
                for (p, v) in pats.iter().zip(vals.iter()) {
                    if !match_pattern(p, v, bindings) {
                        bindings.truncate(save);
                        return false;
                    }
                }
                true
            } else {
                false
            }
        }

        _ => false,
    }
}

// ── Arena helpers (future optimization) ──────────────────────────────────────
// Currently wraps list() — wire to arena when GC is activated.
#[allow(dead_code)]
pub fn arena_list(items: Vec<Value>) -> Value { list(items) }
#[allow(dead_code)]
pub fn arena_cons(head: Value, tail: Value) -> Value { cons(head, tail) }