Попался мне на глаза Brainfuck-оподобный язык Cow. И решил я написать для него интерпретатор на новомодном Rust. А так как Rust — мультипарадигменный язык, то стиль написания программы будет функциональный. Чтобы узнать что получилось — прошу под кат.
Повествование постараюсь вести в виде туториала, вопросы в комментариях, ценные замечания о недостаточной функциональности — туда же: будем исправлять! А пока что поехали.
Предварительное проектирование
Состояние виртуальной коровы машины будем хранить в неизменяемой переменной state. Все изменения будут производится с помощью функций, имеющих такую семантику:
fn change(previousState: CowVM) -> CowVM // newStateПохоже на Elm, Redux, может ещё на что-то, чего я и сам не знаю. Не правда ли?
На самом деле, именно то, что с самого начала очень хорошо видно, как хранить данные, делает эту задачу пригодной для функционального подхода.
Действительно, что такое виртуальная машина Cow?
- Массив команд — самый обычный целочисленный массив;
- Память — второй такой же самый простой целочисленный массив;
- Текущая ячейка команды — индекс ячейки в массиве команд;
- Текущая ячейка памяти — индекс ячейки в массиве памяти;
- Регистр — почти обычное целое число. Почему почти? Узнаем дальше!
- ???
- PROFIT
Уже в самом начале работы над задачей я точно уверен, что все данные на любом этапе работы программы будут храниться именно так. Не появится дополнительных fields или views, заказчик не подкинет парочку модификаций бизнес-логики… Мечта программиста!
Как будем сохранять иммутабельность?
На самом деле сохранять иммутабельность можно только одним способом — каждый раз, когда надо что-то изменить в состоянии нашей программы — создаём заново абсолютно новое состояние, сохраняем его а старое выкидываем на свалку под названием out of the scope. В этом нам помогут следующие волшебные фичи языка Rust:
- Трейт Copy. Если вы пришли из ООП, то структуры с определённым на них Copy трейтом как бы не reference type а value type.
Играть можно тут, но если кратко — присваивание не забирает переменную, а копирует её. - Волшебный struct update syntax. Эта штука внезапно копирует поля из старой структуры в новую.
ВАЖНО: К сожалению, оно совершенно не копирует параметры, на которых не определён трейт Copy (в нашем случае это Vec<i32>). Он их просто переносит. И это очень важно, потому что можно попасться на всякие вот такие ошибки. НО только не в нащем случае! Ведь нам плевать на старую структуру — что там из неё перенесено нам не важно — мы никогда её не будем использовать. Вот это халява!!
Модель
Модель, она же структура, будет в нашей программе одна — как раз таки виртуальная машина языка COW:
#[derive(Debug, Default, Clone)]
pub struct CowVM {
pub program: Vec<u32>,
pub memory: Vec<i32>,
pub program_position: usize,
pub memory_position: usize,
pub register: Option<i32>
}Добавим к нашей структуре немного вкусняшек — Debug, Default, Clone. Что это и зачем — можно прочитать в моей предыдущей статье.
Редьюсер
Тут в общем то тоже нету ничего сложного. Следуя семантическому дзену, определённому на этапе предварительного проектирования, клепаем на каждый опкод языка свою отдельную команду, принимающую виртуальную машину и создающую новую, уже изменённую, которую в дальнеёшем и возвращающую.
Для примера рассмотрим функию для очень важного опкода mOo — команда смещает назад на один указатель на ячейку памяти:
pub fn do_mOo(state: CowVM) ->CowVM {
CowVM{
memory_position: state.memory_position-1,
program_position: state.program_position+1,
..state
}
}Вся функция делает только две вещи — смещает указатель на ячейку памяти на 1 назад — и указатель на ячейку команд на 1 вперёд. Заметим, что не все функции смещают указатель на ячейку программ вперёд, поэтому было принято решение не выделять этот функционал в отдельную функцию. Место это занимает немного — пол строчки, и вызов функции занимал бы приблизительно такое же место, так что в общем-то всё равно…
Ну да ладно, перейдём к более интересным вещам. Помните, я говорил что регистр наш не совсем обычный? То-то и оно — лучший (и пожалуй единственный адекватный) способ хранить nullable значение в Rust — тип Option. Способ, кстати, прямиком из пекла функционального программирования. Что это такое углубляться пожалуй не будем, заметим лишь, что такой подход навязывается самим языком во-первых, а во вторых координально отличается от всех этих ваших языков, в которых есть nil, null и иже с ними. Такие языки обычно называются классическими ООП языками: Java, C#, Python, Ruby, Go… Продолжать в общем-то смысла нету. Просто привыкайте к такому положению вещей.
Вернёмся к нашим баранам. Так как регистр может быть пустой, а может быть не пустой, приходиться работать с ним как с Option. А вот и исходный код нашего редьюсера:
pub fn do_MMM(state: CowVM) -> CowVM {
match state.register {
Some(value) => {
let mut memory = state.memory;
memory[state.memory_position] = value;
CowVM{
register: None,
program_position: state.program_position+1,
memory: memory,
..state
}
},
None => {
CowVM{
register: Some(state.memory[state.memory_position]),
program_position: state.program_position+1,
..state
}
},
}
}Видите эти 4 закрывающие скобочки вконце? Выглядят страшно. Не зря всётаки многие функциональные языки не пользуются скобками. Бррр…
Заметим по дороге не очень элегантный способ поменять значение в памяти нашей виртуальной машины. Ничего лучшего не придумывается, может вы подскажете в комментариях?
Для честности отметим, что в "чисто функциональных" языках нету массивов. Там есть списки или словари. Замена элемента в списке занимает O(N), в словаре — O(logN), а тут по крайней мере O(1). И это радует. Да и память вида:
{"0": 0, "1": 4, .... "255": 0}меня пробирает до дрожи. Так что пусть будет так, как будет.
Остальные команды делаем по аналогии — можно в исходнике на них посмотреть.
Основной цикл работы программы
Тут всё просто:
- Читаем му-му-му исходник,
- Создаём новую виртуальную машину с пустой памятью и заполненным массивом команд,
- Выполняем последовательно все команды пока работа программы не закончится.
Так как у нас функциональный подход — делать всё нужно без циклов: рекурсивно. Так и поступим.
Определим основную рекурсивную функцию — execute:
fn execute(state: CowVM) -> CowVM {
new_state = match state.program[state.program_position] {
0 => commands::do_moo(state),
1 => commands::do_mOo(state),
2 => commands::do_moO(state),
3 => commands::do_mOO(state),
4 => commands::do_Moo(state),
5 => commands::do_MOo(state),
6 => commands::do_MoO(state),
7 => commands::do_MOO(state),
8 => commands::do_OOO(state),
9 => commands::do_MMM(state),
10 => commands::do_OOM(state),
11 => commands::do_oom(state),
_ => state,
}
execute(new_state);
}Логика простая — смотрим новую команду, выполняем её и повторяем сначала. И так до победного конца.
Вот и всё. Интерпретатор языка COW — готов!
Настоящий основной цикл работы программы
Вы спросите меня — "Это что, шутка такая?"
Такой же вопрос задал я сам себе, когда оказалось, что в "мультипарадигменном" (ха-ха!) языке Rust нету Tail Call Optimization. (Что это — читать здесь.)
Без этой занимательной вещицы вы очень быстро узнаете на себе, почему сайт stackoverflow назван именно так.
Что же, придётся переделывать в цикл.
Для этого выкинем рекурсию из функции execute:
fn execute(state: CowVM) -> CowVM {
match state.program[state.program_position] {
0 => commands::do_moo(state),
1 => commands::do_mOo(state),
2 => commands::do_moO(state),
3 => commands::do_mOO(state),
4 => commands::do_Moo(state),
5 => commands::do_MOo(state),
6 => commands::do_MoO(state),
7 => commands::do_MOO(state),
8 => commands::do_OOO(state),
9 => commands::do_MMM(state),
10 => commands::do_OOM(state),
11 => commands::do_oom(state),
_ => state,
}
}А цикл будем запускать прямо в функции main:
fn main() {
let mut state = init_vm();
loop {
if state.program_position == state.program.len() {
break;
}
state = execute(state);
}
}Вы чуствуете всю боль мирового функционального программирования? Мало того, что этот язык заставил нас забыть о красоте родных рекурсий, так ещё и заставил сделать мутабельную переменную!!!
А и на самом деле — к сожалению написать так не получится
fn main() {
let state = init_vm();
loop {
if state.program_position == state.program.len() {
break;
}
let state = execute(state);
}
}из-за причин, которые скрыты в сумраке… На самом деле из-за того что созданные внутри loop переменные исчезают при выходе из области видимости (на следующей строчке в этом случае).
Чтение му-му-му исходников
А вот в работе с IO в Rust нету ничего функционального. Совсем. Так что эта часть выходит за рамки этой статьи и может быть найдена в исходниках этого интерпретатора.
Вывод
По субьективным ощущениям, язык Rust успел заржаветь не состарившись. И ООП в нём какое-то не ООП, и ФП — не совсем ФП. Зато — "мультипарадигменность". Хотя, может на стыке этих парадигм получится нечто ВАУ! Остаётся на это надеятся — и писть на Rust.
Впрочем, очевидные плюсы в функциональном подходе есть. Написав целую программу удалось:
- Не вступить ни разу в коридоры ООП и не создать ни одного класса.
- Ни разу не поиметь проблем с отдалживанием, переназначением, указаним и бог ещё знает что там есть у Rust при работе с переменными. Да мы вообще не делали никаких ссылок, изменяемых переменных (ну почти), я почти забыл что такое
borrowиownership. Скажу честно, писать не думая о том, что у тебя может не скомпилироваться из-за всего этого — сущее наслаждение. - Нам удалось ещё и ни разу не вступить в lifetime параметры — вот уж действительно сумеречная сторона всего Rust. Скажу честно — меня пугают
(x: &'a mut i32)и я очень рад, что мог избежать всего этого. - Мы не реализовали ни одного трейта. Так себе достижение, но внезапно оказывается что в ФП трейты не так уж и нужны/важны.
- Все эти функции по сути своей — чистые, и их очень легко тестировать (возможно об этом будет следующая статья, хотя отличие тестирования в ООП и ФП давно известны и легко гуглятся и так).
Послесловие
Спасибо всем, кто дочитал. Приглашаю вас в комментарии к статье, там мы сможем обсудить различные парадигмы программирования в Rust. Замечания, предложения — всё туда же.
Благодарности
Огромное спасибо @minizinger за разработку особо сложных для меня (потому что самых нефункциональных) мест в программе, вдохновение и поддержку.
Автор: Дмитрий Рубинштейн
