Анатомія Lisp
Інтерпретатор Lisp на Rust без залежностей — одне гомоіконне значення, одне ітеративне ядро, три рушії виконання. Ось як складаються частини.
ключова ідея
Один enum Value є водночас і розібраним AST, і значенням під час виконання. З цього випливають чотири наслідки — кожен окремою думкою.
Розібране синтаксичне дерево та значення під час виконання — це той самий enum. Між кодом і виконанням немає окремого типу вузла.
pub enum Value {
Nil,
Bool(bool),
Int(i64),
Sym(Rc<str>),
Pair(Rc<Cons>),
Closure(Rc<Closure>),
Builtin(BuiltinFn),
}Список — це лише вкладені пари. cons будує пару; car і cdr розбирають її. Структура програми та структура даних — одна й та сама структура.
;; a list is just nested pairs
(cons 1 (cons 2 (cons 3 '()))) ;; => (1 2 3)
// …and a Pair is two slots:
struct Pair { car: Value, cdr: Value }Оскільки код — це дані, макрос — це лише функція з форм у форми. Квазіцитування будує нову форму, а обчислювач її виконує.
;; a macro maps forms to forms
(defmacro unless (c body)
`(if ,c nil ,body))
;; (unless done (step))
;; => (if done nil (step))Кожен payload у купі живе за Rc, тож передача Value клонує вказівник, а не дерево.
Pair(Rc<Cons>) // payload behind an Rc
let b = a.clone(); // O(1): refcount++,
// shares the same consяк це поєднано
Простежте дроти. Код стає одним гомоіконним значенням, і саме хаб Value — те, з чого читає все інше. Наведіть на вузол, щоб підсвітити його нутрощі.
Текст → токени → одне дерево Value, на явному стеку, що не переповнюється.
Хаб Value живить макророзширювач, середовище та обчислювач.
Обчислювач передає кожну форму деревному обхіднику, ВМ або JIT.
Усі троє бачать ті самі помилки, ті самі builtins, той самий прелюд.
усередині ядра
Три компоненти роблять реальну роботу між кодом і результатом. Кожен працює на явному стеку, тож керована користувачем глибина ніколи не сягає стеку викликів хоста.
Текст стає токенами, далі один цикл на явному стеку згортає їх у дерево Value. Мільйон рівнів вкладеності розбирається без рекурсивного спуску.
struct Frame {
items: Vec<Value>, // gathered so far
wrappers: Vec<Rc<str>>, // pending 'quote
tail: Option<Value>, // after a dot
}
// one loop — never recursive descentОбласті видимості — це ланцюг кадрів Rc<RefCell>. Пошук обходить батьків у циклі; замикання захоплює кадр свого визначення — лексично, не динамічно.
type Env = Rc<RefCell<Environment>>;
fn lookup(env: &Env, name: &str) -> Option<Value> {
let mut cur = env.clone();
loop { // walk parents
if let Some(v) = cur.borrow().vars.get(name)
{ return Some(v.clone()); }
cur = cur.borrow().parent.clone()?;
}
}Машина CEK з явним стеком. Стек викликів Rust лишається три кадри завглибшки; вкладеність живе на купному Vec<Frame>, тож хвостові виклики крутяться у сталому просторі.
enum St { Eval(Value, Env), Ret(Value) }
fn run_loop(mut st: St, mut stack: Vec<Frame>) {
loop {
st = match st {
St::Eval(e, env) => step_eval(e, env, stack)?,
St::Ret(v) => match stack.pop() {
None => return Ok(v),
Some(f) => step_return(f, v, stack)?,
},
};
}
}три способи виконання
Деревний обхідник, байткодова ВМ та JIT — взаємозамінні фронтенди над єдиним обчислювачем, єдиною моделлю середовища та єдиною стандартною бібліотекою. Зміни рушій — мова не зміниться.
Еталонний інтерпретатор і оракул для диференційного тестування — кожен інший рушій звіряється з ним побайтово.
Компілює у компактний набір інструкцій і виконує щільний цикл диспетчеризації. Випереджає CPython 3.14 на циклах і арифметиці.
Опційний, за feature-прапорцем. Генерує машинний код через Cranelift і працює у 10–23× швидше за CPython.
виміряно
Кожна програма виконується на всіх трьох рушіях, і результати мусять збігатися з деревним обхідником побайтово. Швидкість ніколи не коштує правильності.
ніколи не падає
Глибину рекурсії задає ввід користувача, тож кожна частина ядра працює на явному купному стеку замість стеку викликів хоста.
Обчислювач, парсер, принтер і Drop працюють на явних стеках. Мільйон рівнів вкладеності повертає відповідь там, де CPython кидає RecursionError.
Області видимості — це кадри Rc<RefCell<Environment>> із захопленням замикань, що звільняються ітеративно, тож глибокі ланцюги не зруйнують стек хоста.
agree() переганяє кожен тест на ВМ і JIT та звіряє побайтовий вивід із деревним обхідником.
стандартна бібліотека
Пласка нативна таблиця покриває примітиви — арифметику з перевіркою, cons / car / cdr, рівність, предикати. Усе інше — це Lisp, вбудований під час компіляції: fold хвостово-рекурсивний, а map і filter визначені через fold, тож їхня рекурсія живе на купному стеку обчислювача, а не на C-стеку хоста.
(def fold
(lambda (f acc xs)
(if (null? xs) acc
(fold f (f acc (car xs)) (cdr xs)))))
(def map
(lambda (f xs)
(reverse (fold (lambda (a x) (cons (f x) a)) '() xs))))