Unlimited Register Machine

urm.rs

//! Unlimited Register Machine
//! https://proofwiki.org/wiki/Definition:Unlimited_Register_Machine

use std::collections::HashMap;

type Address = usize;
type State = HashMap<Address, usize>;

#[derive(Debug)]
enum Op {
    Zero(Address),
    Suc(Address),
    Transfer(Address, Address),
    Jump(Address, Address, Address),
}

#[derive(Debug)]
struct URM {
    cursor: Address,
    program: Vec<Op>,
    state: State,
}

impl URM {
    fn execute(program: Vec<Op>, state: State) -> State {
        let mut machine = URM {
            program,
            state,
            cursor: 0,
        };
        loop {
            if machine.cursor >= machine.program.len() {
                break;
            }
            match machine.program[machine.cursor] {
                Op::Zero(address) => {
                    machine.state.insert(address, 0);
                }
                Op::Suc(address) => {
                    let register_value = machine.state.entry(address).or_insert(0);
                    *register_value += 1;
                }
                Op::Transfer(from, to) => {
                    let register_value = *machine.state.entry(from).or_insert(0);
                    machine.state.insert(to, register_value);
                }
                Op::Jump(lhr, rhs, address) => {
                    let left_value = *machine.state.entry(lhr).or_insert(0);
                    let right_value = *machine.state.entry(rhs).or_insert(0);
                    if left_value == right_value {
                        machine.cursor = address;
                        continue;
                    }
                }
            }
            machine.cursor += 1;
        }
        machine.state
    }
}

fn main() {
    let state = vec![(0, 5), (1, 7)].into_iter().collect();
    let program = vec![
        Op::Jump(1, 2, 4), 
        Op::Suc(0), 
        Op::Suc(2), 
        Op::Jump(1, 1, 0),
        Op::Transfer(0, 100),
        Op::Zero(0),
        Op::Zero(1),
        Op::Zero(2),
    ];
    let final_state = URM::execute(program, state);
    println!("{:?}", final_state);
}