JIT pour Brainfuck

2023-09-05 2 min read (272 words)

Je n'ai pas d'intérêt pour le Brainfuck, mais j'ai vu cet article (anglais) sur un émulateur de GameBoy avec compilation JIT, qui mentionne un autre article sur la création d'un compilateur JIT pour le Brainfuck, et j'ai fait un émulateur de GameBoy avant, mais j'ai pas envie de lui rajouter un JIT (trop chiant), mais je m'ennuie.

Donc. Je refais le tuto du deuxième article en Rust et j'en parle. (mais pas avant de me rendre compte que Rodrigodd, l'auteur du premier article, a déjà fait sa propre série d'articles sur le même sujet).

Commencer

Je commence dans un projet Rust que j'avais déjà créé pour mettre tout mon bazar, parce que c'est un peu lourd de créer un nouveau projet pour chaque truc.

Je crée un fichier "src/bin/brainfuck_interpreter.rs", qui est l'exécutable de l'interpréteur Brainfuck. Il pourra être lancé avec cargo build --bin brainfuck_interpreter

D'abord, je met une fonction main qui affiche "Hello world!" pour que ça compile :

fn main() {
    println!("Hello world!")
}

Ensuite, je convertis le code C++ de lecture du programme Brainfuck en Rust :

/// Representation of a Brainfuck instruction
enum Instruction {
    PointerRight,
    PointerLeft,
    Increment,
    Decrement,
    Output,
    Input,
    JumpForward,
    JumpBack,
}

impl TryFrom<char> for Instruction {
    type Error = ();

    fn try_from(value: char) -> Result<Self, Self::Error> {
        match value {
            '>' => Ok(Self::PointerRight),
            '<' => Ok(Self::PointerLeft),
            '+' => Ok(Self::Increment),
            '-' => Ok(Self::Decrement),
            '.' => Ok(Self::Output),
            ',' => Ok(Self::Input),
            '[' => Ok(Self::JumpForward),
            ']' => Ok(Self::JumpBack),
            _ => Err(()),
        }
    }
}

/// Representation of a Brainfuck program
struct Program {
    instructions: Vec<Instruction>,
}

impl Program {
    /// Parse the program from a string
    fn parse_from_string(source: &str) -> Self {
        // Parse the program from the source
        let instructions = source
            .chars()
            .filter_map(|c| Instruction::try_from(c).ok())
            .collect();

        Self { instructions }
    }
}

Je n'ai pas trouvé comment boucler sur la lecture de chaque caractère du fichier, donc à la place j'ai une fonction qui prend le code source complet d'un programme Brainfuck en chaîne de caractères. Je ne pense pas qu'il y ait des programmes si gros que ça pose problème.

impl Program {
    ...

    /// Memory size available to the program
    const MEMORY_SIZE: usize = 30_000;

    /// Basic interpreter, no JIT
    fn simple_interpreter(&self, verbose: bool) -> Vec<u8> {
        use std::io::{Read, Write};
        use Instruction::*;

        // Initialize state
        let mut memory = vec![0u8; Self::MEMORY_SIZE];
        let mut pc = 0;
        let mut data_pointer: usize = 0;
        let mut stdin = std::io::stdin();
        let mut stdout = std::io::stdout();

        while pc < self.instructions.len() {
            let instruction = &self.instructions[pc];

            if verbose {
                eprintln!();
                eprintln!("PC: {pc}");
                eprintln!("Instruction: {instruction:?}");
                eprintln!("Data pointer: {data_pointer}");
                eprintln!("Memory: {}", memory[data_pointer]);
            }

            match instruction {
                PointerRight => {
                    data_pointer += 1;
                    if data_pointer >= Self::MEMORY_SIZE {
                        data_pointer = 0;
                    }
                }
                PointerLeft => {
                    data_pointer = data_pointer.wrapping_sub(1).clamp(0, Self::MEMORY_SIZE - 1)
                }
                Increment => memory[data_pointer] = memory[data_pointer].wrapping_add(1),
                Decrement => memory[data_pointer] = memory[data_pointer].wrapping_sub(1),
                Output => {
                    stdout
                        .write_all(&memory[data_pointer..][..1])
                        .expect("failed to write character");
                    stdout.flush().expect("failed to flush STDOUT");
                    // print!("{}", memory[data_pointer]);
                }
                Input => {
                    stdin
                        .read(&mut memory[data_pointer..][..1])
                        .expect("failed to read character");
                    eprintln!("{}", memory[data_pointer])
                }
                JumpForward => {
                    if memory[data_pointer] == 0 {
                        let mut bracket_nesting = 1;
                        let saved_pc = pc;

                        while bracket_nesting > 0 && pc < self.instructions.len() {
                            pc += 1;

                            if matches!(self.instructions[pc], JumpBack) {
                                bracket_nesting -= 1;
                            } else if matches!(self.instructions[pc], JumpForward) {
                                bracket_nesting += 1;
                            }
                        }

                        if bracket_nesting != 0 {
                            panic!("unmatched '[' at pc={saved_pc}");
                        }
                    }
                }
                JumpBack => {
                    if memory[data_pointer] == 0 {
                        let mut bracket_nesting = 1;
                        let saved_pc = pc;

                        while bracket_nesting > 0 && pc > 0 {
                            pc -= 1;

                            if matches!(self.instructions[pc], JumpForward) {
                                bracket_nesting -= 1;
                            } else if matches!(self.instructions[pc], JumpBack) {
                                bracket_nesting += 1;
                            }
                        }

                        if bracket_nesting != 0 {
                            panic!("unmatched ']' at pc={saved_pc}");
                        }
                    }
                }
            }

            pc += 1;
        }

        memory
    }
}

Malheureusement, ce code est buggué. Aucun des deux programmes mentionnés dans l'article originel ne fonctionne, j'ai donc rajouté un test :