如何优化 brainf*ck 指令

Question

我正在尝试为我的 brainf*ck 解释器编写优化功能。它基本上将相同的指令合并为 1 条指令。

我写了这个函数，但它不能正常工作：


pub fn optimize_multiple(instructions: &Vec<Instruction>) -> Vec<OptimizedInstruction> {

    let mut opt: Vec<OptimizedInstruction> = Vec::new();

    let mut last_instruction = instructions.get(0).unwrap();
    let mut last_count = 0;

    for instruction in instructions.iter() {

        if instruction == last_instruction {
            last_count += 1;
        }

        else if let Instruction::Loop(i) = instruction {
            opt.push(OptimizedInstruction::Loop(optimize_multiple(i)));
            last_count = 1;
        }

        else {
            opt.push(OptimizedInstruction::new(last_instruction.clone(), last_count));
            last_instruction = instruction;
            last_count = 1;
        }

    }

    opt

}

这是 OptimizedInstruction 枚举和“新”方法：（Instruction::Loop手只是一个占位符，我没用过）

#[derive(Debug, Clone, PartialEq, Eq)]
pub enum OptimizedInstruction {
    IncrementPointer(usize),
    DecrementPointer(usize),
    Increment(usize),
    Decrement(usize),
    Write,
    Read,
    Loop(Vec<OptimizedInstruction>),
}

impl OptimizedInstruction {
    pub fn new(instruction: Instruction, count: usize) -> OptimizedInstruction {
        match instruction {
            Instruction::IncrementPointer => OptimizedInstruction::IncrementPointer(count),
            Instruction::DecrementPointer => OptimizedInstruction::DecrementPointer(count),
            Instruction::Increment => OptimizedInstruction::Increment(count),
            Instruction::Decrement => OptimizedInstruction::Decrement(count),
            Instruction::Write => OptimizedInstruction::Write,
            Instruction::Read => OptimizedInstruction::Read,
            Instruction::Loop(_i) => OptimizedInstruction::Loop(Vec::new()),
        }
    }
}

我运行它用这个输入： ++-[+-++]

但它给了我这个输出：

[Increment(2), Loop([Increment(1), Decrement(1)])]

安装了这个：

[Increment(2), Decrement(1), Loop([Increment(1), Decrement(1), Increment(2)])]

我已经尝试解决它 2 天了，但我仍然不知道为什么它不起作用。

~德林

Answer 1

首先，为了给你的游行添点麻烦，我只想指出 Wilfred 已经用 Rust 制作了一个 brainf*ck 编译器，它可以通过 LLVM (bfc) 编译为本机二进制文件。如果您遇到困难，您可能需要检查他的实现以了解他是如何做到的。如果忽略 LLVM 部分，通读起来并不难，而且他有一个很好的方法。

当分解成它的核心组件时，这个问题围绕着将两个元素合并在一起。我遇到的解决此问题的最优雅方法是使用具有合并功能的迭代器。我写了一个我想象的例子，如下所示。我缩短了一些变量名，因为它们有点长，但总体思路是一样的。合并功能的工作非常简单。当给定两个元素时，尝试将它们合并为一个新元素。然后迭代器处理将它们放入该函数并在它们不能再合并时返回项目。如果你愿意，可以选择一种折叠方式。

pub struct MergeIter<I: Iterator, F> {
    iter: I,
    func: Box<F>,
    held: Option<<I as Iterator>::Item>,
}

impl<I, F> Iterator for MergeIter<I, F>
where
    I: Iterator,
    F: FnMut(&<I as Iterator>::Item, &<I as Iterator>::Item) -> Option<<I as Iterator>::Item>,
{
    type Item = <I as Iterator>::Item;

    fn next(&mut self) -> Option<Self::Item> {
        let mut first = match self.held.take() {
            Some(v) => v,
            None => self.iter.next()?,
        };

        loop {
            let second = match self.iter.next() {
                Some(v) => v,
                None => return Some(first),
            };

            match (self.func)(&first, &second) {
                // If merge succeeds, attempt to merge again
                Some(v) => first = v,
                // If merge fails, store second value for next iteration and return result
                None => {
                    self.held = Some(second);
                    return Some(first);
                }
            }
        }
    }
}

pub trait ToMergeIter: Iterator {
    fn merge<F>(self, func: F) -> MergeIter<Self, F>
    where
        Self: Sized,
        F: FnMut(&Self::Item, &Self::Item) -> Option<Self::Item>;
}

impl<I: Sized + Iterator> ToMergeIter for I {
    fn merge<F>(self, func: F) -> MergeIter<Self, F>
    where
        Self: Sized,
        F: FnMut(&Self::Item, &Self::Item) -> Option<Self::Item>,
    {
        MergeIter {
            iter: self,
            func: Box::new(func),
            held: None,
        }
    }
}

然后我们可以递归地应用这个过程来得到我们的结果。这是一个简短的示例，说明它的外观。它的内存效率不高，因为它每次都会创建一个新的 Vec，但它使指定要合并的指令的过程对您来说更容易，并有助于使您的工作更容易 read/debug。

pub fn optimize(instructions: Vec<Instruction>) -> Vec<Instruction> {
    instructions
        .into_iter()
        // Recursively call function on loops
        .map(|instruction| match instruction {
            Instruction::Loop(x) => Instruction::Loop(optimize(x)),
            x => x,
        })
        // Merge elements using the merge iter
        .merge(|a, b| {
            // State if any two given elements should be merged together or not.
            match (a, b) {
                (Instruction::IncPtr(x), Instruction::IncPtr(y)) => {
                    Some(Instruction::IncPtr(x + y))
                }
                (Instruction::DecPtr(x), Instruction::DecPtr(y)) => {
                    Some(Instruction::DecPtr(x + y))
                }
                (Instruction::Increment(x), Instruction::Increment(y)) => {
                    Some(Instruction::Increment(x + y))
                }
                (Instruction::Decrement(x), Instruction::Decrement(y)) => {
                    Some(Instruction::Decrement(x + y))
                }
                // Etc...
                _ => None,
            }
        })
        // Collect results to return
        .collect()
}

playground link

如何优化 brainf*ck 指令

How to optimize brainf*ck instructions

algorithm

optimization

interpreter

brainfuck

rust