Crisp -- транслятор и модель процессора

Crispy Lisp: компилятор Lisp-подобного языка и потактовая модель стекового микропрограммируемого процессора на Rust.

• ФИО: Толмачёв Игорь Дмитриевич
• Группа: P3212
• Вариант: lisp | stack | neum | mc | tick | binary | stream | mem | pstr | prob1 | vectora

Расшифровка варианта:

• lisp -- синтаксис на S-выражениях, рекурсия, любое выражение возвращает значение
• stack -- стековая архитектура (без регистров общего назначения)
• neum -- фон-Неймановская память
• mc -- микропрограммное устройство управления
• tick -- модель с точностью до такта
• binary -- настоящий бинарный машинный код
• stream -- потоковый ввод-вывод (останов по концу ввода)
• mem -- ввод-вывод, отображённый на память
• pstr -- строки с префиксом длины
• prob1 -- Project Euler #4 (наибольший палиндром-произведение)
• vectora -- векторное усложнение (WIP).

Проект состоит из трёх крейтов: bytecode (ISA и формат файла), compiler (crispc) и vm (crispvm).

Язык программирования

Crisp -- минималистичный Lisp на S-выражениях.

Синтаксис

program    ::= function+
function   ::= "(" "fn" symbol "(" symbol* ")" expr+ ")"

expr       ::= atom | "(" form ")"
form       ::= let | if | while | for | set | do | call
let        ::= "let" "(" binding+ ")" expr+
binding    ::= "(" symbol expr ")"
if         ::= "if" expr expr expr?
while      ::= "while" expr expr+
for        ::= "for" symbol "from" expr "to" expr expr+
set        ::= "set" symbol expr
do         ::= "do" expr+
call       ::= symbol expr*

atom       ::= integer | string | "true" | "false" | "nil" | symbol
integer    ::= ["+"|"-"] digit+
string     ::= '"' character* '"'
comment    ::= ";" <до конца строки>

Встроенные операции (как функции): + - * / % >> << & | ~ = != > >= < <= fetch store c.

Семантика

• Стратегия вычислений -- eager, аргументы вычисляются слева направо до вызова.
• Любое выражение возвращает значение. if, let, do, set, while, for -- выражения; (set x (if p 1 2)), (store (if p 1 2) 1) корректны. while/for возвращают 0.
• Области видимости -- лексические. let, аргументы fn и переменная for видны только в своём теле; вложенные области перекрывают внешние.
• Типизация -- единственный тип -- знаковое 64-битное целое. true/false -- это 1/0, nil -- 0. Строка -- это указатель на область данных (см. ниже).
• Функции объявляются только на верхнем уровне; поддержаны рекурсия и оптимизация хвостового вызова.
• Тело fn/let/while/for -- неявный do-блок (несколько выражений, значение последнего). У if неявного блока нет -- для нескольких действий в ветке нужен явный (do ...).

Отображение выражений на стек и память

Промежуточные значения сложных выражений живут на стеке: транслятор обходит выражение в постфиксном порядке, оставляя результат на вершине стека. Локальные переменные (let, аргументы, счётчик for) хранятся в стеке в памяти (Memory Stack) и адресуются как Sp + offset (FetchMs/StoreMs). Подробнее в разделе "Организация памяти".

Организация памяти

• Машинное слово -- 64 бита (8 байт), адресация байтовая, память однопортовая, общая для кода и данных.
• Регистров общего назначения нет: вычисления идут на стеке. A, B, AluRes внутренние защёлки АЛУ, не видны программисту.
• Локальные переменные и адреса возврата хранятся в памяти через указатель Sp, который растёт вниз от вершины памяти.

Карта памяти:

addr 0x00 : INPUT  port   (mmio, чтение = ввод)
addr 0x01 : OUTPUT port   (mmio, запись = вывод)
addr 0x02 : секция данных (литералы-строки, статика)   <- DATA_BASE
   ...
addr d    : секция кода (инструкции), точка входа = main
   ...
   (свободная память)
   ...
addr Sp   : вершина кадра (растёт вниз: локали, аргументы, адреса возврата)
addr mem  : начальное значение Sp (= размер памяти)

• Литералы. Целые литералы кодируются непосредственно в инструкции PushLit. Строковые литералы укладываются в секцию данных: сначала длина, затем по одному слову на символ; в код попадает непосредственный указатель на эту запись.
• Константы/статические данные -- это строковые литералы; размещаются в секции данных подряд, в порядке появления при трансляции.
• Переменные. Все переменные отображаются в памяти (регистров нет). Вход в let/fn/for сдвигает Sp вниз (Bump/входной пролог), переменная адресуется как Sp + offset*8; выход возвращает Sp обратно.
• Инструкции располагаются в секции кода, исполняются по Pc.
• Процедуры -- это функции в секции кода; вызов Call кладёт адрес возврата в слово ниже текущего кадра (Sp-8), Ret его снимает.
• Прерываний нет -- вариант stream, ввод-вывод синхронный через порты.

Система команд

Особенности:

• Типы данных -- 64-битные слова; АЛУ трактует их как знаковые i64, флаг переноса считается по беззнаковому переполнению (для арифметики двойной точности).
• Стек и адресация. Источник операндов -- стек данных. Адресация памяти: прямая по вершине стека (Fetch/Store) и относительно Sp (FetchMs/ StoreMs). Переходы -- относительно Pc.
• Ввод-вывод отображён на память (mem): чтение слова по адресу 0 берёт слово (u64) из входного потока, запись по адресу 1 отправляет слово в вывод.
• Поток управления -- Jmp, условные If/Else, вызовы Call/Ret, останов Hlt. Прерываний нет.
• Классификация -- стековая машина (Stack), инструкции без адресов операндов, кроме непосредственного аргумента у части команд.

Набор инструкций

Код операции команды равен адресу её обработчика в микропрограмме UMEM, поэтому декодирование вырождается в UPC = op_code. В скобках -- этот код и число тактов на полный цикл (включая 2 такта выборки-декодирования). Команды с аргументом занимают 9 байт (1 + 8), без аргумента -- 1 байт.

Стек и литералы:

• Nop -- нет операции (2, 3)
• PushLit #lit -- положить литерал на стек (3, 4)
• Dup -- продублировать вершину (17, 3)
• Drop -- снять вершину (18, 3)
• Carry -- положить флаг переноса (31, 3)

Память и кадр:

• Fetch -- ds.push(mem[ds.pop()]) (5, 4)
• FetchMs #off -- ds.push(mem[Sp+off]) (7, 6)
• Store -- mem[ds.pop()] = ds.top (11, 4)
• StoreMs #off -- mem[Sp+off] = ds.pop() (13, 6)
• Bump #off -- Sp += off (19, 5)

Управление:

• Jmp #off -- Pc += off (22, 5)
• If #off -- если вершина != 0, то Pc += off; снять вершину (25, 5)
• Else #off -- если вершина = 0, то Pc += off; снять вершину (28, 5)
• Call #off -- толкнуть адрес возврата, Pc += off (64, 7)
• Ret -- снять адрес возврата в Pc (69, 6)
• Hlt -- останов (73, 2)

АЛУ (бинарные, по 4 такта): Add 32, Sub 34, Mul 36, Div 38, Rem 40, Shr 42, Shl 44, And 46, Or 48, Eq 52, Ne 54, Gt 56, Ge 58, Lt 60, Le 62. Унарная Inv 50 (4 такта).

Кодирование инструкций (binary)

Машинный код -- настоящий бинарный файл с сигнатурой CrispBin:

"CrispBin"            8 байт сигнатуры
entrypoint            u64 LE -- смещение main в секции кода
data_len              u64 LE
code_len              u64 LE
<data>                data_len байт
<code>                code_len байт

Инструкция = 1 байт кода операции + опциональный 8-байтный аргумент (i64 LE: литерал или относительное смещение). Отладочный дамп (crispc -e bytecode) даёт строки вида <адрес> - <HEXCODE> - <мнемоника>:

0000 - 030500000000000000 - push_lit #0x5
0009 - 0B                 - store

Транслятор

Консольное приложение crispc:

crispc <FILE> [OUTPUT] [-e tokens|ast|bytecode] [-m N]

• вход -- файл с исходным кодом; выход -- файл машинного кода (OUTPUT)
• -e печатает промежуточную стадию (токены / AST / дизассемблер)
• -m ограничивает глубину вложенности парсера.

Этапы: лексер -> парсер -> кодогенерация.

Вызовы функций и переходы кодируются относительными смещениями, поэтому код позиционно-независим.

Модель процессора

Консольное приложение crispvm:

crispvm <FILE> [-i IN] [-o OUT] [-v] [-p raw|str|dec|hex] [-m str|dec|hex]
               [--mem BYTES] [--max-ticks N]

• -i/-o -- файлы ввода/вывода (по умолчанию stdin/stdout)
• -p -- как разбирать ввод в слова (raw байт -> слово, str символ -> слово, dec/hex числа -> слова, отрицательные поддержаны)
• -m -- как печатать вывод (символы / десятичные / шестнадцатеричные)
• -v -- потактовый журнал в stderr; --max-ticks -- останов по лимиту тактов.

DataPath

Регистры и флаги:

• PC -- счётчик команд; SP -- указатель кадра; AR -- регистр адреса;
• DS -- стек данных; A/B (в коде lhs/rhs) -- защёлки операндов АЛУ; флаг Carry
• UPC -- счётчик микрокоманд (см. ControlUnit).

Мультиплексоры выбирают источник каждой защёлки (сигналы Sel* приходят из устройства управления; на схеме не разведены, чтобы не загромождать). АЛУ комбинационное: его результат -- функция от A/B, за такт защёлкивается в приёмник (PC/SP/AR/стек). Флаг Carry обновляется по беззнаковому переполнению только командами Add/Sub.

ControlUnit (микропрограммное управление, mc)

Управление микропрограммное: устройство управления -- это память микрокоманд UMEM, адресуемая регистром UPC.

• Микрокоманда -- это один элемент UMEM (UOp): набор сигналов-защёлок (latch_lhs, latch_rhs, latch_pc, latch_sp, latch_ar, latch_upc, latch_carry), их мультиплексоров (sel_lhs, sel_rhs, sel_alu, sel_pc, sel_sp, sel_ar, sel_upc) и операций со стеком/памятью (push, drop, read, write). За один такт исполняется ровно одна микрокоманда.
• Такт -- два фронта. На переднем защёлкиваются регистры (Lhs/Rhs/PC/ SP/AR), на заднем выполняются стек и память. АЛУ всю микрокоманду видит Lhs/Rhs предыдущего шага, поэтому операнды нужно защёлкнуть на шаг раньше, чем берётся результат.
• Цикл выборки-декодирования (микроадреса 0-1, общий для всех команд): latch_ar(Pc) + read (MemVal <- mem[PC]) -> latch_upc(Decode). Декодер (decode_upc) выставляет UPC <- op_code: код операции и есть адрес обработчика в UMEM; неизвестный код даёт UnknownOpCode.
• Обработчик инструкции -- последовательность микрокоманд, заканчивающаяся latch_upc(Zero) (возврат на выборку следующей команды) либо Hlt (no_latch_upc -- останов модели).
• Микрокод хранится отдельно от программы (в vm/src/umem.rs), модель исполняет именно его -- это и обеспечивает точность до такта.

Пример: микропрограмма Add (микроадрес 32, обработчик в 2 такта) -- снять два операнда, сложить с переносом, вернуть результат и перейти к следующей команде:

latch_lhs StackB, latch_rhs StackA, drop
drop, sel_alu Add, latch_carry, push Alu, @1

(@1 -- это latch_pc Inc1 + latch_upc Zero: Pc += 1 и возврат на выборку.)

Конвенция вызова. Call кладёт адрес возврата в слово ниже кадра (latch_sp Dec8 перед записью), Ret его снимает (latch_sp Inc8), поэтому вызов не затирает локальные переменные вызывающего.

Журнал

С ключом -v на каждой инструкции печатается строка вида:

tick 8       pc 0x0014  sp 0x2000  carry 0  store                  stack [5, 1]

-- номер такта, PC, SP, флаг переноса, декодированная инструкция и содержимое стека данных.

Тестирование

Интеграционные тесты -- golden-тесты в golden/: для каждого алгоритма закоммичены исходник, машинный код, дизассемблер, ввод-вывод и журнал. Список и формат -- в golden/README.md. Реализованы обязательные алгоритмы: hello, cat, hello_user_name, sort, double (арифметика двойной точности, 128 бит через флаг переноса) и euler4 (алгоритм варианта).

Юнит-тесты транслятора (compiler/src/**/tests.rs) проверяют лексер, AST и кодогенерацию; тесты модели (vm/src/tests.rs) гоняют скомпилированные программы через процессор и сверяют вывод, включая ошибки (деление на ноль, выход за границы, конец ввода).

Проверка и воспроизводимость:

• python golden/check.py -- перегенерирует golden и падает, если что-то разошлось с закоммиченным (детерминизм гарантирует совпадение байт-в-байт)
• хук pre-commit перед коммитом гоняет cargo fmt, cargo clippy, cargo test и golden/check.py.

Пример инструментальной цепочки:

crispc golden/sort/code.crisp sort.bin
echo "3 9 1 5" | crispvm sort.bin -p dec -m dec      # -> 1 5 9