Чому стандартна бібліотека risp написана на risp, а не на Rust

Кожен інтерпретатор проводить лінію між тим, що написано мовою хоста, і тим, що написано інтерпретованою мовою. Де її провести — зазвичай питання смаку, але в risp одна ділянка цієї лінії є несучою для гарантії коректності. map, filter та fold сидять на боці Lisp, і не випадково.

Нативне ядро — це пласка таблиця

Нативна бібліотека навмисно мала й навмисно нудна. Кожна вбудована функція має ту саму форму — звичайна функція зі зрізу аргументів у результат, — і всі вони зареєстровані в одній плаский таблиці. Жодного трейта, жодного dyn, жодного об’єкта-реєстру:

type BuiltinFn = fn(&[Value]) -> RispResult;

pub fn builtin_entries() -> &'static [(&'static str, BuiltinFn)] {
    &[
        ("+", b_add), ("-", b_sub), ("*", b_mul), ("/", b_div),
        ("=", b_num_eq), ("<", b_lt), (">", b_gt), ("<=", b_le), (">=", b_ge),
        ("cons", b_cons), ("car", b_car), ("cdr", b_cdr),
        ("list", b_list), ("length", b_length), ("append", b_append), ("reverse", b_reverse),
        ("not", b_not), ("eq?", b_eq), ("equal?", b_equal),
        ("null?", b_null), ("pair?", b_pair), ("list?", b_listp),
        // ... type predicates, I/O, error, gensym
    ]
}

Те, що в цій таблиці, — це нескоротне ядро: арифметика, примітиви cons, рівність, предикати, трохи введення-виведення та gensym. Те, чого там немає, так само навмисне, як і те, що є, — немає ані b_map, ані b_filter, ані b_fold. Та сама таблиця встановлюється в глобальне середовище деревообхідного інтерпретатора й у байткод-VM, тож обидва двигуни поділяють одну нативну поверхню, і немає другої реалізації, яку треба тримати синхронізованою.

Нативний бік мусить правильно зробити числову вежу

Плаский підпис ховає справжню роботу. Арифметика, наприклад, має зберігати точні цілі, але промотувати до float тієї миті, коли з’являється float, через варіадичний список аргументів. risp пронизує наскрізь маленький тип Num через fold, аби це зробити:

enum Num { Int(i64), Float(f64) }

fn fold_numeric(op: &'static str, acc: Num, rest: &[Value],
    int_op: fn(i64, i64) -> Result<i64, RispError>,   // checked: traps on overflow
    float_op: fn(f64, f64) -> f64,
) -> Result<Num, RispError> {
    let mut acc = acc;
    for v in rest {
        let n = as_num(op, v)?;
        acc = match (acc, n) {
            (Num::Int(a), Num::Int(b)) => Num::Int(int_op(a, b)?),  // stays exact
            (a, b) => Num::Float(float_op(a.as_f64(), b.as_f64())), // promotes
        };
    }
    Ok(acc)
}

int_op — це перевірена операція, тож (+ a b) спрацьовує пасткою на переповненні, а не загортається — та сама пастка, яку зберігають швидкий шлях VM та вбудована перевірка переповнення JIT, тож усі три двигуни згодні щодо того, що робить (* 9223372036854775807 2). Це саме той вид речей, що має бути нативним: щільна, скінченна операція над примітивними значеннями без виклику назад у код користувача.

Лінія, яку map і fold не можуть перетнути

Тепер функції вищого порядку. map має застосувати свій функціональний аргумент до кожного елемента — а це означає виклик назад в обчислювач. Написаний як нативна вбудована функція, цей зворотний виклик виконується на стеку викликів Rust:

eval -> b_map (native) -> eval(user fn) -> ... -> b_map -> eval(user fn) -> ...
        └─ each layer is a real Rust stack frame ─┘

Тож рекурсія, спрямована через нативний map, споживала б стек хоста на кожен рівень, і достатньо великий вхід переповнив би його — мовчки скасувавши всю гарантію «жоден вхід не валить хост», яку ітеративний обчислювач так наполегливо забезпечує. Обчислювач може нарощувати свій кадровий стек у купі до гігабайтів; нативне повторне входження не може, бо воно прип’яте до кількамегабайтного C-стеку. Це і є вся причина, чому map/filter/fold не є нативними.

Прелюдія: стандартна бібліотека самою мовою

Натомість вони живуть у prelude.lisp, написані на risp, де їхня рекурсія виконується на власному кадровому стеку обчислювача в купі і не може переповнитися. Увесь файл — це три визначення:

;; Left fold. Tail-recursive, so folding a list is constant frame-stack; any
;; recursion in `f` grows the heap frame-stack, not the Rust stack.
(def fold
  (lambda (f init xs)
    (if (null? xs)
        init
        (fold f (f init (car xs)) (cdr xs)))))

;; map and filter in terms of fold + reverse — no native re-entry.
(def map
  (lambda (f xs)
    (reverse (fold (lambda (acc x) (cons (f x) acc)) '() xs))))

(def filter
  (lambda (p xs)
    (reverse (fold (lambda (acc x) (if (p x) (cons x acc) acc)) '() xs))))

fold хвостоворекурсивний, тож він виконується у сталому кадровому стеку, хоч би яким довгим був список, а map/filter визначені через fold, тож вони успадковують це безкоштовно. Кожен примітив, на який вони спираються — null?, car, cdr, cons, reverse, — нативний і скінченний. Рекурсія, що могла б підірватися, — це та, яку постачає користувач у f, і ця рекурсія тепер тече через eval, що нарощує купу, а не стек хоста.

Завантаження: include_str! та один санкціонований panic

Прелюдія вбудована в бінарник і обчислюється під час побудови Interpreter, тим самим шляхом, яким іде код користувача:

impl Interpreter {
    pub fn new() -> Self {
        let global = env::new_global();
        builtins::install(&global);     // native table first
        let interp = Interpreter { global };
        interp.load_prelude();          // then the risp-level stdlib
        interp
    }

    fn load_prelude(&self) {
        const PRELUDE: &str = include_str!("prelude.lisp");
        self.run_source(PRELUDE).expect("prelude.lisp must evaluate cleanly");
    }
}

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

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