- PVSM.RU - https://www.pvsm.ru -
Попался мне на глаза Brainfuck-оподобный язык Cow [1]. И решил я написать для него интерпретатор на новомодном Rust [2]. А так как Rust — мультипарадигменный язык, то стиль написания программы будет функциональный. Чтобы узнать что получилось — прошу под кат.
Повествование постараюсь вести в виде туториала, вопросы в комментариях, ценные замечания о недостаточной функциональности — туда же: будем исправлять! А пока что поехали.
Состояние виртуальной коровы машины будем хранить в неизменяемой переменной state
. Все изменения будут производится с помощью функций, имеющих такую семантику:
fn change(previousState: CowVM) -> CowVM // newState
Похоже на Elm, Redux, может ещё на что-то, чего я и сам не знаю. Не правда ли?
На самом деле, именно то, что с самого начала очень хорошо видно, как хранить данные, делает эту задачу пригодной для функционального подхода.
Действительно, что такое виртуальная машина Cow?
Уже в самом начале работы над задачей я точно уверен, что все данные на любом этапе работы программы будут храниться именно так. Не появится дополнительных fields или views, заказчик не подкинет парочку модификаций бизнес-логики… Мечта программиста!
На самом деле сохранять иммутабельность можно только одним способом — каждый раз, когда надо что-то изменить в состоянии нашей программы — создаём заново абсолютно новое состояние, сохраняем его а старое выкидываем на свалку под названием out of the scope. В этом нам помогут следующие волшебные фичи языка Rust:
Модель, она же структура, будет в нашей программе одна — как раз таки виртуальная машина языка 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. Что это и зачем — можно прочитать в моей предыдущей статье [6].
Тут в общем то тоже нету ничего сложного. Следуя семантическому дзену, определённому на этапе предварительного проектирования, клепаем на каждый опкод языка свою отдельную команду, принимающую виртуальную машину и создающую новую, уже изменённую, которую в дальнеёшем и возвращающую.
Для примера рассмотрим функию для очень важного опкода 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 [7]. Способ, кстати, прямиком из пекла функционального программирования. Что это такое углубляться пожалуй не будем [8], заметим лишь, что такой подход навязывается самим языком во-первых, а во вторых координально отличается от всех этих ваших языков, в которых есть 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. (Что это — читать здесь [9].)
Без этой занимательной вещицы вы очень быстро узнаете на себе, почему сайт stackoverflow назван именно так [10].
Что же, придётся переделывать в цикл.
Для этого выкинем рекурсию из функции 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.
Впрочем, очевидные плюсы в функциональном подходе есть. Написав целую программу удалось:
borrow
и ownership
. Скажу честно, писать не думая о том, что у тебя может не скомпилироваться из-за всего этого — сущее наслаждение.(x: &'a mut i32)
и я очень рад, что мог избежать всего этого.Спасибо всем, кто дочитал. Приглашаю вас в комментарии к статье, там мы сможем обсудить различные парадигмы программирования в Rust. Замечания, предложения — всё туда же.
Ссылка на исходник. [11]
Огромное спасибо @minizinger [12] за разработку особо сложных для меня (потому что самых нефункциональных) мест в программе, вдохновение и поддержку.
Автор: Дмитрий Рубинштейн
Источник [13]
Сайт-источник PVSM.RU: https://www.pvsm.ru
Путь до страницы источника: https://www.pvsm.ru/oop/255828
Ссылки в тексте:
[1] Cow: https://ru.wikipedia.org/wiki/Brainfuck#.D0.AF.D0.B7.D1.8B.D0.BA.D0.B8_.D0.BD.D0.B0_.D0.BE.D1.81.D0.BD.D0.BE.D0.B2.D0.B5_Brainfuck
[2] Rust: https://www.rust-lang.org/
[3] тут: https://is.gd/kCDewy
[4] struct update syntax: https://doc.rust-lang.org/book/structs.html#update-syntax
[5] вот такие: https://is.gd/2ghhxP
[6] моей предыдущей статье: https://habrahabr.ru/post/277461/
[7] Option: https://doc.rust-lang.org/std/option/
[8] углубляться пожалуй не будем: https://en.wikipedia.org/wiki/Option_type
[9] здесь: http://stackoverflow.com/questions/310974/what-is-tail-call-optimization
[10] назван именно так: https://is.gd/Tg5bid
[11] Ссылка на исходник.: https://github.com/Virviil/cow.rs
[12] @minizinger: https://github.com/minizinger
[13] Источник: https://habrahabr.ru/post/283450/?utm_source=habrahabr&utm_medium=rss&utm_campaign=best
Нажмите здесь для печати.