From acdc1705ea9821320450767b704a8ffd9fb652c9 Mon Sep 17 00:00:00 2001 From: "Sandeep.C.R" Date: Thu, 7 Sep 2023 14:20:00 +0530 Subject: [PATCH 1/3] MIR: Implement interpreter --- contrib/mir/src/ast.rs | 2 +- contrib/mir/src/interpreter.rs | 111 +++++++++++++++++++++++++++++++++ contrib/mir/src/stack.rs | 2 + 3 files changed, 114 insertions(+), 1 deletion(-) create mode 100644 contrib/mir/src/interpreter.rs diff --git a/contrib/mir/src/ast.rs b/contrib/mir/src/ast.rs index 71dee0aeb0a2..0e763ac4e608 100644 --- a/contrib/mir/src/ast.rs +++ b/contrib/mir/src/ast.rs @@ -24,7 +24,7 @@ impl Type { } } -#[derive(Debug, Eq, PartialEq)] +#[derive(Debug, Clone, Eq, PartialEq)] pub enum Value { NumberValue(i32), BooleanValue(bool), diff --git a/contrib/mir/src/interpreter.rs b/contrib/mir/src/interpreter.rs new file mode 100644 index 000000000000..e37069e48b9a --- /dev/null +++ b/contrib/mir/src/interpreter.rs @@ -0,0 +1,111 @@ +/******************************************************************************/ +/* */ +/* SPDX-License-Identifier: MIT */ +/* Copyright (c) [2023] Serokell */ +/* */ +/******************************************************************************/ + +use crate::ast::*; +use crate::stack::*; + +pub fn interpret(ast: &AST, stack: &mut IStack) { + for i in ast { + interpret_one(&i, stack); + } +} + +fn interpret_one(i: &Instruction, stack: &mut IStack) { + use Instruction::*; + use Value::*; + + match i { + Add => match stack.make_contiguous() { + [NumberValue(o1), NumberValue(o2), ..] => { + let sum = *o1 + *o2; + stack.pop_front(); + stack.pop_front(); + stack.push_front(NumberValue(sum)); + } + _ => unimplemented!(), + }, + Dip(opt_height, nested) => { + let protected_height: usize = opt_height.unwrap_or(1);; + let mut live = stack.split_off(protected_height); + interpret(nested, &mut live); + stack.append(&mut live); + } + Drop(opt_height) => { + let drop_height: usize = opt_height.unwrap_or(1); + *stack = stack.split_off(drop_height); + } + Dup(opt_height) => { + let dup_height: usize = opt_height.unwrap_or(1); + stack.push_front(stack.get(dup_height - 1).unwrap().clone()); + } + Gt => match stack.make_contiguous() { + [NumberValue(i), ..] => { + stack[0] = BooleanValue(*i > 0); + } + _ => panic!("Unexpected stack during instruction!"), + }, + If(nested_t, nested_f) => { + if let Some(BooleanValue(b)) = stack.pop_front() { + if b { + interpret(nested_t, stack); + } else { + interpret(nested_f, stack); + } + } else { + panic!("Unexpected stack during instruction!"); + } + } + Instruction::Int => match stack.make_contiguous() { + [NumberValue(_), ..] => {} + _ => { + panic!("Unexpected stack during instruction!"); + } + }, + Loop(nested) => loop { + if let Some(BooleanValue(b)) = stack.pop_front() { + if b { + interpret(nested, stack); + } else { + break; + } + } else { + panic!("Unexpected stack during instruction!"); + } + }, + Push(_, v) => { + stack.push_front(v.clone()); + } + Swap => { + stack.swap(0, 1); + } + } +} + +#[cfg(test)] +mod interpreter_tests { + use crate::interpreter::*; + use crate::parser::*; + use std::collections::VecDeque; + use Instruction::*; + use Value::*; + + #[test] + fn test_add() { + let mut stack = VecDeque::from([NumberValue(10), NumberValue(20)]); + let expected_stack = VecDeque::from([NumberValue(30)]); + interpret_one(&Add, &mut stack); + assert!(stack == expected_stack); + } + + #[test] + fn test_dip() { + let mut stack = VecDeque::from([NumberValue(10), NumberValue(5), NumberValue(20)]); + let expected_stack = VecDeque::from([NumberValue(10), NumberValue(25)]); + interpret_one(&Dip(None, parse("{ADD}").unwrap()), &mut stack); + assert!(stack == expected_stack); + } +} diff --git a/contrib/mir/src/stack.rs b/contrib/mir/src/stack.rs index ebf0e9148985..f2c905f160fb 100644 --- a/contrib/mir/src/stack.rs +++ b/contrib/mir/src/stack.rs @@ -44,3 +44,5 @@ fn ensure_ty_eq(gas: &mut Gas, ty1: &Type, ty2: &Type) -> Result<(), TcError> { Ok(()) } } + +pub type IStack = VecDeque; -- GitLab From 03d9900d86a1698113168d0481355fb14a9d24df Mon Sep 17 00:00:00 2001 From: "Sandeep.C.R" Date: Thu, 7 Sep 2023 14:20:44 +0530 Subject: [PATCH 2/3] MIR: Add tests to check for interpreter behavior --- contrib/mir/src/interpreter.rs | 112 +++++++++++++++++++++++++++++++++ contrib/mir/src/main.rs | 10 +++ 2 files changed, 122 insertions(+) diff --git a/contrib/mir/src/interpreter.rs b/contrib/mir/src/interpreter.rs index e37069e48b9a..cd57b586c237 100644 --- a/contrib/mir/src/interpreter.rs +++ b/contrib/mir/src/interpreter.rs @@ -108,4 +108,116 @@ mod interpreter_tests { interpret_one(&Dip(None, parse("{ADD}").unwrap()), &mut stack); assert!(stack == expected_stack); } + + #[test] + fn test_dip2() { + let mut stack = VecDeque::from([NumberValue(10), NumberValue(5), NumberValue(20)]); + let expected_stack = VecDeque::from([NumberValue(10), NumberValue(5)]); + interpret_one(&Dip(Some(2), parse("{DROP}").unwrap()), &mut stack); + assert!(stack == expected_stack); + } + + #[test] + fn test_drop() { + let mut stack = VecDeque::from([NumberValue(10), NumberValue(5), NumberValue(20)]); + let expected_stack = VecDeque::from([NumberValue(5), NumberValue(20)]); + interpret_one(&Drop(None), &mut stack); + assert!(stack == expected_stack); + } + + #[test] + fn test_drop2() { + let mut stack = VecDeque::from([NumberValue(10), NumberValue(5), NumberValue(20)]); + let expected_stack = VecDeque::from([NumberValue(20)]); + interpret_one(&Drop(Some(2)), &mut stack); + assert!(stack == expected_stack); + } + + #[test] + fn test_dup() { + let mut stack = VecDeque::from([NumberValue(10), NumberValue(5), NumberValue(20)]); + let expected_stack = VecDeque::from([NumberValue(10), NumberValue(10), NumberValue(5), NumberValue(20)]); + interpret_one(&Dup(None), &mut stack); + assert!(stack == expected_stack); + } + + #[test] + fn test_dup2() { + let mut stack = VecDeque::from([NumberValue(10), NumberValue(5), NumberValue(20)]); + let expected_stack = VecDeque::from([NumberValue(5), NumberValue(10), NumberValue(5), NumberValue(20)]); + interpret_one(&Dup(Some(2)), &mut stack); + assert!(stack == expected_stack); + } + + #[test] + fn test_gt() { + let mut stack = VecDeque::from([NumberValue(10), NumberValue(20)]); + let expected_stack = VecDeque::from([BooleanValue(true), NumberValue(20)]); + interpret_one(&Gt, &mut stack); + assert!(stack == expected_stack); + } + + #[test] + fn test_if_t() { + let mut stack = VecDeque::from([BooleanValue(true), NumberValue(5), NumberValue(20)]); + let expected_stack = VecDeque::from([NumberValue(20)]); + interpret_one(&If(parse("{DROP}").unwrap(), parse("{ADD}").unwrap()), &mut stack); + assert!(stack == expected_stack); + } + + #[test] + fn test_if_f() { + let mut stack = VecDeque::from([BooleanValue(false), NumberValue(5), NumberValue(20)]); + let expected_stack = VecDeque::from([NumberValue(25)]); + interpret_one(&If(parse("{DROP}").unwrap(), parse("{ADD}").unwrap()), &mut stack); + assert!(stack == expected_stack); + } + + #[test] + fn test_int() { + let mut stack = VecDeque::from([NumberValue(10), NumberValue(20)]); + let expected_stack = VecDeque::from([NumberValue(10), NumberValue(20)]); + interpret_one(&Int, &mut stack); + assert!(stack == expected_stack); + } + + #[test] + fn test_push() { + let mut stack = VecDeque::from([NumberValue(10), NumberValue(20)]); + let expected_stack = VecDeque::from([NumberValue(0), NumberValue(10), NumberValue(20)]); + interpret_one(&Push(Type::Nat, NumberValue(0)), &mut stack); + assert!(stack == expected_stack); + } + + #[test] + fn test_loop_0() { + let mut stack = VecDeque::from([BooleanValue(false), NumberValue(10), NumberValue(20)]); + let expected_stack = VecDeque::from([NumberValue(10), NumberValue(20)]); + interpret_one(&Loop(parse("{PUSH nat 1; ADD; PUSH bool False}").unwrap()), &mut stack); + assert!(stack == expected_stack); + } + + #[test] + fn test_loop_1() { + let mut stack = VecDeque::from([BooleanValue(true), NumberValue(10), NumberValue(20)]); + let expected_stack = VecDeque::from([NumberValue(11), NumberValue(20)]); + interpret_one(&Loop(parse("{PUSH nat 1; ADD; PUSH bool False}").unwrap()), &mut stack); + assert!(stack == expected_stack); + } + + #[test] + fn test_loop_many() { + let mut stack = VecDeque::from([BooleanValue(true), NumberValue(10), NumberValue(20)]); + let expected_stack = VecDeque::from([NumberValue(0), NumberValue(20)]); + interpret_one(&Loop(parse("{PUSH int -1; ADD; DUP; GT}").unwrap()), &mut stack); + assert!(stack == expected_stack); + } + + #[test] + fn test_swap() { + let mut stack = VecDeque::from([NumberValue(10), NumberValue(20)]); + let expected_stack = VecDeque::from([NumberValue(20), NumberValue(10)]); + interpret_one(&Swap, &mut stack); + assert!(stack == expected_stack); + } } diff --git a/contrib/mir/src/main.rs b/contrib/mir/src/main.rs index cd74185d034f..59f929fb7281 100644 --- a/contrib/mir/src/main.rs +++ b/contrib/mir/src/main.rs @@ -11,6 +11,7 @@ mod parser; mod stack; mod syntax; mod typechecker; +mod interpreter; fn main() {} @@ -22,6 +23,15 @@ mod tests { use crate::gas::Gas; use crate::parser; use crate::typechecker; + use crate::interpreter; + + #[test] + fn interpret_test_expect_success() { + let ast = parser::parse(&FIBONACCI_SRC).unwrap(); + let mut istack = VecDeque::from([Value::NumberValue(10)]); + interpreter::interpret(&ast, &mut istack); + assert!(istack.len() == 1 && istack[0] == Value::NumberValue(55)); + } #[test] fn typecheck_test_expect_success() { -- GitLab From ded9b32f8c05cd7b165bd274c2788d5f171df234 Mon Sep 17 00:00:00 2001 From: "Sandeep.C.R" Date: Wed, 13 Sep 2023 21:25:55 +0530 Subject: [PATCH 3/3] MIR: Extract function to throw unexpected state error --- contrib/mir/src/interpreter.rs | 16 +++++++++++----- 1 file changed, 11 insertions(+), 5 deletions(-) diff --git a/contrib/mir/src/interpreter.rs b/contrib/mir/src/interpreter.rs index cd57b586c237..3d1f206966f3 100644 --- a/contrib/mir/src/interpreter.rs +++ b/contrib/mir/src/interpreter.rs @@ -14,6 +14,12 @@ pub fn interpret(ast: &AST, stack: &mut IStack) { } } +fn unreachable_state() -> ! { + // If the typechecking of the program being interpreted was successful and if this is reached + // during interpreting, then the typechecking should be broken, and needs to be fixed. + panic!("Unreachable state reached during interpreting, possibly broken typechecking!") +} + fn interpret_one(i: &Instruction, stack: &mut IStack) { use Instruction::*; use Value::*; @@ -29,7 +35,7 @@ fn interpret_one(i: &Instruction, stack: &mut IStack) { _ => unimplemented!(), }, Dip(opt_height, nested) => { - let protected_height: usize = opt_height.unwrap_or(1);; + let protected_height: usize = opt_height.unwrap_or(1); let mut live = stack.split_off(protected_height); interpret(nested, &mut live); stack.append(&mut live); @@ -46,7 +52,7 @@ fn interpret_one(i: &Instruction, stack: &mut IStack) { [NumberValue(i), ..] => { stack[0] = BooleanValue(*i > 0); } - _ => panic!("Unexpected stack during instruction!"), + _ => unreachable_state(), }, If(nested_t, nested_f) => { if let Some(BooleanValue(b)) = stack.pop_front() { @@ -56,13 +62,13 @@ fn interpret_one(i: &Instruction, stack: &mut IStack) { interpret(nested_f, stack); } } else { - panic!("Unexpected stack during instruction!"); + unreachable_state(); } } Instruction::Int => match stack.make_contiguous() { [NumberValue(_), ..] => {} _ => { - panic!("Unexpected stack during instruction!"); + unreachable_state(); } }, Loop(nested) => loop { @@ -73,7 +79,7 @@ fn interpret_one(i: &Instruction, stack: &mut IStack) { break; } } else { - panic!("Unexpected stack during instruction!"); + unreachable_state(); } }, Push(_, v) => { -- GitLab