Pull to refresh

Функциональный Rust: Готовим говядину

Reading time 6 min
Views 9.2K

image


Попался мне на глаза 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 за разработку особо сложных для меня (потому что самых нефункциональных) мест в программе, вдохновение и поддержку.

Tags:
Hubs:
+20
Comments 30
Comments Comments 30

Articles