Лексична область видимості в Lisp на Rust: середовища, замикання та drop із двома шляхами

Кожне посилання на змінну в мові має розв’язуватися проти чогось, і це щось — середовище. У risp представлення навмисно просте — хеш-мапа на область плюс вказівник на батька, — але два рішення навколо нього не такі: як замикання захоплює область, і як глибокий ланцюжок областей звільняється, не підриваючи стек. Ця стаття — про хребет.

Кадр — це мапа плюс батько

Область — це один Environment: власні прив’язки та необов’язкове посилання на кадр, що його охоплює. Дескриптор має лічильник посилань і внутрішню змінюваність, бо замикання роблять кадри спільними, а set! їх змінює:

/// A shared, mutable handle to an Environment frame.
pub type Env = Rc<RefCell<Environment>>;

pub struct Environment {
    vars: HashMap<Rc<str>, Value>,
    parent: Option<Env>,
}

Глобальний кадр не має батька; кожен інший кадр — це child області, у якій його було створено:

pub fn new_global() -> Env {
    Rc::new(RefCell::new(Environment { vars: HashMap::new(), parent: None }))
}
pub fn child(parent: &Env) -> Env {
    Rc::new(RefCell::new(Environment { vars: HashMap::new(), parent: Some(parent.clone()) }))
}

Цей parent.clone() — це збільшення Rc, а не копіювання прив’язок батька: новий кадр коштує одне виділення та один лічильник посилань, незалежно від того, скільки області сидить над ним. Це структура даних, яку увесь обчислювач пронизує наскрізь: def і прив’язка параметрів пишуть у локальний кадр, виклик створює дочірній, а пошук читає вгору ланцюжком.

Пошук обходить ланцюжок, ітеративно

Читання змінної означає пошук у поточному кадрі, потім у його батькові, потім у його батькові — аж до глобального. Як і все інше, що обходить керовану користувачем глибину, цей обхід є циклом, ніколи не рекурсією — ланцюжок областей завглибшки в тисячі коштує ітерацій у купі, а не кадрів стеку:

pub fn lookup(env: &Env, name: &str) -> Option<Value> {
    let mut cursor = env.clone();
    loop {
        let next = {
            let frame = cursor.borrow();
            if let Some(v) = frame.vars.get(name) { return Some(v.clone()); }
            frame.parent.clone()
        };
        match next {
            Some(parent) => cursor = parent,
            None => return None,
        }
    }
}

Визначення та присвоєння розходяться по очевидній лінії. define завжди пише локальний кадр — саме це дає let чи параметру затінити зовнішню прив’язку. set! натомість обходить ланцюжок у пошуках найближчої наявної прив’язки і змінює її на місці, повертаючи UnboundSymbol, якщо такої немає. Затінення випливає прямо з «define локальний, lookup спершу найближчий»: дочірній кадр може прив’язати x до нового значення, поки x батька лишається недоторканим, а set! із дочірнього сягає вгору й переприв’язує батьків.

Замикання захоплюють кадр, а не копію

Саме для цього й потрібен Rc. Замикання — це його параметри й тіло плюс середовище, у якому його було визначено:

pub struct Closure {
    pub name: Option<Rc<str>>,
    pub params: Vec<Rc<str>>,
    pub rest: Option<Rc<str>>,     // variadic tail
    pub body: Rc<Vec<Value>>,
    pub env: Env,                  // the captured defining scope
}

Захоплення — це просто env: env.clone(), одне збільшення лічильника посилань. Замикання тепер співволодіє своїм визначальним кадром і тримає його живим, доки живе саме замикання, — і це і є лексичне захоплення: повернута лямбда, що закрилася над локальною, усе ще може читати й змінювати її, бо обидва вказують на той самий RefCell. Застосування замикання не сягає назад туди, де його викликали; воно робить child того, де його визначили:

Value::Closure(c) => {
    let frame = child(&c.env);     // extend the DEFINING scope, not the call site
    bind_params(&c, &args, &frame)?;
    // ... evaluate the body in `frame`
}

Цей один рядок — child(&c.env), а не child(&caller_env) — це вся різниця між лексичною та динамічною областю видимості. Захоплений env — це відповідь на питання «що означали вільні змінні в цій лямбді?», зафіксована в момент визначення.

Небезпека: звільнення ланцюжка областей

Спільне володіння кадрами через Rc створює ту саму пастку, що й довгі cons-списки. Замикання захоплює кадр; батько того кадру — інший кадр; звільнення останнього власника найзовнішнішого замикання може запустити ланцюжок Drop, що рекурсує на один кадр Rust на кожен рівень області. Тисяча вкладених let, захоплених замиканням, на наївному похідному Drop рекурсувала б на тисячу кадрів углиб під час teardown.

Але змусити кожне звільнення середовища йти через ітеративний teardown обкладало б податком звичайний випадок — виклик функції, що прив’язує два цілих параметри й повертається, — виділенням пам’яті, якого йому ніколи не треба. Тож Drop має два шляхи.

Drop із двома шляхами

Швидкий шлях — це чиста перевірка: якщо цей кадр не є останнім власником свого батька (хтось інший досі тримає батька, тож звільнення не каскадуватиме вгору ланцюжком) і жодне з його прив’язаних значень не може тримати глибокий граф Rc, то звичайне звільнення полів нікуди не рекурсує. Дай йому статися, не виділяй нічого:

impl Drop for Environment {
    fn drop(&mut self) {
        let parent_unique = self.parent.as_ref()
            .is_some_and(|p| Rc::strong_count(p) == 1);
        let has_deep_value = self.vars.values()
            .any(|v| matches!(v, Value::Pair(_) | Value::Closure(_) | Value::Macro(_)));
        if !parent_unique && !has_deep_value {
            return;   // the hot path: a call frame of atoms, sharing its parent
        }

        // Slow path: we own a (possibly deep) parent chain or a value graph.
        let (parent, vals) = self.take_children();
        let mut seed: Vec<Teardown> = Vec::with_capacity(vals.len() + 1);
        if let Some(p) = parent { seed.push(Teardown::Env(p)); }
        seed.extend(vals.into_iter().map(Teardown::Val));
        dismantle(seed);
    }
}

Повільний шлях переміщує подальші посилання кадру — його батька та його прив’язані значення — на робочий стек у купі, який осушує спільний цикл dismantle. take_children спершу спорожнює кадр, тож на момент звільнення його полів вони вже None/порожні й нікуди не рекурсують. Enum Teardown — це те, що дозволяє одному циклу звільняти обидві небезпеки разом: довгий ланцюжок Value і глибокий ланцюжок Env лягають на той самий стек, тож звільнення замикання, що захопило тисячу кадрів let, так само пласке, як звільнення списку з тисячі елементів.

Умови перевірки несуть основну логіку. parent_unique питає «чи я зараз запущу каскад?» — якщо в батька є інші власники, звільнення мене зупиняється тут, і ланцюжок стає чиєюсь чужою турботою пізніше. has_deep_value питає «чи можуть мої власні прив’язки рекурсувати?» — атоми не можуть, а захоплене замикання чи список можуть. Лише коли одне з цих істинне, ми платимо за ітеративний шлях. Переважно поширений кадр — виклик, що прив’язує пару чисел і спільно володіє глобальним як батьком, — бере ранній return і не коштує нічого.

Ціна, яку стирає VM

У цієї моделі є одна справжня ціна: кожне читання змінної — це хешування рядка та зондування HashMap, повторюване вгору ланцюжком. Для деревообхідного інтерпретатора це гарний компроміс — простий, коректний і безпечний для стеку. Але це також найбільший розрив між наївним інтерпретатором і швидким, і саме тому байткод-VM risp розв’язує кожну змінну до фіксованого індексу слота під час компіляції й читає її як єдиний доступ до масиву stack[base + i] — без мапи, без хешування, без обходу ланцюжка. Ланцюжок середовищ, описаний тут, — це те, що компілятор існує, аби сплющити. Деревообхідний інтерпретатор тримає його, бо ланцюжок — це найпростіша річ, що очевидно коректна, а «очевидно коректне» — це еталон, проти якого швидші двигуни диференційно тестуються.

Представлення — це найпростіша річ, що працює (мапа й вказівник), а кмітливість обмежена двома місцями: однорядковим child(&c.env), що дає лексичне захоплення, та drop із двома шляхами, що тримає звичайний випадок безкоштовним, водночас усе ще звільняючи патологічний ланцюжок без рекурсії. Зроби хребет простим і безпечним для стеку — і оптимізувальні двигуни матимуть щось надійне, що сплющувати.