Програмиране с Rust

Курс във Факултета по Математика и Информатика към СУ

Reversible Interpreter

Предадени решения

Краен срок:
20.01.2021 17:00
Точки:
15

Срокът за предаване на решения е отминал

use solution::*;
#[test]
fn test_push() {
let mut interpreter = Interpreter::new();
interpreter.add_instructions(&[
"PUSH 1",
"PUSH -25",
"PUSH 13",
]);
interpreter.forward().unwrap();
interpreter.forward().unwrap();
assert_eq!(interpreter.stack, &[1, -25]);
interpreter.back().unwrap();
assert_eq!(interpreter.stack, &[1]);
interpreter.run().unwrap();
assert_eq!(interpreter.stack, &[1, -25, 13]);
}
#[test]
fn test_pop() {
let mut interpreter = Interpreter::new();
interpreter.add_instructions(&[
"PUSH 1",
"POP",
"PUSH 13",
"POP",
]);
interpreter.forward().unwrap();
assert_eq!(interpreter.stack.len(), 1);
interpreter.forward().unwrap();
assert_eq!(interpreter.stack.len(), 0);
interpreter.run().unwrap();
assert_eq!(interpreter.stack.len(), 0);
}
#[test]
fn test_arithmetic_basic() {
let mut interpreter = Interpreter::new();
// 2 + 1 = 3
interpreter.add_instructions(&[
"PUSH 1",
"PUSH 2",
"ADD",
]);
interpreter.run().unwrap();
assert_eq!(interpreter.stack.last().unwrap(), &3);
// 3 * 3 = 9
interpreter.add_instructions(&[
"PUSH 3",
"MUL",
]);
interpreter.run().unwrap();
assert_eq!(interpreter.stack.last().unwrap(), &9);
// 4 - 9 = -5
interpreter.add_instructions(&[
"PUSH 4",
"SUB",
]);
interpreter.run().unwrap();
assert_eq!(interpreter.stack.last().unwrap(), &-5);
// 5 / -5 = -1
interpreter.add_instructions(&[
"PUSH 5",
"DIV",
]);
interpreter.run().unwrap();
assert_eq!(interpreter.stack.last().unwrap(), &-1);
}
#[test]
fn test_arithmetic_back() {
let mut interpreter = Interpreter::new();
interpreter.add_instructions(&[
"PUSH 1",
"PUSH 2",
"ADD",
"PUSH 3",
"MUL",
"PUSH 4",
"SUB",
"PUSH 5",
"DIV",
]);
interpreter.run().unwrap();
// Before 5 / -5 = -1
interpreter.back().unwrap();
assert_eq!(interpreter.stack, &[-5, 5]);
// Before 4 - 9 = -5
interpreter.back().unwrap();
interpreter.back().unwrap();
assert_eq!(interpreter.stack, &[9, 4]);
// Before 3 * 3 = 9
interpreter.back().unwrap();
interpreter.back().unwrap();
assert_eq!(interpreter.stack, &[3, 3]);
// Before 2 + 1 = 3
interpreter.back().unwrap();
interpreter.back().unwrap();
assert_eq!(interpreter.stack, &[1, 2]);
}
#[test]
fn test_div_1() {
let mut interpreter = Interpreter::new();
interpreter.add_instructions(&[
"PUSH 7",
"PUSH 14",
"DIV",
]);
// 14 / 7 = 2
interpreter.run().unwrap();
assert_eq!(interpreter.stack, &[2]);
interpreter.back().unwrap();
assert_eq!(interpreter.stack, &[7, 14]);
}
#[test]
fn test_div_2() {
let mut interpreter = Interpreter::new();
interpreter.add_instructions(&[
"PUSH 5",
"PUSH 7",
"DIV",
]);
// 7 / 5 = 1
interpreter.run().unwrap();
assert_eq!(interpreter.stack, &[1]);
interpreter.back().unwrap();
assert_eq!(interpreter.stack, &[5, 7]);
}
#[test]
fn test_errors_1() {
let mut interpreter = Interpreter::new();
interpreter.add_instructions(&["POP"]);
assert_eq!(interpreter.forward(), Err(RuntimeError::StackUnderflow));
let mut interpreter = Interpreter::new();
interpreter.add_instructions(&["PUSH 1"]);
interpreter.forward().unwrap();
assert_eq!(interpreter.forward(), Err(RuntimeError::NoInstructions));
interpreter.back().unwrap();
assert_eq!(interpreter.back(), Err(RuntimeError::NoInstructions));
}
#[test]
fn test_errors_2() {
let mut interpreter = Interpreter::new();
interpreter.add_instructions(&[
"PUSH 0",
"PUSH 7",
"DIV",
]);
interpreter.forward().unwrap();
interpreter.forward().unwrap();
assert_eq!(interpreter.forward(), Err(RuntimeError::DivideByZero));
}
#[test]
fn test_restoring_instructions() {
let mut interpreter = Interpreter::new();
interpreter.add_instructions(&[
"PUSH 1",
"PUSH 2",
"ADD",
]);
interpreter.forward().unwrap();
interpreter.forward().unwrap();
assert_eq!(interpreter.instructions, &["ADD"]);
interpreter.back().unwrap();
assert_eq!(interpreter.instructions, &["PUSH 2", "ADD"]);
}
#[test]
fn test_instructions_after_error() {
let mut interpreter = Interpreter::new();
interpreter.add_instructions(&[
"PUSH 0",
"PUSH 2",
"DIV",
"PUSH 3",
]);
interpreter.forward().unwrap();
interpreter.forward().unwrap();
assert_eq!(interpreter.forward(), Err(RuntimeError::DivideByZero));
assert_eq!(interpreter.instructions, &["DIV", "PUSH 3"]);
interpreter.back().unwrap();
interpreter.back().unwrap();
assert_eq!(interpreter.instructions, &["PUSH 0", "PUSH 2", "DIV", "PUSH 3"]);
*interpreter.current_instruction().unwrap() = String::from("PUSH 1");
interpreter.run().unwrap();
}
#[test]
fn test_arg_number() {
let invalid_instructions = [
"ADD 1 2",
"ADD 42",
"SUB -1",
"DIV 1 3 5",
"MUL 12",
"POP 1",
"PUSH",
"PUSH 1 2",
];
for instruction in &invalid_instructions {
let mut interpreter = Interpreter::new();
interpreter.add_instructions(&[instruction]);
assert_eq! {
interpreter.forward(),
Err(RuntimeError::InvalidCommand),
"Should have been invalid: {}", instruction
};
}
}
#[test]
fn test_invalid_args() {
let invalid_instructions = [
"POSH",
"PULL",
"VID",
"ADDIFY",
"DIVISIVIDE",
"UNPOP 12",
];
for instruction in &invalid_instructions {
let mut interpreter = Interpreter::new();
interpreter.add_instructions(&[instruction]);
assert_eq! {
interpreter.forward(),
Err(RuntimeError::InvalidCommand),
"Should have been invalid: {}", instruction
};
}
}

Ще напишем интерпретатор за стеков език, който може да оценява програмата си ред по ред, но и да възстановява старото състояние като форма на "undo".

Първо, какво значи "стеков език"? Интерпретатора ще си съдържа стек от стойности и ще има инструкции, които слагат стойности на стека и инструкции, които вземат стойностите и ги трансформират. Примерна програма:

PUSH 1
PUSH 2
ADD

След първата инструкция, на върха на стека ще има стойност 1, след това 2. Инструкцията ADD взема последните две стойности от стека и ги събира и слага резултата на стека. Така че след изпълнението на тази програма, на стека ще има само една стойност -- 3.

Инструкции

Първо, когато казваме "добавя на върха на стека", имаме предвид метода .push на Vec. Това ще добави стойността на края на вектора, което е по-ефективна операция от това да добавяме в началото. Същото се отнася за махане на елементи "от върха на стека" -- махаме последния с .pop.

Всички стойности са от тип i32, така че може да са положителни или отрицателни. За аритметиката, не се притеснявайте за overflows -- ще тестваме с достатъчно малки числа, за да не се получават проблеми при събиране или умножение.

Ще тестваме командите само с големи букви, но се чувствайте свободни да имплементирате поддръжка за PUSH, Push, push -- но не е задължително (просто няма да е особено трудно).

  • PUSH: Приема точно 1 аргумент, разделен с един интервал (или поне ще тестваме само с един интервал, но може просто да ползвате .split_whitespace()). Добавя стойността на върха на стека.
  • POP: Приема точно 0 аргументи, иначе RuntimeError::InvalidCommand. Премахва стойността на върха на стека.
  • ADD: Взема върха на стека, после новия връх, събира двете стойности и слага новата стойност на върха. Приема точно 0 аргументи.
  • MUL: Същото, само че с умножение. Приема точно 0 аргументи.
  • SUB: Взема върха на стека X, взема новия връх Y, смята X - Y, слага резултата на върха на стека. Приема точно 0 аргументи.
  • DIV: Същото, само че с деление. Ако Y е 0, връщаме RuntimeError::DivideByZero. Приема точно 0 аргументи.

Ако някоя от командите, които вадят нещо от стека се извикат на празен стек, очакваме грешка RuntimeError::StackUnderflow. Примерно PUSH 1 последвано от ADD връща stack underflow -- има само една стойност за събиране.

При различен брой аргументи от описания (примерно ADD 1, PUSH 1 2, PUSH), командата е невалидна с RuntimeError::InvalidCommand. При аргумент, който не е валидно i32 число, пак връщаме RuntimeError::InvalidCommand.

При каквато и да е друга инструкция, очакваме RuntimeError::InvalidCommand.

Базови структури

Както винаги при нещо такова, трябва ни общ тип за грешки:

#[derive(Clone, Debug, PartialEq, Eq)]
pub enum RuntimeError {
    DivideByZero,
    StackUnderflow,
    InvalidCommand,
    NoInstructions,
}

Някои от тези грешки са описани по-горе при операциите. Грешката RuntimeError::NoInstructions се връща, когато се опитваме да "движим" интерпретатора напред или назад, но няма инструкции за движене. Това е един вид сигнал за "край" на интерпретацията. Детайли по-долу.

use std::collections::VecDeque;

#[derive(Debug, Default)]
pub struct Interpreter {
    pub instructions: VecDeque<String>,
    pub stack: Vec<i32>,
    // + още полета за поддръжка на .back() метода
}

Инструкциите се пазят във VecDeque, понеже искаме ефективно да можем да добавяме още инструкции в края им, но също така да махаме инструкции от началото на списъка, докато ги обработваме. Също така за разнообразие, че стига толкоз Vec.

impl Interpreter {
    /// Конструира нов интерпретатор с празен стек и никакви инструкции.
    pub fn new() -> Self {
        todo!()
    }

    /// Добавя инструкции от дадения списък към края на `instructions`. Примерно:
    ///
    /// interpreter.add_instructions(&[
    ///     "PUSH 1",
    ///     "PUSH 2",
    ///     "ADD",
    /// ]);
    ///
    /// Инструкциите не се интерпретират, само се записват.
    ///
    pub fn add_instructions(&mut self, instructions: &[&str]) {
        todo!()
    }

    /// Връща mutable reference към инструкцията, която ще се изпълни при
    /// следващия `.forward()` -- първата в списъка/дека.
    ///
    pub fn current_instruction(&mut self) -> Option<&mut String> {
        todo!()
    }

    /// Интерпретира първата инструкция в `self.instructions` по правилата описани по-горе. Записва
    /// някаква информация за да може успешно да се изпълни `.back()` в по-нататъшен момент.
    ///
    /// Ако няма инструкции, връща `RuntimeError::NoInstructions`. Другите грешки идват от
    /// обясненията по-горе.
    ///
    pub fn forward(&mut self) -> Result<(), RuntimeError> {
        todo!()
    }

    /// Вика `.forward()` докато не свършат инструкциите (може и да се имплементира по други
    /// начини, разбира се) или има грешка.
    ///
    pub fn run(&mut self) -> Result<(), RuntimeError> {
        loop {
            match self.forward() {
                Err(RuntimeError::NoInstructions) => return Ok(()),
                Err(e) => return Err(e),
                _ => (),
            }
        }
    }

    /// "Обръща" последно-изпълнената инструкция с `.forward()`. Това може да се изпълнява отново и
    /// отново за всяка инструкция, изпълнена с `.forward()` -- тоест, не пазим само последната
    /// инструкция, а списък/стек от всичките досега.
    ///
    /// Ако няма инструкция за връщане, очакваме `RuntimeError::NoInstructions`.
    ///
    pub fn back(&mut self) -> Result<(), RuntimeError> {
        todo!()
    }
}

За пример как бихме могли да използваме .back():

let mut interpreter = Interpreter::new();
interpreter.add_instructions(&[
    "PUSH 0",
    "PUSH 42",
    "DIV",
]);

interpreter.forward().unwrap(); // PUSH 0
interpreter.forward().unwrap(); // PUSH 42

// Дотук добре:
println!("Instructions: {:?}\nStack: {:?}", interpreter.instructions, interpreter.stack);
// Instructions: ["DIV"]
// Stack: [0, 42]

println!("{:?}", interpreter.forward());
// => Err(DivideByZero)... Опа, объркахме първата команда, дай назад

interpreter.back().unwrap();
interpreter.back().unwrap();
interpreter.current_instruction().map(|i| *i = String::from("PUSH 2"));

interpreter.run().unwrap();
println!("Instructions: {:?}\nStack: {:?}", interpreter.instructions, interpreter.stack);
// Instructions: []
// Stack: [21]

Забележете, че при грешка в изпълнението на .forward(), не премахваме инструкцията от списъка -- интерпретатора ни гърми на DIV, но това значи, че DIV продължава да бъде "текущата" инструкция, и не се добавя в историята за обръщане. Само успешни инструкции се обръщат с .back().

Няма да тестваме с някакви по-специални неща откъм парсене -- "аргументите" може да приемете че са разделени с точно 1 интервал и че няма интервали преди или след инструкцията. Нищо не ви пречи да ударите един trim все пак и да разбивате компонентите със .split_whitespace(). Парсенето не е предвидено да бъде твърде важно за това домашно.

Как да имплементирате историята?

Ваш избор. Този път няма да ви даваме детайлни помощни средства. Има много начини да го постигнете, изберете си как и го направете. Можете да запазите "обръщаща" поредица от низови команди, примерно PUSH 1 се обръща от POP. Може да запазите вектор от атомарни команди, примерно vec![Op::Push(1), Op::Pop], може да си направите енум с всички възможни обръщаеми команди, и състоянието нужно да ги обърнете.

Не забравяйте, че имате да възстановите две неща при обръщане -- низовете в .instructions и състоянието на .stack и тестовете ще проверяват и двете. Полетата instructions и stack са публични и ще ги достъпваме директно в нашите тестове, така че внимавайте да не им промените типовете.

Базов тест: 04/test_basic.rs

Задължително прочетете (или си припомнете): Указания за предаване на домашни