watchmaker_vm

一个用于遗传算法的虚拟机。

该虚拟机的指令集比现实世界处理器简单得多。没有寄存器，所有操作数都是内存位置。这有助于简化指令的解释，减少围绕寄存器使用的不必要复杂性。

特性

• 适合遗传算法。任何随机的字节序列都是有效的程序。
• 简单的指令格式。每个指令都是一个64位值，包括操作数。
• 相当高效，每条指令的分支因子低于包含寄存器或需要处理表达式树的架构。
• 用于转储指令的实用工具。
• 灵活的内存映射I/O。

使用方法

• 使用rustup安装Rust https://rustup.rs/
• 克隆仓库（见下文）
• 运行 cargo test 或 cargo build

示例

以下创建了一个执行阶乘函数的示例。

    let vm = VirtualMachine::new(
        &ArchitectureBuilder::default()
            .iinput(1)
            .istate(2)
            .ioutput(1)
            .dinput(1)
            .dstate(1)
            .doutput(1)
            .build()
            .unwrap(),
        vec![
            Instruction::IIMOV(
                LeftInteger::Input(0, Mode::Direct),
                RightInteger::State(0, Mode::Direct),
            ),
            Instruction::IIMOV(
                LeftInteger::Input(0, Mode::Direct),
                RightInteger::State(1, Mode::Direct),
            ),
            Instruction::IJLT(
                LeftInteger::State(0, Mode::Direct),
                LeftInteger::Constant(2),
                CodeOffset { offset: 4 },
            ),
            Instruction::ISUB(
                LeftInteger::State(0, Mode::Direct),
                LeftInteger::Constant(1),
                RightInteger::State(0, Mode::Direct),
            ),
            Instruction::IMUL(
                LeftInteger::State(0, Mode::Direct),
                LeftInteger::State(1, Mode::Direct),
                RightInteger::State(1, Mode::Direct),
            ),
            Instruction::IJEQ(
                LeftInteger::Constant(0),
                LeftInteger::Constant(0),
                CodeOffset { offset: -3 },
            ),
            Instruction::IIMOV(
                LeftInteger::State(1, Mode::Direct),
                RightInteger::Output(0, Mode::Direct),
            ),
            Instruction::HLT(),
        ],
    );
    // Write the input to the first location in the integer typed input memory bank.
    vm.iinput()[0] = n as i64;
    
    // Execute the VM until the halt instruction is reached.
    while vm.next_instruction() != &Instruction::HLT() {
        vm.run(1);
    }
    
    // Read the result from the first location of the integer typed output memory bank.
    let result = vm.ioutput()[0];
    println!("factorial of {:?} is {:?}", vm.iinput()[0], result);

以下展示了如何创建可以提供给虚拟机实例的随机指令列表。

        let raw: Vec<u64> = (0..GENOME_SIZE)
            .into_iter()
            .map(|_| rand::thread_rng().next_u64())
            .collect();
        let instructions: Vec<Instruction> = raw.into_iter()
            .map(watchmaker_vm::deserialize)
            .collect();

替代方案

遗传算法是一个非常著名的技巧，因此有很多人可以表示和执行进化的程序。

一些候选方案

• 遗传编程 非常知名且研究广泛。将代码表示为操作数和操作符的树。处理更复杂。可能会引入子树偏差。通常不支持内存映射I/O。 https://en.wikipedia.org/wiki/Genetic_programming#Program_representation
• MLeM 一个Rust crate，专门为遗传算法实现VM。支持内存映射I/O。与这个crate类似，但使用寄存器并支持使用堆栈。看起来每条指令会有更多的分支。 https://crates.io/crates/mlem
• Slash/A "用于（定量）线性遗传编程的编程语言和C++库。" 极简且值得一观。内存架构受限，但可以扩展。不支持内存映射I/O。每条指令执行很少，因此容易受到无谓的复杂性（“图灵陷阱”）的影响。 https://github.com/arturadib/slash-a
• 图灵机 原始的虚拟机。非常知名且研究广泛。每条指令执行很少，因此容易受到无谓的复杂性（“图灵陷阱”）的影响。可能难以解释（参见“Brainfuck” https://en.wikipedia.org/wiki/Brainfuck) https://en.wikipedia.org/wiki/Turing_machine

许可证

MIT授权许可。有关完整许可证详情，请参阅LICENSE。

源代码仓库

https://github.com/thomasbratt/watchmaker_vm