08.07.2018 11:09
aprokurov 21 5000 Источник

Здравствуй, Хабр! Уже несколько недель я занят разработкой своего языка программирования на Rust. Мне бы хотелось расказать о том с чем может столкнуться новичок в этом деле и о чем ему следует знать.


Краткая предистория


Все началось с форка ein, форкнул я его дабы изучить как строятся языки программирования. Так-как ein интерпретируется от и до, то его скорость исполнения оказалась не самой высокой и после того как я начал хоть что то понимать я решил начать писать свой интерпретатор который в конце концов тоже забросил.


Но отчаиваться еще рано! Я прочел пару статей о VM и о том какие они бывают и решил написать простую стековую VM.


Что за "стековая виртуальная машина" и как она работает?


На хабре есть отедльная статья про это, но что бы не гонять по ссылкам изложу вкратце смысл этой вещицы.


Стековая VM выполняет все операции над данными, которые хранятся в виде стека, каждая операция извлекает нужное количество ей данных для операции и после выполнения ее может "отправить" в стек новое число.


Начинаем


Для начала необходимо создать новый проект с помощью cargo:


cargo new habr_vm

Сперва нам необходимо создать несколько базовых операций для нашей VM:


enum Opcode {
      Push(i32),
      Add,
      AddAssign(i32),
      Sub,
      SubAssign(i32),
}

Это наши базовые операции, команда Push будет добавлять в стек новое число, Add и Sub будут брать из стека два числа и выполнять с ними действия(сложение и вычитание соответственно), думаю о AddAssign и SubAssign объяснять не надо.


Cледующая задача это создать саму виртуальную машину, для этого мы создадим не сложную структуру:


struct Vm {
    pub stack: Vec<i32>,
}

И имплементируем ее:


impl Vm {
    //Упрощаем себе жизнь тем что сокращаем писанину
    pub fn pop(&mut self) -> i32 {
        self.stack.pop().unwrap()
    }
    //Здесь будет происходить все самое интересное
    pub fn run(&mut self,program: Vec<Opcode>) {
        for opcode in program { //Проверяем каждую команду в нашей программе
            match opcode {
                Opcode::Push(n) => {
                    //Просто добавляем число в наш стек
                    self.stack.push(n);
                }
                Opcode::Add => {
                    // Берем два числа из стека и складываем их, добавляем в стек уже новое число
                    let value = self.pop() + self.pop();
                    self.stack.push(value);
                }
                Opcode::Sub => {
                   // Тут то же самое что и с складыванием только наоборот 
                    let value = self.pop() - self.pop();
                    self.stack.push(value);
                }
                // Думаю следующие две операции объяснять не нужно
                Opcode::AddAssign(n) => {
                    let mut value = self.pop();
                    value += n;
                    self.stack.push(value);
                }
                Opcode::SubAssign(n) => {
                    let mut value = self.pop();
                    value -= n;
                    self.stack.push(value);
                }
            }
        }
    }
}

Мы иплементировали нашу структуру, что дальше? Дальше надо создать нашу "программу".


Вот как это должно выглядеть:


let program = vec![
     Opcode::Push(2),//Добавляем 2 в наш стек
     Opcode::Push(4),// Добавляем 4 в наш стек
     Opcode::Sub,// Вычитаем 4 - 2
];

Все просто, не так ли? Раз так, то давайте уже запустим нашу программу!


let mut vm = Vm {stack: Vec::new()};
vm.run(program);

// Выводим все числа из стека, на данный момент это будет просто 2 
for i in vm.stack() {
     println!("{}", i);
}
// Вывод
2

Очень просто как по мне, таким образом вы можете добавить еще достаточно опкодов для нужной вам операции.


Заключение


Думаю что я вполне понятно объяснил как это все написать на расте и как это работает.


Хочется добавить что вы с легкостью сможете написать свой ЯП благодаря подобному VM, вам по сути остается написать только парсер, лексер и "компилятор", а если вам охото посмотреть на уже готовый проект то можете пройти по данной ссылке.


Весь код из статьи доступен в данном репозитории


Удачи Хабр!

Комментарии (21)


  1. VolCh
    08.07.2018 15:06
    #18859597
    +1

    Напомнило молодость, МК-61 и FORT :)


  1. I_AM_FAKE
    08.07.2018 15:15
    #18859623
    +1

                    Opcode::SubAssign(n) => {
                    let mut value = self.pop();
                    value += n;
                    self.stack.push(value);
                }


    У тебя тут баг


    1. alexxisr
      08.07.2018 15:31
      #18859649
      -1

      можно подробнее?
      для меня, как для человека ни разу не писавшего на расте, всё выглядит логично.


      1. I_AM_FAKE
        08.07.2018 15:35
        #18859653
        +1

        там у автора копипаст и value += n; повторяется в AddAssign и в SubAssign.


        1. alexxisr
          08.07.2018 15:36
          #18859657
          -1

          ну может так и задумывалось — автор же так и не рассказал, что должны делать эти операции )


        1. aprokurov Автор
          08.07.2018 15:56
          #18859679
          +1

          Спасибо за поправку, уже исправил


  1. EvilMan
    08.07.2018 16:07
    #18859693

    Что будет, если в стеке не окажется нужного количества значений?


    1. aprokurov Автор
      08.07.2018 16:27
      #18859729

      Если кратко, то паника из-за того что в стеке не будет чисел, но если ловить ошибки благодаря Result этого можно избежать


  1. burdakovd
    08.07.2018 16:25
    #18859721
    +1

    > let value = self.pop() — self.pop();

    А в Rust так можно? Если мне не изменяет память, в C++ порядок вычисления аргументов был неопределён, так что результат мог оказаться с противоположным знаком.


    1. newpavlov
      09.07.2018 04:19
      #18860571
      +1

      В Расте порядок строго определён, т.к. нужен для borrow checker'а. Правило: слева-направо и изнутри-наружу, т.е. вот эта строчка a.quuz(a.foo(a.bar(), a.baz()), a.quux()) будет выполняться в следующем порядке: a.bar(), a.baz(), a.foo(), a.quux(), a.quuz().


  1. Arris
    08.07.2018 16:26
    #18859725

    Как насчет примера реализации цикла? К примеру, для вычисления факториала или чисел фибоначчи?


    1. aprokurov Автор
      08.07.2018 16:31
      #18859741

      С тем набором опкодов что есть в данной виртальной машине не выйдет, но здесь есть пример в самом низу README и можете после того как программа выполнится посмотреть файл opcode.txt, все опкоды записаны туда


  1. Gorushan
    08.07.2018 20:14
    #18860055
    -2

    Олег, если нужна скорость, почему Rust, а не Си?


    1. red75prim
      08.07.2018 20:55
      #18860127
      +5

      Скорость у программ на Rust и C с одинаковыми алгоритмами примерно одинаковая. Почему Rust? Удобная система сборки, алгебраические типы, дженерики, встроенный статический анализатор (borrow checker), модули и прочее.


  1. WinLin2
    08.07.2018 21:14
    #18860151
    -1

    ча и ща пишем через а.


  1. Lure_of_Chaos
    08.07.2018 23:03
    #18860349
    +1

    Я бы порекомендовал реализовать примитивные базовые (не пересекающиеся между собой) операции, необходимые для написания любого интерпретатора (ну хотя бы тот же брейнфак). Так, операции AddAssign и SubAssign являются лишними, но не хватает операции Assign.

    Далее, как уже было замечено, сильно не хватает операций ветвления (условия, переходы), чтобы можно было написать нелинейный код. Конечно, для этого потребуется понятие адресации (абсолютной и\или относительной, возможно, меток) — интересно, какой подход выбрали (бы) Вы.

    И последнее: всё описанное с легкостью реализуется на любом ЯП, не только Rust, но и C\C++, Java\C#, Python\Ruby etc.


  1. Lure_of_Chaos
    08.07.2018 23:15
    #18860363
    +1

    И еще, по поводу интерпретаторов: виртуальная машина — только первый шаг, потребуется также реализовать парсер+лексер для выбранной грамматики — что по себе очень серьезная задача, особенно если писать самостоятельно (и чем дальше от семантики ассемблера, тем сложнее).
    Поэтому зачастую проще взять существующую ВМ, сторонний парсер+интерпретатор, и только написать для этого парсера понятную ему грамматику.

    Либо (если похожий язык есть, но нужно его расширить\изменить) — можно написать транспилер в целевой язык и положиться на свойства платформы этого языка. Этот способ привлекателен тем, что сам транспилер не обязан быть быстрым, многие конструкции просто перенести 1:1, и реализовать его можно хоть на любимых регулярках.
    Для языка Си как основы вообще может оказаться достаточным применение макросов и его препроцессора


    1. aprokurov Автор
      09.07.2018 09:50
      #18860887

      Ну в конце статьи есть ссылка на ЯП Neo который я пытаюсь доделать до вменяемого состояния, там так же используется стековая Vm


  1. mexus
    09.07.2018 09:49
    #18860879
    +1

    Решил в рамках разминки слегка добавить коду из статьи идиоматичности, и в итоге так увлёкся, что аж жалко стало выбрасывать. Поэтому предлагаю вашему вниманию несколько альтернативную имплементацию ровно той же машины, что описал автор:
    https://gist.github.com/mexus/0dbdf5af2367719c00bb70c5288d9cc9


    P.S.
    Дабы запихнуть всё в один файл нагородил mod'ов, в реальной жизни всё их содержимое конечно ушло бы в отдельные файлы.


  1. WinLin2
    09.07.2018 13:19
    #18861719

    «ча и ща пишем через а.»

    Можно просто так минусовать и ничего за это не будет?
    Спрашиваю для самообразования.


    1. playermet
      10.07.2018 19:55
      #18867723

      Минусуют, потому что подобные сообщения нужно отправлять автору статьи в личку. Это объяснение есть наверное на каждой третьей статье на хабре под таким же комментарием, но их все ровно пишут и пишут, годами. Пора за них бан вводить.