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